Leetcode701 - 800

Posted on

Leetcode701. Insert into a Binary Search Tree

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Given the tree:
        4
       / \
      2   7
     / \
    1   3
And the value to insert: 5
You can return this binary search tree:

         4
       /   \
      2     7
     / \   /
    1   3 5
This tree is also valid:

         5
       /   \
      2     7
     / \   
    1   3
         \
          4

非常简单，不用详细说了，递归插入一个节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == NULL){
            root = new TreeNode(val);
            return root;
        }
        if(val < root->val)
            root->left = insertIntoBST(root->left,val);
        else
            root->right = insertIntoBST(root->right,val);
        return root;
    }
};

Leetcode703. Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

1
2
3
4
5
6
7
8
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

创建一个优先队列，维护最大的k个数（其实是一个小顶堆）；每次add之后若size大于k则删除队列中的最小值，若小于k则不做操作。最后输出队顶元素即为所求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> q;
    int size;
    
    KthLargest(int k, vector<int>& nums) {
        int len = nums.size();
        size = k;
        for(int i = 0; i < len; i ++)
            add(nums[i]);
    }
    
    int add(int val) {
        q.push(val);
        if(q.size() > size)
            q.pop();
        return q.top();
    }
};

Leetcode704. Binary Search

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

1
2
3
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:
1
2
3
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

二分
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 search(vector<int>& nums, int target) {
        if(nums.size() == 0) 
            return -1;
        int left = 0, right = nums.size() - 1; 
        int mid;
        while(left <= right) {
             mid = left + (right - left) / 2;
            if(nums[mid] < target)
                left = mid + 1;
            else if(nums[mid] > target)
                right = mid - 1;
            else
                return mid;
        }
        if(nums[mid] == target)
            return mid;
        return -1;
    }
};

Leetcode705. Design HashSet

Design a HashSet without using any built-in hash table libraries.

To be specific, your design should include these functions:

add(value): Insert a value into the HashSet.
contains(value) : Return whether the value exists in the HashSet or not.
remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

1
2
3
4
5
6
7
8
9
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // returns true
hashSet.contains(3);    // returns false (not found)
hashSet.add(2);          
hashSet.contains(2);    // returns true
hashSet.remove(2);          
hashSet.contains(2);    // returns false (already removed)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MyHashSet {
public:
    /** Initialize your data structure here. */
    vector<bool> v;

    MyHashSet() {
        v.resize(1000001, 0);
    }
    
    void add(int key) {
        v[key] = true;
    }
    
    void remove(int key) {
        v[key] = false;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return v[key];
    }
};

Leetcode706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

  • put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
  • get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
  • remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

1
2
3
4
5
6
7
8
9
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found) 

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 MyHashMap {
public:
    vector<int> v;
    
    /** Initialize your data structure here. */
    MyHashMap() {
        v.resize(1000001, -1);
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        v[key] = value;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        return v[key];
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        v[key] = -1;
    }
};

由于存入 HashMap 的映射对儿也许不会跨度很大，那么直接就申请长度为 1000000 的数组可能会有些浪费，其实可以使用 1000 个长度为 1000 的数组来代替，那么就要用个二维数组啦，实际上开始只申请了 1000 个空数组，对于每个要处理的元素，首先对 1000 取余，得到的值就当作哈希值，对应申请的那 1000 个空数组的位置，在建立映射时，一旦计算出了哈希值，将对应的空数组 resize 为长度 1000，然后根据哈希值和 key/1000 来确定具体的加入映射值的位置。获取映射值时，计算出哈希值，若对应的数组不为空，直接返回对应的位置上的值。移除映射值一样的，先计算出哈希值，如果对应的数组不为空的话，找到对应的位置并重置为 -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
class MyHashMap {
public:
    MyHashMap() {
        data.resize(1000, vector<int>());
    }
    void put(int key, int value) {
        int hashKey = key % 1000;
        if (data[hashKey].empty()) {
            data[hashKey].resize(1000, -1);
        } 
        data[hashKey][key / 1000] = value;
    }
    int get(int key) {
        int hashKey = key % 1000;
        if (!data[hashKey].empty()) {
            return data[hashKey][key / 1000];
        } 
        return -1;
    }
    void remove(int key) {
        int hashKey = key % 1000;
        if (!data[hashKey].empty()) {
            data[hashKey][key / 1000] = -1;
        } 
    }

private:
    vector<vector<int>> data;
};

Leetcode707. Design Linked List

Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement these functions in your linked list class:

  • get(index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.
  • addAtHead(val) : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
  • addAtTail(val) : Append a node of value val to the last element of the linked list.
  • addAtIndex(index, val) : Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. If index is negative, the node will be inserted at the head of the list.
  • deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.

Example:

1
2
3
4
5
6
7
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2);  // linked list becomes 1->2->3
linkedList.get(1);            // returns 2
linkedList.deleteAtIndex(1);  // now the linked list is 1->3
linkedList.get(1);            // returns 3

Note:

  • All values will be in the range of [1, 1000].
  • The number of operations will be in the range of [1, 1000].

这道题让我们实现一个链表的数据结构，看需要实现的哪些函数，分别是根据坐标取结点，在链表开头和末尾加结点，根据坐标位置加结点，根据坐标位置删除结点。既然是结点组成的链表，那么肯定不能向数组那样可以根据坐标直接访问元素，肯定至少要知道表头的位置。同时，在根据链表取结点函数说明了给定的位置可能是非法的，则也要知道链表中所有元素的个数，这样可以快速的判定给定的位置是否合法。

好，下面来看每个函数如何实现。首先来看根据坐标取结点函数，先判定 index 是否合法，然后从表头向后移动 index 个位置，找到要返回的结点即可。对于增加表头函数就比较简单了，新建一个头结点，next 连上 head，然后 head 重新指向这个新结点，同时 size 自增1。同样，对于增加表尾结点函数，首先遍历到表尾，然后在之后连上一个新建的结点，同时 size 自增1。下面是根据位置来加结点，肯定还是先来判定 index 是否合法，题目要求有过变动，新加一条说是当 index 为负数时，要在表头加个结点，这样的话只需要判断 index 是否大于 size 这一种非法情况。然后再处理一个 corner case，就是当 index 小于等于0的时候，直接调用前面的表头加结点函数即可。然后就是往后遍历 index-1 个结点，这里为啥要减1呢，因为要加入结点的话，必须要知道加入位置前面一个结点才行，链表加入结点的问题之前的题目中做过很多，这里就不说细节了，最后 size 还是要自增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
42
43
44
45
46
47
48
49
50
51
52
53
54
class MyLinkedList {
public:
    MyLinkedList() {
        head = NULL;
        size = 0;
    }
    int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node *cur = head;
        for (int i = 0; i < index; ++i) cur = cur->next;
        return cur->val;
    }
    void addAtHead(int val) {
        Node *t = new Node(val, head);
        head = t;
        ++size;
    }
    void addAtTail(int val) {
        Node *cur = head;
        while (cur->next) cur = cur->next;
        cur->next = new Node(val, NULL);
        ++size;
    }
    void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index <= 0) {addAtHead(val); return;}
        Node *cur = head;
        for (int i = 0; i < index - 1; ++i) cur = cur->next;
        Node *t = new Node(val, cur->next);
        cur->next = t;
        ++size;
    }
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        if (index == 0) {
            head = head->next;
            --size;
            return;
        }
        Node *cur = head;
        for (int i = 0; i < index - 1; ++i) cur = cur->next;
        cur->next = cur->next->next;
        --size;
    }
    
private:
    struct Node {
        int val;
        Node *next;
        Node(int x, Node* n): val(x), next(n) {}
    };
    Node *head, *tail;
    int size;
};

Leetcode709. 转换成小写字母

太简单了

Leetcode712. Minimum ASCII Delete Sum for Two Strings

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

1
2
3
4
5
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

1
2
3
4
5
6
Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

这道题给了我们两个字符串，让我们删除一些字符使得两个字符串相等，我们希望删除的字符的ASCII码最小。这道题跟之前那道Delete Operation for Two Strings极其类似，那道题让求删除的最少的字符数，这道题换成了ASCII码值。其实很多大厂的面试就是这种改动，虽然很少出原题，但是这种小范围的改动却是很经常的，所以当背题侠是没有用的，必须要完全掌握了解题思想，并能举一反三才是最重要的。看到这种玩字符串又是求极值的题，想都不要想直接上DP，我们建立一个二维数组dp，其中dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符变相等所要删除的字符的最小ASCII码累加值。那么我们可以先初始化边缘，即有一个字符串为空的话，那么另一个字符串有多少字符就要删多少字符，才能变空字符串。

所以我们初始化dp[0][j]和dp[i][0]，计算方法就是上一个dp值加上对应位置的字符，有点像计算累加数组的方法，由于字符就是用ASCII表示的，所以我们不用转int，直接累加就可以。这里我们把dp[i][0]的计算放入大的循环中计算，是为了少写一个for循环。好，现在我们来看递推公式，需要遍历这个二维数组的每一个位置即dp[i][j]，当对应位置的字符相等时，s1[i-1] == s2[j-1]，(注意由于dp数组的i和j是从1开始的，所以字符串中要减1)，那么我们直接赋值为上一个状态的dp值，即dp[i-1][j-1]，因为已经匹配上了，不用删除字符。如果s1[i-1] != s2[j-1]，那么就有两种情况，我们可以删除s[i-1]的字符，且加上被删除的字符的ASCII码到上一个状态的dp值中，即dp[i-1][j] + s1[i-1]，或者删除s[j-1]的字符，且加上被删除的字符的ASCII码到上一个状态的dp值中，即dp[i][j-1] + s2[j-1]。这不难理解吧，比如sea和eat，当首字符s和e失配了，那么有两种情况，要么删掉s，用ea和eat继续匹配，或者删掉e，用sea和at继续匹配，记住删掉的字符一定要累加到dp值中才行，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int j = 1; j <= n; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1];
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = dp[i - 1][0] + s1[i - 1];
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = (s1[i - 1] == s2[j - 1]) ? dp[i - 1][j - 1] : min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
            }
        }
        return dp[m][n];
    }
};

我们也可以优化空间复杂度，使用一个一维数组dp，其中dp[i]表示字符串s1和字符串s2的前i个字符变相等所要删除的字符的最小ASCII码累加值。刚开始还是要初始化dp[j]，这里用变量t1和t2保存上一个状态的值，并不断更新。如果面试官没有特别的要求，还是用二维dp数组吧，毕竟逻辑更清晰一些，一维的容易写错～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<int> dp(n + 1, 0);
        for (int j = 1; j <= n; ++j) dp[j] = dp[j - 1] + s2[j - 1];
        for (int i = 1; i <= m; ++i) {
            int t1 = dp[0];
            dp[0] += s1[i - 1];
            for (int j = 1; j <= n; ++j) {
                int t2 = dp[j];
                dp[j] = (s1[i - 1] == s2[j - 1]) ? t1 : min(dp[j] + s1[i - 1], dp[j - 1] + s2[j - 1]);
                t1 = t2;
            }
        }
        return dp[n];
    }
};

Leetcode713. Subarray Product Less Than K

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

1
2
3
4
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

  • 0 < nums.length <= 50000.
  • 0 < nums[i] < 1000.
  • 0 <= k < 10^6.

这道题给了我们一个数组和一个数字K，让求子数组且满足乘积小于K的个数。既然是子数组，那么必须是连续的，所以肯定不能给数组排序了，这道题好在限定了输入数字都是正数，能稍稍好做一点。博主刚开始用的是暴力搜索的方法来做的，就是遍历所有的子数组算乘积和K比较，两个 for 循环就行了，但是 OJ 不答应。于是上网搜大神们的解法，思路很赞。相当于是一种滑动窗口的解法，维护一个数字乘积刚好小于k的滑动窗口，用变量 left 来记录其左边界的位置，右边界i就是当前遍历到的位置。遍历原数组，用 prod 乘上当前遍历到的数字，然后进行 while 循环，如果 prod 大于等于k，则滑动窗口的左边界需要向右移动一位，删除最左边的数字，那么少了一个数字，乘积就会改变，所以用 prod 除以最左边的数字，然后左边右移一位，即 left 自增1。当确定了窗口的大小后，就可以统计子数组的个数了，就是窗口的大小。为啥呢，比如 [5 2 6] 这个窗口，k还是 100，右边界刚滑到6这个位置，这个窗口的大小就是包含6的子数组乘积小于k的个数，即 [6], [2 6], [5 2 6]，正好是3个。所以窗口每次向右增加一个数字，然后左边去掉需要去掉的数字后，窗口的大小就是新的子数组的个数，每次加到结果 res 中即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int res = 0, prod = 1, left = 0;
        for (int i = 0; i < nums.size(); ++i) {
            prod *= nums[i];
            while (left <= i && prod >= k) prod /= nums[left++];
            res += i - left + 1;
        }
        return res;
    }
};

Leetcode714. Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

1
2
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8

Explanation: The maximum profit can be achieved by:

  • Buying at prices[0] = 1
  • Selling at prices[3] = 8
  • Buying at prices[4] = 4
  • Selling at prices[5] = 9
  • The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Note:

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

首先就是要确定需要保存的状态，题目所求为这么多天后能获得的最大收益，那么我们直接令A[i]为第i天所能取得的最大收益。但是我们很快发现，某一天其实会有两种可能性，就是持有一股、或者持有零股，所以我们令 A[i] 为第i天持有一股时的最大收益，而 B[i] 为持有零股时的最大收益。

A[i]状态转移方程分为两种情况，第i天买入和第i天继续持仓。

  • 第i天买入的情况：收益为 B[i−1]−prices[i]
  • 第i天继续持仓的情况：收益为 A[i−1]

以上两个方程乍看都很好理解，但是 A[i] 要在这两个的较大值中选择，在买入一股以后，状态由B转向A，他当前手上的资产为 现金+一股，如果我们想要知道这个决定是否比较优，那么就与相同资产状况的时候做比较，即第i天之前的现金+一股时的资产总额。

如果第i天买入要优于第i-1天手上有一股，我们就选择第i天买入，反之我们就认为 A[i−1] 更优，即保持手中有一股的状态。

B[i]的状态转移方程比较好理解，因为要满足第i天手上没有持有股票的情况的话，只有两种情况，第i天卖出或者继续不买入。对于第i天卖出的情况，算上每笔交易的手续费，此时收益为A[i−1]+prices[i]−fee；对于继续不买入的情况，其收益与前一天空持的收益相同，为B[i−1]。综合以上，总的状态转移方程为：A[i]=max(A[i−1],B[i−1]−prices[i])，B[i]=max(B[i−1],A[i−1]+prices[i]−fee)。

根据题意：最后结果为最后一天手上没有股票时的最大收益，即返回B[prices.size()−1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        // have one stock on hand
        vector<int> A(prices.size(), 0);
        // no stock on hand
        vector<int> B(prices.size(), 0);
        A[0] = A[0] - prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            A[i] = max(A[i - 1], B[i - 1] - prices[i]);
            B[i] = max(B[i - 1], A[i - 1] + prices[i] - fee);
        }
        return B[prices.size() - 1];
    }
};

Leetcode717 1-bit and 2-bit Characters

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:

1
2
3
4
5
Input: 
bits = [1, 0, 0]
Output: True
Explanation: 
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

Example 2:
1
2
3
4
5
Input: 
bits = [1, 1, 1, 0]
Output: False
Explanation: 
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.

Note:

  • 1 <= len(bits) <= 1000.
  • bits[i] is always 0 or 1.

看上去只要判断最后的两三位就可以了，但是既然给了一整个数组，肯定不会这么轻易就让你完成这道题的。我的方法是从头开始遍历这个数组，维护一个int bitA ,用来保存当前这个是不是1，如果是1，那它后面的一位就不用判断了，这两个肯定是组成一个字符的，跳过后一个继续，当前这个位是0，那它肯定是单独编码成字符的，直到最后一位字符，判断它是作为bitA，还是bitA后需要跳过的那个元素。
这里采用的思想是确保前面的元素都已经被确定分成两个一组或者一个一组了，最后的那个才能分得清是否单独分成一组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        int ret = false;
        while(1) {
            if(bits[i] == 0) {
                i ++;
                ret = true;
            }
            else if(bits[i] == 1) {
                i += 2;
                ret = false;
            }
            if(i >= bits.size())
                break;
        }
        return ret;
    }
};

Leetcode718. Maximum Length of Repeated Subarray

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

1
2
3
4
5
6
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

这道题给了我们两个数组A和B，让返回连个数组的最长重复子数组。那么如果将数组换成字符串，实际这道题就是求 Longest Common Substring 的问题了，而貌似 LeetCode 上并没有这种明显的要求最长相同子串的题，注意需要跟最长子序列 Longest Common Subsequence 区分开，关于最长子序列会在 follow up 中讨论。好，先来看这道题，既然是子数组，那么重复的地方一定是连续的，而且起点可能会是在数组中的任意地方，这样的话，最暴力的方法就是遍历A中的每个位置，把每个位置都当作是起点进行和B从开头比较，每次A和B都同时前进一个，假如相等，则计数器会累加1，不相等的话，计数器会重置为0，每次用计数器 cnt 的长度来更新结果 res。然后用同样的方法对B也处理一遍，把每个位置都当作是起点进行和A从开头比较，每次A和B都同时前进一个，这样最终下来，就可以求出最长重复子数组的长度，令人惊喜的是，这种暴力搜索解法的击败率相当的高，参见代码如下：

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 findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size(), res = 0;
        for (int offset = 0; offset < m; ++offset) {
            for (int i = offset, j = 0; i < m && j < n;) {
                int cnt = 0;
                while (i < m && j < n && A[i++] == B[j++]) ++cnt;
                res = max(res, cnt);
            }
        }
        for (int offset = 0; offset < n; ++offset) {
            for (int i = 0, j = offset; i < m && j < n;) {
                int cnt = 0;
                while (i < m && j < n && A[i++] == B[j++]) ++cnt;
                res = max(res, cnt);
            }
        }
        return res;
    }
};

我们还可以使用二分法+哈希表来做，别问博主怎么知道（看了题目标签，然后去论坛上找对应的解法即可，哈哈～）。虽然解法看起来很炫，但不太简洁，不是博主的 style，但还是收录进来吧。这里使用二分搜索法来找什么呢？其实是来直接查找最长重叠子数组的长度的，因为这个长度是有范围限制的，在 [0, min(m, n)] 之间，其中m和n分别是数组A和B的长度。这样每次折半出一个 mid，然后验证有没有这么一个长度为 mid 的子数组在A和B中都存在。从数组中取子数组有些麻烦，可以将数组转为字符串，取子串就相对来说容易一些了。将数组A和B都先转化为字符串 strA 和 strB，但是这里很 tricky，转换的方式不能是直接将整型数字转为字符串，再连接起来，这样会出错，因为会导致一个整型数占据多位字符，所以这里是需要将每个整型数直接加入字符串，从而将该整型数当作 ASCII 码来处理，寻找对应的字符，使得转换后的 strA 和 strB 变成各种凌乱的怪异字符，不过不影响解题。这里的二分应该属于博主之前的总结贴 LeetCode Binary Search Summary 二分搜索法小结 中的第四类，但是写法上却跟第三类的变形很像，因为博主平时的习惯是右边界设置为开区间，所以初始化为 min(m, n)+1，当然博主之前就说过二分搜索的写有各种各样的，像这个帖子中写法也是可以的。博主的这种写法实际上是在找第一个不大于目标值的数，这里的目标值就是那个 helper 子函数，也就是验证函数。如何实现这个验证函数呢，由于是要找长度为 len 的子串是否同时存在于 strA 和 strB 中，可以用一个 HashSet 保存 strA 中所有长度为 len 的子串，然后遍历 strB 中所有长度为 len 的子串，假如有任何一个在 HashSet 中存在，则直接返回 true，否则循环退出后，返回 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
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        string strA = stringify(A), strB = stringify(B);
        int left = 0, right = min(A.size(), B.size()) + 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (helper(strA, strB, mid)) left = mid + 1;
            else right = mid;
        }
        return right - 1;
    }
    bool helper(string& strA, string& strB, int len) {
        unordered_set<string> st;
        for (int i = 0, j = len; j <= strA.size(); ++i, ++j) {
            st.insert(strA.substr(i, j - i));
        }
        for (int i = 0, j = len; j <= strB.size(); ++i, ++j) {
            if (st.count(strB.substr(i, j - i))) return true;  
        } 
        return false;
    }
    string stringify(vector<int>& nums) {
        string res;
        for (int num : nums) res += num;
        return res;
    }
};

对于这种求极值的问题，动态规划 Dynamic Programming 一直都是一个很好的选择，这里使用一个二维的 DP 数组，其中 dp[i][j] 表示数组A的前i个数字和数组B的前j个数字在尾部匹配的最长子数组的长度，如果 dp[i][j] 不为0，则A中第i个数组和B中第j个数字必须相等，且 dp[i][j] 的值就是往前推分别相等的个数。

注意观察，dp 值不为0的地方，都是当A[i] == B[j]的地方，而且还要加上左上方的 dp 值，即dp[i-1][j-1]，所以当前的dp[i][j]就等于dp[i-1][j-1] + 1，而一旦A[i] != B[j]时，直接赋值为0，不用多想，因为子数组是要连续的，一旦不匹配了，就不能再增加长度了。每次算出一个 dp 值，都要用来更新结果 res，这样就能得到最长相同子数组的长度了，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int res = 0, m = A.size(), n = B.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = (A[i - 1] == B[j - 1]) ? dp[i - 1][j - 1] + 1 : 0;
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

Leetcode720. Longest Word in Dictionary

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.
Example 1:

1
2
3
4
5
Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:
1
2
3
4
5
Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

  • All the strings in the input will only contain lowercase letters.
  • The length of words will be in the range [1, 1000].
  • The length of words[i] will be in the range [1, 30].

如果这个有ab,abc，那么是不可以的，因为没有a，也就是说必须最长字母的每一个非空子串都在words里面。一开始没搞懂这个意思。

先对words进行排序。可以用一个hashset保存字符串（首先加入一个空串，便于长度为1的字符串和大于1的字符串同等处理），如果能找到这个字符串的子串（除去末尾最后一个字符），则将该字符串加入set;
同时保存最长字符串，如果字符串长度相等，则返回字典序小的那个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
	public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end());
        string result = "";
        vector<string> vec;
        vec.push_back("");
        for(int i = 0; i < words.size(); i ++) {
            string temp = words[i];
            temp.erase(temp.length()-1);
            if(find(vec.begin(), vec.end(), temp)!=vec.end()) {
                vec.push_back(words[i]);
                if(words[i].length() > result.length()) 
                    result = words[i];
                else if(words[i].length() == result.length())
                    result = result < words[i] ? result : words[i];
            }
        }
        return result;
    }
};

Leetcode721. Accounts Merge

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

1
2
3
Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]

Explanation:
1
2
3
4
The first and third John's are the same person as they have the common email "johnsmith@mail.com".
The second John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Note:

  • The length of accounts will be in the range [1, 1000].
  • The length of accounts[i] will be in the range [1, 10].
  • The length of accounts[i][j] will be in the range [1, 30].

这道题给了一堆人名和邮箱，一个名字可能有多个邮箱，但是一个邮箱只属于一个人，让我们把同一个人的邮箱都合并到一起，名字相同不一定是同一个人，只有当两个名字有相同的邮箱，才能确定是同一个人，题目中的例子很好说明了这个问题，输入有三个 John，最后合并之后就只有两个了。

这个归组类的问题，最典型的就是岛屿问题(例如 Number of Islands II)，很适合使用 Union Find 来做，LeetCode 中有很多道可以使用这个方法来做的题，比如 Friend Circles，Graph Valid Tree，Number of Connected Components in an Undirected Graph，和 Redundant Connection 等等。都是要用一个 root 数组，每个点开始初始化为不同的值，如果两个点属于相同的组，就将其中一个点的 root 值赋值为另一个点的位置，这样只要是相同组里的两点，通过 find 函数得到相同的值。在这里，由于邮件是字符串不是数字，所以 root 可以用 HashMap 来代替，还需要一个 HashMap 映射owner，建立每个邮箱和其所有者姓名之前的映射，另外用一个 HashMap 来建立用户和其所有的邮箱之间的映射，也就是合并后的结果。

首先遍历每个账户和其中的所有邮箱，先将每个邮箱的 root 映射为其自身，然后将 owner 赋值为用户名。然后开始另一个循环，遍历每一个账号，首先对帐号的第一个邮箱调用 find 函数，得到其父串p，然后遍历之后的邮箱，对每个遍历到的邮箱先调用 find 函数，将其父串的 root 值赋值为p，这样做相当于将相同账号内的所有邮箱都链接起来了。接下来要做的就是再次遍历每个账户内的所有邮箱，先对该邮箱调用 find 函数，找到父串，然后将该邮箱加入该父串映射的集合汇总，这样就就完成了合并。最后只需要将集合转为字符串数组，加入结果 res 中，通过 owner 映射找到父串的用户名，加入字符串数组的首位置，参见代码如下：

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
class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string>> res;
        unordered_map<string, string> root;
        unordered_map<string, string> owner;
        unordered_map<string, set<string>> m;
        for (auto account : accounts) {
            for (int i = 1; i < account.size(); ++i) {
                root[account[i]] = account[i];
                owner[account[i]] = account[0];
            }
        }
        for (auto account : accounts) {
            string p = find(account[1], root);
            for (int i = 2; i < account.size(); ++i) {
                root[find(account[i], root)] = p;
            }
        }
        for (auto account : accounts) {
            for (int i = 1; i < account.size(); ++i) {
                m[find(account[i], root)].insert(account[i]);
            }
        }
        for (auto a : m) {
            vector<string> v(a.second.begin(), a.second.end());
            v.insert(v.begin(), owner[a.first]);
            res.push_back(v);
        }
        return res;
    }
    string find(string s, unordered_map<string, string>& root) {
        return root[s] == s ? s : find(root[s], root);
    }
};

Leetcode724. Find Pivot Index

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

1
2
3
4
5
6
Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:

1
2
3
4
5
Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Note:

The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].

题目大意：在一个数组中找到一个数字的下标，要求这个数字左边的数字和等于右边的数字和，如果不存在就返回-1

分析：计算数组所有元素和sum，然后遍历数组，每次将前i-1个数字的和累加在t中，每次从sum中减去nums[i]，这样sum就是nums[i]后面所有数字的和，如果sum == t就返回i，否则就返回-1

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

Leetcode725. Split Linked List in Parts

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:

1
2
3
4
5
Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

1
2
3
4
Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

这道题目是希望把链表分成k组，其中有些限制条件，任意小组之间的长度不能超过1，而且小组链表长度是降序的。看懂题意这道题目的解题思路就很明确了：

  • step1：初始化一个大小为k的链表数组，默认值为NULL
  • step2：遍历链表并计算链表长度
  • step3：计算划分k组后每个小组的链表长度，并开始进行划分
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        ListNode *cur = head, *prev;
        int nums = 0;
        while(cur != NULL) {
            cur = cur->next;
            nums ++;
        }
        vector<int> length(k, nums/k);
        nums = nums % k;
        for (int i = 0; i < nums; i ++)
            length[i] ++;
        vector<ListNode*> res;
        cur = head;
        for (int i = 0; i < length.size(); i ++) {
            if (length[i] <= 0)
                res.push_back(NULL);
            else {
                res.push_back(cur);
                while(cur && length[i]--) {
                    prev = cur;
                    cur = cur->next;
                }
                prev->next = NULL;
            }
        }
        return res;
    }
};

Leetcode728 Self Dividing Numbers

A self-dividing number is a number that is divisible by every digit it contains. For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0. Also, a self-dividing number is not allowed to contain the digit zero. Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

1
2
3
Input: 
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

自除数 是指可以被它包含的每一位数除尽的数。例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。还有，自除数不允许包含 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
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<int> get_indics(int i) {
        vector<int> res;
        int temp;
        while(i > 0) {
            temp = i % 10;
            if(temp == 0) {
                res.clear();
                res.push_back(-1);
                return res;
            }
            res.push_back(temp);
            i /= 10;
        }
        return res;
    }
    
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> result, temp;
        int flag = true;
        for(int i = left; i <= right; i ++) {
            temp = get_indics(i);
            flag = true;
            if(temp.size()==1 && temp[0]==-1)
                continue;
            for(int j = 0; j < temp.size(); j ++){
                if(i % temp[j] != 0)
                    flag = false;
            }
            if(flag)
            result.push_back(i);
        }
        return result;
    }
};

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<int> selfDividingNumbers(int left, int right) {
        vector<int> result;
        bool flag;
        int temp;
        for(int i = left; i <= right; i ++) {
            int ii = i;
            flag = true;
            while(ii > 0) {
                temp = ii % 10;
                if(temp == 0 || i % temp != 0) {
                    flag=false;
                    break;
                }
                ii /= 10;
            }
            if (flag)
                result.push_back(i);
        }
        return result;
    }
};

Leetcode729. My Calendar I

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example 1:

1
2
3
4
5
6
7
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

  • The number of calls to MyCalendar.book per test case will be at most 1000.
  • In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

这道题让我们设计一个我的日历类，里面有一个book函数，需要给定一个起始时间和结束时间，与Google Calendar不同的是，我们的事件事件上不能重叠，实际上这道题的本质就是检查区间是否重叠。那么我们可以暴力搜索，对于每一个将要加入的区间，我们都和已经已经存在的区间进行比较，看是否有重复。而新加入的区间和当前区间产生重复的情况有两种，一种是新加入区间的前半段重复，并且，另一种是新加入区间的后半段重复。比如当前区间如果是[3, 8)，那么第一种情况下新加入区间就是[6, 9)，那么触发条件就是当前区间的起始时间小于等于新加入区间的起始时间，并且结束时间大于新加入区间的结束时间。第二种情况下新加入区间就是[2,5)，那么触发条件就是当前区间的起始时间大于等于新加入区间的起始时间，并且起始时间小于新加入区间的结束时间。这两种情况均返回false，否则就将新区间加入数组，并返回true即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MyCalendar {
public:
    MyCalendar() {}
    
    bool book(int start, int end) {
        for (auto a : cal) {
            if (a.first <= start && a.second > start) return false;
            if (a.first >= start && a.first < end) return false;
        }
        cal.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> cal;
};

下面这种方法将上面方法的两个if判断融合成为了一个，我们来观察两个区间的起始和结束位置的关系发现，如果两个区间的起始时间中的较大值小于结束区间的较小值，那么就有重合，返回false。比如 [3, 8) 和 [6, 9)，3和6中的较大值6，小于8和9中的较小值8，有重叠。再比如[3, 8) 和 [2, 5)，3和2中的较大值3，就小于8和5中的较小值5，有重叠。而对于[3, 8) 和 [9, 10)，3和9中的较大值9，不小于8和10中的较小值8，所以没有重叠，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyCalendar {
public:
    MyCalendar() {}
    
    bool book(int start, int end) {
        for (auto a : cal) {
            if (max(a.first, start) < min(a.second, end)) return false;
        }
        cal.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> cal;
};

Leetcode731. My Calendar II

Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example 1:

1
2
3
4
5
6
7
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true

Explanation:

  • The first two events can be booked. The third event can be double booked.
  • The fourth event (5, 15) can’t be booked, because it would result in a triple booking.
  • The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.
  • The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;
  • The time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Note:

  • The number of calls to MyCalendar.book per test case will be at most 1000.
  • In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

这道题是 My Calendar I 的拓展，之前那道题说是不能有任何的重叠区间，而这道题说最多容忍两个重叠区域，注意是重叠区域，不是事件。比如事件 A，B，C 互不重叠，但是有一个事件D，和这三个事件都重叠，这样是可以的，因为重叠的区域最多只有两个。所以关键还是要知道具体的重叠区域，如果两个事件重叠，那么重叠区域就是它们的交集，求交集的方法是两个区间的起始时间中的较大值，到结束时间中的较小值。可以用一个 TreeSet 来专门存重叠区间，再用一个 TreeSet 来存完整的区间，那么思路就是，先遍历专门存重叠区间的 TreeSet，因为能在这里出现的区间，都已经是出现两次了，如果当前新的区间跟重叠区间有交集的话，说明此时三个事件重叠了，直接返回 false。如果当前区间跟重叠区间没有交集的话，则再来遍历完整区间的集合，如果有交集的话，那么应该算出重叠区间并且加入放重叠区间的 TreeSet 中。最后记得将新区间加入完整区间的 TreeSet 中，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyCalendarTwo {
public:
    MyCalendarTwo() {}
    
    bool book(int start, int end) {
        for (auto &a : s2) {
            if (start >= a.second || end <= a.first) continue;
            return false;
        }
        for (auto &a : s1) {
            if (start >= a.second || end <= a.first) continue;
            s2.insert({max(start, a.first), min(end, a.second)});
        }
        s1.insert({start, end});
        return true;
    }

private:
    set<pair<int, int>> s1, s2;
};

下面这种方法相当的巧妙，建立一个时间点和次数之间的映射，规定遇到起始时间点，次数加1，遇到结束时间点，次数减1。那么首先更改新的起始时间 start 和结束时间 end 的映射，start 对应值增1，end 对应值减1。然后定义一个变量 cnt，来统计当前的次数。使用 TreeMap 具有自动排序的功能，所以遍历的时候就是按时间顺序的，最先遍历到的一定是一个起始时间，所以加上其映射值，一定是个正数。如果此时只有一个区间，就是刚加进来的区间的话，那么首先肯定遍历到 start，那么 cnt 此时加1，然后就会遍历到 end，那么此时 cnt 减1，最后下来 cnt 为0，没有重叠。还是用具体数字来说吧，现在假设 TreeMap 中已经加入了一个区间 [3, 5) 了，就有下面的映射：

3 -> 1

5 -> -1

假如此时要加入的区间为 [3, 8) 的话，则先对3和8分别加1减1，此时的映射为：

3 -> 2

5 -> -1

8 -> -1

最先遍历到3，cnt 为2，没有超过3，此时有两个事件有重叠，是允许的。然后遍历5和8，分别减去1，最终又变成0了，始终 cnt 没有超过2，所以是符合题意的。如果此时再加入一个新的区间 [1, 4)，则先对1和4分别加1减1，那么此时的映射为：

1 -> 1

3 -> 2

4 -> -1

5 -> -1

8 -> -1

先遍历到1，cnt为1，然后遍历到3，此时 cnt 为3了，那么就知道有三个事件有重叠区间了，所以这个新区间是不能加入的，需要还原其 start 和 end 做的操作，把 start 的映射值减1，end 的映射值加1，然后返回 false。否则没有三个事件有共同重叠区间的话，返回 true 即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class MyCalendarTwo {
public:
    MyCalendarTwo() {}
    
    bool book(int start, int end) {
        ++freq[start];
        --freq[end];
        int cnt = 0;
        for (auto f : freq) {
            cnt += f.second;
            if (cnt == 3) {
                --freq[start];
                ++freq[end];
                return false;
            }
        }
        return true;
    }

private:
    map<int, int> freq;
};

Leetcode733. Flood Fill

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:

1
2
3
4
5
6
7
8
9
Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

Note:

The length of image and image[0] will be in the range [1, 50].
The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

这道题给了一个用二维数组表示的图像，不同的数字代表不同的颜色，给了一个起始点坐标，还有一个新的颜色，让我们把起始点的颜色以及其相邻的同样的颜色都换成新的颜色。实际上就是一个找相同区间的题，可以用 BFS 或者 DFS 来做。先来看 BFS 的解法，使用一个队列 queue 来辅助，首先将给定点放入队列中，然后进行 while 循环，条件是 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
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if(image[sr][sc]==newColor)
            return image;
        int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
        queue<pair<int,int> > q;
        int m = image.size(), n = image[0].size();
        q.push(make_pair(sr,sc));
        int org_color = image[sr][sc];
        while(!q.empty()){
            pair<int,int> temp = q.front();
            q.pop();
            image[temp.first][temp.second] = newColor;
            for(int i = 0; i < 4; i ++) {
                int temp1 = temp.first+dir[i][0];
                int temp2 = temp.second+dir[i][1];
                if(0<=temp1 && temp1<m && 0<=temp2 && temp2<n && image[temp1][temp2]==org_color) {
                    q.push(make_pair(temp1,temp2));
                }
            }
        }
        return image;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    
    void color(vector<vector<int>>& image, int i, int j, int m, int n, int c, int o){
        if(i>=0 && j>=0 && i<m && j<n && image[i][j] == o){
            image[i][j] = c;
            color(image, i+1, j, m, n, c, o);
            color(image, i, j-1, m, n, c, o);
            color(image, i-1, j, m, n, c, o);
            color(image, i, j+1, m, n, c, o);
        }
    }
    
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if(newColor!=image[sr][sc])
            color(image, sr, sc, image.size(), image[0].size(), newColor, image[sr][sc]);   
        return image;
    }
};

Leetcode735. Asteroid Collision

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

1
2
3
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

1
2
3
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

1
2
3
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Example 4:

1
2
3
Input: asteroids = [-2,-1,1,2]
Output: [-2,-1,1,2]
Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.

给定一个不含0的长n数组A，表示一个数轴上的小行星的速度，正数代表向右，负数代表向左，绝对值代表小行星的质量。同向的小行星不会相撞，但反向的小行星会相撞，相撞的结果是，质量大的继续存在，小的爆炸；如果质量一样则都爆炸。问最后剩下的小行星的速度状态是什么，返回一个数组。

其实就是模拟相撞的过程。开个栈，遍历A，如果遇到了向右的小行星则直接入栈；否则，如果栈空或者栈顶也是向左的小行星，则也入栈，如果栈不空并且栈顶是向右的小行星，则进行相撞操作，直到栈空或者栈顶是向左的小行星为止，同时记录一下当前小行星是否爆炸。如果退出循环的时候当前小行星没有爆炸，则入栈。最后逆序存一下栈，就是答案。代码如下：

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:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> s;
        for (int i : asteroids) {
            if (i < 0) {
                if (s.empty() || s.top() < 0)
                    s.push(i);
                else {
                    bool is = true;
                    while(!s.empty() && s.top() > 0) {
                        int t = s.top();
                        s.pop();
                        if (t + i > 0) {
                            s.push(t);
                            is = false;
                            break;
                        }
                        else if (t + i == 0) {
                            is = false;
                            break;
                        }
                        else
                            continue;
                    }
                    if (is)
                        s.push(i);
                }
            }
            else
                s.push(i);
        }
        vector<int> res(s.size());
        for (int i = s.size()-1; i >= 0; i --) {
            res[i] = s.top();
            s.pop();
        }
        return res;
    }
};

Leetcode736. Parse Lisp Expression

给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。

表达式语法如下所示:

  • 表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。(整数可以是正整数、负整数、0)
  • let 表达式采用 “(let v1 e1 v2 e2 … vn en expr)” 的形式，其中 let 总是以字符串 “let”来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量 v1被分配为表达式 e1 的值，第二个变量 v2 被分配为表达式 e2 的值，依次类推；最终 let 表达式的值为 expr表达式的值。
  • add 表达式表示为 “(add e1 e2)” ，其中 add 总是以字符串 “add” 来表示，该表达式总是包含两个表达式 e1、e2 ，最终结果是 e1 表达式的值与 e2 表达式的值之 和 。
  • mult 表达式表示为 “(mult e1 e2)” ，其中 mult 总是以字符串 “mult” 表示，该表达式总是包含两个表达式 e1、e2，最终结果是 e1 表达式的值与 e2 表达式的值之 积 。
  • 在该题目中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。为了方便，”add” ，”let” ，”mult” 会被定义为 “关键字” ，不会用作变量名。
  • 最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（按括号计），然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息，请参阅示例。

示例 1：

1
2
3
4
5
6
输入：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
输出：14
解释：
计算表达式 (add x y), 在检查变量 x 值时，
在变量的上下文中由最内层作用域依次向外检查。
首先找到 x = 3, 所以此处的 x 值是 3 。

示例 2：

1
2
3
输入：expression = "(let x 3 x 2 x)"
输出：2
解释：let 语句中的赋值运算按顺序处理即可。

示例 3：

1
2
3
4
5
输入：expression = "(let x 1 y 2 x (add x y) (add x y))"
输出：5
解释：
第一个 (add x y) 计算结果是 3，并且将此值赋给了 x 。 
第二个 (add x y) 计算结果是 3 + 2 = 5 。

提示：

  • 1 <= expression.length <= 2000
  • exprssion 中不含前导和尾随空格
  • expressoin 中的不同部分（token）之间用单个空格进行分隔
  • 答案和所有中间计算结果都符合 32-bit 整数范围
  • 测试用例中的表达式均为合法的且最终结果为整数

这道题让我们解析Lisp语言的表达式。估计题目只让我们处理一些简单的情况，毕竟不可能让我们写一个编译器出来。我们通过分析例子发现，所有的命令都是用括号来包裹的，而且里面还可以嵌套小括号即子命令。让我们处理的命令只有三种，add，mult，和let。其中add和mult比较简单就是加法和乘法，就把后面两个数字或者子表达式的值加起来或成起来即可。let命令稍稍麻烦一些，后面可以跟好多变量或表达式，最简单的是三个，一般第一个是个变量，比如x，后面会跟一个数字或子表达式，就是把后面的数字或子表达式的值赋值给前面的变量，第三个位置是个表达式，其值是当前let命令的返回值。还有一个比较重要的特性是外层的变量值不会随着里层的变量值改变，比如对于下面这个例子：

1
(let x 2 (add (let x 3 (let x 4 x)) x))

刚开始x被赋值为2了，然后在返回值表达式中，又有一个add操作，add操作的第一个变量又是一个子表达式，在这个子表达式中又定义了一个变量x，并复制为3，再其返回值表达式又定义了一个变量x，赋值为4，并返回这个x，那么最内层的表达式的返回值是4，那么x被赋值为3的那层的返回值也是4，此时add的第一个数就是4，那么其第二个x是多少，其实这个x并没有被里层的x的影响，仍然是刚开始赋值的2，那么我们就看出特点了，外层的变量是能影响里层变量的，而里层变量无法影响外层变量。那么我们只要在递归的时候不加引用就行了，这样值就不会在递归函数中被更改了。

对于这种长度不定且每个可能包含子表达式的题，递归是一个很好的选择，由于需要给变量赋值，所以需要建立一个变量和其值之间的映射，然后我们就要来写递归函数了，最开始我们给定的表达式肯定是有括号的，所以我们先处理这种情况，括号对于我们的解析没有用，所以要去掉首尾的括号，然后我们用一个变量cur表示当前指向字符的位置，初始化为0，下面要做的就是先解析出命令单词，我们调用一个子函数parse，在parse函数中，简单的情况就是解析出add，mult，或let这三个命令单词，我们用一个指针来遍历字符，当越界或遇到空格就停止，但是如果我们需要解析的是个子表达式，而且里面可能还有多个子表达式，那么我们就需要找出最外面这个左括号对应的右括号，因为中间可能还会有别的左右括号，里面的内容就再之后再次调用递归函数时处理。判断的方法就是利用匹配括号的方法，用变量cnt来表示左括号的的个数，初始化为1，当要parse的表达式第一个字符是左括号时，进入循环，循环条件是cnt不为0，当遇到左括号时cnt自增1，反之当遇到右括号时cnt自减1，每次指针end都向右移动一个，最后我们根据end的位置减去初始时cur的值（保存在变量t中），可以得到表达式。如果解析出的是命令let，那么进行while循环，然后继续解析后面的内容，如果此时cur大于s的长度了，说明此时是let命令的最后一个部分，也就是返回值部分，直接调用递归函数返回即可。否则就再解析下一个部分，说明此时是变量和其对应值，我们要建立映射关系。如果之前解析出来的是add命令，那么比较简单，就直接解析出后面的两个部分的表达式，并分别调用递归函数，将递归函数的返回值累加并返回即可。对于mult命令同样的处理方式，只不过是将两个递归函数的返回值乘起来并返回。然后我们再来看如果表达式不是以左括号开头的，说明只能是数字或者变量，那么先来检测数字，如果第一个字符是负号或者0到9之间的数字，那么直接将表达式转为int型即可；否则的话就是变量，我们直接从哈希map中取值即可。最后需要注意的就是递归函数的参数哈希map一定不能加引用，具体可以参见上面那个例子的分析，加了引用后外层的变量值就会受内层的影响，这是不符合题意的，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
public:
    unordered_map<string, vector<int>> map;
    int evaluate(string expression) {
        int start = 0;
        return calc(expression, start);
    }

    int calc(string& expression, int& start) {
        if (expression[start] != '(') {
            if (islower(expression[start])) {
                string var = parseStr(expression, start);
                return map[var].back();
            }
            else {
                return parseInt(expression, start);
            }
        }
        int res;
        start ++;
        if (expression[start] == 'l') {
            start += 4;
            vector<string> vars;
            while(true) {
                if (!islower(expression[start])) {
                    res = calc(expression, start);
                    break;
                }
                string var = parseStr(expression, start);
                if (expression[start] = ')') {
                    res = map[var].back();
                    break;
                }
                vars.push_back(var);
                start ++;
                int e = parseInt(expression, start);
                map[var].push_back(e);
                start ++;
            }
        }
        else if (expression[start] == 'a') {
            start += 4;
            int t1 = calc(expression, start);
            start ++;
            int t2 = calc(expression, start);
            res = t1 + t2;
        }
        else if (expression[start] == 'm') {
            start += 5;
            int t1 = calc(expression, start);
            start ++;
            int t2 = calc(expression, start);
            res = t1 * t2;
        }
        start ++;
        return res;
    }

    int parseInt(string& expression, int& start) {
        int flag = 1, res = 0;
        int len = expression.length();
        if (expression[start] == '-') {
            flag = -1;
            start ++;
        }
        while(start < len && expression[start] >= '0' && expression[start] <= '9') {
            res = res * 10 + (expression[start] - '0');
            start++;
        }
        return res * flag;
    }

    string parseStr(string& expression, int& start) {
        string res;
        int len = expression.length();
        while(start < len && expression[start] != ' ' && expression[start] != ')') {
            res += expression[start];
            start ++;
        }
        return res;
    }
};

Leetcode738. Monotone Increasing Digits

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.

Example 1:

1
2
Input: n = 10
Output: 9

Example 2:

1
2
Input: n = 1234
Output: 1234

Example 3:

1
2
Input: n = 332
Output: 299

给定一个非负正整数n，求一个这样的非负整数x，x从左到右读是单调上升的（不要求严格上升），x ≤ n 并且x是满足这两个条件的最大整数。

先将n转为字符串s，然后从左向右扫描。如果一路都是递增的，那么直接返回n自己就好了。否则考虑如何求。我们找到第一个s [ i ] > s [ j ]的位置，这里下降了，需要作出调整。我们必须调整s [ i ]或者其左边的数，否则不能使得数字变得比n小。因为要使得答案尽量大，所以我们尝试改尽量低位的数字，我们就从s [ i ]开始向左找到第一个小于s [ i ]的数，如果找不到，则必须把开头改成s [ i ] − 1才能使得数字变小，接着后面全填9就行了；如果找到了，比如说s [ j ] < s [ i ]，那么可以修改的最低位就是s [ j + 1 ]，将其改为s [ j + 1 ] − 1然后后面全填9即可。代码如下：

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
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        char s[12];
        int len = 0, res = n;
        while(n > 0) {
            s[len++] = '0' + n % 10;
            n /= 10;
        }
        int i = 0, j = len-1;
        while(i <= j) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
            i ++;
            j --;
        }
        i = 0;
        while(i+1 < len && s[i] <= s[i+1])
            i ++;
        if (i == len-1)
            return res;
        j = i;
        while (j >= 0 && s[i] == s[j])
            j --;
        j ++;
        s[j++] --;
        for ( ; j < len; j ++)
            s[j] = '9';
        
        res = 0;
        for (i = 0; i < len; i ++)
            res = res * 10 + (s[i] - '0');
        return res;
    }
};

Leetcode739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

1
2
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Example 2:

1
2
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]

Example 3:

1
2
Input: temperatures = [30,60,90]
Output: [1,1,0]

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

正向遍历温度列表。对于温度列表中的每个元素 T[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 T[prevIndex] 和当前温度 T[i]，如果 T[i] > T[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        int len = t.size();
        vector<int> res(len, 0);
        stack<int> s;
        for (int i = 0; i < len; i ++) {
            while (!s.empty() && t[s.top()] < t[i]) {
                res[s.top()] = i - s.top();
                s.pop();
            }
            s.push(i);
        }
        return res;
    }
};

Leetcode740. Delete and Earn

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

1
2
3
4
5
Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

1
2
3
4
5
6
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

  • The length of nums is at most 20000.
  • Each element nums[i] is an integer in the range [1, 10000].

给出一组数，选择一个就删除它相邻大小的数，求最大的被选择数之和。

将值相等的数归在一起，设置一个数组sum，比如有三个3，那么sum[3]=9,这样处理之后，因为取一个数，那么与它相等的都会被取。再找状态转移方程，因为取i的话，那么i-1就取不了了，所以dp[i]=max(dp[i-2]+sum[i],sum[i-1])，因为自底向上求，所以dp可以用sum代替。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
         vector<int> sums(10001, 0);
        for (int num : nums) sums[num] += num;
        for (int i = 2; i < 10001; ++i) {
            sums[i] = max(sums[i - 1], sums[i - 2] + sums[i]);
        }
        return sums[10000];
    }
};

或者直接使用两个变量：

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 deleteAndEarn(vector<int>& nums) {
        vector<int> dp(10001, 0);
        for (int i : nums)
            dp[i] += i;
        int use = 0, not_use = 0, prev = -2;
        for (int i = 0; i < 10001; i ++) {
            if (dp[i] > 0) {
                int tmp = max(use, not_use);
                if (i - 1 != prev)
                    use = tmp + dp[i];
                else
                    use = not_use + dp[i];
            
            not_use = tmp;
            prev = i;
                }
        }
        return max(use, not_use);
    }
};

Leetcode743. Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

1
2
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

1
2
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

1
2
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

裸的最短路，使用dij求。

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:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> g(n+1, vector<int>(n+1, INT_MAX));
        vector<bool> flag(n+1, false);
        vector<int> dist(n+1, INT_MAX);
        int cnt = 1;
        flag[k] = true;
        for (int i = 0; i < times.size(); i ++)
            g[times[i][0]][times[i][1]] = times[i][2];
        for (int i = 1; i <= n; i ++)
            dist[i] = g[k][i]; 
        dist[k] = 0;
        while(cnt != n) {
            int tmp = -1, minn = INT_MAX;
            for (int i = 1; i <= n; i ++)
                if (!flag[i] && dist[i] < minn) {
                    minn = dist[i];
                    tmp = i;
                }
            if (tmp == -1)
                break;
            flag[tmp] = true;
            cnt ++;
            for (int i = 1; i <= n; i ++) {
                if (!flag[i] && g[tmp][i] != INT_MAX && dist[i] > dist[tmp]+g[tmp][i])
                    dist[i] = dist[tmp]+g[tmp][i];
            }
        }
        int res = INT_MIN;
        for (int i = 1; i <= n; i ++)
            res = max(res, dist[i]);
        if (res == INT_MAX)
            res = -1;
        return res;
    }
};

Leetcode744. Find Smallest Letter Greater Than Target

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = ‘z’ and letters = [‘a’, ‘b’], the answer is ‘a’.

Examples:

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
Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"

Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"

Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"

Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"

很不好的一道题，找到比target大的字母。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int cha = 99999;
        for(char c : letters) {
            if(c > target && (c-target) < cha) 
                cha = c - target;
        }
        return target + cha > 'z' ? letters[0] : target + cha;
    }
};

Leetcode746. Min Cost Climbing Stairs

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

1
2
3
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:
1
2
3
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

简单dp。这道题应该算是之前那道 Climbing Stairs 的拓展，这里不是求步数，而是每个台阶上都有一个 cost，让我们求爬到顶端的最小 cost 是多少。换汤不换药，还是用动态规划 Dynamic Programming 来做。这里定义一个一维的 dp数组，其中 dp[i] 表示爬到第i层的最小 cost，然后来想 dp[i] 如何推导。来思考一下如何才能到第i层呢？是不是只有两种可能性，一个是从第 i-2 层上直接跳上来，一个是从第 i-1 层上跳上来。不会再有别的方法，所以 dp[i] 只和前两层有关系，可以写做如下：
1
dp[i] = min(dp[i- 2] + cost[i - 2], dp[i - 1] + cost[i - 1])

最后返回最后一个数字dp[n]即可
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> v(cost.size()+1, 0);
        v[0] = 0;
        v[1] = 0;
        for(int i = 2; i < cost.size()+1; i ++) {
            v[i] = min(v[i-2]+cost[i-2], v[i-1]+cost[i-1]);
        }
        return v[cost.size()];
    }
};

Leetcode747. Largest Number At Least Twice of Others

In a given integer array nums, there is always exactly one largest element. Find whether the largest element in the array is at least twice as much as every other number in the array. If it is, return the index of the largest element, otherwise return -1.

Example 1:

1
2
3
4
Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Example 2:
1
2
3
Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

查找数组中最大的元素是否至少是数组中其他数字的两倍。是的话就返回最大元素的索引。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int max1 = -1, max2 = -1, index = -1;
        for(int i = 0; i < nums.size(); i ++) {
            if(nums[i] > max1) {
                max2 = max1;
                max1 = nums[i];
                index = i;
            }
            else if(nums[i] > max2) {
                max2 = nums[i];
            }
        }
        return max1 >= max2 * 2 ? index : -1;
    }
};

Leetcode748. Shortest Completing Word

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, “P” on the licensePlate still matches “p” on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of “PP”, the word “pair” does not complete the licensePlate, but the word “supper” does.

Example 1:

1
2
3
4
5
Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".
Note that the answer is not "step", because the letter "s" must occur in the word twice.
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:
1
2
3
4
Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
Output: "pest"
Explanation: There are 3 smallest length words that contains the letters "s".
We return the one that occurred first.

要找包含给出模板所有字母的最短单词，可以使用哈希表记录模板中每个字母的个数，再对应每个单词中每个字母出现的个数，如果后者中每个字母出现个数大于或等于前者，则改单词是完全包含模板的，找出其中长度最短的即可。
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
class Solution {
public:
    
    string tolow(string s) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] >= 'A' && s[i] <= 'Z') {
                s[i] = s[i]-'A'+'a';
            }
        }
        return s;
    }
    
    bool matched(string word, int* mymap) {
        int tmap[26];
        for (int i = 0; i < 26; i++) {
            tmap[i] = mymap[i];
        }
        for (int i = 0; i < word.length(); i++) {
            tmap[word[i]-'a']--;
        }
        for (int i = 0; i < 26; i++)
            if (tmap[i] > 0 )
                return false;
        return true;
    }
    
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        licensePlate = tolow(licensePlate);
         int m[26] = {0};
        for (int i = 0; i < licensePlate.length(); i ++) {
            if (licensePlate[i] <= 'z' && licensePlate[i] >= 'a') 
                m[licensePlate[i]-'a']++;
        }
        string result;
        int minn = 1001;
        for (auto word : words) {
            if (matched(word, m) && word.length() < minn) {
                minn = word.length();
                result = word;
            }
        }
        return result;        
    }
};

Leetcode752. Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.

The lock initially starts at ‘0000’, a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

1
2
3
4
5
6
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

1
2
3
4
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

1
2
3
4
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

1
2
Input: deadends = ["0000"], target = "8888"
Output: -1

这道题说有一种可滑动的四位数的锁，貌似行李箱上比较常见这种锁。给了我们一个目标值，还有一些死锁的情况，就是说如果到达这些死锁的位置，就不能再动了，相当于迷宫中的障碍物。然后问我们最少多少步可以从初始的0000位置滑动到给定的target位置。如果各位足够老辣的话，应该能发现其实本质就是个迷宫遍历的问题，只不过相邻位置不再是上下左右四个位置，而是四位数字每个都加一减一，总共有八个相邻的位置。遍历迷宫问题中求最短路径要用BFS来做，那么这道题也就是用BFS来解啦，和经典BFS遍历迷宫解法唯一不同的就是找下一个位置的地方，这里我们要遍历四位数字的每一位，然后分别加1减1，我们用j从-1遍历到1，遇到0跳过，也就是实现了加1减1的过程。然后我们要计算要更新位上的数字，为了处理9加1变0，和0减1变9的情况，我们统一给该位数字加上个10，然后再加或减1，最后再对10取余即可，注意字符和整型数之间通过加或减’0’来转换。我们用结果res来记录BFS遍历的层数，如果此时新生成的字符串等于target了，直接返回结果res，否则我们看如果该字符串不在死锁集合里，且之前没有遍历过，那么加入队列queue中，之后将该字符串加入visited集合中即可。注意这里在while循环中，由于要一层一层的往外扩展，一般的做法是会用一个变量len来记录当前的q.size()，博主为了简洁，使用了一个trick，就是从q.size()往0遍历，千万不能反回来，因为在计算的过程中q的大小会变化，如果让k < q.size() 为终止条件，绝b会出错，而我们初始化为q.size()就没事，参见代码如下：

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
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        queue<string> q;
        q.push("0000");
        int step = 0;
        set<string> visited;
        for (string s : deadends)
            visited.insert(s);
        
        while(!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i ++) {
                string tmp = q.front();
                q.pop();
                if (visited.count(tmp))
                    continue;
                if (tmp == target)
                    return step;
                for (int j = 0; j < 4; j ++) {
                    for (int k = -1; k < 2; k += 2) {
                        string next = tmp;
                        next[j] = '0' + (next[j] - '0' + k + 10) % 10;
                        q.push(next);
                    }
                }
                visited.insert(tmp);
            }
            step ++;
        }
        return -1;
    }
};

Leetcode754. Reach a Number

You are standing at position 0 on an infinite number line. There is a destination at position target.

You can make some number of moves numMoves so that:

On each move, you can either go left or right.During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction. Given the integer target, return the minimum number of moves required (i.e., the minimum numMoves) to reach the destination.

Example 1:

1
2
3
4
5
6
Input: target = 2
Output: 3
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to -1 (2 steps).
On the 3rd move, we step from -1 to 2 (3 steps).

Example 2:

1
2
3
4
5
Input: target = 3
Output: 2
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to 3 (2 steps).

这道题让我们从起点0开始，每次可以向数轴的左右两个方向中的任意一个走，第一步走距离1，第二步走距离2，以此类推，第n步走距离n，然后给了我们一个目标值 target，问最少用多少步可以到达这个值。这道题的正确解法用到了些数学知识，还有一些小 trick，首先来说说小 trick，第一个 trick 是到达 target 和 -target 的步数相同，因为数轴是对称的，只要将到达 target 的每步的距离都取反，就能到达 -target。下面来说第二个 trick，这个是解题的关键，比如说目标值是4，那么如果一直累加步数，直到其正好大于等于target时，有：

0 + 1 = 1

1 + 2 = 3

3 + 3 = 6

第三步加上3，得到了6，超过了目标值4，超过了的距离为2，是偶数，那么实际上只要将加上距离为1的时候，不加1，而是加 -1，那么此时累加和就损失了2，那么正好能到目标值4，如下：

0 - 1 = -1

-1 + 2 = 1

1 + 3 = 4

这就是第二个 trick 啦，当超过目标值的差值d为偶数时，只要将第 d/2 步的距离取反，就能得到目标值，此时的步数即为到达目标值的步数。那么，如果d为奇数时，且当前为第n步，那么看下一步 n+1 的奇偶，如果 n+1 为奇数，则加上 n+1 再做差，得到的差值就为偶数了，问题解决，如果 n+1 为偶数，则还得加上 n+2 这个奇数，才能让差值为偶数，这样就多加了两步。分析到这里，解题思路也就明晰了吧：

先对 target 取绝对值，因为正负不影响最小步数。然后求出第n步，使得从1累加到n刚好大于等于 target

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int res = 0, sum = 0;
        while(sum < target || ( sum - target) % 2 == 1) {
            res ++;
            sum += res;
        }
        return res;
    }
};

Leetcode756. Pyramid Transition Matrix

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string, like ‘Z’.

For every block of color C we place not in the bottom row, we are placing it on top of a left block of color A and right block of color B. We are allowed to place the block there only if (A, B, C) is an allowed triple.

We start with a bottom row of bottom, represented as a single string. We also start with a list of allowed triples allowed. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: bottom = "XYZ", allowed = ["XYD", "YZE", "DEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  D   E
 / \ / \
X   Y   Z

This works because ('X', 'Y', 'D'), ('Y', 'Z', 'E'), and ('D', 'E', 'A') are allowed triples.

Example 2:

1
2
3
4
5
Input: bottom = "XXYX", allowed = ["XXX", "XXY", "XYX", "XYY", "YXZ"]
Output: false
Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.

Note:

  • bottom will be a string with length in range [2, 8].
  • allowed will have length in range [0, 200].
  • Letters in all strings will be chosen from the set {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}.

这道题让我们累一个金字塔，用字母来代表每块砖的颜色，给了一个allowed数组，里面都是长度为三的字符串，比如“ABC”表示C可以放在A和B的上方，注意AB上面也可以放其他的，比如“ABD”也可以同时出现，不过搭积木的时候只能选择一种。给了我们一个bottom字符串，是金字塔的底层，问我们能不能搭出一个完整的金字塔。那么实际上我们就是从底层开始，一层一层的向上来累加，直到搭出整个金字塔。我们先来看递归的解法，首先由于我们想快速知道两个字母上方可以放的字母，需要建立基座字符串和上方字符集合之间的映射，由于上方字符可以不唯一，所以用个HashSet来放字符。我们的递归函数有三个参数，当前层字符串cur，上层字符串above，还有我们的HashMap。如果cur的大小为2，above的大小为1，那么说明当前已经达到金字塔的顶端了，已经搭出来了，直接返回true。否则看，如果上一层的长度比当前层的长度正好小一个，说明上一层也搭好了，我们现在去搭上上层，于是调用递归函数，将above当作当前层，空字符串为上一层，将调用的递归函数结果直接返回。否则表示我们还需要继续去搭above层，我们先算出above层的长度pos，然后从当前层的pos位置开始取两个字符，就是above层接下来需要搭的字符的基座字符，举个例子如下：

1
2
3
  D   
 / \ / \
A   B   C

我们看到现在above层只有一个D，那么pos为1，在cur层1位置开始取两个字符，得到”BC”，即是D的下一个位置的字符的基座字符串base。取出了base后，如果HashMap中有映射，则我们遍历其映射的字符集合中的所有字符，对每个字符都调用递归函数，此时above字符串需要加上这个遍历到的字符，因为我们在尝试填充这个位置，如果有返回true的，那么当前递归函数就返回true了，否则最终返回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
class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {   
        unordered_map<string, unordered_set<char>> m;
        for (string str : allowed) {
            m[str.substr(0, 2)].insert(str[2]);
        }
        return helper(bottom, "", m);
    }
    bool helper(string cur, string above, unordered_map<string, unordered_set<char>>& m) {
        if (cur.size() == 2 && above.size() == 1) return true;
        if (above.size() == cur.size() - 1) return helper(above, "", m);
        int pos = above.size();
        string base = cur.substr(pos, 2);
        if (m.count(base)) {
            for (char ch : m[base]) {
                if (helper(cur, above + string(1, ch), m)) {
                    return true;
                }
            }
        }
        return false;
    }
};

下面来看一种迭代的写法，这是一种DP的解法，建立一个三维的dp数组，其中dp[i][j][ch]表示在金字塔(i, j)位置上是否可以放字符ch，金字塔的宽和高已经确定了，都是n。每个位置对应着nxn的数组的左半边，如下所示：

F
D E _
A B C

除了底层，每个位置可能可以放多个字符，所以这里dp数组是一个三维数组，第三维的长度为7，因为题目中限定了字母只有A到G共7个，如果dp值为true，表示该位置放该字母，我们根据bottom字符串来初始化dp数组的底层。这里还是需要一个HashMap，不过跟上面的解法略有不同的是，我们建立上方字母跟其能放的基座字符串集合的映射，因为一个字母可能可以放多个位置，所以用个集合来表示。然后我们就开始从倒数第二层开始往顶部更新啦，对于金字塔的每个位置，我们都遍历A到G中所有的字母，如果当前字母在HashMap中有映射，则我们遍历对应的基座字符串集合中的所有字符串，基座字符串共有两个字母，左边的字母对应的金字塔中的位置是(i + 1, j)，右边的字母对应的位置是(i + 1, j + 1)，我们只要在这两个位置上分别查询对应的字母的dp值是否为true，是的话，说明当前位置有字母可以放，我们将当前位置的字母对应的dp值赋值为true。这样，当我们整个更新完成了之后，我们只要看金字塔顶端位置(0, 0)是否有字母可以放，有的话，说明可以搭出金字塔，返回true，否则返回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
class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        int n = bottom.size();
        vector<vector<vector<bool>>> dp(n, vector<vector<bool>>(n, vector<bool>(7, false)));
        unordered_map<char, unordered_set<string>> m;
        for (string str : allowed) {
            m[str[2]].insert(str.substr(0, 2));
        }
        for (int i = 0; i < n; ++i) {
            dp[n - 1][i][bottom[i] - 'A'] = true;
        }
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                for (char ch = 'A'; ch <= 'G'; ++ch) {
                    if (!m.count(ch)) continue;
                    for (string str : m[ch]) {
                        if (dp[i + 1][j][str[0] - 'A'] && dp[i + 1][j + 1][str[1] - 'A']) {
                            dp[i][j][ch - 'A'] = true;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < 7; ++i) {
            if (dp[0][0][i]) return true;
        }
        return false;
    }
};

Leetcode761. Special Binary String

Special binary strings are binary strings with the following two properties:

  • The number of 0’s is equal to the number of 1’s.
  • Every prefix of the binary string has at least as many 1’s as 0’s.

Given a special string S, a move consists of choosing two consecutive, non-empty, special substrings of S, and swapping them. (Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.)

At the end of any number of moves, what is the lexicographically largest resulting string possible?

Example 1:

1
2
3
4
5
Input: S = "11011000"
Output: "11100100"
Explanation:
The strings "10" [occuring at S[1]] and "1100" [at S[3]] are swapped.
This is the lexicographically largest string possible after some number of swaps.

Note:

  • S has length at most 50.
  • S is guaranteed to be a special binary string as defined above.

这道题给了我们一个特殊的二进制字符串，说是需要满足两个要求，一是0和1的个数要相等，二是任何一个前缀中的1的个数都要大于等于0的个数。根据压力山大大神的帖子，其实就是一个括号字符串啊。这里的1表示左括号，0表示右括号，那么题目中的两个限制条件其实就是限定这个括号字符串必须合法，即左右括号的个数必须相同，且左括号的个数随时都要大于等于右括号的个数，可以参见类似的题目Valid Parenthesis String。那么这道题让我们通过交换子字符串，生成字母顺序最大的特殊字符串，注意这里交换的子字符串也必须是特殊字符串，满足题目中给定的两个条件，换作括号来说就是交换的子括号字符串也必须是合法的。那么我们来想什么样的字符串是字母顺序最大的呢，根据题目中的例子可以分析得出，应该是1靠前的越多越好，那么换作括号来说就是括号嵌套多的应该放在前面。比如我们分析题目中的例子:

11011000 -> (()(()))

11100100 -> ((())())

我们发现，题目中的例子中的交换操作其实是将上面的红色部分和蓝色部分交换了，因为蓝色的部分嵌套的括号多，那么左括号就多，在前面的1就多，所以字母顺序大。所以我们要做的就是将中间的子串分别提取出来，然后排序，再放回即可。上面的这个例子相对简单一些，实际上上面的红色和蓝色部分完全可以更复杂，所以再给它们排序之前，其自身的顺序应该已经按字母顺序排好了才行，这种特点天然适合递归的思路，先递归到最里层，然后一层一层向外扩展，直至完成所有的排序。

好，下面我们来看递归函数的具体写法，由于我们移动的子字符串也必须是合法的，那么我们利用检测括号字符串合法性的一个最常用的方法，就是遇到左括号加1，遇到右括号-1，这样得到0的时候，就是一个合法的子字符串了。我们用变量i来统计这个合法子字符串的起始位置，字符串数组v来保存这些合法的子字符串。好了，我们开始遍历字符串S，遇到1，cnt自增1，否则自减1。当cnt为0时，我们将这个字串加入v，注意前面说过，我们需要给这个字串自身也排序，所以我们要对自身调用递归函数，我们不用对整个子串调用递归，因为字串的起始位置和结束位置是确定的，一定是1和0，我们只需对中间的调用递归即可，然后更新i为j+1。当我们将所有排序后的合法字串存入v中后，我们对v进行排序，将字母顺序大的放前面，最后将其连为一个字符串即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string makeLargestSpecial(string S) {
        int cnt = 0, i = 0;
        vector<string> v;
        string res = "";
        for (int j = 0; j < S.size(); ++j) {
            cnt += (S[j] == '1') ? 1 : -1;
            if (cnt == 0) {
                v.push_back('1' + makeLargestSpecial(S.substr(i + 1, j - i - 1)) + '0');
                i = j + 1;
            }
        }
        sort(v.begin(), v.end(), greater<string>());
        for (int i = 0; i < v.size(); ++i) res += v[i];
        return res;
    }
};

Leetcode762. Prime Number of Set Bits in Binary Representation

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

1
2
3
4
5
6
7
Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)

Example 2:
1
2
3
4
5
6
7
8
9
Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)

判断一个范围内的数的二进制表示中的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
class Solution {
public:
    
    bool isprime(int x) {
        if(x == 0 || x == 1)
            return false;
        int xx = sqrt(x);
        for(int i = 2; i <= xx; i ++) {
            if(!(x % i))
                return false;
        }
        return true;
    }
    
    int getbit(int x) {
        int res = 0;
        while(x) {
            int temp = x & 1;
            res = temp == 1 ? res+1 : res;
            x = x >> 1;
        }
        return res;
    }
    
    int countPrimeSetBits(int L, int R) {
        int res = 0;
        for(int i = L; i <= R; i ++) {
            int bit_num = getbit(i);
            printf("%d\n", bit_num);
            if(isprime(bit_num))
                res ++;
        }
        return res;
    }
};

Leetcode763. Partition Labels

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

1
2
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]

Explanation:

  • The partition is “ababcbaca”, “defegde”, “hijhklij”.
  • This is a partition so that each letter appears in at most one part.
  • A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.

Note:

  • S will have length in range [1, 500].
  • S will consist of lowercase letters (‘a’ to ‘z’) only.

字符串分割，且每一个字符只能最多出现在一个子串中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> res;
        int a[26];
        for(int i=0;i<S.size();i++){
            a[((int)(S[i]-'a'))]=i;
        }
        int j=0,temp =0;
        for(int i=0;i<S.size();i++){
            j=max(j,a[((int)(S[i]-'a'))]);
            if(i==j){
                res.push_back(i-temp+1);
                temp = i+1;
            }
        }
        
        return res;
    }
};

Leetcode764. Largest Plus Sign

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An “ axis-aligned plus sign of1s of order k” has some center grid[x][y] = 1 along with 4 arms of length k-1going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

Example 1:

1
2
3
4
5
6
7
8
9
Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.

Example 2:

1
2
3
4
Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.

Example 3:

1
2
3
4
Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.

Note:

  • N will be an integer in the range [1, 500].
  • mines will have length at most 5000.
  • mines[i] will be length 2 and consist of integers in the range [0, N-1].

(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)

这道题给了我们一个数字N，表示一个NxN的二位数字，初始化均为1，又给了一个mines数组，里面是一些坐标，表示数组中这些位置都为0，然后让我们找最大的加型符号。所谓的加型符号是有数字1组成的一个十字型的加号，题目中也给出了长度分别为1，2，3的加型符号的样子。好，理解了题意以后，我们来想想该如何破题。首先，最简单的就是考虑暴力搜索啦，以每个1为中心，向四个方向分别去找，只要任何一个方向遇到了0就停止，然后更新结果res。暴力搜索的时间复杂度之所以高的原因是因为对于每一个1都要遍历其上下左右四个方向，有大量的重复计算，我们为了提高效率，可以对于每一个点，都计算好其上下左右连续1的个数。博主最先用的方法是建立四个方向的dp数组，dp[i][j]表示 (i, j) 位置上该特定方向连续1的个数，那么就需要4个二维dp数组，举个栗子，比如：

原数组：

1
2
3
1  0  1  0
1  1  1  1
1  0  1  1

那么我们建立left数组是当前及其左边连续1的个数，如下所示：

1
2
3
1  0  1  0
1  2  3  4
1  0  1  2

right数组是当前及其右边连续1的个数，如下所示：

1
2
3
1  0  1  0
4  3  2  1
1  0  2  1

up数组是当前及其上边连续1的个数，如下所示：

1
2
3
1  0  1  0
2  1  2  1
3  0  3  2

down数组是当前及其下边连续1的个数，如下所示：

1
2
3
3  0  3  0
2  1  2  2
1  0  1  1

我们需要做的是在这四个dp数组中的相同位置的四个值中取最小的一个，然后在所有的这些去除的最小值中选最大一个返回即可。为了节省空间，我们不用四个二维dp数组，而只用一个就可以了，因为对于每一个特定位置，我们只需要保留较小值，所以在更新的时候，只需要跟原来值相比取较小值即可。在计算down数组的时候，我们就可以直接更新结果res了，因为四个值都已经计算过了，我们就不用再重新在外面开for循环了，参见代码如下：

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
class Solution {
public:
    int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {
        int res = 0, cnt = 0;
        vector<vector<int>> dp(N, vector<int>(N, 0));
        unordered_set<int> s;
        for (auto mine : mines) s.insert(mine[0] * N + mine[1]);
        for (int j = 0; j < N; ++j) {
            cnt = 0;
            for (int i = 0; i < N; ++i) { // up
                cnt = s.count(i * N + j) ? 0 : cnt + 1;
                dp[i][j] = cnt;
            }
            cnt = 0;
            for (int i = N - 1; i >= 0; --i) { // down
                cnt = s.count(i * N + j) ? 0 : cnt + 1;
                dp[i][j] = min(dp[i][j], cnt);
            }
        }
        for (int i = 0; i < N; ++i) {
            cnt = 0;
            for (int j = 0; j < N; ++j) { // left
                cnt = s.count(i * N + j) ? 0 : cnt + 1;
                dp[i][j] = min(dp[i][j], cnt);
            }
            cnt = 0;
            for (int j = N - 1; j >= 0; --j) { // right
                cnt = s.count(i * N + j) ? 0 : cnt + 1;
                dp[i][j] = min(dp[i][j], cnt);
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

LeetCode765. Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

1
2
3
Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

1
2
3
Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

  • len(row) is even and in the range of [4, 60].
  • row is guaranteed to be a permutation of 0…len(row)-1.

这道题给了我们一个长度为n的数组，里面包含的数字是 [0, n-1] 范围内的数字各一个，让通过调换任意两个数字的位置，使得相邻的奇偶数靠在一起。因为要两两成对，所以题目限定了输入数组必须是偶数个。要明确的是，组成对儿的两个是从0开始，每两个一对儿的。比如0和1，2和3，像1和2就不行。而且检测的时候也是两个数两个数的检测，左右顺序无所谓，比如2和3，或者3和2都行。当暂时对如何用代码来解决问题没啥头绪的时候，一个很好的办法是，先手动解决问题，意思是，假设这道题不要求你写代码，就让你按照要求排好序怎么做。随便举个例子来说吧，比如：

[3 1 4 0 2 5]

如何将其重新排序呢？首先明确，交换数字位置的动机是要凑对儿，如果交换的两个数字无法组成新对儿，那么这个交换就毫无意义。来手动交换吧，两个两个的来看数字，前两个数是3和1，知道其不成对儿，数字3的老相好是2，不是1，那么怎么办呢？就把1和2交换位置呗。好，那么现在3和2牵手成功，度假去了，再来看后面的：

[3 2 4 0 1 5]

再取两数字，4和0，互不认识！4跟5有一腿儿，不是0，那么就把0和5，交换一下吧，得到：

[3 2 4 5 1 0]

好了，再取最后两个数字，1和0，两口子，不用动！前面都成对的话，最后两个数字一定成对。而且这种方法所用的交换次数一定是最少的，不要问博主怎么证明，博主也不会 |||-.-～ 明眼人应该已经看出来了，这就是一种贪婪算法 Greedy Algorithm。思路有了，代码就很容易写了，注意这里在找老伴儿时用了一个 trick，一个数 ‘异或’ 上1就是其另一个位，这个不难理解，如果是偶数的话，最后位是0，‘异或’上1等于加了1，变成了可以的成对奇数。如果是奇数的话，最后位是1，‘异或’上1后变为了0，变成了可以的成对偶数。参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int res = 0, n = row.size();
        for (int i = 0; i < n; i += 2) {
            if (row[i + 1] == (row[i] ^ 1)) continue;
            ++res;
            for (int j = i + 1; j < n; ++j) {
                if (row[j] == (row[i] ^ 1)) {
                    row[j] = row[i + 1];
                    row[i + 1] = row[i] ^ 1;
                    break;
                }
            }
        }
        return res;
    }
};

下面来看一种使用联合查找 Union Find 的解法。该解法对于处理群组问题时非常有效，比如岛屿数量有关的题就经常使用 UF 解法。核心思想是用一个 root 数组，每个点开始初始化为不同的值，如果两个点属于相同的组，就将其中一个点的 root 值赋值为另一个点的位置，这样只要是相同组里的两点，通过 find 函数会得到相同的值。 那么如果总共有n个数字，则共有 n/2 对儿，所以初始化 n/2 个群组，还是每次处理两个数字。每个数字除以2就是其群组号，那么属于同一组的两个数的群组号是相同的，比如2和3，其分别除以2均得到1，所以其组号均为1。那么这对解题有啥作用呢？作用忒大了，由于每次取的是两个数，且计算其群组号，并调用 find 函数，那么如果这两个数的群组号相同，那么 find 函数必然会返回同样的值，不用做什么额外动作，因为本身就是一对儿。如果两个数不是一对儿，那么其群组号必然不同，在二者没有归为一组之前，调用 find 函数返回的值就不同，此时将二者归为一组，并且 cnt 自减1，忘说了，cnt 初始化为总群组数，即 n/2。那么最终 cnt 减少的个数就是交换的步数，但是这里为了简便，直接用个 res 变量来统计群组减少的个数，还是用上面讲解中的例子来说明吧：

[3 1 4 0 2 5]

最开始的群组关系是：

群组0：0，1

群组1：2，3

群组2：4，5

取出前两个数字3和1，其群组号分别为1和0，带入 find 函数返回不同值，则此时将群组0和群组1链接起来，变成一个群组，则此时只有两个群组了，res 自增1，变为了1。

群组0 & 1：0，1，2，3

群组2：4，5

此时取出4和0，其群组号分别为2和0，带入 find 函数返回不同值，则此时将群组 0&1 和群组2链接起来，变成一个超大群组，res 自增1，变为了2。

群组0 & 1 & 2：0，1，2，3，4，5

此时取出最后两个数2和5，其群组号分别为1和2，因为此时都是一个大组内的了，带入 find 函数返回相同的值，不做任何处理。最终交换的步数就是 res 值，为2，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int res = 0, n = row.size();
        vector<int> root(n, 0);
        for (int i = 0; i < n; ++i) root[i] = i;
        for (int i = 0; i < n; i += 2) {
            int x = find(root, row[i] / 2);
            int y = find(root, row[i + 1] / 2);
            if (x != y) {
                root[x] = y;
                ++res;
            }
        }
        return res;
    }
    int find(vector<int>& root, int i) {
        return (i == root[i]) ? i : find(root, root[i]);
    }
};

Leetcode766. Toeplitz Matrix

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input:
matrix = [
  [1,2,3,4],
  [5,1,2,3],
  [9,5,1,2]
]
Output: True
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

Example 2:
1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,2],
  [2,2]
]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

矩阵坐标瞎转换……强行模拟出来了。
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:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        
        for(int i = 0; i < m; i ++) {
            int ii = i;
            int constant = matrix[ii][0];
            for(int j = 0; j < n && ii < m; ii ++, j ++)
                if(constant != matrix[ii][j]) {
                    return false;
                }
        }
        
        for(int j = 0; j < n; j ++) {
            int jj = j;
            int constant = matrix[0][jj];
            for(int i = 0; i < m && jj < n; i ++, jj ++)
                if(constant != matrix[i][jj]) {
                    return false;
                }
        }
        return true;
    }
};

Leetcode767. Reorganize String

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

1
2
Input: S = "aab"
Output: "aba"

Example 2:

1
2
Input: S = "aaab"
Output: ""

Note:

  • S will consist of lowercase letters and have length in range [1, 500].

这道题给了一个字符串，让我们重构这个字符串，使得相同的字符不会相邻，如果无法做到，就返回空串，题目中的例子很好的说明了这一点。要统计每个字符串出现的次数啊，这里使用 HashMap 来建立字母和其出现次数之间的映射。由于希望次数多的字符排前面，可以使用一个最大堆，C++ 中就是优先队列 Priority Queue，将次数当做排序的 key，把次数和其对应的字母组成一个 pair，放进最大堆中自动排序。这里其实有个剪枝的 trick，如果某个字母出现的频率大于总长度的一半了，那么必然会有两个相邻的字母出现。这里博主就不证明了，感觉有点像抽屉原理。所以在将映射对加入优先队列时，先判断下次数，超过总长度一半了的话直接返回空串就行了。

接下来，每次从优先队列中取队首的两个映射对儿处理，因为要拆开相同的字母，这两个映射对儿肯定是不同的字母，可以将其放在一起，之后需要将两个映射对儿中的次数自减1，如果还有多余的字母，即减1后的次数仍大于0的话，将其再放回最大堆。由于是两个两个取的，所以最后 while 循环退出后，有可能优先队列中还剩下了一个映射对儿，此时将其加入结果 res 即可。而且这个多余的映射对儿一定只有一个字母了，因为提前判断过各个字母的出现次数是否小于等于总长度的一半，按这种机制来取字母，不可能会剩下多余一个的相同的字母，参见代码如下：

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:
    string reorganizeString(string S) {
        string res = "";
        unordered_map<char, int> m;
        priority_queue<pair<int, char>> q;
        for (char c : S) ++m[c];
        for (auto a : m) {
            if (a.second > (S.size() + 1) / 2) return "";
            q.push({a.second, a.first});
        }
        while (q.size() >= 2) {
            auto t1 = q.top(); q.pop();
            auto t2 = q.top(); q.pop();
            res.push_back(t1.second);
            res.push_back(t2.second);
            if (--t1.first > 0) q.push(t1);
            if (--t2.first > 0) q.push(t2);
        }
        if (q.size() > 0) res.push_back(q.top().second);
        return res;
    }
};

下面这种解法使用了一个长度为 26 的一位数组 cnt 来代替上面的 HashMap 进行统计字母的出现次数，然后比较秀的一点是，把上面的映射对儿压缩成了一个整数，做法是将次数乘以了 100，再加上当前字母在一位数字中的位置坐标i，这样一个整数就同时 encode 了次数和对应字母的信息了，而且之后 decode 也很方便。数组 cnt 更新好了后，需要排个序，这一步就是模拟上面解法中最大堆的自动排序功能。不过这里是数字小的在前面，即先处理出现次数少的字母。这里除了和上面一样检测次数不能大于总长度的一半的操作外，还有一个小 trick，就是构建字符串的时候，是从第二个位置开始的。这里构建的字符串是直接对原字符串S进行修改的，因为 cnt 数组建立了之后，字符串S就没啥用了。用一个变量 idx 来表示当前更新字母的位置，初始化为1，表示要从第二个位置开始更新。因为出现次数最多的字母一定要占据第一个位置才行，这就是留出第一个位置的原因。这里很叼的一点，就是隔位更新，这样能保证相同的字母不相邻，而且当 idx 越界后，拉回到起始位置0，这就有点遍历循环数组的感觉。举个栗子来说吧，比如 “aaabbc”，更新顺序为：

c _

c b

c b _ b

a c b b

a c a b _ b

a c a b a b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    string reorganizeString(string S) {
        int n = S.size(), idx = 1;
        vector<int> cnt(26, 0);
        for (char c : S) cnt[c - 'a'] += 100;
        for (int i = 0; i < 26; ++i) cnt[i] += i;
        sort(cnt.begin(), cnt.end());
        for (int num : cnt) {
            int t = num / 100;
            char ch = 'a' + (num % 100);
            if (t > (n + 1) / 2) return "";
            for (int i = 0; i < t; ++i) {
                if (idx >= n) idx = 0;
                S[idx] = ch;
                idx += 2;
            }
        }
        return S;
    }
};

Leetcode769. Max Chunks To Make Sorted

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].

We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.

Return the largest number of chunks we can make to sort the array.

Example 1:

1
2
3
4
5
Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

1
2
3
4
5
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

题目描述：给出0到arr.length-1之间的一个数组，将这些数组分成一些“块”（分区），并对每个块进行单独的排序，然后将
它们连接后，结果等于排序后的数组，问最多能分多少个分区块

思路：题中有一个点很重要，那就是permutation of [0, 1, …, arr.length - 1]，数组中的元素是0到arr.length-1之间的
所以如果有序的话就是arr[i] == i，那么本身有序的数可以自成一段，而无序的只需要找到最大的那个错序数，作为分段的终点
也就是max 是i 之前中的最大数，如果max == i 那么就保证了前面的数字能够排列成正确的顺序，这就是一个分段，size++，
然后继续向下遍历，找到下一个满足max == i 的地方，就可以又分成一个块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        if(arr.size() == 0)
            return 0;
        vector<int> maxx(arr.size(), 0);
        maxx[0] = arr[0];
        for (int i = 1; i < arr.size(); i ++) {
            maxx[i] = std::max(maxx[i-1], arr[i]);
        }
        int count = 0;
        for (int i = 0; i < arr.size(); i ++) {
            if(i == maxx[i])
                count ++;
        }
        return count;
    }
};

Leetcode773. Sliding Puzzle

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

1
2
3
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.

1
2
3
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
1
2
3
4
5
6
7
8
9
10
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]

由于0的位置只有6个，我们可以列举出所有其下一步可能移动到的位置。为了知道每次移动后拼图是否已经恢复了正确的位置，我们肯定需要用个常量表示出正确位置以作为比较，那么对于这个正确的位置，我们还用二维数组表示吗？也不是不行，但我们可以更加简洁一些，就用一个字符串 “123450”来表示就行了，注意这里我们是把第二行直接拼接到第一行后面的，数字3和4起始并不是相连的。好，下面来看0在不同位置上能去的地方，字符串长度为6，则其坐标为 012345，转回二维数组为：

1
2
0  1  2
3  4  5

那么当0在位置0时，其可以移动到右边和下边，即{1, 3}位置；在位置1时，其可以移动到左边，右边和下边，即{0, 2, 4}位置；在位置2时，其可以移动到左边和下边，即{1, 5}位置；在位置3时，其可以移动到上边和右边，即{0, 4}位置；在位置4时，其可以移动到左边，右边和上边，即{1, 3, 5}位置；在位置5时，其可以移动到上边和左边，即{2, 4}位置。

然后就是标准的BFS的流程了，使用一个HashSet来记录访问过的状态，将初始状态start放入，使用一个queue开始遍历，将初始状态start放入。然后就是按层遍历，取出队首状态，先和target比较，相同就直接返回步数，否则就找出当前状态中0的位置，到dirs中去找下一个能去的位置，赋值一个临时变量cand，去交换0和其下一个位置，生成一个新的状态，如果这个状态不在visited中，则加入visited，并且压入队列queue，步数自增1。如果while循环退出后都没有回到正确状态，则返回-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
class Solution {
public:
    int slidingPuzzle(vector<vector<int>>& board) {
        int n = board.size(), m = board[0].size();
        int res = 0;
        string end = "123450", start = "";
        unordered_set<string> visited;
        queue<string> q;
        vector<vector<int>> dirs{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
                start += to_string(board[i][j]);
        visited.insert(start);
        q.push(start);
        while(!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i ++) {
                string t = q.front(), next;
                q.pop();
                if (t == end)
                    return res;
                int cur = t.find("0");

                for (int j = 0; j < dirs[cur].size(); j ++) {
                    next = t;
                    next[cur] = t[dirs[cur][j]];
                    next[dirs[cur][j]] = t[cur];
                    if (visited.count(next))
                        continue;
                    visited.insert(next);
                    q.push(next);
                }
            } 
            res ++;
        }

        return -1;
    }
};

Leetcode775. Global and Local Inversions

We have some permutation A of [0, 1, …, N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

1
2
3
Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

1
2
3
Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

  • A will be a permutation of [0, 1, …, A.length - 1].
  • A will have length in range [1, 5000].
  • The time limit for this problem has been reduced.

这道题给了一个长度为n的数组，里面是0到n-1数字的任意排序。又定义了两种倒置方法，全局倒置和局部倒置。其中全局倒置说的是坐标小的值大，局部倒置说的是相邻的两个数，坐标小的值大。那么我们可以发现，其实局部倒置是全局倒置的一种特殊情况，即局部倒置一定是全局倒置，而全局倒置不一定是局部倒置，这是解这道题的关键点。题目让我们判断该数组的全局倒置和局部倒置的个数是否相同，那么我们想，什么情况下会不相同？如果所有的倒置都是局部倒置，那么由于局部倒置一定是全局倒置，则二者个数一定相等。如果出现某个全局倒置不是局部倒置的情况，那么二者的个数一定不会相等。所以问题的焦点就变成了是否能找出不是局部倒置的全局倒置。所以为了和局部倒置区别开来，我们不能比较相邻的两个，而是至少要隔一个来比较。我们可以从后往前遍历数组，遍历到第三个数字停止，然后维护一个 [i, n-1] 范围内的最小值，每次和 A[i - 2] 比较，如果小于 A[i - 2]，说明这是个全局的倒置，并且不是局部倒置，那么我们直接返回false即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        int n = A.size(), mn = INT_MAX;
        for (int i = n - 1; i >= 2; --i) {
            mn = min(mn, A[i]);
            if (A[i - 2] > mn) return false;
        }
        return true;
    }
};

Leetcode777. Swap Adjacent in LR String

In a string composed of ‘L’, ‘R’, and ‘X’ characters, like “RXXLRXRXL”, a move consists of either replacing one occurrence of “XL” with “LX”, or replacing one occurrence of “RX” with “XR”. Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.

Example:

1
2
3
4
5
6
7
8
9
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: True
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Note:

  • 1 <= len(start) = len(end) <= 10000.
  • Both start and end will only consist of characters in {‘L’, ‘R’, ‘X’}.

这道题给了我们一个只含有L，R，X三个字符的字符串，然后说有两种操作，一种是把 “XL” 变成 “LX”，另一种是把 “RX” 变成 “XR”。博主刚开始没有读题意，以为二者是可以互换的，错误的认为认为 “LX” 也能变成 “XL”，其实题目这种变换是单向，这种单向关系就是解题的关键，具体来说，就是要把 start 字符串变成 end 字符串的话，L只能往前移动，因为是把 “XL” 变成 “LX”，同样，R只能往后移动，因为是把 “RX” 变成 “XR”。题目给的那个例子并不能很好的说明问题，博主之前那种双向变换的错误认知会跪在这个例子：

1
2
start = "XXRXXLXXXX"
end  = "XXXXRXXLXX"

观察这个 test case，可以发现 start 中的R可以往后移动，没有问题，但是 start 中的L永远无法变到end中L的位置，因为L只能往前移。这道题被归类为 brainteaser，估计就是因为要观察出这个规律吧。那么搞明白这个以后，其实可以用双指针来解题，思路是，每次分别找到 start 和 end 中非X的字符，如果二者不相同的话，直接返回 false，想想问什么？这是因为不论是L还是R，其只能跟X交换位置，L和R之间是不能改变相对顺序的，所以如果分别将 start 和 end 中所有的X去掉后的字符串不相等的话，那么就永远无法让 start 和 end 相等了。这个判断完之后，就来验证L只能前移，R只能后移这个限制条件吧，当i指向 start 中的L时，那么j指向 end 中的L必须要在前面，所以如果i小于j的话，就不对了，同理，当i指向 start 中的R，那么j指向 end 中的R必须在后面，所以i大于j就是错的，最后别忘了i和j同时要自增1，不然死循环了。while 循环退出后，有可能i或j其中一个还未遍历到结尾，而此时剩余到字符中是不能再出现L或R的，否则不能成功匹配，此时用两个 while 循环分别将i或j遍历完成，需要到了L或R直接返回 false 即可，加上了这一步后就不用在开头检测 start 和 end 中L和R的个数是否相同了，参见代码如下：

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 canTransform(string start, string end) {
        int n = start.size(), i = 0, j = 0;
        while (i < n && j < n) {
            while (i < n && start[i] == 'X') ++i;
            while (j < n && end[j] == 'X') ++j;
            if (start[i] != end[j]) return false;
            if ((start[i] == 'L' && i < j) || (start[i] == 'R' && i > j)) return false;
            ++i; ++j;
        }
        while (i < n) {
            if (start[i] != 'X') return false;
            ++i;
        }
        while (j < n) {
            if (end[j] != 'X') return false;
            ++j;
        }
        return true;
    }
};

Leetcode778. Swim in Rising Water

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

1
2
3
4
5
Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

1
2
3
Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:

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

The final route is marked in bold. We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

  • 2 <= N <= 50.
  • grid[i][j] is a permutation of [0, …, N*N - 1].

这道题给了我们一个二维数组，可以看作一个水池，这里不同数字的高度可以看作台阶的高度，只有当水面升高到台阶的高度时，我们才能到达该台阶，起始点在左上角位置，问我们水面最低升到啥高度就可以到达右下角的位置。这是一道蛮有意思的题目。对于这种类似迷宫遍历的题，一般都是DFS或者BFS。而如果有极值问题存在的时候，一般都是优先考虑BFS的，但是这道题比较特别，有一个上升水面的设定，我们可以想象一下，比如洪水爆发了，大坝垮了，那么愤怒汹涌的水流冲了出来，地势低洼处就会被淹没，而地势高的地方，比如山峰啥的，就会绕道而过。这里也是一样，随着水面不断的上升，低于水平面的地方就可以到达，直到水流到了右下角的位置停止。因为水流要向周围低洼处蔓延，所以BFS仍是一个不错的选择，由于水是向低洼处蔓延的，而低洼处的位置又是不定的，所以我们希望每次取出最低位置进行遍历，那么使用最小堆就是一个很好的选择，这样高度低的就会被先处理。在每次取出高度最小的数字时，我们用此高度来更新结果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
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int res = 0, n = grid.size();
        unordered_set<int> visited{0};
        vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.first > b.first;};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp) > q(cmp);
        q.push({grid[0][0], 0});
        while (!q.empty()) {
            int i = q.top().second / n, j = q.top().second % n; q.pop();
            res = max(res, grid[i][j]);
            if (i == n - 1 && j == n - 1) return res;
            for (auto dir : dirs) {
                int x = i + dir[0], y = j + dir[1];
                if (x < 0 || x >= n || y < 0 || y >= n || visited.count(x * n + y)) continue;
                visited.insert(x * n + y);
                q.push({grid[x][y], x * n + y});
            }
        }
        return res;
    }
};

我们也可以使用DP+DFS来做，这里使用一个二维dp数组，其中dp[i][j]表示到达 (i, j) 位置所需要的最低水面高度，均初始化为整型数最大值，我们的递归函数函数需要知道当前的位置 (x, y)，还有当前的水高cur，同时传入grid数组和需要不停更新的dp数组，如果当前位置越界了，或者是当前水高和grid[x][y]中的较大值大于等于dp[x][y]了，直接跳过，因为此时的dp值更小，不需要被更新了。否则dp[x][y]更新为较大值，然后对周围四个位置调用递归函数继续更新dp数组，最终返回右下位置的dp值即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
        helper(grid, 0, 0, grid[0][0], dp);
        return dp[n - 1][n - 1];
    }
    void helper(vector<vector<int>>& grid, int x, int y, int cur, vector<vector<int>>& dp) {
        int n = grid.size();
        if (x < 0 || x >= n || y < 0 || y >= n || max(cur, grid[x][y]) >= dp[x][y]) return;
        dp[x][y] = max(cur, grid[x][y]);
        for (auto dir : dirs) {
            helper(grid, x + dir[0], y + dir[1], dp[x][y], dp);
        }
    }
};

Leetcode779. K-th Symbol in Grammar

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:

1
2
Input: N = 1, K = 1
Output: 0

1
2
Input: N = 2, K = 1
Output: 0

1
2
Input: N = 2, K = 2
Output: 1

1
2
3
4
5
6
7
8
Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001

Note:

  • N will be an integer in the range [1, 30].
  • K will be an integer in the range [1, 2^(N-1)].

这道题说第一行写上了一个0，然后从第二行开始，遇到0，就变为01，遇到1，则变为10，问我们第N行的第K个数字是啥。这是一道蛮有意思的题目，首先如果没啥思路的话，按照给定的方法，一行行generate出来，直到生成第N行，那么第K个数字也就知道了。但是这种brute force的方法无法通过OJ，这里就不多说了，需要想一些更高端的解法。我们想啊，遇到0变为01，那么可不可以把0和1看作上一层0的左右子结点呢，同时，把1和0看作上一层1的左右子结点，这样的话，我们整个结构就可以转为二叉树了，那么前四层的二叉树结构如下所示：

1
2
3
4
5
6
7
              0
       /             \
      0               1
   /     \         /     \
  0       1       1       0
 / \     / \     / \     / \
0   1   1   0   1   0   0   1

我们仔细观察上面这棵二叉树，第四层K=3的那个红色的左子结点，其父结点的位置是第三层的第 (K+1)/2 = 2个红色结点，而第四层K=6的那个蓝色幽子结点，其父节点的位置是第三层的第 K/2 = 3个蓝色结点。那么我们就可以一层一层的往上推，直到到达第一层的那个0。所以我们的思路是根据当前层K的奇偶性来确定上一层中父节点的位置，然后继续往上一层推，直到推倒第一层的0，然后再返回确定路径上每一个位置的值，这天然就是递归的运行机制啊。我们可以根据K的奇偶性知道其是左结点还是右结点，由于K是从1开始的，所以当K是奇数时，其是左结点，当K是偶数时，其是右结点。而且还能观察出来的是，左子结点和其父节点的值相同，右子结点和其父节点值相反，这是因为0换成了01，1换成了10，左子结点保持不变，右子结点flip了一下。想通了这些，那么我们的递归解法就不难写出来了，参见代码如下：

1
2
3
4
5
6
7
8
class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 1) return 0;
        if (K % 2 == 0) return (kthGrammar(N - 1, K / 2) == 0) ? 1 : 0;
        else return (kthGrammar(N - 1, (K + 1) / 2) == 0) ? 0 : 1;
    }
};

我们可以简化下上面的解法，你们可能会说，纳尼？已经三行了还要简化？没错，博主就是这样一个精益求精的人（此处应有掌声👏）。我们知道偶数加1除以2，和其本身除以2的值是相同的，那么其实不论K是奇是偶，其父节点的位置都可以用 (K+1)/2 来表示，问题在于K本身的奇偶决定了其左右结点的位置，从而决定要不要flip父节点的值，这才是上面解法中我们要使用 if…else 结构的原因。实际上我们可以通过‘亦或’操作来实现一行搞定，叼不叼。我们来看下变换规则，0换成了01，1换成了10。

0 -> 01

左子结点(0) = 父节点(0) ^ 0

右子结点(1) = 父节点(0) ^ 1

1 -> 10

左子结点(1) = 父节点(1) ^ 0

右子结点(0) = 父节点(1) ^ 1

那么只要我们知道了父结点的值和当前K的奇偶性就可以知道K的值了，因为左子结点就是父结点值‘亦或’0，右子结点就是父结点值‘亦或’1，由于左子结点的K是奇数，我们可以对其取反再‘与’1，所以就是 (~K & 1)，再‘亦或’上递归函数的返回值即可，参见代码如下：

1
2
3
4
5
6
7
class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 1) return 0;
        return (~K & 1) ^ kthGrammar(N - 1, (K + 1) / 2);
    }
};

Leetcode781. Rabbits in Forest

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

  • answers will have length at most 1000.
  • Each answers[i] will be an integer in the range [0, 999].

这道题说的是大森林中有一堆成了精的兔子，有着不同的颜色，还会回答问题。每个兔子会告诉你森林中还有多少个和其颜色相同的兔子，当然并不是所有的兔子多出现在数组中，所以我们要根据兔子们的回答，来估计森林中最少有多少只能确定的兔子。例子1给的数字是 [1, 1, 2]，第一只兔子说森林里还有另一只兔子跟其颜色一样，第二只兔子也说还有另一只兔子和其颜色一样，那么为了使兔子总数最少，我们可以让前两只兔子是相同的颜色，可以使其回答不会矛盾。第三只兔子说森林里还有两只兔子和其颜色一样，那么这只兔的颜色就不能和前两只兔子的颜色相同了，否则就会跟前面两只兔子的回答矛盾了，因为根据第三只兔子的描述，森林里共有三只这种颜色的兔子，所有总共可以推断出最少有五只兔子。对于例子2，[10, 10, 10] 来说，这三只兔子都说森林里还有10只跟其颜色相同的兔子，那么这三只兔子颜色可以相同，所以总共有11只兔子。

来看一个比较tricky的例子，[0, 0, 1, 1, 1]，前两只兔子都说森林里没有兔子和其颜色相同了，那么这两只兔子就是森林里独一无二的兔子，且颜色并不相同，所以目前已经确定了两只。然后后面三只都说森林里还有一只兔子和其颜色相同，那么这三只兔子就不可能颜色都相同了，但我们可以让两只颜色相同，另外一只颜色不同，那么就是说还有一只兔子并没有在数组中，所以森林中最少有6只兔子。分析完了这几个例子，我们可以发现，如果某个兔子回答的数字是x，那么说明森林里共有x+1个相同颜色的兔子，我们最多允许x+1个兔子同时回答x个，一旦超过了x+1个兔子，那么就得再增加了x+1个新兔子了。所以我们可以使用一个HashMap来建立某种颜色兔子的总个数和在数组中还允许出现的个数之间的映射，然后我们遍历数组中的每个兔子，如果该兔子回答了x个，若该颜色兔子的总个数x+1不在HashMap中，或者映射为0了，我们将这x+1个兔子加入结果res中，然后将其映射值设为x，表示在数组中还允许出现x个也回答x的兔子；否则的话，将映射值自减1即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numRabbits(vector<int>& answers) {
        int res = 0;
        unordered_map<int, int> m;      
        for (int ans : answers) {
            if (!m.count(ans + 1) || m[ans + 1] == 0) {
                res += ans + 1;
                m[ans + 1] = ans;
            } else {
                --m[ans + 1];
            }
        }
        return res;
    }
};

Leetcode783. Minimum Distance Between BST Nodes

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

1
2
3
4
5
6
7
8
9
10
11
12
Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 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
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    void dfs(TreeNode* root, vector<int>& v) {
        if(root == NULL)
            return;
        dfs(root->left, v);
        v.push_back(root->val);
        dfs(root->right, v);
    }
    
    int minDiffInBST(TreeNode* root) {
        vector<int> vec;
        int minn = INT_MAX;
        dfs(root, vec);
        for(int i = 1; i < vec.size(); i ++) {
            minn = min(minn, abs(vec[i] - vec[i-1]));
        }
        return minn;
    }
};

Leetcode784. Letter Case Permutation

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:

1
2
3
4
5
6
7
8
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

每遇上一个字母，就从头把结果容器中已有的字符串全部过一遍，针对当前字母修改大小写，然后存入这个结果容器中。
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:
    
    vector<string> letterCasePermutation(string S) {
        vector<string> result;
        result.push_back(S);
        string c;
        for(int i = 0; i < S.length(); i ++) {
            if (('a' <= S[i]) && (S[i] <= 'z') || ('A' <= S[i]) && (S[i] <= 'Z')) {
                int l = result.size();
				for (int j = 0; j < l; j++) {
                    string tm = result[j];
                    if('a' <= tm[i] && tm[i] <= 'z') {
                        c = (tm[i]-'a'+'A');
                        result.push_back(tm.replace(i, 1, c));
                    }
                    else if('A' <= tm[i] && tm[i] <= 'Z') {
                        c = (tm[i]-'A'+'a');
                        result.push_back(tm.replace(i, 1, c));
                    }
                }
            }
        }
        return result;
    }
};

Leetcode785. Is Graph Bipartite?

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:

1
2
3
4
5
6
7
8
9
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:

1
2
3
4
5
6
7
8
9
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

Note:

  • graph will have length in range [1, 100].
  • graph[i] will contain integers in range [0, graph.length - 1].
  • graph[i] will not contain i or duplicate values.
  • The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

这道题让我们验证给定的图是否是二分图，所谓二分图，就是可以将图中的所有顶点分成两个不相交的集合，使得同一个集合的顶点不相连。为了验证是否有这样的两个不相交的集合存在，我们采用一种很机智的染色法，大体上的思路是要将相连的两个顶点染成不同的颜色，一旦在染的过程中发现有两连的两个顶点已经被染成相同的颜色，说明不是二分图。这里我们使用两种颜色，分别用1和 -1 来表示，初始时每个顶点用0表示未染色，然后遍历每一个顶点，如果该顶点未被访问过，则调用递归函数，如果返回 false，那么说明不是二分图，则直接返回 false。如果循环退出后没有返回 false，则返回 true。在递归函数中，如果当前顶点已经染色，如果该顶点的颜色和将要染的颜色相同，则返回 true，否则返回 false。如果没被染色，则将当前顶点染色，然后再遍历与该顶点相连的所有的顶点，调用递归函数，如果返回 false 了，则当前递归函数的返回 false，循环结束返回 true，参见代码如下：

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 isBipartite(vector<vector<int>>& graph) {
        vector<int> colors(graph.size());
        for (int i = 0; i < graph.size(); ++i) {
            if (colors[i] == 0 && !valid(graph, 1, i, colors)) {
                return false;
            }
        }
        return true;
    }
    bool valid(vector<vector<int>>& graph, int color, int cur, vector<int>& colors) {
        if (colors[cur] != 0) return colors[cur] == color;
        colors[cur] = color;
        for (int i : graph[cur]) {
            if (!valid(graph, -1 * color, i, colors)) {
                return false;
            }
        }
        return true;
    }
};

我们再来看一种迭代的解法，整体思路还是一样的，还是遍历整个顶点，如果未被染色，则先染色为1，然后使用 BFS 进行遍历，将当前顶点放入队列 queue 中，然后 while 循环 queue 不为空，取出队首元素，遍历其所有相邻的顶点，如果相邻顶点未被染色，则染成和当前顶点相反的颜色，然后把相邻顶点加入 queue 中，否则如果当前顶点和相邻顶点颜色相同，直接返回 false，循环退出后返回 true，参见代码如下：

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 isBipartite(vector<vector<int>>& graph) {
        vector<int> colors(graph.size());
        for (int i = 0; i < graph.size(); ++i) {
            if (colors[i] != 0) continue;
            colors[i] = 1;
            queue<int> q{{i}};
            while (!q.empty()) {
                int t = q.front(); q.pop();
                for (auto a : graph[t]) {
                    if (colors[a] == colors[t]) return false;
                    if (colors[a] == 0) {
                        colors[a] = -1 * colors[t];
                        q.push(a);
                    }
                }
            }
        }
        return true;
    }
};

Leetcode787. Cheapest Flights Within K Stops

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:

1
2
3
4
5
6
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:

The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

1
2
3
4
5
6
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:

The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Note:

  • The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n`` - 1.
  • The size of flights will be in range [0, n * (n - 1) / 2].
  • The format of each flight will be (src, dst, price).
  • The price of each flight will be in the range [1, 10000].
  • k is in the range of [0, n - 1].
  • There will not be any duplicated flights or self cycles.

这道题给了我们一些航班信息，包括出发地，目的地，和价格，然后又给了我们起始位置和终止位置，说是最多能转K次机，让我们求出最便宜的航班价格。那么实际上这道题就是一个有序图的遍历问题，博主最先尝试的递归解法由于没有做优化，TLE了，实际上我们可以通过剪枝处理，从而压线过OJ。首先我们要建立这个图，选取的数据结构就是邻接链表的形式，具体来说就是建立每个结点和其所有能到达的结点的集合之间的映射，然后就是用DFS来遍历这个图了，用变量cur表示当前遍历到的结点序号，还是当前剩余的转机次数K，访问过的结点集合visited，当前累计的价格out，已经全局的最便宜价格res。在递归函数中，首先判断如果当前cur为目标结点dst，那么结果res赋值为out，并直接返回。你可能会纳闷为啥不是取二者中较小值更新结果res，而是直接赋值呢？原因是我们之后做了剪枝处理，使得out一定会小于结果res。然后判断如果K小于0，说明超过转机次数了，直接返回。然后就是遍历当前结点cur能到达的所有结点了，对于遍历到的结点，首先判断如果当前结点已经访问过了，直接跳过。或者是当前价格out加上到达这个结点需要的价格之和大于结果res的话，那么直接跳过。这个剪枝能极大的提高效率，是压线过OJ的首要功臣。之后就是标记结点访问，调用递归函数，以及还原结点状态的常规操作了，参见代码如下：

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 findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        int res = INT_MAX;
        unordered_map<int, vector<vector<int>>> m;
        unordered_set<int> visited{{src}};
        for (auto flight : flights) {
            m[flight[0]].push_back({flight[1], flight[2]});
        }
        helper(m, src, dst, K, visited, 0, res);
        return (res == INT_MAX) ? -1 : res;
    }
    void helper(unordered_map<int, vector<vector<int>>>& m, int cur, int dst, int K, unordered_set<int>& visited, int out, int& res) {
        if (cur == dst) {res = out; return;}
        if (K < 0) return;
        for (auto a : m[cur]) {
            if (visited.count(a[0]) || out + a[1] > res) continue;
            visited.insert(a[0]);
            helper(m, a[0], dst, K - 1, visited, out + a[1], res);
            visited.erase(a[0]);
        }
    }
};

下面这种解法是用BFS来做的，还是来遍历图，不过这次是一层一层的遍历，需要使用queue来辅助。前面建立图的数据结构的操作和之前相同，BFS的写法还是经典的写法，但需要注意的是这里也同样的做了剪枝优化，当当前价格加上新到达位置的价格之和大于结果res的话直接跳过。最后注意如果超过了转机次数就直接break，参见代码如下： 

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 findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        int res = INT_MAX, cnt = 0;
        unordered_map<int, vector<vector<int>>> m;
        queue<vector<int>> q{{{src, 0}}};
        for (auto flight : flights) {
            m[flight[0]].push_back({flight[1], flight[2]});
        }
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto t = q.front(); q.pop();
                if (t[0] == dst) res = min(res, t[1]);
                for (auto a : m[t[0]]) {
                    if (t[1] + a[1] > res) continue;
                    q.push({a[0], t[1] + a[1]});
                }
            }
            if (cnt++ > K) break;
        }
        return (res == INT_MAX) ? -1 : res;
    }
};

再来看使用Bellman Ford算法的解法，关于此算法的detail可以上网搜帖子看看。核心思想还是用的动态规划Dynamic Programming，最核心的部分就是松弛操作Relaxation，也就是DP的状态转移方程。这里我们使用一个二维DP数组，其中dp[i][j]表示最多飞i次航班到达j位置时的最少价格，那么dp[0][src]初始化为0，因为飞0次航班的价格都为0，转机K次，其实就是飞K+1次航班，我们开始遍历，i从1到K+1，每次dp[i][src]都初始化为0，因为在起点的价格也为0，然后即使遍历所有的航班x，更新dp[i][x[1]]，表示最多飞i次航班到达航班x的目的地的最低价格，用最多飞i-1次航班，到达航班x的起点的价格加上航班x的价格之和，二者中取较小值更新即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> dp(K + 2, vector<int>(n, 1e9));
        dp[0][src] = 0;
        for (int i = 1; i <= K + 1; ++i) {
            dp[i][src] = 0;
            for (auto x : flights) {
                dp[i][x[1]] = min(dp[i][x[1]], dp[i - 1][x[0]] + x[2]);
            }
        }
        return (dp[K + 1][dst] >= 1e9) ? -1 : dp[K + 1][dst];
    }
};

Leetcode788. Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other (on this case they are rotated in a different direction, in other words 2 or 5 gets mirrored); 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:

1
2
3
4
5
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

输入N,判断数字是否是good数字。旋转180度变成另一个数，2 5 6 9旋转后是good数字。0 1 8旋转后是本身。含有3 4 7的不是good数字。
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 rotatedDigits(int N) {
        int count=0;
        for(int i = 1; i <= N; i ++)
            if(judge(i))
                count ++;
        return count;
    }
    bool judge(int N){
        bool flag = false;
        while(N){
            int k = N % 10;
            if(k == 3 || k == 4 || k == 7){
                flag = false;
                break;
            }
            if(k == 2 || k == 5 || k == 6 || k == 9)
                flag = true;
            N /= 10;
        }
        return flag;
    }
};

Leetcode790. Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

说是有一个2xN大小的棋盘，我们需要用这些多米诺和三格骨牌来将棋盘填满，问有多少种不同的填充方法，结果需要对一个超大数取余。

首先就来设计dp数组，这里我们就用一个一维的dp数组就行了，其中dp[i]表示填满前i列的不同填法总数对超大数10e^9+7取余后的结果。那么DP解法的难点就是求状态转移方程了，没什么太好的思路的时候，就从最简单的情况开始罗列吧。题目中给了N的范围是[1, 1000]，那么我们来看：

当N=1时，那么就是一个2x1大小的棋盘，只能放一个多米诺骨牌，只有一种情况。

当N=2时，那么就是一个2x2大小的棋盘，如下图所示，我们有两种放置方法，可以将两个多米诺骨牌竖着并排放，或者是将其横着并排放。

当N=3时，那么就是一个3x2大小的棋盘，我们共用五种放置方法，如下图所示。仔细观察这五种情况，我们发现其时时跟上面的情况有联系的。前两种情况其实是N=2的两种情况后面加上了一个竖着的多米诺骨牌，第三种情况其实是N=1的那种情况后面加上了两个平行的横向的多米诺骨牌，后两种情况是N=0（空集）再加上两种三格骨牌对角摆开的情况。

当N=4时，那么就是一个4x2大小的棋盘，我们共用十一种放置方法，太多了就不一一画出来了，但是其也是由之前的情况组合而成的。首先是N=3的所有情况后面加上一个竖着多米诺骨牌，然后是N=2的所有情况加上两个平行的横向的多米诺骨牌，然后N=1再加上两种三格骨牌对角摆开的情况，然后N=0（空集）再加上两种三格骨牌和一个横向多米诺骨牌组成的情况。

根据目前的状况，我们可以总结一个很重要的规律，就是dp[n]是由之前的dp值组成的，其中 dp[n-1] 和 dp[n-2] 各自能贡献一种组成方式，而dp[n-3]，一直到dp[0]，都能各自贡献两种组成方式，所以状态转移方程呼之欲出：

1
2
3
4
5
6
7
dp[n] = dp[n-1] + dp[n-2] + 2 * (dp[n-3] + … + dp[0])

        = dp[n-1] + dp[n-3] + dp[n-2] + dp[n-3] + 2 * (dp[n-4] + … dp[0])

        = dp[n-1] + dp[n-3] + dp[n-1]

        = 2 * dp[n-1] + dp[n-3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numTilings(int n) {
        int M = 1e9 + 7;
        vector<long> dp(n+2, 0);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        if (n < 3)
            return dp[n];
        for (int i = 3; i <= n; i ++)
            dp[i] = (2 * dp[i-1] + dp[i-3]) % M;
        return dp[n];
    }
};

Leetcode791. Custom Sort String

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :

1
2
3
4
5
6
7
Input: 
S = "cba"
T = "abcd"
Output: "cbad"
Explanation: 
"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". 
Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

  • S has length at most 26, and no character is repeated in S.
  • T has length at most 200.
  • S and T consist of lowercase letters only.

这道题给了我们两个字符串S和T，让我们将T按照S的顺序进行排序，就是说在S中如果字母x在字母y之前，那么排序后的T中字母x也要在y之前，其他S中未出现的字母位置无所谓。那么我们其实关心的是S中的字母，只要按S中的字母顺序遍历，对于遍历到的每个字母，如果T中有的话，就先排出来，这样等S中的字母遍历完了，再将T中剩下的字母加到后面即可。所以我们先用HashMap统计T中每个字母出现的次数，然后遍历S中的字母，只要T中有，就将该字母重复其出现次数个，加入结果res中，然后将该字母出现次数重置为0。之后再遍历一遍HashMap，将T中其他字母加入结果res中即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string customSortString(string order, string s) {
        map<char, int> m;
        string res;
        for (int i = 0; i < s.length(); i ++)
            m[s[i]] ++;
        for (int i = 0; i < order.length(); i ++) {
            while(m[order[i]] --)
                res += order[i];
        }
        for (auto it = m.begin(); it != m.end(); it ++)
            while(it->second > 0) {
                res += it->first;
                it->second --;
            }
        return res;
    }
};

Leetcode792. Number of Matching Subsequences

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.

Example 1:

1
2
3
Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

1
2
Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

这道题给了我们一个字符串S，又给了一个单词数组，问我们数组有多少个单词是字符串S的子序列。注意这里是子序列，而不是子串，子序列并不需要连续。那么只要我们知道如何验证一个子序列的方法，那么就可以先尝试暴力搜索法，就是对数组中的每个单词都验证一下是否是字符串S的子序列。验证子序列的方法就是用两个指针，对于子序列的每个一个字符，都需要在母字符中找到相同的，在母字符串所有字符串遍历完之后或之前，只要子序列中的每个字符都在母字符串中按顺序找到了，那么就验证成功了。

其实是words数组里有大量相同的单词，而且字符串S巨长无比，那么为了避免相同的单词被不停的重复检验，我们用两个HashSet来记录验证过的单词，为啥要用两个呢？因为验证的结果有两种，要么通过，要么失败，我们要分别存在两个HashSet中，这样再遇到每种情况的单词时，我们就知道要不要结果增1了。如果单词没有验证过的话，那么我们就用双指针的方法进行验证，然后根据结果的不同，存到相应的HashSet中去。

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:
    int numMatchingSubseq(string s, vector<string>& words) {
        int res = 0, len = s.length();
        unordered_set<string> pass, out;
        for (int i = 0; i < words.size(); i ++) {
            if (pass.count(words[i])) {
                res ++;
                continue;
            }
            if (out.count(words[i]))
                continue;
            int j = 0, k = 0;
            for (; j < len && k < words[i].length(); j ++)
                if (s[j] == words[i][k])
                    k ++;
            if (k == words[i].length()) {
                res++;
                pass.insert(words[i]);
            }
            else
                out.insert(words[i]);
        }
        return res;
    }
};

Leetcode794. Valid Tic-Tac-Toe State

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters “ “, “X”, and “O”. The “ “ character represents an empty square.

Here are the rules of Tic-Tac-Toe:

  • Players take turns placing characters into empty squares (“ “).
  • The first player always places “X” characters, while the second player always places “O” characters.
  • “X” and “O” characters are always placed into empty squares, never filled ones.
  • The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty.
  • No more moves can be played if the game is over.

Example 1:

1
2
3
Input: board = ["O  ", "   ", "   "]
Output: false
Explanation: The first player always plays "X".

Example 2:
1
2
3
Input: board = ["XOX", " X ", "   "]
Output: false
Explanation: Players take turns making moves.

Example 3:
1
2
Input: board = ["XXX", "   ", "OOO"]
Output: false

Example 4:
1
2
Input: board = ["XOX", "O O", "XOX"]
Output: true

Note:

  • board is a length-3 array of strings, where each string board[i] has length 3.
  • Each board[i][j] is a character in the set {“ “, “X”, “O”}.

这道题又是关于井字棋游戏的，之前也有一道类似的题 Design Tic-Tac-Toe，不过那道题是模拟游戏进行的，而这道题是让验证当前井字棋的游戏状态是否正确。这题的例子给的比较好，cover 了很多种情况：

情况一：

1
2
3
0 _ _
_ _ _
_ _ _

这是不正确的状态，因为先走的使用X，所以只出现一个O，是不对的。

情况二：

1
2
3
X O X
_ X _
_ _ _

这个也是不正确的，因为两个 player 交替下棋，X最多只能比O多一个，这里多了两个，肯定是不对的。

情况三：

1
2
3
X X X
_ _ _ 
O O O

这个也是不正确的，因为一旦第一个玩家的X连成了三个，那么游戏马上结束了，不会有另外一个O出现。

情况四：

1
2
3
X O X
O _ O
X O X

这个状态没什么问题，是可以出现的状态。

好，那么根据给的这些例子，可以分析一下规律，根据例子1和例子2得出下棋顺序是有规律的，必须是先X后O，不能破坏这个顺序，那么可以使用一个 turns 变量，当是X时，turns 自增1，反之若是O，则 turns 自减1，那么最终 turns 一定是0或者1，其他任何值都是错误的，比如例子1中，turns 就是 -1，例子2中，turns 是2，都是不对的。根据例子3，可以得出结论，只能有一个玩家获胜，可以用两个变量 xwin 和 owin，来记录两个玩家的获胜状态，由于井字棋的制胜规则是横竖斜任意一个方向有三个连续的就算赢，那么分别在各个方向查找3个连续的X，有的话 xwin 赋值为 true，还要查找3个连续的O，有的话 owin 赋值为 true，例子3中 xwin 和 owin 同时为 true 了，是错误的。还有一种情况，例子中没有 cover 到的是：

情况五：

1
2
3
X X X
O O _
O _ _

这里虽然只有 xwin 为 true，但是这种状态还是错误的，因为一旦第三个X放下后，游戏立即结束，不会有第三个O放下，这么检验这种情况呢？这时 turns 变量就非常的重要了，当第三个O放下后，turns 自减1，此时 turns 为0了，而正确的应该是当 xwin 为 true 的时候，第三个O不能放下，那么 turns 不减1，则还是1，这样就可以区分情况五了。当然，可以交换X和O的位置，即当 owin 为 true 时，turns 一定要为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
26
27
28
29
class Solution {
public:
    bool validTicTacToe(vector<string>& board) {
        bool xwin = false, owin = false;
        vector<int> row(3), col(3);
        int diag = 0, antidiag = 0, turns = 0;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 'X') {
                    ++row[i]; ++col[j]; ++turns;
                    if (i == j) ++diag;
                    if (i + j == 2) ++antidiag;
                } else if (board[i][j] == 'O') {
                    --row[i]; --col[j]; --turns;
                    if (i == j) --diag;
                    if (i + j == 2) --antidiag;
                }
            }
        }
        xwin = row[0] == 3 || row[1] == 3 || row[2] == 3 ||
               col[0] == 3 || col[1] == 3 || col[2] == 3 ||
               diag == 3 || antidiag == 3;
        owin = row[0] == -3 || row[1] == -3 || row[2] == -3 ||
               col[0] == -3 || col[1] == -3 || col[2] == -3 ||
               diag == -3 || antidiag == -3;
        if ((xwin && turns == 0) || (owin && turns == 1)) return false;
        return (turns == 0 || turns == 1) && (!xwin || !owin);
    }
};

Leetcode795. Number of Subarrays with Bounded Maximum

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :

1
2
3
4
5
6
Input: 
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Note:

  • L, R and A[i] will be an integer in the range [0, 10^9].
  • The length of A will be in the range of [1, 50000].

这道题给了我们一个数组，又给了我们两个数字L和R，表示一个区间范围，让我们求有多少个这样的子数组，使得其最大值在[L, R]区间的范围内。既然是求子数组的问题，那么最直接，最暴力的方法就是遍历所有的子数组，然后维护一个当前的最大值，只要这个最大值在[L, R]区间的范围内，结果res自增1即可。但是这种最原始，最粗犷的暴力搜索法，OJ不答应。但是其实我们略作优化，就可以通过了。优化的方法是，首先，如果当前数字大于R了，那么其实后面就不用再遍历了，不管当前这个数字是不是最大值，它都已经大于R了，那么最大值可能会更大，所以没有必要再继续遍历下去了。同样的剪枝也要加在内层循环中加，当curMax大于R时，直接break掉内层循环即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int res = 0, n = A.size();
        for (int i = 0; i < n; ++i) {
            if (A[i] > R) continue;
            int curMax = INT_MIN;
            for (int j = i; j < n; ++j) {
                curMax = max(curMax, A[j]);
                if (curMax > R) break;
                if (curMax >= L) ++res;
            }
        }
        return res;
    }
};

虽然上面的方法做了剪枝后能通过OJ，但是我们能不能在线性的时间复杂度内完成呢。答案是肯定的，我们先来看一种官方解答贴中的方法，这种方法是用一个子函数来算出最大值在[-∞, x]范围内的子数组的个数，而这种区间只需要一个循环就够了，为啥呢？我们来看数组[2, 1, 4, 3]的最大值在[-∞, 4]范围内的子数组的个数。当遍历到2时，只有一个子数组[2]，遍历到1时，有三个子数组，[2], [1], [2,1]。当遍历到4时，有六个子数组，[2], [1], [4], [2,1], [1,4], [2,1,4]。当遍历到3时，有十个子数组。其实如果长度为n的数组的最大值在范围[-∞, x]内的话，其所有子数组都是符合题意的，而长度为n的数组共有n(n+1)/2个子数组，刚好是等差数列的求和公式。所以我们在遍历数组的时候，如果当前数组小于等于x，则cur自增1，然后将cur加到结果res中；如果大于x，则cur重置为0。这样我们可以正确求出最大值在[-∞, x]范围内的子数组的个数。而要求最大值在[L, R]范围内的子数组的个数，只需要用最大值在[-∞, R]范围内的子数组的个数，减去最大值在[-∞, L-1]范围内的子数组的个数即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        return count(A, R) - count(A, L - 1);
    }
    int count(vector<int>& A, int bound) {
        int res = 0, cur = 0;
        for (int x : A) {
            cur = (x <= bound) ? cur + 1 : 0;
            res += cur;
        }
        return res;
    }
};

下面这种解法也是线性时间复杂度的，跟上面解法的原理很类似，只不过没有写子函数而已。我们使用left和right来分别标记子数组的左右边界，使得其最大值在范围[L,R]内。那么当遍历到的数字大于等于L时，right赋值为当前位置i，那么每次res加上right - left，随着right的不停自增1，每次加上的right - left，实际上也是一个等差数列，跟上面解法中的子函数本质时一样的。当A[i]大于R的时候，left = i，那么此时A[i]肯定也大于等于L，于是rihgt=i，那么right - left为0，相当于上面的cur重置为0的操作，发现本质联系了吧，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
        int res = 0, left = -1, right = -1;
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] > R) left = i;
            if (A[i] >= L) right = i;
            res += right - left;
        }
        return res;
    }
};

Leetcode796. Rotate String

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = ‘abcde’, then it will be ‘bcdea’ after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1:

1
2
Input: A = 'abcde', B = 'cdeab'
Output: true

Example 2:
1
2
Input: A = 'abcde', B = 'abced'
Output: false

这道题给了我们两个字符串A和B，定义了一种偏移操作，以某一个位置将字符串A分为两截，并将两段调换位置，如果此时跟字符串B相等了，就说明字符串A可以通过偏移得到B。现在就是让我们判断是否存在这种偏移，那么最简单最暴力的方法就是遍历所有能将A分为两截的位置，然后用取子串的方法将A断开，交换顺序，再去跟B比较，如果相等，返回true即可，遍历结束后，返回false，参见代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool rotateString(string A, string B) {
        if (A.size() != B.size()) return false;
        for (int i = 0; i < A.size(); ++i) {
            if (A.substr(i, A.size() - i) + A.substr(0, i) == B) return true;
        }      
        return false;
    }
};

可以在A之后再加上一个A，这样如果新的字符串(A+A)中包含B的话，说明A一定能通过偏移得到B。就比如题目中的例子，A=”abcde”, B=”bcdea”，那么A+A=”abcdeabcde”，里面是包括B的，所以返回true即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool rotateString(string A, string B) {
        if(A=="" && B == "")
            return true;
        if(A.length() != B.length())
            return false;
        string AA = A + A;
        return AA.find(B) < A.length();
    }
};

Leetcode797. All Paths From Source to Target

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:

1
2
3
4
5
6
7
8
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:
The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

这道题给了我们一个无回路有向图，包含N个结点，然后让我们找出所有可能的从结点0到结点N-1的路径。

这个图的数据是通过一个类似邻接链表的二维数组给的，最开始的时候博主没看懂输入数据的意思，其实很简单，我们来看例子中的input，[[1,2], [3], [3], []]，这是一个二维数组，最外层的数组里面有四个小数组，每个小数组其实就是和当前结点相通的邻结点，由于是有向图，所以只能是当前结点到邻结点，反过来不一定行。那么结点0的邻结点就是结点1和2，结点1的邻结点就是结点3，结点2的邻结点也是3，结点3没有邻结点。

那么其实这道题的本质就是遍历邻接链表，由于要列出所有路径情况，那么递归就是不二之选了。我们用cur来表示当前遍历到的结点，初始化为0，然后在递归函数中，先将其加入路径path，如果cur等于N-1了，那么说明到达结点N-1了，将path加入结果res。否则我们再遍历cur的邻接结点，调用递归函数即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        helper(graph, 0, {}, res);
        return res;
    }
    void helper(vector<vector<int>>& graph, int cur, vector<int> path, vector<vector<int>>& res) {
        path.push_back(cur);
        if (cur == graph.size() - 1) res.push_back(path);
        else for (int neigh : graph[cur]) helper(graph, neigh, path, res);
    }
};

Leetcode799. Champagne Tower

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one cup (250ml) of champagne.

Then, some champagne is poured in the first glass at the top. When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it. When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on. (A glass at the bottom row has it’s excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full. After two cups of champagne are poured, the two glasses on the second row are half full. After three cups of champagne are poured, those two cups become full - there are 3 full glasses total now. After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)

Example 1:

1
2
3
Input: poured = 1, query_glass = 1, query_row = 1
Output: 0.0
Explanation: We poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:

1
2
3
Input: poured = 2, query_glass = 1, query_row = 1
Output: 0.5
Explanation: We poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

Note:

  • poured will be in the range of [0, 10 ^ 9].
  • query_glass and query_row will be in the range of [0, 99].

这道题用高脚杯摆了个金字塔，貌似在电影里见过这种酷炫的效果，不过好像还是3D的，组了个立体的酒杯金字塔。这道题中的金字塔是2D的，降低了一些难度。在我们最开始没有什么思路的时候，我们就从最简单的开始分析吧：

当只倒一杯酒的时候，只有最顶端的酒杯被填满。

当倒二杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯各自装了一半。

当倒三杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯也被填满。

当倒四杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯也被填满，第三层的三个酒杯分别被填了四分之一，二分之一，和四分之一。

当倒五杯酒的时候，最顶端的酒杯被填满，且第二层的两个酒杯也被填满，第三层的三个酒杯分别被填了二分之一，填满，和二分之一。

…

如果酒是无限的，那么最终每个酒杯就会被填满，所以难点就是怎么知道在倒K杯酒后，当前的酒杯还剩多少。不管酒量又多大，当前酒杯最多只能装一杯，多余的酒都会流到下一行的两个酒杯。那么比如我们总共倒了五杯酒，那么最顶端的酒杯只能留住一杯，剩下的四杯全部均分到下行的酒杯中了，而离其最近的下一行的两个酒杯会平均分到其多出来的酒量。那么第二层的酒杯分别会得到(5-1)/2=2杯。而第二层的两个酒杯也分别只能留住一杯，各自多余的一杯还要往第三层流，那么第三层的第一个杯子接住了第二层的第一个杯子流下的半杯，而第三层的第二个杯子接住了第二层的两个杯子各自流下的半杯，于是填满了。第三层的第三个杯子接住了第二层的第二个杯子流下的半杯。那么我们的思路应该就是处理每一个杯子，将多余的酒量均分到其下一层对应的两个酒杯中，我们只需要处理到query_row那一行即可，如果地query_glass中的酒量超过一杯了，那么我们返回1就行了，因为多余的还会往下流，但我们不需要再考虑了。

我们建立一个二维的dp数组，其中dp[i][j]表示第i行第j列的杯子将要接住的酒量（可能大于1，因为此时还没有进行多余往下流的处理），那么我们就逐个遍历即可，将多余的酒量均分加入下一行的两个酒杯中即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<vector<double>> dp(101, vector<double>(101, 0));
        dp[0][0] = poured;
        for (int i = 0; i <= query_row; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (dp[i][j] >= 1) {
                    dp[i + 1][j] += (dp[i][j] - 1) / 2.0;
                    dp[i + 1][j + 1] += (dp[i][j] - 1) / 2.0;
                }
            }
        }
        return min(1.0, dp[query_row][query_glass]);
    }
};

我们可以对上面的代码进行空间上的优化，只用一个一维数组即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> dp(101, 0);
        dp[0] = poured;
        for (int i = 1; i <= query_row; ++i) {
            for (int j = i; j >= 0; --j) {
                dp[j + 1] += dp[j] = max(0.0, (dp[j] - 1) / 2.0);
            }
        }
        return min(1.0, dp[query_glass]);
    }
};