领扣刷题笔记（C++ Difficulty：Medium）

注：C++兼容C的输入输出，会增大IO开销，可以添加以下代码提高IO效率

static const auto init = []() {
    /*
     *关掉c++中iostream和c中cstdio流的同步（cout和printf，cin和scanf）
     *关掉后不能同时使用c和c++的输入输出；
     */
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);//完成cin和cout的解耦，减少大量的缓冲区刷新操作
    return nullptr;
}();

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路：

对集合的每一个元素进行迭代，迭代时，我们保留原来的子集，并在原来的子集后面加入新的元素，之后再加入集合
迭代过程如下
[] -> 1 -> [1]
[] [1] -> 2 -> [2] [1,2]
[] [1] [2] [1,2] -> 3 -> [3] [1,3] [2,3] [1,2,3]
[] [1] [2] [1,2] [3] [1,3] [2,3] [1,2,3]

解答：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> tmp;
        result.push_back(tmp);
        int len = nums.size();
        for(int i =0; i < len; ++i){
            int resLen = result.size();
            for(int j=0; j < resLen; ++j){
                vector<int> tmp = result[j];
                tmp.push_back(nums[i]);
                result.push_back(tmp);
            }
        }
        return result;
    }
};

201. Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: [5,7]
Output: 4
Example 2:
Input: [0,1]
Output: 0

解题思路：

通过观察可以知道5的二进制为101，6的二进制为110，7的二进制为111，输出4的二进制为100，可以发现，只要找到二进制的左边公共部分即可。
可以先建立一个32位都是1的mask，然后每次左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与即得最终结果。

解答：

//方法1
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        unsigned int mask = UINT_MAX;
        while ((m & mask) != (n & mask)) {
            mask <<= 1;
        }
        return mask & m;
    }
};
//方法2
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int cnt = 0;
        while(m!= n){
            m>>=1;
            n>>=1;
            ++cnt;
        }
        return m<<cnt;
    }
};

807. Max Increase to Keep City Skyline

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.
At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.
What is the maximum total sum that the height of the buildings can be increased?
Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation:

The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]
The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]
The grid after increasing the height of buildings without affecting skylines is:
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

• 1 < grid.length = grid[0].length <= 50.
• All heights grid[i][j] are in the range [0, 100].
• All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

解题思路：

• 遍历grid获取skyline数值存入到col和row中；
• 遍历grid，利用col和row中最小的skyline值来计算最大增量，最后得出结果；

解答：

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
    int len = grid.size();
    int result = 0;
    vector<int> col(len, 0), row(len, 0);
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            row[i] = max(row[i], grid[i][j]);
            col[j] = max(col[j], grid[i][j]);
        }
    }
    for (int i = 0; i < len; ++i)
        for (int j = 0; j < len; ++j)
            result += min(row[i], col[j]) - grid[i][j];
    return result;
}
};

957. Prison Cells After N Days

There are 8 prison cells in a row, and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• Otherwise, it becomes vacant.
  (Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)
  We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.
  Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)
  Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

1. cells.length == 8
2. cells[i] is in {0, 1}
3. 1 <= N <= 10^9

解题思路：

暂时超出时间限制

解答

//超出时间限制
class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        vector<int> tmp(8,0);
        for(int d = 0; d < N; ++d)
        {
            for(int i = 1; i < 7; ++i)
            {
                if(cells[i-1] == cells[i+1])
                    tmp[i] = 1;
                else tmp[i] = 0;
            }
            cells = tmp;
        }
        return cells;
    }
};

待更新