LeetCode 409. Longest Palindrome

Oct 4, 2016

题目描述:

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note: Assume the length of given string will not exceed 1,010.

Example:

1
2
3
4
5
6
7
8
Input:
"abccccdd"

Output:
7

Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

给出一个字符数组, 问从中取出字符拼成的回文串最长是多少. 这道题比较简单, 回文串中的字符都是成对出现的, 因此如果一个字母的数量超过了2, 那么它就一定可以放在回文串中, 数量则是必须是偶数奇数的话则减1. 最后看是否还有剩下的字母, 如果有就可以选一个放在中间.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> letters(52, 0);
        for(auto i : s){
            if(i >= 'a' && i <= 'z'){
                letters[i - 'a']++;
            }
            else{
                letters[i - 'A' + 26]++;
            }
        }
        int ans = 0;
        for(auto i : letters){
            if(i > 1){
                ans += i % 2 ? i - 1 : i;
            }
        }
        if(ans < s.length()) ans++;
        return ans;
    }
};

LeetCode 142. Linked List Cycle II

Oct 2, 2016

题目描述:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

同样是使用双指针, 不过要比上一题更进一步. 假设链表有环, 环的长度为m, 去掉环的长度为n(这些节点都一定在环之前), 相遇时快慢指针走过的长度为k和2k. 那么慢指针在环上走过的距离为k-n, 快指针为2k-n, 因为它们指向同一个节点, 所以它们的差k一定是m的整数倍. 因此慢指针只要再走n个节点就会回到进入环的那个节点(k-n+n=k).

虽然我们并不知道m和n的值, 但n是环之前的节点数量, 只要再让一个指针从头结点开始与慢指针同步向前, 当他们相遇时就正好走过了n个节点, 而他们指向的节点就是进入环的节点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next) return nullptr;
        ListNode *p1 = head->next, *p2 = head->next->next;
        while(p1 && p2 && p2->next){
            if(p1 == p2){
                while(true){
                    if(p1 == head) return p1;
                    p1 = p1->next;
                    head = head->next;
                }
            }
            
            p1 = p1->next;
            p2 = p2->next->next;
        }
        return nullptr;
    }
};

LeetCode 141. Linked List Cycle

Oct 2, 2016

题目描述:

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

经典题, 使用快慢指针.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode *p1 = head, *p2 = head->next;
        while(p1 && p2){
            if(p1 == p2) return true;
            p1 = p1->next;
            if(!p2->next){
                return false;
            }
            p2 = p2->next->next;
        }
        return false;
    }
};

LeetCode 140. Word Break II

Oct 2, 2016

题目描述:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

这道题是上一题的升级版. 这道题的主要问题在于在特定情况下解空间很大, 呈指数增长但是最后却无法到达字符串结尾, 这种情况下会超时. 所以可以先用类似上一道题的办法来先确定以第i-1个字符为结尾的子串是否能被分割, 保存在dp[i]中. 这一步之后就可以知道有没有解. 然后再通过从后向前DFS的方法搜索每一个解. 之所以不采用从前向后是因为从前向后搜索的话有可能在最后一步无法正好到达结尾, 而从后往前可以保证这一点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    vector<string> ans;
    int sLen, maxWordLen;
public:
    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        sLen = s.length();
        
        for(auto i : wordDict){
            maxWordLen = max(maxWordLen, (int)i.length());
        }
        
        vector<int> dp(sLen + 1, 0);
        dp[0] = 1;
        for(int i = 0; i <= s.size(); i++){
            for(int j = i - 1; j >= 0 && i - j <= maxWordLen; j--){
                string str = s.substr(j, i - j);
                if(dp[j] && wordDict.count(str)){
                    dp[i] = 1;
                    break;
                }
            }
        }

        if(!dp[sLen]) return ans;
        vector<int> path;
        DFS(dp, path, sLen, s, wordDict);
        return ans;
    }
    
    void DFS(vector<int> &dp, vector<int> &path, int index, string &s, unordered_set<string>& wordDict){
        if(index == 0){
            string str;
            int lastIndex = 0;
            for(auto i = path.rbegin(); i != path.rend(); i++){
                str += s.substr(lastIndex, (*i) - lastIndex);
                str += " ";
                lastIndex = *i;
            }
            if(!str.empty())str.pop_back();
            ans.push_back(str);
            return;
        }
        path.push_back(index);
        for(int j = index - 1; j >= 0 && index - j <= maxWordLen; j--){
            if(dp[j] && wordDict.count(s.substr(j, index - j))){
                DFS(dp, path, j, s, wordDict);
            }
        }
        path.pop_back();
    }
};

LeetCode 139. Word Break

Sep 29, 2016

题目描述:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

使用DP, 从前到后遍历字符串, 记录下可以分割的坐标(也就是从开头到该坐标的子串是可以被分割的). 对于每增加一个字母, 判断每个被记录的坐标到该字母所组成的子串是否在dict中, 如果在, 那么这个坐标也是可以分割的. 最后判断所记录的坐标的最后一个是不是字符串的结尾.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        vector<int> trueIndex;
        for(int i = 0; i < s.size(); i++){
            for(auto j = trueIndex.rbegin(); j != trueIndex.rend(); j++){
                if(wordDict.count(s.substr(*j + 1, i - *j))){
                    trueIndex.push_back(i);
                    break;
                }
            }
            if((trueIndex.empty() || trueIndex.back() != i) && wordDict.count(s.substr(0, i + 1))) trueIndex.push_back(i);
        }
        return !trueIndex.empty() && trueIndex.back() == (s.length() - 1);
    }
};

LeetCode 138. Copy List with Random Pointer

Sep 29, 2016

题目描述:

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

这是一个单纯的哈希表问题, 不知道为什么归类为hard. 首先遍历一次链表进行拷贝, 同时建立原链表节点到新链表节点的映射关系, 再遍历一次新链表更新random的值即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode*, RandomListNode*> m;
        if(!head) return nullptr;
        RandomListNode *p = head, *newHead = new RandomListNode(head->label), *np = newHead;
        while(p){
            if(p->next)
                np->next = new RandomListNode(p->next->label);
            np->random = p->random;
            m[p] = np;
            p = p->next;
            np = np->next;
        }
        
        p = newHead;
        while(p){
            if(p->random){
                p->random = m[p->random];
            }
            p = p->next;
        }
        
        return newHead;
    }
};

LeetCode 137. Single Number II

Sep 29, 2016

题目描述:

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

最简单的方法是使用哈希表. 但是要不使用额外空间就要用位运算的方法, 思路是除了要找的元素外, 每个数字都重复了三次, 所以32-bit整数中的每一位出现1的总次数是3的倍数, 找出出现次数不是3的倍数的位, 就是要找的数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return useBit(nums);
    }
    
    int useMap(vector<int> &nums){
        // 使用哈希表的方法
        unordered_map<int, int> m;
        for(int i = 0; i < nums.size(); i++){
            if(++m[nums[i]] == 3) m.erase(nums[i]);
        }
        return m.begin()->first;
    }
    
    int useBit(vector<int> &nums){
        // 使用位运算的方法
        int re = 0;
        for(int i = 0; i < 32; i++){
            int b = 1 << i;
            int n = 0;
            for(int i = 0; i < nums.size(); i++){
                if(nums[i] & b) n++;
            }
            if(n % 3) re |= b;
        }
        return re;
    }
};

LeetCode 407. Trapping Rain Water II

Sep 28, 2016

题目描述:

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note: Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

1
2
3
4
5
6
7
8
9
Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

img The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

img After the rain, water are trapped between the blocks. The total volume of water trapped is 4.

这道题对于时间复杂度要求比较高, 轻易就会超时. 我的解法Runtime也不是很短, 有100多ms, 所以权当参考吧.

首先简单的对三维空间进行BFS是绝对超时, 因为最多有110*110*20000个坐标. 我一开始是使用分层进行BFS的办法, 确定每一层中不能装水的位置有多少. 之所以是搜索哪些不能装水而不是哪些能装水是因为搜索与边缘连通的位置只要从四条边开始搜索, 而搜索不与边缘连通的位置要从每个非边缘位置搜索, 数量要多得多.

有两种坐标是不能装水的:

  1. 与边缘连通的
  2. 该位置的高度比层数高的

拿总的面积减去不能装水的面积就是有水的面积, 把每一层的面积加起来就是最终的装水的体积. 但是这个办法是超时了, 我总结的超时原因是对每一层都从边缘开始BFS, 实际上并不需要每次都从最初始的情况开始BFS, 而可以在上一层的基础上进行BFS.

当层数为level的时候, 我们要检查的是height==level-1的坐标, 因为height>=level的坐标不能装水, 而height<level-1的坐标在之前的level已经计算过了, 那么对于所有的height==level-1的坐标有两种情况: 能存水和不能存水. 而区分条件是是否与边缘连通, 在知道上一层每个坐标与边缘连通情况(一个二维数组)的时候, 只要判断四周的坐标是否与边缘连通即可(因为已经不能存水的位置随着高度增加永远不能存水), 如果出现了一个height==level-1的坐标与边缘连通的情况, 那么就从这个点开始BFS, 能到达的坐标都是不能存水的.

在这种方法中, 二维平面上的每个点只有一次被BFS遍历到的机会, 大大降低了时间复杂度.

关于二维坐标表示: 二维坐标可以用pair来表示, 但是处理一个对象总没有用int来的快, 这道题由于长宽最大只有110, 所以完全可以把x,y坐标保存在一个int型中, 前16位保存x, 后16位保存y. int xy=x<<16|y, int x = xy>>16, y=xy&0xff.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class Solution {
    int m, n, area;
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int ans = 0;
        m = heightMap.size();
        if(m == 0) return 0;
        n = heightMap[0].size();
        area = n * m; // 每一层的总面积
        
        priority_queue<int, vector<int>, greater<int>> pq; // 保存所有的高度
        unordered_map<int, vector<int>> hm; // 保存每一个高度对应的所有坐标
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                pq.push(heightMap[i][j]);
                hm[heightMap[i][j]].push_back(xy2int(i, j));
            }
        }
        // 以下处理最底层, 生成初始的visited数组
        vector<vector<int>> visited(m, vector<int>(n, 0));
        int edgeArea = 0;
        for(int i = 0; i < n; i++){
            if(!visited[0][i]) edgeArea += BFS(heightMap, 0, i, pq.top() + 1, visited);
            if(!visited[m - 1][i]) edgeArea += BFS(heightMap, m - 1, i, pq.top() + 1, visited);
        }
        for(int i = 0; i < m; i++){
            if(!visited[i][0]) edgeArea += BFS(heightMap, i, 0, pq.top() + 1, visited);
            if(!visited[i][n - 1]) edgeArea += BFS(heightMap, i, n - 1, pq.top() + 1, visited);
        }
        // 以下先得到下一层的高度, 然后用高度差乘本层的装水面积得到两层之间总得装水体积
        // 下面的循环中对每一层都做这样的处理
        int t = pq.top();
        while(!pq.empty() && pq.top() == t) pq.pop(); 
        if(!pq.empty()){
            int higherArea = pq.size();
            // higherArea表示的是高度比当前层高的格子数
            // edgeArea是与边缘连通的格子数
            // pq.top() - t得到高度差
            ans += (area - higherArea - edgeArea) * (pq.top() - t);
        }
        // 处理上层
        while(!pq.empty()){
            int level = pq.top() + 1;
            vector<int> &h = hm[level - 1];
            for(auto i : h){
                int x = i >> 16, y = i & 0xff;
                if(!visited[x][y] && (besideEdge(x, y, visited) || onEdge(x, y))){
                    // 没有被标记与边缘连通但是四周有与边缘连通的坐标或者自己就在边上
                    edgeArea += BFS(heightMap, x, y, level, visited);
                }
            }
            
            while(!pq.empty() && pq.top() == level - 1) pq.pop();
            if(pq.empty()) break;
            int higherArea = pq.size();
            ans += (area - higherArea - edgeArea) * (pq.top() - level + 1);
        }
        
        return ans;
    }
    
    int xy2int(int x, int y){
        return x << 16 | y;
    }
    
    bool besideEdge(int x, int y, vector<vector<int>> &visited){
        // 判断四周是否被标记为与边缘连通
        return ((x > 0 && visited[x - 1][y]) || 
           (x < m - 1 && visited[x + 1][y]) || 
           (y > 0 && visited[x][y - 1]) ||
           (y < n - 1 && visited[x][y + 1]));
    }
    
    int BFS(vector<vector<int>>& heightMap, int i, int j, int k, vector<vector<int>> &visited){
        // 广度优先搜索
        int ans = 0;
        if(heightMap[i][j] >= k) return 0;
        queue<int> q;
        q.push(xy2int(i, j));
        visited[i][j] = 1;
        while(!q.empty()){
            int curi = q.front() >> 16, curj = q.front() & 0xff;
            ans++;
            if(curi > 0 && !visited[curi - 1][curj] && heightMap[curi - 1][curj] < k){
                q.push(xy2int(curi - 1, curj));
                visited[curi - 1][curj] = 1;
            }
            if(curi < m - 1 && !visited[curi + 1][curj] && heightMap[curi + 1][curj] < k){
                q.push(xy2int(curi + 1, curj));
                visited[curi + 1][curj] = 1;
            }
            if(curj > 0 && !visited[curi][curj - 1] && heightMap[curi][curj - 1] < k){
                q.push(xy2int(curi, curj - 1));
                visited[curi][curj - 1] = 1;
            }
            if(curj < n - 1 && !visited[curi][curj + 1] && heightMap[curi][curj + 1] < k){
                q.push(xy2int(curi, curj + 1));
                visited[curi][curj + 1] = 1;
            }
            q.pop();
        }
        return ans;
    }
    
    bool onEdge(int i, int j){
        return i == 0 || j == 0 || i == m - 1 || j == n - 1;
    }
};

LeetCode 136. Single Number

Sep 28, 2016

题目描述:

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

使用异或.

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(auto i : nums){
            ans ^= i;
        }
        return ans;
    }
};