lihe / leetcode Goto Github PK

Shortest Path in a Grid with Obstacles Elimination

Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2:

Input: 
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
Output: -1
Explanation: 
We need to eliminate at least two obstacles to find such a walk.

Constraints:

• grid.length == m
• grid[0].length == n
• 1 <= m, n <= 40
• 1 <= k <= m*n
• grid[i][j] == 0 **or** 1
• grid[0][0] == grid[m-1][n-1] == 0

算法思路：利用BFS解题，将二维矩阵扩充为三维，z代表当前消除的障碍物数量；visited[x][y][z]，代表消除z个障碍是否到达[x, y]处。

class Solution {
    private int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};


    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;

        boolean[][][] visited = new boolean[m][n][k + 1];
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(0, 0, 0));

        visited[0][0][0] = true;

        int distance = 0;

        while (!queue.isEmpty()){
            distance++;

            int size = queue.size();

            for(int i = 0; i < size; i++){
                Point point = queue.poll();

                int x = point.x;
                int y = point.y;
                int z = point.z;

                if(x == m - 1 && y == n - 1){  // 达到目的地
                    return distance - 1;
                }

                for(int j = 0; j < 4; j++){  // 四个方向
                    int new_x = x + dir[j][0];
                    int new_y = y + dir[j][1];
                    int new_z = z;

                    if(new_x < 0 || new_x >= m || new_y < 0 || new_y >= n){  // 超出矩阵范围
                        continue;
                    }

                    if(grid[new_x][new_y] == 1){
                        if ( z < k){  // 可以继续消除障碍物
                            new_z = z + 1;
                        }
                        else{
                            continue;  // 已经到达上限
                        }
                    }

                    if(!visited[new_x][new_y][new_z]){  // 判断是否访问过
                        queue.add(new Point(new_x, new_y, new_z));

                        visited[new_x][new_y][new_z] = true;
                    }
                }
            }
        }
        return -1;
    }

    class Point{
        int x;
        int y;
        int z;

        public Point(int x, int y, int z){
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
}

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

题意：已知字符串S和字符串T，求在S中的最小窗口，使得这个窗口包含了T中的所有字符。

算法思路：

1. 设置两字符哈希数组，map_s与map_t，map_s代表当前处理的窗口区间中的字符数量，map_t代表了字符串T的字符数量；
2. 设置两个指针i和begin指向字符串S的第一个字符；
3. i指针向后逐个扫描字符串中的字符，这个过程中循环检查begin指针是否可以向前移动；
   • 如果当前begin指向的字符，T中没有出现，直接向前移动begin；
   • 如果当前begin指向的字符，T中出现了，但是当前区间窗口中该字符的数量足够，直接向前移动begin，并跟新map_s;
4. 指针i没向前扫描一个字符，即检查是否可以跟新最终的结果；

在整个过程中，使用begin和i维护一个窗口，该窗口中的子串满足题目条件，窗口线性向前滑动，整体时间复杂度为O(n)。

class Solution{
private:
    bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){
        for(int i = 0; i < vec_t.size(); i++){
            if(map_s[vec_t[i]] < map_t[vec_t[i]]){
                return false;
            }
        }
        return true;
    }

public:
    std::string minWindow(std::string s, std::string t){
        const int MAX_ARRAY_LEN = 128;
        int map_t[MAX_ARRAY_LEN] = {0};
        int map_s[MAX_ARRAY_LEN] = {0};
        std::vector<int> vec_t;
        for(int i = 0; i < t.length(); i++){
            map_t[t[i]]++;
        }
        for(int i = 0; i < MAX_ARRAY_LEN; i++){
            if(map_t[i] > 0){
                vec_t.push_back(i);
            }
        }

        int window_begin = 0;
        std::string result;
        for(int i = 0; i < s.length(); i++){
            map_s[s[i]]++;
            while(window_begin < i){
                char begin_ch = s[window_begin];
                if(map_t[begin_ch] == 0){
                    window_begin++;
                }
                else if(map_s[begin_ch] > map_t[begin_ch]){
                    map_s[begin_ch]--;
                    window_begin++;
                }
                else{
                    break;
                }
            }
            if(is_window_ok(map_s, map_t, vec_t)){
                int new_window_len = i - window_begin + 1;
                if(result == "" || result.length() > new_window_len){
                    result = s.substr(window_begin, new_window_len);
                }
            }
        }
        return result;
    }
};

5279. Subtract the Product and Sum of Digits of an Integer

Easy

Given an integer number n, return the difference between the product of its digits and the sum of its digits.

Example 1:

Input: n = 234
Output: 15 
Explanation: 
Product of digits = 2 * 3 * 4 = 24 
Sum of digits = 2 + 3 + 4 = 9 
Result = 24 - 9 = 15

Example 2:

Input: n = 4421
Output: 21
Explanation: 
Product of digits = 4 * 4 * 2 * 1 = 32 
Sum of digits = 4 + 4 + 2 + 1 = 11 
Result = 32 - 11 = 21

Constraints:

• 1 <= n <= 10^5

class Solution {
    public int subtractProductAndSum(int n) {
        int sum = 0, mum = 1;
        while(n != 0){
            sum += n % 10;
            mum *= n % 10;

            n /= 10;
        }
        return mum - sum;
    }
}

5280. Group the People Given the Group Size They Belong To

Medium

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.

You can return any solution in any order and the same applies for IDs. Also, it is guaranteed that there exists at least one solution.

Example 1:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

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

Constraints:

• groupSizes.length == n
• 1 <= n <= 500
• 1 <= groupSizes[i] <= n

class Solution{
    public List<List<Integer>> groupThePeople(int[] groupSizes){
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();
        
        for(int i = 0; i < groupSizes.length; i++){
            int flag = groupSizes[i];
            if(! map.containsKey(flag))
                map.put(flag, new ArrayList<>());
            
            map.get(flag).add(i);
            
            if(map.get(flag).size() == flag){
                result.add(map.get(flag));
                map.remove(flag);
            }
        }
        return result;
    }
}

5281. Find the Smallest Divisor Given a Threshold

Medium

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:

Input: nums = [19], threshold = 5
Output: 4

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^6
• nums.length <= threshold <= 10^6

class Solution{
    public int smallestDivisor(int[] nums, int threshold){
        int lo = 1, hi = 1000000;

        while (lo < hi){
            int mid = (lo + hi) / 2;

            int result = cal(nums, mid);
            
            if(result > threshold)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
    
    private int cal(int[] nums, int div){
        int sum = 0;
        for(int n : nums){
            sum += Math.ceil((double)n / (double)div);
            //if(n % div != 0) sum += 1;
        }
        return (int)sum;
    }
}

5282. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Hard

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbours of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighboors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

Binary matrix is a matrix with all cells equal to 0 or 1 only.

Zero matrix is a matrix with all cells equal to 0.

Example 1:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2:

Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We don't need to change it.

Example 3:

Input: mat = [[1,1,1],[1,0,1],[0,0,0]]
Output: 6

Example 4:

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix can't be a zero matrix

Constraints:

• m == mat.length
• n == mat[0].length
• 1 <= m <= 3
• 1 <= n <= 3
• mat[i][j] is 0 or 1.

Remove Covered Intervals

Given a list of intervals, remove all intervals that are covered by another interval in the list. Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.

After doing so, return the number of remaining intervals.

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Constraints:

• 1 <= intervals.length <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• intervals[i] != intervals[j] for all i != j

算法思路：

• 对数组进行排序，第一个数字小的放前面；当第一个数字相等时，第二个数字大的放前面；
• result = intervals.lenght，进行一遍遍历，定义max = intervals[0][1]，如果intervals[i][1]于max，result --，如果intervals[i][1]> max，max = intervals[i][1]。

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> {
            if (x[0] < y[0])
                return -1;
            else if (x[0] == y[0]) {
                if (x[1] > y[1])
                    return -1;
            }
            return 1;
        });


        int len = intervals.length;
        int max = intervals[0][1];

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][1] <= max){
                len--;
                continue;
            }
            else if(intervals[i][1] > max){
                max = intervals[i][1];
            }
        }

        return len;
    }
}

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

算法思路：

1. 设置递推数组dp[0...n], dp[i]，dp[i]代表到达第i阶有多少种走法，初始化为0；
2. 设置dp[1] = 1，dp[2] = 2;
3. 利用dp[i] = dp[i - 1] + dp[i - 2]从第三阶推至第n阶。

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

Element Appearing More Than 25% In Sorted Array

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

// 1ms 39.3MB
class Solution {
    public int findSpecialInteger(int[] arr) {
        int result = arr[0];
        int i = 0;
        int cnt = 0;
        while (i < arr.length){
            cnt = 0;
            while (arr[i] == result){
                cnt ++;
                if(cnt >= arr.length / 4 + 1){
                    return result;
                }
                i++;
            }
            result = arr[i];
        }
        return result;
    }
}

// 11ms 39.2MB
class Solution {
    public int findSpecialInteger(int[] arr) {
        int[] list = new int[100000];
        int result = 0;
        for(int i = 0; i < arr.length; i++){
            list[arr[i]]++;
        }
        for(int i = 0; i < list.length; i++){
            if(list[i] >= (int)Math.ceil((double)arr.length / 4)){
                result = i;
            }
        }
        return result;
    }
}

Iterator for Combination

Design an Iterator class, which has:

• A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• A function next() that returns the next combination of length combinationLength in lexicographical order.
• A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• There will be at most 10^4 function calls per test.
• It's guaranteed that all calls of the function next are valid.

import java.util.*;

class CombinationIterator {
    List<String> ans;
    String str;

    int len;
    public CombinationIterator(String characters, int combinationLength) {
        ans = new ArrayList<>();
        str = characters;
        len = combinationLength;
        backtrack(new StringBuilder(), 0);
    }

    public void backtrack(StringBuilder sb, int index){
        if(sb.length() == len){
            ans.add(sb.toString());
            return;
        }
        for(int i = index; i < str.length(); i++){
            sb.append(str.charAt(i));
            backtrack(sb, i + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    public String next() {
        return ans.remove(0);
    }

    public boolean hasNext() {
        return !ans.isEmpty();
    }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

算法思路：

1. 设置一个二维数组dp[][]，并初始化数组为0。dp[][]从底向上递推时，走到三角形第i行第j列时的最优解；
2. 从三角形的底向三角形上方进行动态规划：
   • 动态规划的边界条件：底面上的最优值即为三角形的最底一层的值；
   • 利用i循环，从第二层递推至第一层，对每层的各列进行动态规划递推：第i行，第j列的最优解为dp[i][j]，可达到(i,j)的两个位置的最优解为dp[i + 1][j]和dp[i + 1][j + 1]，dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]。
   • 返回dp[0][0]。

class Solution{
public:
    int minimumTotal(std::vector<std::vector<int>> &triangle){
        if(triangle.size() == 0){
            return 0;
        }
        std::vector<std::vector<int>> dp;
        for(int i = 0; i < triangle.size(); i++){
            dp.push_back(std::vector<int> ());
            for(int j = 0; j < triangle[i].size(); j++){
                dp[i].push_back(0);
            }
        }

        for(int i = 0; i < dp.size(); i++){
            dp[dp.size() -  1][i] = triangle[dp.size() - 1][i];
        }
        for(int i = dp.size() - 2; i >= 0; i--){
            for(int j = 0; j < dp[i].size(); j++){
                dp[i][j] = std::min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return dp[0][0];
    }
};

Sequential Digits

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

Example 1:

Input: low = 100, high = 300
Output: [123,234]

Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]

Constraints:

• 10 <= low <= high <= 10^9

算法思路：一共36个数，通过打表即可解决。

class Solution {
    public List<Integer> sequentialDigits(int low, int high) {
        int[] list = {12, 23, 34, 45, 56, 67, 78, 89,
                123, 234, 345, 456, 567, 678, 789,
        1234, 2345, 3456, 4567, 5678, 6789,
        12345, 23456, 34567, 45678, 56789,
        123456, 234567, 345678, 456789,
        1234567, 2345678, 3456789,
        12345678, 23456789,
        123456789};

        List result = new LinkedList();
        for(int i = 0; i < list.length; i++){
            if(list[i] <= high && list[i] >= low){
                result.add(list[i]);
            }
        }
        return result;
    }
}

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

解题思路：

1. 设dp[i][j]是到达(i,j)时的最优解；
2. dp[i, j] = min(dp[i-1][j], dp[i][j-1]) + grid(i,j)

class Solution{
public:
    int minPathSum(std::vector<std::vector<int>> &grid){
        if(grid.size() == 0){
            return 0;
        }
        int row = grid.size();
        int column = grid[0].size();
        std::vector<std::vector<int>> dp(row, std::vector<int>(column, 0));

        dp[0][0] = grid[0][0];
        for(int i = 1; i < column; i++){
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for(int i = 1; i < row; i++){
            dp[i][0] = dp[i - 1][0] + grid[i][0];
            for(int j = 1; j < column; j++){
                dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[row - 1][column - 1];
    }
};

Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

题意：将DNA序列看成一个只包含[A，B，C，D]四个字符的字符串，给一个DNA字符串，找出所有长度为10的且出现次数超过一次的字符串。

算法思路：

方法一：

1. 枚举DNA字符串中所有的长度为10的子串，将其插入到哈希Map中，并记录子串的数量；
2. 遍历哈希Map，将所有出现次数超过一次的子串存储到结果中

算法复杂度为O(n)

class Solution{
public:
    std::vector<std::string> findRepeatedDnaSequences(std::string s){
        std::map<std::string, int> word_map;
        std::vector<std::string> result;
        for(int i = 0; i < s.length(); i++){
            std::string word = s.substr(i, 10);
            if(word_map.find(word) != word_map.end()){
                word_map[word] += 1;
            }
            else{
                word_map[word] = 1;
            }
        }
        std::map<std::string, int> :: iterator it;
        for(it = word_map.begin(); it != word_map.end(); it++){
            if(it -> second > 1){
                result.push_back(it -> first);
            }
        }
        return result;
    }
};

方法二：

1. 设置全局变量哈希int g_hash_map[1028576] 1048576 = 2^20，表示所有的长度为10的DNA序列；
2. 将DNA字符串的前十个字符使用左移运算转化为整数key，g_hash_map[key]++;
3. 从DNA的第11个字符开始，按顺序遍历各个字符，遇到一个字符即将key右移二位（去掉最低位），并将新的DNA字符s[i]转化为整数后，或到最后两位，g_hash_map[key]++;
4. 遍历哈希表g_hash_map，若g_hash_map[i] > 1，将i从低到高位转化为10个DNA序列，push到结果数组。

int g_hash_map[1048576] = {0};

std::string change_int_to_DNA(int DNA){
    static const char DNA_CHAR[] = {'A', 'C', 'G', 'T'};
    std::string str;
    for(int i = 0; i < 10; i++){
        str += DNA_CHAR[DNA & 3];
        DNA = DNA >> 2;
    }
    return str;
}

class Solution{
public:
    std::vector<std::string> findRepeatedDnaSequences(std::string s){
        std::vector<std::string> result;
        if(s.length() < 10){
            return result;
        }
        for(int i = 0; i < 1048576; i++){
            g_hash_map[i] = 0;
        }
        int char_map[128] = {0};
        char_map['A'] = 0;
        char_map['C'] = 1;
        char_map['G'] = 2;
        char_map['T'] = 3;
        int key = 0;
        for(int i = 9; i >= 0; i--){
            key = (key << 2) + char_map[s[i]];
        }
        g_hash_map[key] = 1;
        for(int i = 10; i < s.length(); i++){
            key = key >> 2;
            key = key | (char_map[s[i]] << 18);
            g_hash_map[key]++;
        }
        for(int i = 0; i < 1048576; i++){
            if(g_hash_map[i] > 1){
                result.push_back(change_int_to_DNA(i));
            }
        }
        return result;
    }
};

Count Servers that Communicate

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m <= 250
• 1 <= n <= 250
• grid[i][j] == 0 or 1

算法思路：首先遍历一遍，记录每行每列分别有多少台服务器；然后再便利一遍，如果grid[i, j] = 1，count_row[i] > 1 或 count_col[j] > 1，则result++。

class Solution {
    public int countServers(int[][] grid) {
        int row_n = grid.length;
        int col_n = grid[0].length;

        int[] count_row = new int[row_n];
        int[] count_col = new int[col_n];

        for(int i = 0; i < row_n; i++){
            for(int j = 0; j < col_n; j++){
                if(grid[i][j] == 1){
                    count_row[i]++;
                    count_col[j]++;
                }
            }
        }

        int result=  0;
        for(int i = 0; i < row_n; i++){
            for(int j = 0; j < col_n; j++){
                if(grid[i][j] == 1 && (count_row[i] > 1 || count_col[j] > 1)){
                    result++;
                }
            }
        }
        return result;
    }
}

第一次参加Leetcode周赛，做出来两题，感觉排名前十的都是神仙。

5255. Cells with Odd Values in a Matrix

Easy

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

Example 1:

Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

Example 2:

Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.

Constraints:

• 1 <= n <= 50
• 1 <= m <= 50
• 1 <= indices.length <= 100
• 0 <= indices[i][0] < n
• 0 <= indices[i][1] < m

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        if(indices.size() == 0)
            return 0;
        vector<vector<int>> girl(n, vector<int>(m, 0));
        for(int i = 0; i < indices.size(); i++){
            int row = indices[i][0];
            int col = indices[i][1];
            for(int j = 0; j < m; j++){
                girl[row][j]++;
            }
            for(int j = 0; j < n; j++){
                girl[j][col]++;
            }
        }
        int result = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(girl[i][j] % 2){
                    result++;
                }
            }
        }
        return result;
    }
};

5256. Reconstruct a 2-Row Binary Matrix

Medium

Given the following details of a matrix with n columns and 2 rows :

• The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
• The sum of elements of the 0-th(upper) row is given as upper.
• The sum of elements of the 1-st(lower) row is given as lower.
• The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:

• 1 <= colsum.length <= 10^5
• 0 <= upper, lower <= colsum.length
• 0 <= colsum[i] <= 2

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int sum = 0;
        for(int i = 0; i < colsum.size(); i++){
            sum += colsum[i];
        }
        int all = upper + lower;
        if(all != sum)
            return vector<vector<int>>();
        vector<vector<int>> girl(2, vector<int>(colsum.size(), 0));
        for(int i = 0; i < colsum.size(); i++){
            girl[0][i] = colsum[i];
        }
        for(int i = 0; i < colsum.size(); i++){
            if(lower !=0 && girl[0][i] != 0){
                girl[0][i]--;
                girl[1][i]++;
                lower--;
            }
        }
        return girl;
    }
};

5257. Number of Closed Islands

Medium

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

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

Constraints:

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

class Solution{
public:
    void dfs(std::vector<std::vector<int>> &grid, int i, int j, int &val){
        if(i < 0 || i == grid.size()|| j < 0 || j == grid[0].size()){  // 边界条件
            val = 0;
            return;
        }
        if(grid[i][j] == 1)
            return;
        grid[i][j] = 1;  // 标记已访问过的方块
        dfs(grid, i + 1, j, val);
        dfs(grid, i - 1, j, val);
        dfs(grid, i, j - 1, val);
        dfs(grid, i, j + 1, val);
    }

    int closedIsland(std::vector<std::vector<int>> &grid){
        int result = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 0){
                    int val = 1;
                    dfs(grid, i, j, val);
                    result += val;
                }
            }
        }
        return result;
    }
};

5258. Maximum Score Words Formed by Letters

Hard

Given a list of words, list of single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

Example 1:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

Example 2:

Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.

Example 3:

Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter "e" can only be used once.

Constraints:

• 1 <= words.length <= 14
• 1 <= words[i].length <= 15
• 1 <= letters.length <= 100
• letters[i].length == 1
• score.length == 26
• 0 <= score[i] <= 10
• words[i], letters[i] contains only lower case English letters.

class Solution{
public:
    vector<int> group(vector<string> &words, int bit){
        vector<int> g(26, 0);
        for(int i = 0; i < words.size(); i++){
            if(bit & (1 << i)){
                for(auto c : words[i]){
                    g[c - 'a']++;
                }
            }
        }
        return g;
    }

    int maxScoreWords(vector<string> &words, vector<char> &letters, vector<int> &score){
        vector<int> l(26, 0);
        for(auto c : letters){
            l[c - 'a']++;
        }

        int result = 0;
        for(int i = 0; i < (1 << words.size()); i++){
            auto g = group(words, i);
            int temp = 0;
            for(int j = 0; j < 26; j++){
                if(l[j] < g[j]){
                    temp = 0;
                    break;
                }
                else{
                    temp += g[j] * score[j];
                }
            }
            result = max(result, temp);
        }
        return result;
    }
};

Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Given a m x n matrix mat and an integer threshold. Return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

Constraints:

• 1 <= m, n <= 300
• m == mat.length
• n == mat[i].length
• 0 <= mat[i][j] <= 10000
• 0 <= threshold <= 10^5

class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int result = 0;

        for(int i = 0; i < mat.length; i++){
            for(int j = 0; j < mat[0].length; j++){
                if(j != 0){
                    mat[i][j] += mat[i][j - 1];
                }
                int len = 0;
                int maxlen = Math.min(i, j) + 1;
                while (len < maxlen){
                    int area = 0;
                    for(int k = 0; k < len + 1; k++){
                        int prefix = j - len - 1 < 0 ? 0 : mat[i - k][j - len - 1];
                        area += mat[i - k][j] - prefix;
                    }
                    if(area > threshold) {
                        break;
                    }
                    len++;
                }
                result =  len > result ? len : result;
            }
        }
        return result;
    }
}

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

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

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

分析：由于同时从相邻的两个房屋中盗取财宝就会触发报警器，所以若选择盗取第i个房间的财宝就一定不能选择第i-1个房间的财宝，若不从第i个房间盗取财宝则相当于只考虑从前i-1个房间盗取财宝。

解题思路：

1. 确认原问题和子问题：
   • 原问题为求n个房间的最优解，子问题为求前1个房间，前2个房间...前n-1个房间的最优解。
2. 确认状态：
   • 第i个状态为前i个房间能获得的最大财宝。
3. 确认边界状态的值：
   • 前1个房间的最优解是第一个房间的财宝；
   • 前2个房间的最优解是第1、2个房间中较大财宝的；
4. 确定状态转移方程：
   • 选择第i个房间：第i个房间和前i-2个房间的最优解；
   • 不选择第i个房间：前i-1个房间的最优解；
   • 状态转移方程为：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (i >= 3)。

class Solution{
public:
    int rob(std::vector<int> &nums){
        if(nums.size() == 0){
            return 0;
        }
        if(nums.size() == 1){
            return nums[0];
        }
        std::vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        dp[1] = std::max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); i++){
            dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

Student Attendance Record I

You are given a string representing an attendance record for a student. The record only contains the following three characters:

1. 'A' : Absent.
2. 'L' : Late.
3. 'P' : Present.

A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False

class Solution {
    public boolean checkRecord(String s) {
        int count = 0;
        for(int i = 0; i < s.length() && count < 2; i++){
            if(s.charAt(i) == 'A')
                count++;
        }
        return count < 2 && s.indexOf("LLL") < 0;
    }
}

Minimum Time Visiting All Points

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

• In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
• You have to visit the points in the same order as they appear in the array.

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
Time from [1,1] to [3,4] = 3 seconds 
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Constraints:

• points.length == n
• 1 <= n <= 100
• points[i].length == 2
• -1000 <= points[i][0], points[i][1] <= 1000

算法思路：两个点之间移动所需的最短时间，取决于横纵坐标中相差较大的。

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int result = 0;
        for(int i = 0; i < points.length - 1; i++){
            int x = Math.abs(points[i][0] - points[i + 1][0]);
            int y = Math.abs(points[i][1] - points[i + 1][1]);
            if(x >= y)
                result += x;
            else 
                result += y;
        }
        return result;
    }
}

Number of Closed Islands

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

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

Example 3:

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

Constraints:

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

class Solution{
public:
    void dfs(std::vector<std::vector<int>> &grid, int i, int j, int &val){
        if(i < 0 || i == grid.size()|| j < 0 || j == grid[0].size()){
            val = 0;
            return;
        }
        if(grid[i][j] == 1)
            return;
        grid[i][j] = 1;
        dfs(grid, i + 1, j, val);
        dfs(grid, i - 1, j, val);
        dfs(grid, i, j - 1, val);
        dfs(grid, i, j + 1, val);
    }

    int closedIsland(std::vector<std::vector<int>> &grid){
        int result = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 0){
                    int val = 1;
                    dfs(grid, i, j, val);
                    result += val;
                }
            }
        }
        return result;
    }
};

Search Suggestions System

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

• 1 <= products.length <= 1000
• There are no repeated elements in products.
• 1 <= Σ products[i].length <= 2 * 10^4
• All characters of products[i] are lower-case English letters.
• 1 <= searchWord.length <= 1000
• All characters of searchWord are lower-case English letters.

算法思路：对products排序后暴力解决。

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);

        List<List<String>> result = new ArrayList<>();
        
        for(int i = 1; i <= searchWord.length(); i++){
            
            String substr = searchWord.substring(0, i);  // 生成子串
            
            List<String> collector = new ArrayList<>();
            for(String x: products){
                if(x.startsWith(substr)){  // x是否以substr为前缀
                    collector.add(x);
                    if(collector.size() == 3)
                        break;
                }
            }
            result.add(collector);
        }
        return result;
    }
}

Minimum Swaps to Make Strings Equal

You are given two strings s1 and s2 of equal length consisting of letters "x" and "y" only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

Example 1:

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: 
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2:

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: 
Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

Example 3:

Input: s1 = "xx", s2 = "xy"
Output: -1

Example 4:

Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4

Constraints:

• 1 <= s1.length, s2.length <= 1000
• s1, s2 only contain 'x' or 'y'.

class Solution {
    public int minimumSwap(String s1, String s2) {
        int xy = 0;
        int yx = 0;
        for(int i = 0; i < s1.length(); i ++){
            if(s1.charAt(i) == s2.charAt(i)){
                continue;
            }
            else if(s1.charAt(i) == 'x') xy++;
            else yx++;
        }
        return ((xy + yx) & 1) == 1 ? -1 : (xy + 1) / 2 + (yx + 1) / 2;
    }
}

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" 
             is a subsequence and not a substring.

题意：已知一个字符串，求该字符串的无重复字符的最长子串长度。

算法思路：

1. 设置一个记录字符数量的字符哈希，char_map;
2. 设置一个记录当前满足条件的最长子串变量word；
3. 设置两个指针（记做指针i和指针begin）指向字符串的第一个字符；
4. 设置最长满足条件的子串的长度result；
5. i指针向后逐个扫描字符串中的字符，在这个过程中，使用char_map，记录字符数量；
   • 如果word中没有出现过该字符：对word尾部添加字符并检查result是否需要更新；
   • 否则：begin指针向前移动，更新char_map中的字符数量，直到字符s[i]数量为1，更新word，将word赋值为begin和i之间的 子串。

在整个过程之间，使用begin和i维护一个窗口，该窗口中的子串满足题目中的条件，窗口线性向前滑动，时间复杂度为O(n)。

class Solution{
public:
    int lengthOfLongestSubstring(std::string s){
        int begin = 0;
        int result = 0;
        std::string word = "";
        int char_map[128] = {0};
        for(int i = 0; i < s.length(); i++){
            char_map[s[i]]++;
            if(char_map[s[i]] == 1){
                word += s[i];
                if(result < word.length()){
                    result = word.length();
                }
            }
            else{
                while(begin < i && char_map[s[i]] > 1){
                    char_map[s[begin]]--;
                    begin++;
                }
                word = "";
                for(int j = begin;j <= i; j++){
                    word += s[j];
                }
            }
        }
        return result;
    }
};

Word Pattern

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

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

Example 1:

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

Example 2:

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

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

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

题意：一直str和pattern，判断str和pattern是否匹配。（匹配代表字符创str和pattern中的字符一一对应）

解题思路：

1. 设置字符串到pattern单词的映射（哈希表）；使用数字use[128]记录pattern字符是否使用。
2. 便利str，按照空格拆分单词，同时对应的向前移动指向pattern字符的指针，每拆分出一个单词，判断：
   • 如果该单词从未出现在哈希表中：
     • 如果当前的pattern字符已被使用，返回false
     • 将该单词与当前指向的pattern字符做映射
     • 标记当前指向的pattern字符已被使用
   • 否则：
     • 如果当前单词在哈希表中的映射不是指向当前的pattern字符，则返回false
3. 若单词个数与pattern字数不匹配，则返回false。

class Solution {
public:
    bool wordPattern(std::string pattern, std::string str) {
    	std::map<std::string, char> word_map;
    	char used[128] = {0};
    	std::string word;
    	int pos = 0;
    	str.push_back(' ');
    	for (int i = 0; i < str.length(); i++){
	    	if (str[i] == ' '){
	    		if (pos == pattern.length()){
	    			return false;
		    	}
	    		if (word_map.find(word) == word_map.end()){
	    			if (used[pattern[pos]]){
			    		return false;
			    	}
		    		word_map[word] = pattern[pos];
		    		used[pattern[pos]] = 1;
		    	}
		    	else{
	    			if (word_map[word] != pattern[pos]){
			    		return false;
			    	}
	    		}
	    		word = "";
	    		pos++;
	    	}
	    	else{
	    		word += str[i];
	    	}
	    }
	    if (pos != pattern.length()){
    		return false;
    	}
        return true;
    }
};

Number of Ways to Stay in the Same Place After Some Steps

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps.

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

Example 1:

Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

Constraints:

• 1 <= steps <= 500
• 1 <= arrLen <= 10^6

算法思路：利用动态规划的**，设dp[steps][len]表示经过steps步到达len位置的方法的数量，dp[i][j] = dp[i - 1][j - 1] + dp[i -1][j] + dp[i + 1][j - 1]，且len <= steps + 1，所以len取steps + 1和arrLen中的较小值。

class Solution {
    private static int MOD = 1_000_000_007;

    public int numWays(int steps, int arrLen) {
        int len = Math.min(steps + 1, arrLen);

        int[][] dp = new int[steps+1][len];
        dp[0][0] = 1;
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j < len; j++) {
                dp[i][j] = dp[i-1][j];
                if (j - 1 >= 0){
                    dp[i][j] += dp[i-1][j-1];
                    dp[i][j] %= MOD;
                }
                if (j + 1 < len){ 
                    dp[i][j] += dp[i-1][j+1]; 
                    dp[i][j] %= MOD; 
                }
            }
        }
        return dp[steps][0];
    }
}

Find the Smallest Divisor Given a Threshold

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:

Input: nums = [19], threshold = 5
Output: 4

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^6
• nums.length <= threshold <= 10^6

算法思路：

​ 记cal(x)为以x为除数，数组里每个数除以x的累加和，易知cal(x)是一个单调递减函数，可以利用函数的单调性，用二分法快速定位x大小。

class Solution{
    public int smallestDivisor(int[] nums, int threshold){
        int lo = 1, hi = 1000000;

        while (lo < hi){
            int mid = (lo + hi) >> 1;
            int result = cal(nums, mid);
            
            if(result > threshold)
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo;
    }
    
    private int cal(int[] nums, int div){
        int sum = 0;
        for(int n : nums){
            sum += Math.ceil((double)n / (double)div);  // 向上取整
            //if(n % div != 0) sum += 1;
        }
        return (int)sum;
    }
}

Longest Palindrome

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

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

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

Example:

Input:
"abccccdd"

Output:
7

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

题意：用题目中所给字符串中的字符，求可以生成的最长回文串的长度。

算法思路：

1. 利用字符哈希方法统计字符创中所有字符的数量
2. 设最长回文字符串偶数长度为max_length = 0
3. 设置是否有中心点标记flag = 0
4. 遍历每一个字符，字符数为count，若count为偶数max_length += count，若count为奇数，max_length += count - 1, f1ag = 1

• 最终最长回文字串长度为max_length + flag

class Solution {
public:
    int longestPalindrome(std::string s) {
    	int char_map[128] = {0};
    	int max_length = 0;
    	int flag = 0;
    	for (int i = 0; i < s.length(); i++){
	    	char_map[s[i]]++;
	    }
	    for (int i = 0; i < 128; i++){
    		if (char_map[i] % 2 == 0){
		    	max_length += char_map[i];
		    }
		    else{
    			max_length += char_map[i] - 1;
    			flag = 1;
    		}
    	}
    	return max_length + flag;
    }
};

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

[
   [5,4,11,2],
   [5,8,4,5]
]

题意：给定一个二叉树与整数sum，找出所有的从根节点到野子节点的路径，这些路径上的节点的和为sum。

解题思路：

1. 从根节点深度优先遍历二叉树，先序遍历时将该节点值存储至path栈中，使用path_value累加节点值；
2. 当遍历至叶节点是，检查path_value的值是否为sum，若为sum，将pathpush进入result中；
3. 在后续遍历时，将该节点从path栈中弹出，path_valut减去节点值。

class Solution{
public:
    std::vector<std::vector<int>> pathSum(TreeNode* root, int sum){
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        int path_value = 0;
        preorder(root, path_value, sum, path, result);
        return result;
    }

private:
    void preorder(TreeNode* node, int &path_value,
            int sum, std::vector<int> &path, std::vector<std::vector<int>> &result){
        if(!node){
            return;
        }
        path_value += node -> val;
        path.push_back(node -> val);
        if(!node -> left && !node -> right && path_value == sum){
            result.push_back(path);
        }
        preorder(node -> left, path_value, sum, path, result);
        preorder(node -> right, path_value, sum, path, result);
        path_value -= node -> val;
        path.pop_back();
    }
};

Find Positive Integer Solution for a Given Equation

Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly increasing, i.e.:

• f(x, y) < f(x + 1, y)
• f(x, y) < f(x, y + 1)

The function interface is defined like this:

interface CustomFunction {
public:
  // Returns positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};

For custom testing purposes you're given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you'll know only two functions from the list.

You may return the solutions in any order.

Example 1：

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Example 2：

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y

Constraints:

• 1 <= function_id <= 9
• 1 <= z <= 100
• It's guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
• It's also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000

题意：找出所有符合f(x, y) = z的[x, y]

算法思路：

1. 设置左指针left和右指针right，左指针指向1，右指针指向1000；
2. 循环判断f(left, right)是否等于z；
   • 如果等于，则将[left, right]push进最终的结果中；
   • 否则如果f(left, right) > z则right--；
     • 如果f(left, right) < z则left++；

利用双指针遍历一遍即可找出所有符合条件的[x, y],时间复杂度为O(n)。

/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 * public:
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     int f(int x, int y);
 * };
 */

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        std::vector<std::vector<int>> result;
        int left = 1, right = 1000;
        while(left <= 1000 && right >= 1){
            int ans = customfunction.f(left, right);
            if(ans == z){
                std::vector<int> temp;
                temp.push_back(left);
                temp.push_back(right);
                result.push_back(temp);
                left++;
            }
            else if(ans > z){
                right--;
            }
            else{
                left++;
            }
        }
        return result;
    }
};

Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

• Only one letter can be changed at a time.
• Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

算法思路：

1. 单词和单词之间的转换可以理解为一张图，图的定点为单词，若两个单词之间可以相互转换，则这两个单词代表的定点之间有一条边，题目求的是从beginword到endword的最短路径；
2. 使用map构造邻接表所表示的图，map定义为以string为key，vector<string>为value，将beginwordpush进wordlist，遍历wordlist，对任意两个单词，若它们只差一个字母，则将其相连；

bool connect(const std::string &word1, const std::string &word2){
    int cnt = 0;
    for(int i = 0; i < word1.size(); i++){
        if(word1[i] != word2[i]){
            cnt++;
        }
    }
    return cnt == 1;
}

void construct_graph(std::string &beginWord, std::vector<std::string> &wordList,
                     std::map<std::string, std::vector<std::string>> &graph){
    wordList.push_back(beginWord);
    for(int i = 0; i < wordList.size(); i++){
        graph[wordList] = std::vector<std::string>();
    }
    for(int i = 0; i < wordList.size(); i++){
        for(int j = i + 1; j < wordList.size(); j++){
            if(connect(wordList[i], wordList[j])){
                graph[wordList[i]].push_back(wordList[j]);
                graph[wordList[j]].push_back(wordList[i]);
            }
        }
    }
}

3. 设置搜索队列Q，队列节点为pair<定点，步数>；设置集合visit，记录搜索过的节点；将<beginWord, 1> 添加至队列；
4. 只要队列不空；取出队头元素：
   • 若取出的队头元素是endword，返回到达当前节点的步数；
   • 否则拓展该节点，将与该节点相连且未添加到visit中的节点与步数同时添加的到队列Q，并将拓展节点加入viist；
5. 若最终都无法到达endword则返回0；

int BFS_graph(std::string &beginWord, std::string &endWord,
              std::map<std::string, std::vector<std::string>> &graph){
    std::queue<std::pair<std::string, int>> Q;
    std::set<std::string> visit;
    Q.push(std::make_pair(beginWord, 1));
    visit.insert(beginWord);
    while(!Q.empty()){
        std::string node = Q.front().first;
        int step = Q.front().second;
        Q.pop();
        if(node == endWord){
            return step;
        }
        const std::vector<std::string> &neighbors = graph[node];
        for(int i = 0; i < neighbors.size(); i++){
            if(visit.find(neighbors[i]) == visit.end()){
                Q.push(std::make_pair(neighbors[i], step + 1));
                visit.insert(neighbors[i]);
            }
        }
    }
    return 0;
}

class Solution{
public:
    int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
        std::map<std::string, std::vector<std::string>> graph;
        construct_graph(beginWord, wordList, graph);
        return BFS_graph(beginWord, endWord, graph);
    }
};

Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

Note:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

算法思路：

1. 用动态规划来进行推导，dp[i][j]代表至少要有多少血生命才能到达[i,j]还活着.
2. 从右下往左上推导设dp_min = min(dp[i-1][j], dp[i][j-1])，dp[i][j] = max(1, dp_min - dungeon[i][j])

class Solution{
public:
    int calculateMinimumHP(std::vector<std::vector<int>> &dungeon){
        if(dungeon.size() == 0){
            return 0;
        }

        std::vector<std::vector<int>> dp(dungeon.size(), std::vector<int>(dungeon[0].size(), 0));
        int row = dungeon.size();
        int column = dungeon[0].size();
        dp[row - 1][column - 1] = std::max(1, 1 - dungeon[row - 1][column - 1]);
        for(int i = column - 2; i >= 0; i--){
            dp[row - 1][i] = std::max(1, dp[row - 1][i + 1] - dungeon[row - 1][i]);
        }
        for(int i = row - 2; i >= 0; i--){
            dp[i][column - 1] = std::max(1, dp[i + 1][column - 1] - dungeon[i][column - 1]);
        }
        for(int i = row - 2; i >= 0; i--){
            for(int j = column - 2; j >= 0; j--){
                int dp_min = std::min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = std::max(1, dp_min - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

class Solution{
    public int countSquares(int[][] matrix){
        int m = matrix.length;
        int n = matrix[0].length;
        int ans = 0;
        int[][] dp = new int[m][n];

        for(int i = 0; i < m; i++){
            ans += dp[i][0] = matrix[i][0];
        }
        for(int i = 0; i < n; i++){
            ans += dp[0][i] = matrix[0][i];
        }

        if(matrix[0][0] == 1){
            ans--;
        }

        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 1) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    ans += dp[i][j];
                }
            }
        }

        return ans;
    }
}

5263. Shift 2D Grid

Easy

Given a 2D grid of size n * m and an integer k. You need to shift the grid k times.

In one shift operation:

• Element at grid[i][j] becomes at grid[i][j + 1].
• Element at grid[i][m - 1] becomes at grid[i + 1][0].
• Element at grid[n - 1][m - 1] becomes at grid[0][0].

Return the 2D grid after applying shift operation k times.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:

• 1 <= grid.length <= 50
• 1 <= grid[i].length <= 50
• -1000 <= grid[i][j] <= 1000
• 0 <= k <= 100

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        if(k == 0){
            return grid;
        }
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> result(n, vector<int>(m, 0));
        for(int cnt = 0; cnt < k; cnt++){
            for(int i = 0; i < n; i++){
                for(int j = 1; j < m; j++){
                    result[i][j] = grid[i][j - 1];
                }
            }
            for(int i = 1; i < n; i++){
                result[i][0] = grid[i - 1][m - 1];
            }
            result[0][0] = grid[n - 1][m - 1];
            grid = result;
        }
        return result;
    }
};

5264. Find Elements in a Contaminated Binary Tree

Medium

Given a binary tree with the following rules:

1. root.val == 0
2. If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
3. If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

• FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
• bool find(int target) Return if the target value exists in the recovered binary tree.

Example 1:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]
Explanation
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True 

Example 2:

Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output
[null,true,true,false]
Explanation
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

Example 3:

Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output
[null,true,false,false,true]
Explanation
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

Constraints:

• TreeNode.val == -1
• The height of the binary tree is less than or equal to 20
• The total number of nodes is between [1, 10^4]
• Total calls of find() is between [1, 10^4]
• 0 <= target <= 10^6

5265. Greatest Sum Divisible by Three

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).。

Constraints:

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

5266. Minimum Moves to Move a Box to Their Target Location

Hard

Storekeeper is a game, in which the player pushes boxes around in a warehouse, trying to get them to target locations.

The game is represented by a grid of size n*``m, where each element is a wall, floor or a box.

Your task is move the box 'B' to the target position 'T' under the following rules:

• Player is represented by character 'S' and can move up, down, left, right in the grid if its a floor (empy cell).
• Floor is represented by character '.' that means free cell to walk.
• Wall is represented by character '#' that means obstacle (impossible to walk there).
• There is only one box 'B' and one target cell 'T' in the grid.
• The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
• The player cannot walk through the box.

Return the minimum number of pushes to move the box to the target. If there is no way to reach the target, return -1.

Example 1:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3
Explanation: We return only the number of times the box is pushed.

Example 2:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#","#","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: -1

Example 3:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T",".",".","#","#"],
               ["#",".","#","B",".","#"],
               ["#",".",".",".",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 5
Explanation:  push the box down, left, left, up and up.

Example 4:

Input: grid = [["#","#","#","#","#","#","#"],
               ["#","S","#",".","B","T","#"],
               ["#","#","#","#","#","#","#"]]
Output: -1

Constraints:

• 1 <= grid.length <= 20
• 1 <= grid[i].length <= 20
• grid contains only characters '.', '#', 'S' , 'T', or 'B'.
• There is only one character 'S', 'B' and 'T' in the grid.

Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

struct Qitem{
    std::string node;
    int parent_pos;
    int step;
    Qitem(std::string _node, int _parent_pos, int _step): node(_node), parent_pos(_parent_pos), step(_step){}
};

class Solution{
public:
    std::vector<std::vector<std::string>> findLadders(std::string beginWord,
                                                      std::string endWord, std::vector<std::string> &wordList){
        std::map<std::string, std::vector<std::string>> graph;
        construct_graph(beginWord, wordList, graph);
        std::vector<Qitem> Q;
        std::vector<int> end_word_pos;
        BFS_graph(beginWord, endWord, graph, Q, end_word_pos);
        std::vector<std::vector<std::string>> result;
        for(int i = 0; i < end_word_pos.size(); i++){
            int pos = end_word_pos[i];
            std::vector<std::string> path;
            while(pos != -1){
                path.push_back(Q[pos].node);
                pos = Q[pos].parent_pos;
            }
            result.push_back(std::vector<std::string>());
            for(int j = path.size() - 1; j >= 0; j--){
                result[i].push_back(path[j]);
            }
        }
        return result;
    }
private:
    void BFS_graph(std::string &beginWord, std::string &endWord,
                   std::map<std::string, std::vector<std::string>> &graph,
                   std::vector<Qitem> &Q, std::vector<int> &end_word_pos){
        std::map<std::string, int> visit;
        int min_step = 0;
        Q.push_back(Qitem(beginWord, -1, 1));
        visit[beginWord] = 1;
        int front = 0;
        while(front != Q.size()){
            const std::string &node = Q[front].node;
            int step = Q[front].step;
            if(min_step != 0 && step > min_step){
                break;
            }
            if(node == endWord){
                min_step = step;
                end_word_pos.push_back(front);
            }
            const std::vector<std::string> &neighbors = graph[node];
            for(int i = 0; i < neighbors.size(); i++){
                if(visit.find(neighbors[i]) == visit.end() || visit[neighbors[i]] == step + 1){
                    Q.push_back(Qitem(neighbors[i], front, step + 1));
                    visit[neighbors[i]] = step + 1;
                }
            }
            front++;
        }
    }
    bool connect(const std::string &word1, const std::string &word2){  // 判断 word1 word2 是否可以转化
        int cnt = 0;
        for(int i = 0; i < word1.length(); i++){
            if(word1[i] != word2[i]){
                cnt++;
            }
        }
        return cnt == 1;
    }

    void construct_graph(std::string &beginWord, std::vector<std::string> &wordList,
                         std::map<std::string, std::vector<std::string>> &graph){
        int has_begin_word = 0;
        for(int i = 0; i < wordList.size(); i++){
            if(wordList[i] == beginWord){
                has_begin_word = 1;
            }
            graph[wordList[i]] = std::vector<std::string>();
        }
        for(int i = 0; i < wordList.size(); i++){
            for(int j = i + 1; j < wordList.size(); j++){
                if(connect(wordList[i], wordList[j])){
                    graph[wordList[i]].push_back(wordList[j]);
                    graph[wordList[j]].push_back(wordList[i]);
                }
            }
            if(has_begin_word == 0 && connect(beginWord, wordList[i])){
                graph[beginWord].push_back(wordList[i]);
            }
        }
    }
};

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分析：将求n个数的数组的最大子段和转化为分别求出以第1个、第2个...第n个数字结尾的最大子段和，再找出这n结果中最大的，即为结果。

算法思路：

1. dp[i]为以第i个数字结尾的最大子段和；
2. 若dp[i-1] > 0则dp[i] = dp[i-1] + nums[i]，否则dp[i] = nums[i];
3. 边界值dp[0] = nums[0]。

class Solution{
public:
    int maxSubArray(std::vector<int> &nums){
        std::vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int max_res = dp[0];
        for(int i = 1; i < nums.size(); i++){
            dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
            if(max_res < dp[i]){
                max_res = dp[i];
            }
        }
        return max_res;
    }
};

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

算法思路：

方法一：

1. 前序遍历二叉树，将节点指针push进入vector；
2. 顺序遍历vector中的节点，将前面的节点的左指针置空，右指针与后面的节点相连。

该方法可以通过题目，但是不满足in-place的条件。

class Solution{
public:
    void flatten(TreeNode* root){
        std::vector<TreeNode*> node_vec;
        preorder(root, node_vec);
        for(int i = 1; i < node_vec.size(); i++){
            node_vec[i - 1] -> left = NULL;
            node_vec[i - 1] -> right = node_vec[i];
        }
    }

private:
    void preorder(TreeNode* node, std::vector<TreeNode*> &node_vec){
        if(!node){
            return;
        }
        node_vec.push_back(node);
        preorder(node -> left, node_vec);
        preorder(node -> right, node_vec);
    }
};

方法二：

1. 从下往上，将每个节点的右子树放到左子树的最右节点；
2. 将左子树放到右子树，并将左子树置空。

class Solution{
public:
    void flatten(TreeNode* root){
        TreeNode* last = NULL;
        preorder(root, last);
    }

private:
    void preorder(TreeNode* node, TreeNode* &last){
        if(!node){
            return;
        }
        if(!node -> left && !node -> right){
            last = node;
            return;
        }
        TreeNode* left = node -> left;
        TreeNode* right = node -> right;
        TreeNode* left_last = NULL;
        TreeNode* right_last = NULL;
        if(left){
            preorder(left, left_last);
            node -> left = NULL;
            node -> right = left;
            last = left_last;
        }
        if(right){
            preorder(right, right_last);
            if(left_last){
                left_last -> right = right;
            }
            last = right_last;
        }
    }
};

Course Schedule

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

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

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

Example 1:

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

Example 2:

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

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

题意：已知有n个课程，标记从0到n-1，课程之间是有依赖关系的，已知n个课程的依赖关系，求是否可以将n个课程全部完成。

分析：将课程看做顶点，课程见的依赖关系看成有向边，构造有向图；如果图中无环，则可以完成全部课程，否则不能。

方法一：

算法思路：

1. 在深度优先搜索时，如果正在搜索某一顶点，又回到了该顶点，即证明图有环。

struct GraphNode{
    int label;
    std::vector<GraphNode*> neighbors;
    GraphNode(int x): label(x){}
};

bool DFS_graph(GraphNode* node, std::vector<int> &visit){
    visit[node -> label] = 0;
    for(int i = 0; i < node -> neighbors.size(); i++){
        if(visit[node -> neighbors[i] -> label] == -1){
            if(DFS_graph(node -> neighbors[i], visit) == 0){
                return false;
            }
        }
        else if(visit[node -> neighbors[i] -> label] == 0){
            return false;
        }
    }
    visit[node -> label] = 1;
    return true;
}

class Solution{
public:
    bool canFinish(int numCourse, std::vector<std::vector<int>> &prequisites){
        std::vector<GraphNode*> graph;
        std::vector<int> visit;
        for(int i = 0; i < numCourse; i++){
            graph.push_back(new GraphNode(i));
            visit.push_back(-1);
        }
        for(int i = 0; i < prequisites.size(); i++){
            GraphNode* begin = graph[prequisites[i][1]];
            GraphNode* end = graph[prequisites[i][0]];
            begin -> neighbors.push_back(end);
        }
        for(int i = 0; i < graph.size(); i++){
            if(visit[i] == -1 && !DFS_graph(graph[i], visit)){
                return false;
            }
        }
        for(int i = 0; i < numCourse; i++){
            delete graph[i];
        }
        return true;
    }
};

方法二：

算法思路：

1. 在宽度优先搜索是，只将入度为0的点添加至队列；
2. 当完成一个顶点的搜索后，它指向的所有顶点的入度都减一；
3. 若此时某顶点入度为0则添加至队列；
4. 完成搜索后，若所有的顶点入度都为0，则无环，否自有环。

struct GraphNode{
    int label;
    std::vector<GraphNode*> neighbors;
    GraphNode(int x): label(x){}
};

class Solution{
public:
    bool canFinish(int numCourse, std::vector<std::vector<int>> &prerequisites){
        std::vector<GraphNode*> graph;
        std::vector<int> degree;
        for(int i = 0; i < numCourse; i++){
            degree.push_back(0);
            graph.push_back(new GraphNode(i));
        }
        for(int i = 0; i < prerequisites.size(); i++){
            GraphNode* begin = graph[prerequisites[i][1]];
            GraphNode* end = graph[prerequisites[i][0]];
            begin -> neighbors.push_back(end);
            degree[prerequisites[i][0]]++;
        }
        std::queue<GraphNode*> Q;
        for(int i = 0; i < numCourse; i++){
            if(degree[i] == 0){
                Q.push(graph[i]);
            }
        }
        while(!Q.empty()){
            GraphNode* node = Q.front();
            Q.pop();
            for(int i = 0; i < node -> neighbors.size(); i++){
                degree[node -> neighbors[i] -> label]--;
                if(degree[node -> neighbors[i] -> label] == 0){
                    Q.push(node -> neighbors[i]);
                }
            }
        }
        for(int i = 0; i < graph.size(); i++){
            delete graph[i];
        }
        for(int i = 0; i < degree.size(); i++){
            if(degree[i]){
                return false;
            }
        }
        return true;
    }
};

Find Winner on a Tic Tac Toe Game

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (" ").
• The first player A always places "X" characters, while the second player B always places "O" characters.
• "X" and "O" characters are always placed into empty squares, never on 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.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return "Draw", if there are still movements to play return "Pending".

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X "
" O "
" "

Constraints:

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= moves[i][j] <= 2
• There are no repeated elements on moves.
• moves follow the rules of tic tac toe.

算法思路：

1. 一共只有九个格子，并且赢面是固定的，可以使用一个9位二进制代表最后棋盘的结果，规定：井字形棋盘的[i,j]代表二进制数的第3*i + j位，没走一步棋等价于与对应的位进行异或运算。
2. 将一方的数字与能获胜的数字k进行与运算，如果结果为k，则此方获胜，若双方都未获胜则：
   • 若总步数为9步，则平局；
   • 否则，未完成；
3. 赢面数字只有8种分别是7, 56, 448, 73, 146, 292, 273, 84

public String tictactoe(int[][] moves) {
    int a = 0, b = 0, len = moves.length;

    int[] ac =  {7, 56, 448, 73, 146, 292, 273, 84};
    for(int i = 0; i < len; i++){
        if((i & 1) == 1){
            b ^= 1 << (3 * moves[i][0] + moves[i][1]);
        }else{
            a ^= 1 << (3 * moves[i][0] + moves[i][1]);
        }
    }

    for(int i : ac){
        if((a & i) == i){
            return "A";
        }
        if((b & i) == i){
            return "B";
        }
    }
    return len == 9 ? "Draw" : "Pending";
}

Encode Number

Given a non-negative integer num, Return its encoding string.

The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:

Example 1:

Input: num = 23
Output: "1000"

Example 2:

Input: num = 107
Output: "101100"

Constraints:

• 0 <= num <= 10^9

算法思路：将num+1转化为二进制后删去第一位，以字符串的格式输出。

class Solution {
public:
    string encode(int num) {
        num += 1;
        string str = "";
        while(num){
            str += to_string(num % 2);
            num /= 2;
        }
        string result  = "";
        for(int i = str.size() - 2; i > 0; i--){
            result += str[i];
        }
        return result;
    }
};

Number of Burgers with No Waste of Ingredients

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

• Jumbo Burger: 4 tomato slices and 1 cheese slice.
• Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

Example 1:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]
Explantion: To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input: tomatoSlices = 17, cheeseSlices = 4
Output: []
Explantion: There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input: tomatoSlices = 4, cheeseSlices = 17
Output: []
Explantion: Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input: tomatoSlices = 0, cheeseSlices = 0
Output: [0,0]

Example 5:

Input: tomatoSlices = 2, cheeseSlices = 1
Output: [0,1]

Constraints:

• 0 <= tomatoSlices <= 10^7
• 0 <= cheeseSlices <= 10^7

class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        List<Integer> result = new ArrayList<>();
        if(tomatoSlices > 4 * cheeseSlices || tomatoSlices < 2 * cheeseSlices || tomatoSlices % 2 != 0){
            return result;
        }

        int bigBurgers = tomatoSlices / 2 - cheeseSlices;
        int smallBurgers = 2 * cheeseSlices - tomatoSlices / 2;
        result.add(bigBurgers);
        result.add(smallBurgers);
        return result;
    }
}

Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

题意：已知一组字符串，将所有由颠倒的字母顺序构成的字放到一起输出。

算法思路：

方法一：

哈希表以内部进行排序的各个单词为key，以字符串向量为value，存储各个字符数量相同的字符串。

• 设置字符串到字符串向量的哈希表anagram，便利字符串向量strs中的单词strs[i]:
  • 设置临时变量str = strs[i]，对str进行排序。
  • 若str未出现在anagram中，设置str到一个空字符串向量的映射。
  • 将str[i]添加至字符串向量anagram[str]中。
• 遍历哈希表anagram，将全部key对应的value push进最终结果中。

class Solution{
public:
    std::vector<std::vector<std::string>> groupAnagrams(
            std::vector<std::string>& strs){
        std::map<std::string, std::vector<std::string>> anagram;
        std::vector<std::vector<std::string>> result;
        for(int i = 0; i < strs.size(); i++){
            std::string str = strs[i];
            std::sort(str.begin(), str.end());
            if(anagram.find(str) == anagram.end()){
                std::vector<std::string> item;
                anagram[str] = item;
            }
            anagram[str].push_back((strs[i]));
        }
        std::map<std::string, std::vector<std::string>> :: iterator it;
        for(it = anagram.begin(); it != anagram.end(); it++){
            result.push_back((*it).second);
        }
        return result;
    }
};

方法二：

哈希表以26个字母的字符数量为key，以字符串向量为value，存储各个字符数量相同的字符串。

• 设置vector到字符串向量的哈希表anagram，遍历字符串向量strs中的单词trs[i]:
  • 统计strs[i]中的各个字符数量，存储至vec。
  • 若vec未出现在anagram中，设置一个vec到一个空字符串向量的映射。
  • 将strs[i]添加到字符串向量anagram[vec]中。
• 便利哈希表anagram，将全部key对应的value push进最终的结果中。

void change_to_vector(std::string &str, std::vector<int> &vec){
    for(int i = 0; i < 26; i++) {
        vec.push_back(0);
    }
    for(int i = 0; i < str.length(); i++) {
        vec[str[i] - 'a']++;
    }
}

class Solution{
public:
    std::vector<std::vector<std::string>> groupAnagrams(
            std::vector<std::string>& strs){
        std::map<std::vector<int>, std::vector<std::string>> anagram;
        std::vector<std::vector<std::string>> result;
        for(int i = 0; i < strs.size(); i++){
            std::vector<int> vec;
            change_to_vector(strs[i], vec);
            if(anagram.find(vec) == anagram.end()){
                std::vector<std::string> item;
                anagram[vec] = item;
            }
            anagram[vec].push_back(strs[i]);
        }
        std::map<std::vector<int>, std::vector<std::string>> :: iterator it;
        for(it = anagram.begin(); it != anagram.end(); it++){
            result.push_back((*it).second);
        }
        return result;
    }
};

Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:

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

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Note:

1. The length sum of the given matchsticks is in the range of 0 to 10^9.
2. The length of the given matchstick array will not exceed 15.

class Solution {

    public boolean makesquare(int[] nums) {
        if(nums.length < 4){
            return false;
        }
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }

        if(sum % 4 != 0){
            return false;
        }

        Integer[] list = new Integer[nums.length];

        for(int i = 0; i < nums.length; i++) list[i] = nums[i];
        Arrays.sort(list);
        for(int i = 0; i < nums.length; i++) nums[i] = list[i];

        int[] bucket = new int[]{0 , 0 , 0 , 0};;
        return generate(0, nums, sum / 4, bucket);
    }

    public boolean generate(int i, int[] nums, int target, int[] bucket){
        if(i >= nums.length){
            return bucket[0] == target && bucket[1] == target && bucket[2] == target && bucket[3] == target;
        }
        for(int j = 0; j < 4; j++){
            if(bucket[j] + nums[i] > target){
                continue;
            }
            bucket[j] += nums[i];
            if(generate(i + 1, nums, target, bucket)){
                return true;
            }
            bucket[j] -= nums[i];
        }
        return false;
    }
}

5108. Encode Number

Medium

Given a non-negative integer num, Return its encoding string.

The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:

Example 1:

Input: num = 23
Output: "1000"

Example 2:

Input: num = 107
Output: "101100"

Constraints:

• 0 <= num <= 10^9

class Solution {
public:
    string encode(int num) {
        num += 1;
        string str = "";
        while(num){
            str += to_string(num % 2);
            num /= 2;
        }
        string result  = "";
        for(int i = str.size() - 2; i > 0; i--){
            result += str[i];
        }
        return result;
    }
};

5109. Smallest Common Region

Medium

You are given some lists of regions where the first region of each list includes all other regions in that list.

Naturally, if a region X contains another region Y then X is bigger than Y.

Given two regions region1, region2, find out the smallest region that contains both of them.

If you are given regions r1, r2 and r3 such that r1 includes r3, it is guaranteed there is no r2 such that r2 includes r3.

It's guaranteed the smallest region exists.

Example 1:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

Constraints:

• 2 <= regions.length <= 10^4
• region1 != region2
• All strings consist of English letters and spaces with at most 20 letters.

5110. Synonymous Sentences

Medium

Given a list of pairs of equivalent words synonymsand a sentencetext .

Example 1:

Input:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
Output:
["I am cheerful today but was sad yesterday",
"I am cheerful today but was sorrow yesterday",
"I am happy today but was sad yesterday",
"I am happy today but was sorrow yesterday",
"I am joy today but was sad yesterday",
"I am joy today but was sorrow yesterday"]

Constraints:

• 0 <= synonyms.length <= 10
• synonyms[i].length == 2
• synonyms[0] != synonyms[1]
• All words consist of at most 10 English letters only.
• text is a single space separated sentence of at most 10 words.

5125. Handshakes That Don't Cross

Hard

You are given an even number of people num_people that stand around a circle and each person shakes hands with someone else, so that there are num_people / 2 handshakes total.

Return the number of ways these handshakes could occur such that none of the handshakes cross.

Since this number could be very big, return the answer mod 10^9 + 7

Example 1:

Input: num_people = 2
Output: 1

Example 2:

Input: num_people = 4
Output: 2
Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].

Example 3:

Input: num_people = 6
Output: 5

Example 4:

Input: num_people = 8
Output: 14

Constraints:

• 2 <= num_people <= 1000
• num_people % 2 == 0

Shift 2D Grid

Given a 2D grid of size n * m and an integer k. You need to shift the grid k times.

In one shift operation:

• Element at grid[i][j] becomes at grid[i][j + 1].
• Element at grid[i][m - 1] becomes at grid[i + 1][0].
• Element at grid[n - 1][m - 1] becomes at grid[0][0].

Return the 2D grid after applying shift operation k times.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Example 2:

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
Output: [[1,2,3],[4,5,6],[7,8,9]]

Constraints:

• 1 <= grid.length <= 50
• 1 <= grid[i].length <= 50
• -1000 <= grid[i][j] <= 1000
• 0 <= k <= 100

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        if(k == 0){
            return grid;
        }
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> result(n, vector<int>(m, 0));
        for(int cnt = 0; cnt < k; cnt++){
            for(int i = 0; i < n; i++){
                for(int j = 1; j < m; j++){
                    result[i][j] = grid[i][j - 1];
                }
            }
            for(int i = 1; i < n; i++){
                result[i][0] = grid[i - 1][m - 1];
            }
            result[0][0] = grid[n - 1][m - 1];
            grid = result;
        }
        return result;
    }
};

Group the People Given the Group Size They Belong To

There are n people whose IDs go from 0 to n - 1 and each person belongs exactly to one group. Given the array groupSizes of length n telling the group size each person belongs to, return the groups there are and the people's IDs each group includes.