Leetcode201 - 300

Posted on

Leetcode201. Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

1
2
Input: left = 5, right = 7
Output: 4

Example 2:

1
2
Input: left = 0, right = 0
Output: 0

Example 3:

1
2
Input: left = 1, right = 2147483647
Output: 0

我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可，我们可以从建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与就是最终结果，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int i = 0;
        while(left > 0 && right > 0) {
            if (left == right)
                break;
            left >>= 1;
            right >>= 1;
            i ++;
        }
        return left << i;
    }
};

Leetcode202. Happy Number

Write an algorithm to determine if a number n is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example:

1
2
3
4
5
6
7
Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 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:
    bool isHappy(int n) {
        int cycle = 100, sum;
        vector<int> nums;
        while(cycle--) {
            int temp = n;
            nums.clear();
            while(temp) {
                nums.push_back(temp%10);
                temp /= 10;
            }
            sum = 0;
            for(int i : nums)
                sum += i*i;
            if(sum == 1)
                return true;
            n = sum;
        }
        return false;
    }
};

对于一个数n，如果n不是Happy Number，那么在求n各数位平方和以及求在n之后的每个数的各数位平方和的过程中，一定会产生循环，利用这个性质：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isHappy(int n) {
        map<int,int> thash;
        while(n && !thash[n]){
            thash[n] = n;
            int temp = 0, low;
            while(n) {
                low = n % 10;
                temp += low * low;
                n /= 10;
            }
            n = temp;
        }
        if(n == 1){
            return true;
        }
        return false;
    }
};

Leetcode203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

删除列表中对应val的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *ptr = new ListNode(-1);
        ListNode *prev, *cur;
        ptr->next = head;
        cur = head;
        prev = ptr;
        while(cur != NULL) {
            if(cur->val == val)
                prev->next = cur->next;
            else
                prev = cur;
            cur = cur->next;
        }
        return ptr->next;
    }
};

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
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val)
    {
        vector<int> v;
        ListNode* a = head;
        while(a != NULL) {
            v.push_back(a->val);
            a = a->next;
        }
        vector<int> y;
        int s = v.size();
        for(int i = 0; i < s; i ++) {
            if(v[i] != val) {
                y.push_back(v[i]);
            }
        }

        reverse(y.begin(),y.end());
        int n = y.size();
        ListNode* z = new ListNode(0);
        ListNode* p = z;
        for(int i = 0; i < n; i ++) {
            p->next = new ListNode(y.back());
            y.pop_back();
            p = p->next;
        }
        return z->next;
    }
};

Leetcode204. Count Primes

Count the number of prime numbers less than a non-negative number, n.

Example:

1
2
3
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

判断一定范围内有几个合数，下边这个简单的做法会超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    
    bool isprimes(int n) {
        for(int i = 2; i <= n/2; i ++){
            if(n % i == 0)
                return false;
        }
        return true;
    }
    
    int countPrimes(int n) {
        int sum = 0;
        for(int i = 2; i < n; i ++)
            if(isprimes(i))
                sum ++;
        return sum;
    }
};

所以要用其他的方法，比如素数筛
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:

    int countPrimes(int n) {
        int sum = 0;
        if(n < 2)
            return 0;
        int nn = sqrt(n);
        bool prime[n];
        for(int i = 0; i < n; i ++)
            prime[i] = true;
        prime[0] = prime[1] = false;
        for(int i = 2; i <= nn; i ++) {
            for(int j = i*2; j < n; j += i) {
                prime[j] = false;
            }
        }
        for(int i = 2; i < n; i ++) {
            if(prime[i])
                sum ++;
        }
        return sum;
    }
};

Leetcode205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

1
2
Input: s = "egg", t = "add"
Output: true

Example 2:
1
2
Input: s = "foo", t = "bar"
Output: false

Example 3:
1
2
Input: s = "paper", t = "title"
Output: true

这道题让我们求同构字符串，就是说原字符串中的每个字符可由另外一个字符替代，可以被其本身替代，相同的字符一定要被同一个字符替代，且一个字符不能被多个字符替代，即不能出现一对多的映射。根据一对一映射的特点，需要用两个 HashMap 分别来记录原字符串和目标字符串中字符出现情况，由于 ASCII 码只有 256 个字符，所以可以用一个 256 大小的数组来代替 HashMap，并初始化为0，遍历原字符串，分别从源字符串和目标字符串取出一个字符，然后分别在两个数组中查找其值，若不相等，则返回 false，若相等，将其值更新为 i + 1，因为默认的值是0，所以更新值为 i + 1，这样当 i=0 时，则映射为1，如果不加1的话，那么就无法区分是否更新了。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] = i + 1;
            m2[t[i]] = i + 1;
        }
        return true;
    }
};

另一种使用两个unorder_map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int ssize = s.size(), tsize = t.size();
        if(ssize != tsize)
            return false;
        map<char, char> mp, mp2;
        for(int i = 0; i < ssize; i ++) {
            if(mp.find(s[i]) == mp.end())
                mp[s[i]] = t[i];
            else if(mp[s[i]] != t[i])
                return false;
            if(mp2.find(t[i]) == mp2.end())
                mp2[t[i]] = s[i];
            else if(mp2[t[i]] != s[i])
                return false;
        }
        return true;
    }
};

Leetcode206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

假设存在链表 1 -> 2 -> 3 -> NULL，我们想要把它改成 NULL <- 1 <- 2 <- 3。

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev,*next,*curr;
        curr=head;
        prev = NULL;
        while(curr!=NULL){
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

Leetcode207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

1
2
3
4
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:
1
2
3
4
5
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.
  • 1 <= numCourses <= 10^5

定义二维数组 graph 来表示这个有向图，一维数组 in 来表示每个顶点的入度。开始先根据输入来建立这个有向图，并将入度数组也初始化好。然后定义一个 queue 变量，将所有入度为0的点放入队列中，然后开始遍历队列，从 graph 里遍历其连接的点，每到达一个新节点，将其入度减一，如果此时该点入度为0，则放入队列末尾。直到遍历完队列中所有的值，若此时还有节点的入度不为0，则说明环存在，返回 false，反之则返回 true。

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
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
        int in[numCourses];
        for(int i = 0; i < numCourses; i ++)
            in[i] = 0;
        for(auto i : prerequisites) {
            graph[i[1]][i[0]] = 1;
            in[i[0]] ++;
        }
        queue<int> q;
        for(int i = 0; i < numCourses; i ++)
            if(in[i] == 0)
                q.push(i);
        while(!q.empty()) {
            int temp = q.front();
            q.pop();
            for(int i = 0; i < numCourses; i ++) {
                if(graph[temp][i] == 1) {
                    in[i]--;
                    if(in[i] == 0)
                        q.push(i);   
                }
            }
        }
        for(int i = 0; i < numCourses; i ++)
            if(in[i] != 0)
                return false;
        return true;
    }
};

Leetcode208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Example:

1
2
3
4
5
6
7
8
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

实现一个字典树即可

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
class Trie {
private:
    struct Node{
        Node *next[26];
        bool isleaf;
        Node(){
            for(int i=0;i<26;i++)
                next[i]=NULL;
            isleaf=false;
        }
    };
    Node* head;
    
public:
    /** Initialize your data structure here. */
    Trie() {
        head = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Node* current = head;
        for(int i=0;i<word.size();i++){
            int index = word[i]-'a';
            if(current->next[index]==NULL){
                current->next[index] = new Node();
            }
            current = current->next[index];
        }
        current->isleaf = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* current = head;
        for(int i=0;i<word.size();i++){
            int index = word[i]-'a';
            if(current->next[index]==NULL)
                return false;
            else
                current = current->next[index];
        }
        return current->isleaf;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* current = head;
        for(int i=0;i<prefix.size();i++){
            int index = prefix[i]-'a';
            if(current->next[index]==NULL)
                return false;
            else
                current = current->next[index];
        }
        return true;
    }
};

这个实现的内存占用有些高了，抄一下其他人的
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 TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch -'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch -'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
    }
    public void setEnd() {
        isEnd = true;
    }
    public boolean isEnd() {
        return isEnd;
    }
}

Insertion of a key to a trie
We insert a key by searching into the trie. We start from the root and search a link, which corresponds to the first key character. There are two cases :

A link exists. Then we move down the tree following the link to the next child level. The algorithm continues with searching for the next key character.
A link does not exist. Then we create a new node and link it with the parent’s link matching the current key character. We repeat this step until we encounter the last character of the key, then we mark the current node as an end node and the algorithm finishes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }
}

Search for a key in a trie
Each key is represented in the trie as a path from the root to the internal node or leaf. We start from the root with the first key character. We examine the current node for a link corresponding to the key character. There are two cases :

A link exist. We move to the next node in the path following this link, and proceed searching for the next key character.

A link does not exist. If there are no available key characters and current node is marked as isEnd we return true. Otherwise there are possible two cases in each of them we return false :

There are key characters left, but it is impossible to follow the key path in the trie, and the key is missing.
No key characters left, but current node is not marked as isEnd. Therefore the search key is only a prefix of another key in the trie.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Trie {
    ...

    // search a prefix or whole key in trie and
    // returns the node where search ends
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
           char curLetter = word.charAt(i);
           if (node.containsKey(curLetter)) {
               node = node.get(curLetter);
           } else {
               return null;
           }
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
       TrieNode node = searchPrefix(word);
       return node != null && node.isEnd();
    }
}

Search for a key prefix in a trie
The approach is very similar to the one we used for searching a key in a trie. We traverse the trie from the root, till there are no characters left in key prefix or it is impossible to continue the path in the trie with the current key character. The only difference with the mentioned above search for a key algorithm is that when we come to an end of the key prefix, we always return true. We don’t need to consider the isEnd mark of the current trie node, because we are searching for a prefix of a key, not for a whole key.

1
2
3
4
5
6
7
8
9
10
class Trie {
    ...

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}

Leetcode209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

1
2
3
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

1
2
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

1
2
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

需要定义两个指针 left 和 right，分别记录子数组的左右的边界位置，然后让 right 向右移，直到子数组和大于等于给定值或者 right 达到数组末尾，此时更新最短距离，并且将 left 像右移一位，然后再 sum 中减去移去的值，然后重复上面的步骤，直到 right 到达末尾，且 left 到达临界位置，即要么到达边界，要么再往右移动，和就会小于给定值。

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 minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        if (len == 0)
            return 0;
        int left = 0, right = 0;
        int sum = 0, res = INT_MAX;
        
        while(right < len) {
            while(right < len && sum < target) {
                sum += nums[right++];
            }
            while(sum >= target) {
                res = min(res, right-left);
                sum -= nums[left++];
            }
        }
        
        return res == INT_MAX ? 0 : res;
    }
};

Leetcode210. Course Schedule II

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

1
2
3
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

1
2
3
4
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

1
2
Input: numCourses = 1, prerequisites = []
Output: [0]

这道题我们得找出要上的课程的顺序，即有向图的拓扑排序 Topological Sort，从 queue 中每取出一个数组就将其存在结果中，最终若有向图中有环，则结果中元素的个数不等于总课程数，那我们将结果清空即可。

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
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res;
        vector<vector<int> > graph(numCourses, vector<int>(0));
        vector<int> in(numCourses, 0);
        for (auto &a : prerequisites) {
            graph[a.second].push_back(a.first);
            ++in[a.first];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()) {
            int t = q.front();
            res.push_back(t);
            q.pop();
            for (auto &a : graph[t]) {
                --in[a];
                if (in[a] == 0) q.push(a);
            }
        }
        if (res.size() != numCourses) res.clear();
        return res;
    }
};

Leetcode212.Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

1
2
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

1
2
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.

这道题是在之前那道 Word Search 的基础上做了些拓展，之前是给一个单词让判断是否存在，现在是给了一堆单词，让返回所有存在的单词，在这道题最开始更新的几个小时内，用 brute force 是可以通过 OJ 的，就是在之前那题的基础上多加一个 for 循环而已，但是后来出题者其实是想考察字典树的应用，所以加了一个超大的 test case，以至于 brute force 无法通过，强制我们必须要用字典树来求解。LeetCode 中有关字典树的题还有 Implement Trie (Prefix Tree) 和 Add and Search Word - Data structure design，那么我们在这题中只要实现字典树中的 insert 功能就行了，查找单词和前缀就没有必要了，然后 DFS 的思路跟之前那道 Word Search 基本相同，请参见代码如下：

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
class Solution {
public:
    struct TrieNode {
        TrieNode *child[26];
        string str;
    };
    struct Trie {
        TrieNode *root;
        Trie() : root(new TrieNode()) {}
        void insert(string s) {
            TrieNode *p = root;
            for (auto &a : s) {
                int i = a - 'a';
                if (!p->child[i]) p->child[i] = new TrieNode();
                p = p->child[i];
            }
            p->str = s;
        }
    };
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> res;
        if (words.empty() || board.empty() || board[0].empty()) return res;
        vector<vector<bool>> visit(board.size(), vector<bool>(board[0].size(), false));
        Trie T;
        for (auto &a : words) T.insert(a);
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (T.root->child[board[i][j] - 'a']) {
                    search(board, T.root->child[board[i][j] - 'a'], i, j, visit, res);
                }
            }
        }
        return res;
    }
    void search(vector<vector<char>>& board, TrieNode* p, int i, int j, vector<vector<bool>>& visit, vector<string>& res) { 
        if (!p->str.empty()) {
            res.push_back(p->str);
            p->str.clear();
        }
        int d[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        visit[i][j] = true;
        for (auto &a : d) {
            int nx = a[0] + i, ny = a[1] + j;
            if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size() && !visit[nx][ny] && p->child[board[nx][ny] - 'a']) {
                search(board, p->child[board[nx][ny] - 'a'], nx, ny, visit, res);
            }
        }
        visit[i][j] = false;
    }
};

Leetcode213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

1
2
3
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

1
2
3
4
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

1
2
Input: nums = [0]
Output: 0

现在房子排成了一个圆圈，则如果抢了第一家，就不能抢最后一家，因为首尾相连了，所以第一家和最后一家只能抢其中的一家，或者都不抢，那这里变通一下，如果把第一家和最后一家分别去掉，各算一遍能抢的最大值，然后比较两个值取其中较大的一个即为所求。那只需参考之前的 House Robber 中的解题方法，然后调用两边取较大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        if (nums.size() == 1)
            return nums[0];
        return max(robb(nums, 0, nums.size()-1), robb(nums, 1, nums.size()));
    }
    
    int robb(vector<int>& nums, int l, int r) {
        if (r-l <= 1)
            return nums[l];
        vector<int> dp(r, 0);
        
        dp[l] = nums[l];
        dp[l+1] = max(nums[l], nums[l+1]);
        for (int i = l+2; i < r; i ++) {
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[r-1];
    }
};

当然，我们也可以使用两个变量来代替整个 DP 数组，讲解与之前的帖子 House Robber 相同，分别维护两个变量 robEven 和 robOdd，顾名思义，robEven 就是要抢偶数位置的房子，robOdd 就是要抢奇数位置的房子。所以在遍历房子数组时，如果是偶数位置，那么 robEven 就要加上当前数字，然后和 robOdd 比较，取较大的来更新 robEven。这里就看出来了，robEven 组成的值并不是只由偶数位置的数字，只是当前要抢偶数位置而已。同理，当奇数位置时，robOdd 加上当前数字和 robEven 比较，取较大值来更新 robOdd，这种按奇偶分别来更新的方法，可以保证组成最大和的数字不相邻，最后别忘了在 robEven 和 robOdd 种取较大值返回，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() <= 1) return nums.empty() ? 0 : nums[0];
        return max(rob(nums, 0, nums.size() - 1), rob(nums, 1, nums.size()));
    }
    int rob(vector<int> &nums, int left, int right) {
        int robEven = 0, robOdd = 0;
        for (int i = left; i < right; ++i) {
            if (i % 2 == 0) {
                robEven = max(robEven + nums[i], robOdd);
            } else {
                robOdd = max(robEven, robOdd + nums[i]);
            }
        }
        return max(robEven, robOdd);
    }
};

Leetcode215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.

这道题让我们求数组中第k大的数字，怎么求呢，当然首先想到的是给数组排序，然后求可以得到第k大的数字。先看一种利用 C++ 的 STL 中的集成的排序方法，不用我们自己实现，这样的话这道题只要两行就完事了，代码如下：

1
2
3
4
5
6
7
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

下面这种解法是利用了 priority_queue 的自动排序的特性，跟上面的解法思路上没有什么区别，当然我们也可以换成 multiset 来做，一个道理，参见代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> q(nums.begin(), nums.end());
        for (int i = 0; i < k - 1; ++i) {
            q.pop();
        }
        return q.top();
    }
};

这道题最好的解法应该是下面这种做法，用到了快速排序 Quick Sort 的思想，这里排序的方向是从大往小排。对快排不熟悉的童鞋们随意上网搜些帖子看下吧，多如牛毛啊，总有一款适合你。核心思想是每次都要先找一个中枢点 Pivot，然后遍历其他所有的数字，像这道题从大往小排的话，就把大于中枢点的数字放到左半边，把小于中枢点的放在右半边，这样中枢点是整个数组中第几大的数字就确定了，虽然左右两部分各自不一定是完全有序的，但是并不影响本题要求的结果，因为左半部分的所有值都大于右半部分的任意值，所以我们求出中枢点的位置，如果正好是 k-1，那么直接返回该位置上的数字；如果大于 k-1，说明要求的数字在左半部分，更新右边界，再求新的中枢点位置；反之则更新右半部分，求中枢点的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        while (true) {
            int pos = partition(nums, left, right);
            if (pos == k - 1) return nums[pos];
            if (pos > k - 1) right = pos - 1;
            else left = pos + 1;
        }
    }
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left], l = left + 1, r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot) {
                swap(nums[l++], nums[r--]);
            }
            if (nums[l] >= pivot) ++l;
            if (nums[r] <= pivot) --r;
        }
        swap(nums[left], nums[r]);
        return r;
    }
};

Leetcode216. Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

1
2
3
4
5
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

1
2
3
4
5
6
7
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

n是k个数字之和，如果n小于0，则直接返回，如果n正好等于0，而且此时out中数字的个数正好为k，说明此时是一个正确解，将其存入结果res中，具体实现参见代码入下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > res;
        vector<int> out;
        combinationSum3DFS(k, n, 1, out, res);
        return res;
    }
    void combinationSum3DFS(int k, int n, int level, vector<int> &out, vector<vector<int> > &res) {
        if (n < 0) return;
        if (n == 0 && out.size() == k) res.push_back(out);
        for (int i = level; i <= 9; ++i) {
            out.push_back(i);
            combinationSum3DFS(k, n - i, i + 1, out, res);
            out.pop_back();
        }
    }
};

Leetcode217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

1
2
Input: [1,2,3,1]
Output: true

Example 2:
1
2
Input: [1,2,3,4]
Output: false

Example 3:
1
2
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

构造一个set，不重复就加进去，重复返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        set<int> s;
        if(nums.size() == 0)
            return false;
        s.insert(nums[0]);
        for(int i = 1; i < nums.size(); i ++) {
            if(s.count(nums[i]))
                return true;
            else
                s.insert(nums[i]);
        }
        return false;
    }
};

还有一个是排序
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]==nums[i-1])
                return true;
        }
        return false;
    }
};

Leetcode218. The Skyline Problem

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]

这里用到了 multiset 数据结构，其好处在于其中的元素是按堆排好序的，插入新元素进去还是有序的，而且执行删除元素也可方便的将元素删掉。这里为了区分左右边界，将左边界的高度存为负数，建立左边界和负高度的 pair，再建立右边界和高度的 pair，存入数组中，都存进去了以后，给数组按照左边界排序，这样就可以按顺序来处理那些关键的节点了。在 multiset 中放入一个0，这样在某个没有和其他建筑重叠的右边界上，就可以将封闭点存入结果 res 中。下面按顺序遍历这些关键节点，如果遇到高度为负值的 pair，说明是左边界，那么将正高度加入 multiset 中，然后取出此时集合中最高的高度，即最后一个数字，然后看是否跟 pre 相同，这里的 pre 是上一个状态的高度，初始化为0，所以第一个左边界的高度绝对不为0，所以肯定会存入结果 res 中。接下来如果碰到了一个更高的楼的左边界的话，新高度存入 multiset 的话会排在最后面，那么此时 cur 取来也跟 pre 不同，可以将新的左边界点加入结果 res。第三个点遇到绿色建筑的左边界点时，由于其高度低于红色的楼，所以 cur 取出来还是红色楼的高度，跟 pre 相同，直接跳过。下面遇到红色楼的右边界，此时首先将红色楼的高度从 multiset 中删除，那么此时 cur 取出的绿色楼的高度就是最高啦，跟 pre 不同，则可以将红楼的右边界横坐标和绿楼的高度组成 pair 加到结果 res 中，这样就成功的找到我们需要的拐点啦，后面都是这样类似的情况。当某个右边界点没有跟任何楼重叠的话，删掉当前的高度，那么 multiset 中就只剩0了，所以跟当前的右边界横坐标组成pair就是封闭点啦，具体实现参看代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
   vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> h, res;
        multiset<int> m;
        int pre = 0, cur = 0;
        for (auto &a : buildings) {
            h.push_back({a[0], -a[2]});
           h.push_back({a[1], a[2]});
        }
        sort(h.begin(), h.end());
        m.insert(0);
        for (auto &a : h) {
            if (a.second < 0) m.insert(-a.second);
            else m.erase(m.find(a.second));
            cur = *m.rbegin();
            if (cur != pre) {
                res.push_back({a.first, cur});
                pre = cur;
            }
        }
        return res;
    }
};

Leetcode219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:
1
2
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:
1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int, int> mp;
        if(nums.size() == 0)
            return false;
        for(int i = 0; i < nums.size(); i ++) {
            if(mp.find(nums[i]) == mp.end()) 
                mp[nums[i]] = i;
            else if(i - mp[nums[i]] <= k)
                return true;
            else 
                mp[nums[i]] = i;
        }
        return false;
    }
};

Leetcode221. Maximal Square

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example 1:

1
2
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

1
2
Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

1
2
Input: matrix = [["0"]]
Output: 0

类似85题，注意是正方形。

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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int width = matrix.size();
        if (width == 0)
            return 0;
        int height = matrix[0].size();
        int res = 0;
        vector<vector<int>> dp(width, vector<int>(height, 0));
        for (int i = 0; i < width; i ++) {
            for (int j = 0; j < height; j ++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = j == 0 ? 1 : dp[i][j-1]+1;
                    int length = dp[i][j];
                    for (int k = i; k >= 0; k --) {
                        length = min(length, dp[k][j]);
                        if ((i-k+1) == length)
                            res = max(res, (i-k+1)*length);
                    }
                }
            }
        }
        return res;
    }
};

来个效率高的：

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 maximalSquare(vector<vector<char>>& matrix) {
        int width = matrix.size();
        if (width == 0)
            return 0;
        int height = matrix[0].size();
        int res = 0;
        vector<vector<int>> dp(width, vector<int>(height, 0));
        for (int i = 0; i < width; i ++) {
            for (int j = 0; j < height; j ++) {
                if (i == 0 || j == 0)
                    dp[i][j] = matrix[i][j] - '0';
                else if (matrix[i][j] == '1') {
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
                }
                res = max(res, dp[i][j]);
            }
        }
        return res*res;
    }
};

Leetcode222. Count Complete Tree Nodes

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

这道题给定了一棵完全二叉树，让我们求其节点的个数。最暴力的解法就是直接用递归来统计结点的个数，根本不需要考虑什么完全二叉树还是完美二叉树，

1
2
3
4
5
6
class Solution {
public:
    int countNodes(TreeNode* root) {
        return root ? (1 + countNodes(root->left) + countNodes(root->right)) : 0;
    }
};

完美二叉树一定是完全二叉树，而完全二叉树不一定是完美二叉树。那么这道题给的完全二叉树就有可能是完美二叉树，若是完美二叉树，节点个数很好求，为2的h次方减1，h为该完美二叉树的高度。若不是的话，只能老老实实的一个一个数结点了。思路是由 root 根结点往下，分别找最靠左边和最靠右边的路径长度，如果长度相等，则证明二叉树最后一层节点是满的，是满二叉树，直接返回节点个数，如果不相等，则节点个数为左子树的节点个数加上右子树的节点个数再加1(根节点)，其中左右子树节点个数的计算可以使用递归来计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countNodes(TreeNode* root) {
        int hLeft = 0, hRight = 0;
        TreeNode *pLeft = root, *pRight = root;
        while (pLeft) {
            ++hLeft;
            pLeft = pLeft->left;
        }
        while (pRight) {
            ++hRight;
            pRight = pRight->right;
        }
        if (hLeft == hRight) return pow(2, hLeft) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

Leetcode223. Rectangle Area

Find the total area covered by two rectilinearrectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

1
2
Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

Note:

Assume that the total area is never beyond the maximum possible value of int.

尝试先找出所有的不相交的情况，只有四种，一个矩形在另一个的上下左右四个位置不重叠，这四种情况下返回两个矩形面积之和。其他所有情况下两个矩形是有交集的，这时候只要算出长和宽，即可求出交集区域的大小，然后从两个矩型面积之和中减去交集面积就是最终答案。求交集区域的长和宽也不难，由于交集都是在中间，所以横边的左端点是两个矩形左顶点横坐标的较大值，右端点是两个矩形右顶点的较小值，同理，竖边的下端点是两个矩形下顶点纵坐标的较大值，上端点是两个矩形上顶点纵坐标的较小值。

1
2
3
4
5
6
7
8
class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int sum1 = (C - A) * (D - B), sum2 = (H - F) * (G - E);
        if (E >= C || F >= D || B >= H || A >= G) return sum1 + sum2;
        return sum1 - ((min(G, C) - max(A, E)) * (min(D, H) - max(B, F))) + sum2;
    }
};

我自己的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int inter_x1 = max(ax1, bx1);
        int inter_x2 = min(ax2, bx2);
        int inter_y1 = max(ay1, by1);
        int inter_y2 = min(ay2, by2);
        
        int total_area = (ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1);
        if (bx1 > ax2 || by2 < ay1 || bx2 < ax1 || by1 > ay2)
            return total_area;
        else
            return total_area - (inter_x2-inter_x1)*(inter_y2-inter_y1);
    }
};

Leetcode224. Basic Calculator

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

1
2
Input: s = "1 + 1"
Output: 2

Example 2:

1
2
Input: s = " 2-1 + 2 "
Output: 3

Example 3:

1
2
Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of digits, ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘.
  • s represents a valid expression.
  • ‘+’ is not used as a unary operation (i.e., “+1” and “+(2 + 3)” is invalid).
  • ‘-‘ could be used as a unary operation (i.e., “-1” and “-(2 + 3)” is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

这道题让我们实现一个基本的计算器来计算简单的算数表达式，而且题目限制了表达式中只有加减号，数字，括号和空格，没有乘除，那么就没啥计算的优先级之分了。于是这道题就变的没有那么复杂了。我们需要一个栈来辅助计算，用个变量sign来表示当前的符号，我们遍历给定的字符串s，如果遇到了数字，由于可能是个多位数，所以我们要用while循环把之后的数字都读进来，然后用sign*num来更新结果res；如果遇到了加号，则sign赋为1，如果遇到了符号，则赋为-1；如果遇到了左括号，则把当前结果res和符号sign压入栈，res重置为0，sign重置为1；如果遇到了右括号，结果res乘以栈顶的符号，栈顶元素出栈，结果res加上栈顶的数字，栈顶元素出栈。代码如下：

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
class Solution {
public:
    int calculate(string s) {
        int res = 0, len = s.length();
        stack<int> st;
        int op = 1;
        st.push(1);
        
        for (int i = 0; i < len;) {
            if (s[i] == ' ') {
                i ++;
                continue;
            }
            
            if (s[i] == '(') {
                st.push(op);
                i ++;
            } else if (s[i] == ')') {
                st.pop();
                i ++;
            } else if (s[i] == '+') {
                op = 1 * st.top();
                i ++;
            } else if (s[i] == '-') {
                op = -1 * st.top();
                i ++;
            } else {
                long long val = 0;
                while(i < len && '0' <= s[i] && s[i] <= '9')
                    val = val * 10 + s[i++] - '0';
                res += (op * val);
            }
            
        }
        
        return res;
    }
};

Leetcode225. Implement Stack using Queues

Implement the following operations of a stack using queues.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • empty() — Return whether the stack is empty.

Example:

1
2
3
4
5
6
7
MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

  • You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
  • Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
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
class MyStack {
public:
    
    queue<int> que;
    
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
        int temp = que.size();
        while(temp > 1) {
            int xx = que.front();
            que.pop();
            que.push(xx);
            temp --;
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int tt = que.front();
        que.pop();
        return tt;
    }
    
    /** Get the top element. */
    int top() {
        return que.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};

Leetcode226. Invert Binary Tree

Invert a binary tree.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9
Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
            return root;
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        if(root->left) invertTree(root->left);
        if(root->right) invertTree(root->right);
        return root;
    }
};

Leetcode227. Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negativeintegers, +, -, *, / operators and empty spaces ``. The integer division should truncate toward zero.

Example 1:

1
2
Input: "3+2*2"
Output: 7

Example 2:

1
2
Input: " 3/2 "
Output: 1

Example 3:

1
2
Input: " 3+5 / 2 "
Output: 5

Note:

  • You may assume that the given expression is always valid.
  • Do not use the eval built-in library function.

这道题是之前那道 Basic Calculator 的拓展，不同之处在于那道题的计算符号只有加和减，而这题加上了乘除，那么就牵扯到了运算优先级的问题，好在这道题去掉了括号，还适当的降低了难度，估计再出一道的话就该加上括号了。不管那么多，这道题先按木有有括号来处理，由于存在运算优先级，我们采取的措施是使用一个栈保存数字，如果该数字之前的符号是加或减，那么把当前数字压入栈中，注意如果是减号，则加入当前数字的相反数，因为减法相当于加上一个相反数。如果之前的符号是乘或除，那么从栈顶取出一个数字和当前数字进行乘或除的运算，再把结果压入栈中，那么完成一遍遍历后，所有的乘或除都运算完了，再把栈中所有的数字都加起来就是最终结果了，参见代码如下：

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 calculate(string s) {
        long res = 0, num = 0, n = s.size();
        char op = '+';
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            if (s[i] >= '0') {
                num = num * 10 + s[i] - '0';
            }
            if ((s[i] < '0' && s[i] != ' ') || i == n - 1) {
                if (op == '+') st.push(num);
                if (op == '-') st.push(-num);
                if (op == '*' || op == '/') {
                    int tmp = (op == '*') ? st.top() * num : st.top() / num;
                    st.pop();
                    st.push(tmp);
                }
                op = s[i];
                num = 0;
            } 
        }
        while (!st.empty()) {
            res += st.top();
            st.pop();
        }
        return res;
    }
};
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
class Solution {
public:
    int calculate(string s) {
        long res = 0, curRes = 0, num = 0, n = s.size();
        char op = '+';
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            }
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == n - 1) {
                switch (op) {
                    case '+': curRes += num; break;
                    case '-': curRes -= num; break;
                    case '*': curRes *= num; break;
                    case '/': curRes /= num; break;
                }
                if (c == '+' || c == '-' || i == n - 1) {
                    res += curRes;
                    curRes = 0;
                }
                op = c;
                num = 0;
            } 
        }
        return res;
    }
};
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
class Solution {
public:
    int calculate(string s) {
        int len = s.length();
        long long res = 0, last_val;
        char op = '+';
        
        for (int i = 0; i < len; ) {
            if (s[i] == ' ') {
                i ++;
                continue;
            }
            
            if ('0' <= s[i] && s[i] <= '9') {
                long long val = 0;
                while(i < len && '0' <= s[i] && s[i] <= '9')
                    val = val* 10 + s[i++] - '0';
            
                if (op == '+') {
                    res += val;
                    last_val = val;
                } else if (op == '-') {
                    res -= val;
                    last_val = -val;
                } else if (op == '*') {
                    res = res - last_val + last_val * val;
                    last_val = last_val * val;
                } else if (op == '/') {
                    res = res - last_val + last_val / val;
                    last_val = last_val / val;
                }
            }
            else {
                op = s[i];
                i ++;
            }
        }
        return res;
    }
};

Leetcode228. Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

1
2
3
Input:  [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

1
2
3
Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

这道题给定我们一个有序数组，让我们总结区间，具体来说就是让我们找出连续的序列，然后首尾两个数字之间用个“->”来连接，那么我只需遍历一遍数组即可，每次检查下一个数是不是递增的，如果是，则继续往下遍历，如果不是了，我们还要判断此时是一个数还是一个序列，一个数直接存入结果，序列的话要存入首尾数字和箭头“->”。我们需要两个变量i和j，其中i是连续序列起始数字的位置，j是连续数列的长度，当j为1时，说明只有一个数字，若大于1，则是一个连续序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        int i = 0, n = nums.size();
        while (i < n) {
            int j = 1;
            while (i + j < n && (long)nums[i + j] - nums[i] == j) ++j;
            res.push_back(j <= 1 ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[i + j - 1]));
            i += j;
        }
        return res;
    }
};

Leetcode229. Majority Element II

Given an integer array of size n , find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

1
2
Input: [3,2,3]
Output: [3]

Example 2:

1
2
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

这道题让我们求出现次数大于 n/3 的数字，而且限定了时间和空间复杂度，那么就不能排序，也不能使用 HashMap，这么苛刻的限制条件只有一种方法能解了，那就是摩尔投票法 Moore Voting，这种方法在之前那道题 Majority Element 中也使用了。题目中给了一条很重要的提示，让先考虑可能会有多少个这样的数字，经过举了很多例子分析得出，任意一个数组出现次数大于 n/3 的数最多有两个，具体的证明博主就不会了，博主也不是数学专业的（热心网友用手走路提供了证明：如果有超过两个，也就是至少三个数字满足“出现的次数大于 n/3”，那么就意味着数组里总共有超过 3*(n/3) = n 个数字，这与已知的数组大小矛盾，所以，只可能有两个或者更少）。那么有了这个信息，使用投票法的核心是找出两个候选数进行投票，需要两遍遍历，第一遍历找出两个候选数，第二遍遍历重新投票验证这两个候选数是否为符合题意的数即可，选候选数方法和前面那篇 Majority Element 一样，由于之前那题题目中限定了一定会有大多数存在，故而省略了验证候选众数的步骤，这道题却没有这种限定，即满足要求的大多数可能不存在，所以要有验证，参加代码如下：

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:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        int a = 0, b = 0, cnt1 = 0, cnt2 = 0, n = nums.size();
        for (int num : nums) {
            if (num == a) ++cnt1;
            else if (num == b) ++cnt2;
            else if (cnt1 == 0) { a = num; cnt1 = 1; }
            else if (cnt2 == 0) { b = num; cnt2 = 1; }
            else { --cnt1; --cnt2; }
        }
        cnt1 = cnt2 = 0;
        for (int num : nums) {
            if (num == a) ++cnt1;
            else if (num == b) ++cnt2;
        }
        if (cnt1 > n / 3) res.push_back(a);
        if (cnt2 > n / 3) res.push_back(b);
        return res;
    }
};

Leetcode230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

1
2
3
4
5
6
7
Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

1
2
3
4
5
6
7
8
9
Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

如果用中序遍历所有的节点就会得到一个有序数组。先来看一种非递归的方法，中序遍历最先遍历到的是最小的结点，只要用一个计数器，每遍历一个结点，计数器自增1，当计数器到达k时，返回当前结点值即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int cnt = 0;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            ++cnt;
            if (cnt == k) return p->val;
            p = p->right;
        }
        return 0;
    }
};

当然，此题我们也可以用递归来解，还是利用中序遍历来解，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        return kthSmallestDFS(root, k);
    }
    int kthSmallestDFS(TreeNode* root, int &k) {
        if (!root) return -1;
        int val = kthSmallestDFS(root->left, k);
        if (k == 0) return val;
        if (--k == 0) return root->val;
        return kthSmallestDFS(root->right, k);
    }
};

再来看一种分治法的思路，由于 BST 的性质，可以快速定位出第k小的元素是在左子树还是右子树，首先计算出左子树的结点个数总和 cnt，如果k小于等于左子树结点总和 cnt，说明第k小的元素在左子树中，直接对左子结点调用递归即可。如果k大于 cnt+1，说明目标值在右子树中，对右子结点调用递归函数，注意此时的k应为 k-cnt-1，应为已经减少了 cnt+1 个结点。如果k正好等于 cnt+1，说明当前结点即为所求，返回当前结点值即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int cnt = count(root->left);
        if (k <= cnt) {
            return kthSmallest(root->left, k);
        } else if (k > cnt + 1) {
            return kthSmallest(root->right, k - cnt - 1);
        }
        return root->val;
    }
    int count(TreeNode* node) {
        if (!node) return 0;
        return 1 + count(node->left) + count(node->right);
    }
};

这道题的 Follow up 中说假设该 BST 被修改的很频繁，而且查找第k小元素的操作也很频繁，问我们如何优化。其实最好的方法还是像上面的解法那样利用分治法来快速定位目标所在的位置，但是每个递归都遍历左子树所有结点来计算个数的操作并不高效，所以应该修改原树结点的结构，使其保存包括当前结点和其左右子树所有结点的个数，这样就可以快速得到任何左子树结点总数来快速定位目标值了。定义了新结点结构体，然后就要生成新树，还是用递归的方法生成新树，注意生成的结点的 count 值要累加其左右子结点的 count 值。然后在求第k小元素的函数中，先生成新的树，然后调用递归函数。在递归函数中，不能直接访问左子结点的 count 值，因为左子节结点不一定存在，所以要先判断，如果左子结点存在的话，那么跟上面解法的操作相同。如果不存在的话，当此时k为1的时候，直接返回当前结点值，否则就对右子结点调用递归函数，k自减1，参见代码如下：

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
// Follow up
class Solution {
public:
    struct MyTreeNode {
        int val;
        int count;
        MyTreeNode *left;
        MyTreeNode *right;
        MyTreeNode(int x) : val(x), count(1), left(NULL), right(NULL) {}
    };

    MyTreeNode* build(TreeNode* root) {
        if (!root) return NULL;
        MyTreeNode *node = new MyTreeNode(root->val);
        node->left = build(root->left);
        node->right = build(root->right);
        if (node->left) node->count += node->left->count;
        if (node->right) node->count += node->right->count;
        return node;
    }

    int kthSmallest(TreeNode* root, int k) {
        MyTreeNode *node = build(root);
        return helper(node, k);
    }

    int helper(MyTreeNode* node, int k) {
        if (node->left) {
            int cnt = node->left->count;
            if (k <= cnt) {
                return helper(node->left, k);
            } else if (k > cnt + 1) {
                return helper(node->right, k - 1 - cnt);
            }
            return node->val;
        } else {
            if (k == 1) return node->val;
            return helper(node->right, k - 1);
        }
    }
};

Leetcode231. Power of Two

Given an integer, write a function to determine if it is a power of two.

Example 1:

1
2
Input: 1 Output: true 
Explanation: 2^0 = 1

Example 2:
1
2
Input: 16 Output: true
Explanation: 2^4 = 16

判断一个数是不是2的幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n == 0)
            return false;
        while(n != 1) {
            int temp = n & 1;
            if(temp != 0)
                return false;
            n = n >> 1;
        }
        return true;
    }
};

Leetcode232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

  • push(x) — Push element x to the back of queue.
  • pop() — Removes the element from in front of queue.
  • peek() — Get the front element.
  • empty() — Return whether the queue is empty.

Example:

1
2
3
4
5
6
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

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
class MyQueue {
public:
    
    stack<int> s1, s2;
    int front;
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        if(s1.empty()) {
            front = x;
        }
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }
        int res = s2.top();
        s2.pop();
        while(!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
        return res;
    }
    
    /** Get the front element. */
    int peek() {
        while(!s1.empty()){
            s2.push(s1.top());
            s1.pop();
        }
        int res = s2.top();
        while(!s2.empty()){
            s1.push(s2.top());
            s2.pop();
        }
        return res;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();
    }
};

Leetcode233. Number of Digit One

Given an integer n, count the total number of digit1 appearing in all non-negative integers less than or equal to n.

Example 1:

1
2
Input: n = 13
Output: 6

Example 2:

1
2
Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 2 * 109

这道题让我们比给定数小的所有数中1出现的个数，之前有道类似的题 Number of 1 Bits，那道题是求转为二进数后1的个数，博主开始以为这道题也是要用那题的方法，其实不是的，这题实际上相当于一道找规律的题。那么为了找出规律，就先来列举下所有含1的数字，并每 10 个统计下个数，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1的个数  含1的数字                                          数字范围
1           1                                               [1, 9]
11          10  11  12  13  14  15  16  17  18  19          [10, 19]
1           21                                              [20, 29]
1           31                                              [30, 39]
1           41                                              [40, 49]
1           51                                              [50, 59]
1           61                                              [60, 69]
1           71                                              [70, 79]
1           81                                              [80, 89]
1           91                                              [90, 99]
11         100  101  102  103  104  105  106  107  108  109 [100, 109]
21         110  111  112  113  114  115  116  117  118  119 [110, 119]
11         120  121  122  123  124  125  126  127  128  129 [120, 129]

通过上面的列举可以发现，100 以内的数字，除了10-19之间有 11 个 ‘1’ 之外，其余都只有1个。如果不考虑 [10, 19] 区间上那多出来的 10 个 ‘1’ 的话，那么在对任意一个两位数，十位数上的数字(加1)就代表1出现的个数，这时候再把多出的 10 个加上即可。比如 56 就有 (5+1)+10=16 个。如何知道是否要加上多出的 10 个呢，就要看十位上的数字是否大于等于2，是的话就要加上多余的 10 个 ‘1’。那么就可以用 (x+8)/10 来判断一个数是否大于等于2。对于三位数区间 [100, 199] 内的数也是一样，除了 [110, 119] 之间多出的10个数之外，共 21 个 ‘1’，其余的每 10 个数的区间都只有 11 个 ‘1’，所以 [100, 199] 内共有 21 + 11 9 = 120 个 ‘1’。那么现在想想 [0, 999] 区间内 ‘1’ 的个数怎么求？根据前面的结果，[0, 99] 内共有 20 个，[100, 199] 内共有 120 个，而其他每 100 个数内 ‘1’ 的个数也应该符合之前的规律，即也是 20 个，那么总共就有 120 + 20 9 = 300 个 ‘1’。那么还是可以用相同的方法来判断并累加1的个数，参见代码如下：

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int countDigitOne(int n) {
        int res = 0, a = 1, b = 1;
        while (n > 0) {
            res += (n + 8) / 10 * a + (n % 10 == 1) * b;
            b += n % 10 * a;
            a *= 10;
            n /= 10;
        }
        return res;
    }
};

Leetcode234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

1
2
Input: 1->2
Output: false

Example 2:
1
2
Input: 1->2->2->1
Output: true

使用反转链表。不同的是不反转整个链表，只反转回文的后半段链表。然后就是判断出哪里是回文的中间位置。

首先说反转链表函数。设置一个节点pre为空，是反转链表后的起始节点。设置节点next为空，是要反转链表当前节点的next节点。遍历，只要head不为空，则先将head->next保存在next节点中。然后head->next指向pre，然后head节点保存在pre中。最后head保存next节点。遍历结束，返回pre节点，即完成反转。

然后说判断回文中间位置。设置一个慢指针slow，一个快指针fast。遍历，只要fast->next和fast->next->next不为空，则slow往前走一步，fast往前走两步，slow = slow->next，fast = fast->next->next，这样当不满足遍历条件、结束遍历时，slow刚好指在中间位置，如果长度是计数，则刚好中间，长度是偶数，则中间前一个。

然后说反转后半部分链表。将slow->next开始反转，slow->next = reverselist(slow->next)，然后将slow = slow->next。

最后是判断是否是回文。这时，可同时遍历head和slow，判断二者值是否相等即可，不相等直接返回false。遍历结束后，返回true。

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
class Solution {
public:
    
    ListNode* reverseList(ListNode *head) {
        ListNode *pre = NULL, *next = NULL;
        while(head) {
            next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return true;
        ListNode *slow = head, *fast = head;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow->next = reverseList(slow->next);
        slow = slow->next;

        while(slow) {
            if (slow->val != head->val)
                return false;
            slow = slow->next;
            head = head->next;
        }
        return true;
    }
};

Leetcode235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

1
2
3
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:
1
2
3
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

这道题我们可以用递归来求解，我们首先来看题目中给的例子，由于二叉搜索树的特点是左<根<右，所以根节点的值一直都是中间值，大于左子树的所有节点值，小于右子树的所有节点值，那么我们可以做如下的判断，如果根节点的值大于p和q之间的较大值，说明p和q都在左子树中，那么此时我们就进入根节点的左子节点继续递归，如果根节点小于p和q之间的较小值，说明p和q都在右子树中，那么此时我们就进入根节点的右子节点继续递归，如果都不是，则说明当前根节点就是最小共同父节点，直接返回即可。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;
        if (root->val > max(p->val, q->val)) 
            return lowestCommonAncestor(root->left, p, q);
        else if (root->val < min(p->val, q->val)) 
            return lowestCommonAncestor(root->right, p, q);
        else return root;
    }
};

当然，此题也有非递归的写法，用个 while 循环来代替递归调用即可，然后不停的更新当前的根节点，也能实现同样的效果，代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (true) {
            if (root->val > max(p->val, q->val)) root = root->left;
            else if (root->val < min(p->val, q->val)) root = root->right;
            else break;
        }      
        return root;
    }
};

Leetcode236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

Example 1:

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the binary tree.

在二叉树中来搜索p和q，然后从路径中找到最后一个相同的节点即为父节点，可以用递归来实现，在递归函数中，首先看当前结点是否为空，若为空则直接返回空，若为p或q中的任意一个，也直接返回当前结点。否则的话就对其左右子结点分别调用递归函数，由于这道题限制了p和q一定都在二叉树中存在，那么如果当前结点不等于p或q，p和q要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树，那么我们分别来讨论：

  • 若p和q分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回p和q结点的位置，而当前结点正好就是p和q的最小共同父结点，直接返回当前结点即可，这就是题目中的例子1的情况。
  • 若p和q同时位于左子树，这里有两种情况，一种情况是 left 会返回p和q中较高的那个位置，而 right 会返回空，所以最终返回非空的 left 即可，这就是题目中的例子2的情况。还有一种情况是会返回p和q的最小父结点，就是说当前结点的左子树中的某个结点才是p和q的最小父结点，会被返回。
  • 若p和q同时位于右子树，同样这里有两种情况，一种情况是 right 会返回p和q中较高的那个位置，而 left 会返回空，所以最终返回非空的 right 即可，还有一种情况是会返回p和q的最小父结点，就是说当前结点的右子树中的某个结点才是p和q的最小父结点，会被返回，写法很简洁，代码如下：
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if (!root || p == root || q == root) return root;
       TreeNode *left = lowestCommonAncestor(root->left, p, q);
       TreeNode *right = lowestCommonAncestor(root->right, p , q);
       if (left && right) return root;
       return left ? left : right;
    }
};

上述代码可以进行优化一下，如果当前结点不为空，且既不是p也不是q，那么根据上面的分析，p和q的位置就有三种情况，p和q要么分别位于左右子树中，要么同时位于左子树，或者同时位于右子树。我们需要优化的情况就是当p和q同时为于左子树或右子树中，而且返回的结点并不是p或q，那么就是p和q的最小父结点了，已经求出来了，就不用再对右结点调用递归函数了，这是为啥呢？因为根本不会存在 left 既不是p也不是q，同时还有p或者q在 right 中。首先递归的第一句就限定了只要遇到了p或者q，就直接返回，之后又限定了只有当 left 和 right 同时存在的时候，才会返回当前结点，当前结点若不是p或q，则一定是最小父节点，否则 left 一定是p或者q。这里的逻辑比较绕，不太好想，多想想应该可以理清头绪吧，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if (!root || p == root || q == root) return root;
       TreeNode *left = lowestCommonAncestor(root->left, p, q);
       if (left && left != p && left != q) return left;
       TreeNode *right = lowestCommonAncestor(root->right, p , q);
　　　　if (left && right) return root;
       return left ? left : right;
    }
};

Leetcode237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list — head = [4,5,1,9], which looks like following:

Example 1:

1
2
3
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:
1
2
3
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

这道题让我们删除链表的一个节点，更通常不同的是，没有给我们链表的起点，只给我们了一个要删的节点，跟我们以前遇到的情况不太一样，我们之前要删除一个节点的方法是要有其前一个节点的位置，然后将其前一个节点的next连向要删节点的下一个，然后delete掉要删的节点即可。这道题的处理方法是先把当前节点的值用下一个节点的值覆盖了，然后我们删除下一个节点即可。
1
2
3
4
5
6
7
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

Leetcode238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of numsexcept nums[i].

Example:

1
2
Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

这道题给定我们一个数组，让我们返回一个新数组，对于每一个位置上的数是其他位置上数的乘积，并且限定了时间复杂度 O(n)，并且不让我们用除法。如果让用除法的话，那这道题就应该属于 Easy，因为可以先遍历一遍数组求出所有数字之积，然后除以对应位置的上的数字。但是这道题禁止我们使用除法，那么我们只能另辟蹊径。我们想，对于某一个数字，如果我们知道其前面所有数字的乘积，同时也知道后面所有的数乘积，那么二者相乘就是我们要的结果，所以我们只要分别创建出这两个数组即可，分别从数组的两个方向遍历就可以分别创建出乘积累积数组。参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> fwd(n, 1), bwd(n, 1), res(n);
        for (int i = 0; i < n - 1; ++i) {
            fwd[i + 1] = fwd[i] * nums[i];
        }
        for (int i = n - 1; i > 0; --i) {
            bwd[i - 1] = bwd[i] * nums[i];
        }
        for (int i = 0; i < n; ++i) {
            res[i] = fwd[i] * bwd[i];
        }
        return res;
    }
};

我们可以对上面的方法进行空间上的优化，由于最终的结果都是要乘到结果 res 中，所以可以不用单独的数组来保存乘积，而是直接累积到结果 res 中，我们先从前面遍历一遍，将乘积的累积存入结果 res 中，然后从后面开始遍历，用到一个临时变量 right，初始化为1，然后每次不断累积，最终得到正确结果，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums.size(), 1);
        for (int i = 1; i < nums.size(); ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int right = 1;
        for (int i = nums.size() - 1; i >= 0; --i) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
};

Leetcode239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

1
2
Input: nums = [1], k = 1
Output: [1]

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

双端单调队列

本题要找长度为 k 的区间的最大值。模拟这个区间的移动过程，可以发现，右边增加一个数，左边必然会去掉一个数。

那么最大的数有什么性质呢？可以发现，如果扫描区间末尾，在已经遍历过的数之中，一个数 a 在 b 前面，并且 a 还比 b 小，那么 a 在之后的区间里永远无法成为最大值。

所以我们遍历到一个数时，它之前的所有比它小的数都可以去掉了，只保留比它大的数就行了。这就让人想到了之前介绍过的单调栈，但是本题中是先进先出，所以要改用单调队列。此外队列末尾不仅要增加元素，还得维护单调递减，适当去除一些元素，所以队列两端都得有插入和删除的功能。所以本题要使用双端队列，而队列中的元素又是单调递减的，所以又是双端单调队列。

这样思路就很明确了：

  • 遍历元素 nums[i] ，然后跟队列尾部元素比较，如果比尾部元素大，就出队，然后继续比较，直到 nums[i] 小于尾部元素，然后将它入队。
  • 然后用一下队列首部元素的下标，计算出队列中区间的长度，如果大于 k 了，那么队首元素就要出队。
  • 最后队首元素就是当前区间的最大值。

分块法

试想如果我们将数组划分为相同大小的若干块，每一块中最大值都是知道的话，那么要求区间最大值，只需要看它在哪几块里就行了。

那么块的大小应该设成多少呢？

如果块大小为 k ，就可以发现长度为 k 的区间 [i, j] 要么正好就是一个完整的块，要么跨越了两个相邻块。那么我们只需要知道 i 到它那块末尾元素中最大值，以及 j 到它那块开头最大值就行了，两个部分合并求最大值就是区间的最大值了。而每个元素到它自己那块的开头和末尾的最大值都可以预处理出来，方法和求前缀和类似。

那为什么块大小不能是其他值呢？如果块大小大于 k ，那么会出现区间完全包含于一块之中的情况，那就和不分块一样了。如果块大小小于 k ，那么就会出现区间横跨了好几块，那么还得遍历中间块的最大值。极端情况下如果块大小为 1 ，那么就等于暴力求解。

代码

双端单调队列（c++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> Q;
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            while (!Q.empty() && nums[i] >= nums[Q.back()]) Q.pop_back();
            Q.push_back(i);
            if (i - Q.front() + 1 > k) Q.pop_front();
            if (i >= k-1) res.push_back(nums[Q.front()]);
        }
        return res;
    }
};

双端单调队列+数组实现（c++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> Q(n, 0);
        vector<int> res;
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            while (r-l > 0 && nums[i] >= nums[Q[r-1]]) r--;
            Q[r++] = i;
            if (i - Q[l] + 1 > k) l++;
            if (i >= k-1) res.push_back(nums[Q[l]]);
        }
        return res;
    }
};

分块法（c++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> lmax(n, 0), rmax(n, 0);
        vector<int> res;
        if (!n) return res;
        for (int i = 0; i < n; ++i) {
            if (i%k == 0) lmax[i] = nums[i];
            else lmax[i] = max(lmax[i-1], nums[i]);
        }
        for (int i = n-1; i >= 0; --i) {
            if ((i+1)%k == 0 || i == n-1) rmax[i] = nums[i];
            else rmax[i] = max(rmax[i+1], nums[i]);
        }
        for (int i = k-1; i < n; ++i) {
            res.push_back(max(lmax[i], rmax[i-k+1]));
        }
        return res;
    }
};

双端单调队列（python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        Q = collections.deque()
        res = []
        for i in range(n):
            while len(Q) > 0 and nums[i] >= nums[Q[-1]]:
                Q.pop()
            Q.append(i)
            if i - Q[0] + 1 > k:
                Q.popleft()
            if i >= k-1:
                res.append(nums[Q[0]])
        return res

双端单调队列+数组实现（python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        Q = [0] * n
        res = []
        l, r = 0, 0
        for i in range(n):
            while r-l > 0 and nums[i] >= nums[Q[r-1]]:
                r -= 1
            Q[r] = i
            r += 1
            if i - Q[l] + 1 > k:
                l += 1 
            if i >= k-1:
                res.append(nums[Q[l]])
        return res

分块法（python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import collections
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        lmax, rmax = [0] * n, [0] * n
        res = []
        if n == 0:
            return res
        for i in range(n):
            if i%k == 0:
                lmax[i] = nums[i]
            else:
                lmax[i] = max(lmax[i-1], nums[i])
        for i in range(n-1, -1, -1):
            if (i+1)%k == 0 or i == n-1:
                rmax[i] = nums[i]
            else:
                rmax[i] = max(rmax[i+1], nums[i])
        for i in range(k-1, n):
            res.append(max(lmax[i], rmax[i-k+1]))
        return res

Leetcode240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Example:

Consider the following matrix:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.

从右上角开始, 比较target 和 matrix[i][j]的值. 如果小于target, 则该行不可能有此数, 所以i++; 如果大于target, 则该列不可能有此数, 所以j—. 遇到边界则表明该矩阵不含target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0 || matrix[0].size()==0)
            return false;
        int i=0,j=matrix[0].size()-1;
        while(i<matrix.size() && j>=0) {
            if(matrix[i][j]==target)
                return true;
            if(matrix[i][j] < target)
                i++;
            else 
                j--;
        }
        return false;
    }
};

然后，做一些简单的优化，就能从打败50%升到打败60%。比如尽量少的使用matrix[i][j]，而是用变量把它存下来。

Leetcode241. Different Ways to Add Parentheses 添加括号的不同方式

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

1
2
3
4
5
Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

1
2
3
4
5
6
7
8
Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

这道题让给了一个可能含有加减乘的表达式，让我们在任意位置添加括号，求出所有可能表达式的不同值。

先从最简单的输入开始，若 input 是空串，那就返回一个空数组。若 input 是一个数字的话，那么括号加与不加其实都没啥区别，因为不存在计算，但是需要将字符串转为整型数，因为返回的是一个整型数组。当然，input 是一个单独的运算符这种情况是不存在的，因为前面说了这道题默认输入的合法的。下面来看若 input 是数字和运算符的时候，比如 “1+1” 这种情况，那么加不加括号也没有任何影响，因为只有一个计算，结果一定是2。再复杂一点的话，比如题目中的例子1，input 是 “2-1-1” 时，就有两种情况了，(2-1)-1 和 2-(1-1)，由于括号的不同，得到的结果也不同，但如果我们把括号里的东西当作一个黑箱的话，那么其就变为 ()-1 和 2-()，其最终的结果跟括号内可能得到的值是息息相关的，那么再 general 一点，实际上就可以变成 () ? () 这种形式，两个括号内分别是各自的表达式，最终会分别计算得到两个整型数组，中间的问号表示运算符，可以是加，减，或乘。那么问题就变成了从两个数组中任意选两个数字进行运算，瞬间变成我们会做的题目了有木有？而这种左右两个括号代表的黑盒子就交给递归去计算，像这种分成左右两坨的 pattern 就是大名鼎鼎的分治法 Divide and Conquer 了，是必须要掌握的一个神器。类似的题目还有之前的那道 Unique Binary Search Trees II 用的方法一样，用递归来解，划分左右子树，递归构造。

好，继续来说这道题，我们不用新建递归函数，就用其本身来递归就行，先建立一个结果 res 数组，然后遍历 input 中的字符，根据上面的分析，我们希望在每个运算符的地方，将 input 分成左右两部分，从而扔到递归中去计算，从而可以得到两个整型数组 left 和 right，分别表示作用两部分各自添加不同的括号所能得到的所有不同的值，此时我们只要分别从两个数组中取数字进行当前的运算符计算，然后把结果存到 res 中即可。当然，若最终结果 res 中还是空的，那么只有一种情况，input 本身就是一个数字，直接转为整型存入结果 res 中即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        for (int i = 0; i < input.size(); ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                vector<int> left = diffWaysToCompute(input.substr(0, i));
                vector<int> right = diffWaysToCompute(input.substr(i + 1));
                for (int j = 0; j < left.size(); ++j) {
                    for (int k = 0; k < right.size(); ++k) {
                        if (input[i] == '+') res.push_back(left[j] + right[k]);
                        else if (input[i] == '-') res.push_back(left[j] - right[k]);
                        else res.push_back(left[j] * right[k]);
                    }
                }
            }
        }
        if (res.empty()) res.push_back(stoi(input));
        return res;
    }
};

Leetcode242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:
1
2
Input: s = "rat", t = "car"
Output: false

判断异位词，即包含相同的字符的字符串。使用map记录每个字符串中的字符，判断map是否相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isAnagram(string s, string t) {
        map<char, int> ss, tt;
        for(int i = 0; i < s.size(); i ++) {
            if(ss.find(s[i]) == ss.end())
                ss[s[i]] = 1;
            else ss[s[i]] ++;
        }
        for(int i = 0; i < t.size(); i ++) {
            if(tt.find(t[i]) == tt.end())
                tt[t[i]] = 1;
            else tt[t[i]] ++;
        }
        return ss == tt;
    }
};

Leetcode243. Shortest Word Distance

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:

1
2
3
4
5
6
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int idx = -1, res = INT_MAX;
        for (int i = 0; i < words.size(); ++i) {
            if (words[i] == word1 || words[i] == word2) {
                if (idx != -1 && words[idx] != words[i]) {
                    res = min(res, i - idx);
                }
                idx = i;
            }
        }
        return res;
    }
};

Leetcode246. Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string.

Example 1:

1
2
Input:  "69"
Output: true

Example 2:
1
2
Input:  "88"
Output: true

Example 3:
1
2
Input:  "962"
Output: false

这道题定义了一种对称数，就是说一个数字旋转 180 度和原来一样，也就是倒过来看一样，比如 609，倒过来还是 609 等等，满足这种条件的数字其实没有几个，只有 0,1,8,6,9。这道题其实可以看做求回文数的一种特殊情况，还是用双指针来检测，首尾两个数字如果相等的话，只有它们是 0,1,8 中间的一个才行，如果它们不相等的话，必须一个是6一个是9，或者一个是9一个是6，其他所有情况均返回 false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	public:
    bool isStrobogrammatic(string num) {
        int l = 0, r = num.size() - 1;
        while (l <= r) {
            if (num[l] == num[r]) {
                if (num[l] != '1' && num[l] != '0' && num[l] != '8'){
                    return false;
                }
            } else {
                if ((num[l] != '6' || num[r] != '9') && (num[l] != '9' || num[r] != '6')) {
                    return false;
                }
            }
            ++l; --r;
        }
        return true;
    }
};

Leetcode247. Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n.

For example, Given n = 2, return [“11”,”69”,”88”,”96”].

可以像是一层层的给字符串从里向外穿衣服一样DFS生成所有的解.

其中翻转之后和自身相等有0, 1, 8, 在n为奇数的情况下最里面的一个数可以为这三个数的任意一个. 再外边就一次给两端添加一个对称的字符. 如果是最外层的话需要注意不能是为0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
	public:
    void DFS(int n, string str)
    {
        if(n==0) return result.push_back(str);
        if(n%2==1) for(auto val: same) DFS(n-1, val);
        if(n%2==1) return;
        for(int i = (n==2)?1:0; i < two.size(); i++)
            DFS(n-2, two[i].first + str + two[i].second);
    }
    
    vector<string> findStrobogrammatic(int n) {
        if(n <= 0) return {};
        DFS(n, "");
        return result;
    }
private:
    vector<string> result;
    vector<string> same{"0", "1", "8"};
    vector<pair<char,char>> two{{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
};

Leetcode252. Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

Example 1:

1
2
Input: [[0,30],[5,10],[15,20]]
Output: false

Example 2:
1
2
Input: [[7,10],[2,4]]
Output: true

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

这道题给了我们一堆会议的时间，问能不能同时参见所有的会议，这实际上就是求区间是否有交集的问题，那么最简单暴力的方法就是每两个区间比较一下，看是否有 overlap，有的话直接返回 false 就行了。比较两个区间a和b是否有 overlap，可以检测两种情况，如果a的起始位置大于等于b的起始位置，且此时a的起始位置小于b的结束位置，则一定有 overlap，另一种情况是a和b互换个位置，如果b的起始位置大于等于a的起始位置，且此时b的起始位置小于a的结束位置，那么一定有 overlap，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        for (int i = 0; i < intervals.size(); ++i) {
            for (int j = i + 1; j < intervals.size(); ++j) {
                if ((intervals[i][0] >= intervals[j][0] && intervals[i][0] < intervals[j][1]) || (intervals[j][0] >= intervals[i][0] && intervals[j][0] < intervals[i][1])) return false;
            }
        }
        return true;
    }
};

我们可以先给所有区间排个序，用起始时间的先后来排，然后从第二个区间开始，如果开始时间早于前一个区间的结束时间，则说明会议时间有冲突，返回 false，遍历完成后没有冲突，则返回 true，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
};

Leetcode253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

Example 1:

1
2
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

1
2
Input: [[7,10],[2,4]]
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

这道题是之前那道 Meeting Rooms 的拓展，那道题只问我们是否能参加所有的会，也就是看会议之间有没有时间冲突，而这道题让求最少需要安排几个会议室，有时间冲突的肯定需要安排在不同的会议室。这道题有好几种解法，先来看使用 TreeMap 来做的，遍历时间区间，对于起始时间，映射值自增1，对于结束时间，映射值自减1，然后定义结果变量 res，和房间数 rooms，遍历 TreeMap，时间从小到大，房间数每次加上映射值，然后更新结果 res，遇到起始时间，映射是正数，则房间数会增加，如果一个时间是一个会议的结束时间，也是另一个会议的开始时间，则映射值先减后加仍为0，并不用分配新的房间，而结束时间的映射值为负数更不会增加房间数，利用这种思路可以写出代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        map<int, int> m;
        for (auto a : intervals) {
            ++m[a[0]];
            --m[a[1]];
        }
        int rooms = 0, res = 0;
        for (auto it : m) {
            res = max(res, rooms += it.second);
        }
        return res;
    }
};

第二种方法是用两个一维数组来做，分别保存起始时间和结束时间，然后各自排个序，定义结果变量 res 和结束时间指针 endpos，然后开始遍历，如果当前起始时间小于结束时间指针的时间，则结果自增1，反之结束时间指针自增1，这样可以找出重叠的时间段，从而安排新的会议室，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<int> starts, ends;
        int res = 0, endpos = 0;
        for (auto a : intervals) {
            starts.push_back(a[0]);
            ends.push_back(a[1]);
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        for (int i = 0; i < intervals.size(); ++i) {
            if (starts[i] < ends[endpos]) ++res;
            else ++endpos;
        }
        return res;
    }
};

Leetcode256. Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Example:

1
2
3
4
Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. 
             Minimum cost: 2 + 5 + 3 = 10.

解题思路：一道很明显的动态规划的题目. 每个房子有三种染色方案, 那么如果当前房子染红色的话, 最小代价将是上一个房子的绿色和蓝色的最小代价+当前房子染红色的代价. 对另外两种颜色也是如此. 因此动态转移方程为:

  • Sub-problem: find the minimum cost to paint the houses up to current house in red, blue or green.
  • Function:
    • Red: min(f[i - 11][1], f[i - 1][2]) + costs[i][0].
    • Blue: min(f[i - 1][0], f[i - 1][2]) + costs[i][1].
    • Green: min(f[i - 1][0], f[i - 1][1]) + costs[i][2].
    • Initialization: f[0][i] = 0.
    • Answer: min(f[costs.length][i]).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        // 直接initialize成0更好
        vector<vector<int>> dp(n + 1, vector<int>(3, INT_MAX));
        
        for (int i = 0; i < 3; i ++)
            dp[0][i] = 0;
        
        for(int i = 1; i < n + 1; i++){
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        
        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};

Leetcode257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
Input:
   1
 /   \
2     3
 \
  5
Output: ["1->2->5", "1->3"]
Explanation: All root-to-leaf paths are: 1->2->5, 1->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
class Solution {
public:
    
    vector<string> res;
    
    void dfs(TreeNode* root, string cur) { 
        if(root->left == NULL && root->right == NULL) {
            res.push_back(cur);
            return;
        }
        
        if(root->left)
            dfs(root->left, cur+"->"+to_string(root->left->val));
        if(root->right)
            dfs(root->right, cur+"->"+to_string(root->right->val));
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root == NULL)
            return res;
        dfs(root, to_string(root->val));
        return res;
    }
};

Leetcode258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

1
2
3
4
Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

逐位相加直到小于10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int addDigits(int num) {
        int res = num;
        while(res / 10) {
            int temp = res, sum = 0;;
            while(temp) {
                sum += temp%10;
                temp /= 10;
            }
            res = sum;
        }
        return res;
    }
};

Leetcode259. 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example:

1
2
3
4
5
Input: nums = [-2,0,1,3], and target = 2
Output: 2 
Explanation: Because there are two triplets which sums are less than 2:
	[-2,0,1]
	[-2,0,3]

这道题是 3Sum 问题的一个变形，让我们求三数之和小于一个目标值，那么最简单的方法就是穷举法，将所有的可能的三个数字的组合都遍历一遍，比较三数之和跟目标值之间的大小，小于的话则结果自增1，参见代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        int res = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < int(nums.size() - 2); ++i) {
	        int left = i + 1, right = nums.size() - 1, sum = target - nums[i];
	        for (int j = left; j <= right; ++j) {
	            for (int k = j + 1; k <= right; ++k) {
	                if (nums[j] + nums[k] < sum) ++res;
		        }
		    }
		}
        return res;
    }
};

题目中的 Follow up 让我们在 O(n^2) 的时间复杂度内实现，那么借鉴之前那两道题 3Sum Closest 和 3Sum 中的方法，采用双指针来做，这里面有个 trick 就是当判断三个数之和小于目标值时，此时结果应该加上 right-left，因为数组排序了以后，如果加上 num[right] 小于目标值的话，那么加上一个更小的数必定也会小于目标值，然后将左指针右移一位，否则将右指针左移一位，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
	public:
    int threeSumSmaller(vector<int>& nums, int target) {
	    if (nums.size() < 3) return 0;
	    int res = 0, n = nums.size();
	    sort(nums.begin(), nums.end());
	    for (int i = 0; i < n - 2; ++i) {
	        int left = i + 1, right = n - 1;
	        while (left < right) {
	    	    if (nums[i] + nums[left] + nums[right] < target) {
	    	        res += right - left;
	    	        ++left;
	    	    } else {
	    	        --right;
	    	    }
	    	}
	    }
	    return res;
	}
};

Leetcode260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

1
2
Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

  • The order of the result is not important. So in the above example, [5, 3] is also correct.
  • Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

这道题其实是很巧妙的利用了 Single Number 的解法，因为那道解法是可以准确的找出只出现了一次的数字，但前提是其他数字必须出现两次才行。而这题有两个数字都只出现了一次，那么我们如果能想办法把原数组分为两个小数组，不相同的两个数字分别在两个小数组中，这样分别调用 Single Number 的解法就可以得到答案。那么如何实现呢，首先我们先把原数组全部异或起来，那么我们会得到一个数字，这个数字是两个不相同的数字异或的结果，我们取出其中任意一位为 ‘1’ 的位，为了方便起见，我们用 a &= -a 来取出最右端为 ‘1’ 的位，具体来说下这个是如何操作的吧。就拿题目中的例子来说，如果我们将其全部 ‘异或’ 起来，我们知道相同的两个数 ‘异或’ 的话为0，那么两个1，两个2，都抵消了，就剩3和5 ‘异或’ 起来，那么就是二进制的 11 和 101 ‘异或’ ，得到110。然后我们进行 a &= -a 操作。首先变负数吧，在二进制中负数采用补码的形式，而补码就是反码 +1，那么 110 的反码是 11…1001，那么加1后是 11…1010，然后和 110 相与，得到了 10，就是代码中的 diff 变量。得到了这个 diff，就可以将原数组分为两个数组了。为啥呢，我们想阿，如果两个相同的数字 ‘异或’ ，每位都会是0，而不同的数字 ‘异或’ ，一定会有对应位不同，一个0一个1，这样 ‘异或’ 是1。比如3和5的二进制 11 和 101，如果从低往高看，最开始产生不同的就是第二位，那么我们用第二位来和数组中每个数字相与，根据结果的不同，一定可以把3和5区分开来，而其他的数字由于是成对出现，所以区分开来也是成对的，最终都会 ‘异或’ 成0，不会3和5产生影响。分别将两个小组中的数字都异或起来，就可以得到最终结果了，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        diff &= -diff;
        vector<int> res(2, 0);
        for (auto &a : nums) {
            if (a & diff) res[0] ^= a;
            else res[1] ^= a;
        }
        return res;
    }
};

Leetcode261. Graph Valid Tree

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Example 1:

1
2
3
Input: 
n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

1
2
3
Input: 
n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0,1] is the same as [1,0] and thus will not appear together in edges.

这道题给了一个无向图，让我们来判断其是否为一棵树，如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环，所以焦点就变成了验证是否是连通图和是否含有环。首先用 DFS 来做，根据 pair 来建立一个图的结构，用邻接链表来表示，还需要一个一位数组v来记录某个结点是否被访问过，然后用 DFS 来搜索结点0，遍历的思想是，当 DFS 到某个结点，先看当前结点是否被访问过，如果已经被访问过，说明环存在，直接返回 false，如果未被访问过，现在将其状态标记为已访问过，然后到邻接链表里去找跟其相邻的结点继续递归遍历，注意还需要一个变量 pre 来记录上一个结点，以免回到上一个结点，这样遍历结束后，就把和结点0相邻的节点都标记为 true，然后再看v里面是否还有没被访问过的结点，如果有，则说明图不是完全连通的，返回 false，反之返回 true，参见代码如下：

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
class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        vector<vector<int>> g(n, vector<int>());
        vector<bool> v(n, false);
        for (auto a : edges) {
            g[a.first].push_back(a.second);
            g[a.second].push_back(a.first);
        }
        if (!dfs(g, v, 0, -1)) return false;
        for (auto a : v) {
            if (!a) return false;
        }
        return true;
    }
    bool dfs(vector<vector<int>> &g, vector<bool> &v, int cur, int pre) {
        if (v[cur]) return false;
        v[cur] = true;
        for (auto a : g[cur]) {
            if (a != pre) {
                if (!dfs(g, v, a, cur)) return false;
            }
        }
        return true;
    }
};

下面来看 BFS 的解法，思路很相近，需要用 queue 来辅助遍历，这里没有用一维向量来标记节点是否访问过，而是用了一个 HashSet，如果遍历到一个节点，在 HashSet 中没有，则加入 HashSet，如果已经存在，则返回false，还有就是在遍历邻接链表的时候，遍历完成后需要将结点删掉，参见代码如下：

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:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        vector<unordered_set<int>> g(n, unordered_set<int>());
        unordered_set<int> s{{0}};
        queue<int> q{{0}};
        for (auto a : edges) {
            g[a.first].insert(a.second);
            g[a.second].insert(a.first);
        }
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (auto a : g[t]) {
                if (s.count(a)) return false;
                s.insert(a);
                q.push(a);
                g[a].erase(t);
            }
        }
        return s.size() == n;
    }
};

我们再来看 Union Find 的方法，这种方法对于解决连通图的问题很有效，思想是遍历节点，如果两个节点相连，将其 roots 值连上，这样可以找到环，初始化 roots 数组为 -1，然后对于一个 pair 的两个节点分别调用 find 函数，得到的值如果相同的话，则说明环存在，返回 false，不同的话，将其 roots 值 union 上，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool validTree(int n, vector<pair<int, int>>& edges) {
        vector<int> roots(n, -1);
        for (auto a : edges) {
            int x = find(roots, a.first), y = find(roots, a.second);
            if (x == y) return false;
            roots[x] = y;
        }
        return edges.size() == n - 1;
    }
    int find(vector<int> &roots, int i) {
        while (roots[i] != -1) i = roots[i];
        return i;
    }
};

Leetcode263. Ugly Number

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

1
2
3
Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:
1
2
3
Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:
1
2
3
Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.

检测一个数是否为丑陋数，所谓丑陋数就是其质数因子只能是 2，3，5。那么最直接的办法就是不停的除以这些质数，如果剩余的数字是1的话就是丑陋数了。
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0) return false;
        while (num % 2 == 0) num /= 2;
        while (num % 3 == 0) num /= 3;
        while (num % 5 == 0) num /= 5;
        return num == 1;
    }
};

Leetcode264. Ugly Number II

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

1
2
3
Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

1
2
3
Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

这道题是之前那道 Ugly Number 的拓展，这里让找到第n个丑陋数，还好题目中给了很多提示，基本上相当于告诉我们解法了，根据提示中的信息，丑陋数序列可以拆分为下面3个子列表：

(1) 1x2 , 2x2, 2x2 , 3x2, 3x2 , 4x2 , 5x2…

(2) 1x3, 1x3 , 2x3, 2x3, 2x3 , 3x3, 3x3…

(3) 1x5, 1x5, 1x5, 1x5 , 2x5, 2x5, 2x5…

仔细观察上述三个列表，可以发现每个子列表都是一个丑陋数分别乘以 2，3，5，而要求的丑陋数就是从已经生成的序列中取出来的，每次都从三个列表中取出当前最小的那个加入序列，请参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res(1, 1);
        int i2 = 0, i3 = 0, i5 = 0;
        while (res.size() < n) {
            int m2 = res[i2] * 2, m3 = res[i3] * 3, m5 = res[i5] * 5;
            int mn = min(m2, min(m3, m5));
            if (mn == m2) ++i2;
            if (mn == m3) ++i3;
            if (mn == m5) ++i5;
            res.push_back(mn);
        }
        return res.back();
    }
};

Leetcode266. Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

1
2
Input: "code"
Output: false

Example 2:
1
2
Input: "aab"
Output: true

Example 3:
1
2
Input: "carerac"
Output: true

Hint:

  • Consider the palindromes of odd vs even length. What difference do you notice?
  • Count the frequency of each character.

这道题让我们判断一个字符串的全排列有没有是回文字符串的，那么根据题目中的提示，我们分字符串的个数是奇偶的情况来讨论，如果是偶数的话，由于回文字符串的特性，每个字母出现的次数一定是偶数次，当字符串是奇数长度时，只有一个字母出现的次数是奇数，其余均为偶数，那么利用这个特性我们就可以解题，我们建立每个字母和其出现次数的映射，然后我们遍历 HashMap，统计出现次数为奇数的字母的个数，那么只有两种情况是回文数，第一种是没有出现次数为奇数的字母，再一个就是字符串长度为奇数，且只有一个出现次数为奇数的字母，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_map<char, int> m;
        int cnt = 0;
        for (auto a : s) ++m[a];
        for (auto a : m) {
            if (a.second % 2 == 1) ++cnt;
        }
        return cnt == 0 || (s.size() % 2 == 1 && cnt == 1);
    }
};

Leetcode268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1:

1
2
Input: [3,0,1]
Output: 2

Example 2:
1
2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

随机从0到size()选取了n个数，其中只有一个丢失了（显然的）。
别人的算法：数学推出，0到size()的总和减去当前数组和sum.
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i ++) {
            sum += nums[i];
        }
        return n*(n+1)/2 - sum;
    }
};

这道问题被标注为位运算问题：参考讨论区的位运算解法：

异或运算xor，
0 ^ a = a ^ 0 =a
a ^ b = b ^ a
a ^ a = 0
0到size()间的所有数一起与数组中的数进行异或运算，
因为同则0，0异或某个未出现的数将存活下来

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 1; i <= nums.size(); i++) 
            res =res ^ i ^ nums[i-1]; 
        return res; 
    }
};

Leetcode270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target.

Example:

1
2
3
4
5
6
7
8
9
Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

这道题让我们找一个二分搜索数的跟给定值最接近的一个节点值，由于是二分搜索树，所以博主最先想到用中序遍历来做，一个一个的比较，维护一个最小值，不停的更新，实际上这种方法并没有提高效率，用其他的遍历方法也可以，参见代码如下：
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 closestValue(TreeNode* root, double target) {
        double d = numeric_limits<double>::max();
        int res = 0;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            if (d >= abs(target - p->val)) {
                d = abs(target - p->val);
                res = p->val;
            }
            p = p->right;
        }
        return res;
    }
};

实际我们可以利用二分搜索树的特点 (左<根<右) 来快速定位，由于根节点是中间值，在往下遍历时，根据目标值和根节点的值大小关系来比较，如果目标值小于节点值，则应该找更小的值，于是到左子树去找，反之去右子树找，参见代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        int res = root->val;
        while (root) {
            if (abs(res - target) >= abs(root->val - target)) {
                res = root->val;
            }
            root = target < root->val ? root->left : root->right;
        }
        return res;
    }
};

Leetcode273. Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

1
2
3
123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

这道题让我们把一个整型数转为用英文单词描述，就像在check上写钱数的方法，我最开始的方法特别复杂，因为我用了几个switch语句来列出所有的单词，但是我看网上大神们的解法都是用数组来枚举的，特别的巧妙而且省地方，膜拜学习中。题目中给足了提示，首先告诉我们要3个一组的进行处理，而且题目中限定了输入数字范围为0到231 - 1之间，最高只能到billion位，3个一组也只需处理四组即可，那么我们需要些一个处理三个一组数字的函数，我们需要把1到19的英文单词都列出来，放到一个数组里，还要把20,30，… 到90的英文单词列出来放到另一个数组里，然后我们需要用写技巧，比如一个三位数n，百位数表示为n/100，后两位数一起表示为n%100，十位数表示为n%100/10，个位数表示为n%10，然后我们看后两位数是否小于20，小于的话直接从数组中取出单词，如果大于等于20的话，则分别将十位和个位数字的单词从两个数组中取出来。然后再来处理百位上的数字，还要记得加上Hundred。主函数中调用四次这个帮助函数，然后中间要插入”Thousand”, “Million”, “Billion”到对应的位置，最后check一下末尾是否有空格，把空格都删掉，返回的时候检查下输入是否为0，是的话要返回’Zero’。参见代码如下：

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:
    string numberToWords(int num) {
        string res = convertHundred(num % 1000);
        vector<string> v = {"Thousand", "Million", "Billion"};
        for (int i = 0; i < 3; ++i) {
            num /= 1000;
            res = num % 1000 ? convertHundred(num % 1000) + " " + v[i] + " " + res : res;
        }
        while (res.back() == ' ') res.pop_back();
        return res.empty() ? "Zero" : res;
    }
    string convertHundred(int num) {
        vector<string> v1 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        vector<string> v2 = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        string res;
        int a = num / 100, b = num % 100, c = num % 10;
        res = b < 20 ? v1[b] : v2[b / 10] + (c ? " " + v1[c] : "");
        if (a > 0) res = v1[a] + " Hundred" + (b ? " " + res : "");
        return res;
    }
};

Leetcode274. H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

1
2
3
4
5
6
Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h , the maximum one is taken as the h-index.

这道题让我们求H指数，这个质数是用来衡量研究人员的学术水平的质数，定义为一个人的学术文章有n篇分别被引用了n次，那么H指数就是n。而且wiki上直接给出了算法，可以按照如下方法确定某人的H指数：1、将其发表的所有SCI论文按被引次数从高到低排序；2、从前往后查找排序后的列表，直到某篇论文的序号大于该论文被引次数。所得序号减一即为H指数。我也就没多想，直接按照上面的方法写出了代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int res = 0, size = citations.size();
        for (int i = 0; i < size; i ++) {
            if (citations[i] >= size-i) {
                res = max(res, size-i);
            }
        }
        return res;
    }
};

Leetcode275. H-Index II

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

1
2
3
4
5
6
Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h , the maximum one is taken as the h-index.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int size = citations.size();
        int left = 0, right = size-1;
        while(left <= right) {
            int mid = left + (right-left)/2;
            if (citations[mid] == size-mid)
                return size-mid;
            else if (citations[mid] > size-mid)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return size - left;
    }
};

Leetcode278. First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

  1. 找出一个序列中第一个出错的位置，可以理解位这个序列是有序的，利用二分查找找到第一个位置
  2. 二分查找在处理的时候，如果不是，start = mid + 1; 是的话应该直接赋值start， 因为这时候这个值有可能就是第一个值
  3. 为什么要用 start + （end - start)/2 这种写法，而不是直接用（start + end）/2？这是为了防止大数溢出，假设这时候start已经是一个很大的数了，就会产生溢出
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            int start = 1, end = n;
            while (start < end){
                int mid = start + (end - start)/2;
                if(!isBadVersion(mid))  start = mid + 1;
                else end = mid;
            }
            return start;    
        }
    }

Leetcode279. Perfect Squares

Given a positive integer n , find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

1
2
3
Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

这道题说是给我们一个正整数，求它最少能由几个完全平方数组成。这道题是考察四平方和定理。先来看第一种很高效的方法，根据四平方和定理，任意一个正整数均可表示为4个整数的平方和，其实是可以表示为4个以内的平方数之和，那么就是说返回结果只有 1,2,3 或4其中的一个，首先我们将数字化简一下，由于一个数如果含有因子4，那么我们可以把4都去掉，并不影响结果，比如2和8,3和12等等，返回的结果都相同，读者可自行举更多的栗子。还有一个可以化简的地方就是，如果一个数除以8余7的话，那么肯定是由4个完全平方数组成，这里就不证明了，因为我也不会证明，读者可自行举例验证。那么做完两步后，一个很大的数有可能就会变得很小了，大大减少了运算时间，下面我们就来尝试的将其拆为两个平方数之和，如果拆成功了那么就会返回1或2，因为其中一个平方数可能为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSquares(int n) {
        while (n % 4 == 0) n /= 4;
        if (n % 8 == 7) return 4;
        for (int a = 0; a * a <= n; ++a) {
            int b = sqrt(n - a * a);
            if (a * a + b * b == n) {
                return !!a + !!b;
            }
        }
        return 3;
    }
};

这道题远不止这一种解法，我们还可以用动态规划 Dynamic Programming 来做，我们建立一个长度为 n+1 的一维dp数组，将第一个值初始化为0，其余值都初始化为INT_MAX，i从0循环到n，j从1循环到i+j<=n的位置，然后每次更新dp[i+j]的值，动态更新 dp 数组，其中dp[i]表示正整数i至少由多个完全平方数组成，那么我们求n，就是返回dp[n]即可，也就是 dp 数组的最后一个数字。需要注意的是这里的写法，i必须从0开始，j必须从1开始，因为我们的初衷是想用dp[i]来更新dp[i + j * j]，如果i=0，j=1了，那么dp[i]和dp[i + j * j]就相等了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; ++i) {
            for (int j = 1; i + j * j <= n; ++j) {
                dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);
            }
        }
        return dp.back();
    }
};

Leetcode282. Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binaryoperators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

1
2
Input: _num_ = "123", _target_ = 6
Output: ["1+2+3", "1*2*3"]

Example 2:

1
2
Input: _num_ = "232", _target_ = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

1
2
Input: _num_ = "105", _target_ = 5
Output: ["1*0+5","10-5"]

Example 4:

1
2
Input: _num_ = "00", _target_ = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

1
2
Input: _num_ = "3456237490", _target_ = 9191
Output: []

这道题给了我们一个只由数字组成的字符串，让我们再其中添加+,-或号来形成一个表达式，该表达式的计算和为给定了target值，让我们找出所有符合要求的表达式来。看了题目中的例子1和2，很容易让人误以为是必须拆成个位数字，其实不是的，比如例子3中的 “105”, 5能返回”10-5”，说明连着的数字也可以。如果非要在过往的题中找一道相似的题，我觉得跟 Combination Sum II 很类似。不过这道题要更复杂麻烦一些。还是用递归来解题，我们需要两个变量diff和curNum，一个用来记录将要变化的值，另一个是当前运算后的值，而且它们都需要用 long 型的，因为字符串转为int型很容易溢出，所以我们用长整型。对于加和减，diff就是即将要加上的数和即将要减去的数的负值，而对于乘来说稍有些复杂，此时的diff应该是上一次的变化的diff乘以即将要乘上的数，有点不好理解，那我们来举个例子，比如 2+32，即将要运算到乘以2的时候，上次循环的 curNum = 5, diff = 3, 而如果我们要算这个乘2的时候，新的变化值diff应为 32=6，而我们要把之前+3操作的结果去掉，再加上新的diff，即 (5-3)+6=8，即为新表达式 2+32 的值，有点难理解，大家自己一步一步推算吧。

还有一点需要注意的是，如果输入为”000”,0的话，容易出现以下的错误：

Wrong：[“0+0+0”,”0+0-0”,”0+00”,”0-0+0”,”0-0-0”,”0-00”,”00+0”,”00-0”,”000”,”0+00”,”0-00”,”000”,”00+0”,”00-0”,”000”,”000”]

Correct：[“000”,”00+0”,”00-0”,”0+00”,”0+0+0”,”0+0-0”,”0-00”,”0-0+0”,”0-0-0”]

我们可以看到错误的结果中有0开头的字符串出现，明显这不是数字，所以我们要去掉这些情况，过滤方法也很简单，我们只要判断长度大于1且首字符是‘0’的字符串，将其滤去即可，参见代码如下：

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
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        helper(num, target, 0, 0, "", res);
        return res;
    }
    void helper(string num, int target, long diff, long curNum, string out, vector<string>& res) {
        if (num.size() == 0 && curNum == target) {
            res.push_back(out); return;
        }
        for (int i = 1; i <= num.size(); ++i) {
            string cur = num.substr(0, i);
            if (cur.size() > 1 && cur[0] == '0') return;
            string next = num.substr(i);
            if (out.size() > 0) {
                helper(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);
                helper(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);
                helper(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);
            } else {
                helper(next, target, stoll(cur), stoll(cur), cur, res);
            }
        }
    }
};
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
class Solution {
public:
    string s;
    int target;
    vector<string> res;
    void dfs(const string& exp, int pos, long long sum, long long lastval) {
        if (pos == s.length()) {
            if (sum == target) 
                res.push_back(exp);
            return;
        }
        
        const string ops = pos == 0 ? "+" : "+-*";
        long long val = 0;
        for (int i = pos; i < s.length(); i ++) {
            if (i > pos && s[pos] == '0')
                break;
            val = val * 10 + s[i] - '0';
            
            // 整个s的第一个符号只能是+
            for (char op : ops) {            
                string newexpr;
                if (!pos) 
                    newexpr = s.substr(pos, i-pos+1);
                else
                    newexpr = exp + string(1, op) + s.substr(pos, i-pos+1);
                if (op == '+') {
                    dfs(newexpr, i+1, sum+val, val);
                }
                else if (op == '-') {
                    dfs(newexpr, i+1, sum - val, -val);
                } else {
                    dfs(newexpr, i+1, sum - lastval + lastval * val, lastval * val);
                }
            }
        }
        
    }
    vector<string> addOperators(string num, int target) {
        this->s = num;
        this->target = target;
        
        dfs("", 0, 0, 0);
        return res;
    }
};

Leetcode283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

1
2
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

  • You must do this in-place without making a copy of the array.
  • Minimize the total number of operations.

把0移动到数组末尾：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int begin = 0, end = 0;
        if(nums.size() == 1)
            return;
        while(begin < nums.size() && end < nums.size()) {
            end = begin;
            if(nums[begin] == 0) {
                while(end < nums.size() && nums[end] == 0)
                    end ++;
                if(end == nums.size())
                    break;
                int temp = nums[begin];
                nums[begin] = nums[end];
                nums[end] = temp;
            }
            begin ++;
        }
    }
};

优化方法:
1
2
3
4
5
6
7
void moveZeroes(vector<int>& nums) {
    for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
        if (nums[cur] != 0) {
            swap(nums[lastNonZeroFoundAt++], nums[cur]);
        }
    }
}

Leetcode287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

1
2
Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2
Input: [3,1,3,4,2]
Output: 3

Note:

  • You must not modify the array (assume the array is read only).
  • You must use only constant, O (1) extra space.
  • Your runtime complexity should be less than O ( n 2).
  • There is only one duplicate number in the array, but it could be repeated more than once.

这道题给了我们 n+1 个数，所有的数都在 [1, n] 区域内，首先让证明必定会有一个重复数，这不禁让博主想起了小学华罗庚奥数中的抽屉原理(又叫鸽巢原理)，即如果有十个苹果放到九个抽屉里，如果苹果全在抽屉里，则至少有一个抽屉里有两个苹果，这里就不证明了，直接来做题吧。题目要求不能改变原数组，即不能给原数组排序，又不能用多余空间，那么哈希表神马的也就不用考虑了，又说时间小于 O(n2)，也就不能用 brute force 的方法，那也就只能考虑用二分搜索法了，在区间 [1, n] 中搜索，首先求出中点 mid，然后遍历整个数组，统计所有小于等于 mid 的数的个数，如果个数小于等于 mid，则说明重复值在 [mid+1, n] 之间，反之，重复值应在 [1, mid-1] 之间，然后依次类推，直到搜索完成，此时的 low 就是我们要求的重复值，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1, right = nums.size();
        while (left < right){
            int mid = left + (right - left) / 2, cnt = 0;
            for (int num : nums) {
                if (num <= mid) ++cnt;
            }
            if (cnt <= mid) left = mid + 1;
            else right = mid;
        }    
        return right;
    }
};

另一种方法的基本思想是将数组抽象为一条线和一个圆环，因为1～n之间有n＋1个数，所以一定有重复数字出现，所以重复的数字即是圆环与线的交汇点。然后设置两个指针，一个快指针一次走两步，一个慢指针一次走一步。当两个指针第一次相遇时，令快指针回到原点（0）且也变成一次走一步，慢指针则继续前进，再次回合时即是线与圆环的交汇点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = nums[nums[0]], slow = nums[0];
        while(fast != slow) {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }
        fast = 0;
        while(fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
};

Leetcode289. Game of Life

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  • Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  • Any live cell with two or three live neighbors lives on to the next generation.
  • Any live cell with more than three live neighbors dies, as if by over-population..
  • Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
Output: 
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

Follow up:

  • Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  • In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

这道题是有名的 康威生命游戏，这是一种细胞自动机，每一个位置有两种状态，1为活细胞，0为死细胞，对于每个位置都满足如下的条件：

  1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡
  2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活
  3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡
  4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活

由于题目中要求用置换方法 in-place 来解题，所以就不能新建一个相同大小的数组，那么只能更新原有数组，题目中要求所有的位置必须被同时更新，但在循环程序中还是一个位置一个位置更新的，当一个位置更新了，这个位置成为其他位置的 neighbor 时，怎么知道其未更新的状态呢？可以使用状态机转换：

  • 状态0： 死细胞转为死细胞
  • 状态1： 活细胞转为活细胞
  • 状态2： 活细胞转为死细胞
  • 状态3： 死细胞转为活细胞

最后对所有状态对2取余，则状态0和2就变成死细胞，状态1和3就是活细胞，达成目的。先对原数组进行逐个扫描，对于每一个位置，扫描其周围八个位置，如果遇到状态1或2，就计数器累加1，扫完8个邻居，如果少于两个活细胞或者大于三个活细胞，而且当前位置是活细胞的话，标记状态2，如果正好有三个活细胞且当前是死细胞的话，标记状态3。完成一遍扫描后再对数据扫描一遍，对2取余变成我们想要的结果。参见代码如下：

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
class Solution {
public:
    void gameOfLife(vector<vector<int> >& board) {
        int m = board.size(), n = m ? board[0].size() : 0;
        vector<int> dx{-1, -1, -1, 0, 1, 1, 1, 0};
        vector<int> dy{-1, 0, 1, 1, 1, 0, -1, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int cnt = 0;
                for (int k = 0; k < 8; ++k) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && (board[x][y] == 1 || board[x][y] == 2)) {
                        ++cnt;
                    }
                }
                if (board[i][j] && (cnt < 2 || cnt > 3)) board[i][j] = 2;
                else if (!board[i][j] && cnt == 3) board[i][j] = 3;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                board[i][j] %= 2;
            }
        }
    }
};

Leetcode290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

1
2
Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:
1
2
Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:
1
2
Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:
1
2
Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

给定一种规律 pattern 和一个字符串 str ，判断 str 中的单词和pattern的字母是否遵循相同的映射， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

自己的代码，在测评的帮助下加了很多的boundary case，超过了双百：

  • Runtime: 0 ms, faster than 100.00% of C++ online submissions for Word Pattern.
  • Memory Usage: 6.7 MB, less than 100.00% of C++ online submissions for Word Pattern.
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
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        map<string, char> mapp;
        string word;
        str.push_back(' ');
        int i=0, j=0, count=0;;
        while(i<str.size()) {
            word="";
            while(str[i]!=' ') {
                word += str[i];
                i++;
            }
            i++;
            count ++; // str一共有多少个单词
            if (mapp.find(word)==mapp.end()) {
                int temp=0;
                while(temp<j) {
                    if (pattern[temp]==pattern[j])
                        break;
                    temp ++;
                }
                if(temp == j)
                    mapp[word] = pattern[j];
                else
                    return false;
            }
            else
                if (mapp[word] != pattern[j])
                    return false;
            j++;
        }
        if(count != pattern.size())
            return false;
        return true;
    }
};

看看人家的思路：这道题目主要考察哈希表和字符串的内容。可以将题目拆解为下面三步：

  • 设置pattern字符到单词（字符串 str）的映射（哈希），使用HashMap()存储；使用HashSet() 记录被使用过的单词 。
  • 若单词个数和pattern字符个数不匹配，返回false；
  • 遍历pattern，同时对应的向前移动 str 中单词的指针，每次拆分出pattern中的一个字符， 判断：
    • 如果该字符从未出现在哈希表中：
    • 如果该字符对应的单词已被使用过 ，即HashSet()中包含该字符对应的单词，则返回false；
    • 将该字符与其对应的单词做映射，加入哈希表中；标记该字符指向的单词为已使用，并加入HashSet()；
    • 如果该字符在哈希表的映射单词与当前指向的单词不同，则返回false；
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
class Solution {
    public boolean wordPattern(String pattern, String str) {
        HashMap<Character, String> map = new HashMap<>();
        HashSet<String> set = new HashSet<>();
        String[] array = str.split(" ");

        if (pattern.length() != array.length) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char key = pattern.charAt(i);
            if (!map.containsKey(key)) {
                if (set.contains(array[i])) {
                    return false;
                }
                map.put(key, array[i]);
                set.add(array[i]);
            } else {
                if (!map.get(key).equals(array[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}

Leetcode292. Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

Example:

1
2
3
4
5
Input: 4
Output: false 
Explanation: If there are 4 stones in the heap, then you will never win the game;
             No matter 1, 2, or 3 stones you remove, the last stone will always be 
             removed by your friend.

规律就是当有4,8,12,16….4n…时，我一定输；其他情况我一定赢。

因为当为4n时，我拿后剩下4n-1,4n-2,4n-3块，对方可以拿到4n-4=4(n-1)块。然后我再拿，对方再拿到4(n-2)块。。无论我怎么拿，对方总能拿到最后剩下4块。。。这样我就输了。同理，不为4n时，我总能拿到4n，这样对方就输了。

1
2
3
4
5
6
class Solution {
public:      
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

Leetcode293. Flip Game

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip twoconsecutive “++” into “—“. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = “++++”, after one move, it may become one of the following states:

1
2
3
4
5
[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

这道题让我们把相邻的两个 ++ 变成 —，真不是一道难题，就从第二个字母开始遍历，每次判断当前字母是否为+，和之前那个字母是否为+，如果都为加，则将翻转后的字符串存入结果中即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<string> generatePossibleNextMoves(string s) {
        vector<string> res;
        for (int i = 1; i < s.size(); i ++) {
            if (s[i] == '+' && s[i - 1] == '+') {
                res.push_back(s.substr(0, i - 1) + "--" + s.substr(i + 1));
            }
        }
        return res;
    }
};

Leetcode295. Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

1
2
3
4
5
Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation

1
2
3
4
5
6
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

这道题给我们一个数据流，让我们找出中位数，由于数据流中的数据并不是有序的，所以我们首先应该想个方法让其有序。如果我们用vector来保存数据流的话，每进来一个新数据都要给数组排序，很不高效。所以之后想到用multiset这个数据结构，是有序保存数据的，但是它不能用下标直接访问元素，找中位数也不高效。这里用到的解法十分巧妙，我们使用大小堆来解决问题，其中大堆保存右半段较大的数字，小堆保存左半段较小的数组。这样整个数组就被中间分为两段了，由于堆的保存方式是由大到小，我们希望大堆里面的数据是从小到大，这样取第一个来计算中位数方便。我们用到一个小技巧，就是存到大堆里的数先取反再存，这样由大到小存下来的顺序就是实际上我们想要的从小到大的顺序。当大堆和小堆中的数字一样多时，我们取出大堆小堆的首元素求平均值，当小堆元素多时，取小堆首元素为中位数，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MedianFinder {
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        small.push(num);
        large.push(-small.top());
        small.pop();
        if (small.size() < large.size()) {
            small.push(-large.top());
            large.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        return small.size() > large.size() ? small.top() : 0.5 *(small.top() - large.top());
    }

private:
    priority_queue<long> small, large;
};

LeetCode296. Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example:

1
2
3
4
5
6
7
8
Input: 
1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 6

Explanation: Given three people living at (0,0), (0,4), and (2,2), The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

这道题让我们求最佳的开会地点，该地点需要到每个为1的点的曼哈顿距离之和最小，题目中给了提示，让从一维的情况来分析，先看一维时有两个点A和B的情况,

1
______A_____P_______B_______

可以发现，只要开会为位置P在 [A, B] 区间内，不管在哪，距离之和都是A和B之间的距离，如果P不在 [A, B] 之间，那么距离之和就会大于A和B之间的距离，现在再加两个点C和D：

1
______C_____A_____P_______B______D______

通过分析可以得出，P点的最佳位置就是在 [A, B] 区间内，这样和四个点的距离之和为AB距离加上 CD 距离，在其他任意一点的距离都会大于这个距离，那么分析出来了上述规律，这题就变得很容易了，只要给位置排好序，然后用最后一个坐标减去第一个坐标，即 CD 距离，倒数第二个坐标减去第二个坐标，即 AB 距离，以此类推，直到最中间停止，那么一维的情况分析出来了，二维的情况就是两个一维相加即可，参见代码如下：

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 minTotalDistance(vector<vector<int>>& grid) {
        vector<int> rows, cols;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] == 1) {
                    rows.push_back(i);
                    cols.push_back(j);
                }
            }
        }
        return minTotalDistance(rows) + minTotalDistance(cols);
    }
    int minTotalDistance(vector<int> v) {
        int res = 0;
        sort(v.begin(), v.end());
        int i = 0, j = v.size() - 1;
        while (i < j) res += v[j--] - v[i++];
        return res;
    }
};

我们也可以不用多写一个函数，直接对 rows 和 cols 同时处理，稍稍能简化些代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> rows, cols;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] == 1) {
                    rows.push_back(i);
                    cols.push_back(j);
                }
            }
        }
        sort(cols.begin(), cols.end());
        int res = 0, i = 0, j = rows.size() - 1;
        while (i < j) res += rows[j] - rows[i] + cols[j--] - cols[i++];
        return res;
    }
};

Leetcode297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

1
2
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

1
2
Input: root = []
Output: []

二叉树的序列化与反序列化

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
/**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  * };
  */
const int N = 200000;
char buf[N];

class Codec {
	public:
    int length;
    
    void dfs(TreeNode* root) {
        if (length)
            buf[length++] = ',';
        if (!root) {
            buf[length++] = '#';
            return;
        }
	        
        string val = to_string(root->val);
        for (char c : val)
            buf[length++] = c;
	        
        dfs(root->left);
        dfs(root->right);
    }
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        length = 0;
        dfs(root);
        buf[length] = 0;
        return string(buf);
    }

    TreeNode* gen(string data, int& cur) {
        if (cur >= data.length())
            return NULL;
        if (data[cur] == '#') {
            cur += 2;
            return NULL;
        }
        
        int flag = 1, val = 0;
        if (data[cur] == '-') {
            cur ++;
            flag = -1;
        }
	        
        while(cur < data.length() && data[cur] != ',') {
            val = val * 10 + data[cur] - '0';
            cur ++;
        }
        TreeNode* root = new TreeNode(flag * val);
        cur ++;
        root->left = gen(data, cur);
        root->right = gen(data, cur);
        return root;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int cur = 0;
        return gen(data, cur);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

Leetcode299. Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it, each time your friend guesses a number, you give a hint, the hint tells your friend how many digits are in the correct positions (called “bulls”) and how many digits are in the wrong positions (called “cows”), your friend will use those hints to find out the secret number.

For example:

1
2
Secret number:  1807
Friend's guess: 7810

According to Wikipedia: “Bulls and Cows (also known as Cows and Bulls or Pigs and Bulls or Bulls and Cleots) is an old code-breaking mind or paper and pencil game for two or more players, predating the similar commercially marketed board game Mastermind. The numerical version of the game is usually played with 4 digits, but can also be played with 3 or any other number of digits.”

Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows, in the above example, your function should return 1A3B.

You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

这道题提出了一个叫公牛母牛的游戏，有一个四位数字，你猜一个结果，然后根据你猜的结果和真实结果做对比，提示有多少个数字和位置都正确的叫做bulls，还提示有多少数字正确但位置不对的叫做cows，根据这些信息来引导我们继续猜测正确的数字。这道题并没有让我们实现整个游戏，而只用实现一次比较即可。给出两个字符串，让我们找出分别几个bulls和cows。这题需要用哈希表，来建立数字和其出现次数的映射。我最开始想的方法是用两次遍历，第一次遍历找出所有位置相同且值相同的数字，即bulls，并且记录secret中不是bulls的数字出现的次数。然后第二次遍历我们针对guess中不是bulls的位置，如果在哈希表中存在，cows自增1，然后映射值减1，参见如下代码：

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string getHint(string secret, string guess) {
        int m[256] = {0}, bulls = 0, cows = 0;
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) ++bulls;
            else ++m[secret[i]];
        }
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] != guess[i] && m[guess[i]]) {
                ++cows;
                --m[guess[i]];
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

我们其实可以用一次循环就搞定的，在处理不是bulls的位置时，我们看如果secret当前位置数字的映射值小于0，则表示其在guess中出现过，cows自增1，然后映射值加1，如果guess当前位置的数字的映射值大于0，则表示其在secret中出现过，cows自增1，然后映射值减1，参见代码如下：

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string getHint(string secret, string guess) {
        int m[256] = {0}, bulls = 0, cows = 0;
        for (int i = 0; i < secret.size(); ++i) {
            if (secret[i] == guess[i]) ++bulls;
            else {
                if (m[secret[i]]++ < 0) ++cows;
                if (m[guess[i]]-- > 0) ++ cows;
            }
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

Leetcode300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

1
2
3
Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

  • There may be more than one LIS combination, it is only necessary for you to return the length.
  • Your algorithm should run in O( n2 ) complexity.

这道题让我们求最长递增子串 Longest Increasing Subsequence 的长度，简称 LIS 的长度。首先来看一种动态规划 Dynamic Programming 的解法，这种解法的时间复杂度为 O(n2)，类似 brute force 的解法，维护一个一维 dp 数组，其中 dp[i] 表示以 nums[i] 为结尾的最长递增子串的长度，对于每一个 nums[i]，从第一个数再搜索到i，如果发现某个数小于 nums[i]，更新 dp[i]，更新方法为 dp[i] = max(dp[i], dp[j] + 1)，即比较当前 dp[i] 的值和那个小于 num[i] 的数的 dp 值加1的大小，就这样不断的更新 dp 数组，到最后 dp 数组中最大的值就是要返回的 LIS 的长度，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

下面来看一种优化时间复杂度到 O(nlgn) 的解法，这里用到了二分查找法，所以才能加快运行时间哇。思路是，先建立一个数组 ends，把首元素放进去，然后比较之后的元素，如果遍历到的新元素比 ends 数组中的首元素小的话，替换首元素为此新元素，如果遍历到的新元素比 ends 数组中的末尾元素还大的话，将此新元素添加到 ends 数组末尾(注意不覆盖原末尾元素)。如果遍历到的新元素比 ends 数组首元素大，比尾元素小时，此时用二分查找法找到第一个不小于此新元素的位置，覆盖掉位置的原来的数字，以此类推直至遍历完整个 nums 数组，此时 ends 数组的长度就是要求的LIS的长度，特别注意的是 ends 数组的值可能不是一个真实的 LIS，比如若输入数组 nums 为 {4, 2， 4， 5， 3， 7}，那么算完后的 ends 数组为 {2， 3， 5， 7}，可以发现它不是一个原数组的 LIS，只是长度相等而已，千万要注意这点。参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> ends{nums[0]};
        for (auto a : nums) {
            if (a < ends[0]) ends[0] = a;
            else if (a > ends.back()) ends.push_back(a);
            else {
                int left = 0, right = ends.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (ends[mid] < a) left = mid + 1;
                    else right = mid;
                }
                ends[right] = a;
            }
        }
        return ends.size();
    }
};