Leetcode1103. Distribute Candies to People

We distribute some number of candies, to a row of n = num_people people in the following way:

We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.

Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.

This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).

Return an array (of length num_people and sum candies) that represents the final distribution of candies.

Example 1:

1
2
3
4
5
6
7

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

1
2
3
4
5
6
7

Input: candies = 10, num_people = 3
Output: [5,2,3]
Explanation: 
On the first turn, ans[0] += 1, and the array is [1,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0].
On the third turn, ans[2] += 3, and the array is [1,2,3].
On the fourth turn, ans[0] += 4, and the final array is [5,2,3].

最后要注意的是，如果当前糖果数小于本应该分配的糖果数，则将当前糖果全部给予，也就是要判断剩余糖果数 candies 与本该分配糖果数 i+1 的大小，谁小分配谁

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

class Solution {
	public:
    vector<int> distributeCandies(int candies, int num_people) {
        vector<int> res(num_people, 0);
        int temp = 1, i = 0;
        while(candies > 0) {
            res[i%num_people] += min(candies, i+1);
            candies -= min(candies, i+1);
            i ++;
        }
        return res;
    }
};

Leetcode1104. Path In Zigzag Labelled Binary Tree

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]
Example 2:

Input: label = 26
Output: [1,2,6,10,26]

Constraints:

1 <= label <= 10^6

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

class Solution {
	public:
    vector<int> res;
    vector<int> pathInZigZagTree(int label) {
        build(label);
        return res;
    }
    
    void build(int label){
        int level;
        int lastMin;
        res.insert(res.begin(), label);
        if(label != 1){
            level = (int)(log(label)/log(2));
            lastMin = pow(2, level)/2;
            build( lastMin + (lastMin*2)-1 - label/2 );
        }
    }
};

因为不管是奇数行还是偶数行，该行与上一行的方向都是反着来的

可以先求出顺着来时这个结点对应的父结点，再求出对应父结点在它所在行对称的结点

这里有个求对称的方法：按顺序排列且每个数都能找到对称数的一系列数，每一对对陈数的和都相同，所以求某个数的在某一行的对称数，只用找出这一行两端的数，求出和，再减去这个数就能得到这个数的对称数

所以只用从传进来的这个结点递归，每次递归求出自己对应的父结点，递归到1时结束，每次递归记录一次当前结点的号码

最后得到的一系列结点号码就是路径

Leetcode1105. Filling Bookcase Shelves

You are given an array books where books[i] = [thicknessi, heighti] indicates the thickness and height of the ith book. You are also given an integer shelfWidth.

We want to place these books in order onto bookcase shelves that have a total width shelfWidth.

We choose some of the books to place on this shelf such that the sum of their thickness is less than or equal to shelfWidth, then build another level of the shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.

Note that at each step of the above process, the order of the books we place is the same order as the given sequence of books.

For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.
Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Example 1:

1
2
3
4
5

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
Output: 6
Explanation:
The sum of the heights of the 3 shelves is 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

Example 2:

1
2

Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
Output: 4

这道题说是让用书来填书架，每本书有其固定的宽和高，需要按给定的顺序来排列书，要么排在新的一行，要么排在之前的层，注意每层的宽度不能超过给定的 shelf_width 的限制，每层的高度按照最高的那本书来计算，问怎么安排才能使得整个书架的高度最小。这种数组玩极值的题目，大概率就是贪婪算法或者动态规划 Dynamic Programming，但是这里贪婪算法就不太合适，因为书的高度是不确定的，就算尽量每行尽可能的多放书，并不能保证整体的高度是最小的。所以只能祭出动态规划了，先来定义 DP 数组，这里使用一个一维的 dp 数组，其中dp[i]表示前i本书可以组成的最小高度，大小初始化为n+1。接下来找动态转移方程，对于每一本新的书，最差的结果就是放到新的一行中，这样整个高度就增加了当前书的高度，所以dp[i]可以先赋值为dp[i-1] + height，然后再进行优化。方法是不停加上之前的书，条件是总宽度不能超过给定值，高度选其中最高的一个，每次用dp[j] + height来更新dp[i]，最终返回dp[n]即可，参见代码如下：

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

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int sw) {
        int len = books.size();
        vector<int> dp(len+1, INT_MAX);
        for (int i = 0; i < len; i ++) {
            int h = 0, w = 0;
            for (int j = i; j >= 0; j --) {
                if ((w += books[j][0]) > sw)
                    break;
                h = max(h, books[j][1]);
                dp[i] = min(dp[i], (j == 0 ? 0 : dp[j-1]) + h);
            }
        }
        return dp[len-1];
    }
};

Leetcode1108. Defanging an IP Address

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period “.” with “[.]”.

Example 1:

1
2

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"

Example 2:

1
2

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"

Constraints:

• The given address is a valid IPv4 address.

把IP地址中的“.”换成“[.]”，没有难度。

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

class Solution {
	public:
    string defangIPaddr(string address) {
        string answer(address.length()+6,'\0');
        for(int i=0, j=0;i<address.length();i++){
            if(address[i]=='.'){
                answer[j++]='[';
                answer[j++]='.';
                answer[j++]=']';
            }
            else
				answer[j++]=address[i];
	    }
	return answer;
   }
};

Leetcode1109. Corporate Flight Bookings

There are n flights that are labeled from 1 to n.

You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range.

Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i.

Example 1:

1
2
3
4
5
6
7
8
9

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight labels:        1   2   3   4   5
Booking 1 reserved:  10  10
Booking 2 reserved:      20  20
Booking 3 reserved:      25  25  25  25
Total seats:         10  55  45  25  25
Hence, answer = [10,55,45,25,25]

Example 2:

1
2
3
4
5
6
7
8

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels:        1   2
Booking 1 reserved:  10  10
Booking 2 reserved:      15
Total seats:         10  25
Hence, answer = [10,25]

Constraints:

• 1 <= n <= 2 * 104
• 1 <= bookings.length <= 2 * 104
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 104

这道题说是有n个航班，标号从1到n，每次公司可以连续预定多个航班上的座位，用一个三元数组 [i, j, k]，表示分别预定航班i到j上的k个座位，最后问每个航班上总共被预定了多少个座位。博主先试了一下暴力破解，毫无意外的超时了，想想为啥会超时，因为对于每个预定的区间，都遍历一次的话，最终可能达到n的平方级的复杂度。所以就需要想一些节省运算时间的办法，其实这道的解法很巧妙，先来想想，假如只有一个预定，是所有航班上均订k个座位，那么暴力破解的方法就是从1遍历到n，然后每个都加上k，但还有一种方法，就是只在第一天加上k，然后计算累加和数组，这样之后的每一天都会被加上k。如果是预定前一半的航班，那么暴力破解的方法就是从1遍历到 n/2，而这里的做法是在第一个天加上k，在第 n/2 + 1 天减去k，这样再求累加和数组时，后一半的航班就不会加上k了。对于所有的预定都可以采用这种做法，在起始位置加上k，在结束位置加1处减去k，最后再整体算累加和数组，这样就把平方级的时间复杂度缩小到了线性，完美通过 OJ，参见代码如下：

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

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n);
        for (auto booking : bookings) {
            res[booking[0] - 1] += booking[2];
            if (booking[1] < n) res[booking[1]] -= booking[2];
        }
        for (int i = 1; i < n; ++i) {
            res[i] += res[i - 1];
        }
        return res;
    }
};

Leetcode1110. Delete Nodes And Return Forest

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

1
2

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

Example 2:

1
2

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

Constraints:

• The number of nodes in the given tree is at most 1000.
• Each node has a distinct value between 1 and 1000.
• to_delete.length <= 1000
• to_delete contains distinct values between 1 and 1000.

这道题给了一棵二叉树，说了每个结点值均不相同，现在让删除一些结点，由于删除某些位置的结点会使原来的二叉树断开，从而会形成多棵二叉树，形成一片森林，让返回森林中所有二叉树的根结点。对于二叉树的题，十有八九都是用递归来做的，这道题也不例外，先来想一下这道题的难点在哪里，去掉哪些点会形成新树，显而易见的是，去掉根结点的话，左右子树若存在的话一定会形成新树，同理，去掉子树的根结点，也可能会形成新树，只有去掉叶结点时才不会生成新树，所以当前结点是不是根结点就很重要了，这个需要当作一个参数传入。由于需要知道当前结点是否需要被删掉，每次都遍历 to_delete 数组显然不高效，那就将其放入一个 HashSet 中，从而到达常数级的搜索时间。这样递归函数就需要四个参数，当前结点，是否是根结点的布尔型变量，HashSet，还有结果数组 res。在递归函数中，首先判空，然后判断当前结点值是否在 HashSet，用一个布尔型变量 deleted 来记录。若当前是根结点，且不需要被删除，则将这个结点加入结果 res 中。然后将左子结点赋值为对左子结点调用递归函数的返回值，右子结点同样赋值为对右子结点调用递归的返回值，最后判断当前结点是否被删除了，是的话返回空指针，否则就返回当前指针，这样的话每棵树的根结点都在递归的过程中被存入结果 res 中了，参见代码如下：

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

class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        vector<TreeNode*> res;
        unordered_set<int> st(to_delete.begin(), to_delete.end());
        helper(root, true, st, res);
        return res;
    }
    TreeNode* helper(TreeNode* node, bool is_root, unordered_set<int>& st, vector<TreeNode*>& res) {
        if (!node) return nullptr;
        bool deleted = st.count(node->val);
        if (is_root && !deleted) res.push_back(node);
        node->left = helper(node->left, deleted, st, res);
        node->right = helper(node->right, deleted, st, res);
        return deleted ? nullptr : node;
    }
};

Leetcode1111. Maximum Nesting Depth of Two Valid Parentheses Strings

A string is a valid parentheses string (denoted VPS) if and only if it consists of “(“ and “)” characters only, and:

It is the empty string, or

• It can be written as AB (A concatenated with B), where A and B are VPS’s, or
• It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

• depth(“”) = 0
• depth(A + B) = max(depth(A), depth(B)), where A and B are VPS’s
• depth(“(“ + A + “)”) = 1 + depth(A), where A is a VPS.

For example, “”, “()()”, and “()(()())” are VPS’s (with nesting depths 0, 1, and 2), and “)(“ and “(()” are not VPS’s.

Given a VPS seq, split it into two disjoint subsequences A and B, such that A and B are VPS’s (and A.length + B.length = seq.length).

Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.

Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.

Example 1:

1
2

Input: seq = "(()())"
Output: [0,1,1,1,1,0]

Example 2:

1
2

Input: seq = "()(())()"
Output: [0,0,0,1,1,0,1,1]

Constraints:

• 1 <= seq.size <= 10000

题目很简单，就是将一个集合拆分为两个depth最接近的两个集合。所以我们需要先计算出总的depth(S)是多少，然后将其除2就得到了其中一个集合的depth(A)，然后就可以计算出另外一个集合的depth(B)=depth(S)-depth(A)。

接着考虑如何将两个集合挑选出来，也是非常容易的，我们只需要再次遍历seq，记录遍历的’(‘的数目，如果’(‘的数目超过了As（A集合的depth）的话，我们就将对应的字符标记为B集合的即可（也就是标记为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 Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int ds=0,cur=0;
        for(int i=0;i<seq.length();i++){
            if(seq[i]=='('){
                cur+=1;
                ds=max(ds,cur);
            }
            else
                cur-=1;
        }
        int as=ds/2;
        vector<int> res(seq.length(),0);
        for(int i=0;i<seq.length();i++){
            if(seq[i]=='('){
                cur+=1;
                if(cur>as)
                    res[i]=1;
            }
            else{
                if(cur>as)
                    res[i]=1;
                cur-=1;
            }
        }
        return res;
    }
};

Leetcode1114. Print in Order

Suppose we have a class:

1
2
3
4
5

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Example 1:

1
2
3

Input: [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

1
2
3

Input: [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

现在三个线程，每个线程分别调用三个函数中的一个。无论线程的产生和调用关系怎么样，最终输出的结果要求都是”firstsecondthird”。如何设计是三个函数。这个是Leetcode的新题型，也就是说并发类型，我觉得很实用，工作中能用到。一般情况下，最简单的协调不同线程之间的调度关系，都可以使用mutex来做，本质是信号量。

std::mutex的成员函数有四个：

• 构造函数，std::mutex不允许拷贝构造，也不允许 move 拷贝，最初产生的 mutex 对象是处于 unlocked 状态的。
• lock()，调用线程将锁住该互斥量。线程调用该函数会发生下面 3 种情况：
  • (1). 如果该互斥量当前没有被锁住，则调用线程将该互斥量锁住，直到调用 unlock之前，该线程一直拥有该锁。
  • (2). 如果当前互斥量被其他线程锁住，则当前的调用线程被阻塞住。
  • (3). 如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)。
• unlock()， 解锁，释放对互斥量的所有权。
• try_lock()，尝试锁住互斥量，如果互斥量被其他线程占有，则当前线程也不会被阻塞。线程调用该函数也会出现下面 3 种情况，
  • (1). 如果当前互斥量没有被其他线程占有，则该线程锁住互斥量，直到该线程调用 unlock 释放互斥量。
  • (2). 如果当前互斥量被其他线程锁住，则当前调用线程返回 false，而并不会被阻塞掉。
  • (3). 如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)。

也就是说一个锁能控制两个线程的执行顺序。这个题中我们需要保持三个函数是按顺序执行的，则需要两个锁m1和m2。在开始的时候，两个锁都锁起来。first()可以直接执行，second()等待m1释放之后执行，third()等待m2释放之后执行。first()结束之后释放m1，second()结束之后释放m2.因此三个的顺序都协调一致了。C++代码如下：

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

class Foo {
	private:
    mutex m1, m2;
	public:
    Foo() {
	        m1.lock();
	        m2.lock();
	    }

    void first(function<void()> printFirst) {
	        // printFirst() outputs "first". Do not change or remove this line.
	        printFirst();
	        m1.unlock();
	    }

    void second(function<void()> printSecond) {
	        m1.lock();
	        // printSecond() outputs "second". Do not change or remove this line.
	        printSecond();
	        m1.unlock();
	        m2.unlock();
	    }

    
    void third(function<void()> printThird) {
	        m2.lock();
	        // printThird() outputs "third". Do not change or remove this line.
	        printThird();
	        m2.unlock();
	    }
};

Leetcode1122. Relative Sort Array

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don’t appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:

1
2

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19] 

Constraints:

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• Each arr2[i] is distinct.
• Each arr2[i] is in arr1.

arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中，对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

基本思路是：

1. 首先题目的意思是按照arr2的元素顺序返回arr1的元素，假定返回的新数组为arr3，然后把剩余的arr1元素按照升序顺序拼接到arr3后边返回
2. 遍历一遍arr1使用map [Int:Int] 记录每一个元素的次数
3. 遍历arr2，把在arr2出现的元素当做key取出value值，arr3 add value次key值
4. 把剩余的字典键值对所对应的key值排序，添加到arr3后边
5. 时间复杂度 O(nlogn)
6. 空间复杂度 O(n)

注意map是有序的，内部是用平衡树存储，而unordered_map是用hash做的，也不能保证插入的顺序，因此这里使用了大佬的做法

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<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int count_arr[1001];
        vector<int> ans;
        memset(count_arr, 0, sizeof(count_arr));
        for(int i=0;i<arr1.size();i++)
            count_arr[arr1[i]]++;
        
        for(int i=0;i<arr2.size();i++){
            int len = count_arr[arr2[i]];
            for(int j=0;j<len;j++)
                ans.push_back(arr2[i]);
            count_arr[arr2[i]]=-1;
        }
        vector<int> s;
        for(int i=0; i<arr1.size(); i++){
            if(count_arr[arr1[i]] > 0) s.push_back(arr1[i]);
        }        
        sort(s.begin(), s.end());
        for(int i=0;i<s.size();i++)
            ans.push_back(s[i]);
        return ans;
    }
};

Leetcode1123. Lowest Common Ancestor of Deepest Leaves

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children
• The depth of the root of the tree is 0, and if the depth of a node is d, the depth of each of its children is d+1.
• The lowest common ancestor of a set S of nodes is the node A with the largest depth such that every node in S is in the subtree with root A.

Example 1:

1
2
3
4
5
6

Input: root = [1,2,3]
Output: [1,2,3]
Explanation: 
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".

Example 2:

1
2

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

Example 3:

1
2

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

Constraints:

• The given tree will have between 1 and 1000 nodes.
• Each node of the tree will have a distinct value between 1 and 1000.

写一个递归函数，返回(LCA, 最大深度)，然后对左右子树分别调用这个函数。如果两棵子树的高度不同，则显然最大深度的叶子只存在更深的子树中，那么另一棵子树就不用管了，LCA也不变；否则LCA是当前树根。

就是，他不是要求最大深度公共子树么，就求左右子树的深度，如果相等了，说明找到了，因为是从上往下的，这就是最大的深度；否则的话对左右子树分别搞一搞。

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 solve(TreeNode* root){
        if(root == NULL)
            return 0;
        return 1 + max(solve(root->left), solve(root->right));
        
    }
    
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        if(root==NULL)
            return 0;
        int l = solve(root->left);
        int r = solve(root->right);
        if(l == r)
            return root;
        if(l < r)
            return lcaDeepestLeaves(root->right);
        else
            return lcaDeepestLeaves(root->left);
    }
};

Leetcode1124. Longest Well-Performing Interval

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

1
2
3

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Constraints:

• 1 <= hours.length <= 10000
• 0 <= hours[i] <= 16

把所有大于8的转成1，小于8的转成-1，找到最长的字串，字串的和大于等于1，最优解的字串的和肯定是1，因为如果大于1的话肯定可以往后走。

存储可能的target_sum的序列。

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 longestWPI(vector<int>& hours) {
        for(int i=0;i<hours.size();i++)
            hours[i]=hours[i]>8?1:-1;
        unordered_map<int, int> idx;
        int r = 0,inx=0;
        int last=0;
        int maxx=0;
        for(int i=0;i<hours.size();i++){
            r += hours[i];
            if(r>0){
                maxx = i+1;
            }
            if (!idx.count(r)) 
                idx[r] = i;
            if (idx.count(r - 1))
                maxx = max(maxx, i - idx[r - 1]);
        }
        return maxx;
    }
};

LeetCode] 1125. Smallest Sufficient Team

In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.

For example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].
Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.

It is guaranteed an answer exists.

Example 1:

1
2

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

Example 2:

1
2

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

Constraints:

• 1 <= req_skills.length <= 16
• 1 <= req_skills[i].length <= 16
• req_skills[i] consists of lowercase English letters.
• All the strings of req_skills are unique.
• 1 <= people.length <= 60
• 0 <= people[i].length <= 16
• 1 <= people[i][j].length <= 16
• people[i][j] consists of lowercase English letters.
• All the strings of people[i] are unique.
• Every skill in people[i] is a skill in req_skills.
• It is guaranteed a sufficient team exists.

这道题给了一个技能数组，是完成某一个项目所需要的必备技能。又给了一个候选人的数组，每个人都有不同的技能，现在问最少需要多少人可以完成这个项目。由于每个人的技能点不同，为了能完成这个项目，所选的人的技能点的并集要正好包含所有的项目必备技能，而且还要求人数尽可能的少，这就是一道典型的动态规划 Dynamic Programming 的题。这道题敢标 Hard 是有其一定的道理的，首先 DP 数组的定义就是一个难点，因为我们也不知道最少需要多少个人可以拥有所有的必备技能。另一个难点是如何表示这些技能，总不能每次都跟 req_skills 数组一一对比吧，太不高效了。一个比较好的方法是使用二进制来表示，有多少个技能就对应多少位，某人拥有某技能，则对应位上为1，否则为0。若总共有n个必备技能，实际上只用一个 2^n-1 的数字就可以表示了。这里我们的 dp 数组定义为 HashMap，建立技能集合的位表示数和拥有这些技能的人（最少的人数）的集合之间的映射，那么最终的结果就是 dp[(1<<n)-1] 对应的数组的长度了。首先将 dp[0] 映射为空数组，因为0表示没有任何技能，自然也不需要任何人，这个初始化是一定要做的，之后会讲原因。这里再用另一个 HashMap，将每个技能映射到其在技能数组中的坐标，这样方便之后快速的翻转技能集合二进制的对应位。先用一个 for 循环来建立这个 skillMap 的映射，然后就是遍历每个候选人了，使用一个整型变量 skill，然后根据 skillMap 查找这个人所有的技能，并将其对应位翻为1，这样此时的 skill 就 encode 了该人的所有的技能。现在就该尝试更新 dp 了，遍历此时 dp 的所有映射，此时之前加入的那个初始化的映射就发挥作用了，就像很多其他 DP 的题都要给 dp[0] 初始化一样，没有这个引子，后面的更新都不会发生，整个 for 都进不去。将当前的 key 值或上 skill，则表示将当前这个人加到了某个映射的人的集合中了，这样就可能会生出现一个新的技能集合的位表示数（也可能不出现，即当前这个人的所有技能已经被之前集合中的所有人包括了），此时看若 dp 中不存在这个技能集合的位表示数，或者新的技能集合的位表示数对应的人的集合长度大于原来的人的集合长度加1，说明 dp 需要被更新了，将新的位表示数映射到加入这个人后的新的人的集合，这样更新下来，就能保证最终 dp[(1<<n)-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

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int n = req_skills.size();
        unordered_map<int, vector<int>> dp(1 << n);
        dp[0] = {};
        unordered_map<string, int> skillMap;
        for (int i = 0; i < n; ++i) {
            skillMap[req_skills[i]] = i;
        }
        for (int i = 0; i < people.size(); ++i) {
            int skill = 0;
            for (string str : people[i]) {
                skill |= 1 << skillMap[str];
            }
            for (auto a : dp) {
                int cur = a.first | skill;
                if (!dp.count(cur) || dp[cur].size() > 1 + dp[a.first].size()) {
                    dp[cur] = a.second;
                    dp[cur].push_back(i);
                }
            }
        }
        return dp[(1 << n) - 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

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int m = req_skills.size(), n = people.size();
        int maxstate = 1 << m;
        // f[i][s] = 考虑前i个人的时候，状态为s所需的最小人数
        vector<vector<int>> f(n+1, vector<int>(maxstate, 1e9));
        // path[i][s] = 前i个人的时候，选人方案，
        vector<vector<long long>> path(n+1, vector<long long>(maxstate, 0));
        
        f[0][0] = 0;
        
        for (int i = 1; i <= n; i ++) {
            int state = 0;
            for (const auto& str : people[i-1]) {
                int id = find(req_skills.begin(), req_skills.end(), str) - req_skills.begin();
                state |= (1 << id);
            }
            
            for (int j = 0; j < maxstate; j ++) {
                if (f[i-1][j] < f[i][j]) {
                    f[i][j] = f[i-1][j];
                    path[i][j] = path[i-1][j];
                }
                
                int news = j | state;
                if (f[i-1][j] + 1 < f[i][news]) {
                    f[i][news] = f[i-1][j] + 1;
                    path[i][news] = path[i-1][j] | (1LL << i);
                }
            }
        }
        
        vector<int> ret;
        for (int i = 1; i <= n; i ++)
            if ((path[n][maxstate-1] >> i) & 1)
                ret.push_back(i-1);
        return ret;
    }
};

Leetcode1128. Number of Equivalent Domino Pairs

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==d and b==c) - that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Example 1:

1
2

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

给你一个由一些多米诺骨牌组成的列表 dominoes。如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d]，等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

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 numEquivDominoPairs(vector<vector<int>>& dominoes) {
        int temp;
        int ans = 0;
        map<int, int> mp;

        for(int i = 0; i < dominoes.size(); i ++) {
            if(dominoes[i][0] > dominoes[i][1]) {
                temp = dominoes[i][0];
                dominoes[i][0] = dominoes[i][1];
                dominoes[i][1] = temp;
            }
            temp = dominoes[i][0]*10 + dominoes[i][1];
            mp[temp] ++;
        }
        for(pair<int, int> i : mp) {
            int v = i.second;
            ans += (v*(v-1))/2;
        }
        return ans;
    }
};

Leetcode1129. Shortest Path with Alternating Colors

Consider a directed graph, with nodes labelled 0, 1, …, n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn’t exist).

Example 1:

1
2

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

1
2

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

1
2

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

1
2

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

1
2

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

• 1 <= n <= 100
• red_edges.length <= 400
• blue_edges.length <= 400
• red_edges[i].length == blue_edges[i].length == 2
• 0 <= red_edges[i][j], blue_edges[i][j] < n

这道题给了一个有向图，跟以往不同的是，这里的边分为两种不同颜色，红和蓝，现在让求从结点0到所有其他结点的最短距离，并且要求路径必须是红蓝交替，即不能有相同颜色的两条边相连。这种遍历图求最短路径的题目的首选解法应该是广度优先遍历 Breadth-first Search，就像迷宫遍历的问题一样，由于其遍历的机制，当其第一次到达某个结点时，当前的步数一定是最少的。不过这道题还有一个难点，就是如何保证路径是红蓝交替的，这就跟以往有些不同了，必须要建立两个图的结构，分别保存红边和蓝边，为了方便起见，使用一个二维数组，最外层用0表示红边，1表示蓝边。内层是一个大小为n的数组，因为有n个结点，数组中的元素是一个 HashSet，因为每个结点可能可以连到多个其他的结点，这个图的结构可以说是相当的复杂了。

接下来就是给图结构赋值了，分别遍历红边和蓝边的数组，将对应的结点连上，就是将相连的结点加到 HashSet 中。由于到达每个结点可能通过红边或者蓝边，所以就有两个状态，这里用一个二维的 dp 数组来记录这些状态，其中 dp[i][j] 表示最后由颜色i的边到达结点j的最小距离，除了结点0之外，均初始化为 2n，因为即便是有向图，到达某个结点的最小距离也不可能大于 2n。由于是 BFS 遍历，需要用到 queue，这里的 queue 中的元素需要包含两个信息，当前的结点值，到达该点的边的颜色，所以初始化时分别将 (0,0) 和 (0,1) 放进去，前一个0表示结点值，后一个表示到达该点的边的颜色。接下来就可以进行 BFS 遍历了，进行 while 循环，将队首元素取出，将结点值 cur 和颜色值 color 取出。由于到达当前结点的边的颜色是 color，接下来就只能选另一种颜色了，则可以用 1-color 来选另一种颜色，并且在该颜色下遍历和 cur 相连的所有结点，若其对应的 dp 值仍为 2n，说明是第一次到达该结点，可用当前 dp 值加1来更新其 dp 值，并且将新的结点值与其颜色加入到队列中以便下次遍历其相连结点。当循环结束之后，只需要遍历一次 dp 值，将每个结点值对应的两个 dp 值中的较小的那个放到结果 res 中即可，注意要进行一下判断，若 dp 值仍为 2n，说明无法到达该结点，需要换成 -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:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        vector<int> res(n);
        vector<vector<int>> dp(2, vector<int>(n));
        vector<vector<unordered_set<int>>> graph(2, vector<unordered_set<int>>(n));
        for (auto &edge : red_edges) {
            graph[0][edge[0]].insert(edge[1]);
        }
        for (auto &edge : blue_edges) {
            graph[1][edge[0]].insert(edge[1]);
        }
        for (int i = 1; i < n; ++i) {
            dp[0][i] = 2 * n;
            dp[1][i] = 2 * n;
        }
        queue<vector<int>> q;
        q.push({0, 0});
        q.push({0, 1});
        while (!q.empty()) {
            int cur = q.front()[0], color = q.front()[1]; q.pop();
            for (int next : graph[1 - color][cur]) {
                if (dp[1 - color][next] == 2 * n) {
                    dp[1 - color][next] = 1 + dp[color][cur];
                    q.push({next, 1 - color});
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            int val = min(dp[0][i], dp[1][i]);
            res[i] = val == 2 * n ? -1 : val;
        }
        return res;
    }
};

Leetcode1130. Minimum Cost Tree From Leaf Values

Given an array arr of positive integers, consider all binary trees such that:

• Each node has either 0 or 2 children;
• The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
• The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

Example 1:

1
2
3
4
5
6
7
8
9
10

Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /\
  12   4        6    8
 /  \               /\
6    2             2   4

Constraints:

• 2 <= arr.length <= 40
• 1 <= arr[i] <= 15
• It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

这道题给了一个数组，说是里面都是一棵树的叶结点，说是其组成的树是一棵满二叉树，且这些叶结点值是通过中序遍历得到的，树中的非叶结点值是是其左右子树中最大的两个叶结点值的乘积，满足这些条件的二叉树可能不止一个，现在让找出非叶结点值之和最小的那棵树，并返回这个最小值。

通过观察例子，可以发现叶结点值 6，2，4 的顺序是不能变的，但是其组合方式可能很多，若有很多个叶结点，那么其组合方式就非常的多了。题目中给的提示是用动态规划 Dynamic Programming 来做，用一个二维的 dp 数组，其中 dp[i][j] 表示在区间 [i, j] 内的子数组组成的二叉树得到非叶结点值之和的最小值，接下来想状态转移方程怎么写。首先，若只有一个叶结点的话，是没法形成非叶结点的，所以 dp[i][i] 是0，最少得有两个叶结点，才有非0的值，即dp[i][i+1] = arr[i] * arr[i+1]，而一旦区间再大一些，就要遍历其中所有的小区间的情况，用其中的最小值来更新大区间的 dp 值。

这种用区间dp做，第一层循环是区间长度，第二层枚举起点，第三层枚举终点。这里的区间长度从1到n，长度为1，表示至少有两个叶结点，i从0遍历到 n-len，j可以直接确定出来为 i+len，然后用k来将区间 [i, j] 分为两个部分，由于分开的小区间在之前都已经更新过了，所以其 dp 值可以直接得到，然后再加上这两个区间中各自的最大结点值的乘积。为了不每次都遍历小区间来获得最大值，可以提前计算好任意区间的最大值，保存在 maxVec 中，这样就可以快速获取了，最后返回的结果保存在 dp[0][n-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

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(n));
        vector<vector<int>> maxVec(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            int curMax = 0;
            for (int j = i; j < n; ++j) {
                curMax = max(curMax, arr[j]);
                maxVec[i][j] = curMax;
            }
        }
        for (int len = 1; len < n; ++len) {
            for (int i = 0; i + len < n; ++i) {
                int j = i + len;
                dp[i][j] = INT_MAX;
                for (int k = i; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxVec[i][k] * maxVec[k + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

下面的这种解法是参见了大神 lee215 的帖子，是一种利用单调栈来解的方法，将时间复杂度优化到了线性，惊为天人。思路是这样的，当两个叶结点生成一个父结点值，较小的那个数字使用过一次之后就不再被使用了，因为之后形成的结点是要子树中最大的那个结点值。所以问题实际上可以转化为在一个数组中，每次选择两个相邻的数字a和b，移除较小的那个数字，代价是 a*b，问当移除到数组只剩下一个数字的最小的代价。Exactly same problem，所以b是有可能复用的，要尽可能的 minimize，数字a可以是一个局部最小值，那么b就是a两边的那个较小的数字，这里使用一个单调栈来做是比较方便的。关于单调栈，博主之前也有写过一篇总结 LeetCode Monotonous Stack Summary 单调栈小结，在 LeetCode 中的应用也非常多，是一种必须要掌握的方法。这里维护一个最小栈，当前栈顶的元素是最小的，一旦遍历到一个较大的数字，此时当前栈顶的元素其实是一个局部最小值，它就需要跟旁边的一个较小的值组成一个左右叶结点，这样形成的父结点才是最小的，然后将较小的那个数字移除，符合上面的分析。然后继续比较新的栈顶元素，若还是小，则继续相同的操作，否则退出循环，将当前的数字压入栈中。最后若栈中还有数字剩余，则一定是从大到小的，只需将其按顺序两两相乘即可，参见代码如下：

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

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int res = 0, n = arr.size();
        vector<int> st{INT_MAX};
        for (int num : arr) {
            while (!st.empty() && st.back() <= num) {
                int mid = st.back();
                st.pop_back();
                res += mid * min(st.back(), num);
            }
            st.push_back(num);
        }
        for (int i = 2; i < st.size(); ++i) {
            res += st[i] * st[i - 1];
        }
        return res;
    }
};

Leetcode1137. N-th Tribonacci Number

The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given n, return the value of Tn.

Example 1:

1
2
3
4
5

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

1
2

Input: n = 25
Output: 1389537

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

class Solution {
	public:
    int tribonacci(int n) {
        vector<int> v(n+1, 0);
        v[0] = 0;
        v[1] = 1;
        v[2] = 1;
        if(n < 3)
            return v[n];
        for(int i = 3; i <= n; i ++) {
            v[i] = v[i-1] + v[i-2] + v[i-3];
        }
        return v[n];
    }
};

Leetcode1138. Alphabet Board Path

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”], as shown in the diagram below.

We may make the following moves:

• ‘U’ moves our position up one row, if the position exists on the board;
• ‘D’ moves our position down one row, if the position exists on the board;
• ‘L’ moves our position left one column, if the position exists on the board;
• ‘R’ moves our position right one column, if the position exists on the board;
• ‘!’ adds the character board[r][c] at our current position (r, c) to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to target in the minimum number of moves. You may return any path that does so.

Example 1:

1
2

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

1
2

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

• 1 <= target.length <= 100
• target consists only of English lowercase letters.

这道题给了一个字母表盘，就是 26 个小写字母按每行五个排列，形成一个二维数组，共有六行，但第六行只有一个字母z。然后给了一个字符串 target，起始位置是在a，现在让分别按顺序走到 target 上的所有字符，问经过的最短路径是什么。

由于表盘上的字母位置是固定的，所以不需要进行遍历来找特定的字母，而是可以根据字母直接确定其在表盘的上的坐标，这样当前字母和目标字母的坐标都确定了，就可以直接找路径了，其实就是个曼哈顿距离。由于路径有很多条，只要保证距离最短都对，那么就可以先走横坐标，或先走纵坐标。其实这里选方向挺重要，因为有个很 tricky 的情况，就是字母z，因为最后一行只有一个字母z，其不能往右走，只能往上走，所以这里定一个规则，就是先往上走，再向右走。同理，从别的字母到z的话，也应该先往左走到头，再往下走。顺序确定好了，就可以想怎么正确的生成路径，往上的走的话，说明目标点在上方，则说明当前的x坐标大，则用 curX - x，由于不一定需要向上走，所以这个差值有可能是负数，则需要跟0比较大小，取较大的那个。其他情况，都是同理的，往右走用目标y坐标减去当前y坐标；往左走，用当前y坐标减去目标y坐标；往下走，用目标x坐标减去当前x坐标，最后再加上感叹号。结束一轮后，别忘了更新 curX 和 curY，参见代码如下：

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

class Solution {
public:
    string alphabetBoardPath(string target) {
        string res;
        int curX = 0, curY = 0;
        for (char c : target) {
            int x = (c - 'a') / 5, y = (c - 'a') % 5;
            res += string(max(0, curX - x), 'U') + string(max(0, y - curY), 'R') + string(max(0, curY - y), 'L') + string(max(0, x - curX), 'D') + '!';
            curX = x;
            curY = y;
        }
        return res;
    }
};

Leetcode1139. Largest 1-Bordered Square

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn’t exist in the grid.

Example 1:

1
2

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

1
2

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 1

这道题给了一个只有0和1的二维数组 grid，现在让找出边长均为1的最大正方形的元素个数，实际上就是这个正方形的面积，也就是边长的平方。给定的 grid 不一定是个正方形，首先来想，如何确定一个正方形，由于边长的是相同的，只要知道了边长，和其中的一个顶点，那么这个正方形也就确定了。如何才能快速的知道其边长是否均为1呢，每次都一个一个的遍历检查的确太不高效了，比较好的方法是统计连续1的个数，注意这里不是累加和数组，而且到当前位置为止的连续1的个数，需要分为两个方向，水平和竖直。这里用left表示水平，top表示竖直。若left[i][j]为k，则表示从grid[i][j-k]到grid[i][j]的数字均为1，同理，若top[i][j]为k，则表示grid[i-k][j]到grid[i][j]的数字均为1，则表示找到了一个边长为k的正方形。由于grid不一定是正方形，那么其可以包含的最大的正方形的边长为grid的长和宽中的较小值。边长确定了，只要遍历左上顶点的就行了，然后通过连续1数组top和left来快速判断四条边是否为1，只要找到了这个正方形，就可以直接返回了，否则就将边长减少1，继续查找，参见代码如下：

解法一：

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

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> left(m, vector<int>(n)), top(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) continue;
                left[i][j] = j == 0 ? 1 : left[i][j - 1] + 1;
                top[i][j] = i == 0 ? 1 : top[i - 1][j] + 1;
            }
        }
        for (int len = min(m, n); len > 0; --len) {
            for (int i = 0; i < m - len + 1; ++i) {
                for (int j = 0; j < n - len + 1; ++j) {
                    if (top[i + len - 1][j] >= len && top[i + len - 1][j + len - 1] >= len && left[i][j + len - 1] >= len && left[i + len - 1][j + len - 1] >= len) return len * len;
                }
            }
        }
        return 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

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int mx = 0, m = grid.size(), n = grid[0].size();
        vector<vector<int>> left(m, vector<int>(n)), top(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) continue;
                left[i][j] = j == 0 ? 1 : left[i][j - 1] + 1;
                top[i][j] = i == 0 ? 1 : top[i - 1][j] + 1;
            }
        }
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int small = min(left[i][j], top[i][j]);
                while (small > mx) {
                    if (top[i][j - small + 1] >= small && left[i - small + 1][j] >= small) mx = small;
                    --small;
                }
            }
        }
        return mx * mx;
    }
};

Leetcode1140. Stone Game II

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

Example 1:

1
2
3

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Example 2:

1
2

Input: piles = [1,2,3,4,5,100]
Output: 104

Constraints:

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 104

这道题是石头游戏系列的第二道，跟之前那道 Stone Game 不同的是终于换回了 Alice 和 Bob！还有就是取石子的方法，不再是只能取首尾两端的石子堆，而是可以取 [1, 2M] 范围内的任意X堆，M是个变化的量，初始化为1，每次取完X堆后，更新为 M = max(M, X)。这种取石子的方法比之前的要复杂很多，由于X的值非常的多，而且其不同的选择还可能影响到M值，那么整体的情况就特别的多，暴力搜索基本上是行不通的。这种不同状态之间转移的问题用动态规划 Dynamic Programming 是比较合适的，首先来考虑 DP 数组的定义，题目要求的是 Alice 最多能拿到的石子个数，拿石子的方式是按顺序的，不能跳着拿，所以决定某个状态的是两个变量，一个是当前还剩多少石子堆，可以通过当前位置坐标i来表示，另一个是当前的m值，只有知道了当前的m值，那么选手才知道能拿的堆数的范围，所以 DP 就是个二维数组，其 dp[i][m] 表示的意义在上面已经解释了。接下来考虑状态转移方程，由于在某个状态时已经知道了m值，则当前选手能拿的堆数在范围 [1, 2m] 之间，为了更新这个 dp 值，所有x的情况都要遍历一遍，即在剩余堆数中拿x堆，但此时x堆必须小于等于剩余的堆数，即 i + x <= n，i为当前的位置。由于每个选手都是默认选最优解的，若能知道下一个选手该拿的最大石子个数，就能知道当前选手能拿的最大石子个数了，因为二者之和为当前剩余的石子个数。由于当前选手拿了x堆，则下个选手的位置是 i+x，且m更新为 max(m,x)，所以其 dp 值为 dp[i + x][max(m, x)])。为了快速得知当前剩余的石子总数，需要建立累加和数组，注意这里是建立反向的累加和数组，其中 sums[i] 表示范围 [i, n-1] 之和。分析到这里就可以写出状态状态转移方程如下：

1

dp[i][m] = max(dp[i][m], sums[i] - dp[i + x][max(m, x)])

解法一：

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 stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> sums = piles;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int i = n - 2; i >= 0; --i) {
            sums[i] += sums[i + 1];
        }
        for (int i = 0; i < n; ++i) {
            dp[i][n] = sums[i];
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int m = n - 1; m >= 1; --m) {
                for (int x = 1; x <= 2 * m && i + x <= n; ++x) {
                    dp[i][m] = max(dp[i][m], sums[i] - dp[i + x][max(m, x)]);
                }
            }
        }
        return dp[0][1];
    }
};

解法二：

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

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> sums = piles;
        vector<vector<int>> memo(n, vector<int>(n));
        for (int i = n - 2; i >= 0; --i) {
            sums[i] += sums[i + 1];
        }
        return helper(sums, 0, 1, memo);
    }
    int helper(vector<int>& sums, int i, int m, vector<vector<int>>& memo) {
        if (i + 2 * m >= sums.size()) return sums[i];
        if (memo[i][m] > 0) return memo[i][m];
        int res = 0;
        for (int x = 1; x <= 2 * m; ++x) {
            int cur = sums[i] - sums[i + x];
            res = max(res, cur + sums[i + x] - helper(sums, i + x, max(x, m), memo));
        }
        return memo[i][m] = res;
    }
};

Leetcode1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

1
2
3

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

1
2
3

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

1
2
3

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

这道题让求最长相同的子序列。使用一个二维数组 dp，其中dp[i][j]表示text1的前i个字符和text2的前j个字符的最长相同的子序列的字符个数，这里大小初始化为(m+1)x(n+1)，这里的m和n分别是text1和text2的长度。接下来就要找状态转移方程了，如何来更新dp[i][j]，若二者对应位置的字符相同，表示当前的LCS又增加了一位，所以可以用dp[i-1][j-1] + 1来更新dp[i][j]。否则若对应位置的字符不相同，由于是子序列，还可以错位比较，可以分别从text1或者text2去掉一个当前字符，那么其dp值就是dp[i-1][j]和dp[i][j-1]，取二者中的较大值来更新dp[i][j]即可，最终的结果保存在了dp[m][n]中，参见代码如下：

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

class Solution {
public:
    int longestCommonSubsequence(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int>> dp(m+1, vector(n+1, 0));
        for (int i = 1; i <= m; i ++)
            for (int j = 1; j <= n; j ++) 
                if (word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        return dp[m][n];
    }
};

Leetcode1144. Decrease Elements To Make Array Zigzag

Given an array nums of integers, a move consists of choosing any element and decreasing it by 1.

An array A is a zigzag array if either:

Every even-indexed element is greater than adjacent elements, ie. A[0] > A[1] < A[2] > A[3] < A[4] > …
OR, every odd-indexed element is greater than adjacent elements, ie. A[0] < A[1] > A[2] < A[3] > A[4] < …
Return the minimum number of moves to transform the given array nums into a zigzag array.

Example 1:

1
2
3

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Example 2:

1
2

Input: nums = [9,6,1,6,2]
Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

这道题说是每次可以给数组中的任意数字减小1，现在想将数组变为之字形，就是数字大和小交替出现，有两种，一种是偶数坐标的数字均大于其相邻两个位置的数字，一种是奇数坐标的数字均大于其相邻的两个位置的数字。对于第一种情况来说，其奇数坐标位置的数字就均小于其相邻两个位置的数字，同理，对于第二种情况，其偶数坐标位置的数字就均小于其相邻两个位置的数字。这里我们可以分两种情况来统计减少次数，一种是减小所有奇数坐标上的数字，另一种是减小所有偶数坐标上的数字。减小的方法是找到相邻的两个数字中的较小那个，然后比其小1即可，即可用 nums[i] - min(left, right) + 1 来得到，若得到了个负数，说明当前数字已经比左右的数字小了，不需要再减小了，所以需要跟0比较，取较大值。这里用了一个大小为2的 res 数组，这用直接根据当前坐标i，通过 i%2 就可以更新对应的次数了，最终取二者中的较小值返回即可，参见代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int n = nums.size(), res[2] = {0, 0};
        for (int i = 0; i < n; ++i) {
            int left = i > 0 ? nums[i - 1] : 1001;
            int right = i < n - 1 ? nums[i + 1] : 1001;
            res[i % 2] += max(0, nums[i] - min(left, right) + 1);
        }
        return min(res[0], res[1]);
    }
};

Leetcode1146. Snapshot Array

Implement a SnapshotArray that supports the following interface:

SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.

• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

1
2
3
4
5
6
7
8
9

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

• 1 <= length <= 50000
• At most 50000 calls will be made to set, snap, and get.
• 0 <= index < length
• 0 <= snap_id < (the total number of times we call snap())
• 0 <= val <= 10^9

这道题让实现一个 SnapshotArray 的类，具有给数组拍照的功能，就是说在某个时间点spapId拍照后，当前数组的值需要都记录下来，同理，每一次调用snap()函数时，都需要记录整个数组的状态，这是为了之后可以查询任意一个时间点上的任意一个位置上的值。最简单粗暴的方法当前就是用一个二维数组，每次拍照的时候，都把整个数组都存到二维数组中，其坐标就是snapId。但是这种方法不高效，而且占用了巨大的空间，被 OJ 豪不留情的抹杀掉了。来分析一下不高效的原因，这是因为每次拍照时，可能数组的大部分数据并没有变动，每次都再存一遍整个数组是浪费的。这里我们关心的是调用set()函数，因为这会改变数组的值，若能建立snapId和更新值之间的映射，就可以根据二分法来快速定位某一个snapId的值了，因为snapId是按顺序递增的。这样就可以用一个Vector of Map 或者 Map of Map 的数据结构来实现，外层的 TreeMap 是映射建立数组坐标到内层 TreeMap 之间的映射，内层的 TreeMap 是建立 snapId 和更新值之间的映射。初始化时，要将 0->0 这个映射对儿加到每一个位置，因为初始化时数组的每个元素都是0。在set()函数中就可以更新HashMap中的映射值，snap()就直接累加snapId，比较麻烦的就是get()函数，给定的snapId可能在内层的HashMap中不存在，需要查找第一个不大于给定snapId的映射值，那么就先找第一个大于snapId的位置，再回退一位就好了，参见代码如下：

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 SnapshotArray {
public:
    SnapshotArray(int length) {
        for (int i = 0; i < length; ++i) {
            snapMap[i] = {{0, 0}};
        }
    }
    
    void set(int index, int val) {
        snapMap[index][snapId] = val;
    }
    
    int snap() {
        return snapId++;
    }
    
    int get(int index, int snap_id) {
        auto it = snapMap[index].upper_bound(snap_id);
        --it;
        return it->second;
    }

private:
    int snapId = 0;
    map<int, map<int, int>> snapMap;
};

Leetcode1147. Longest Chunked Palindrome Decomposition

You are given a string text. You should split it to k substrings (subtext1, subtext2, …, subtextk) such that:

• subtexti is a non-empty string.
• The concatenation of all the substrings is equal to text (i.e., subtext1 + subtext2 + … + subtextk == text).
• subtexti == subtextk - i + 1 for all valid values of i (i.e., 1 <= i <= k).

Return the largest possible value of k.

Example 1:

1
2
3

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

1
2
3

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

1
2
3

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

1
2
3

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Constraints:

• 1 <= text.length <= 1000
• text consists only of lowercase English characters.

这道题是关于段式回文的，想必大家对回文串都不陌生，就是前后字符对应相同的字符串，比如 noon 和 bob。这里的段式回文相等的不一定是单一的字符，而是可以是字串，参见题目中的例子，现在给了一个字符串，问可以得到的段式回文串的最大长度是多少。由于段式回文的特点，你可以把整个字符串都当作一个子串，则可以得到一个长度为1的段式回文，所以答案至少是1，不会为0。而最好情况就是按字符分别相等，那就变成了一般的回文串，则长度就是原字符串的长度。比较的方法还是按照经典的验证回文串的方式，用双指针来做，一前一后。不同的是遇到不相等的字符不是立马退出，而是累加两个子串 left 和 right，每累加一个字符，都比较一下 left 和 right 是否相等，这样可以保证尽可能多的分出来相等的子串，一旦分出了相等的子串，则 left 和 right 重置为空串，再次从小到大比较，参见代码如下：

解法一：

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

class Solution {
public:
    int longestDecomposition(string text) {
        int res = 0, n = text.size();
        string left, right;
        for (int i = 0; i < n; ++i) {
            left += text[i], right = text[n - i - 1] + right;
            if (left == right) {
                ++res;
                left = right = "";
            }
        }
        return res;
    }
};

我们也可以使用递归来做，写法更加简洁一些，i从1遍历到 n/2，代表的是子串的长度，一旦超过一半了，说明无法分为两个了，最终做个判断即可。为了不每次都提取出子串直接进行比较，这里可以先做个快速的检测，即判断两个子串的首尾字符是否对应相等，只有相等了才会提取整个子串进行比较，这样可以省掉一些不必要的计算，参见代码如下：

解法二：

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

class Solution {
public:
    bool is_equal(string text, int x, int y, int len) {
        for (int i = 0; i < len; i ++)
            if (text[x+i] != text[y+i])
                return false;
        return true;
    }
    
    int longestDecomposition(string text) {
        int n = text.length();
        for (int i = 1; i <= n/2; i ++) {
            if (is_equal(text, 0, n-i, i))
                return 2 + longestDecomposition(text.substr(i, n-i*2));
        }
        return n > 0 ? 1 : 0;
    }
};

Leetcode1154. Day of the Year

Given a string date representing a Gregorian calendar date formatted as YYYY-MM-DD, return the day number of the year.

Example 1:

1
2
3

Input: date = "2019-01-09"
Output: 9
Explanation: Given date is the 9th day of the year in 2019.

Example 2:

1
2

Input: date = "2019-02-10"
Output: 41

Example 3:

1
2

Input: date = "2003-03-01"
Output: 60

Example 4:

1
2

Input: date = "2004-03-01"
Output: 61

判断一个日期是一年中的第几天。

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

class Solution {
public:
    int dayOfYear(string date) {
        int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
        int year = stoi(date.substr(0, 4));
        int month = stoi(date.substr(5,7));
        int day = stoi(date.substr(8, 10));
        int ans = 0;
        for(int i = 0; i < month; i ++)
            ans += days[i];
        ans += day;
        if((year%100==0 && year%400 == 0) || (year%100 != 0 && year%4 == 0))
            if(month > 2)
                ans += 1;
        return ans;
    }
};

Leetcode1156. Swap For Longest Repeated Character Substring

You are given a string text. You can swap two of the characters in the text.

Return the length of the longest substring with repeated characters.

Example 1:

1
2
3

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa" with length 3.

Example 2:

1
2
3

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa" with length 6.

Example 3:

1
2
3

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa" with length is 5.

核心是如下几种情况

• 仅有一段连续的字符
• 两段及以上的连续的字符，它们之间仅有有一个不符合，可以连接在一起
• 两段及以上的连续的字符，但是中间超过1个，按照要求，没办法连接

思路

• 遍历一次字符串，构建不同的连续字符串的起点到终点的数组
• 按照每个字符去遍历，考虑上面3种情况，同时需要额外考虑
• 对于情况2，如果有多一个同样的字符，交换后就是a+b+1,额外一个字符交换过来
• 对于情况3，额外交换一个，即a+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

class Solution {
public:
    int maxRepOpt1(string text) {
        vector<vector<pair<int, int> > > mapp(26, vector<pair<int, int>>());;
        int i = 0, n = text.length();
        while(i < n) {
            int j = i+1;
            while(j < n && text[i] == text[j])
                j ++;
            mapp[text[i]-'a'].push_back(make_pair(i, j-1));
            i = j;
        }
        int res = 0;
        for (i = 0; i < 26; i ++) {
            if (mapp[i].size() == 0)
                continue;
            int len = mapp[i].size();
            bool has_equal = len > 1;
            for (int j = 0; j < len; j ++) {
                res = max(res, mapp[i][j].second - mapp[i][j].first + 1 + has_equal);
            }
            
            if (len >= 2) {
                has_equal = len > 2;
                for (int j = 0; j < len-1; j ++) 
                    if (mapp[i][j+1].first - mapp[i][j].second == 2)
                        res = max(res, mapp[i][j].second-mapp[i][j].first+1 + mapp[i][j+1].second-mapp[i][j+1].first+1 + has_equal);
            }
        }
        return res;
    }
};

Leetcode1155. Number of Dice Rolls With Target Sum

You have d dice and each die has f faces numbered 1, 2, …, f.

Return the number of possible ways (out of fd total ways) modulo 109 + 7 to roll the dice so the sum of the face-up numbers equals target.

Example 1:

1
2
3
4

Input: d = 1, f = 6, target = 3
Output: 1
Explanation:
You throw one die with 6 faces.  There is only one way to get a sum of 3.

Example 2:

1
2
3
4
5

Input: d = 2, f = 6, target = 7
Output: 6
Explanation:
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

1
2
3
4

Input: d = 2, f = 5, target = 10
Output: 1
Explanation:
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4:

1
2
3
4

Input: d = 1, f = 2, target = 3
Output: 0
Explanation:
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5:

1
2
3
4

Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation:
The answer must be returned modulo 10^9 + 7.

Constraints:

• 1 <= d, f <= 30
• 1 <= target <= 1000

这道题题说是给了d个骰子，每个骰子有f个面，现在给了一个目标值 target，问同时投出这d个骰子，共有多少种组成目标值的不同组合，结果对超大数字 1e9+7 取余。首先来考虑 dp 数组该如何定义，根据硬币找零系列的启发，目标值本身肯定是占一个维度的，因为这个是要求的东西，另外就是当前骰子的个数也是要考虑的因素，所以这里使用一个二维的 dp 数组，其中dp[i][j]表示使用i个骰子组成目标值为j的所有组合个数，大小为d+1 by target+1，并初始化dp[0][0]为1。接下来就是找状态转移方程了，当前某个状态dp[i][k]跟什么相关呢，其表示为使用i个骰子组成目标值k，那么拿最后一个骰子的情况分析，其可能会投出[1,f]中的任意一个数字j，那么之前的目标值就是k-j，且用了i-1个骰子，其dp值就是dp[i-1][k-j]，当前投出的点数可以跟之前所有的情况组成一种新的组合，所以当前的dp[i][k]就要加上dp[i-1][k-j]，那么状态转移方程就呼之欲出了：

1

dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % M;

解法一：

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

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        int M = 1e9 + 7;
        vector<vector<int>> dp(d + 1, vector<int>(target + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= d; ++i) {
            for (int j = 1; j <= f; ++j) {
                for (int k = j; k <= target; ++k) {
                    dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % M;
                }
            }
        }
        return dp[d][target];
    }
};

我们可以进行空间上的优化，由于当前使用i个骰子的状态值依赖于使用 i-1 个骰子的状态，所以没必要保存所有的骰子个数的 dp 值，可以在遍历i的时候，新建一个临时的数组t，来保存使用i个骰子的 dp 值，并在最后交换 dp 和 t 即可，参见代码如下：

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

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        int M = 1e9 + 7;
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= d; ++i) {
            vector<int> t(target + 1);
            for (int j = 1; j <= f; ++j) {
                for (int k = j; k <= target; ++k) {
                    t[k] = (t[k] + dp[k - j]) % M;
                }
            }
            swap(dp, t);
        }
        return dp[target];
    }
};

Leetcode1160. Find Words That Can Be Formed by Characters

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

1
2
3
4

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

1
2
3
4

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• All strings contain lowercase English letters only.

一道简单题卡了这么久，我真的是太弱鸡了，不过它卡时间很扯淡。。。chars中每个字符出现的次数要大于等于word中每个字符出现的次数，即表示可以组成这个word。

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

class Solution {
	public:
    int countCharacters(vector<string>& words, string chars) {
        int char_len[26];
        for(int i=0;i<26;i++)
            char_len[i]=0;
        for(int i=0;i<chars.length();i++)
            char_len[chars[i]-'a']++;
        int res=0;
        int word_len[26];
        for(int i=0;i<words.size();i++){
            bool flag=true;
            for(int j=0;j<26;j++)
                word_len[j]=0;
            for(int j=0;j<words[i].length();j++)
                if(++word_len[words[i][j]-'a'] > char_len[words[i][j]-'a']){
                    flag=false;
                    break;
                }
            if(flag) 
                res += words[i].length();
        }
        return res;
    }    
};

Leetcode1161. Maximum Level Sum of a Binary Tree

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Example 1:

1
2
3
4
5
6
7

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

很简单的层次遍历，就当熟悉一下queue的用法。

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

class Solution {
	public:
    int maxLevelSum(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int maxx = -99999;
        int layer = 0, max_layer = 0;
        while(!q.empty()){
            int len = q.size();
            int sum = 0;
            layer++;
            for(int i = 0; i < len; i ++){
 	            TreeNode* temp = q.front();
		        q.pop();
		        if(temp->left != NULL)
		            q.push(temp->left);
			    if(temp->right != NULL)
		            q.push(temp->right);
			    sum += temp->val;
			}
			if(sum > maxx){
			    maxx = sum;
			    max_layer = layer;
			}
	    }
	    return max_layer;
	}
};

Leetcode1162. As Far from Land as Possible

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Example 1:

1
2
3

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

1
2
3

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1

这道题给了一个只有0和1的二维数组，说是0表示水，1表示陆地，现在让找出一个0的位置，使得其离最近的1的距离最大，这里的距离用曼哈顿距离表示。这里最暴力的方法就是遍历每个0的位置，对于每个遍历到的0，再遍历每个1的位置，计算它们的距离，找到最小的距离保存为该0位置的距离，然后在所有0位置的距离中找出最大的。这种方法不是很高效，目测无法通过 OJ，博主都没有尝试。其实这道题的比较好的解法是建立距离场，即每个大于1的数字表示该位置到任意一个1位置的最短距离，在之前那道 Shortest Distance from All Buildings 就用过这种方法。建立距离场用 BFS 比较方便，因为其是一层一层往外扩散的遍历，这里需要注意的是要一次把所有1的位置都加入 queue 中一起遍历，而不是对每个1都进行 BFS，否则还是过不了 OJ。这里先把位置1都加入 queue，然后这里先做个剪枝，若位置1的个数为0，或者为 n^2，表示没有陆地，或者没有水，直接返回 -1。否则进行 while 循环，步数 step 加1，然后用 for 循环确保进行层序遍历，一定要将 q.size() 放到初始化中，因为其值可能改变。然后就是标准的 BFS 写法了，取队首元素，遍历其相邻四个结点，若没有越界且值为0，则将当前位置值更新为 step，然后将这个位置加入 queue 中继续遍历。循环退出后返回 step-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

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int step = 0, n = grid.size();
        vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        queue<vector<int>> q;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) continue;
                q.push(vector<int>{i, j});
            }
        }
        if (q.size() == 0 || q.size() == n * n) return -1;
        while (!q.empty()) {
            ++step;
            for (int k = q.size(); k > 0; --k) {
                auto t = q.front(); q.pop();
                for (auto dir : dirs) {
                    int x = t[0] + dir[0], y = t[1] + dir[1];
                    if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 0) continue;
                    grid[x][y] = step;
                    q.push({x, y});
                }
            }
        }
        return step - 1;
    }
};

我们也可以强行用 DFS 来做，这里对于每一个值为1的点都调用递归函数，更新跟其相连的所有0位置的距离，最终也能算出整个距离场，从而查找出最大的距离，参见代码如下：

解法二：

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

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int res = -1, n = grid.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    helper(grid, i, j);
                }
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] > 1) res = max(res, grid[i][j] - 1);
            }
        }
        return res;
    }
    void helper(vector<vector<int>>& grid, int i, int j, int dist = 1) {
        int n = grid.size();
        if (i < 0 || j < 0 || i >= n || j >= n || (grid[i][j] != 0 && grid[i][j] <= dist)) return;
        grid[i][j] = dist;
        helper(grid, i - 1, j, dist + 1);
        helper(grid, i + 1, j, dist + 1);
        helper(grid, i, j - 1, dist + 1);
        helper(grid, i, j + 1, dist + 1);
    }
};

其实这道题的最优解法并不是 BFS 或者 DFS，而是下面这种两次扫描的方法，在之前那道 01 Matrix 中就使用过。有点像动态规划的感觉，还是建立距离场，先从左上遍历到右下，遇到1的位置跳过，然后初始化0位置的值为 201（因为n不超过 100，所以距离不会超过 200），然后用左边和上边的值加1来更新当前位置的，注意避免越界。然后从右边再遍历到左上，还是遇到1的位置跳过，然后用右边和下边的值加1来更新当前位置的，注意避免越界，同时还要更新结果 res 的值。最终若 res 为 201，则返回 -1，否则返回 res-1，参见代码如下：

解法三：

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 maxDistance(vector<vector<int>>& grid) {
        int res = 0, n = grid.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) continue;
                grid[i][j] = 201;
                if (i > 0) grid[i][j] = min(grid[i][j], grid[i - 1][j] + 1);
                if (j > 0) grid[i][j] = min(grid[i][j], grid[i][j - 1] + 1);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (grid[i][j] == 1) continue;
                if (i < n - 1) grid[i][j] = min(grid[i][j], grid[i + 1][j] + 1);
                if (j < n - 1) grid[i][j] = min(grid[i][j], grid[i][j + 1] + 1);
                res = max(res, grid[i][j]);
            }
        }
        return res == 201 ? -1 : res - 1;
    }
};

Leetcode1165. Single-Row Keyboard

There is a special keyboard with all keys in a single row.

Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25), initially your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index i to index j is |i - j|.

You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.

Example 1:

1
2
3
4

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4. 

Example 2:

1
2

Input: keyboard = "pqrstuvwxyzabcdefghijklmno", word = "leetcode"
Output: 73

Constraints:

• keyboard.length == 26
• keyboard contains each English lowercase letter exactly once in some order.
• 1 <= word.length <= 10^4
• word[i] is an English lowercase letter.

简单打表即可。

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

class Solution {
	public:
    int calculateTime(string keyboard, string word) {
        vector<int> pos(26,-1);
        int k=0;
        for(int i=0;i<keyboard.length();i++)
            pos[keyboard[i]-'a'] = k++;
        int res=pos[word[0]-'a'];
        for(int i=1;i<word.length();i++)
            res += abs(pos[word[i]-'a']-pos[word[i-1]-'a']);
        return res;
    }
};

Leetcode1170. Compare Strings by Frequency of the Smallest Character

Let’s define a function f(s) over a non-empty string s, which calculates the frequency of the smallest character in s. For example, if s = “dcce” then f(s) = 2 because the smallest character is “c” and its frequency is 2.

Now, given string arrays queries and words, return an integer array answer, where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words.

Example 1:

1
2
3

Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").

1
2
3

Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").

第一步，肯定要把每个query和word的f(s)求出来，求每个字符的次数，然后找出最小的字符出现的次数。
第二步，找出words中f(word) > f(query)有多少个时，对于2000*2000的量级，可以暴力两重循环，即对每个query都去遍历一次words的f(word)结果。

时间复杂度O(N^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

class Solution {
	public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> qs, ws;
        for(string query : queries) 
            qs.push_back(getfreq(query));
        for(string word : words)
            ws.push_back(getfreq(word));
        vector<int> res;
        for(int i : qs) {
            int count = 0;
            for(int j : ws) {
                if(j > i)
                    count ++;
            }
            res.push_back(count);
        }
        return res;
    }
        
    int getfreq(string query) {
        vector<int> q(26, 0);
        for(char c : query)
            q[c-'a'] ++;
        for(int i : q)
            if(i != 0)
                return i;
        return 0;
    }
};

Leetcode1171. Remove Zero Sum Consecutive Nodes from Linked List

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

1
2
3

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

1
2

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

1
2

Input: head = [1,2,3,-3,-2]
Output: [1]

对于两个前缀和相等部分，表示里面就是0，所以可以消除，在加入map的时候还能把之前的ListNode覆盖掉，达到消除的目标。消除时候就是把next指针指向和的下一个结点。在第二次遍历的时候发现了现在有的sum和表示当前的节点和后边某个节点的前缀和都是sum，中间的和就是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

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        // 第一次遍历构建 前缀和 到 结点的映射
        // 如果有多个，则保存最后一个，即右边界，尽可能覆盖更多
        unordered_map<int, ListNode*> sum2node;
        // 构建个虚结点来解决结点删除边缘情况
        ListNode* dummy = new ListNode();
        dummy->next = head;
        int sum = 0;
        ListNode* curr = dummy;
        while (curr != nullptr)
        {
            sum += curr->val;
            sum2node[sum] = curr;
            curr = curr->next;
        }

        curr = dummy;
        // 第二次遍历去发现相等为0情况则忽略结点
        sum = 0;
        while (curr != nullptr)
        {
            sum += curr->val;
            // 因为前面计算过没有sum，所以sum必然存在sum2node里
            // 如果正好出现，可能是正常的自己的结点
            // 如果就是下一个相同的结点，那么就是把这一段结点忽略掉
            curr->next = sum2node[sum]->next;
            curr = curr->next;
        }
        return dummy->next;
    }
};

Leetcode1175. Prime Arrangements

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

1
2
3

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

1
2

Input: n = 100
Output: 682289015

题目的意思是计算一个由1到n组成的数列中，质数恰好位于质数索引上的排列组合个数，本质上是一个数学问题。结合n = 5的例子来看，1到5中，只有2,3,5是质数，1和4不是质数，因此排列质数就有321 = 6种可能，分别是:

1

[2,3,5],[2,5,3],[3,2,5],[3,5,2],[5,2,3],[5,3,2]

1

[1,4],[4,1]

1
2

[1,2,3,4,5],[1,2,5,4,3],[1,3,2,4,5],[1,3,5,4,2],[1,5,2,4,3],[1,5,3,4,2]
[4,2,3,1,5],[4,2,5,1,3],[4,3,2,1,5],[4,3,5,1,2],[4,5,2,1,3],[4,5,3,1,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

class Solution {
public:
    
    bool isprime(int n) {
        int nn = sqrt(n);
        for(int i = 2; i <= nn; i ++) {
            if(n % i == 0)
                return false;
        }
        return true;
    }
    
    int numPrimeArrangements(int n) {
        int count1 = 0, count2;
        for(int i = 2; i <= n; i ++) {
            if(isprime(i))
                count1 ++;
        }
        count2 = n - count1;
        long res = 1;
        for(int i = 1; i <= count1; i ++)
            res = (res*i)%(1000000007);
        for(int i = 1; i <= count2; i ++)
            res = (res*i)%(1000000007);
        return res;
    }
};