刷题笔记

作者: 毒死预言家的女巫 | 来源:发表于2020-03-11 22:44 被阅读0次

最近在准备面试，发现自己真的菜的不行，就计划接下来的时间把 leetcode 上面刷的 中等题 和 每日一题做个简书笔记。稍微记录一下，等保研时或许还有用。

旋转图像
题目：给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

说明：给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

思路：可以先沿着反对角线转一次，再从中间转一次。

class Solution {

    //解题思路：先沿着对角线转一次，再沿着水平线转一次
    public void rotate(int[][] matrix) {
        for(int i =  0; i < matrix.length; i++){
            for(int j = 0; j <matrix.length - i ; j++){
                swap(matrix,i,j,matrix.length-1-j,matrix.length-1-i);
            }
        }
        for(int i =  0; i < matrix.length/2; i++){
            for(int j = 0; j <matrix.length; j++){
                swap(matrix,i,j,matrix.length-1-i,j);
            }
        }
    }

    //swap element i and j
    public void swap(int matrix[][],int ix,int iy,int jx,int jy){
        int temp = matrix[ix][iy];
        matrix[ix][iy] = matrix[jx][jy];
        matrix[jx][jy] = temp;
    }
}

有效的数独：

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
输出：true

思路：

可以遍历三次 9*9 数组，分别判断是否符合三个要求
可以只遍历一次，访问每一个元素时判断三个要求是否被违背：可以用二进制位来表示一列 / 一行 / 一个 3*3的 Grid 中的状态，使用位操作更新。

class Solution {

    private final int VERTICAL = 0;
    private final int HORIZONTAL = 1;
    private final int GRID = 2;

    public boolean isValidSudoku(char[][] board) {
        int status[] = new int[27];//一列、一格、一行有九个状态，九个bit就够,总共27个。
        for(int i  = 0 ; i < 9; i ++){
            for(int j = 0; j < 9; j ++){
                if(board[i][j] !='.'){    
                    int n = board[i][j] - '0';
                    if(!checkAndSet(status, VERTICAL ,i, n)){
                        return false;
                    }
                    if(!checkAndSet(status, HORIZONTAL, j,n)){
                        return false;
                    }
                    if(!checkAndSet(status, GRID, (i/3) * 3 + (j/3), n)){
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /*
    * @param type : VERTICAL(从上到下), HORIZONTAL(从左到右)，GRID(3*3)
    * @param index : 这一类中的第 index 行/列/格子。 
    * @param num : 数字 1-9
    */
    public boolean checkAndSet(int status[], int type, int index, int num){
        int i = type * 9 + index;
        if((status[i] & (1 << (num-1))) == 0 ){
            status[i] = (status[i]^(1<<(num-1)));
            return true;
        }
        return false;
    }
}

这里使用了short，内存使用率为 9/16，可以换成int，会把内存使用率提高到 27/32。

跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

思想：将数组中分成“好位置”和“坏位置”，可以从好位置跳到最后而坏位置不可以；动态规划，从后向前(反过来也行)一格一格的试探好位置，并记录目前最靠前的好位置

    public boolean canJump(int[] nums) {
        int last = nums.length-1;//数组的最后一个位置一定是“好位置”
        for(int j = last-1; j >-1; --j){
            if(last - j <= nums[j]){
                last = j;
            }
        }
        if(last == 0){
            return true;
        }
        return false;
    }
}

第k个排列
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

输入: n = 3, k = 3
输出: "213"

class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> l = new ArrayList<>();
        l.add(1);
        int fac[] = new int[n];
        fac[0] = 1;
        for(int i = 1; i < n; i++){
            fac[i] = fac[i-1] * i; //初始化到一个数组中，运用动态规划。
            l.add(i+1);
        }
        StringBuilder builder = new StringBuilder("");
        k--;

        //观察序列，n = 3 的全排列，第一个数index是 (位置-1)/2 ,第二个数是(位置-1)/1,第三个数是(位置-1)/1，除数除了最后一项是1，符合n!,只需要维护一个数组，按照计算得到的idx从数组中取出并删除。
        for(int i = n-1; i >= 0; --i){    
            int idx = k / fac[i];
            k -= idx * fac[i];
            builder.append((char)(l.get(idx)+'0'));//要先强制转型，否则append会把后面的树作为int处理，得到4950这样的
            l.remove(idx);
        }
        return builder.toString();               
    }
}

多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

输入: [3,2,3]
输出: 3

我使用的解法是哈希映射的方法，太naive，不贴代码了，记录下官方十分强大的投票算法。

//如果我们把众数记为 +1+1，把其他数记为 -1−1，将它们全部加起来
//，显然和大于 0，从结果本身我们可以看出众数比其他数多。
class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这里的candidate可能不是众数，但是没有关系，由于众数占多数，在数组中总是可能出现count=0的时候，这时会重新选择候选人，其他人投出去的选票，总是会被众数投出去的抵消掉。

旋转链表：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

暴力的解法可以遍历列表k遍，每次将最后一个节点置于第一个，时间复杂度(k*n)。
更好的方法是：将首尾相连，将head相连，将head和last都向后挪动 n - k%n 位。


class Solution {

    public ListNode rotateRight(ListNode head, int k) {
        if(head==null ){
            return null;
        }
        ListNode l = head;  
        int n = 1;     
        while(l.next!=null){
           l = l.next; 
           n++;
        }    
        l.next = head;
        for(int i = 0; i < n - k%n; i++){ //注意这里要%n，否则k>n时出问题。
            head = head.next;
            l = l.next;
        }
        l.next = null;
        return head;
    }
}

不同路径

一道很典型的动态规划题，方程很好找。
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2

无障碍物版本：

class Solution {

    // len(x,y) = len(x+1,y) + len (x,y+1);
    // len (m, n-1) = 1;
    public int uniquePaths(int m, int n) {
        int res[][] = new int[m][n];
        res[m-1][n-1] = 1;
        for(int i = m -1 ; i >=0; --i){
            for(int j = n-1; j >=0; --j){
                if(j < n - 1){
                    res[i][j] += res[i][j+1];
                }
                if(i < m - 1){
                    res[i][j] += res[i+1][j];
                }
            }
        }
        return res[0][0];
    } 

}

障碍物版本

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int res[][] = new int[m][n];
        if(obstacleGrid[m-1][n-1] == 0){
           res[m-1][n-1] = 1;           
        }
        for(int i = m - 1 ; i >=0; --i){
            for(int j = n - 1; j >=0; --j){
                if(obstacleGrid[i][j] == 0){
                    if(j < n - 1){
                        res[i][j] += res[i][j+1];
                    }
                    if(i < m - 1){
                        res[i][j] += res[i+1][j];
                    }
                }
            }
        }
        return res[0][0];
    }
}

最短路径

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res[][] = new int[m][n];
        res[m-1][n-1] = grid[m-1][n-1];
        for(int i = m - 1 ; i >=0; --i){
            for(int j = n - 1; j >=0; --j){
                if(i == m-1 && j < n-1){
                    res[i][j] = res[i][j+1] +grid[i][j];
                }
                if(j == n-1 && i < m-1){
                    res[i][j] = res[i+1][j] + grid[i][j];
                }
                if(j < n - 1 && i < m-1){
                    res[i][j] = Math.min(res[i][j+1] ,res[i+1][j]) +grid[i][j];
                }           
            }
        }
        return res[0][0];
    }
}

简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：输入："/a/./b/../../c/"
输出："/c"

示例 5：
输入："/a/../../b/../c//.//"
输出："/c"

示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"

思路：使用LinkedList 模拟栈来简化路径

class Solution {
    LinkedList<String> list = new LinkedList<>();
    public String simplifyPath(String path) {
        String[] strs=path.split("/");
        for(String str: strs){
            if(str.equals("")||str.equals(".")){
                continue;
            }
            if(str.equals("..")){
                if(list.size()>0){
                    list.removeLast();
                }
            } else {
                list.addLast(str);
            }
        }
        StringBuilder sb= new StringBuilder("");
        if(list.size() == 0){
            return "/";
        }
        for(String str:list){
            sb.append("/");
            sb.append(str);
        }
        return sb.toString();
    }
}

拼写单词

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。
提示：

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
所有字符串中都仅包含小写英文字母

思路：限制了只会出现小写字母(连续)，那么我们可以去统计单词中每个字母出现的次数存在数组中，如果A单词中的每个字母的出现次数都小于等于B单词中的出现次数，可以认为是“掌握了”

class Solution {
    public int countCharacters(String[] words, String chars) {
        int chs[] = new int[26];
        for(char ch :chars.toCharArray()){
            chs[ch-'a']++;
        }
        int res = 0;
        for(String str:words){
            int s[] = new int[26];
            for(char ch : str.toCharArray()){
                s[ch-'a']++;
            }
            boolean f = false;
            for(int i = 0; i < 26; ++i){
                if(s[i] > chs[i]){
                    f = true;
                    break;
                }
            }
            if(!f){
                res+=str.length();
            }
        }
        return res;
    }
}

搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true

这个脑子就是得转一下，我死命想用两次二分法在两个维度上分别搜索，但是死活不行，看完力扣官方题解之后茅塞顿开。什么有序二维数组，从内存的角度上来看就是个有序的一维数组嘛！

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0){
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0;
        int high = m * n -1;
        int mid = (low+high)/2;
        while(low <= high){
            int val = matrix[mid/n][mid%n];
            if(val < target){
                low = mid + 1;
            } else if(val == target){
                return true;
            } else {
                high = mid - 1;
            }
            mid = (low+high)/2;
        }
        return false;
    }
}

颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

思路，桶排序。

class Solution {
    public void sortColors(int[] nums) {
        int colors[] = new int[3];
        for(int i =0; i< nums.length;++i){
            colors[nums[i]]++;
        }
        int j = 0;
        for(int i = 0; i < nums.length;++i){
            while( j < 3 && colors[j] == 0){
                j++;
            }
            if(j==3){
                break;
            }
            nums[i] = j;
            colors[j]--;
        }
    }
}

无重复最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路：使用动态规划，存放每一个字母最近出现的下标的下一位。使用一次扫描而结果就是在迭代过程中的 max(oldVal, 右指针-max(左指针,index[右指针所在字母]+1,)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int index[] = new int[256];//存放字母出现的下标的下一位，会随着扫描更新为最右的坐标，0表示还没出现过
        int res = 0;
        int i = 0;//左指针
        for(int j = 0; j < s.length(); ++j){
            i = Math.max(index[s.charAt(j)],i);//如果当前字母在i之后出现过，那么左指针就要更新到之前出现过位置的下一位，若没有出现，i不变。
            res = Math.max(res, j-i+1);// 更新一下res
            index[s.charAt(j)] = j+1;// 更新index
        } 
        return res;
    }
}

删除排序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length==0){
            return 0;
        } 
        int oldVal = nums[0];
        int res = 1;
        int j = 1;
        for(int i = 1; i < nums.length; ++i){
            if(oldVal!=nums[i]){
                j = 1;
                nums[res++] = nums[i]; 
                oldVal = nums[i];
            } else if(j < 2&&nums[i]==oldVal){
                nums[res++] = nums[i];
                j++;
            }
        }
        return res;
    }
}

最大子序和
考虑到有负数有正数，

极端情况，全是负数，那么就相当于找最小元素
如果只有一个正数，那么正数所在的大小为1的序列就是最大子序
可以考虑使用动态规划：
- 记录一个大小为n的数组，记录包含当前元素为子序列最后一个元素时的最大子序和。
- 如果之前的子序和大于0，那么当前的最大子序列和等于之前最大子序列和加上当前元素，否则就是当前元素。在迭代的过程中记录最大的子序列和。

class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length, maxSum = nums[0];
    for(int i = 1; i < n; ++i) {
      if (nums[i - 1] > 0) nums[i] += nums[i - 1];//原地修改
      maxSum = Math.max(nums[i], maxSum);//记录最大子序列和
    }
    return maxSum;
  }
}

二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/
2 3 <---
\
5 4 <---

思路：使用队列辅助广度优先遍历，记录树的深度。有一个无意间发现的小技巧，我在开始写的时候按照正常思路从左向右遍历子树，发现得到的是 二叉树的左视图，变换遍历顺序之后，得到了二叉树的右视图。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    class Pair{
        int depth;
        TreeNode n;
        Pair(TreeNode n, int depth){
            this.n = n;
            this.depth = depth;
        }
    }

    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        LinkedList<Pair> q = new LinkedList<>();
        q.addLast(new Pair(root,0)); 
        List<Integer> l = new ArrayList<>();
        int prevDepth = -1;
        while(!q.isEmpty()){
            Pair p = q.removeFirst();
            if(p.depth!=prevDepth){
                l.add(p.n.val);
            }
            
            if(p.n.right!=null){//先右子
                q.addLast(new Pair(p.n.right,p.depth+1));
            }
            if(p.n.left!=null){//再左子
                q.addLast(new Pair(p.n.left,p.depth+1));
            }
            prevDepth = p.depth;
        }
        return l;
    }
}

二维区域和检索 - 矩阵不可变

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。

图中子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

image

给定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

说明:

你可以假设矩阵不可变。
会多次调用 sumRegion 方法。
你可以假设 row1 ≤ row2 且 col1 ≤ col2。

思路：由于会调用多次sumRegion方法，一般的暴力解法会超时。
可以先计算所有(i,j)的 sumRegion(0,0,i,j) ，记为 s(i, j) , 则 $sumRegion(r_1, c_1, r_2, c_2) = s(r_2, c_2) - s(r_2,c_1) - s(r_1,c_2) + s(r_1 -1 , c_1 - 1)$

class NumMatrix {

    //注意这里的sumRegion会调用多次

    int sum[][];

    public NumMatrix(int[][] matrix) {
        if(matrix.length==0){
            return;
        } else {
            int m = matrix.length;
            int n = matrix[0].length;
            sum = new int[m+1][n+1];//sum下标从1开始，小 trick，
            for(int i = 0; i < m; ++i){
                for(int j= 0; j < n; ++j){
                    sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] + matrix[i][j] - sum[i][j];
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row1][col1] + sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1];
    }
}

01矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。给定的矩阵元素不超过10000个

两个相邻元素间的距离为 1 。

示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0

示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1

思路：两遍dp，一次从左上往右下，一次从右下往左上。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int row = matrix.size();
        if(row == 0){
            return matrix;
        }
        int col = matrix[0].size();
        vector<vector<int>> distance(row,vector(col,INT_MAX - 10000));//-10000是因为
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(matrix[i][j]==0){//第一次扫描的时候看看标记出来0
                    distance[i][j] = 0;
                } else {
                    if(i>0){//注意边界条件
                        distance[i][j] = min(distance[i-1][j]+1,distance[i][j]);
                    }
                    if(j>0){
                        distance[i][j] = min(distance[i][j-1]+1,distance[i][j]);
                    }
                }
            }
        }
        for(int i = row-1; i >=0; --i){
            for(int j = col-1; j >=0; --j){
           
                    if(i<row-1){
                        distance[i][j] = min(distance[i+1][j]+1,distance[i][j]);
                    }
                    if(j<col-1){
                        distance[i][j] = min(distance[i][j+1]+1,distance[i][j]);
                    }
           
            }
        }
        return distance;
    }
};

感觉如果不知道起点在哪的时候：(0,0) 不一定是0，需要我们去搜索一下，可以用这种方式解决。这里使用了两次dp，正好cover了所有情况(向左，向右，向上，向下)

机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

思路：
把和的格子看成障碍物，直接以（0,0）作为起点，使用bfs搜索。

class Solution {
    // 计算 x 的数位之和
    int get(int x) {
        int res=0;
        for (; x; x /= 10) {
            res += x % 10;
        }
        return res;
    }
public:
    int movingCount(int m, int n, int k) {
        if (!k) return 1;
        queue<pair<int,int> > Q;
        // 向右和向下的方向数组
        int dx[2] = {0, 1};
        int dy[2] = {1, 0};
        vector<vector<int> > vis(m, vector<int>(n, 0));
        Q.push(make_pair(0, 0));
        vis[0][0] = 1;
        int ans = 1;
        //需要证明，如果sum(m)+sum(n)<k,则一定有一条路径
        while (!Q.empty()) {
            auto [x, y] = Q.front();
            Q.pop();
            for (int i = 0; i < 2; ++i) {
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) continue;
                Q.push(make_pair(tx, ty));
                vis[tx][ty] = 1;
                ans++;
            }
        }
        return ans;
    }
};

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

使用回溯法：

class Solution {
public:
    
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        generate(n*2,n,res,"",0);
        return res;
    }

    void generate(int n,int l/*左括号剩余个数*/, vector<string>& v,string str,int m/*字符串中左括号比右括号多的个数*/){
             
        if(n<1){
            v.push_back(str);
            return;
        }   
        if(l > 0){
            // str = str + '('; 别这么写，会影响下面的case！！！
            generate(n-1,l-1,v,str+'(',m+1);
        }
        if(m > 0){
            // str = str + ')'; 
            generate(n-1,l,v,str+')',m-1);
        }
    }
};

二叉树插入

给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。

添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。

将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。

如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。

输入:
二叉树如下所示:
4
/ \
2 6
/ \ /
3 1 5
且 v = 1 d = 2

输出:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5

思路：使用bfs获得第d-1层的所有节点，然后按照题目要求添加。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(root==nullptr){
            return root;
        }
        if(d==1){
            TreeNode* newRoot = new TreeNode(v);
            newRoot->left = root;
            return newRoot;
        }
        pair<TreeNode*,int> rootpair = make_pair(root,1);
        queue<pair<TreeNode*,int>> q;//记录深度
        q.push(rootpair);
        while(!q.empty()){
            auto [node, curDepth] = q.front();
            if(curDepth==d-1){
                break;
            }
            q.pop();
            if(node->left!=nullptr){
                q.push(make_pair(node->left,curDepth+1));
            }
            if(node->right!=nullptr){
                q.push(make_pair(node->right,curDepth+1));
            }
        }
        while(!q.empty()){
            auto [node, curDepth] = q.front();
            q.pop();
            TreeNode* leftTemp = node->left;
            TreeNode* rightTemp = node->right;
            node -> left = new TreeNode(v);
            node -> right = new TreeNode(v);
            node -> left -> left = leftTemp;
            node -> right -> right = rightTemp;
            
        }
        return root;
    }
};

相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。


class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p&&!q){
            return true;
        }
        if((p&&!q)||(!p&&q)||p->val!=q->val){
            return false;
        }
        queue<TreeNode*> pQ;
        queue<TreeNode*> qQ;
        pQ.push(p);
        qQ.push(q);
        while(!pQ.empty()){
            TreeNode* ptmp = pQ.front();
            TreeNode* qtmp = qQ.front();
            pQ.pop();
            qQ.pop();
            if(qtmp->left||ptmp->left){
                if(!qtmp->left || !ptmp->left || ptmp->left->val != qtmp->left->val){
                    return false;
                } 
                pQ.push(ptmp->left);
                qQ.push(qtmp->left);    
            }
            if(qtmp->right||ptmp->right){
                if(!qtmp->right || !ptmp->right || ptmp->right->val != qtmp->right->val){
                    return false;
                } 
                pQ.push(ptmp->right);
                qQ.push(qtmp->right);    
            }
        }        
        return true;
    }
};

衍生：对称二叉树：
给定一个二叉树，检查它是否是镜像对称的。

思路：一个树如果是对称的，那它左子和右子的值一定相等，左子的左子和右子的右子一定对称。

    bool isSymmetric(TreeNode* root){
        if(!root){
            return true;
        }
        return isMirror(root->left,root->right);

        // if(!root||(!root->left&&!root->right)){ return true;}

        //wrong!
        // if(root->left&&root->right){
        //     return isSymmetric(root->left)&&isSymmetric(root->right)&& root->left->val==root->right->val;
        // } else {
        //     return false;
        // } 
    }

    bool isMirror(TreeNode* node1,TreeNode* node2){
        if(!node1&&!node2){
            return true;
        }
        if(!node1||!node2){
            return false;
        }
        
        return (node1->val == node2 ->val)   
            && isMirror(node1->left,node2->right)
            && isMirror(node1->right,node2->left);
    }

二叉树展开为链表
给定一个二叉树，原地将它展开为链表。
TIM截图20200415101029.png

方案一，自顶向下搜索，将左子树挂在右子上，原有的右子树挂在现在最右节点的右边。

public:
    void flatten(TreeNode* root){
       while(root){
           if(!root->left){
               root = root->right;
            } else {
                TreeNode* r = root -> right;
                root -> right = root -> left;
                root -> left = nullptr;
                TreeNode* tmp = root;
                while(tmp->right){
                    tmp = tmp -> right;
                }
                tmp -> right = r;
                root = root->right;
            }
       }
    }

方案二，不难看出链表化后的二叉树是其前序遍历的版本，我们可以反其道而行之，使用后序遍历，头插到链表上。

    TreeNode* pre;//当前链表
    void flatten(TreeNode* root){//后序遍历
        if(!root){
            return; 
        }
        flatten(root->right);
        flatten(root->left);
        //头插入链表
        root->right = pre;
        pre = root;
        //记得把left置null
        root->left = nullptr;
    }

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路：先对于intervals 按照左区间大小排序，从前向后遍历，步长为1，如果可以合并（R1 > L2），就合并

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) { 
        if(intervals.size()==0){
            return {};
        }
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> res;
        for(int i = 0; i< intervals.size(); ++i){
            int L = intervals[i][0],R = intervals[i][1];
            if(res.empty()|| L >res.back()[1] ){
                res.push_back({L,R});
            } else {
                res.back()[1] = max(res.back()[1],R);
            }
        }
        return res;
    }
};

反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int i = 0;
        ListNode* h = new ListNode(0);
        h->next = head;
        ListNode* prev = h;
        for(int i = 0; i < m-1; ++i){
            prev=prev->next;
        }
        ListNode* rStart = prev->next;//反转前第m个节点，
        ListNode* end = rStart; //反转后的第n个节点
        ListNode* rBetween = new ListNode(0);//反转的过程以头插法，插入这个列表
        for(int i = m-1; i< n; ++i){
            ListNode* tmp = rStart->next;
            rStart->next = rBetween->next;
            rBetween->next = rStart;
            rStart = tmp;
        }
        prev->next = rBetween->next;
        end->next = rStart;
        return h->next;
    }
};

反转链表
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

class Solution {
public:
    //迭代版本
    // ListNode* reverseList(ListNode* head) {
    //     ListNode* h = new ListNode(0);
    //     h->next = head;
    //     ListNode* res = new ListNode(0);
    //     while(h->next!=nullptr){
    //         h = h -> next;
    //         ListNode* tmp = res -> next;
    //         res->next = new ListNode(h->val);
    //         res->next -> next = tmp;
    //     }
    //     return res->next;
    // }

  

   //递归
    ListNode* reverseList(ListNode* head){
        if(!head||!head->next){
            return head;
        }
        ListNode* res = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return res;
    }
};

二叉搜索树的最近公共祖先

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

思路：根据平衡二叉搜索树定义，两个节点（2, 4）的最近公共祖先的值（2）一定大于等于较小节点（4）且小于等于较大节点（4），且最近公共祖先的父节点的值(6)一定同时大于两个节点或同时小于两个节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root||!p||!q){
            return root;
        }
        TreeNode* res = root;
        while(res){
            if(res->val >= p->val && res->val >= q->val){//等于是
                if(res->val == p->val || res->val ==q->val){//防止 2,4 都大于等于2，即示例 2 
                    break;
                }
                res = res->left;
            } else if(res->val <= p->val && res->val <= q->val){
                if(res->val == p->val || res->val ==q->val){
                    break;
                }
                res = res->right;
            } else {
                break;
            }
        }
        return res;
    }
};

最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

思路：动态规划

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n==0){
            return 0;
        }
        int dp[n][3];

        dp[0][0]=0;//当天不持股，且当天没卖出
        dp[0][1]=-prices[0];//第i天持股
        dp[0][2]=0;//当天不持股，股票是当天卖出的，第0天特殊情况，认为当天买入当天卖出

        for(int i = 1; i< n ;i++){
            dp[i][0] = max(dp[i-1][0],dp[i-1][2]); //
            dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1]);
            dp[i][2] = dp[i-1][1]+prices[i];
        }

        return max(dp[n-1][0],dp[n-1][2]);//
    }
};
```![TIM截图20200423182940.png](https://img.haomeiwen.com/i8081626/dce80ebfbab1375f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)


28. 超级丑数
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

> 示例:
   输入: n = 12, primes = [2,7,13,19]
   输出: 32 
   解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为： 
  [1,2,4,7,8,13,14,16,19,26,28,32] 。

使用动态规划，观察一下规律：
* 开始时丑数序列dp为 $[1]$
* $dp[1] = min(dp[0] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[0]* prime[0] =2$
* $dp[2] = min(dp[1] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[1]* prime[0]=4$
* $dp[3] = min(dp[2] * prime[0],dp[0] * prime[1],dp[0] * prime[2],dp[0] * prime[3])= dp[0]* prime[1]=7$
* $dp[4] = min(dp[2] * prime[0],dp[1] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[2]*prime[0]=8$
* $dp[5] = min(dp[3] * prime[0],dp[1] * prime[1],dp[0] * prime[2],dp[0] * prime[3]) = dp[0]*prime[2]=13$
* **! dp[6]中出现了 2 * 7 和 7 * 2 相等的情况，需要都考虑进来并去重。** $dp[6] = min(dp[3] * prime[0],dp[1] * prime[1],dp[1] * prime[2],dp[0] * prime[3]) = dp[3]*prime[0]= dp[1] * prime[1] =14$

根据上述规律，维护下两个数组：
* index数组：index[j] 是第j个prime当前在dp的下标
* dp：超级丑数序列。
```c++
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        if(n==0){
            return 1;
        }
        int dp[n];
        dp[0]=1;
        int k = primes.size();
        vector<int> index(k,0);
        for(int i = 1; i < n; ++i){
            int minVal = INT_MAX;
            for(int j = 0; j < k; ++j){
                if(dp[index[j]] * primes[j]<minVal){
                    minVal = dp[index[j]] * primes[j];
                }
            }
            for(int j =0; j < k; ++j){//去重 2*7 和 7*2
                if(dp[index[j]]* primes[j] == minVal){
                    ++index[j];
                }
            }
            dp[i]=minVal;
        }
        return dp[n-1];
    }
};

硬币
给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:

输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

思路：动态规划

一开始我想的是这样的一个方程，但是结果不对，原因是因为1+5和5+1会被认为是6的两种找零方式。

img_0835.png
修改后的方程：

TIM截图20200423182940.png

实现：

class Solution {
public:

    int mod = 1000000007;
    int coins[4] = {1,5,10,25};

    int waysToChange(int n) {
        if(n==0){
            return 0;
        }
        int dp[n+1];
        for(int i = 1; i<=n; ++i){
            dp[i]=0;
        }
        dp[0]=1;
    
        for(int i = 0; i <4; ++i){
            int coin=coins[i];
            for(int j = coin; j <= n; ++j){
                dp[j] = (dp[j]+dp[j-coin])%mod;
            }
        }
        return dp[n];
    }
};

不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:
输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

TIM截图20200424082620.png

class Solution {
public:
    int numTrees(int n) { 
        if(n==0){
            return 1;
        }
        int dp[n+1];//dp[i]表示有i个节点的组成树的个数
        dp[0] = 1;
        for(int i=1; i <= n; ++i){
            int tmp = 0;
            for(int j=0; j < i;++j){
                tmp += dp[j]*dp[i-j-1]; 
            }
            dp[i] = tmp;
        }
        return dp[n];        
    }
};

螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

思路：使用4个变量{l, r, b, t}记录一个bounding box，按照螺旋的顺序，对box进行遍历：

如果矩阵的大小是{x, y}，一开始 {l,r,t,b} = {0, y-1, 0, x-1}
然后从左遍历box中的第一行，top 向下移动一个单位，如果 top 比 bottom还低（即 boundingbox中只剩一行）结束。
从上到下遍历最后一列，...
从右到左遍历最后一行，...
从下到上遍历第一列，...
back to 1

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int len =  matrix.size();
        if(len==0){
            return vector<int>();
        }
        int t = 0,l= 0,b=len,r=matrix[0].size();
        vector<int> res;
        while(true){
            for(int i = l; i < r; ++i){
                res.push_back(matrix[t][i]);
            }
            t++;
            if(t==b){
                break;
            }
            for(int i = t; i < b; ++i){
                res.push_back(matrix[i][r]);
            }
            r--;
            if(r==l){
                break;
            }
            for(int i = r; i >= l; --i){
                res.push_back(matrix[b][i]);
            }
            b--;
            if(t==b){
                break;
            }
            for(int i = b; i >= t; --i){
                res.push_back(matrix[i][l]);
            }
            l++;
            if(l==r){
                break;
            }
        }
        return res;
    }
};

验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

思路：一开始的时候没有注意到是整个左子树的节点都要小于，右子树都要大于。所以没有考虑到这种case

TIM截图20200425220044.png

需要在递归的时候加上一个上下界的判断。

    bool isValidBST(TreeNode* root) {
        if(!root){
            return true;
        }
        return isValidBST(root,((long)INT_MIN)-1,((long)INT_MAX)+1);//long是需要考虑边界值的情况
    }

    bool isValidBST(TreeNode* root, long min, long max){
        return  root->val > min && root->val < max
                && (!root->left ||isValidBST(root->left,min,root->val)) 
                && (!root->right||isValidBST(root->right,root->val,max)); 

    }

合并 k 个有序列表：

先实现有序列表的两两合并，再进行归并式的合并，分而治之。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0){
            return nullptr;
        }
        return merge(lists,0,lists.size()-1);
    }

    ListNode* merge(vector<ListNode*> v, int start,int end){
        if(start == end){
            return v[start];
        }
        int mid = start+end >> 1;
        return merge2Lists(merge(v,start,mid),merge(v,mid+1,end));
    }

    ListNode* merge2Lists(ListNode* l1,ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* tmp = head;
        while(l1 && l2){
            if(l1->val < l2->val){
                head -> next = l1;
                l1 = l1 -> next;
            } else {
                head -> next = l2;
                l2 = l2 ->next;
            }
            head = head-> next;
        }
        head -> next = l1? l1:l2 ;
        return tmp->next;
    }
};

数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

思路：先考虑一个简单一点的case，如果一个组中只有一个出现一次的数字，其他数字都出现了2次，那么我们可以将整个列表异或得到那个只出现一次的数据：

        int ret = 0;
        for(int n : nums)
            ret ^= n;

那可以将上面的问题变成：

先将给定的数组分为两个 只有一个出现一次的数字，其他数字都出现了2次 的两个数组
分别对于两个数组进行异或，得到结果

问题就是在如何实现1上面，为了实现1，分到的数组有两个要求：
1）两个只出现一次的数字需要被分到两个组
2）任意一对大小相同的数字要被分到一个组

这个要求依旧可以巧妙的使用异或解决：
将整个数组全员异或得到一个值 $x$ ，由于一个数组中有两个只出现一次的树，所以 $x$ 中肯定有一位是1，记录下这个1的位置，用这个bit位的值将数组一分为二。这个分组方法满足我们上面的要求：

由于在这个位置bit相同的数字会分到同一个数组，所以两个相同的数字会被分到同一组，满足1）
由于在 $x$ 中这个位是1，证明只出现一次的两个数在这个位上的bit值不同，所以这两个只出现一次的数字不会出现在同一个组中，满足2）。

实现：

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ret = 0;
        for(int n : nums)
            ret ^= n;
        int div = 1;
        while((div & ret) == 0)
            div <<= 1;
        int a=0, b=0;
        for(int n: nums)
            if(n & div)
                a ^= n;
            else 
                b ^= n;
        return vector<int>{a,b};
    }
};

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

思路：递归
实现：

class Solution {
public:

    vector<vector<int>> res;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> list= {};
        func(list,0,nums);//这里nums没排序也过了，不过要注意一下，如果题目没有明确是否有序还是要排一下
        return res;
    }

    void func(vector<int>& list,int index, vector<int> nums){
        if(index == nums.size()){
            res.push_back(list);
            return;
        }
        for(int i = index; i < nums.size();++i){
            list.push_back(nums[i]);
            func(list, i+1,nums);
            list.pop_back();
        }
        func(list,nums.size(),nums);
    }
};

子集
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

代码的整体框架沿用了第一个，使用剪枝去重：画一下递归树，发现我们剪枝的规则是：在水平上连续相等的枝子，我们只保留第一个：

img_0836.png

可以看到两个重复的2，我们只保留了第一个，这样得到的子集集合就是答案：

class Solution {
public:

    vector<vector<int>> res;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> list= {};
        sort(nums.begin(),nums.end());
        func(list,0,nums);
        return res;
    }

    void func(vector<int>& list,int index, vector<int> nums){
        if(index == nums.size()){
            res.push_back(list);
            return;
        }
        for(int i = index; i < nums.size();++i){
            if(i > index && nums[i] == nums[i-1]){ /*注意 i > index 而不是 > 0 否则会错误的将[2,2]所在的枝子剪掉*/
                continue;
            }
            list.push_back(nums[i]);
            func(list, i+1,nums);
            list.pop_back();            
        }
        func(list,nums.size(),nums);
    }
};

格雷编码
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。

格雷编码序列必须以 0 开头。

是一道找规律的题：
0 -> [0]
1 -> [ 0, 1]
2 -> [ 00, 01, 11, 10]
3 -> [000,001,011,010,
110, 111,101,100]

2 中的 00,01可以认为是1中的[0,1]前面加了个0，也就是没变；而11,10可以认为是1中的[0,1]倒序过来再加个1。

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result(1,0);
        for(int i = 0; i < n; i++){
            int mask = 1 << i;
            for(int j = result.size()-1; j>=0; --j){
                result.push_back(mask^result[j]);
            } 
        }
        return result;
    }
};

二叉树锯齿状层次遍历
要求：层次遍历的基础上，第一层从左到右遍历第二层从右到左，以此类推。
思路：如果使用BFS，需要对于在换层的时候对队列进行倒序，复杂度较高。如果使用BFS，可以用根据层数，直接使用insert(vec.begin(), val)和push_back(val)插入，效率更高。

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        dfs(res,0,root);
        return res;
    }

    void dfs(vector<vector<int>>& res, int level, TreeNode* root){
        if(!root){
            return;
        }
        if(level >= res.size()){
            res.push_back(vector<int>());
        }
        if(!root->left){
            dfs(res,level+1,root->left);
        }
        if(!root->right){
            dfs(res,level+1,root->right);
        }
        if(level%2==0){
            res[level].push_back(root->val);
        } else {
            res[level].insert(res[level].begin(),root->val);
        }
    }

38.目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
注意:

数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。

思路：

剪枝
搜索空间为2^n，可以排序后进行剪枝，即：如果现在剩余的数组和都已经小于当前sum和目标S之间差的绝对值，可以进行剪枝。剪枝之前可以进行一次倒序排序，使剪枝后的效率更高。

class Solution {

    int res = 0;
    vector<int> sum;
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int len = nums.size();
        if(len==0){
            return S==0?1:0;
        }
        sort(nums.rbegin(),nums.rend());
        sum=vector(len,0);
        sum[len-1]=nums[len-1];
        for(int i = len-2; i >=0; --i){
            sum[i] = sum[i+1] + nums[i];
        }
        findTargetSum(nums,0,0,S);
        return res;
    }

    void findTargetSum(vector<int>&nums, int index, int s, int target){
        if(index == nums.size()&&s==target){
            res+=1;
           return;
        }
        if(index >= nums.size()||(s < target && target-s > sum[index])||(s > target && s - target > sum[index])){
            return;
        }
        findTargetSum(nums,index+1,s-nums[index],target);
        findTargetSum(nums,index+1,s+nums[index],target);
    }


};

2、动态规划
可以把这个问题考虑成为：我要把nums分成两个集合，一个集合是正，一个集合是负数，有集中分发可以让两个集合相加等于S。题中限制了 数组非空，且长度不会超过20。初始的数组的和不会超过1000。 我们可以整一个num.size() * 2001的数组，设dp[i][j]为数组前i个元素和为j的方法个数
$dp[i][j] = dp[i-1][j-nums[i]+1000]+dp[i-1][j+nums[i]+1000]$
可以使用元祖法来省空间

前K个高频单词
没什么好讲的思路，主要熟悉一下c++的api
值得注意的一点，iterator取出元素会做一个deep copy，修改它不会影响数组中的元素值。
class Solution {
public:

typedef struct sfi{
string s;
int freq = 0;//出现次数
} comp;

typedef pair<string,sfi> pss;
static bool cmp(pss i, pss j){
if (i.second.freq == j.second.freq){
return i.second.s < j.second.s;
} else {
return i.second.freq > j.second.freq;
}
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string,comp> v;
for(int i = 0; i < words.size(); ++i){
auto iter = v.find(words[i]);
if(iter == v.end()){
comp c;
c.s=words[i];
c.freq = 1;
v[words[i]]=c;
} else {
comp c = iter->second;//这里是一个deep copy!
c.freq++;
v[words[i]]=c;
}
}
vector<pss> vec;
for(auto mp=v.begin(); mp != v.end(); mp++){
vec.push_back(pss(mp->first, mp->second));
}
sort(vec.begin(),vec.end(),cmp);
vector<string> res;
for(int i = 0; i < k; ++i){
res.push_back(vec[i].first);
}
return res;
}
};
奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

code：

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* odd = head;
        if(!odd){
            return head;
        }
        ListNode* even = head->next;
        ListNode* tmp = even;
        while(odd->next&&even->next){
            odd->next = odd->next->next;
            odd = odd ->next;
            even->next = even->next->next;
            even = even->next;
        }
        odd->next=tmp;
        return head;
    }
};

把二叉搜索树转化为累加树
使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

思路：二叉树反向中序遍历

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int s = 0;
        sum(root, s);
        return root;
    }

    void sum(TreeNode* root, int& s){
        if(!root){
            return;
        }
        sum(root->right, s);
        s += root->val;
        root -> val = s;
        sum(root->left, s);
    }
};

祖父节点值为偶数的节点和
给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：

该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0 。

 */
class Solution {
public:
    int sumEvenGrandparent(TreeNode* root) {
        if(!root){
            return 0;
        }
        queue<TreeNode*> q;
        q.push(root);
        int res = 0;
        while(!q.empty()){
            TreeNode* t = q.front();
            q.pop();
            if(t->val%2==0){
                res+=sumOfGrandChildren(t);
            }
            if(t->left){
                q.push(t->left);
            }
            if(t->right){
                q.push(t->right);
            }
        }
        return res;
    }

    int sumOfGrandChildren(TreeNode* root){
        TreeNode* leftChild = root->left;
        TreeNode* rightChild = root -> right;
        int res = 0;
        if(leftChild){
            res += leftChild->left?  leftChild->left->val:0;
            res += leftChild->right? leftChild->right->val:0;
        } 
        if(rightChild){
            res += rightChild -> left? rightChild->left->val : 0;
            res += rightChild -> right? rightChild->right->val:0;
        }
        return res;
    }
};

重复的DNA序列
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]

思路：
滑动窗口+HashMap

string 版本

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int len = 10;
        vector<string> res;
        if(s.size() < len){
            return res;
        }
        char strs[s.size()+1];
        strcpy(strs, s.c_str());
        map<string,int> m;
        for(int i=0; i <= s.size()-len; ++i){
            char* a = strs + i;
            char* b = strs + i + len;
            char tmp = *b;
            *b = '\0';
            auto iter = m.find(a);
            if(iter!=m.end()){
                m[a] = iter->second+1;
            } else {
                m[a] = 1;
            }
            *b = tmp;
        }
        for(auto i = m.begin(); i!=m.end(); ++i){
            if(i->second>1){
                res.push_back(i->first);
            }
        }
        return res;
    }
};

问题：string 计算hash时间太长，string是不可变对象，会大量new新的obj

2、改进版
使用0-3来表示四种字母，即使用两位来表示一个字母。key的计算也比较简单，可以使用位运算来更新key。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int len = 10;
        vector<string> res;
        if(s.size() < len){
            return res;
        }
        unordered_map<int,int> m;
        int key = 0;
        for(int i = 0; i < len-1; ++i){
            key = (key << 2) + getVal(s[i]);
        }
        int mask = 0xFFFFF;
        for(int i=len-1; i < s.size(); ++i){
            key = ((key << 2)&mask) + getVal(s[i]);
            auto iter = m.find(key);
            if(iter!=m.end()){
                m[key] = iter->second+1; 
            } else {
                m[key] = 1;
            }
        }
        for(auto i = m.begin(); i!=m.end(); ++i){
            if(i->second>1){
                res.push_back(decode(i->first,len));
            }
        }
        return res;
    }

    string decode(int val,int len){
        char dir[] = {'A','C','G','T'};
        char res[len+1];
        res[len] = '\0';
        for(int i = 0 ; i < len; ++i){
            res[len-i-1] = dir[val&0x3];
            val >>= 2;
        }
        return string(res);
    }

    int getVal(char a){
        if(a=='A') return 0;
        if(a=='C') return 1; 
        if(a=='G') return 2;
        if(a=='T') return 3;
        return 0;
    }
};

值得一提的是，这里使用unordered_map会比map快一倍（88ms vs 188ms）

只出现一次的元素
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3
示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

思路：异或，永远滴神！

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int seen_once=0, seen_twice = 0;
        //使用异或的时候，可以把一个int当成一个int集合，异或一次，就是放进这个集合，再异或一次，就取出来。
        for(int num:nums){
            // 如果见到过0次，seen_twice 和 seen_once 两个集合里面就不会有这个数字，可认为是0.
            // 如果见到过1次，seen_twice 是 0，seen_once 是 num
            // 如果见到过2次，seen_twice 是 num
           
            seen_once = ~seen_twice & (num ^ seen_once );
          //    见过0次+1 ：~0  &  (num ^ seen_once) = num^seen_once = num
          //    见过1次+1 ：~0  &  (num ^ seen_once) = num^seen_once = 0
          //    见过2次+1 ：~num & (num ^ seen_once) = ~num & (num^0)= 0

            seen_twice = ~seen_once & (num ^ seen_twice);
          //    见过0次+1 ：~num(这里seen_once=num，因为上面的代码执行过了) &  (num ^ seen_twice) = ~num & num = 0 
          //    见过1次+1 ：~0  &  (num ^ seen_twice) = num ^ seen_twice = num;
          //    见过2次+1 ：~0  &  (num ^ seen_twice) = num ^ seen_twice = 0; 
        }
        return seen_once;//最后seen_once剩下来的就是只出现了一个的
    }
};

缺失的数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:
输入: [3,0,1]
输出: 2

示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

方案1 ：数学
根据求和公式，可以计算出原本的总和，减去数组中的元素就是缺失的元素，但是会有溢出风险，可以边加下标边减数组中的内容

  int missingNumber(vector<int>& nums) {
        int sum = 0;
        for (int i = 1; i <= nums.size(); i++) {
            sum += i;
            sum -= nums[i - 1];
        }
        return sum;
    }

方案2:异或
使用异或的场景是，只要有办法凑对找落单的，可以往异或方向去考虑：当我们遍历一个数组的时候，可以得到[0, len-1]的这些下标，再加上len，就是[0, len-1]，数组中的元素是[0, len]中少了一个，把所有的这些异或起来，成对的变成0，落单的就留了下来。

 int missingNumber(vector<int>& nums) {
        int len = nums.size();
        int missing = 0;
        for(int i = 0; i < len; ++i){
            missing ^= i ^ nums[i]; 
        }
        return missing^len;
}

移除掉k位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

思路：首先我们需要考虑怎么样可以使删除后的数字最小，高位的数字优先级高，所以需要从左向右扫描。我们希望从高位开始，尽可能的非单调递减。所以就要删除高位逆序对中的第一个数字。需要考虑到删完数字为0开头和删完为0的特殊情况。自己写的太啰嗦，借鉴力扣大神的一个写法。

class Solution {
public:
string removeKdigits(string num, int k) {
        if(num.size() == k) return string(1, '0');
        string stk;//string可以拿来当一个栈使用，下面算法保证这个栈内的元素单调非递减
        int i = 0;
        while(k > 0 && i < num.size()) // 将num中的字符按规则移动到栈中
        {
            if(stk.empty() || stk.back() <= num[i])  // 直接入栈，并转而遍历下一个元素
            {
                stk.push_back(num[i]);
                ++i;
            }    
            else // stk.back() > num[i]
            {
                stk.pop_back();
                --k;
            }
        }
        // 1. 如果i == 0, 则 k 可能不等于0, 移除掉stk末尾k个元素.
        // 2. 如果k == 0, 则 i 可能不等于0, 需要加上num中i之后的元素.
        stk = stk.substr(0, stk.size() - k) + num.substr(i);

        // 移除开头的0,在全0的情况下保证至少剩下一个0.
        size_t beginIndex = 0;
        while(beginIndex < stk.size() - 1 && stk[beginIndex] == '0') ++beginIndex;
        
        return stk.substr(beginIndex);
    }
};

快速幂

class Solution {
public:
    double myPow(double x, int n) {
        int neg = n < 0;
        n=abs(n);
        double res = 1;
        double cur = x;
        while(n > 0){
            int m = n%2;
            n/=2;
            if(m){
                res *=cur;
            }
            cur *=cur;
        }
        return neg? 1/res:res;
    }
};

变体：超级次方
你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1:

输入: a = 2, b = [3]
输出: 8
示例 2:

输入: a = 2, b = [1,0]
输出: 1024

思路：开始还头疼想着想着怎么把大数数组转成2进制，后来看了一个题解，可以十进制直接快速幂后对于10进制的那个个位数再进行一次二进制快速幂。

class Solution {
    //(a*b)%c = (a%c)*(b%c);
    public:
    int superPow(int a, vector<int>& b) {
        a= a%1337;
        int res = 1;
        int cur = a;
        for(int i = 0; i < b.size(); ++i){
            if(b[b.size()-1-i]>0){
                res = (res *fastPow(cur,b[b.size()-1-i]))%1337;
            }
            cur = fastPow(cur,10);//dp中如果dp[i]可以只由固定个dp[i-x]递推出来，可以不用开数组，固定几个变量就好。
        }
        return res;
    }
    int fastPow(int a, int n){
        int res = 1;
        int cur = a%1337;
        while(n>0){
            if(n%2==1){
                res*=cur;
            }
            cur=(cur*cur)%1337;
            n/=2;
        }
        return res%1337;
    }
};

等差数列划分

示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

思路：统计所有的等差数组长度lens(>=3)，每个等差序列有(len-2)*(len-1)/2个len>3的子序列

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if(A.size() < 3){
            return 0;
        }
        int res = 0;
        //思路：先找数组中等差数组的长度，再
        int len = 2;//等差数组长度（要大于三）
        int oldDiff = A[1]-A[0];
        int cur = 2;
        // vector<int> lens; //记录数组中非重叠等差数组们的长度 改-无需记录，循环的时候算就可以了
        while(cur < A.size()){
            int curDiff = A[cur]-A[cur-1];
            if(curDiff != oldDiff ){
                oldDiff = curDiff;
                if(len > 2){
                    // lens.push_back(len);
                   res += (len-1)*(len-2)/2;
                } 
                len = 2;
            } else {
                len++;
            }
            cur++;
        }
        if(len > 2){
            res += (len-1)*(len-2)/2;
            // lens.push_back(len);
        } 
        // int res = 0;
        // for(int num : lens){
        //     res += (num-1)*(num-2)/2;//
        // }
        return res;
    }
};

思路2:动态规划，

查找和最小的k个数对
可以使用优先级队列/小顶堆来实现
Priority queues are a type of container adaptors, specifically designed such that** its first element is always the greatest of the elements it contains**, according to some strict weak ordering criterion.

// Priority queue

class Solution {
public:
    struct cmp{
        bool operator ()(pair<int,int> a, pair<int,int> b){
            return a.first + a.second > b.first + b.second;
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> res;
        priority_queue<pair<int,int>, vector<pair<int,int> >,cmp> q;//priority_queue<Type, Container, Compare>
        for(int i = 0; i < nums1.size(); ++i){
            for(int j = 0; j < nums2.size(); ++j){
                q.push(pair<int,int>(nums1[i],nums2[j]));
            }
        }
        for(int i = 0; i < k && !q.empty();++i){
            pair<int,int> p =q.top();
            q.pop();
            res.push_back({p.first,p.second});
        }
        return res;
    }
};

旋转函数
给定一个长度为 n 的整数数组 A 。

假设 Bk 是数组 A 顺时针旋转 k 个位置后的数组，我们定义 A 的“旋转函数” F 为：

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。

计算F(0), F(1), ..., F(n-1)中的最大值。

注意:
可以认为 n 的值小于 105。

示例:

A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

思路：
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (1 * 4) + (2 * 3) + (3 * 2) + (0 * 6) = 0 + 4 + 6 + 6 = 16
F(2) = (2 * 4) + (3 * 3) + (0 * 2) + (1 * 6) = 0 + 6 + 8 + 9 = 23
F(3) = (3 * 4) + (0 * 3) + (1 * 2) + (2 * 6) = 0 + 2 + 12 + 12 = 26
规律如下，如果数组nums的长度为len，总和为sum，F(i) = F(i-1) + sum - nums[len-1-i];

注意，在加和的过程中可能溢出

class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        long res=0;
        int len=A.size();
        long sum=0;
        for(int i = 0; i < len; ++i){
            res += A[i]*i;
            sum += A[i];
        }
        long old = res;//注意会溢出
        for(int i = 0; i<len-1; ++i){
            old = old + sum - A[len-1-i]*(long)len;
            res = max(res,old);
        } 
        return (int)res;
    }
};

刷题笔记

二叉树的右视图

二维区域和检索 - 矩阵不可变

二叉搜索树的最近公共祖先

最佳买卖股票时机含冷冻期

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读