每次做题需要检查一下的问题：

1.字母拼写。看看写着写着变量名是不是写偏了。

2.while循环 for循环 还有链表里面有没有移动，循环是否可以结束。

3.如果函数的参数比较多的话，检查下函数参数有没有填对，仔细想想。

N皇后问题详解

具体的思考思路如下：

1.数据结构的选择：

​ 选用什么数据结构可以模拟出一个棋盘。联想到Z型字符串，似乎对于这种问题，利用StringBuilder的list可以用来模拟一个字符串二维序列。

​ 为了解决这个问题，我们应当从一个空棋盘开始回溯：

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<List<String>> solveNQueens(int n) {
		List<List<String>> res=new ArrayList<>();
    	List<StringBuilder> board=new ArrayList<>();//选取StringBuilder的list作为一个二维字符串序列的容器
    	for(int i=0;i<n;i++){
            StringBuilder sb=new StringBuilder();
            for(int j=0;j<n;j++){
                sb.append(".");
            }
            board.add(sb);
        }//初始化空棋盘
    	backTrack(res,board,0);
    return res;//记得返回答案
    }

2.怎么回溯？

回溯其实要解决如下的几个问题，或者说回溯可以问几个问题来引导自己的思路：

​ 1.什么时候终结自己的回溯，回溯每次改变的量是什么，回溯每次不变的行为是什么？

​ 回溯的终点应该是当最后一行的皇后都已经被选定，这个时候回溯达到终点。

​ 因此，回溯每次都要改变自己做选择的行数。

​ 对于每一行，每次都要做的行为是选取一列，保证该列的前提下，然后选取一个皇后。做完选择后，继续到下一行做选择。

​

​ 注意：做完回溯之后的回退，这个多做几题就知道了。

因此可以写出下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void backTrack(List<List<String>> res,List<StringBuilder> board,int depth){
    int size=board.size();
    if(depth==board.size()){
        List<String> ans=new ArrayList<>();
        for(StringBuilder row:board){
            ans.add(row.toString());
        }
        res.add(ans);
    }
    for(int i=0;i<size;i++){
        if(!isValid(board,depth,i))continue;
        board.get(depth).setCharAt(i,'Q');//注意这个api，自己没有记住
        backTrack(res,board,depth+1);
        board.get(depth).setCharAt(i,'.');
    }
}

3.根据题目写有效性的判断：

对于同一行只有一个皇后，已经在回溯中写了。

要判断对角线和同一列的。注意，都只需要判断上方即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
boolean isValid(List<StringBuilder> board,int row,int col){
    int size=board.size();
    for(int i=0;i<row;i++){
        if(board.get(i).charAt(col)=='Q')return false;
    }
    
    for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){//千万要注意一下，这里的终止判断条件语句要用&&连接，自己之前之前直接用,连接了，低级错误
        if(board.get(i).charAt(j)=='Q')return false;
    }
    
    for(int i=row-1,j=col+1;i>=0&&j<size;i--,j++){ //这个for循环里面的变量加减问题自己已经出现过多次错误了，自己一定要小心
        if(board.get(i).charAt(j)=='Q')return false;
    }
    return true;
}

子集问题

依然是问自己几个问题：

1.回溯的终点在哪里？如何回溯？

这里一个重要的问题就是，回溯每次做的选择是什么，可能的选择是什么。

这里回溯的终点为当最后一个位置都已经确定的时候，即

depth==n的时候就可以返回一个答案了。

对于其中每一个位置，都有选或者不选两个选项，因此与普通回溯的for循环不同，就是一个push和一个pop的操作。

1
2
3
4
5
6
7
8
9
public void backTrack(int[]nums,int depth,List<List<Integer> res,Deque<Integer> path){
    int len=num.length;
    if(depth==len){
        res.add(new ArrayList<>(path));
    }
    path.push(nums[depth]);
    backTrack(nums,depth+1,res,path);
    path.pop(nums[depth]);
}

说明一下，Deque的实现类型最好用ArrayDeque。

组合总和问题

这道题我一开始没有看出来是使用回溯，所以想一想回溯应用的场景：

1.寻找所有可行解的问题，其本质是暴力查询，也就是回溯。

因此这道题应该是可以意识到要用回溯的。

依然问问回溯的问题：

回溯的终点在哪里，我们每次做什么动作：

​ 因为每次目标是凑到target，因此回溯的终点就是达到target或者已经超出了target。于是，在我们的回溯函数中，我们始终用target去减去候选值，当得到结果为负的时候，回溯就结束。

​ 每次做的动作就是选出一个数出来，这里要引入一个begin的思路。就是说，由于[1,1,2]和[1,2,1]是一样的，因此我们要利用for循环的方式，来保证我们选数是按照一定顺序的。同时要注意一点，就是我们选数是可以重复的，所以回溯往里面深入的时候，其实是没有量的变化的，我们依靠终结条件来跳出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new ArrayDeque<>();
        int len=candidates.length;
        if(len==0)return res;
        
        backTrack(candidates,target,0,res,path);//写这种好多参数的函数，一定要检查一下是否和下面的函数对应
        return res;//不要忘记返回值
    }
    public void backTrack(int[] candidates,int target,int depth,List<List<Integer>> res,Deque<Integer> path){
    if(target<0)return;
    if(target==0){
        res.add(new ArrayList<>(path));
    }
    for(int i=depth;i<candidates.length;i++){
        path.addLast(candidates[i]);
        backTrack(candidates,target-candidates[i],i,res,path);//回溯里这里传递的参量不要不动脑，稍微想一想
        path.removeLast();
    }
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new ArrayDeque<>();
        int len=candidates.length;
        if(len==0)return res;
        Arrays.sort(candidates);
        backTrack(candidates,target,0,res,path);
        return res;
    }
    public void backTrack(int[] candidates,int target,int depth,List<List<Integer>> res,Deque<Integer> path){
    if(target<0)return;
    if(target==0){
        res.add(new ArrayList<>(path));
    }
    for(int i=depth;i<candidates.length;i++){
        if(target-candidates[i]<0)break;
        path.addLast(candidates[i]);
        backTrack(candidates,target-candidates[i],i,res,path);
        path.removeLast();
    }
}
}//一个小优化，注意在哪里剪枝---先找到重复的地方

复原IP地址

这道题有很多的边界条件，因此需要做考虑。

终点条件非常简单，就是4个整数都选完了。

因此，其实就是有四层，每一层做选择的问题。并且有一个限制条件，就是每一层实际都最多选三个字母。

一些限制条件列举如下：

​ 1.如果0开头，该层就要结束。

​ 2.每一层内部for循环里面，是上限是depth+3

所以尝试写写backTrack:

1
2
3
4
5
6
7
8
9
public void backTrack(int index,int depth,String s,StringBuilder path,List<String> res){
    if(depth==4){
        res.add(path.toString());
    }
    
    for(int i=index;i<index+3;i++){
       //我自己在写的时候，写到这里卡住了。因为我还是沿袭以前的思路，，但是其实就是要把实际意义给抽象清楚，这次说的其实是截取一个范围。
    }
}

下面是不考虑多余情况的一个backTrack：

1
2
3
4
5
6
7
8
9
10
if(begin==len){
    if(depth==4){
        res.add(String.join(".", path));//记住这个连接的api
    }
    return;
}

for(int i=begin;i<begin+index;i++){
    if(judgeIP(begin,i,))
}

22. 括号生成

这种生成所有可能符合条件的题目，还是应该想到回溯方法。

层数就是退出的条件。而每次做出的选择，就是是否选择)和(。一个小tip是在编程的时候想一想，一次选择的完整过程是怎样的。

如果不考虑说要列举所有的组合，一次过程可能是这样的：

1
2
3
4
5
for(int i=0;i<n;i++){
	path.add('(');
	//中间插入递归
	path.add(')');
}

但是解回溯问题一定注意的一点是，不要用for循环来推进层数。层数应该是由里面的递归来推进的。

在所有的题目中，每一层只关注这一层做的事情。比如这里，添加’(‘和’)’是一层里面的动作，外面就不要添加for循环了。

所以，一层里面的写法是：

1
2
3
4
5
6
7
8
9
10
if(条件1){
选择1
递归
}

if(条件2){
选择2
递归
}

一定要注意，当一层完成一个决定，那么就应当向下面一层推进这个决定。

这道题的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        StringBuilder path=new StringBuilder();

        backTrack(n,path,res,0,0,0);
        return res;
    }

    public void backTrack(int n,StringBuilder path,List<String> res,int depth,int open,int close){
       if(depth==n){
           res.add(path.toString());
           return;
       }
       if(open<n){//这道题只有两个决定，对于做决定的代码，只要关注这个决定的影响即可。同时，if里面是决定的条件
           path.append('(');//选择了(,因此准备添加
           backTrack(n,path,res,depth,open+1,close);//推进决定
           path.deleteCharAt(path.length()-1);//记住这个api，deleteCharAt,然后记住path.length()//返回
       }
       if(close<open){
           path.append(')');
           backTrack(n,path,res,depth+1,open,close+1);
           path.deleteCharAt(path.length()-1);
       }
    }
}

做这种题目，一定记住检查一下递归有没有还原为原来的状态。

47. 全排列 II

对于此题，出现了重复的数字。其实很容易也更应该想到的，就是先做一个排序。其实对这道题有启发的是三数之和。

150. 逆波兰表达式求值

这道题是栈的应用。

但是关键是要自己可以模拟出逆波兰表达式的解法。

注意代码如何写会比较清晰。

1.如果遇到数字，那么入栈。

2.如果遇到操作符，就将两个数字出栈，然后根据操作符对数字进行运算。将运算的结果入栈。

这里注意审题，tokens是字符串形式

所以代码如下（官方题解）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));//记住parseInt函数
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) { //switch case的写法自己也不熟
                    case "+":
                        stack.push(num1 + num2);
                        break;// 注意这里的break
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

自己的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int evalRPN(String[] tokens) {
        int len=tokens.length;
        Deque<Integer> stack=new ArrayDeque<>();
        for(int i=0;i<len;i++){
            String str=tokens[i];
            if(isNum(str)){
                stack.push(Integer.parseInt(str));
            }else{
                int num1=stack.pop();
                int num2=stack.pop();
                switch(str){
                    case "-":stack.push(num2-num1);break;
                    case "/":stack.push(num2/num1);break;
                    case "+":stack.push(num1+num2);break;
                    case "*":stack.push(num1*num2);break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isNum(String str){
        if("*".equals(str)||"+".equals(str)||"-".equals(str)||"/".equals(str))return false;
        else return true;
    }
}

198. 打家劫舍

关键是要明白一个道理，对于第i个房子，可以选择不偷。

动态规划一个要点是明确当前可以做的动作，以及如何正确清晰表现当前可以做的动作。

124. 二叉树中的最大路径和

1.每个动作的返回值是什么？记录改变值是怎样的？

2.递归的终止是什么？

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

最大路径和：注意不一定经过根节点。

对于根节点这个点来说，其希望得到的是最大值是

root.val+maxLeft+maxRight。

但是完全可能出现不经过根节点的情况。这个时候最大值可能是left.val+left.left.val+left.right.val。

这里要注意到，maxLeft本质是什么。maxLeft本质是选择放弃掉root.left的边。

所以，每个节点要计算：

​ 包含当前节点的最大值–该值和max变量比较

​ 当前节点可能的返回值–该值为了计算上层的值

同时要注意到返回值可能为负数，因此要和0做一个比较以舍去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root==null)return 0;
        getMax(root);
        return max;
    }

    public int getMax(TreeNode root){
        if(root==null)return 0;
        int left=Math.max(getMax(root.left),0);
        int right=Math.max(getMax(root.right),0);

        int  returnVal=Math.max(root.val+left,root.val+right);
        int maxVal=Math.max(returnVal,root.val+left+right);

        max=Math.max(maxVal,max);
        return returnVal;
    }
}

49. 字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        /*
        1.取出String中的每个string
        2.将String变成charArray
        3.排序。
        4.用map放下key和value
        5.将map同一个key下面的value返回
        */

        HashMap<String,List<String>> map=new HashMap();
        for(String str:strs){
            char[] charArray=str.toCharArray();
            Arrays.sort(charArray);
            //String str1=charArray.toString(); 这个写法不对诶，hashMap里面的String相等是要自己定义吗
            String str1=new String(charArray);
            List<String> list=map.getOrDefault(str1,new ArrayList<String>());
            list.add(str);
            map.put(str1,list);

        }
        List<List<String>> res=new ArrayList<>();

        for(List<String> val:map.values()){
            res.add(val);
        }
        return res;
    }
}

718. 最长重复子数组

对于一开始没有思路的题目，要学会使用暴力解法解题，然后分析暴力解法的问题，然后进行优化。

如果不考虑时间复杂度，我会怎么想这道题呢？

我会从A数组的第一个字母开始，遍历A数组字母，然后与B数组字母比较，最后获得最长的数组的长度并记录下来，伪代码如下所示：

1
2
3
4
5
对于A数组的元素：
    对于B数组的元素：
    	如果相等 计数器++
    		A数组的指针和B数组的指针加加
    	如果不等 计数器清零 然后A数组又从头开始

这个时候考虑移动A的位置，让A可以错位和B比较：

​ 1.若A的长度为i，B的长度为m。

​ 2.则A可以以B起点0的位置到B起点m的位置比较。

1
2
3
4
5
6
7
8
9
10
11
12
public int sameLength(int[] nums1,int []nums2,int addA,int addB,int len){
    int ret=0;
    
    for(int i=0;i<len;i++){//对于数组问题，一定要考虑到的是可以访问的边界
        int count=0;
        while(nums[addA+i]==nums[addB+i]){
            count++;
        }
        ret=Math.max(ret,count);
    }
    return ret;
}

外层的函数为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
```





#### [239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)

由于需要记录滑动窗口的最大值，考虑维护一个优先队列，队列维护值和索引两个量。按照值的大小进行排序。



开始将前K个数放入队列中，然后扩展窗口。扩展的过程中，添加新的数到队列中，然后获取队列的头部到答案中，但是要注意，对于索引已经不在窗内的值直接丢弃，直到数被包含在窗口内。



所以：

​	1.建立优先队列。

​	2.将K个数放入优先队列。

​	3.对优先队列的每个数，如果队首的数在范围内，添加队首的数到答案；如果不在范围，一直出队，直到队首的数在窗内。



```java
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> priorityQueue=new PriorityQueue<int[]>((pair1,pair2)->{
            return pair1[0]==pair2[0]?pair2[1]-pair2[1]:pair2[0]-pair1[0]; 
        });//记忆这里的lambda表达式，这里lambda实现了匿名类的方法之后直接就替代了匿名类
        int len=nums.length;

        for(int i=0;i<k;i++){
            priorityQueue.offer(new int[]{nums[i],i});
        }

        int[] ans=new int[len-k+1];
        ans[0]=priorityQueue.peek()[0];
        for(int i=k;i<len;i++){
            priorityQueue.offer(new int[]{nums[i],i});
            while(priorityQueue.peek()[1]<i-k+1){
                priorityQueue.poll();
            }
            ans[i-k+1]=priorityQueue.peek()[0];
        }
        return ans;
    }

}

76. 最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public String minWindow(String s, String t) {
        int[] need=new int[128];
        int[] windows=new int[128];

        /*
            1.t为被覆盖的。
            2.维护一个need数组，记录t中每个字符的个数
            3.从left=0，right=0开始开始遍历s，对于扩大窗口的时候，判断进入窗口的字符：
                1.如果是need中的元素，那么windows对应++，并且检验一下是否符合条件了
                2.如果不是need中的元素，那么直接移动
            4.当判断已经符合条件的时候，此时缩小窗口，left++，对于移出窗口的元素，如果不是need中的元素，可以继续；如果是，那么就要处理windows并处理符合的状态
        */
        int left=0;
        int right=0;
        char[] tArray=t.toCharArray();
        for(char ch:tArray){
            need[ch]++;
        }
        char[] sArray=s.toCharArray();
        int count=0;
        int start=0;
        int end=0;
        int maxL=s.length()+1;
        while(right<s.length()){
            if(need[sArray[right]]>windows[sArray[right]]){
                count++;//如果此时windows还没有对应填满，此时会增加一个计数
            }
            windows[sArray[right]]++;
            right++; 
            while(count==t.length()){//当窗口符合条件
                if(right-left<maxL){
                    maxL=right-left;
                    start=left;
                    end=right;
                }
                if(need[sArray[left]]==windows[sArray[left]])count--;//注意这里，只有当如果将left移出去就会使得不符合条件的时候，才需要跳出循环
                windows[sArray[left]]--;
                left=left+1;
            }
            
        }
        if(maxL==s.length()+1)return "";
        return s.substring(start,end);
    }
}

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

19. 删除链表的倒数第 N 个结点

478. 在圆内随机生成点

代码出现错误的点：变量名写着写着就忘记了~依靠自动补全补错变量名，记住random的api

首先是要记住一些api，比如Math.pow(num,2);再比如Math.random()

Math.random()生成[0,1）的double类型数据。

由于生成的范围都是正方形，所以对于正方形外面的要丢弃。

当然，也可以考虑用极坐标来解决问题。但是要注意极坐标在选取半径的长度的时候，半径的长度也应该符合概率分布。由于圆的面积是r^2，因此半径的概率分布应该是double d = rad * Math.sqrt(Math.random());

用第一种方法就够了吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    private double radius;
    private double x_center;
    private double y_center;

    public Solution(double radius, double x_center, double y_center) {
        this.radius=radius;
        this.y_center=y_center;
        this.x_center=x_center;
    }
    
    public double[] randPoint() {
        double x_ans=0;
        double y_ans=0;
        double x_start=x_center-radius;
        double y_start=y_center-radius;
        double distance=0;
        do{
            x_ans=x_start+radius*2*Math.random();
            y_ans=y_start+radius*2*Math.random();
            double x_distance=Math.pow((x_ans-x_center),2);
            double y_distance=Math.pow((y_ans-y_center),2);
            distance=Math.sqrt(x_distance+y_distance);
        }while(distance>radius);
        return new double[]{x_ans,y_ans};
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(radius, x_center, y_center);
 * double[] param_1 = obj.randPoint();
 */

136. 只出现一次的数字

java中的异或: ^

739. 每日温度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        /*
        1.单调栈的思路。
        2.对于还没有找到更高温度的，想要将该值存储起来。因此考虑用栈。

        1.维护一个栈，对于一个元素，先入栈，然后比较后一个元素和该元素索引对应值。如果新元素较大，那么就将旧元素出栈，然后返回结果。
        */
        Deque<Integer> stack=new ArrayDeque<>();
        int len=temperatures.length;
        int[] result=new int[len];
        for(int i=0;i<len;i++){
            while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){//是peek不是peak
                int index=stack.pop();//注意语法
                result[index]=i-index;
            }
            stack.push(i);//注意语法
        }
        return result;

    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==0)return 0;
        int left=returnLeft(nums,target);
        int right=returnRight(nums,target);

        return right-left+1;
    }
    public int returnLeft(int[] nums,int target){
        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>=target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        if(left>=nums.length||nums[left]!=target)return -1;
        return left;
    }

    public int returnRight(int[] nums,int target){
        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]<=target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        if(right<0||nums[right]!=target)return -2;//注意对范围的判断
        return right;//这道题出现的一个错误是括号的位置放置错误
    }
}

410. 分割数组的最大值

发现有些题解是讲得真清楚。https://www.bilibili.com/video/BV1rb411T7dR?from=search&seid=5879260362287173147

没有状态的时候就看看视频呗。思路很巧妙，记忆题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int splitArray(int[] nums, int m) {
        int len=nums.length;
        int max=0;
        int sum=0;
        
        for(int num:nums){
            max=Math.max(max,num);
            sum+=num;
        }

        int low=max;//集合的值最小是max
        int high=sum;//这里主要要记住的就是low和high的赋值

        while(low<high){ //这个二分搜索的边界是怎么写的值得注意，自己没有写对
            int mid=low+(high-low)/2;
            int piecies=split(nums,mid);
            if(piecies>m){
                low=mid+1;
            }else{
                high=mid;
            }
        }
        return high;
    }

    public int split(int[]nums,int count){
        int piecies=1;
        int sum=0;
        for(int num:nums){
            if(sum+num>count){
                sum=0;
                piecies++;
            }
            sum+=num;
        }
        return piecies;
    }

}
//上述解法比较固定，只能针对这道题。其实就是有一个可能的返回范围，然后进行猜数，这种返回一定范围内答案的题目可以考虑使用二分搜索，然后再计算块数的时候自己还是犯了错误，还是要小心

528. 按权重随机选择

此题实际上也是一道记忆体，因为要理解题目的意思。这里将题目的意思翻译一下：

比如说给一个数组：[1,2,7,2]

这里的意思是选择下标为1的概率是1/(1+2+7+2)。

这里我们考虑在0-sum-1的范围内随机生成一个数，其实就是实现了这里的1/sum。

由于每个数都有不同的权重，因此，我们希望，如果随机生成的randomInt在不同的范围内，对应不同的下标。以上面的数组为例：

1对应的应该是0这个数。

而2对应的是1,2这两个数。

7对应的是3,4,5,6,7,8,9这7个数。

因此，当在一定范围内产生数据之后，后面其实就是判断范围的事情了。

同时，我们观察到，判断范围的是累加和数组，比如上面。

[0,1,3,10,12]

如果是0,1,3,10取==号时是0,1,2,3这三个下标，

同时往下取。即找右边界。

29. 两数相除

这道题也主要是记忆这个方法。就是可以将数写成div*2的次幂组合的形式。

然后通过逐次减去对应的指数即

1
2
3
4
5
6
7
while(a>=b){
    while(a<b<<shift){//用上面的例子相当于是先减去4*2^2，然后减去4*2^1.类推
        shift--;
    }
    a=a-b<<shift;
    res+=1<<shift;
}

25. K 个一组翻转链表

思路其实还比较简单，见注释，不过有很多可能错误的细节：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        /*
        1.用递归的思路解决这个问题。
        2.首先分段，找到k个节点。
        3.对于k个节点做反转，传入k个节点的首节点以及后面的尾节点，返回头节点。
        4.对后面递归做这个动作，需要保证前面一段的尾部连接到后面的递归返回的头节点中
        */
        ListNode cur=head;
        for(int i=k;i>0;i--){
            if(cur==null)return head;
            cur=cur.next;
            
        }
        ListNode  tail=cur;
        ListNode returnHead=reverse(head,tail);
        head.next=reverseKGroup(tail,k);
        return returnHead;
    }

    public ListNode reverse(ListNode head,ListNode tail){
        ListNode pre=null;
        ListNode next=null;
        while(head!=tail){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}

232. 用栈实现队列

92. 反转链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        /*
        1.预留下pre节点，可以申请一个dummyHead
        2.返回一个头结点，可以被预留的节点返回
        3.预留下尾部节点最后反转的时候最后指向尾部节点
        */
        if(right==left)return head;
        ListNode dummyHead=new ListNode(0);
        dummyHead.next=head;
        ListNode pre=dummyHead;
        ListNode leftNode=dummyHead.next;
        ListNode rightNode=dummyHead.next;
        while(left-1>0){
            leftNode=leftNode.next;
            pre=pre.next;
            left--;
        }
        while(right-1>0){
            rightNode=rightNode.next;
            right--;
        }
        ListNode tail=rightNode.next;
        reverse(leftNode,tail);
        pre.next=rightNode;
        return dummyHead.next;
    }
    public void reverse(ListNode LeftNode,ListNode tail){
        ListNode pre=tail;
        ListNode cur=LeftNode;
        ListNode next=LeftNode.next;
        while(cur!=tail){
            cur.next=pre;
            pre=cur;
            cur=next;
            next=cur.next;
        }
        
    }
}

23. 合并K个升序链表

143. 重排链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        /*
        1.找到中点。
        2.反转链表
        3.连接链表
        */
        if(head==null)return;
        ListNode mid=findMid(head);
        ListNode secondHead=mid.next;
        mid.next=null;

        secondHead=reverse(secondHead);
        ListNode cur1=head;
        ListNode cur2=secondHead;
        while(cur1!=null&&cur2!=null){
            ListNode next1=cur1.next;
            ListNode next2=cur2.next;
            cur1.next=cur2;
            cur2.next=next1;
            cur1=next1;
            cur2=next2;
        }
    }

    public ListNode findMid(ListNode head){
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}

分而治之解决问题。

155. 最小栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class MinStack {

    /*
    1.使用两个栈，一个对数据进行监控，一个对当前最小值进行监控。
    */

    Deque<Integer> minStack;
    Deque<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        minStack=new ArrayDeque<Integer>();
        stack=new ArrayDeque<Integer>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty()||val<=minStack.peek()){
            minStack.push(val);
        }

    }
    
    public void pop() {
        int num=stack.pop();
        if(num==minStack.peek()){
            minStack.pop();//代码尽量写规范，自己这里写得不规范然后就报错了
            /*
            	之前的写法：
            	if(minStack.peek()==stack.pop()){
            		minStack.pop();出现了错误，是什么原因
            	}
            
            
            
            */
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

234. 回文链表

很简单的题目，但是没有注意细节，没有想清楚就可能卡住半天。

下面是错误解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode mid=findMid(head);
        mid=reverse(mid.next);
        ListNode cur1=head;
        ListNode cur2=mid;

        while(cur1!=null&&cur2!=null){
            if(cur1.val!=cur2.val)return false;
            cur1=cur1.next;
            cur2=cur2.next;
        }
        if(cur1!=null||cur2!=null)return false;//千万要注意，这个时候链表又没有断开，不能用这种方法判断
        return true;

    }

    public ListNode findMid(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        
        return slow;//这里返回的是什么用例子想一下
    }

    public ListNode reverse(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}

165. 比较版本号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int compareVersion(String version1, String version2) {
    String[] nums1 = version1.split("\\.");
    String[] nums2 = version2.split("\\.");
    int n1 = nums1.length, n2 = nums2.length;

    // compare versions
    int i1, i2;
    for (int i = 0; i < Math.max(n1, n2); ++i) {
      i1 = i < n1 ? Integer.parseInt(nums1[i]) : 0;
      i2 = i < n2 ? Integer.parseInt(nums2[i]) : 0;//记住API，前导0直接忽略
      if (i1 != i2) {
        return i1 > i2 ? 1 : -1;
      }
    }
    // the versions are equal
    return 0;
  }
}


32. 最长有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;//注意两个过程切换的时候需要做的一个初始化过程
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

468. 验证IP地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    public String validIPAddress(String IP) {
        IP=IP.toLowerCase();
        /*
        1.判断ipv4和ipv6.
        2.ipv4
            4组
            0-255 但是注意不会用0开头
            用.分隔
        3.ipv6
            8组
            16进制
            最多4个字母
            ：分割

        */
        if(IP.contains(".")){
            String[] str=IP.split("\\.",-1);//这里注意，limit=-1的情况下，这里会尽可能分割，包括分割长度为0的情况
            if(str.length!=4)return "Neither";
            for(int i=0;i<4;i++){//不允许0开头，不超过255
                String s=str[i];
                if(s.length()==0||s.charAt(0)=='0'&&s.length()>1||s.length()>3)return "Neither";
                for(int j=0;j<s.length();j++){
                    char ch=s.charAt(j);
                    if(ch>='0'&&ch<='9')continue;
                    else return "Neither";
                }
                int num=Integer.parseInt(s);
                if(num<0||num>255)return "Neither";
            } 
            return "IPv4";
        }else if(IP.contains(":")){
            String[] str=IP.split(":",-1);
            if(str.length!=8)return "Neither";
            for(int i=0;i<8;i++){
                if(!isDigit(str[i]))return "Neither";
                int len=str[i].length();
                if(len==0||len>4)return "Neither";
            }
            return "IPv6";

        }else return "Neither";
    }

    public boolean isDigit(String str){
        char[] charArray=str.toCharArray();
        for(char ch:charArray){
            if(ch<='9'&&'0'<=ch||ch>='a'&&ch<='f')continue;
            else return false;
        }
        return true;

    }

    
}

221. 最大正方形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix==null||matrix[0].length==0)return 0;
        int row=matrix.length;
        int col=matrix[0].length;
        int[][] dp=new int[row+1][col+1]; //注意这里dp预留一个1的写法，根据dp的转移式子列写dp方程
        int max=0;

        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                if(matrix[i-1][j-1]=='1'){
                    dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                }
                max=Math.max(max,dp[i][j]);
            }
        }
        return max*max;
    }
}

可以练习一下1277. 统计全为 1 的正方形子矩阵，其实是一样的解法。

128. 最长连续序列

本质是利用了set这个数据结构的查找优势来简化了步骤。

但是要注意一个trick：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0)return 0;
        HashSet<Integer> set=new HashSet<>();

        for(int num:nums){
            set.add(num);
        }
        int max=1;
        for(int num:nums){
           
            if(set.contains(num-1))continue;//对于之前遍历过的，要记得省略
            int currentNum=num;
            int currentLength=1;
            while(set.contains(currentNum+1)){
                currentLength++;
                currentNum++;
            }
            max=Math.max(max,currentLength);
        }
        return max;
    }
}

227. 基本计算器 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
    // 使用 map 维护一个运算符优先级
    // 这里的优先级划分按照「数学」进行划分即可
    Map<Character, Integer> map = new HashMap<>(){{
        put('-', 1);
        put('+', 1);
        put('*', 2);
        put('/', 2);
        put('%', 2);
        put('^', 3);
    }};
    public int calculate(String s) {
        // 将所有的空格去掉
        s = s.replaceAll(" ", "");//ATTENTION
        char[] cs = s.toCharArray();
        int n = s.length();
        // 存放所有的数字
        Deque<Integer> nums = new ArrayDeque<>();
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.addLast(0);
        // 存放所有「非数字以外」的操作
        Deque<Character> ops = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == '(') {
                ops.addLast(c);
            } else if (c == ')') {
                // 计算到最近一个左括号为止
                while (!ops.isEmpty()) {
                    if (ops.peekLast() != '(') {
                        calc(nums, ops);
                    } else {
                        ops.pollLast();
                        break;
                    }
                }
            } else {
                if (isNumber(c)) {
                    int u = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
                    nums.addLast(u);
                    i = j - 1;
                } else {

                    // 有一个新操作要入栈时，先把栈内可以算的都算了 
                    // 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
                    while (!ops.isEmpty() && ops.peekLast() != '(') {
                        char prev = ops.peekLast();
                        if (map.get(prev) >= map.get(c)) {
                            calc(nums, ops);
                        } else {
                            break;
                        }
                    }
                    ops.addLast(c);
                }
            }
        }
        // 将剩余的计算完
        while (!ops.isEmpty()) calc(nums, ops);
        return nums.peekLast();
    }
    void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast(), a = nums.pollLast();
        char op = ops.pollLast();
        int ans = 0;
        if (op == '+') ans = a + b;
        else if (op == '-') ans = a - b;
        else if (op == '*') ans = a * b;
        else if (op == '/')  ans = a / b;
        else if (op == '^') ans = (int)Math.pow(a, b);
        else if (op == '%') ans = a % b;
        nums.addLast(ans);
    }
    boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}

必须反复练习，孰能生巧。

下面是switch语句的语法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
switch(grade)//直接加大括号，不加引号
{
   case 'A' :
      System.out.println("优秀"); 
      break;
   case 'B' :
   case 'C' :
      System.out.println("良好");
      break;
   case 'D' :
      System.out.println("及格");
      break;
   case 'F' :
      System.out.println("你需要再努力努力");
      break;
   default :
      System.out.println("未知等级");
}

出现的错误：

1.hashmap的初始化语句出错。注意如何初始化。

2.swtich拼写错误，语法不熟悉。

3.有一个函数忘记实现了。

不熟练的点：对连续数的处理。以及对符号进栈时候的处理。要加强练习。

15. 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();

        int length=nums.length;
        if(length<3){
            return ans;
        }

        Arrays.sort(nums);

        for(int i=0;i<length-2;i++){  //注意是length-2
            if(nums[i]>0)break;
            if(i>0&&nums[i]==nums[i-1]){
                    continue;
                }
            int left=i+1;
            int right=length-1;
            
            while(left<right){
               
                if(nums[i]+nums[left]+nums[right]==0){
                    ans.add(List.of(nums[i],nums[left],nums[right]));//注意该语法
                   
                    while(left<right&&nums[left]==nums[left+1])left++;
                    while(left<right&&nums[right]==nums[right-1])right--;
                    left++;
                    right--;//这里忘记了移动指针，要分清楚每一步做了什么事情
                    
                }else if(nums[i]+nums[left]+nums[right]<0){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return ans;
    }
}

记忆点：

​ 三数之和的难点在于去重复的设计。这里的策略是：

​ 对于基准的外层的第一个数字i，是采用先去重，再使用的策略，就是说使用第一个有效的数字。

​ 对于外层的left和right，则首先将符合条件的加入，然后一直往后推进直到不重复。这里可能难想一点。

然后是一个kpi。 res.add(List.of(nums[i],left,right));

然后是指针移动题目，要分清楚每个if else 做的事情，不要忘记移动指针。

460. LFU 缓存

题意描述：

1.常数时间查找到节点： map存储节点。

2.常数时间更改节点。

3.插入节点时候做判断：

​ 1.排除最不常使用项目。[建立频率和双向链表映射]

​ 2.使用最不常使用中的最久不使用项目。[插入双向链表]

实现两个函数：

​ get:

​ 1.如果map有，

​ 将节点的cnt++；

​ 在原来的链表删除； 1链表删除。2.map删除。

​ 添加新的链表 1.添加链表。2.添加map。

​ 2.否则返回-1；

​ put:

​ 1.如果map有：

​ 1.获取节点。

​

​ 3.删除原来的节点，记录使用的频率。

​ 4.原来的频率加1，更新值，形成新的节点。

​ 5.新的节点插入新的频率链表。

​ 2.如果map没有：

​ 1.创建新节点，频率为1.

​ 2.插入频率为1的节点。

​ 3.判断容量是否超标。

​ 4.如果超出容量，则依据使用频率遍历列表，取出列表中的尾部节点。注意取出之后跳出。

LFU 的数据结构：

1.两个map。分别是key—node和key-list。

2.list是双向链表。

3.get操作：

​ 1.如果没有，返回-1；

​ 2.如果有，首先返回值，然后做更新操作。

​ 3.node的频率加1.

​ 4.将node从原来的list中移除。

​ 5.将node添加到现在对应的频率Dlist中。

4.put操作：

​ 1.如果已经有了，做更新操作。同时执行get即可。

​ 2.如果没有

​ 1.生成node，将node添加到频率为1的队列中。（头插入

​ 2.如果出现了capacity溢出的情况，

​ 3.如果队列为1的队列长度》1,删除队列为1 的节点，删除尾部

​ 4.如果队列为1 的队列长度为1，那么就往高频率的队列往上查找。

​ 5.特殊情况：如果capacity==0，那么就不管如何直接返回。

这里需要分析一下错误原因，之前错误的有两点：

1.一点是在remove里面管辖了map的操作，导致逻辑错误。

2另外一点是在get里面操作了节点的cnt。

因此，规定可以操作的范围是必要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package leetcodeTest;

import java.util.HashMap;
import java.util.Map;

public class leetcodeLFU {
    static class LFUCache {
        class Node{
            int val;
            int key;
            int cnt;
            Node pre;
            Node next;
            public Node(int key,int val){
                this.val=val;
                this.cnt=1;
                this.key=key;
            }
        }

        class Dlist{
            Node head;
            Node tail;
            int len;
            public Dlist(){
                head=new Node(-1,0);
                tail=new Node(-1,0);
                head.next=tail;
                tail.pre=head;
                len=0;
            }

            public void remove(Node node){
                len=len-1;
                //nMap.remove(node.key);
                Node pre=node.pre;
                Node next=node.next;
                pre.next=next;
                next.pre=pre;
            }

            public void add(Node node){
                node.next=head.next;
                head.next.pre=node;
                node.pre=head;
                head.next=node;
                len=len+1;
            }
        }

        int capacity;
        int size;

        Map<Integer,Node> nMap;
        Map<Integer,Dlist> fMap;


        public LFUCache(int capacity) {
            this.capacity=capacity;
            size=0;
            nMap=new HashMap<>();
            fMap=new HashMap<>();
            fMap.put(1,new Dlist());
        }

        public int get(int key) {
            if(!nMap.containsKey(key))return -1;
            else{
                Node node=nMap.get(key);
                int preF=node.cnt;
                node.cnt++;//2
                Dlist preList=fMap.get(preF);
               // preList.remove(node);//注意长度


                Dlist curList=fMap.getOrDefault(node.cnt,new Dlist());
                curList.add(node);//注意长度

                fMap.put(node.cnt,curList);

                return node.val;
            }
        }

        public void put(int key, int value) {
            if(nMap.containsKey(key)){
                Node node=nMap.get(key);
                node.val=value;
                //node.cnt++;
                get(node.key);
            }else{
                size++;
                Dlist list1=fMap.get(1);
                Node node=new Node(key,value);
                list1.add(node);
                nMap.put(key,node);
                if(size>capacity){
                    if(list1.len>1){
                        list1.remove(list1.tail.pre);//注意也要从nMap中删除，长度要记得变化
                        nMap.remove(node.key);
                        size--;
                        return;
                    }
                    for(int i=2;i<=fMap.size();i++){
                        Dlist list=fMap.get(i);
                        if(list.len>=1){
                            list.remove(list.tail.pre);
                            nMap.remove(node.key);
                            break;
                        }
                    }
                    size--;
                }

            }
        }
    }

    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    public static void main(String[] args) {
        LFUCache testCache = new LFUCache(2);
        testCache.put(1,1);
        testCache.put(2,2);
       // testCache.get(1);
        // get1=testCache.get(1);
       testCache.put(2,1);
       testCache.put(4,4);
       //testCache.get(2);

    }
}

43. 字符串相乘

要记忆一下相乘的策略。

这里输入是n,m位的数组，两个数组相乘的结果最多是m+n位：

​ 对于每一位，乘积的结果可能为2位数。2位数的个位放置在i+j+1的位置，十位放置在i+j的位置。

然后遵守答案，应该从前往后遍历，去掉可能存在的前导0。

不知道哪里错了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public String multiply(String num1, String num2) {
        int len1=num1.length();
        int len2=num2.length();
        if(len1==0||len2==0)return null;
        char[] num1Array=num1.toCharArray();
        char[] num2Array=num2.toCharArray();

        char[] res=new char[len1+len2];

        Arrays.fill(res,'0');

        for(int i=len1-1;i>0;i--){//这里要取到0，弄错了，没有加等号
            for(int j=len2-1;j>0;j--){
                int multiAns=(num1Array[i]-'0')*(num2Array[j]-'0')+(res[i+j+1]-'0');
                res[i+j+1]=(char)(multiAns%10+'0');
                res[i+j]=(char)(multiAns/10+res[i+j]);//注意想清楚乘法，多位相乘到底是什么情况
            }
        }

        boolean seen=false;

        StringBuilder sb=new StringBuilder();

        for(int i=0;i<len1+len2;i++){
            if(res[i]=='0'&&!seen)continue;
            sb.append(res[i]);
            seen=true;
        }

        return sb.length()==0?"0":sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public String multiply(String num1, String num2) {
        int len1=num1.length();
        int len2=num2.length();
        if(len1==0||len2==0)return null;
        char[] num1Array=num1.toCharArray();
        char[] num2Array=num2.toCharArray();

        char[] res=new char[len1+len2];

        Arrays.fill(res,'0');

        for(int i=len1-1;i>=0;i--){
            for(int j=len2-1;j>=0;j--){
                int num1Temp=(int)(num1Array[i]-'0');
                int num2Temp=(int)(num2Array[j]-'0');
                int temp=num1Temp*num2Temp+(int)(res[i+j+1]-'0');
                int tempFirst=temp%10;
                int tempSecond=temp/10;
                res[i+j+1]=(char)(tempFirst+'0');
                res[i+j]=(char)(tempSecond+'0'+res[i+j]-'0');
            }
        }

        boolean seen=false;

        StringBuilder sb=new StringBuilder();
        

        for(int i=0;i<len1+len2;i++){
            if(res[i]=='0'&&!seen)continue;
            sb.append(res[i]);
            seen=true;
        }

        return sb.length()==0?"0":sb.toString();
    }
}

错误原因：

​ 1.for循环的终止条件写错。查了很久还是没查出来。

​ 2.乘法少想了一位。

498. 对角线遍历

方向遍历题目。主要是考察细节和细心。不要怕麻烦，将矩阵的搜索移动用几个固定的算法给描述出来。

类比的想法是第54题，可以一起看看。

这里相当于试探查找。首先找到1，这个时候方向是斜向上的。然后到边界之后，开始尝试向右，向右如果在边界中，那么方向换向。然后再找。

简单描述如下：

​ 方向1查找

​ 找到边界

​ 如果可以右边走

​ 右边走

​ 换方向直到边界

​ 如果可以往下边走

​ 下边走

​ 换方向到边界

错误描述：

1.注意 1不是boolean值，要用true。

2.方向弄错，上下左右的方向弄错了。和i和j的关系弄错了。i+1是向下。然后是符号位的变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int col=mat.length;
        int row=mat[0].length;
        if(col==0||row==0) return null;
        int[]res=new int[col*row];
        int count=0;

        boolean rightUp=true;
        int i=0;
        int j=0;

        while(true){
            res[count]=mat[i][j];
            count++;
            if(count==row*col)return res;
            if(rightUp){     
                if((i-1)>=0&&(j+1)<row){// (i+1)<col&&(j+1)<row
                    i=i-1; //上
                    j=j+1; //右
                   
                }else{
                    if(j+1<row){
                        j=j+1;//右
                       
                    }else{
                        i=i+1;//下
                    }
                    rightUp=false;
                }
            }else{
                if((i+1)<col&&(j-1)>=0){
                    i=i+1;//下
                    j=j-1;//左
                   
                }else{
                    if(i+1<col){
                        i=i+1;
                    }else{
                        j=j+1;
                    }
                    rightUp=true;
                }
            }
        }

        
    }
}

322. 零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        
        Arrays.fill(dp,amount+1);
        dp[0]=0;

        for(int i=0;i<=amount;i++){
            for(int coin:coins){
                if(coin>i)continue;
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}

394. 字符串解码

用一个例子来进行分析：

​ 3[a2[c]]

​ 2[abc]3[cd]ef

考虑建立 数字栈和字符串栈（栈建立的意义是先存储再使用，数字是需要一会儿使用的，然后字符串也可能会一会儿使用，然后就考虑遇到不同的东西的时候的行为）

遇到数字：

​ 数字入栈

遇到[：

​ tail入栈

遇到字母：

​ tail.append

遇到]:

​ 1.这个时候tail应该有一串内容了。

​ 2.出栈数字，然后重复添加tail的内容。

​ 3.放入栈中。

152. 乘积最大子数组

这道题一开始想到了动态规划。但是自己否决了。因为动态规划的时候，觉得有个负数，无法判断。但是其实如果是负数的话，其实就是多维持一个最小值。自己还是应该多想一步。

维持上一个步骤的最小值和最大值，下一步再在上一步的基础上计算即可得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProduct(int[] nums) {
        int len=nums.length;
        int max=0;
        int[] minDp=new int[len];
        int[] maxDp=new int[len];
        minDp[0]=nums[0];
        maxDp[0]=nums[0];
        for(int i=1;i<len;i++){
            minDp[i]=Math.min(minDp[i-1]*nums[i],Math.min(nums[i],maxDp[i-1]*nums[i]));//要比较三个数
            maxDp[i]=Math.max((minDp[i-1]*nums[i],Math.max(nums[i],maxDp[i-1]*nums[i]));
        }

        int max=0;
        for(int num:maxDp){
            max=Math.max(max,num);
        }
        return max;




    }
}

剑指 Offer 10- II. 青蛙跳台阶问题

类似于斐波那契数列。这里难点还是dp的确立。

dp[n]=dp[n-1]+dp[n-2]。这里理解一点，之所以这里dp[n-1]和dp[n-2]是不同的两个方法，在于其最后一步一定是不一样的。比如dp[n-1]最后一步是1，而dp[n-2]最后一步是2。

另外，题目要求最后的结果要对1000000007取余。这里记住，在计算过程中取余是等价的。

191. 位1的个数

这是一道记忆题。关键是要记住这种位与然后消去1的方法：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret=0;
        while(n!=0){
            n=n&(n-1);
            ret++;
        }
        return ret;
    }
}

125. 验证回文串

审题。然后有些api忘记了自己实现就好。

224. 基本计算器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    public int calculate(String s) {
        s=s.replaceAll(" ","");
        char[] sc=s.toCharArray();
        Deque<Integer> numStack=new ArrayDeque<>();
        Deque<Character> opsStack=new ArrayDeque<>();

        int i=0;
        int len=sc.length;
        numStack.push(0);
        while(i<len){
            if(sc[i]=='('){
                opsStack.push('(');
                i++;
            }else if(sc[i]==')'){
                char op=opsStack.pop();
                while(op!='('){
                    calculate(numStack,op);
                    op=opsStack.pop();
                }
                i++;
            }else if(isDigit(sc[i])){
                int u=0;
                while(i<len&&isDigit(sc[i])){
                    int temp=sc[i]-'0';
                    u=u*10+temp;
                    i++;
                }
                numStack.push(u);
            }else{
                while(!opsStack.isEmpty()&&opsStack.peek()!='('){
                    char op=opsStack.pop();
                    calculate(numStack,op);
                }
                opsStack.push(sc[i]);
                i++;
            }  
        }
        while(!opsStack.isEmpty()){
            char op=opsStack.pop();
            calculate(numStack,op);
        }
        return numStack.pop();

    }

    public boolean isDigit(char ch){
        if(ch>='0'&&ch<='9')return true;
        else return false;
    }

    public void calculate(Deque<Integer> numStack,char ch){
        int num1=numStack.pop();
        int num2=numStack.pop();
        if(ch=='+') numStack.push(num1+num2);
        else numStack.push(num2-num1);
    }
}

这里主要是要将模拟的情况弄清楚，确保模拟的办法不要出错。

然后自己又犯下的错误是：没有注意到越界的情况，导致了越界；开始模拟的错误是，没有正确模拟，要注意如果平级的字符进去，要先计算。

模拟的要点是根据自己的例子给出方案。关键是大致思路，然后是对细节进行修补改进。解法一定要有逻辑性。

像这道题，就是通过对不同的情况进行一个分类，然后求解。

对于比如对角线遍历的问题，就是自己找规律然后描述规律看如何求解。

394. 字符串解码

自己开始的解法超出内存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public String decodeString(String s) {
        /*
        1.遇到数字，入栈。
        2.遇到字母，加入StringBuilder.
        3.遇到[将sb加入栈中。
        4.遇到],取出num，对sb repeat，然后将sb和栈内的字母相加。
        */
        Deque<Integer> numStack=new ArrayDeque<>();
        Deque<String> stringStack=new ArrayDeque<>();

        char[] sc=s.toCharArray();
        int len=sc.length;

        int i=0;
        StringBuilder sb=new StringBuilder();
        while(i<len){
            if(isDigit(sc[i])){
            int u=0;
            while(i<len&&isDigit(sc[i])){
                int temp=sc[i]-'0';
                u=u*10+temp;
                i++;
            }
            numStack.push(u);
            }else if(sc[i]=='['){
                stringStack.push(sb.toString());
                sb=new StringBuilder();
                i++;
            }else if(sc[i]==']'){
                int repeat=numStack.pop();
                StringBuilder temp=new StringBuilder(stringStack.pop());
                for(int j=0;j<repeat;i++){
                    temp.append(sb);
                }
                sb=temp;
                i++;
            }else{
                sb.append(sc[i]);
                i++;
            }
          
        }
        return stringStack.pop();
    }
    public boolean isDigit(char ch){
        if(ch<='9'&&ch>'0')return true;
        return false;
    }
}

560. 和为K的子数组

关键点是前缀和的思路，然后是之前要记住put 0。

这里的hash表主要是对比的时候省下时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int subarraySum(int[] nums, int k) {
        int len=nums.length;
        int sum=0;
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(0,1);//默认是有0，对应的情况是一个数本身为k
        int count=0;
        for(int i=0;i<len;i++){
            sum+=nums[i];
            int findx=sum-k;
            count=count+map.getOrDefault(findx,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }
}

402. 移掉 K 位数字

这里是是一个非常简单的思路：就是尽量让高位的数尽可能小就行，要多记忆这种想法。

这道题消耗的时间主要是数据结构没搞清楚，开始想用stack来做这个事情，但是实际上由于前导0的存在，还是用双端队列来做比较合适。

这里是用了一个队列来存储，来比较下一个数和队列里面的数的大小，想办法将大的数给去掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public String removeKdigits(String num, int k) {
        int len=num.length();

        Deque<Character> deque=new LinkedList<>();
        char[] nc=num.toCharArray();
        for(int i=0;i<len;i++){
            char digit=nc[i];
            while(!deque.isEmpty()&&k>0&&digit<deque.peekLast()){
                deque.pollLast();
                k--;
            }//这里是对高位的数，尽可能让高位的数小
            deque.offerLast(digit);
        }

        for(;k>0;k--){
            deque.pollLast();
        }

        boolean seen=false;
        StringBuilder sb=new StringBuilder();
        while(!deque.isEmpty()){
            char digit=deque.pollFirst();
            if(!seen&&digit=='0')continue;
            sb.append(digit);
            seen=true;
        }

        return sb.length()>0?sb.toString():"0";
    }
}

442. 数组中重复的数据

index sort题目，这道题做过，自己忘记了。可以看下面的视频：

https://www.bilibili.com/video/BV1z5411E7Zw?from=search&seid=13427860998490101079

这种题目还是手写一下，搞清楚对应的情况，然后再做比较简单。java代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int len=nums.length;
        List<Integer> list=new ArrayList<>();

        for(int i=0;i<len;i++){

            while(nums[i]!=i+1&&nums[nums[i]-1]!=nums[i]){
                swap(i,nums[i]-1,nums);
            }
        }

        for(int i=0;i<len;i++){
            if(nums[i]!=i+1){
                list.add(nums[i]);
            }
        }
        return list;
    }

    public void swap(int index1,int index2,int[] nums){
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }
}

剑指 Offer 52. 两个链表的第一个公共节点

做过好多遍了，记忆一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa=headA;
        ListNode pb=headB;
        while(pa!=pb){
            pa=(pa==null?headB:pa.next);
            pb=(pb==null?headA:pb.next);
        }
        return pa;
    }
}

556. 下一个更大元素 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int nextGreaterElement(int n) {
        long sum=0;

        char[] nums=String.valueOf(n).toCharArray();
        int len=nums.length;
        int i=len-1;
        while(i>0&&nums[i]<=nums[i-1]){
            i--;
        }
        if(i==0)return -1;
        int j=i;
        while(j<len&&nums[j]>nums[i-1]){
            j++;
        }
        swap(nums,i-1,j-1);
        reverse(nums,i);
        int ans=0;
        try{
            ans=Integer.parseInt(String.valueOf(nums));
        }catch (Exception e){
            return -1;
        }
        return ans;
    }

    public void swap(char[] nums,int index1,int index2){
        char temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }

    public void reverse(char[] nums,int index){
        int left=index;
        int right=nums.length-1;
        while(left<right){
            swap(nums,left,right);
            left++;
            right--;
        }
    }
}

每次写leetcode，调试都花了最长的时间。我怀疑其实都是因为开始做题的时候没把答案理解清楚。然后有些点就错了。因此一定要记录错误，因为这些错误就是最耗时间的。

我犯下的错误:

1.下标没有看清楚，然后下标越界。

2，注意合理的过程：

​ 首先将左边的小数和右边的大数交换之后，还要对小数之后的数进行一个翻转。这个翻转的下标我一开始弄错了。应该是左边的数的后一位而非右边的数的后一位。把答案理解清楚，慢就是快。

剑指 Offer 51. 数组中的逆序对

首先将步骤给搞清楚，弄明白：

1.明确我们是在哪一步可以确定逆序对的数量，实际上我们是在合并的时候确定逆序对的数量。

2.因此我们写一个函数首先对数组进行分裂与合并。该函数的返回值，就是这一轮的分裂和合并可以确定的逆序对的数量：

在确定参数的时候要想清楚函数里面要做如下的事情：

1.将数组切分成两部分，继续递归调用后面的函数，将子数组排列为有序

2.在得到有序的子数组之后，将两个子数组合并，得到该轮合并可以得到的逆序对的值。

拓展有小和问题：

image-20220907205845121

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
//
// 
//
// 示例 1: 
//
// 输入: [7,5,6,4]
//输出: 5 
//
// 
//
// 限制： 
//
// 0 <= 数组长度 <= 50000 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 
// 👍 497 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int reversePairs(int[] nums) {
        int len=nums.length;
        if(len<2)return 0;
        int[] copy = new int[len];
        for(int i=0; i<len; i++) {
            copy[i]=nums[i];
        }

        int[] temp = new int[len];
        return reversePairs(copy,0,len-1,temp);
    }

    public int reversePairs(int[] nums, int left,int right,int[] temp){
        if(right==left)return 0;
        int mid=left+(right-left)/2;//这里还是要注意

        int leftPair = reversePairs(nums,left,mid,temp);
        int rightPair = reversePairs(nums,mid+1,right,temp);

        if(nums[mid]<=nums[mid+1])return leftPair+rightPair;

        int mergeNum=mergeSort(nums,left,right,mid,temp);
        return mergeNum+leftPair+rightPair;
    }

    public int mergeSort(int[] nums,int left,int right,int mid,int[] temp){
        int count=0;
        for(int i=0;i<nums.length;i++){
            temp[i]=nums[i];
        }
        //下面的过程是通过递归的方式，对temp进行排序，每次挑选出两边的最小值到num中
        //一共是四种情况，包括左边排完了，右边排完了，然后还有左边小，右边小
        int i=left;
        int j=mid+1;
        for(int k=left;k<=right;k++){
            if(i==mid+1){
                nums[k]=temp[j];
                j++;
            }else if(j==right+1){
                nums[k]=temp[i];
                i++;
            }else if(temp[i]<=temp[j]){
                nums[k]=temp[i];
                i++;
            }else{
                nums[k]=temp[j];
                j++;
                count+=mid-i+1;
            }
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

回顾自己的代码，出现最大错误的原因是在遍历的时候边界没有自己敲，然后自动补全让自己错误了。注意边界条件，注意==。

394. 字符串解码

思路其实一直很简单，但是之前不知道为啥一直报错。

先把整体的思路写一写。

这里遇到不同的字符对应不同的操作：

1.数字：将数字整体当成字符串存入。

2.字符和[:作为字符串存入即可。

3.]:当遇到]的时候：

​ 先将里面的所有字符取出合并成一个字符串，注意要逆序一下。

​ 然后将数字取出，得到repeat的次数。

​ 根据repeat的次数将字符串repeat生成新的字符。

​ 放入栈中。

4.最后将栈中元素全部取出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    int ptr;

    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>();
        ptr = 0;

        while (ptr < s.length()) {
            char cur = s.charAt(ptr);
            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s);
                stk.addLast(digits);
            } else if (Character.isLetter(cur) || cur == '[') {
                // 获取一个字母并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++))); 
            } else {
                ++ptr;
                LinkedList<String> sub = new LinkedList<String>();
                while (!"[".equals(stk.peekLast())) {
                    sub.addLast(stk.removeLast());
                }
                Collections.reverse(sub);
                // 左括号出栈
                stk.removeLast();
                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }

        return getString(stk);
    }

    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++));
        }
        return ret.toString();
    }

    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }
}


晚上还是把结果写出来了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public String decodeString(String s) {
        /*
        1.因为包含括号的嵌套，因此考虑使用栈来解决该问题
        2.对于数字，直接入栈（字符串形式进去）
        3.对于[,入栈
        4.对于字符，入栈。
        5.对于]
            开始出栈，出栈的元素累积成字符串直到[为止，然后反转
            然后数字出栈，然后repeat然后放入栈中和前面的元素连接
            最后总的字符串出栈
        */

        int len=s.length();

        Deque<String> stack=new ArrayDeque<>();

        for(int i=0;i<len;i++){
            if(isDigit(s.charAt(i))){
                int u=0;
                while(i<len&&isDigit(s.charAt(i))){
                    u=u*10+s.charAt(i)-'0';
                    i++;
                }
                stack.push(String.valueOf(u));
                i--;
            }else if(s.charAt(i)==']'){
                StringBuilder sb=new StringBuilder();
                while(!"[".equals(stack.peek())){
                    sb.insert(0,stack.pop());
                }
                stack.pop();
                int num=Integer.parseInt(stack.pop());
                for(int j=0;j<num;j++){
                    stack.push(sb.toString());
                }
            }else{
                stack.push(s.charAt(i)+"");
            }
        }

        StringBuilder sb=new StringBuilder();
        while(!stack.isEmpty()){
            sb.insert(0,stack.pop());
        }
        return sb.toString();
    }

    public boolean isDigit(char ch){
        if(ch>='0'&&ch<='9')return true;
        else return false;
    }
}

犯下的错误：

1.局部循环量名字冲突。for i 内部循环变量名字写成一样了，低级错误。

2.注意栈的类型

3.坑了自己很久，就是String的比较要用equals不要用==

225. 用队列实现栈

一道非常弱智的题目，这里用一个队列实现了栈。

每次在push的时候操作，每次push元素的时候，将前面的元素poll出来然后放在队尾，相当于对于每一个push到队列中的元素，都把当前push的这个元素放到队首。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyStack {

    /** Initialize your data structure here. */
    Queue<Integer> queue;
    public MyStack() {
        queue=new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int size=queue.size();
        queue.offer(x);
        while(size>0){
            size--;
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

这里犯下的错误是之前的初始化代码和声明冲突，这完全就是不小心引起的错误。

443. 压缩字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int compress(char[] chars) {
        /*
        1.双指针遍历
            rPoint 0 开始指向读取的位置
            wPoint 0 开始指向写的位置
        2.读取的时候要做的事情：
            记录当前的字符
            记录当前的数字
        3.写的时候要做的事情
            写对应的字符
            写对应的数字
        4.外层的大循环是读指针遍历字符数组
        */

        int rPoint=0;
        int wPoint=0;
        int len=chars.length;
        while(rPoint<len){
            char cur=chars[rPoint];
            int count=0;
            while(rPoint<len&&cur==chars[rPoint]){ //指针问题边界错误，拼写错误
                count++;
                rPoint++;
            }
            chars[wPoint++]=cur;
            if(count>1){
                for(char ch:(""+count).toCharArray()){//另外注意这个首先转字符串然后转数组的方法
                chars[wPoint++]=ch;
            }
            }
            
        }
        return wPoint;
    }
}

75. 颜色分类

思路如下：

1.定义两个指针，其中一个指向0要放入的位置，一个指向2要放入的位置。

2.定义一个i，i遍历到point2就结束循环。

3.如果nums[i]==0，交换point0和nums[i]的位置。point0++,i++。因为这里point0肯定已经被遍历过了，所以只需要检测一次。

4.如果nums[i]=2，交换point2和nums[i]的位置。point2–，i++。但是注意这个时候的point2是没有做检查的，因此需要继续判断nums[i]的情况，如果是2则继续4，如果是0则继续3。

答案的程序的运行结构设计非常巧妙。while+if的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void sortColors(int[] nums) {
        int point0=0;
        int len=nums.length;
        int point2=len-1;

        for(int i=0;i<=point2;i++){//凡是指针问题，一定要关注边界
            while(i<=point2&&nums[i]==2){
                int temp=nums[point2];
                nums[point2]=nums[i];
                nums[i]=temp;
                point2--;
            }
            if(nums[i]==0){
                int temp=nums[point0];
                nums[point0]=nums[i];
                nums[i]=temp;
                point0++;
            }
        }
    }
}

912. 排序数组

下面是快速排序的一个笔记：

快速排序的步骤：

1.找出数组的左边界右边界，调用quickSort函数。

2.在quickSort函数里面调用partition函数，该函数可以将一个元素放置到应该放置的位置，然后返回该元素的位置。

3.利用partition生成的边界，确定下一轮quickSort的位置，递归调用。

4.partition做的事情是：

​ 1.选择一个为基准。

​ 2.遍历数组。

​ 3.对于比基准大的，不管；对于比基准小的将其交换到小指针所指向的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
```



#### [120. 三角形最小路径和](https://leetcode-cn.com/problems/triangle/)

谈谈我的思路过程。

看到题目的时候，我就在想是否可以用动态规划，然后参考了一下之前做过的[198. 打家劫舍](https://leetcode-cn.com/problems/house-robber/)。198是道典型的动态规划题目，两道题其实都挺像，就是说上一层的选择对下一层有影响。

198题之所以可以用动态规划，是因为每一个点的值，都是可以由前面两个点的值决定的，而前面两个点的值也是由其前方值决定的。所以虽然看起来我们有很多的选，**但是实际上一切都是注定的，利用表格就可以将动态规划的值给表示出来。**



这道三角形的题目，无非是由线性的线段点变成了二维数组而已，实际上还是一样的，只需要将每个点的最优解标注出来，那么所有的最优解都得到了。



**人生也是如此。因为我们的每一个下一次的选择，都依赖于当前的选择，因此，贪心算法是合适的。不用畏惧小概率事件，就在当前的节点出发，争取在每个时间节点获得最优解，那么就可以得到人生的最优解。**

当然，人生的难点在于，我们在一个时间点上，很难有超出该时间点的认识水平，以至于无法对自己当时的选择进行评估。但是，**我相信如果能克服自己的懒惰，努力做到现有认识水平的最优解，至少不会太过于倒霉吧。**

代码如下：

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /*
        1.f[i][j]=Math.min(f[i-1][j-1],f[i-1][j])+triangle.get(i).get(j)
        2.注意，上面的式子有一些特殊情况要考虑：
            1.0 0 =triangle.get(0).get(0)
            2.i=j的时候，j越界，因此j<i  注意这里的f[i-1][j]越界，所以这个式子要单独写
            3.上层结束后才可以到下层，因此需要按i遍历
        */
        int row=triangle.size();
        int[][] f=new int[row][row];

        f[0][0]=triangle.get(0).get(0);

        for(int i=1;i<row;i++){
            f[i][0]=f[i-1][0]+triangle.get(i).get(0);
            for(int j=1;j<i;j++){
                f[i][j]=Math.min(f[i-1][j-1],f[i-1][j])+triangle.get(i).get(j);
            }
            f[i][i]=f[i-1][i-1]+triangle.get(i).get(i);
        }

        int min=Integer.MAX_VALUE;
        for(int j=0;j<row;j++){
            if(min>f[row-1][j])min=f[row-1][j];
        }

        return min;
    }
}

1.这道题也是数组问题，因此需要判断边界。

2.注意观察数组形状，不用求col。

3.get方法。

剑指 Offer 45. 把数组排成最小的数

很累，精神状态不算好，写题写得辛苦。

仍然是注意下标的问题。首先是快排记得实在不是很清楚，必须反复记忆。然后是忘记了取==。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public String minNumber(int[] nums) {
        int len=nums.length;
        String[] sA=new String[len];
        for(int i=0;i<len;i++){
            sA[i]=String.valueOf(nums[i]);
        }

        quickSort(sA,0,len-1);

        StringBuilder res=new StringBuilder();

        for(String s:sA){
            res.append(s);
        }
        return res.toString();
    }

    public void quickSort(String[] sA,int left,int right){
        if(left>=right)return;
        int pivot=partition(sA,left,right);
        quickSort(sA,left,pivot-1);
        quickSort(sA,pivot+1,right);
    }

    public int partition(String[] sA,int left,int right){
        String pivot=sA[left];
        int swapP=left;
        for(int i=left+1;i<=right;i++){
            if((pivot+sA[i]).compareTo(sA[i]+pivot)>0)//定义如果比pivot小，那么就放到前面，如果比pivot大++
            {
                swapP++;
                swap(sA,swapP,i);
            }
        }
        swap(sA,left,swapP);
        return swapP;
        /*
        1.将pivot和后面的指针比较，
        */
    }

    public void swap(String[] sA,int index1,int index2){
        String temp=sA[index1];
        sA[index1]=sA[index2];
        sA[index2]=temp;
    }
}

93. 复原 IP 地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Stack;

public class Solution {

    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        List<String> res = new ArrayList<>();
        // 如果长度不够，不搜索
        if (len < 4 || len > 12) {
            return res;
        }

        Deque<String> path = new ArrayDeque<>(4);
        int splitTimes = 0;
        dfs(s, len, splitTimes, 0, path, res);
        return res;
    }

    /**
     * 判断 s 的子区间 [left, right] 是否能够成为一个 ip 段
     * 判断的同时顺便把类型转了
     *
     * @param s
     * @param left
     * @param right
     * @return
     */
    private int judgeIfIpSegment(String s, int left, int right) {
        int len = right - left + 1;

        // 大于 1 位的时候，不能以 0 开头
        if (len > 1 && s.charAt(left) == '0') {
            return -1;
        }

        // 转成 int 类型
        int res = 0;
        for (int i = left; i <= right; i++) {
            res = res * 10 + s.charAt(i) - '0';
        }

        if (res > 255) {
            return -1;
        }
        return res;
    }

    private void dfs(String s, int len, int split, int begin, Deque<String> path, List<String> res) {
        if (begin == len) {
            if (split == 4) {
                res.add(String.join(".", path));
            }
            return;
        }
        
        //跳出条件：如果已经遍历结束，并且有4段，那么就将path连接成字符串存入res

        // 看到剩下的不够了，就退出（剪枝），len - begin 表示剩余的还未分割的字符串的位数
        if (len - begin < (4 - split) || len - begin > 3 * (4 - split)) {
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (begin + i >= len) {
                break;
            }//对于每一个起点，考虑三种情况，就是接下来一段是1,2,3的三种情况

            int ipSegment = judgeIfIpSegment(s, begin, begin + i);
            if (ipSegment != -1) {
                // 在判断是 ip 段的情况下，才去做截取
                path.addLast(ipSegment + "");
                dfs(s, len, split + 1, begin + i + 1, path, res);
                path.removeLast();
            }
        }
    }
}

代码的整体思路：

​ 1.对长度做一个大概的判断，如果离谱直接返回。

​ 2.建立dfs函数，进行遍历：

​ 首先判断是否到了退出条件：已经到了结尾且分段数符合要求

         其次从当前点开始，分别以1,2,3位长度进行分段

​ 对分段进行判断，要求分段合理

​ 如果分段合理，那么就将该答案放入path，并进行下一轮dfs

自己写的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res=new ArrayList<>();
        int len=s.length();
        if(len<4||len>12)return res;
        Deque<String> path=new ArrayDeque<>();
        dfs(res,s,0,0,path);
        return res;
    }

    public void dfs(List<String> res,String s,int splitTime,int begin,Deque<String> path){
        int len=s.length();
        if(splitTime==4){
            if(begin==len){
                res.add(String.join(".",path));

            }else{
                return;
            }
        }
        
        if(len-begin<4-splitTime||len-begin>3*(4-splitTime))return;

        for(int i=begin;i<begin+3&&i<len;i++){
            int ans=isValidIp(s,begin,i);
            if(ans==-1)continue;
            path.addLast(ans+"");
            dfs(res,s,splitTime+1,i+1,path);
            path.removeLast();
        }
    }

    public int isValidIp(String s,int begin,int end){
        if(end-begin>0&&s.charAt(begin)=='0')return -1;
        int count=0;
        for(int i=begin;i<=end;i++){
            count=count*10+s.charAt(i)-'0';
        }
        if(count>255)return -1;
        return count;
    }
}

自己写的需要注意的是：

1.记住及时传入参数，比如String 的长度。

2.这里ArrayDeque的用法,这里使用了addLast和removeLast。

3.String.join(“.”,path)

662. 二叉树最大宽度

宽度优先搜索算法：

官方的参考题解：

1.建立一个新的数据结构的队列。

2.将root作为第一个新的数据结构的种子加入队列。

3.在队列不空的情况下

​ 弹出队列的节点

​ 分别以节点的左右节点作为种子生成新的节点并添加入队列

​ 这里要用一个深度值来记录保证每进入下一层，都可以记录下一层节点的left值，然后在每一次取出节点的时候都计算一遍宽度，求出最长的宽度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<AnnotatedNode> queue = new LinkedList();
        queue.add(new AnnotatedNode(root, 0, 0));
        int curDepth = 0, left = 0, ans = 0;
        while (!queue.isEmpty()) {
            AnnotatedNode a = queue.poll();
            if (a.node != null) {
                queue.add(new AnnotatedNode(a.node.left, a.depth + 1, a.pos * 2));
                queue.add(new AnnotatedNode(a.node.right, a.depth + 1, a.pos * 2 + 1));
                if (curDepth != a.depth) {
                    curDepth = a.depth;
                    left = a.pos;
                }
                ans = Math.max(ans, a.pos - left + 1);
            }
        }
        return ans;
    }
}

class AnnotatedNode {
    TreeNode node;
    int depth, pos;
    AnnotatedNode(TreeNode n, int d, int p) {
        node = n;
        depth = d;
        pos = p;
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/maximum-width-of-binary-tree/solution/er-cha-shu-zui-da-kuan-du-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

下面是我的答案如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null)return 0;
        Queue<myNode> queue=new LinkedList<>();
        queue.offer(new myNode(0,root));
        int max=0;
        while(!queue.isEmpty())
        {
            int size=queue.size();
            List<Integer> list=new ArrayList<>();
            for(int i=0;i<size;i++){
                myNode node=queue.poll();   
                TreeNode treeNode=node.node;
                int position=node.position;
                if(treeNode!=null){
                    list.add(position);
                    queue.offer(new myNode(position*2+1,treeNode.left));
                    queue.offer(new myNode(position*2+2,treeNode.right));
                }  
            }
            if(list.size()>=1){
                max=Math.max(max,list.get(list.size()-1)-list.get(0)+1);
            }
             
         }
         return max;
    }
    class myNode{
        int position;
        TreeNode node;

        public myNode(int position,TreeNode node){
            this.position=position;
            this.node=node;
        }
    }
}

犯下的错误：

1.首先是要注意队列里面存的是自己的myNode，因此如果要判断空的话，应该判断myNode的node属性是否为空。

2.其次是出现数组，arraylist这种，就一定要看是否会越界。

3.>=号的抉择，一定要弄清楚解题的范围。

剑指 Offer 40. 最小的k个数

经典tok 问题，不要只满足于堆排序。

还有一个用快排来解题的思路，可以看这道题：

215. 数组中的第K个最大元素

此题有两个坑点。一个是注意第K个最大元素，所以之前要将k计算出来交换位置。

另外一个是一定要将快排记忆熟练，记清楚分界指针是什么时候什么条件下移动的。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public int findKthLargest(int[] nums, int k) {
        /*
        1.每次都用partition方法确定一个元素的位置，根据这个元素的位置更换区间。
        2. int index=partition(0,nums.length);
        3.if(index==k)return nums[k];
          if(index<k) partition(index+1,nums.length);

        */
        int right=nums.length-1;
        int left=0;
        k=nums.length-k;
        do{
            int index=partition(nums,left,right);
            if(index==k)return nums[k];
            if(index<k) left=index+1;
            if(index>k) right=index-1;
        }while(true);
    }


    public int partition(int[] nums,int left,int right){
        if(right>left){
        Random rand=new Random();
        int index=left+rand.nextInt(right-left+1);
        swap(nums,left,index);
        }

        int pivot=nums[left];
        int swapI=left;
        for(int i=left+1;i<=right;i++){
            
            if(nums[i]<pivot){
                swapI++;
                swap(nums,swapI,i);
            }
        }
        swap(nums,swapI,left);
        return swapI;
    }

    public void swap(int[] nums,int left,int right){
        int temp=nums[left];
        nums[left]=nums[right];
        nums[right]=temp;
    }
}

91. 解码方法

首先根据题意简单写了一个回溯的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    int count;
    public int numDecodings(String s) {
        /*
        1.返回方法的总数：想到了回溯的解法。
        先按照回溯写一写吧
        2.回溯返回的条件：已经将s遍历完毕
        3.回溯描述：
            1.遍历s
            2.以当前字符或者当前字符的下一位为基准，判断是否有效，有效则继续，无效则放弃。
        */

        int len=s.length();
        count=0;
        dfs(s,0,len);
        return count;
    }

    public void dfs(String s,int begin,int len){
        if(begin==len){
            count++;
            return;
        }
        if(s.charAt(begin)!='0')
        dfs(s,begin+1,len);
        if(isValid(s,begin,begin+1)){
            dfs(s,begin+2,len);
        }
    }

    public boolean isValid(String s,int begin,int end){
        if(end>=s.length())return false;
        int num=(s.charAt(begin)-'0')*10+s.charAt(end)-'0';
        if(num>=10&&num<=26)return true;
        else return false;
        
    }
}

但是发现超时。

然后还有一些其他问题：

1.比如说发现’0’是没有对应编码的，这个自己要注意审题，不要弄错。

但是上面的方法是会超时的，因此考虑动态规划的想法。

这种类型的动态规划的想法其实就是递归的想法。假设知道前面的解的答案，从而得到后面的解的答案：

1.对于i位置而言，i位置可能对应的字符串的个数为：

​ 1.考虑i位置对应1个字符的情况：

​ 如果i位置不是’0’，那么f_i=f_i-1

​ 2.考虑i位置对应2个字符的情况：

​ 如果i-1–i符合条件，那么f_i=f_i-2

依据上面式子列写方程即可。

297. 二叉树的序列化与反序列化

试着写一下思路：

1.序列化的思路：

​ 1.通过dfs遍历每一个节点。

​ 2.如果遇到普通的值，那么就将该值作为字符串存入列表中；如果是null，则存入null字段。这里注意，为了区分数字和数字之间，每个字符串要用,连接。

2.反序列化的思路：

​ 1.对于上面得到的字符串，以,为单位分割为数组。

​ 2.然后遍历数组每次将list(0)作为root节点对应的值，然后remove，然后利用递归的方式将list传入，这里同样遵循先序的原则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }
  
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));//记住这个api
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }
  
    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }
  
        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);
    
        return root;
    }
}

不知道为啥按下面写的超时，也不难诶，今天状态不太行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb=new StringBuilder();
        sb=rserialize(root,sb);
        return sb.toString();
    }

    public StringBuilder rserialize(TreeNode root,StringBuilder sb){
        if(root==null){
            sb.append("NULL,");
            return sb;
        }
        sb.append(String.valueOf(root.val)+",");
        sb=rserialize(root.left,sb);
        sb=rserialize(root.right,sb);
        return sb;

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str=data.split(",");
        List<String> list=new LinkedList<>(Arrays.asList(str));
        TreeNode node=rdeserialize(list);
        return node;
    }

    public TreeNode  rdeserialize(List<String> list){
        if(list.get(0).equals("NULL")){
            list.remove(0);
            return null;
        }

        TreeNode root=new TreeNode(Integer.valueOf(list.get(0)));//思路不清晰了，这里要记得移除0
        root.left=rdeserialize(list);
        root.right=rdeserialize(list);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

459. 重复的子字符串

看下这道题的思路：

kmp以后再说吧。

比如说有一个字符串：abcabc

发现如果移动这个字符串的话：bcabca cabcab abcabc

想要出现上述组合的话，一种方式是像上面一样逐次移动字符串，另外一种方式的而话，是通过拼接的方式组合字符串，那么所谓的移动，其实就会在其中出现了。

比如 abcabc+abcabc=abcabcabcabc

其中是会包含一个abcabc的，因为其中从第3位开始相当于移动了3位。

因此，java的一行代码是：

1
return (s+s).indexOf(s,1)!=s.length();

这里注意一下，因为这里有两个s相加，因此，其肯定是存在s的，因此在s.length()的位置一定可以找到匹配的字符串。这里只有在前面存在字符串的时候，返回值才不是s.length()。

55. 跳跃游戏

思路：

以nums = [2,3,1,1,4]为例子。

这里：

nums[0]: 1,2 记录max=2

nums[1]:2,3,4

nums[2]:3

nums[3]:4

nums[4] over

思路就是每个点更新可以去的最大值，然后如果i没有到达最大值就更新。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean canJump(int[] nums) {
        int maxPosition=nums[0];
        int i=0;
        while(i<nums.length&&i<=maxPosition){
            maxPosition=Math.max(maxPosition,nums[i]+i);
            i++;
        }
        if(i==nums.length)return true;
        return false;

    }
}

这里犯下的错误：

1.注意<=符号要搞清楚意义。

2.记得任何数组相关问题不要越界。

445. 两数相加 II

有了思路以后其实就还比较简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        /*
        1.建立两个栈，将链表节点的值放在栈中。
        2.对两个栈进行出栈操作
        出栈的数进行运算，更新进位，注意这里循环条件也包括一个对进位的判断
        */
        Deque<Integer> stack1=new ArrayDeque<>();
        Deque<Integer> stack2=new ArrayDeque<>();

        ListNode point1=l1;
        ListNode point2=l2;
        while(point1!=null){
            stack1.push(point1.val);
            point1=point1.next;
        }
        while(point2!=null){
            stack2.push(point2.val);
            point2=point2.next;
        }

        int cur=0;
        ListNode head=new ListNode(0);
        while(!stack1.isEmpty()||!stack2.isEmpty()||cur!=0){
            int num1=stack1.isEmpty()?0:stack1.pop();
            int num2=stack2.isEmpty()?0:stack2.pop();
            int ans=num1+num2+cur;
            cur=ans/10;
            ans=ans%10;
            head.next=new ListNode(ans,head.next);
        }
        return head.next;
    }
}

但是要注意哈，这里犯了一个傻逼错误，三元表示多打了一个冒号。

然后这里有一个已经声明的量又声明了一遍。

63. 不同路径 II

这里假设机器人的坐标是i,j。由于每次只能向下或者向右移动一步。因此，下一轮坐标是

i+1,j 或者i,j+1。因此

如果想到达i,j 那么可以是i-1,j点也可以是i,j-1点到达。

所以可以给出递推式子：

1
f[i][j]=f[i-1][j]+f[i][j-1];

这里要注意一下：

1.i和j的边界。当i=0时,j=0时。

2.当

1
2
obstacleGrid[i][j]=0时
此时f[i][j]=0

405. 数字转换为十六进制数

这道题的思路是首先将数字转换为二进制表示（不用转换，其实只要用位运算默认就是二进制），然后每4位二进制数进行一个转换。四位二进制数刚好对应的就是10进制的1-15，所以写一个数组，然后数组完成这样的一个映射即可。

逻辑上设计用while循环来做这个事情，当num为0的时候循环结束，每次取num的低位，然后num要记得右移。

这里要注意一下对负数的处理，因为都表示成二进制了，所以直接就转换成十六进制即可。然后记住循环终止条件不能写错成num>0。因为num可能是负数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String toHex(int num) {
        if(num==0)return "0";//注意这里的特殊值处理
        char[] table="0123456789abcdef".toCharArray();
        StringBuilder sb=new StringBuilder();

        while(num!=0){
            int count=num&0xf;
            sb.insert(0,table[count]);
            num>>>=4;
        }
        return sb.toString();
    }
}

384. 打乱数组

洗牌算法的一个很好的解释：

https://www.zhihu.com/search?q=%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95&type=content

官方解法给出了下面的一个暴力答案：

1.solution里面传入原始的数组，这里要用array指向原始的数组，然后克隆一份origin数组以后备用。

2.reset里面要将array指向origin数组，然后orgin数组指向自己的克隆。

3.shuffle函数首先要得到一个拷贝数组的列表，然后要从列表中随机挑选数放到array的数组中；这里随机的下标的选择方式为rand.nextInt(aux.size())。这个函数的含义是可以随机生成0-aux.size()-1范围的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private int[] array;
    private int[] original;

    private Random rand = new Random();

    private List<Integer> getArrayCopy() {
        List<Integer> asList = new ArrayList<Integer>();
        for (int i = 0; i < array.length; i++) {
            asList.add(array[i]);
        }
        return asList;
    }

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return array;
    }
    
    public int[] shuffle() {
        List<Integer> aux = getArrayCopy();

        for (int i = 0; i < array.length; i++) {
            int removeIdx = rand.nextInt(aux.size());
            array[i] = aux.get(removeIdx);
            aux.remove(removeIdx);
        }

        return array;
    }
}

还有一个洗牌算法的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    private int[] array;
    private int[] original;

    Random rand = new Random();

    private int randRange(int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private void swapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return original;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            swapAt(i, randRange(i, array.length));
        }
        return array;
    }
}

其实洗牌算法就是一句话，就是在for循环内部，交换i和i之后的元素。

当然，也可以反方向，反方向的实现随机数就更简单。

就是第一轮是0–n-1

然后是0-n-2

0-n-3 这样的交换。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    private int[] arr;
    private int[] origin;
    private Random rand=new Random();
    public Solution(int[] nums) {
        arr=nums;
        origin=nums.clone();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        arr=origin;
        origin=origin.clone();
        return arr;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
       for(int i=arr.length-1;i>=0;i--){
           swap(i,rand.nextInt(i+1));
       }
       return arr;
    }

    public void swap(int index1,int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

注意数组到底的api是length。

207. 课程表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>()); //每一个课程都建立一个链表
        // Get the indegree and adjacency of every course.
        for(int[] cp : prerequisites) { //依赖表
            indegrees[cp[0]]++;    //
            adjacency.get(cp[1]).add(cp[0]);//链表里记录的是这个课程对应的课程
        }
        // Get all the courses with the indegree of 0.
        for(int i = 0; i < numCourses; i++)
            if(indegrees[i] == 0) queue.add(i);//先将入度为0的入队
        // BFS TopSort.
        while(!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for(int cur : adjacency.get(pre))//对邻接表的每一个元素，都可以减去一个入度
                if(--indegrees[cur] == 0) queue.add(cur);
        }
        return numCourses == 0;//最后应该所有的入度为0，即所有课程都入队并出队了
    }
}

思路解析：

1.首先建立一个数组，这个数组维持的是每一个节点的入度。初始为0

2然后建立一个二维数组，即List<List> 结构。

3.遍历题目中提供的 prerequisites二维数组。

对于每一个子数组，都ch[0]表示的是要修的课程，在对应的入度表中更新。而ch[1]表示的是需要先修的课程，在链表中对应添加ch[0]。

4.当上述二维数组和一维数组建立完毕，将入度为0的课程编号加入链表，然后对于当前的节点，找到二维数组对应的课程，然后把入度表的相应值减1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        /*
        1.创建一个数组，记录入度。
        2.创建一个二维的列表，记录节点。
        3.维持一个队列，将入度为0的节点入队，然后遍历入队。

        这里0-1表示1是0的一个入度，因此0-1是添加序号为1的列表
        */
        int[] record=new int[numCourses];
        List<List<Integer>> list=new ArrayList<>();

        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<>());//注意这里的arraylist是如何声明定义
        }

        for(int[] ch:prerequisites){
            record[ch[0]]++;
            list.get(ch[1]).add(ch[0]);
        }

        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(record[i]==0)queue.offer(i);
        }

        while(!queue.isEmpty()){
            int num=queue.poll();
            for(int course:list.get(num)){
                record[course]--;
                if(record[course]==0)queue.offer(course);
            }
            numCourses--;
        }

        return numCourses==0;

    }
}

下面的解法有样例通不过：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        /*
           1. prerequisites[1]------>[0]
           2.建立一个list<list> 用来维护每一个节点的出度，比如说pre[1] 就添加pre[0]
           每添加一个出度，就在对应的节点（[0]）的计数数组里加1
           3.维护一个队列，用来装所有入度为0的节点，实时更新。
        */

        List<List<Integer>> list=new ArrayList<>();

        int[] count=new int[numCourses];

        //这里如何将pre数组的内容更新到链表里面去卡住了，这里的策略是初始化和更新严格分开
        for(int i=0;i<numCourses;i++){
            list.add(new ArrayList<>());
        }

        for(int[] pre:prerequisites){
            count[pre[0]]++;
            list.get(pre[1]).add(pre[0]);
        }
        Queue<Integer> queue=new LinkedList<>();

        for(int i=0;i<numCourses;i++){
            if(count[i]==0)queue.offer(i);
        }

        while(!queue.isEmpty()){
            int num=queue.poll();
            for(int pre0:list.get(num)){
                count[pre0]--;
                if(count[pre0]==0)queue.offer(pre0);//怎么犯下这种低级错误呢，明明是pre0很明显的，然后写成了count[pre0].
            }
            numCourses--;
        }
        return numCourses==0;
    }
}

剑指 Offer 61. 扑克牌中的顺子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isStraight(int[] nums) {
        /*
        1.挑选出第一个数，直到第一个数不是0；
        同时，如果第一个数是0的话，count++；
        2.当挑选出第一个非0数的时候，count++，同时可以求出以该点为基准的max min
        3.继续挑数，如果新的数在上面范围内，count++，同时根据新的数求出改点的记住 max min
        */

        int max=13;
        int min=0;
        Set<Integer> set=new HashSet<>();

        for(int i=0;i<5;i++){
            if(nums[i]==0){
                continue;
            }else{
                if(nums[i]<=max&&nums[i]>=min&&!set.contains(nums[i])){
                    max=Math.min(nums[i]+4,max);
                    min=Math.max(nums[i]-4,min);
                    set.add(nums[i]);
                }else{
                    return false;
                }
            }
        }
        return true;
    }
}

犯下的错误：

1.set应该用add方法。

2.注意这里的max和min自己要想清楚怎么调整，然后==的边界情况注意。

295. 数据流的中位数

liweiwei的题解说得很清楚：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/you-xian-dui-lie-python-dai-ma-java-dai-ma-by-liwe/

思路就是观察到中位数实际上就是前后两个数组的最大值和最小值，这个时候就用堆来实现就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MedianFinder {

    /** initialize your data structure here. */
    Queue<Integer> maxQueue;
    Queue<Integer> minQueue;
    int count;
    public MedianFinder() {
        maxQueue=new PriorityQueue<>((a,b)->{
            return b-a;
        });
        minQueue=new PriorityQueue<>();
        count=0;
    }
    
    public void addNum(int num) {
        count++;
        maxQueue.offer(num);
        minQueue.offer(maxQueue.poll());

        if((count&1)!=0){
            maxQueue.offer(minQueue.poll());
        }
    }
    
    public double findMedian() {
        if((count&1)!=0){
            return (double)maxQueue.peek();
        }else{
            return (maxQueue.peek()+minQueue.peek())/(2.0);
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

犯下的错误：

1.注意java中的数据类型转换，if语句中1不是boolean类型，需要自己做一个==的判断才可以。

2.返回答案的时候，注意返回double类型，自己要在前面做一个强制类型转换。

4. 寻找两个正序数组的中位数

下面是liweiwei的答案，我写一下具体的思路。

大的思路是找分割线。这里找分割线的原则是在小数组里面找。这里以小数组的left和right作为边界，然后一直找到符合条件的边界。

这里有边界i和边界j。其中，边界i是由每次查找的区间取中间确定的，而边界j是由长度减去i所确定的。其中，区间变换的原则是用nums1[i-1]和nums2[j]比较，用nums[i]和nums2[j-1]比较。通过比较的不同情况，对边界进行调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;

        // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;
        int totalLeft = (m + n + 1) / 2;

        // 在 nums1 的区间 [0, m] 里查找恰当的分割线，
        // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
        int left = 0;
        int right = m;

        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            if (nums1[i - 1] > nums2[j]) {
                // 下一轮搜索的区间 [left, i - 1]
                right = i - 1;
            } else {
                // 下一轮搜索的区间 [i, right]
                left = i;
            }
        }

        int i = left;
        int j = totalLeft - i;

        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if (((m + n) % 2) == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
        }
    }
}


63. 不同路径 II

思路。

首先写一下不考虑任何情况的递归的方程。

这里我们明显是设立一个二维数组

1
dp[i][j]表示的是到矩阵i,j点的路径方式

由于机器人只能向下或者向右移动，因此

1
想到i,j 只能是i-1,j或者是i,j-1出发开始移动。

所以可以得到一个递推方程：

1
2
3
4
dp[i][j]=dp[i-1][j]+dp[i][j-1]
另外需要考虑障碍物的情况，一旦
    obstacleGrid[i][j]==0
    那么显然dp[i][j]==0

考虑数组的初始化，主要是对边界的初始化：

如果没有障碍物，那么上边界即i=0的点都是1，左边界即j=0的点也都是1。不过这里要注意，一旦出现了一个障碍物，那么接下来点也全部都是0。

所以可以写出如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid==null||obstacleGrid[0].length==0)return 0;

        int row=obstacleGrid.length;
        int col=obstacleGrid[0].length;

        int[][] dp=new int[row][col];

        for(int i=0;i<row&&obstacleGrid[i][0]==0;i++){ //在没有障碍物的情况下，对dp进行初始化
            dp[i][0]=1;
        }

        for(int j=0;j<col&&obstacleGrid[0][j]==0;j++){
            dp[0][j]=1;
        }

        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if(obstacleGrid[i][j]==1)dp[i][j]=0;
                else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[row-1][col-1];
    }
}

最为重要的记忆点其实就是对边界的初始化，应该算一道ease题目。

139. 单词拆分

这道题要审清楚题目。

这里说的是能否将字符串连续拆分成字典里的字符串。

这里一个思路是遍历字符串，然后对于一串序列看是否在字典里。

我们用两个指针，low和high来指定我们讨论的子串的上标和下标。其中一个思路是，我们从0出发，依次以字典里的单词的长度为顺序，查看low–low+dicString.length是与字典的子串相同。如果在一个点，都找不到相同的，那么就可以跳出循环结束；否则则继续直到字符串结束。

于是我们选择用一个数组来记录每一点的拆解情况，如果一个点可以被拆解，那么就记为true，否则为false。而只有当dp[n]=true的时候，才认为可以将单词成功拆分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len=s.length();

        boolean[] dp=new boolean[len+1];

        dp[0]=true;

        for(int low=0;low<len;low++){
            if(dp[low]==false)continue; //注意这个剪枝的边界，然后是注意dp数组的下标的+1关系
            for(String str:wordDict){
                int high=low+str.length();
                if(high<=len&&s.substring(low,high).equals(str)){
                    dp[high]=true;
                }
            }
        }
        return dp[len];
    }
}

这个视频讲得很清楚其实：https://www.youtube.com/watch?v=KppuKbiBX78&ab_channel=happygirlzt

135. 分发糖果

参考视频：https://www.youtube.com/watch?v=sHnbaKcx-Kg&ab_channel=M.C%E7%B1%B3%E5%BC%80%E6%9C%97%E5%9F%BA%E7%BD%97

思路：就是左右两次遍历。

先是向左遍历，遇到上升沿就加1。

然后是向右遍历，同样是遇到上升沿就加1。

最后将两次遍历的最大值做一个汇总即可。取两次遍历的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int candy(int[] ratings) {
        int len=ratings.length;

        int[] left=new int[len];
        int[] right=new int[len];

        Arrays.fill(left,1);
        Arrays.fill(right,1);

        for(int i=1;i<len;i++){
            if(ratings[i]>ratings[i-1]){
                left[i]=left[i-1]+1;
            }
        }

        for(int j=len-1;j>0;j--){
            if(ratings[j]<ratings[j-1]){
                right[j-1]=right[j]+1;
            }
        }
        int  ret=0;

        for(int i=0;i<len;i++){
            ret+=Math.max(left[i],right[i]);
        }

        return ret;
    }
}

279. 完全平方数

这道题其实是一道完全背包问题。不过用到了背包问题思想，完全不用全都靠背包的解法来做。而是自己想一想条件，就可以将dp方程写出来。

如果用递归来做这道题的话，希望组成的n相同的情况下，用到的数尽可能小。可以想到列举所有的情况。

用子问题的思路来求解这道题。

这里思考dp[n]和dp[n-x]的关系，假设这里x是平方数。可以写出

dp[n]=Math.min(dp[n],dp[n-x]+1);

这里注意初始化一下数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numSquares(int n) {
        /*
        1.形成完全平方数列表，列表对应i值。
        2.j是target值n。
        3.返回结果是min值。

        当然，可以用经典完全背包思路做这道题，但是也可以用背包的改编来思考这道题。
        f[n]代表的是组成n的最小数量。所以f[n]和f[n-x]的关系，可能就是f[n]=f[n-x]。不过是f[n]一直在记录最小值而已。
        dp的核心其实是记忆。
        */
        int[] dp=new int[n+1];

        Arrays.fill(dp,Integer.MAX_VALUE);

        dp[0]=0;

        for(int i=1;i*i<=n;i++){
            int x=i*i;
            for(int j=x;j<=n;j++){
                dp[j]=Math.min(dp[j],dp[j-x]+1);
            }
        }
        return dp[n];
    }
}

518. 零钱兑换 II

这道题求解的是可以凑成amount的组合的总数。说实话，刚开始拿到题目有一点儿懵。

这里考虑完全背包，即

对于第i个硬币，有两种情况

  dp[i] [j]=dp[i-1] [j]

还有一种情况我写的时候似乎遇到了困难：

​ 我开始是这样写的：

​ dp[i] [j]=dp[i-1] [j-coins[i]]

但是这样写不太对，因为coins实际上可以选择多次，因此应该改写成：

​ dp[i] [j]=dp[i-1] [j-coins[i]]+dp[i-1] [j-coins[i]*2]+dp[i-1] [j-coins[i] *3] +。。。

但是这样写很冗余，因此做完全背包的二维优化：

​ dp[j]+=dp[j-coins[i]]

329. 矩阵中的最长递增路径

要求最长的递增路径。考虑到如果要考察路径的话，可能需要对表格中的每个节点做遍历。

遍历的过程可以用递归来考虑。比如说一个节点可以有上下左右四种行走的方向。那么其最长路径的值当然是是个方向的最大值。因此以改点为起点的最大长度即可以记录在一个数组中，同时该节点前方可能也有路径到达该点，其值返回加和即可。

1.建立dp表格。

2.对于每一个表格，为起点开始遍历。

3.如果这个表格之前已经遍历过了，有值了就不遍历。

遍历过程：

1.判断边界条件。如果到了边界就返回0。

2.如果一个节点有值了，那么就返回该节点的值。

3.否则就继续递归，然后返回递归的结果+1.

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int len1=matrix.length;
        int len2=matrix[0].length;

        int[][] dp=new int[len1][len2];
        int res=0;
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(dp[i][j]==0){
                    dfs(matrix,i,j,dp,Integer.MIN_VALUE);//这里传入的是MIN_VALUE
                    res=Math.max(res,dp[i][j]);
                }
            }
        }
        return res;
    }

    public int dfs(int[][] matrix,int i,int j,int[][] dp,int prev){
        if(i>=matrix.length||j>=matrix[0].length||i<0||j<0||prev>=matrix[i][j])return 0;
        if(dp[i][j]!=0)return dp[i][j];//表格已经有值了也是一个重要返回条件

        int left=dfs(matrix,i,j-1,dp,matrix[i][j]);
        int right=dfs(matrix,i,j+1,dp,matrix[i][j]);
        int up=dfs(matrix,i+1,j,dp,matrix[i][j]);
        int down=dfs(matrix,i-1,j,dp,matrix[i][j]);

        dp[i][j]=Math.max(left,Math.max(right,Math.max(up,down)))+1;

        return dp[i][j];
    }
}

494. 目标和

0-1背包问题。见到这种题目，似乎就是套套公式就可以了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        /*
        a+b=sum
        a-b=target

        a=(sum+target)/2

        dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]

        dp[j]=dp[j]+dp[j-nums[i]]
        dp[0][0]=1

        */

        int sum=0;
        for(int num:nums){
            sum+=num;
        }

        if(target>sum||(sum-target)%2==1)return 0; //还是仔细想想count是怎么求解的

        int count=(sum-target)/2;
        int[] dp=new int[count+1];
        dp[0]=1;

        for(int num:nums){
            for(int j=count;j>=num;j--){
                dp[j]=dp[j]+dp[j-num];
            }
        }
        return dp[count];


    }
}

1981. 最小化目标值与所选元素的差

这道题是周赛的题目，自己也是看了背包之后，似乎是可以将这道题写出来了，但是可能今天精神状态都不太好，这里写的边界有一些问题。

其实这里和之前的背包一点小不同，以前的背包的话，是第i个选不选，这里的话，是第i次选选哪一个。

背包的理解可以用写dfs的方式来列写。

如果要写一个dfs的话，首先肯定要记录dfs的层数，在这里就是搜索到哪列了，另外是dfs的终结条件，什么情况下得到想要的结果：即找到了最终数的加和，所以也要维持一个加和。

所以就有了dp数组最重要的两个元素，f[i] [j] 分别对应的是：

i:-第i行。

j:当前的加和。

这里改变的结果应当是 是否可以取到j。因此设定这是一个boolean数组。

这里一个问题是可能需要引入第3个变量x，代表当前选择的数。这是和传统背包不同的地方，所以转移方程可以写成：

f[i] [j]=f[i] [j]||f[i-1] [j-x]

这里注意如果已经可以取到true的情况，要保留这个true的情况。其实也可以做一个启发，如果f[i] [j]已经是真的了，就不需要再考虑了。

下面思考如何遍历以及初始条件。

初始条件就是对于第一列的元素，可以默认其对应的j都是true的。

就是f[0] [x]都是true.符合我们的dp数组的定义。

遍历的话，当然是从前往后遍历，背包问题的遍历也很套路，就是先遍历层数i,内部遍历j。

所以就可以写出下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        /*
        f[i][j]=f[i][j]||f[i-1][j-x]
        */
        int len1=mat.length;
        int len2=mat[0].length;

        boolean[][] f=new boolean[len1][4901];

        for(int x:mat[0]){
            f[0][x]=true;
        }

        for(int i=1;i<len1;i++){
            for(int num:mat[i]){
                for(int j=num;j<4901;j++){
                    f[i][j]=f[i][j]||f[i-1][j-num];
                }
            }
        }

        int ans1=Integer.MAX_VALUE;
        int ans2=Integer.MAX_VALUE;

        for(int i=target;i<4901;i++){
            if(f[len1-1][i]==true){
                ans1=i-target;
                break;
            }
        }

        for(int i=target;i>=0;i--){
            if(f[len1-1][i]==true){
                ans2=target-i;
                break;
            }
        }

        return Math.min(ans1,ans2);

    }
}

进一步分析，这里数组开到了4901，但是target的量远小于4901。因此，可以考虑将数组开到target长度，然后对于大于target的值，直接记录即可。

208. 实现 Trie (前缀树)

https://www.bilibili.com/video/BV1uh411o7Si?from=search&seid=8344112185875136350

10. 正则表达式匹配

题意简单描述：

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所以有一下的情况：

首先试图写几个例子：

1
2
3
4
5
6
7
8
9
s=aaa
p=aaa
    
    
s=aaa
p=a*
    
s=b
p=a*b

1.首先判断首字符是否匹配。

2.然后判断第二个字符是否是*

​ 如果是*，那么既可以是

​ isMatch(s,p.substring(2))//取*为0

​ 也可以是

​ firstMatch&&isMatch(s.sbstring(1),p)//取*为n

于是又下面的递归写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isMatch(String s, String p) {
        if (p.length() == 0) return s.length() == 0;

        boolean firstMatch = s.length() > 0 &&
        (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');

        if (p.length() >= 2 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) ||
             (firstMatch && isMatch(s.substring(1), p));
        } else {
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
}

关键点：1.举出例子，先比较第一个字符。2.比较第二个字符，根据是否是*进一步判断。

dp的解法再看一下：https://leetcode-cn.com/problems/regular-expression-matching/solution/shua-chuan-lc-dong-tai-gui-hua-jie-fa-by-zn9w/

440. 字典序的第K小数字

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

class Solution {
    public int findKthNumber(int n, int k) {
        long cur = 1; //初始节点指向1
        k -= 1;//第一个节点，那么就直接k--
        
        while (k > 0) {//每次遍历都会减去k，因此当k为0的时候，就完成了遍历
            int nodes = countNodes(n, cur);//
            if (k >= nodes) {
                cur += 1;//如果k比当前节点下的节点多，那么cur就偏移一下
                k -= nodes;//k减去对应的节点数量
            } else {
                cur *= 10;//否则，cur就进入下一层，进入下一层这个过程，相当于舍弃了一个节点
                k--;//因为舍弃了一个节点，相当于k--
            }
        }
        
        return (int) cur;
    }
    
    private int countNodes(long n, long cur) { //这个代码好难想，要举例子才行
        long total = 0;
        
        long next = cur + 1;
        while (cur <= n) {
            total += Math.min(n - cur + 1, next - cur);
            cur *= 10;
            next *= 10;
        }
        
        return (int) total;
    }
}

自己的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int findKthNumber(int n, int k) {
        long cur=1; //注意是long类型
        k--;

        while(k>0){
            int nodes=countNoder(n,cur);
            if(k<nodes){
                cur=cur*10;
                k--;
            }else{
                cur=cur+1;
                k=k-nodes;
            }
        }
        return (int)cur;
    }

    public int countNoder(int n,long cur){
       long total=0;
       long next=cur+1;
       while(cur<=n){
           total+=Math.min(n-cur+1,next-cur);
           cur=cur*10;
           next=next*10;
       }
       return (int)total;
    }
}

168. Excel表列名称

一个思路题，只要记住这种思路；但是如果没有思路的话，想起来估计还挺麻烦的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder sb=new StringBuilder();

        while(columnNumber!=0){
            columnNumber--;
            sb.append((char)(columnNumber%26+'A'));//这里注意char要做一个转换
            columnNumber=columnNumber/26;
        }
        sb.reverse();
        return sb.toString();
    }
}

一个例子：

总之要注意无论是取余的时候还是/的时候都要减去1。因此直接减减就好。

GCD算法（辗转相除法）

记住下面这个图，记住跳楼梯的过程是取模即可：

image-20220907205711883

887. 鸡蛋掉落

假设鸡蛋数是K,所站立的楼层是N。

那么考虑状态之间的转移。

如果在楼层N下面的x扔了一个鸡蛋：

​ 1.鸡蛋碎了：k=k-1,N=x-1

​ 2.鸡蛋没有碎：k,N-X（注意，这里将楼层N理解为需要找寻临界点的楼层数 ）

所以可以写下面的转移方程：

f(K,N)=max(f(K-1,X-1),f(K,N-X))

这里的X通过遍历得到，注意，我们求的应该是遍历的最小值。

对于上面的函数，如果用递归的话，会计算许多中间节点，于是考虑用数组存储答案。

想用数组存储答案，首先确定一些特殊值：

这里思考下我们的程序如何设计：

1.首先是我们其实就是求一个dp[n] [k]的问题。

为了避免重复计算，我们使用一个map，利用map来将n*100+k作为key（这里是防止n+key和key之间相互冲突的一种方法），然后将对应的n,k情况的值存储在map中。

2.对于每个n,k。首先看之前是否求解过，如果没有求解过，那么首先我们知道 dp[k] [n]=Math.min(Math.max(dp[k-1] [x],dp[k] [n-x]]))

这里我们就要想办法去求dp[k-1] [x]和dp[k] [n-x]两者最大值的最小值。

然后由于上面两个值和x的关系是：

image-20210826140838217

故我们的目标就是求出x0和x1,然后取其中（两者最大值）的最小值。

又我们x的范围是0-n。且记住（数学证明）x1-x0=1

所以我们可以用二分查找来确定x1和x0。

二分查找的终止条件是 left+1=right这个时候就认为找到了。

如果说dp[k-1] [x]=t1,dp[k] [n-x]=t2

如果t1>t2 那么说明x大了,right=mid;

如果t1<t2 说明x小了，left=mid;

依照这种思路即可求解题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    HashMap<Integer,Integer> map=new HashMap<>();
    public int superEggDrop(int k, int n) {
        return dp(k,n);
    }

    public int dp(int k,int n){
        if(map.containsKey(100*n+k))return map.get(100*n+k);
        if(k==1)return n;
        if(n==0)return 0; 
        int low=1;
        int high=n;

        while(low+1<high){
            int mid=(high+low)/2;

            int t1=dp(k-1,mid-1);
            int t2=dp(k,n-mid);

            if(t1>t2){
                high=mid;
            }else{
                low=mid;
            }
        }

        int ans=Math.min(Math.max(dp(k-1,low-1),dp(k,n-low)),Math.max(dp(k-1,high-1),dp(k,n-high)))+1; //状态转移方程要想清楚，不然会做的题会做错
        map.put(n*100+k,ans);
        return ans;
    }
}

不要把上面的题目当成多难的题目。其实就是求出了一个稍微复杂的dp数组，然后改数组需要用二分法确定一下范围，仅此而已。

400. 第 N 位数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findNthDigit(int n) {
        if(n==0)return 0;
        int  digit=1;
        long start=1;
        long countIndex=digit*9*start;

        while(n>countIndex){
            n=n-(int)countIndex;
            start=start*10;
            digit=digit+1;
            countIndex=digit*9*start;
        }

        long num=start+(n-1)/digit;
        int bitSet=(n-1)%digit;

        return (int)((String.valueOf(num).charAt(bitSet))-'0');
    }
}

此题最后要注意一下输入的值可能不讲武德，虽然输入在int类型内，可是可能会导致start和countIndex超出范围。

然后就是一个找规律题。

这里最后的n-1是一个巧妙的思路。

剑指 Offer 54. 二叉搜索树的第k大节点

自己的解法，总是不知道哪里有错：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int count;
    int ans;
    public int kthLargest(TreeNode root, int k) {
        count=k;
        ans=0;
        search(root);
        return ans;
    }

    public void search(TreeNode root){
        if(root==null)return;
        
        search(root.left);
        if(count==0)return;

        if(--count==0)ans=root.val;
        search(root.right);
    }
}

最后发现是right和left写反了。

这个写反不仅仅是不小心，更是没有搞清楚题意。题目说的是第K大的，这就要求要降序排列。因此是中序排列的倒序。即先遍历right再遍历left。

二叉搜索树与双向链表

思路是中序遍历然后建立双链表。

这里一个点就是需要维护一个head和pre。

在遍历一个点的时候的行为是：

1.pre.right=root;

root.left=pre;

pre=root;

用图画一下理解一下。

对于head为空的情况，证明之前没有pre，所以这个时候要head==null。

觉得是一道记忆题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    Node pre=null;
    Node head=null;
    public Node treeToDoublyList(Node root) {
        /*
            1.边界条件，如果是root那么就返回。
            2.对root做dfs操作。
            3.对首部和尾部的节点做操作处理
        */
        if(root==null)return root;
        dfs(root);
        head.left=pre;
        pre.right=head;
        return head;
    }
    public void dfs(Node root){
        if(root==null)return;
        dfs(root.left);
        if(head==null)head=root;
        else pre.right=root;
        root.left=pre;
        pre=root;
        dfs(root.right);
    }
}

98. 验证二叉搜索树

这道题一个直观的思路是利用中序遍历，记录一下上次遍历的点，然后比较当前节点和上次遍历节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode pre;
    public boolean isValidBST(TreeNode root) {
        pre=null;
        return dfs(root);
    }

    public boolean dfs(TreeNode root){
        if(root==null)return true;
        boolean left=dfs(root.left);

        if(pre!=null&&pre.val>=root.val)return false;
        pre=root;
        boolean right=dfs(root.right);
        return right&&left;
    }
}

其实和转成双链表挺像的，可以联系起来复习。

97. 交错字符串

建议自己用一个例子过一遍，这道题就是靠记忆，我觉得没法想出来。

其实就还是像用双指针一样做对比，不过用了一个dp数组来做记录。

其中，初始化dp数组为真，然后后面就是判断s1和s2对应的字符是否能与s3契合。

官方题解讲得还行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1=s1.length();
        int len2=s2.length();
        int len3=s3.length();

        if(len1+len2!=len3)return false;

        boolean[][] dp=new boolean[len1+1][len2+1];

        dp[0][0]=true;

        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                int p=i+j-1;
                if(i>0)dp[i][j]=dp[i][j]||(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(p));
                if(j>0)dp[i][j]=dp[i][j]||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(p));
            }
        }
        return dp[len1][len2];
        
    }
}

这里最好理解一下dp数组的下标含义。其中，dp[0] [0]意义是s1和s2都为空的时候，因此此时为真。

而dp[1] [1]意义是s1和s2中的第一个元素是否可以交错组合成s3的前两个元素。因此dp[1] [1]比较的自然是s.charAt(i-1)即下标里面的0元素。

另外考虑一下如何优化这个数组。

优化数组的事情最好绘制一个图来实现

不过我看了一下图，觉得这道题其实不是很好用滚动数组来解释。因为这里其实相当于以s2为基准，dp通过的要求是做两次检验，有一次可以通过即可以接受，然后优化为一个维度的数组作这件事情即可。

剑指 Offer 34. 二叉树中和为某一值的路径

说实话，人傻了，一个低级错误卡了半天。

因此，要养成做完题过一遍代码的习惯。能省时间而不是费时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null)return res;

        dfs(root,target,res,new ArrayList<>());
        return res;
    }

    public void dfs(TreeNode root,int target,List<List<Integer>> res,List<Integer> list){
        if(root==null)return;
      if(root!=null&&root.left==null&&root.right==null){ //这个低级错误是把树的轴给写错了
          if(target-root.val==0){
              list.add(root.val);
              res.add(new ArrayList<>(list));
              list.remove(list.size()-1);
          }else return;
      }

      list.add(root.val);
      dfs(root.left,target-root.val,res,list);
      dfs(root.right,target-root.val,res,list);
      list.remove(list.size()-1);
        

    }
}

18. 四数之和

发现自己的编码习惯是真的差劲。

在变量改变的时候，用if 语句，结果下面没写else，然后就继续执行if语句了。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        /*
        1.排序
        2.确定第一个数
        3.确定第二个数。尤其记忆的是为了防止重复而做的判断。
        4.双指针靠拢。
        */

        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<>();

        int len=nums.length;
        if(len<4)return res;

        for(int i=0;i<len-3;i++){
            if(i>0&&nums[i]==nums[i-1]){ //这个要记忆啊
                continue;
            }
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)break;
            if(nums[i]+nums[len-1]+nums[len-2]+nums[len-3]<target)continue;
            for(int j=i+1;j<len-2;j++){
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target)break;
                if(nums[i]+nums[j]+nums[len-1]+nums[len-2]<target)continue;
                int left=j+1;
                int right=len-1;
                while(left<right){
                    while(left>j+1&&left<right&&nums[left]==nums[left-1])left++;
                    while(right<len-1&&right>len&&nums[right]==nums[right+1]) right--;
                    if(left>=right)break;
                    if(nums[i]+nums[j]+nums[left]+nums[right]==target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;
                        right--;
                    }
                    else if(nums[i]+nums[j]+nums[left]+nums[right]<target) left++;
                    else right--;
                }
            }
        }

        return res;
    }
}

剑指 Offer 62. 圆圈中最后剩下的数字

约瑟夫环问题。

记忆的题目。关键是理解倒推的思路。

比如说下面的例子：

0 1 2 3 4

3 4 0 1

1 3 4

1 3

3

每次删除第3个。

我们可以确定，最后我们求的那个数的下标是0。那么我们就可以推出该数在上一轮的下标。

求法是（cur+m)%arrayNum

即是（前一轮的下标+偏移的位置）%数组上一轮的长度。

因此，数组的长度是从2到n。

前一轮的下标从0开始更新。

所以可以写出下面的代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int lastRemaining(int n, int m) {
        int ans=0;

        for(int i=2;i<=n;i++){
            ans=(ans+m)%i;
        }
        return ans;
    }
}

37. 解数独

看这个视频题解即可：https://www.youtube.com/watch?v=ZV0InYdJKYw&t=185s&ab_channel=happygirlzt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public void solveSudoku(char[][] board) {
        /*
        1.大循环遍历每一个点，如果是空，那么就进行判断。
        2如果说大循环可以顺利结束，那么就返回。
        3.中间需要判断是否可以填入点，判断方式包括：
            1.行
            2.列
            3.3*3矩阵：
                确定矩阵所在的行：3*(row/3)+i/3
                确定矩阵所在的列：3*(col/3)+i/3
        */
        helper(board);
        
    }

    public boolean isValid(char[][] board,int row,int col,char k){
        for(int i=0;i<9;i++){
            if(board[row][i]==k)return false;
            if(board[i][col]==k)return false;
            if(board[3*(row/3)+i/3][3*(col/3)+i%3]==k)return false;//这是找同一个矩阵的相同的值的一个trick
        }
        return true;
    }

    public boolean helper(char[][] board){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]=='.'){
                    for(char k='1';k<='9';k++){
                        if(isValid(board,i,j,k)){
                            board[i][j]=k;
                            if(helper(board))return true;
                            board[i][j]='.';
                        }
                    }return false;
                }
            }
        }
        return true;
    }
}

84. 柱状图中最大的矩形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int largestRectangleArea(int[] heights) {
        /*
        1.维护一个栈，存储下标。
        2.其中，入栈和出栈的原则是：
            如果遇到一个比栈顶大的数：入栈
            如果遇到一个比栈顶小的数：将栈里的数先出栈，计算之前的栈内元素所可以组成的矩形的大小
            更新维护最大值
        */
        Deque<Integer> stack=new ArrayDeque<>();
        stack.push(-1);
        int len=heights.length;
        int max=0;
        for(int i=0;i<len;i++){
            while(stack.peek()!=-1&&heights[i]<=heights[stack.peek()]){
                max=Math.max(max,heights[stack.pop()]*(i-stack.peek()-1));
            }
            stack.push(i);
        }//这个时候栈内的元素都是单调递增的

        while(stack.peek()!=-1){
            max=Math.max(max,heights[stack.pop()]*(len-stack.peek()-1));
        }
        return max;


    }
}

这道题最为重要的思想就是边界的确定。如果维持栈内的数据是单调增加的话，那么最终计算的时候，相当于右边的边界就是n，而左边的边界就是栈内的元素。在入栈过程中，遇到较小值出栈的时候，相当于是找到了左边界，而由于前面的数比当前数小，因此右边界也是确定，因此可以用上述写法。

547. 省份数量

虽然深度优先直接想出来了，但是还是看了下思路找想到用深度优先。

联通图有机会可以想一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int findCircleNum(int[][] isConnected) {
        /*
        1.深度优先的思路其实就还比较平和。
        2.就是维护一个访问数组，如果有一个节点在大循环里没有被访问过，那么计数器就++
        3.然后对于一个新的节点，利用dfs，将其周围的点全部都访问。这样计数器只有在新连通图的时候才++
        然后注意 isConnected[i][j] 表示第i个点和第j个点相连
        */
        int len=isConnected.length;
        boolean[] visited=new boolean[len];
        int cnt=0;
        for(int i=0;i<len;i++){
            if(!visited[i]){
                cnt++;
                dfs(i,isConnected,visited);
            }
        }
            return cnt;
    }

    public void dfs(int i,int[][] isConnected,boolean[] visited){
        if(visited[i])return;
        visited[i]=true;
        for(int j=0;j<isConnected.length;j++){
            if(isConnected[i][j]==1&&!visited[j]){
                dfs(j,isConnected,visited);
            }
        }

    }
}

16. 最接近的三数之和

显然自己把三数之和给忘记了~~~

有些操作就不对，有时间复习一下三数之和（其实昨天刚写了四数之和）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        //思路和三数之和一样应该
        int ans=100000;
        Arrays.sort(nums);
        int len=nums.length;

        for(int i=0;i<len-2;i++){
            while(i>0&&i<len-2&&nums[i]==nums[i-1])i++;
            int left=i+1;
            int right=len-1;
            while(left<right){
                int num=nums[i]+nums[left]+nums[right];
                if(num==target)return target;
                if(Math.abs(num-target)<Math.abs(ans-target))ans=num;
                if(num>target)right--;
                else left++;
            }
            //if(ans>target)return ans;这个减枝操作是错误的
        }
        return ans;
    }
}

剑指 Offer 33. 二叉搜索树的后序遍历序列

这道题还是要画图自己看着理解一下。

本质是利用画图之后节点之间的关系来解题。

思路如下：

1.给定数组的首部和尾部。

2.遍历寻找第一个大于尾部的数（就是找左右子树的分界点）

3.找到分界点后，遍历后半部分（即右子树），看是否有小于尾部节点的点（不能小，小就错了）

4.递归搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recurn(postorder,0,postorder.length-1);
    }
    public boolean recurn(int[] postorder,int begin,int end){
        if(begin>=end)return true;
        int i=begin;
        
        while(postorder[i]<postorder[end]){
            i++;
        }
        int mid=i;
        while(postorder[i]>postorder[end]){
            i++;
        }
        return  i==end&&recurn(postorder,begin,mid-1)&&recurn(postorder,mid,end-1);
    }
}

678. 有效的括号字符串

首先是一个左右两边遍历的思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean checkValidString(String s) {
        int left=0;
        int right=0;
        int star=0;

        int len=s.length();

        for(char ch:s.toCharArray()){
            if(ch=='(')left++;
            if(ch==')')right++;
            if(ch=='*')star++;
            if(right>star+left)return false;
        }
        if(left>right+star)return false;

        left=0;
        right=0;
        star=0;

        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)==')')right++;
            if(s.charAt(i)=='(')left++;
            if(s.charAt(i)=='*')star++;
            if(left>right+star)return false;
        }
        if(right>left+star)return false;

        return true;
        
    }
}

还有一个比较巧妙的思路：

维持一个low和一个high，这个low和high维持的是（括号的平衡性，比如出现了一个（，那么low和high都++。

如果不是左括号，那么low–。对于high来说，则判断是否是右括号，如果是右括号，那么减去1，否则加上1。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean checkValidString(String s) {
       int lo = 0, hi = 0;
       for (char c: s.toCharArray()) {
           lo += c == '(' ? 1 : -1;
           hi += c != ')' ? 1 : -1;
           if (hi < 0) break;
           lo = Math.max(lo, 0);
       }
       return lo == 0;
    }
}

题解：https://leetcode.com/problems/valid-parenthesis-string/solution/

528. 按权重随机选择

思路很清晰的题目。把代码看一下就行。

先求出前缀和，然后随机出一个数出来。

这里是 int targ = rand.nextInt(tot); 这样一个生成的下标的范围。

我写的不知道哪里错了：

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

    List<Integer> list=new ArrayList<>();
    Random rand=new Random();
    int tot;
    public Solution(int[] w) {
        tot=0;
        for(int num:w){
            tot+=num;
            list.add(num);
        }
    }
    
    public int pickIndex() {
        int target=rand.nextInt(tot);
        int low=0;
        int high=list.size()-1;
        while(low!=high){
            int mid=(high+low)/2;
            if(target>=list.get(mid))low=mid+1;
            else high=mid;
        }
        return low;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */

525. 连续数组

这道题也是一个思路题。

具体的思路是：

由于nums里面只有0和1，想要0和1达到平衡，那么就计算数组的前缀和就好了。

比如0 1 0 1 0 0 0 1

前缀和就是：

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

那么就知道了 前缀和相同的下标间的数组肯定是平衡的（相当于+1和-1的数量是相同的）

但是有了这个思路之后还是要考虑要范围的问题（利用前缀和求解的时候都要想一想前缀和如何初始化的问题）

这里如果是0 1 0 1

那么前缀和是

-1 0 -1 0 那么显然有问题。因为最后一个前缀和显示不出效果。

所以前缀和可以多设置一个。初始前缀和为0.

用下面例子检验一下：

0 0 0 1 0 1 0 1 0 1 0 1 0

-1 -2 -3 -2 -3 -2 -3 -2 -3 -2 -3

所以前缀和要多一个。然后用map查找前缀和相同的下标的值的差距即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMaxLength(int[] nums) {
        /*
     
        */
        int[] count=new int[nums.length+1];
        for(int i=1;i<count.length;i++){
            count[i]=count[i-1]+(nums[i-1]==0?-1:1);
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        int ans=0;
        for(int i=0;i<count.length;i++){
            if(!map.containsKey(count[i]))map.put(count[i],i);
            else ans=Math.max(ans,i-map.get(count[i]));
        }
        return ans;

    }
}

多试几个例子，然后总结下规律就可以了。

leetcode50的视频题解：https://www.youtube.com/watch?v=DKt7DAgJjbk&ab_channel=happygirlzt

42. 接雨水

这道题有几个点。

首先是如何求单独一列的储水量。这个可以看题解：

https://leetcode-cn.com/problems/trapping-rain-water/

其实就是想象一下，对于单独一列，其存水量就是两边最高的两个柱体中最矮的那一边减去当前的。

有了这个思路之后，就是一个双指针的问题。

首先是一个计算列存水量的指针。根据题意，这个指针的范围当然是1—-length-2.

然后另外有一个存储maxLeft和maxRight的数。这两个数在不同的情况下进行更新。

然后如何保证每次都可以选择maxLeft和maxRight中较小的数进行计算呢？

这里通过控制每次指针所指向的旁边最近的高度值来实现，只要控制住在旁边最近的值中，每次更新小的那边就可以了。

核心代码逻辑如下

(int i 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    //从左到右更
    if (height[left - 1] < height[right + 1]) {//这里就是每次都选择小的一边更新
        max_left = Math.max(max_left, height[left - 1]);
        int min = max_left;
        if (min > height[left]) {
            sum = sum + (min - height[left]);
        }
        left++;
    //从右到左更
    } else {
        max_right = Math.max(max_right, height[right + 1]);
        int min = max_right;
        if (min > height[right]) {
            sum = sum + (min - height[right]);
        }
        right--;
    }
}


300. 最长递增子序列

最基本的一个思路：

1.动态规划。直接看代码就行。就是说对于每一个nums[i]，都可以比较i前面的哪一个元素比当前元素小，然后将当前元素接在对应的元素前面，然后进行更新。注意一下的是循环过程。核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}


这道题另外有一个思路，是更新tail值的思路。

image-20220907205618268

维护一个tail的数组，保证tail是递增的，如果新出现的数比tail小，那么就替换掉tail中最后一个比这个数大的数。

这样做的目的其实是因为长度其实都已经记录在res里面了，上图的情况中，如果下一个数是1，那么tail应该更新成为：

1 3 7

如果后面出现的数比7大，那么就相当于1没有替换。

如果后面出现的数比7小，那么其实就是替换前面的3，长度也没有增长。这个思路自己调试一下就可以跑通。

然后题目中为了优化，做了一个二分查找。这里找的逻辑是：

1.如果nums[mid]<num,那么left=mid+1

2.如果>=num,那么right=mid

同时注意什么时候更新长度：在最后取到右边界的时候更新长度。

416. 分割等和子集

背包问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
参考代码：
    class Solution {
    public boolean canPartition(int[] nums) {
        /*
        1.如果可以分割，那么一定存在着dp[i]
        2.选择一定数，然后成为一个target这件事情，也可以分解成这个问题的子问题：
            dp[i][j]= dp[i-1][j]||dp[i-1][j-nums[i]];
        3.如果是背包的话，那么：
            在第i个选择，且容量为j的情况下，也可以分解为这个问题的子问题：
            dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-nums[i]])
        */

        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        if((sum&1)==1)return false;
        int target=sum/2;

        int len=nums.length;
        
        int[] dp=new int[target+1];
        dp[0]=true;

        //dp[j]=dp[j]||dp[j-nums[i]]

        for(int i=0;i<len;i++){
            for(int j=0;j<target+1&&j>nums[i];j++){
                dp[j]=dp[j]||dp[j-nums[i]];
            }
        }
    }
}
1
2
3
4
5
6
7
8
while(left+1<right&&nums[left+1]==nums[left]){
                           left++;
                           count++;
                       }
                       while(left<(right-1)&&nums[right-1]==nums[right]){
                           right--;
                           count++;
                       }