跳至主要內容

LeetCode题库

PPLong大约 188 分钟

LeetCode 题库

🌍 当前题库题目数:  

WANTED 📜

JZ-03. 两数相加 ⭐

Time: 2021/4/6 09:46:00
Tag: # Foreach# Foreach# Foreach
2021/4/6 09:46:00
Hash
Replace
image-20210308090153998
image-20210308090153998

思考:

未排序、有重复数字、找出的是任意的重复数字、所有数字大小都在0---n-1的范围内、输出的是重复的那个数字

1. 基于哈希表

       Map map = new  HashMap();
        int i = 0;
        while(i<nums.length){
            if((int)map.getOrDefault(nums[i],-1) != -1){
                return nums[i];
            }
            map.put(nums[i], nums[i]);
            i++;
        }
        return -1;
image-20210308092439462
image-20210308092439462

时间复杂度 O(N) 空间复杂度 O(N)

2. 原地置换nb

这里确实 应该多看题目给的数字范围在0--n-1思考,这是解这道题的关键,之前的哈希表是没有用到这个条件的

 int temp;
        for(int i =0; i<nums.length; i++){
            while(nums[i] != i){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
          
        }
       return -1;

理解这里的思想主要是自己想一个数组一步步去进行 有点桶排序的感觉?

image-20210308124958004
image-20210308124958004

这里最后发现问题的关键是 n-1范围内, 索引为i对应的位置上肯定是 i ,然后去判断时 发现重复的元素,肯定是在他的值对应的索引上去找的,如果有这个值,则找到了,没有,则说明还未填上,则填上。

这里主要是还是要掌握桶排序的思想,先去思考能不能通过ON的方式解决问题

JZ-04. 二维数组中的查找 ⭐⭐

image-20210310083059606
image-20210310083059606

观察:

每行递增、每列递增

1. 自己想的矩阵分割法

2. 翻转矩阵 / 线性搜索

​ 矩阵的右上角开始

int j = matrix[0].length-1;
int i = 0;
int num = 16;
while(true){
    if(i<0||j<0) break;
    if(matrix[i][j]>num) j--;
    else if(matrix[i][j]<num) i++;
    else if(matrix[i][j] == num)
        System.out.println(num);

JZ-07. 重建二叉树 ⭐⭐

2021/4/12 12:03:00
Recursion
Tree

1. 递归

前提理论: 对于任何一棵树而言,前序遍历形式为: [根节点,[左子树的前序遍历结果],[右子树的前序遍历结果]][根节点, [左子树的前序遍历结果], [右子树的前序遍历结果]]

中序遍历形式为[[左子树的中序遍历结果],根节点,[右子树的中序遍历结果]][[左子树的中序遍历结果], 根节点,[右子树的中序遍历结果]]

所以思路大概可以确定:

  1. 通过前序遍历找到根节点
  2. 通过根节点在中序遍历中确定其左右子树
  3. 对子树进行同样的操作,但需要注意的是,在子树的划分过程中,要考虑 界限 的问题
    • 如果是左子树则左边界与父节点保持一致,修改右边界为父节点的前一个位置
    • 如果是右子树则右边界与父节点保持一致,修改坐边界为父节点的后一个位置

可以理解为:构建过程在前序遍历中顺序推动,在中序遍历中动态查找并确定子树范围

class Solution {
    static int preIdx = 0;
    static Map<Integer, Integer> inMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inMap= new HashMap<>();
        for(int i = 0; i < preorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        preIdx = 0;
        return build(preorder, inorder, 0, preorder.length - 1);
    }

    public TreeNode build(int[] preorder, int[] inorder, int l, int r) {
      	// notice the problem of bound overflow
        if(preIdx >= inorder.length || r < l ) {
            return null;
        }
        if(r - l == 0) {
            // Don't forget to increment `preIdx`
            preIdx++;
            return new TreeNode(inorder[l]);
        }
        // Optimize: use map to reduce each foreach below
        int inIdx = inMap.get(preorder[preIdx++]);
        TreeNode node = new TreeNode(inorder[inIdx]);
      	// the key to show recursion
        node.left = build(preorder, inorder, l, inIdx - 1);
        node.right = build(preorder, inorder, inIdx + 1, r);;
        return node;
    }
}

JZ-10. 青蛙跳台阶 ⭐

2021/4/6 09:46:00
DP
image-20210315090449362
image-20210315090449362

思考

就是拼砖头的递归思想

返回格式 ()+1

1. 递归(超时)

if(num == 0 || num == 1){
    return   1;
}
if(num == 2){
    return 2;
}
 return getMax(num-2)+getMax(num - 1) ;

递归的时间复杂度是On*n 空间复杂度 On 所以肯定超时了

2. 动态规划

典型的斐波那契数列问题,艹,就是一个三个缓存数进行斐波那契数列的运算

为什么是斐波那契?

以后看算法题的时候,先看其通项结构

f(n) = f(n-1) + f(n-2)

         int a = 1;
            int b = 1;
            int sum = 0;
            for(int i =0;i< num;i++){
            sum = (a+b)%1000000007;
            a = b;
            b = sum;
         }
         return a;

时间复杂度 On 空间复杂度 O1

image-20210315092525503
image-20210315092525503

JZ-12. 矩阵中的路径

2023/4/13 17:49:00
DFS
Incursion

1. 回溯 DFS

思路,

  • 开辟同纬度标志位数组
  • 如果当前元素满足条件,则设置标志数组表明该位置的元素已被访问,同时进行以下操作
    • 对该元素周围(上下左右)对字符进行下一个word字符的检索。
    • 如果都不符合条件,则表明在该元素不符合条件,含有该位置的元素无法构成最终的word单词。将元素上的标志位还原(以便其他位置的元素进行判断)
  • 如果当前元素不满足条件,则返回false
class Solution {
    public boolean exist(char[][] board, String word) {
        int[][] flags = new int[board.length][board[0].length];
      	// puffed code, need optimize
        boolean res = false;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                // optimize, no need for foreach if res is true
                if(res) {
                    return true;
                }
                // mutiple check to cover all conditions
                if(board[i][j] == word.charAt(0)) {
                    res = dfsFindCurChar(board, flags, word, i, j, 0);
                }
            }
        }
        return res;
    }

    
    public boolean dfsFindCurChar(char[][] board,int[][] flags,  String word, int i, int j, int index) {
        if(index == word.length()) {
            return true;
        }
        // avoid bound overflow
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
         // if flag is already dropped in at
        if(flags[i][j] == 1) {
            return false;
        }
        if(board[i][j] == word.charAt(index)) {
            flags[i][j] = 1;
            // can be optimzed
            boolean onRight = dfsFindCurChar(board, flags, word, i+1, j, index+1);
            boolean onLeft = dfsFindCurChar(board, flags, word, i-1, j, index+1);
            boolean onDown = dfsFindCurChar(board, flags, word, i, j+1, index+1);
            boolean onUp = dfsFindCurChar(board, flags, word, i, j-1, index+1);
            // need optimze
            if(onRight || onLeft || onDown || onUp) {
                return true;
            }
        }
        // if not equate to the char, we need to reset this flag to ensure another incursion could work.
        flags[i][j] = 0;
        return false;
    
    }
}

优化

一个小的优化例子,比较有趣,不用设置额外的标志位来进行,仅需要把board字符数组中的元素设置为指定字符表明该字符已被访问过即可,并且在失败时进行还原(通过word)即可。

class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                // code optimization
                if(dfsFindCurChar(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
    
    public boolean dfsFindCurChar(char[][] board,  String word, int i, int j, int index) {
        if(index == word.length()) {
            return true;
        }
        // avoid bound overflow
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        // if flag is already dropped in at
        if(board[i][j] == '\0') {
            return false;
        }
        if(board[i][j] == word.charAt(index)) {
            board[i][j] = '\0';
            // can be optimzed
            boolean onRight = dfsFindCurChar(board, word, i+1, j, index+1);
            boolean onLeft = dfsFindCurChar(board, word, i-1, j, index+1);
            boolean onDown = dfsFindCurChar(board, word, i, j+1, index+1);
            boolean onUp = dfsFindCurChar(board, word, i, j-1, index+1);
            // need optimze
            if(onRight || onLeft || onDown || onUp) {
                return true;
            }
          	// vital: if not equate to the char, we need to reset this flag to ensure another incursion could work.
            board[i][j] = word.charAt(index);
        }
        return false;
    
    }
}

剪枝: 同时这里也是基于DFS,所以可以进行剪枝优化,即通过 || 运算符,拿到一个true值就返回结果。

错误总结

慎用自增表达式 i++

在进行回溯的时候老是爱犯一个错误,就是错用自增表达式,这样的情况在之前while循环中也出现过,但场景不同,比较以下代码的不同

 boolean onRight = dfsFindCurChar(board, word, i++, j, index++);
 boolean onLeft = dfsFindCurChar(board, word, i--, j, index++);
 // separator
 boolean onRight = dfsFindCurChar(board, word, i+1, j, index+1);
 boolean onLeft = dfsFindCurChar(board, word, i-1, j, index+1);

很明显,前者会出现错误,因为i++后的i不再是原来的值,因此i--也会得到错误的值,所以这里涉及原值传递时,慎用自增表达式

JZ-14 -I 剪绳子 ⭐⭐

2021/4/6 09:46:00
Formula
image-20210330163524643
image-20210330163524643

思考:

动态规划、通项式、贪心算法?

后来发现在求On的时候有复杂的情况,就放弃了,应该是数学方面的问题,不应该暴力迭代

O (1):

image-20210330163659124
image-20210330163659124
image-20210330163712589
image-20210330163712589
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        if(b == 0) return (int)Math.pow(3, a);
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        return (int)Math.pow(3, a) * 2;
    }
}
// 作者:jyd
// 链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/

JZ-22. 链表中倒数第k个节点 ⭐

2021/4/6 09:46:00
DFS
TwinPointer
image-20210315222551714
image-20210315222551714

思考

正常情况下,O n+n?

1. 递归寻找?

我最开始准备是 getNode(node.next)先往下去找,找到next为null时再向上返回,但是这时候如何去减k值我就不知道了

这个最后在第三点中得到解决👍

2. 妙妙双指针

让前指针先走k步,然后后指针跟随者前指针一起走

核心的点是在当pre为null时,也就是走到头了,这时候former与pre差k步,也就是倒数第k个元素。

    	  ListNode premer = head;
        ListNode former = head;
        for(int i =0;i<k;i++){  
            premer = premer.next;
        }
        while(premer != null){
            premer = premer.next;
            former = former.next;
        }
        return former;
image-20210315225759099
image-20210315225759099

时间复杂度O n 空间复杂度 O2

如果这种问题递归不行的话,就想想双指针会怎么做吧

3. 回溯

📆 2022.10.30 回顾想的解法,主要是解决两个问题

  1. 回溯时倒数第k个 如何判断,如何判断当前是倒数第几个元素
  2. 回溯时如何既有当前元素的逆序数,又有当前元素的指针?
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        return (ListNode)(method(head, k)[1]);
    }
		
    // Object[0] 当前结点的逆序数(m == k 时返回的是结点的data值)
 		// Object[1] 当前元素:只有逆序数与k相等时才不为空
    public Object[] method(ListNode head, int k) {
        if(head == null) 
            return new Object[]{0, null};
        Object[] object = method(head.next, k);
        int m = (int)object[0] + 1;
        if(m == k) {
            return new Object[]{head.val, head};
        }
        if(object[1] != null) {
                return object; 
        }
        return new Object[]{m, null};
    }
}

这里需要注意的是,回溯时并不是只有mk后就不回溯了,而是之后一直到头结点都有回溯到过程,所以在这个过程中要灵活处理返回到Object[] 确保它就为mk时的那个值

image-20221030195355851
image-20221030195355851

递归?

JZ-24. 反转链表 ⭐

2021/4/6 09:46:00
Recursion
TwinPointer
image-20210308212250360
image-20210308212250360

思考

似乎没什么,注意 null

1. 自己写的 pre 指针代码

if(head == null){
            return null;
        }
        if(head.next ==null){
            return head;
        }
       int i = 0;
        ListNode prer;
        ListNode pre;
        ListNode Lastpre;
      
        while(true) {
            pre = head;
            Lastpre = head;
            try{
                pre = pre.next;
            }catch(NullPointerException e){
                pre = null;
            }
            for (int j = 0; j < i; j++) {
                pre = pre.next;
                Lastpre = Lastpre.next;
            }

            prer = pre.next;


            Lastpre.next = prer;
            pre.next = head;
            head = pre;
            i++;
            if(prer == null){
                break;
            }

        }
        return head;

​ 写了很久,结果太拉了,自己都不想分析了

image-20210308224413999
image-20210308224413999

2. 双指针

            ListNode cur =null;
            ListNode pre = head;
            ListNode t ;
            while(pre != null){
                t = pre.next;
                pre.next = cur;
                cur = pre;  // ①标记
                pre = t;
            }
            return cur;

这里主要还是自己以前的老问题,就是标记1处,这里就理解为是单纯的赋值就行了

image-20210308224939792
image-20210308224939792

3. 递归

if (head == null || head.next == null) {
    return head;
}
ListNode ret = reverseList(head.next);
head.next.next = head;
// 5.next = head;
head.next = null;
//此处置空的时候一定要注意关注点是ret 而不是head...
return ret;

递归理解起来有一定的难度

特别是注意ret 和 head的包含关系, 如果理解不了的时候就报head.next.next 用另一个遍历替换 head.next = ret 集中关注在ret上,因为递归,所以内存消耗肯定很多啦

这种递归给我的启示是以后分不清next的时候或者等价关系,就用中间变量去解耦,或者用已知指针替换,这样会更好理解一些

image-20210308232940772
image-20210308232940772

Jz-47. 礼物的最大价值 ⭐⭐

2021/4/6 09:46:00
DP
image-20210315082753010
image-20210315082753010

1. 递归

2. 动态规划

    public static int getMax(int[][] matrix){
          for( int i =0;i< matrix.length ; i++){
              for(int j = 0;j<matrix[0].length;j++){
                  if(i == 0&& j ==0 ) continue;
                  if(i == 0){
                      matrix[i][j] += matrix[i][j-1];
                  }
                  else if(j == 0){
                      matrix[i][j] += matrix[i-1][j];
                  }
                  else {
                      matrix[i][j] += Math.max(matrix[i][j-1],matrix[i-1][j]);
                  }

              }
          }
          return matrix[matrix.length-1][matrix[0].length-1];
    }
}

时间复杂度 O m*n 空间复杂度 O 1

回顾动态规划的思想,这种问题还是很典型,这种动态规划的思想会破坏原有矩阵

image-20210315090005261
image-20210315090005261

继续优化

对矩阵很大的情况,很少有可能会在第一行或者第一列进行加,所以这个时候可以先进行初始化。然后相当于从[1] [1]开始

   int m = grid.length, n = grid[0].length;
        for(int j = 1; j < n; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++) 
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
        return grid[m - 1][n - 1];

自己对动态规划还是不熟悉

Jz-48. 最长的不含重复字符的子字符串 ⭐⭐

2021/4/6 09:46:00
DP
image-20210318165801690
image-20210318165801690

思考

平常解 时间复杂度

关键是每一次index到一个数都需要和当前字符串的字母进行对比,能避免吗?实质是相同字母的最大间距,也可能不是。

1. 动态规划

JZ-50. 第一个只出现一次的字符⭐

2023/3/8 15:32:00
Hash
Foreach

1. 哈希表+遍历

先按序遍历一次,统计次数,然后再按序遍历一次,统计第一个出现次数为1的字符

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Integer nums = map.get(c);
            if(nums == null) {
                map.put(c, 1);
            }else{
                map.put(c, ++nums);
            }
        }
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(map.get(c) == 1) {
                return c;
            }
        }
        return ' '
    }
}

注意,这里map的value也可也设置为,只出现一次则为索引值,出现多次则为-1,最终遍历判断

2. 哈希表+队列

主要按FIFO顺序存储出现的元素,那最后肯定希望的是从队列中拿出一个队头元素(首次出现)就行了,不用再遍历一次,因此问题就变成了当队头元素出现两次及以上时,如何将队头元素出队,所以队列中要判断当前元素的出现次数。

  • 当元素第一次出现时,先添加进Map中统计并且插入队列中
  • 当元素多次出现时,先将统计的值置为-1(表示多次出现),然后再判断队头以及之后的元素是否是单次出现的,如果是的话则需要出队
class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        Queue<Character> queue = new LinkedList<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(!map.containsKey(c)) {
                map.put(c, i);
                queue.offer(c);
            }else{
                map.put(c, -1);
              	// 关键代码, 比较当前元素是否是多次出现的
                while(!queue.isEmpty() && map.get(queue.peek()) == -1) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty()?' ':queue.poll();
    }
}

JZ-54. 二叉搜索树第k大节点 ⭐

2021/4/6 09:46:00
InOrder Traversal
Tree
image-20210405161703797
image-20210405161703797

思考

递归 ?

中序遍历

class Solution {
    int res =0, m =0;
    public int kthLargest(TreeNode root, int k) {
        m = k;
        getMax(root);
        return res;
    }
    public void getMax(TreeNode node){
        if(node == null){
            return ;
        }
        getMax(node.right);
        if(m == 0){
            return ;
        }
        if(--m == 0){
            res = node.val;
        }
        getMax(node.left);
    }
}

时间复杂度 On 空间复杂度 O1

image-20210405164353990
image-20210405164353990

这道题主要一直在纠结递归的返回参数问题,思考的时候没有思考深入, 没有想清楚本质,以后遇到这种问题还是要多想一哈,不过感觉递归还是个人的弱点.....

涉及到二叉搜索树,就要想清楚他的性质,中序遍历是从小到大的排序数组

JZ-56 数组中数字出现的次数 I ⭐⭐

2021/4/6 09:46:00
Hash
XOR
image-20210402213300125
image-20210402213300125

思考

On 时间复杂度 O1 空间复杂度

哈希表肯定用不了 取模算不了 动态规划算不了 双指针 数组肯定是偶数长度的

两次遍历? 排序?

1. My hashTable

public int[] singleNumbers(int[] nums) {
        int max = nums[0];
    
        int[] result = {-1,-1};
        for(int i = 0;i<nums.length;i++){
            if(max<nums[i])
                max = nums[i];
        }
        int[] hash = new int[max*2+2];
        for(int i = 0;i<max*2+2;i++){
            hash[i] = -1;
        }
        for(int i  = 0;i<nums.length;i++){
            int x = nums[i];
            if(hash[x*2] != -1){
                hash[2*x+1] = x;
            }else{
                hash[2*x] = x;
            }
        }
        for(int i =0;i<nums.length;i++){
            if(hash[2*nums[i]+1] == -1 ){
                if(result[0] == -1){
                    result[0] = nums[i];
                }else{
                    result[1] = nums[i];
                }
            }
        }  
          return result;     
    }

居然还不错?

image-20210402220633539
image-20210402220633539

2. My HashMap

 public int[] singleNumbers(int[] nums) {
        
        HashMap<Integer,Integer> hashMap = new HashMap();
        
        int[] result = {-1,-1};
        for(int i = 0;i<nums.length;i++){
            if(hashMap.getOrDefault(nums[i],-1) == -1){
                hashMap.put(nums[i],1);
            }else{
                hashMap.put(nums[i],2);
            }
        }
        for(int i = 0;i<nums.length;i++){
            if(hashMap.get(nums[i])==1){
                if(result[0] == -1){
                    result[0] = nums[i];
                }else{
                    result[1] = nums[i];
                }
            }
        }
        return result;
        
    }
image-20210402221317356
image-20210402221317356

3. 异或大法

理由: 相同的两个数字异或结果肯定为 0 ,且异或具有交换性

分组:找到不同的a,b不同的位数 进行分组

public int[] singleNumbers(int[] nums) {

    int total = 0;
    for(int num:nums){
         total ^= num;
    }
    int mask = 1;
    while((mask & total) == 0){
        mask <<= 1;
    }
    int a =0 ,b = 0;
    for(int num:nums){
        if((mask & num) ==0){
            a ^= num;
        }else{
            b ^= num;
        }
    }
    return new int[]{a,b};
}
image-20210403095612566
image-20210403095612566

Jz-63. 股票的最大利润 ⭐⭐

2021/4/6 09:46:00
DP
TwinPointer
image-20210316215457375
image-20210316215457375

思考

双指针?排序?

前后遍历 O 2N

1. 双指针遍历

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }
        int maxInterval = 0;
        int preIndex = 0;
        int lasIndex = prices.length - 1;
        while(preIndex != lasIndex){
            while(lasIndex != preIndex){
                if(prices[lasIndex] - prices[preIndex] >maxInterval){
                    maxInterval = prices[lasIndex] - prices[preIndex];
                }
                lasIndex --;
            }
            preIndex ++;
            lasIndex = prices.length - 1;
        }
        return maxInterval;
    }

时间复杂度 On*n 空间复杂度 O1

2. 动态规划

核心思想

创建一个数组 dp[i]代表的是i天卖出时的最大收益

又可等于 第i-1天的最大收益 或者 第i天价格 - 前i-1天价格的最低价

 public int maxProfit(int[] prices) {
        int minValue = Integer.MAX_VALUE;
        int profit = 0;
        for(int i =0; i<prices.length; i++){
            minValue = Math.min(minValue,prices[i]);
            profit = Math.max(profit,prices[i]-minValue);
        }
        return profit;
    }
image-20210316225500458
image-20210316225500458

时间复杂度On 空间复杂度O1

还是,多去找通项公式,不一定是符号表达的,能用语言刻画的一样可以

JZ-II-16. 不含重复字符的最长子字符串⭐⭐

2021/4/6 09:46:00
Foreach
Hash
Queue

1. 暴力

统计从索引为i处开始且符合条件的子串的最大长度,空间复杂度O(n^2)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        Map<Character, Integer> map;
        for(int i = 0; i < s.length(); i++) {
            int temp = 0;
            map = new HashMap<>();
            for(int j = i; j < s.length(); j++) {
                if(map.get(s.charAt(j)) == null) {
                    temp++;
                    map.put(s.charAt(j), 1);
                }else{
                    break;
                }
            }
            max = Math.max(temp, max);
        }
        return max;
    }
}

2. 滑动窗口-队列+哈希

还不错,能把这个想出来。

思路就是维通过先进先出维护一个队列、当前队列对应的哈希表、队列中队头元素的索引队列中时刻维护着当前遍历长度下符合条件的最长子串,通过一次遍历就能解决问题。时间复杂度比解法1更好一点

  • 当前元素不在哈希表中(说明队列中肯定也没有), 则该元素入队并添加到哈希表中,Value为索引
  • 当前元素在哈希表中(说明队列中肯定有该元素), 则将队头到与当前字符重复的那个字符所在的队列区间清空(同时清空哈希表), 再将当前元素添加到队列与哈希表中。

为什么这里可以使用滑动窗口的思路?

递增性⤴️

如果我们依次递增地枚举子串的起始位置,那么子串的结束位置也是递增的!这里的原因在于,假设我们选择字符串中的第 kkk 个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为 rk。那么当我们选择第 k+1个字符作为起始位置时,首先从 k+1到 rk 的字符显然是不重复的,并且由于少了原本的第 k 个字符,我们可以尝试继续增大 rk ,直到右侧出现了重复字符为止。这样一来,我们就可以使用「滑动窗口」来解决这个问题了:

摘自力扣官方题解open in new window

public int lengthOfLongestSubstring(String s) {
    Queue<Character> queue = new LinkedList<>();
    Map<Character, Integer> map = new HashMap<>();
    int max = 0;
    int curIndex = 0;
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if(map.get(c) == null) {
            map.put(c, i);
            queue.offer(c);
        }else{
            max = Math.max(queue.size(), max);
            int num = map.get(c);
            while(curIndex <= num) {
                map.remove(queue.poll());
                curIndex++;
            }
            i--;
        }
    }
    return Math.max(queue.size(), max);
}

优化

尝试考虑不使用Queue而使用左右指针维护,Map改为HashSet

问题

这里自己犯了一个很经典的问题,在写代码时,while判断时,为了代码简洁,使用了第一种写法,但最终却一直报超时。

// Solution 1
while(curIndex <= num) {
    map.remove(queue.poll());
    curIndex++;
}
// Solution 2
while(curIndex++ <= num) {
    map.remove(queue.poll());
}

这其实就是在while循环中使用 自增/减符号不当可能引发的错误❎。例如当curIndex = 1, num = 3时,使用第一种方式最终curIndex结果为 4, 而第二种结果方式为5.原因很简单,因为在第一种方式里,判断时只要条件不满足就会退出循环,而第二种方式里,条件不满足会退出循环并且还会对curIndex自增,所以这就造成了curIndex比预期值多了1.

JD-17.09. 第K个数 ⭐⭐

2021/4/6 09:46:00
DP
image-20210428183546466
image-20210428183546466

思考

递归、动态规划 无果

1. 动态规划

 public int getKthMagicNumber(int k) {
        int[] numList=new int[k];
        int p3=0,p5=0,p7=0;
        numList[0]=1;
        for(int i=1;i<k;i++){
            numList[i]=Math.min(Math.min(numList[p3]*3,numList[p5]*5),numList[p7]*7);
            if(numList[i]==numList[p3]*3) p3++;
            if(numList[i]==numList[p5]*5) p5++;
            if(numList[i]==numList[p7]*7) p7++;
        }
        return numList[k-1];

    }
image-20210428183707107
image-20210428183707107

这是合并子序列问题,当这种可选择的,可分成不同数组的I问题,可以采用合并子序列方法,多索引判断

面试-17.10. 主要元素 ⭐

2022/11/14 11:05:00
image-20221114110525822
image-20221114110525822

思考

  • 要求在On的时间复杂度内,肯定是一次遍历。最开始尝试用“最近出现最多次”的方法来统计,但最后发现不可行。但想不到其他的办法了

1. Boyer-Moore 投票算法

自己想的“最近出现最多次”方法的原理与之基本相同,但关键点在于没有对候选元素进行再一次验证。也就是当面对[1,2,3]和 [3,2,3]的情况时想不到处理的对策,这也是自己算法的问题所在,只做了第一步却没有做第二步。

int majorityElement(int* nums, int numsSize){
    int cur_num = nums[0];
    int count = 0;
    for(int i = 0; i < numsSize; i++) {
      	// 优化,如果出现size / 2 + 1次,则说明就是主元素
        if(count > numsSize / 2) {
            return cur_num;
        }
        if(cur_num == nums[i]) {
            count++;
        }else{
            count--;
        }
        // count为0时,即候选数不间断出现的次数与这之间出现其他不同的数的次数抵消,则替换候选数
        if(count <= 0) {
            cur_num = nums[i];
            count = 1;
        }
    }
    count = 0;
  	// 验证候选数是否符合条件
    for(int i = 0; i < numsSize; i++) {
        if(nums[i] == cur_num) {
            count++;
        }
    }
    return count > numsSize / 2? cur_num : -1; 
}

什么当数组中存在主要元素时,Boyer-Moore 投票算法可以确保得到主要元素?

LeetCode: Boyer-Moore投票算法中,遇到相同的数则将 count 加 1,遇到不同的数则将 count 减 1。根据主要元素的定义,主要元素的出现次数大于其他元素的出现次数之和,因此在遍历过程中,主要元素和其他元素两两抵消,最后一定剩下至少一个主要元素,此时candidate 为主要元素,且 count≥1。

image-20221114112209399
image-20221114112209399

总结

  • 验证也是设计算法时一个重要的环节 ⚠️ ,再次遍历不会影响On的时间复杂度

1. 两数之和 ⭐

2021/3/7 23:02:00
TwinPointer
Hash
image-20210307223505616
image-20210307223505616

先审题, 两个整数,返回数组下标,给出的数组不是排序的,返回的数组是排序的?

回过头才发现忽略的因素: 数组是否有相同元素?

思路

  1. 二分?
  2. 排序后找?

我的代码:

1. 双头指针

        int[] result = new int[2];
        int i,j;
	    //一个向前 一个向后,避免重复查找
        for(i = 0; i < nums.length;i++){
            for(j = nums.length-1; j>i; j--){
                if(nums[i]+nums[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return null;
image-20210307224350988
image-20210307224350988

时间复杂度 O(N2) 空间复杂度 O(1)

2. 哈希表

确实,最开始想到了郑老板出题的时候这个,只是怕放入map集合又会消耗一定的时间,哎.....

        Map map = new HashMap<Integer,Integer>();
        int j ;
        for(int i =0; i<nums.length; i++){
            j = (int)map.getOrDefault(nums[i],-1);
            if(j != -1){
                return new int[]{j,i};
            }
            map.put(target - nums[i] , i);
        }
        return null;

image-20210307230039420
image-20210307230039420

时间复杂度 : O(N) 空间复杂度 O(N) 哈希表的开销

这里由于哈希表 的get方法是 O(1)的开销,所以考虑哈希表的方式直接查找,精妙之处在与其索引key的灵活使用

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

2022/11/8 21:12:00
Foreach
image-20221108211139910
image-20221108211139910

思路

  • 暴力解法:将两个数组合二为一然后直接取中位数即可,时间、空间复杂度O(m + n)
  • 基于数组是正序的来思考

1. 双指针 (未达标)

并不需要得到整个数组再去用O1的时间找,只需要在定位到中位数,即哪个数在数组,也就是位于 (m + n) / 2 或者 (m + n) / 2与 (m + n) / 2 - 1的位置,在此之前数组都是正序排序的。所以只需要在两个数组中筛选出前(m + n) / 2个数即可。

代码不够优雅,有待改进。

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int i = 0;
    int j = 0;
    int index = 0;
    double arr[2];
    while(i + j  <= (nums1Size + nums2Size) / 2) {
      	// 用于保存(nums1Size + nums2Size) / 2的元素到另一个变量中
        if(i + j == (nums1Size + nums2Size) / 2) {
            index = 1;
        }
        if(i >= nums1Size) {
            arr[index] = nums2[j++];
        }
        else if(j >= nums2Size) {
            arr[index] = nums1[i++];
        }
        else if(nums1[i] > nums2[j]) {
            arr[index] = nums1[i] < nums2[j] ? nums1[i]:nums2[j];
            j++;
        }else{
            arr[index] = nums1[i] < nums2[j] ? nums1[i]:nums2[j];
            i++;
        }
        
    }
  	// 判断中位数是一个还是两个
    if((nums1Size + nums2Size) % 2 == 0) {
        return (double)((arr[0] + arr[1]) / 2.0); 
    }else{
        return arr[1];
    }
}

时间复杂度O(m + n)

image-20221108211307933
image-20221108211307933

2. 二分查找

可以思考一种在Olog时间复杂度内到方法,巧妙

6. Z 字形变换⭐⭐

2022/3/3 20:32:00
Foreach
Formula
image-20220303191539454
image-20220303191539454

审题

  • Z字形排序主要针对列 numRow限定行数,多的行数可能会增加难度
  • 可能的数据结构、数学公式?
  • 分析:
    • 简单:先创建二维字符矩阵,然后根据填好的矩阵按照次序输出,但这样的空间复杂度高
    • 进阶:按照规律直接划分一维的数组
  • 做后反思点:
    • row不为1和n和为1和n的时候的特殊情况,一次存在2个点和只存在一个点

1. 暴力

先划分好二维字符矩阵,然后再按照Z字形排序依次填入矩阵中,最后从矩阵中依照行列顺序读就行了。

缺点:耗费O(numRow * actCol)的空间复杂度

2. 数学公式

一维字符数组本来不用排到二维矩阵中就有的Z字形逻辑,逻辑上通过等差数列也可以得到

public String convert(String s, int numRows) {
    // 特殊情况判断,避免后面除法出现分母为0的情况
        if(numRows == 1) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        int actCol = s.length() / (numRows * 2 - 2) + 1;
        int n = numRows;
        int curRow = 1;
        int i = 1;
        while(curRow <= numRows) {
            if(curRow == 1 || curRow == numRows) {
                for(i = 0; i < actCol; i++) {
                    if((curRow + 2 * i * (n-1)) <= s.length()){
                        sb.append(s.charAt((curRow + (2 * i * (n-1))) - 1));
                    }
                }
                curRow++;
            }else{
                if(curRow <= s.length()) {
                    sb.append(s.charAt(curRow - 1));
                }
                for(i = 1; i <= actCol; i++) {
                    if(curRow + 2 * i * (n-1) - (curRow-1) * 2<= s.length()){
                        sb.append(s.charAt(curRow + 2 * i * (n-1) - (curRow-1) * 2 - 1));
                    }
                    if(curRow + 2 * i * (n-1)<= s.length()){
                        sb.append(s.charAt(curRow + 2 * i * (n-1) - 1));
                    }
                }
                curRow++;
            }
        }
        return sb.toString();
    }
image-20220303202830051
image-20220303202830051

还不错!On的时间复杂度和空间复杂度,sb节省了一定的时间

3. 顺序遍历 分行存储 (转)

思路就是按照顺序遍历,通过索引flag区分到哪一行了,到Z字形转折点时就flag--,非常的巧妙。思路真的是非常的好想,为什么我开始没有想到这么好滴思路?感觉自己一下就跳过顺序遍历这种想法了,可能因为觉得分行存储不好做吧(但实际还是可以的)

class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}

// 作者:jyd
// 链接:https://leetcode-cn.com/problems/zigzag-conversion/solution/zzi-xing-bian-huan-by-jyd/

但因为使用了多个SB,所以这里的空间占用率略高,还存在多个sb合并的合并的情况,所以时间复杂度也相对较高,但是思路确实是非常的清晰的。

image-20220303204028214
image-20220303204028214

反思

还是做题的时候的一些问题:

  1. 寄... 花了很多时间,中间卡了很久,结果是因为自己做题是设了个n,默认的是numRows,但应用的时候没有写,导致查了半天bug。还是写的时候严谨一点,尽可能用它给的参数,否则就自己提前说明好来
  2. 数学太撇,等差公式还看错了.....
  3. 还有charAt和自己写的row起始索引不一致导致后续更换问题,本来是0开始,我自己为了方便从1开始,但后续就需要-1,如果没发现这个问题的话还会有错误
image-20201009182029446
image-20201009182029446

7. 整数反转 ⭐⭐

Time : 2022 / 4 / 6 9 :46
TAG : Overflow / Decimal

2022/4/6 09:46:00
Math
image-20220405204338443
image-20220405204338443

审题

  • 翻转后整数超过32位signed 范围就返回0
  • 环境不准存储64位整数
  • 思路:
    • 直接:
      • 十进制按位取,然后再拼凑
      • 位运算?

1. 十进制按位计算

按十进制取位,然后再反过来乘,组成新的十进制。但需要注意以下问题:

  • 负数取模问题:temp取绝对值,因为负数的符号影响之后的加减法
  • 如何正确判断溢出的情况?

冗余:我这里ArrayList完全没必要,因为后面的计算顺序是从后往前算,其实也可以从前往后算

 public int reverse(int x) {
        int temp = Math.abs(x);
        List<Integer> list = new ArrayList<>();
        int res = 0;
        int flag = 0;
        int paw = 1;
        while(temp / 10 != 0) {
            list.add(temp % 10);
            temp = temp / 10;
        }
        list.add(temp % 10);
        int i =  list.size();
        while(i > 0) {
            int tmp = list.get(--i);
            if(i == list.size() - 1 && tmp == 0) {
                flag = 1;
            }else{
                // Overflow detection
                if(res > tmp * paw + res) {
                    return 0;
                }
                res = (tmp * paw) +res;
                flag = 0;
                paw *= 10;
            }
        }
     // overflow detection.not rigorous
        if(res % 10 != list.get(list.size() - 1)) {
            return 0;
        }
        if(x < 0){
            return -Math.abs(res);
        }
        return res;
    }

O(n)的时间复杂度,加减法和模10耗时

image-20220405212648589
image-20220405212648589

题解的优化

官方题解的优化确实比我写的要好得多,用 < Integer.xxx_VALUE / 10 来判断是否溢出,这种方法非常的简便快速

 public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
image-20220406093819912
image-20220406093819912

注意点

题解的方法跟我方法差距这么大主要是有一个原因:

  • 当顺序取模10的数,即从低到高位,则

    rev = rev * 10 + digit;
    
  • 当逆序取模10的数,即从高到低位,则

    res = (digit * paw) +res;
    

两种思路不一样,产生的解决方法也就不一样,第一种的解决方法能在一次遍历内就解决,而我这一种要先遍历一次并存储,再从集合中去取,经历两次运算和集合操作,自然就要慢一点。

所以还是对一种已知方法就数学问题上要思考一下有没有其他的方式能得到这个值,多思考几种方案取最简洁的那一种

2. 字符串反转

突发奇想,用类库进行字符串反转,再Catch Exception去捕获溢出时转换的异常,比较慢但是算是一种方法.......

public int reverse(int x) {
        String s = String.valueOf(Math.abs(x));
        s = new StringBuilder(s).reverse().toString();
        int i = 0;
        for(i = 0 ; i < s.length() ;i++) {
            if(s.charAt(i) != '0') {
                break;
            }
        }
    	// 截取尾数连续为0的部分
        s=s.substring(i,s.length());
        if(s.length() < 1) {
            return 0;
        }
         int res = 0;
        try{
            res = Integer.parseInt(s);
        }catch(NumberFormatException e) {
            return 0;
        }
        if(x < 0) {
            return 0-res;
        }
        return res;
    }
image-20220406093556481
image-20220406093556481

11. 盛最多水的容器 ⭐⭐

2021/4/6 09:46:00
Foreach
image-20201010183940869
image-20201010183940869

1. 暴力(超时)

 public int maxArea(int[] height) {
        int final_max = 0;
        for(int i = 0; i < height.length; i++) {
            int max = 0;
            for(int j = 0; j < height.length; j++) {
                int min = Math.min(height[i], height[j]);
                int gap = Math.abs(i - j);
                max = Math.max(max, min*gap);
            }
            final_max = Math.max(final_max, max);
        }
        return final_max;
    }

2. 一次遍历(转)

  • 若向内 移动短板 ,水槽的短板 min(h[i], h[j]) 可能变大,因此下个水槽的面积 可能增大 。
  • 若向内 移动长板 ,水槽的短板 min(h[i], h[j]) 不变或变小,因此下个水槽的面积 一定变小
class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]): 
                Math.max(res, (j - i) * height[j--]); 
        }
        return res;
    }
}

// 作者:Krahets
// 链接:https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
image-20201010182820360
image-20201010182820360

12. 整数转罗马数字 ⭐⭐

2021/4/6 09:46:00
Hash
Greedy
image-20201012085753307
image-20201012085753307

我的代码:

HaspMap 存储键值对 判断

   static String getOne(int n){
        StringBuilder stringBuilder=new StringBuilder("");
        int a[]={1,4,5,9,10,40,50,90,100,400,500,900,1000};
        int i=a.length-1;
        Map hashMap=new HashMap<Integer,String>();
        hashMap.put(1,"I");  hashMap.put(4,"IV"); hashMap.put(9,"IX");
        hashMap.put(40,"XL"); hashMap.put(90,"XC");hashMap.put(400,"CD");
        hashMap.put(900,"CM");  hashMap.put(5,"V"); hashMap.put(10,"X");
        hashMap.put(50,"L");hashMap.put(100,"C");   hashMap.put(1000,"M");
        while(i>=0){
            if(n/a[i]>0){
                n=n-a[i];
                stringBuilder.append(hashMap.get(a[i]));
            }else{
                i--;
            }
        }
        return String.valueOf(stringBuilder);
    }
image-20201012090037059
image-20201012090037059

贪心法int String 基本数组 对应存储

   public String intToRoman(int num) {

        StringBuilder stringBuilder=new StringBuilder("");

        int[] a = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] s = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

        int i=0;

        while(i<a.length){

            if(num>=a[i]){
                num=num-a[i];
                stringBuilder.append(s[i]);
            }else{
                i++;
            }
        }
        return String.valueOf(stringBuilder);

    }
image-20201012090139984
image-20201012090139984

思考

  • 对于判断 和 输出对于字符的思路,我的思路上与题设大体一致
  • 不能解决 4 -9 的问题,就只能存储进数组中,通过索引解决

HashMap 中的get方法时间复杂度是否为O(1)?

在hash不发生冲突的情况下, 是O(1),也就是说,最优情况才是O(1),没有第二种方法直接建立int a[] 和String s[]的直接对应联系来的 快

15. 三数之和 ⭐⭐

2023/3/23 12:00:00
Foreach

审题

  • 一个三元组中的元素之间不可以有重复,且三元组组与组之间不可有重复
  • 思路:
    • 三个元素相加=0可以简化为两个数之和等于第三个数,所以能尽快验证前两个数之和是否在第三个数中是极好的(O(1)时间复杂度), 所以考虑到用哈希来缓存
    • 方案不可行,因为很难解决三元组组间不重复问题

1. 排序+双指针 (R)

现在已知通过暴力三重循环能够解决问题,但如何将问题的时间复杂度从O(N3)优化到O(N2)?

外层循环肯定是不变的,那也就是针对当前索引的元素,如何通过一次遍历找到数组中其他两个元素,使其两元素之和等于这个元素的相反数?

所以可以通过先将数组排序(关键),然后在内循环中使用双指针来同步进行.双指针一头在首一头在尾,通过两指针元素之和与外循环元素相反数比较,从而判断此时该左指针右移(三数之和小于0)还是右指针左移(三数之和大于0),两指针逐步趋于目标值,就能通过一次遍历找出相符合的所以另外两个元素

同时注意细节,这里要三元组组间不重复,所以要排除内外循环当前元素与前一个位置相同的情况

所以能够将时间复杂度为O(N3)的暴力解法优化为时间复杂度为O(N2) 空间复杂度为O(logN)的算法(排序时二分递归占用空间)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {
          	// 针对外层循环, 避免重复的问题
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1;
            int r = nums.length - 1;
            while(l < r) {
                // 避免重复的问题, 只用判断左/右一种情况即可
                if(l != i + 1 && nums[l] == nums[l-1]) {
                    l++;
                    continue;
                }
                if(nums[l] + nums[r] + nums[i] == 0) {
                    List<Integer> cur = new ArrayList<>();
                    cur.add(nums[i]);
                    cur.add(nums[l]);
                    cur.add(nums[r]);
                    res.add(cur);
                  	// 不要忘记自增左或右指针
                    l++;
                }else if(nums[l] + nums[r] + nums[i] > 0) {
                    r--;
                }else{
                    l++;
                }
            }
        }
        return res;
    }
}

17. 电话号码的字母组合 ⭐⭐

2021/4/6 09:46:00
Foreach
image-20201012205456540
image-20201012205456540

我的代码:

String类型的迭代

    private String letterMap[] = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };
    private ArrayList<String> res;   
List<String> letterCombinations(String digits){
       if(digits.equals(""))
           return list;
       else{
           getString(digits,0,"");
           return list;
       }
    }
    void  getString(String digits,int index,String tmp){
        if(index==digits.length()) {
            list.add(tmp);
            return ;
        }
        char c=digits.charAt(index);
        String letter=arrstr[c-'0'];

        for(int i=0;i<letter.length();i++){
            getString(digits,index+1,tmp+letter.charAt(i));
        }
    }
image-20201012212830953
image-20201012212830953

StringBuilder 实现的迭代

class Solution {
	//一个映射表,第二个位置是"abc“,第三个位置是"def"。。。
	//这里也可以用map,用数组可以更节省点内存
	String[] letter_map = {" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	public List<String> letterCombinations(String digits) {
		//注意边界条件
		if(digits==null || digits.length()==0) {
			return new ArrayList<>();
		}
		iterStr(digits, new StringBuilder(), 0);
		return res;
	}
	//最终输出结果的list
	List<String> res = new ArrayList<>();
	
	//递归函数
	void iterStr(String str, StringBuilder letter, int index) {
		//递归的终止条件,注意这里的终止条件看上去跟动态演示图有些不同,主要是做了点优化
		//动态图中是每次截取字符串的一部分,"234",变成"23",再变成"3",最后变成"",这样性能不佳
		//而用index记录每次遍历到字符串的位置,这样性能更好
		if(index == str.length()) {
			res.add(letter.toString());
			return;
		}
		//获取index位置的字符,假设输入的字符是"234"
		//第一次递归时index为0所以c=2,第二次index为1所以c=3,第三次c=4
		//subString每次都会生成新的字符串,而index则是取当前的一个字符,所以效率更高一点
		char c = str.charAt(index);
		//map_string的下表是从0开始一直到9, c-'0'就可以取到相对的数组下标位置
		//比如c=2时候,2-'0',获取下标为2,letter_map[2]就是"abc"
		int pos = c - '0';
		String map_string = letter_map[pos];
		//遍历字符串,比如第一次得到的是2,页就是遍历"abc"
		for(int i=0;i<map_string.length();i++) {
            
            letter.append(map_string.charAt(i));
            //如果是String类型做拼接效率会比较低
			//iterStr(str, letter+map_string.charAt(i), index+1);
            iterStr(str, letter, index+1);
            //这个方法保证了每一次大循环后得到的stringbuilder都是新的
            //注意: 这里的删除方法很重要!!
            letter.deleteCharAt(letter.length()-1);
		}
	}
}
image-20201012205626708
image-20201012205626708

思考

StringBuilder 确实操作比 String类型快很多很多,且在 空间占用上也远远低于 String

这还得归结于String 相加时 总会新分配一个String对象进行赋值


21. 合并两个有序列表 ⭐

2021/4/6 09:46:00
Foreach
Recursion
image-20201016083409297
image-20201016083409297

1. 迭代

/*
	题目给的是:  有 序 的数组,这点很重要
*/
public  ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode nodehead = new ListNode(-1);
        ListNode pre = nodehead;
		// 理解这里pre=nodehead 的指向问题
        while (l1 != null && l2 != null) {
            try {
                if (l1.val <= l2.val) {
                    pre.next = l1; // 这里的两步都能想到
                    l1 = l1.next;
                } else {
                    pre .next= l2;
                    l2 = l2.next;
                }
                // 这里注意! 关键点  是指针节点后移的步骤
                // 那pre之前的数呢? ---传给nodehead了 
                pre = pre.next;
            }catch (NullPointerException e){
            }
        }
        //抓一下最后几个节点,可能不止一个节点,但他是有序的,就无妨了
        pre.next=l1==null?l2:l1;
        return nodehead.next;
       /**
    	*    时间复杂度O(n+m) 空间复杂度O(1) (pre 和nodepre作为变量)
    	*/
    }
image-20201016083455230

2. 递归

public  ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        else if(l2==null)
            return l1;
    //到这里都没问题
        else if(l1.val<=l2.val) {
    //此处 总爱 直接return一个 函数方法体 其实是不对的 ,具体得到的是谁呢?
    // 用 node.next能够实现对元素的保存
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else{
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
    /**
    *    时间复杂度O(n+m) 空间复杂度O(m+n) (递归函数的调用)
    	 所以 执行结果内存消耗稍微慢于 迭代
    */
}
image-20201016084013216
image-20201016084013216

分析:

自己做的时候,开始是都想到了这两种算法,不过后来总觉得哪里行不通,就放弃了递归,采用迭代。分析问题的原因:

  1. 问题用那种方法解决?
    1. 从头部解决: --------迭代
      • 用头元素记录 ,标兵元素去移动
    2. 从尾部解决: --------递归
      • 为了得到保存结果 用next指针继续下一次判断
  2. 两者的关键点 都是 巧妙的使用 next指针

26. 删除排序数组中的重复项 ⭐

2021/4/6 09:46:00
Foreach
image-20201018171723036
image-20201018171723036

1. 暴力三循环 --解非排序数组

/**
 * 删除数组中重复元素的
 * 分析: 造成 时间复杂度高的步骤: 判断 之后的元素是否相等和 移动数组
 */
// for     三层循环来做  算法不稳定  O(N3)/Ok(1)
static int deleteSameNode(int[] nums){
    int total=nums.length;
    // 设置total 用于 循环体中 避免重复判断
    for(int i=0;i<total;i++){
        for(int j=i+1;j<total;j++){
            if(nums[i]==nums[j]) {
                total-=1;
                for(int k=j;k<total;k++){

                        nums[k]=nums[k+1];

                }
                j--;       //注意这里的 j--
                }
            }
    }
    return total;
}

注意点:

  • j-- :避免多个重复的数在一起而被漏掉
  • total作为循环判断的依据: 避免多个重复的数在一起而被漏掉 或者 重复判断了移动到末尾的数字

2. 双指针单循环 --- 解排序数组

 static int deleteSameNode_2(int[] nums) {
        int i = 0;

        for (int j = 1; j < nums.length; j++) {
            if(nums[i]!=nums[j]){
                i++;
                nums[i]=nums[j];
            }
        }
        return i+1;
    }
image-20201018231302964
image-20201018231302964

反思

这里我思考的时候 ,没有看题目要求, 直接按照一般的数组来解决了,其实 题目给的 有序数组 ,双循环再想到单循环双指针 ,是非常好解决的。此处也提供了一种思路, 先将 数组 有序化 ,再通过这种方式 进行O(n) 的运算

28. 实现strStr() ⭐⭐

Time : 2022 / 3 / 26 10 : 23
TAG : KMP、迭代

2022/3/26 10:23:00
KMP
Foreach
image-20220326095118494
image-20220326095118494

审题

  • 返回匹配的子字符串在母字符串中第一次出现的位置
  • 母串长度为n 字符串长度为m

1. 暴力迭代

在母串中依次查找,时间复杂度O(nm)

2. KMP

关于KMP,在字符串匹配中的应用是十分重要的,因为它把O(mn)的时间复杂度降低至O(m + n)

Knuth-Morris-Pratt 算法,简称 KMP 算法,由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三人于 1977 年联合发表

KMP的核心步骤:

  1. 根据目标子串生成next数组(重点)
  2. 在母串中依据目标子串和next数组进行查找
public int strStr(String haystack, String needle) {
        if(needle.equals("")) {
            return 0;
        }else if(haystack.equals("")) {
            return -1;
        }
        int[] next = kmp_gen_next(needle);
        int res = is_son_str(haystack, needle, next);
        return res;
    }
    public int is_son_str(String s, String son, int[] next) {
        int i = 1;
        int j = 1;
        while(i <= s.length() && j <= son.length()) {
            if(j == 0 || s.charAt(i-1) == son.charAt(j-1)) {
                i++;
                j++;
            }else{
                j = next[j-1];
            }
        }
        if(j > son.length()){
            return i - j;
        }
        return -1;
    }
     public int[] kmp_gen_next(String s) {
        int[] next = new int[s.length()];
        int i = 1;
        int j = 0;
        next[0] = 0;
        while(i < next.length) {
            if(j == 0 || s.charAt(i - 1) == s.charAt(j - 1)) {
                i++;
                j++;
                next[i-1] = j;
            }else{
                j = next[j-1];
            }
        }
        return next;
    }
image-20220326100442552
image-20220326100442552

优化

针对next数组优化,因为如果father_str[i] != son_str[j] 且 son_str[j] == son_str[next[j]]时,就会出现不必要的重复判断,因为之前判断两者不相等,而转化j后再去判断,(但son_str[j] == son_str[next[j]])所以两者肯定还是不相等,就优化了next数组

	public int[] kmp_gen_next_modified(String s) {
        int[] next = new int[s.length()];
        int i = 1;
        int j = 0;
        next[0] = 0;
        while(i < next.length) {
            if(j == 0 || s.charAt(i - 1) == s.charAt(j - 1)) {
                i++;
                j++;
                if(s.charAt(i - 1) != s.charAt(j - 1))
                    next[i - 1] = j;
                else
                    next[i-1] = next[j - 1];
            }else{
                j = next[j-1];
            }
        }
        return next;
    }

不明显,可能是生成next时多了一些判断?

image-20220326100339847
image-20220326100339847

二刷-C语言版本

自己觉得KMP难理解的点(配合图来理解):

  1. 先理解前缀和后缀,KMP是通过子串的前后缀来进行线性判断的。也就是说,如果子串有相同的最长前、后缀,则就可以进行移位比较
  2. 接下来,如何计算这个最长的前后缀?问题的关键也就变成了计算next数组了,那next数组是什么?next数组是指示截止当前元素为止,当前长度的数组最长前后缀的长度是多少?例如abcabcd,d处的数值便是3(因为有最长前后缀abc)。计算next数组时的一个难点,也是我认为比较难以理解的一个地方:在比较计算第k个索引元素的值时。先看前一个元素的值,也就是看到前一个数为止当前数组的最大前后缀,若值为m。
    1. 则比较第m+1个元素与当前元素是否相等,如果相等,就说明到当前元素为止,数组能构成一个更长的前后缀(这里可以画图理解),所以当前元素的值=前一个元素值+1
    2. 如果不想等的话,则要去找次长的前后缀,然后比较次长的前缀 和 加了新元素的后缀是否相等,如果找到了就等于次长前缀长度 + 1,如果没找到,就重复这个过程,直到没有最长前后缀,此时当前元素的值为0(也就是没有最长前后缀)。
int * genNext(char * needle, int length) {
    int *next = (int *) calloc(length, sizeof(int));
    int i = 1;
    int cur_hop = 0;
    while(i < length) {
        if(needle[i] == needle[cur_hop]) {
            cur_hop++;
            next[i] = cur_hop;
            i++;
        }else{
            if(cur_hop == 0) {
                next[i] == 0;
                i++;
            }
            else{
                cur_hop = next[cur_hop - 1];
            }
        }
    }
    return next;
}
int strStr(char * haystack, char * needle){
    int i, j = 0;
    int length = strlen(needle);
    int out_length = strlen(haystack);
    int *next = genNext(needle, length);
    while(i < out_length) {
        if(haystack[i] == needle[j]){
            j++;
            i++;
        }else if(j > 0){
            j = next[j - 1];
        }else{
            i++;
        }
        if(j >= length) {
            return i - j;
        }
    }
    return -1;
}
image-20221103213544861
image-20221103213544861

29. 两数相除 ⭐⭐

Time: 2021 10 12 4:06pm

2021/10/12 16:06:00
Foreach
Bin
Iteration
image-20211012150254273
image-20211012150254273

审题

  • 不得使用* / mod,也就是说+ - 位运算都可以用、
  • 返回[商]
  • 除数不为0
  • 可以为负数
  • 排除递归、dp...

1. 暴力

2. 二分查找(转)

  1. 先把特殊情况罗列
  2. 因为溢出的可能,所以都取成负数
  3. 在判断溢出时用负数和移动不等式两边去进行巧妙判断
class Solution {
    public int divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }
        
        // 一般情况,使用二分查找
        // 将所有的正数取相反数,这样就只需要考虑一种情况
        boolean rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }
        
        int left = 1, right = Integer.MAX_VALUE, ans = 0;
        while (left <= right) {
            // 注意溢出,并且不能使用除法
            int mid = left + ((right - left) >> 1);
            boolean check = quickAdd(divisor, mid, dividend);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == Integer.MAX_VALUE) {
                    break;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rev ? -ans : ans;
    }

    // 快速乘
    public boolean quickAdd(int y, int z, int x) {
        // x 和 y 是负数,z 是正数
        // 需要判断 z * y >= x 是否成立
        int result = 0, add = y;
        while (z != 0) {
            if ((z & 1) != 0) {
                // 需要保证 result + add >= x
                if (result < x - add) {
                    return false;
                }
                result += add;
            }
            if (z != 1) {
                // 需要保证 add + add >= x
                if (add < x - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            z >>= 1;
        }
        return true;
    }
}
image-20211012155401725
image-20211012155401725
image-20211012155418405
image-20211012155418405

3. 类二分查找(转)

class Solution {
    public int divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }
        
        // 一般情况,使用类二分查找
        // 将所有的正数取相反数,这样就只需要考虑一种情况
        boolean rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }

        List<Integer> candidates = new ArrayList<Integer>();
        candidates.add(divisor);
        int index = 0;
        // 注意溢出
        while (candidates.get(index) >= dividend - candidates.get(index)) {
            candidates.add(candidates.get(index) + candidates.get(index));
            ++index;
        }
        int ans = 0;
        // 没看懂
        for (int i = candidates.size() - 1; i >= 0; --i) {
            if (candidates.get(i) >= dividend) {
                ans += 1 << i;
                dividend -= candidates.get(i);
            }
        }

        return rev ? -ans : ans;
    }
}

4. 递归(转)

感觉这个比上面的好懂一点

举个例子:11 除以 3 。
首先11比3大,结果至少是1, 然后我让3翻倍,就是6,发现11比3翻倍后还要大,那么结果就至少是2了,那我让这个6再翻倍,得12,11不比12大,吓死我了,差点让就让刚才的最小解2也翻倍得到4了。但是我知道最终结果肯定在2和4之间。也就是说2再加上某个数,这个数是多少呢?我让11减去刚才最后一次的结果6,剩下5,我们计算5是3的几倍,也就是除法,看,递归出现了。说得很乱,不严谨,大家看个大概,然后自己在纸上画一画,或者直接看我代码就好啦!

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1){
            if(dividend>INT_MIN) return -dividend;// 只要不是最小的那个整数,都是直接返回相反数就好啦
            return INT_MAX;// 是最小的那个,那就返回最大的整数啦
        }
        long a = dividend;
        long b = divisor;
        int sign = 1; 
        if((a>0&&b<0) || (a<0&&b>0)){
            sign = -1;
        }
        a = a>0?a:-a;
        b = b>0?b:-b;
        long res = div(a,b);
        if(sign>0)return res>INT_MAX?INT_MAX:res;
        return -res;
    }
    int div(long a, long b){  // 似乎精髓和难点就在于下面这几句
        if(a<b) return 0;
        long count = 1;
        long tb = b; // 在后面的代码中不更新b
        while((tb+tb)<=a){
            count = count + count; // 最小解翻倍
            tb = tb+tb; // 当前测试的值也翻倍
        }
        return count + div(a-tb,b);
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置 ⭐⭐

2022/4/6 14:50:00
BinaryS
Foreach
image-20220406102748986
image-20220406102748986

审题

  • 升序排列的数组,有重复数字,数字可为负数
  • 找的数不存在,返回[-1,-1]
  • 思路:
    • 直接:
      • 迭代
    • 进阶:
      • 二分查找:问题,如何找到起始的点?

1. 顺序遍历

时间复杂度O(n),没有充分利用到升序数组这个条件

public int[] searchRange(int[] nums, int target) {
        int start = -1;
        int end = -1;
        int[] res = new int[2];
        for(int i = 0; i < nums.length; i++) {
            if(target < nums[i]) {
                break;
            }
            if(target == nums[i] && start == -1) {
                start = i;
                end = i;
            }else if(target == nums[i]) {
                end++;
            }
        }
        res[0] = start;
        res[1] = end;
        return res;
    }
image-20220406103252339
image-20220406103252339

2. 二分查找

不仅对整体二分查找,还二分查找中点target的左右端点。

public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1,-1};
        int f1 = binarySearch(nums,0,nums.length - 1,target);
        if(f1 != -1) {
            int left = f1;
            int right = f1;
            while(true) {
                // 临时保存binarSearch结果,避免重复运算
                int l_temp;
                int r_temp;
                if(left == -1 && right == -1) {
                    break;
                }
                if(left != -1) {
                    l_temp = binarySearch(nums,0,left - 1,target);
                    if(l_temp == -1) {
                        res[0] = left;
                    }
                    left = l_temp;
                }
                if(right != -1) {
                    r_temp = binarySearch(nums,right + 1,nums.length - 1,target);
                    if(r_temp == -1) {
                        res[1] = right;
                    }
                    right = r_temp;
                }
            }
        }
        return res;
    }
	// 二分查找
    public int binarySearch(int[] nums, int l, int r,int t) {
        while(l < r) {
            int m = (l + r) / 2; // 靠左边
            // 注意这里+1 和 -1,必要的
            if(nums[m] < t) {
                l = m+1;
            }else if(nums[m] > t) {
                r = m-1;
            }else{
                return m;
            }
        }
        // 如果l==r还要判断中间值
        if(l == r) {
            if(nums[r] == t)
                return r;
        }

        return -1;
    }
image-20220406113758421
image-20220406113758421

**补充:**官方题解的方法是设置bool值来表明是查找第一个大于target和第一个大于等于target的值

反思

  • 二分法想起容易,写起来还是十分费劲,自己写有很多的bug

36. 有效的数独 ⭐⭐

image-20210917143810318
image-20210917143810318

审题

  • 分区域 ,每行每列每九宫格

........已经不知道自己有多蠢了,题的意思是求出题中所给缺陷数独是否符合规范!!而不是求是否能生成一个数独。。。搁这做了半天一直不对。。。

看题!!!看题!!!看题!!!

最后摘一道题解,日后再做一下

1. 顺序检验(转)

 bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][10] = {0};// 哈希表存储每一行的每个数是否出现过,默认初始情况下,每一行每一个数都没有出现过
        // 整个board有9行,第二维的维数10是为了让下标有9,和数独中的数字9对应。
        int col[9][10] = {0};// 存储每一列的每个数是否出现过,默认初始情况下,每一列的每一个数都没有出现过
        int box[9][10] = {0};// 存储每一个box的每个数是否出现过,默认初始情况下,在每个box中,每个数都没有出现过。整个board有9个box。
        for(int i=0; i<9; i++){
            for(int j = 0; j<9; j++){
                // 遍历到第i行第j列的那个数,我们要判断这个数在其所在的行有没有出现过,
                // 同时判断这个数在其所在的列有没有出现过
                // 同时判断这个数在其所在的box中有没有出现过
                if(board[i][j] == '.') continue;
                int curNumber = board[i][j]-'0';
                if(row[i][curNumber]) return false; 
                if(col[j][curNumber]) return false;
                if(box[j/3 + (i/3)*3][curNumber]) return false;

                row[i][curNumber] = 1;// 之前都没出现过,现在出现了,就给它置为1,下次再遇见就能够直接返回false了。
                col[j][curNumber] = 1;
                box[j/3 + (i/3)*3][curNumber] = 1;
            }
        }
        return true;
    }

除此之外还可以考虑位运算的方法,这里的理解也比较巧妙

38. 外观数列 ⭐

Recursion

* String 与 StringBuilder 关于效率和递归的使用

image-20201027184424039
image-20201027184424039

1. 递归

/**
         * 思路: 这种问题看起来很没有思路但是实际上又和前一项有联系
         *  考虑到追根溯源 --- 从尾部解决 然后对每一层进行分析
         */
        //String的增删效率低 但是这里我的效率依然很低....  
public static String countAndSay(int n) {
        if(n==1) return "1";
    
        StringBuilder str=new StringBuilder("");
        String bcstr=countAndSay(n-1);

        for(int i=0;i<bcstr.length();i++){
            int j=1;
            for(int k=i;k<bcstr.length()-1;k++){
                if(bcstr.charAt(i)==bcstr.charAt(k+1)) {
                    j++;
                    i++;
                }
                else break;
                }
            str.append(String.valueOf(j)+bcstr.charAt(i));
            }
        return String.valueOf(str);
        }
image-20201027184706268
image-20201027184706268

这种做法能做出来,但我觉得基于迭代的 空间复杂度 还有String自身的增添麻烦,且每一次迭代都会新建StringBuilder对象,是会效率不高。

2. 看题解后的细节调整

细节分析: 这里的主要效率不高的拖延点在于str.append 的操作

​ 可能是由于 str.append(String.valueOf(j)+bcstr.charAt(i)); 使得两个字符串再次相加得到的新字符串,再将新的字符串赋值上去,使得在这里出现的String类型的增删。 且append(int ) 添加的是String类型的数字,但由于append(int+char)型的是会先将char 转换成加上int的char 再赋值给builder, 所以这里连用append 更好。

str.append(j).append(bcstr.charAt(i));
image-20201027185740882
image-20201027185740882

42. 接雨水 ⭐⭐⭐

2021/4/6 09:46:00
Foreach
Stack
DP
image-20220117101802334
image-20220117101802334

审题

  • 区间和高度决定了能够接多少水,以接近区间的最高点和起点决定?
  • 算每一个可接单元的每一层吗?
  • 做法:先在LogN的时间点找到每个区间,然后在区间内进行运算
  • 做后思考:如何在On的情况下计算?

1. 暴力--顺序搜索

以起始点大小为判断条件,找到末点大于起始点的点,分情况讨论:

  • 如果找到了 ,则在此基础上以较小的起始点为顶,起始点 - 各点的值逐渐累加
  • 没有找到,则找第二大的点,并以末点为顶......
  public int trap(int[] height) {
        int total = 0;
        for(int i = 0; i < height.length; i++) {
            for(int j = i+1; j < height.length ; j++) {
                // confirm a region
                if(height[j] >=  height[i]) {
                    for(int k = i+1; k < j; k ++){
                        total += height[i] - height[k];
                    }
                    i = j - 1;
                    break;
                }
                // if can`t find a number bigger than height[i]
                if(j == height.length - 1 && height[j] < height[i]) {
                    int temp = i + 1;
                    for(j = i + 1; j < height.length; j++) {
                        if(height[temp] < height[j])
                            temp = j;
                    }
                    j = temp;
                    for(int k = i+1; k < j; k++) {
                        total += height[j] - height[k]; 
                    }
                    i = j - 1;
                    break;
                }
            }
        }
        return total;
    }
image-20220117154832631
image-20220117154832631

为什么这么慢?
考虑到内部其实有三层循环(但实际上只有两层),最坏时可能对每一个起点,都没有一个比他大的点,并且第二大的点都在末尾排列,所以时间复杂度来到了O(n^2)
如何消除平方的时间复杂度关键要么换算法类型要么就解决如何找第二大的点

2. 动态编程 (转 - 验)

确实,这个题符合动态编程的特点。要想知道该点处的积水量,即找到该点左右两侧最大值中较小的那个,这里用On的空间复杂度去保存这些点,以便能实现O1的计算,所以能在On的时间复杂度内完成。

 public int trap(int[] height) {
        int total = 0;
        int[] right_max = new int[height.length];
        int[] left_max = new int[height.length];
        right_max[height.length - 1] = height[height.length - 1];
        left_max[0] = height[0];
        for(int i = 1; i < height.length; i++) {
            left_max[i] = Math.max(left_max[i - 1], height[i]);
            right_max[height.length - 1 - i] =  Math.max(height[height.length - 1 - i], right_max[height.length  - i]); 
        }
        for(int i = 1; i < height.length; i++) {
            total += Math.min(left_max[i], right_max[i]) - height[i];
        }
        return total;
    }
image-20220117161221631
image-20220117161221631

3. 栈存储 (转 - 验)

思路与 1 一致,有点像1、2的结合,不需要先遍历,有补偿机制。On的时间复杂度和空间复杂度。但不知道为啥这么慢

  int total = 0;
        Deque<Integer> stack = new LinkedList<>();
        int index = 0;
        int distance, rel_height;
        while(index < height.length) {
            while(!stack.isEmpty() && height[index]  > height[stack.peek()]) {
                int pop = stack.pop();
                if(stack.isEmpty())
                    break;
                distance = index - stack.peek() - 1;
                rel_height = Math.min(height[index], height[stack.peek()]) - height[pop];
                total += rel_height * distance;
            }
            stack.push(index++);
        }
        return total;
image-20220117163209828
image-20220117163209828

4. 超妙双指针 (转)

On的时间复杂度 O1的空间复杂度 。非常的妙,以相向的双指针处的值的当前差值来决定从哪边进行补偿,并存储了对应两边的最大值。而又由于其双指针差值选择避开了出现较小的值导致错误补偿的可能

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                ans += (left_max - height[left]);
            }
            ++left;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                ans += (right_max - height[right]);
            }
            --right;
        }
    }
    return ans;
}
// 链接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
image-20220117164109645
image-20220117164109645

43. 字符串相乘

image-20210403103757421
image-20210403103757421

思考:

不能用Bigdemical 大数相乘 注意最高位数 返回类型为String long可能有溢出

位运算?

1. My 自实现的进位机制

if(num1.equals("0")||num2.equals("0")){
    return "0";
}
int l1 = num1.length();
int l2 = num2.length();
int l3 = l1 + l2;
char[] result = new char[l3];
for(int i =0 ;i<l3;i++){
    result[i] = '0';
}
//冗杂
int min = Math.min(l1,l2);
if(l1 == min){
    String temp  =num1;
    num1 = num2;
    num2 = temp;
}
//选出最小的数
for(int i = num2.length()-1;i>=0;i--){
    for(int j = num1.length()-1; j>=0;j--){
        int mr =  (num1.charAt(j)-48)*(num2.charAt(i)-48);
        result[i+j+1] += ( char )(mr % 10 ) ;
        if(result[i+j+1] >= 58){
            result[i+j] += 1;
            result[i+j+1] = (char) (result[i+j+1]-10);
        }
        //这里有冗杂的成分
        result[i+j] += mr/10;
        if(result[i+j]>=58){
            result[i+j-1] += 1;
            result[i+j] -= 10;
        }
    }
}
if(result[0] == '0'){
    return new String(result).substring(1);
}else{
    return new String(result);
}

时间复杂度 O(m * n ) 空间复杂度 O(m+n)

image-20210403200458765
image-20210403200458765

整解的思路差不多,但是在处理result[i+j-1]这一块更加简洁

50. Pow(x,n) ⭐⭐

Time : 2022 / 4 / 5 10 : 46
TAG : Iteration / Recursion / Complement / Bits

2022/4/5 10:46:00
Foreach
Recursion
Bits
image-20220402195616362
image-20220402195616362

审题

  • x是小数,返回的也是double类型数字.指数可能为负数
  • 可能的做法:
  • 思路:
    • 简单:递归;递归
    • 进阶:能否在对数时间复杂度内完成

1. 递归(Stack Over)

public double myPow(double x, int n) {
        if(n > 0) {
            return myPow(x,n-1)*x;
        }
        if(n == 0) {
            return 1.0;
        }
        return myPow(1/x,-n); 
    }

优化(Stack OF)

  public double myPow(double x, int n) {
        return myPow(x,(long)n);
      }
  public double myPow(double x, long n) {
        if(n == 0) {
            return 1.0;
        }
        if(n < 0) {
            return myPow(1/x,-n);
        }
        if(n / 3 > 0) {
            return myPow(x * x * x , n / 3) * myPow(x,n % 3);
        }
        if(n / 2 > 0) {
            return myPow(x * x,n / 2) * ((n & 1) == 1?x:1);
        }
        return x;
    }
image-20220402205928765
image-20220402205928765

2. 迭代(OverTime)

 public double myPow(double x, int n) {
        if(n == 0) {
            return 1.0D;
        }
        if(n < 0) {
            n = -n;
            x = 1/x;
        }
        double res = x;
        while(--n > 0) {
            res = res * x;
        }
        return res; 
    }

优化

public double myPow(double x, int n) {
        if(n == 0) {
            return 1.0D;
        }
        Long longx = new Long(n);
        if(n < 0) {
            longx = Math.abs(longx);
            x = 1/x;
        }
        if(longx == 1) {
            return x;
        }
        double res = 1.0d;
        while(longx / 2> 0) {
            res = res * ((longx & 1) == 0?1.0:x);
            x = x * x ;
            longx /= 2;

        }
        res *= x;
        return res;
    }
image-20220402205324791
image-20220402205324791

问题

这里还涉及到了自己的一个学习漏洞,对补码的理解和计算机位表示的混乱理解:

具体解析参见文章《计算机组成原理》 [补码的加减法]章节

这道题我的问题主要在于:signed int (1 >> 31 - 1)等于多少,这里应该从位的角度先去理解,计算-1的补码然后二者相加,因为是补码运算,所以符号位囊括在计算过程中。(而-a = ~a+1,这一点也很重要,简化理解过程),得到二进制存储后,再根据对应的数据类型去转化,这里得到的其实是1>>31,而又是signed int,所以结果又根据原码->补码的反操作来求补码->原码,得到原码的值应该是-1>>31。

总结一下就是:完全按照计算机的步骤来,不要自己一会补码运算一会原码相加,把自己都搞混了

总结

一直想做这道题,今天终于还是抽时间写了这道题。这道题踩到坑了,最开始用迭代和递归,都没做出来,要么超时要么StackOF。以为是算法本身的问题,但后来实在没办法,想了想后觉得奇怪。一调试发现一个重要的问题!也是非常基础的问题(只怪自己基础不牢固)

int n=Integer.MIN_VALUEthenn=n int \ n = Integer.MIN\_VALUE \quad then \quad -n = n

53. 最大子序和 ⭐⭐

DFS
老版
老版
新版
新版

思考

O n 的解法

动态规划?

1. My DP

    public int maxSubArray(int[] nums) {
        
        int max = nums[0];
        int[] dp = new int[nums.length]; 
        dp[0] = nums[0];
        for(int i =1;i<dp.length;i++){
            dp[i] =Math.max(dp[i-1]+nums[i],nums[i]);
            max = Math.max(dp[i],max);
      
        }
        return max;
    }

dp 序列求,最开始题没看清楚以为求的是数组子序列, 设置了end 和begin,后来一看只求最大值 ...

空间复杂度 On 时间复杂度 On

image-20210405094811575
image-20210405094811575

改进

动态规划需要额外的数组一般是可以改进的

所以这里我改进了之后

    public int maxSubArray(int[] nums) {
        
        int max = nums[0];
        int dp_pre = nums[0];
        for(int i =1;i<nums.length;i++){
            dp_pre =Math.max(dp_pre+nums[i],nums[i]);
            max = Math.max(dp_pre,max);
      
        }
        return max;
    }

空间复杂度变为O 1

image-20210405095134634
image-20210405095134634

2. 分治 线段树

....

image-20210405161553429
image-20210405161553429

再回首

2023/3/4 21:52:00

1. 动态规划

既然要找出数组最大和的连续子数组,那可以这样想,从1开始,在整个数组中找出以第i个数结尾且和最大的子数组。为什么这样?这样就有递推式:

  • 以当前元素结尾且包含前一个元素
  • 以当前元素结尾但不包含前一个元素

则有表达式

maxSubArrSums[i]={maxSubArrSums[i1]+nums[i]nums[i] maxSubArrSums[i]=\begin{cases}maxSubArrSums[i - 1] + nums[i] \\nums[i]\end{cases}

class Solution {
    public int maxSubArray(int[] nums) {
        int[] sumsArr = new int[nums.length];
        int curMaxSum = nums[0];
        sumsArr[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            sumsArr[i] = Math.max(sumsArr[i - 1] + nums[i], nums[i]);
            curMaxSum = Math.max(sumsArr[i], curMaxSum);
         }
        return curMaxSum;
    }
}

最终再将maxSubArrSums优化,转化成一个变量即可

2. 分治(线段树) (R)

求一个数组的最大连续子序列和,那可以分成左右两部分来看:

整体最大连续子段和={左部分的最大子段和右部分的最大字段和左部分与右部分交集的子段和 整体最大连续子段和=\begin{cases}左部分的最大子段和 \\右部分的最大字段和\\左部分与右部分交集的子段和\end{cases}

这样就已经解决了两种情况了,只需要解决最后一种左右部分交集的子段和,如何处理?这就引申出来了一个整体的从左开始的最大子段和和从右结束的最大子段和,这样

左右部分交集的子段和=左部分从右结束的最大子段和+右部分从左开始的最大子段和 左右部分交集的子段和 = 左部分从右结束的最大子段和 + 右部分从左开始的最大子段和

class Solution {
    public class Status{
        int lSum, rSum, iSum, mSum ;
        public Status(int lSum, int rSum, int iSum, int mSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            // 区间和
            this.iSum = iSum;
            // 最大子段和
            this.mSum = mSum;
        }
    }
    public int maxSubArray(int[] nums) {
        return getStatus(nums, 0 , nums.length - 1).mSum;
    }

    public Status getStatus(int[] nums, int l, int r) {
        if(l == r) {
            return new Status(nums[l],nums[l], nums[l], nums[l]);
        }
        int m = (l + r) >> 1;
        Status left = getStatus(nums, l, m);
        Status right = getStatus(nums, m + 1, r);
        return sumLeftAndRightSub(left, right);
    }

    public Status sumLeftAndRightSub(Status left, Status right) {
        int iSum = left.iSum + right.iSum;
        int lSum = Math.max(left.lSum, left.iSum + right.lSum);
        int rSum = Math.max(right.rSum, right.iSum + left.rSum);
        int mSum = Math.max(Math.max(left.mSum, right.mSum), left.rSum + right.lSum);
        return new Status(lSum, rSum, iSum, mSum);
    }
}

时间复杂度:O(n)(分治是O(logN), 但是遍历了所有节点) 空间复杂度:(OlogN)

这种方法还要维护额外的变量,有递归的调用,有什么好处呢?关键是它是一种类似线段树的想法,可以解决任何子区间[l, r]之间问题,在建成树状结构后,只需要O(logN)的时间复杂度就可以求出答案

55. 跳跃游戏 ⭐⭐

2022/3/20 20:12:00
DFS
Greedy
image-20220320183910326
image-20220320183910326

审题

  • 非负整数数组,代表最大可跳步数,判断的是能否跳到最后一个下标
  • 可能的算法:DFS / dp
  • 可以做一些优化,比如元素值都大于0,则true
  • 思路:
    • 简单:
      • DFS:构建回溯方法,当前索引,当前所跳步数
    • 进阶:一次遍历后是否可行?按理说可以
      • DP:

1. DFS(OverTime)

超时,但结果应该是对的。IDEA上测1000次超时数组,此方法用时14ms,dp用时3ms,超时没问题

三次搜索,三种情况的并集(需要考虑判断正负的条件):

  1. 当前最大步数下的下一个索引位置
  2. 邻接的下一个索引开始
  3. 当前步数-1搜索
class Solution 
    public boolean canJump(int[] nums) {
        boolean res = false;
        boolean allPositive = true;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= 0)
                allPositive = false;
        }
        if(allPositive) {
            return true;
        }
        res = dfs(nums,0,nums[0]);
        return res ;
    }
    private boolean dfs(int[] nums, int index, int cur_step) {
        if(index >= nums.length || (cur_step == 0 && index != nums.length - 1)) {
            return false;
        }
        if(nums[index] + index == nums.length - 1 || (index == nums.length - 1)) {
            return true;
        }
        boolean longJmp = false;
        boolean nextJmp = false;
        boolean decreaseJmp = false;
        if(cur_step + index < nums.length) {
            longJmp =  dfs(nums,index + cur_step, nums[index +cur_step]);
        }
        if(index + 1 < nums.length) {
            nextJmp =  dfs(nums,index+1, nums[index+1]);
        }
        decreaseJmp = dfs(nums,index, cur_step - 1);
        return longJmp | nextJmp | decreaseJmp ;
    }
}

2. DP / 贪心

DP ! 我滴超人!(其实是贪心hhh)
激动的心,颤抖的手,这道题的答案我KO

当然理论还是因为两点:

  1. 可以通过一次遍历得到
  2. 当前boolean值可以由上一个元素的是否可行的boolean值推出

DP的推导:
dp中记录的是到了当前这一个索引,还剩下多少步数(也就是最大步数,所以是贪心)可以走(因为步数肯定是连续的,从0 - m)

  1. dp[i - 1] <= 0不能够到达dp[i]
  2. dp[i - 1] > 0 能到达,这时要考虑dp[i]的值的取舍,因为保持的是当前索引还剩下的最大步数,为确保最大,则需要在nums[i]和dp[i - 1] - 1上做出取舍,取最大值。
class Solution {
    public boolean canJump(int[] nums) {
        boolean res = false;
        boolean allPositive = true;
        if(nums.length == 1) {
            return true;
        }
        // 优化一,一次遍历 能确定true但不能确定false 
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= 0)
                allPositive = false;
        }
        if(allPositive) {
            return true;
        }
        // 可优化点三,dp[] -> dp (int)
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            // 优化二,可直接调到最后一个,就可以直接判断正
            if(dp[i - 1] + i - 1 >= nums.length -1) {
                return true;
            }
            if(dp[i - 1] <= 0) {
                dp[i] = 0;
                return false;
            }else{
                dp[i] = Math.max(dp[i - 1] - 1, nums[i]);
            }
        }
        return dp[nums.length - 1] >= 0;
    }
}

这个结果我非常满意哈哈哈

image-20220320193010949
image-20220320193010949

优化的重要性

可能是题库给的测试数据偏向问题,这里我去掉了前面的一次遍历(判断是否都为正数的情况,因为全部为正数则肯定可以通过)。结果相当哇塞

image-20220320193142772
image-20220320193142772

没想到去掉了原以为影响不大的一次遍历,O(n)上不会有影响,但实际却还是相差甚远,优化的重要性是不言而喻的.这里之后应该是某几次偏差,删除后又试了下,恢复正常94%,因为题解方法最慢都是O(n),只是操作上多做了几步判断,这里这样做其实意义不是很大。

还有一个优化就是可直接一步跳到最后一格,则判正(不过貌似加上影响不大,还与添加位置有关系)

dp最根本的优化

忘记了dp最根本的优化思路,即把数组替换成单个变量

3. 简洁的思路(转)

表示当前索引下还可以跳多远,思路相似

public static boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }
        //前n-1个元素能够跳到的最远距离
        int k = 0;
        for (int i = 0; i <= k; i++) {
            //第i个元素能够跳到的最远距离
            int temp = i + nums[i];
            //更新最远距离
            k = Math.max(k, temp);
            //如果最远距离已经大于或等于最后一个元素的下标,则说明能跳过去,退出. 减少循环
            if (k >= nums.length - 1) {
                return true;
            }
        }
        //最远距离k不再改变,且没有到末尾元素
        return false;
    }

反思

  • On 一次遍历的思路帮大忙,优化的思路还是不错
  • dp最终优化没有想到,化数组为单变量
  • DFS不是很熟悉,好在磨了一会后想到了

68. 文本左右对其 ⭐⭐⭐

image-20210909101658006
image-20210909101658006

审题

每行至少有一个word

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配,则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐,且单词之间不插入额外的空格。

空格情况: 均分、不均分

1. 核心步骤拆分法硬解...

直接硬解,核心部分拆分成两个方法

  • 一行中多少个单词
  • 一行中的单词如何排列
    • 均分
    • 不均分情况
    • 最后一排
    • 只有一个单词情况
  public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        // detect how many numbers it can contain
        int column = 0;
        int index = 0;
        String newLine;
        while(index < words.length){
            int size = getMaxNumInSingle(words,maxWidth,index);
            String single = makeSingleStr(words,maxWidth,index,size);
            result.add(single);
            index+=size;
        }
        return result;
    }
	// 获取单行有多少个字母
    public int getMaxNumInSingle(String[] words, int maxWidth, int index) {
        int length = 0;
        int size = 0 ;
        for(;index<words.length;index++) {
            if(length + words[index].length()  == maxWidth) {
                size ++;
                break;
            }
            if(length + words[index].length() > maxWidth) {
                break;
            }
            if(length + words[index].length() < maxWidth) {
                // 加1 是因为空格,这里下加上不加很重要
                length += words[index].length() + 1;
                size ++;
            }
        }
        return size;       
    }
	// 获取单行单词排列后String  StringBuilder此处可优化
    public String makeSingleStr(String[] words, int maxWidth, int index, int size) {
        int i = index;
        int allLength = 0;
        StringBuilder str = new StringBuilder();
        // 一个单词情况
        if(size == 1){
            str.append(words[index]);
            for(int j = 0; j<maxWidth-words[index].length();j++){
                str.append(" ");
            }   
            return str.toString();
        
        }
        // 最后一行情况
        if(index+size == words.length) {
            for(int k = index; k<index+size-1; k++) {
                str.append(words[k]);
                str.append(" ");
            }
            str.append(words[index+size-1]);
            int strLength = str.length();
            for(int k = 0; k<maxWidth-strLength;k++){
                str.append(" ");
            } 
            return str.toString();
        }
        while(i<index+size) {
            allLength += words[i].length();
            i++;
        }
       
        int curSpaces = 0;
        for(int k = index; k < index+size-1; k++ ){
            str.append(words[k]);
            int temp = curSpaces;
            if(((maxWidth - allLength - temp)% (index+size-k-1)) == 0 ){
                for ( int j = 0 ;j<(maxWidth - allLength - temp)/(index+size-k-1);j++) {
                    str.append(" ");
                    curSpaces ++;
                }
            }
            else {
                for ( int j = 0 ;j<(maxWidth - allLength - temp)/(index+size-k-1)+1;j++) {
                    str.append(" ");
                    curSpaces++;
                }
            }
        }
        str.append(words[index+size-1]);
        return str.toString();
    }
image-20210909114750596
image-20210909114750596

这道题做起来真的还是很慢,1h......前前后后太多小错误没有顾忌到,另外String的长度是length()而不是length...

StringBuilder处可优化

也提供了一种解题思路吧,以后面对这种步骤性强的题,自己可以分成几步,然后分步解决,思路会清晰很多。

看了题解的方法,通过模拟列举出各种情况对这些情况一一讨论,和我这里的思路比较相似,不过在处理多个单词上,他的做法更好

image-20210909120051637
image-20210909120051637

这里学习一下这种方法...

69. x 的平方根 ⭐

2021/4/6 09:46:00
NewTon Iteration
Binary
image-20220405111251379
image-20220405111251379

牛顿迭代法:

    static int sqrtByNewton(int x){
      	long i=x;
        while((long)i*i>x){
            i=(i+x/i)/2;
        }
        return (int)i;
    }
image-20201009180452249
image-20201009180452249

二分法:

   static int sqrtWithBinary(int x){
  
        long result=-1;
        long left=0,right=x/2+1,mid;
        while(true){
            mid=(right+left+1)/2;
            if(mid*mid>x){
                right=mid-1;
            }else if(mid*mid<x){
                left=mid;
                result=mid;
            }else{
                return (int)mid;
            }
            if(left>=right)
                return (int)right;
        }
       /*
       	分析: 此处mid=(right+left+1)/2; 必须是在右中部。因为在左中部容易出现无限循环的现象
       */
    }
image-20201009180734101
image-20201009180734101

用除法避免 int 溢出的情况

用 int 型测试较大数字时, 由于 i*i 可能溢出,所以 需要提前设置为long 型 ,而后强转为 int

    public int mySqrt(int x) {
   
        if(x==1||x==0)return x;
        int left=0,right=x/2+1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(x/mid==mid||(x/mid>mid&&x/(mid+1)<(mid+1))){//刚好
                return mid;
            }
            else if(x/mid>mid){//mid比根小
                left=mid;
            }
            else{//mid比根大
                right=mid;
            }
        }
        return -1;

}

75. 颜色分类 ⭐⭐

2021/4/6 09:46:00
Double Pointer
image-20220115145212197
image-20220115145212197

审题

  • 原地排序,返回的还是原来的数组
  • 想法:三指针标识当前位置.难点:前段的插入会导致后一段向后移动。想法变更:先统计次数,然后提前设置好分界点

1. 顺序移位(X)

 public static  void sortColors(int[] nums) {
        int[] color = new int[3];
        int i = 0;
        int temp = nums[0];
        for(; i < nums.length; i++) {
            color[nums[i]]++;
        }
        i = 0;
        int[] cntColor = new int[3];
        while(i < nums.length) {
            temp = nums[i];
            if(cntColor[nums[i]] == color[nums[i]]) {
                i++;
                continue;
            }
            int min,max,k;
            min = max = 0;
            for(k = 0; k < nums[i]; k++) {
                min += color[nums[i]];
            }
            max = min + color[k];
            if(i < max && i >= min) {
                i++;
                continue;
            }
            int total = 0;
            for(int z = 0; z < nums[i]; z++) {
                total += color[z];
            }
            nums[i] = nums[cntColor[nums[i]] + total];
            nums[cntColor[temp] + total] = temp;
            cntColor[temp]++;
            if(i >= max || i < min){
                continue;
            }
            i++;
        }

通过用例 85/87.......

基于三指针

2. 单指针--多趟(R)

利用单指针,先一遍将0排好,再将1排好,在LogN的时间复杂度内解决问题。要注意ptr究竟代表了什么 ---> 当前最小数字的最远索引

不要小瞧这种在LogN的复杂度内多次遍历的情况,因为最终也代表了LogN的复杂度

3. 双指针(R)

针对0 和 1的顺序双指针

注意:搞清楚P1 和 P2到底指向什么---> 开始处那么我们可能会把一个 1 交换出去。当 p_0 < p_1时,我们已经将一些 1连续地放在头部,此时一定会把一个 1交换出去,导致答案错误

4. 双指针(R)

针对0 和 2 的相向双指针

相比之前的做法,也有需要注意的点:即2的指针交换i处位置后,要考虑交换的是什么,不能交换完就进行下一处交换了,因为可能交换后nums[i]的值是0或2.所以需要不停交换,直至不为2.

104. 二叉树的最大深度 ⭐

2021/4/6 09:46:00
Recursion
Tree
image-20201013151647518
image-20201013151647518

我的代码:

递归法

 public int maxDepth(TreeNode root) {
        int left=0,right=0;
     /*
     	try catch 抓nullpointer异常,避免报错
     */
        try{
        if(root.left==null&&root.right==null){
            return 1;
        }
        left= 1+maxDepth(root.left);
	    right= 1+maxDepth(root.right);
        }
        }catch(NullPointerException e){ 
        }
        return left>right?left:right;
    }
image-20201013151715852
image-20201013151715852

思考

  • 判断 Null 型对象以后 还是加上try -catch 语句更好

  • 学会使用

        left= 1+maxDepth(root.left);
        right= 1+maxDepth(root.right);
    

    类的递归方法


105. 前中序构造二叉树 ⭐⭐

2021/4/6 09:46:00
Foreach
Stack
Hash
image-20210409123330409
image-20210409123330409

思路

递归 node.left = .....

1. My 递归

public TreeNode buildTree(int[] preorder, int[] inorder) {
        return addLR(0,preorder.length-1,new TreeNode(),preorder,inorder,0);
    }
    public TreeNode addLR(int l,int r,TreeNode node,int[] preorder, int[] inorder,int i){
        if(l>r){
            return null;
        }
        if(l==r){
            return new TreeNode(inorder[l]);
        }
        int index = lookForPre(preorder[i],inorder);
        if(node == null)
            node = new TreeNode();
        node.val = inorder[index];
        node.left = addLR(l,index-1,node.left,preorder,inorder,i+1);
        node.right = addLR(index+1,r,node.right,preorder,inorder,i+index-l+1);

        return node;

    }
    public int lookForPre(int num, int[] inorder){
        int j;
        for(j =0;j<inorder.length;j++){
            if(num == inorder[j])
                return j;
        }
        return -1;
    }

image-20210409123449155
image-20210409123449155

时间复杂度 On? 空间复杂度 On

2. hashmap的小改进

 public HashMap<Integer,Integer> hashMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        hashMap = new HashMap();
        for(int i =0;i<preorder.length;i++){
            hashMap.put(inorder[i],i);
        }
        return addLR(0,preorder.length-1,new TreeNode(),preorder,inorder,0);
    }
    public TreeNode addLR(int l,int r,TreeNode node,int[] preorder, int[] inorder,int i){
        if(l>r){
            return null;
        }
        if(l==r){
            return new TreeNode(inorder[l]);
        }
        int index = lookForPre(preorder[i]);
        if(node == null)
            node = new TreeNode();
        node.val = inorder[index];
        node.left = addLR(l,index-1,node.left,preorder,inorder,i+1);
        node.right = addLR(index+1,r,node.right,preorder,inorder,i+index-l+1);

        return node;

    }
    public int lookForPre(int num){
    
        return hashMap.get(num);
    }

hashmap增加了On的占用空间但在get num在中序数组中的位置时非常快....

看来hashmap在算法题中还是很重要,设计到for循环查找时还是要考虑一下

image-20210409124022095
image-20210409124022095

3. 迭代 + 栈

image-20210409124118335
image-20210409124118335

也是类似阿里栈算法的那道题,比较难想.....

112. 路径总和⭐

2023/3/12 11:15:00
DFS

1. 递归(R)

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
        if(root.left == null && root.right == null) {
            return (targetSum - root.val == 0);
        }
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

反思

自己做这种递归题老是容易想多.....

113. 路径总和II⭐⭐

2023/3/12 18:12:00
DFS

思路

  • 输出所有可能的路径;根节点到叶子结点;注意: 不是找到一条合适的路径就可以返回了,这里必须要遍历完所有的路径
  • 直接:遍历所有从根节点到叶子结点的可能,成功则将其加入到List中

1. 遍历/DFS

核心思路还是与LeetCode-112.路径总和的问题差不多,但是需要注意的是这里是需要遍历完所有路径的。采用只能在一端增删的List

  • 对当前不为空的元素,先添加进当前List中,递归判断是否是叶子结点且满足targetSum
    • 是:拷贝一份当前List副本并且存放至外层List中, 并且将当前元素从队尾删除
    • 否:更新当前List的索引(最新元素的位置)。递归计算其左、右孩子是否满足条件。最终将当前元素从队尾删除

需要注意的是,这里递归前后涉及到元素的队尾插入和队尾删除操作,也是有DFS思想的。

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> total = new ArrayList<>(); 
        List<Integer> list = new ArrayList<>(); 
        method(root, targetSum, list, total, 0);
       
        return total;
    }
	
  	// index: 维护队尾状态的索引指针
    public void method(TreeNode root, int targetSum, List<Integer> list, List<List<Integer>> total, int index) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            if(targetSum - root.val == 0) {
                list.add(root.val);
                // add to total list
                List<Integer> temp =  new  ArrayList<>();
                for(int i = 0; i < list.size(); i++) {
                    temp.add(list.get(i));
                }
                total.add(temp);
                list.remove(list.size() - 1);
                return;
            }
        }
        list.add(root.val);
        int curIndex = list.size() - 1;
        method(root.left, targetSum - root.val, list, total, curIndex);
        method(root.right, targetSum - root.val, list, total, curIndex);
        list.remove(curIndex);
    }
}

121. 买卖股票 ⭐

2021/4/6 09:46:00
Foreach
DP
image-20201007090522974
image-20201007090522974

我的代码:

暴力法

  1. //暴力法:    for二重循环 两指针索引 遍历    
    //缺点 : 时间慢, 有重复计算           
    //时间复杂度:  O(n^2)  空间复杂度 O(1)--一个常量
    public static int maxProfit(int[] prices) {
            int max=0;
            for(int i=0;i<prices.length;i++){
                for(int j=prices.length-1;j>i;j--){
                    if(prices[j]-prices[i]>max) {
                        max = prices[j] - prices[i];
                    }
                }
            }
            return max;
        }
    
    image-20201007090734202
    image-20201007090734202

动态规划

//动态规划  一次遍历
//原因:  买入的 股票价格总是在最前面!!!
//时间复杂度: O(n)  空间复杂度 O(1)--两个常量
public static int maxProfit_2(int[] prices) {
        int max=0,min=Integer.MAX_VALUE;
        for(int i=0;i<prices.length;i++){
           	if(prices[i]<min)
                min=prices[i];
            else if(prices[i]-min>max)	//这一步很重要
                max=prices[i]-min;
        }
        return max;
    }
image-20201007092356306
image-20201007092356306

134. 加油站 ⭐⭐

2021/4/6 09:46:00
Foreach
Math

在所求点后的过程量 >= 0 的情况

image-20220228202154091
image-20220228202154091

审题

  • 油箱容量是无限的,开始油箱为空 ; 若存在解 则解唯一、
  • 可能的数据结构:
  • 可能的算法:迭代?动态规划?
  • 先尝试最简单的:依次循环

1. 暴力迭代

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int i = 0;
        int res ;

        for(; i < gas.length; i++) {
            res = 0;
            for(int j = 0; j < gas.length; j++) {
                if(i + j >= gas.length) {
                    res += gas[i + j - gas.length];
                    res -= cost[i + j- gas.length];
                }else{
                    res += gas[i + j];
                    res -= cost[i + j];
                }
                if(res < 0) {
                    break;
                }
            }
            if(res >= 0){
                return i;
            }
        }
        return -1;
    }
}

理所应当的超时.....

稍稍优化:temp[i] = gas[i] - cost[i];

2. 一次遍历

捞汁巨聪明,核心还是两个数组差值组成的新数组到达某一限度的判定问题。核心:

  • before:管之前没有达标的那一部分数,就不用之后再回归头算一次了
  • res:管当前可能的累计和,有可能不会<0,也可能<0。如果<0,则就需要累加到before上并清零这个res
  • 若最终before + res < 0 则不存在这样的点,因为遍历了所有的点都不行

这里我优化了一下:

  • 能够到达加油站的必要条件:差值数组和必须大于0

这里单独把差值数组提前算出来是没有意义的,浪费了On的空间,所有结果的空间复杂度这么高,其余的话应该都是最优的。

 public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int res;
        int before ;
        int index = 0;
        int[] temp = new int[n];
        for(int i = 0; i < n; i++) {
            temp[i] = gas[i] - cost[i];
        }
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += temp[i];
        }
        if(sum < 0)
            return -1;
        before = 0;
        res = 0;
        for(int i = 0; i < n; i++) {
            if(temp[i] < 0 && res + temp[i] < 0){
                if(res + temp[i] < 0){
                    before += res + temp[i];
                    res = 0;
                    index = i + 1;
                }
            }else{
                res += temp[i];
            }
        }
        if(res + before < 0)
            return -1;
        return index;
    }
image-20220301213651013
image-20220301213651013

解决一个自己很蠢的问题:
数组超出长度后回到头部:(i+cnt)%arr.length....不要再用什么if else判断了

3. 折线图的思想

一种很巧妙的方法,也是不容易想通的。找出差值的最小值点,折线图表示的是以0加油站为起点的(在0加油站时没加油也没耗油)油耗情况,绿色代表gas 黄色代表cost。

折线图表示的肯定是一个或者多个V形的走势,那只需要把最小的那个点找出来,以那个点的下一个站为起点,在最终油量剩余量 >= 0的情况下,肯定过程油量的>=0的(因为图的起点不一样了,以那个站点为起点,则不可能再出现X轴的情况) 可以理解是把图像竖直平移再水平平移(更换了站点)

image-20220301221158225
image-20220301221158225

图摘自链接:https://leetcode-cn.com/problems/gas-station/solution/shi-yong-tu-de-si-xiang-fen-xi-gai-wen-ti-by-cyayc/open in new window

public int canCompleteCircuit(int[] gas, int[] cost) {
    int len = gas.length;
    int spare = 0;
    int minSpare = Integer.MAX_VALUE;
    int minIndex = 0;

    for (int i = 0; i < len; i++) {
        spare += gas[i] - cost[i];
        if (spare < minSpare) {
            minSpare = spare;
            minIndex = i;
        }
    }

    return spare < 0 ? -1 : (minIndex + 1) % len;
}

// 作者:cyaycz
// 链接:https://leetcode-cn.com/problems/gas-station/solution/shi-yong-tu-de-si-xiang-fen-xi-gai-wen-ti-by-cyayc/。
image-20220301221650883
image-20220301221650883

作者的结果显示内存消耗为 72%,可能有误差,但这确实也从图像的方向上提供了一个非常好的思路

137. 只出现一次的数字II ⭐

只出现一次的数字I -----

image-20220504190821760
image-20220504190821760

审题

1. Hash + List缓存

这个做法治标不治本,因为他并没有区分是其他数字都重复了三次,如果其他数字重复了N次,也可以通过这个做法来算,所以他不太可能是针对当前算法的最好解法,只能说是通解

    public int singleNumber(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.get(nums[i]) == null) {
                map.put(nums[i], 1);
                list.add(nums[i]);
            }else{
                int temp = map.get(nums[i]);
                map.put(nums[i],++temp);
            }
        }
        for(int i = 0; i <list.size(); i++) {
            if(map.get(list.get(i)) == 1) {
                return list.get(i);
            }
        }
        return nums[0];
    }

O(2N)的时间复杂度 O(N)的空间复杂度。直接遍历Hash表的键值对也可以,这样空间复杂度能提到70%

2. 有限状态自动机(转)

146. LRU缓存 ⭐⭐

image-20210411092859009
image-20210411092859009

思考

get 和 put的方法说明

1. My LruHashMap

 static class Node {
        Node next,prev;
        int key;
        int value;
        Node(int key,int value){
            this.key = key;
            this.value = value;
        }
        Node(){}
    }
    private HashMap<Integer,Node> cache;
    private  int size;
    private int MaxSize;
    private Node head,tail;
    public LRUCache(int capacity) {
        cache = new HashMap();
        size = 0;
        MaxSize = capacity;
        head = new Node();
        tail = new Node();
        tail.prev  = head;
        head.next = tail;
    }

    public int get(int key) {
        Node res = cache.get(key);
        if(res == null) {
            return -1;
        }
        addToTail(res);

        return res.value;
    }

    public void put(int key, int value) {
        if(size == 0){
            Node node = new Node(key,value);
            head = node;
            tail = node;
            size++;
            cache.put(key,node);
        }else {
            Node temp = cache.get(key);
            if (temp != null) {
                temp.value = value;
                addToTail(temp);
            } else {
                Node node = new Node(key, value);
                cache.put(key, node);
                addNewToTaile(node);
                size++;
                if (size > MaxSize) {
                    removeEldest();
                    size--;
                }
            }
        }
    }
    public void addNewToTaile(Node node) {
        node.next = null;
        node.prev = null;
        node.prev = tail;
        tail.next = node;
        tail = node;

    }
    public void addToTail(Node node){
        if(head == tail){
            return ;
        }
        else if(node == tail){
            return ;
        }
        else if(node == head){
            Node temp;
            temp = node.next;
            head = temp;
            head.prev =null;
        }else{
            Node prev,next;
            prev = node.prev;
            next = node.next;
            if(prev == null){
                tail = node.next;
                tail.prev = null;
            }else if(next == null){

            }else{
                node.prev.next = next;
                node.next.prev = prev;
            }


        }
        addNewToTaile(node);

    }
    public void removeEldest(){
        Node temp ;
        cache.remove(head.key);
        temp = head.next;
        head = temp;
        head.prev = null;

    }
 static class Node {
        Node next,prev;
        int key;
        int value;
        Node(int key,int value){
            this.key = key;
            this.value = value;
        }
        Node(){}
    }
    private HashMap<Integer,Node> cache;
    private  int size;
    private int MaxSize;
    private Node head,tail;
    public LRUCache(int capacity) {
        cache = new HashMap();
        size = 0;
        MaxSize = capacity;
        head = new Node();
        tail = new Node();
        tail.prev  = head;
        head.next = tail;
    }

    public int get(int key) {
        Node res = cache.get(key);
        if(res == null) {
            return -1;
        }
        addToTail(res);

        return res.value;
    }

    public void put(int key, int value) {
        if(size == 0){
            Node node = new Node(key,value);
            head = node;
            tail = node;
            size++;
            cache.put(key,node);
        }else {
            Node temp = cache.get(key);
            if (temp != null) {
                temp.value = value;
                addToTail(temp);
            } else {
                Node node = new Node(key, value);
                cache.put(key, node);
                addNewToTaile(node);
                size++;
                if (size > MaxSize) {
                    removeEldest();
                    size--;
                }
            }
        }
    }
    public void addNewToTaile(Node node) {
        node.next = null;
        node.prev = null;
        node.prev = tail;
        tail.next = node;
        tail = node;

    }
    public void addToTail(Node node){
        if(head == tail){
            return ;
        }
        else if(node == tail){
            return ;
        }
        else if(node == head){
            Node temp;
            temp = node.next;
            head = temp;
            head.prev =null;
        }else{
            Node prev,next;
            prev = node.prev;
            next = node.next;
            if(prev == null){
                tail = node.next;
                tail.prev = null;
            }else if(next == null){

            }else{
                node.prev.next = next;
                node.next.prev = prev;
            }


        }
        addNewToTaile(node);

    }
    public void removeEldest(){
        Node temp ;
        cache.remove(head.key);
        temp = head.next;
        head = temp;
        head.prev = null;
    }

根据LinkedHashMap 而来 --- 内部节点前后指针,并且存储通过 Key,Node<Key,Value>存

注意特殊情况判断(这里一个bug卡了很久很久),注意插入 时容量判断问题

image-20210411111403208
image-20210411111403208

155. 最小栈 ⭐

image-20210426175732260
image-20210426175732260

思考

1. 自定义

class MinStack {

    /** initialize your data structure here. */
    class Node{
        int val;
        Node next;
        Node(int val){
            this.val = val;
        }
    }
    Node head;
    Node min;
    public MinStack() {
        head = null;
        min = head;
    }
    
    public void push(int val) {
        Node node = new Node(val);
        node.next = head;
        head = node;
        if(min == null){
            min = head;
        }else if(min.val > val){
            min = node;
        }
    }
    
    public void pop() {
        if(head.val == min.val){
            Node node = head.next;
            min = node;
            while(node != null){
                min = node.val>min.val ?  min:node;
                node = node.next;
            }
        }
        head = head.next;
        
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return min.val;
    }
}
image-20210426181131420
image-20210426181131420

思路就是维护一个头指针,和一个最小指针,在pop时进行判断,虽然会有偶尔的On时间复杂度,但整体来说是好的。从Lru中学到

162. 寻找峰值 ⭐⭐

2021/4/6 09:46:00
Foreach
Binary
image-20210915162321698
image-20210915162321698

审题

  • 严格大于
  • 包含多个,返回任意一个
  • 时间复杂度O(logn),想到了二分?
  • 返回的是索引值而不是值

1. 顺序判断

  public int findPeakElement(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        if(nums.length == 2) {
            return nums[0] > nums[1] ? 0: 1;
        }
        int index = 1;
        while(index < nums.length - 1) {
            if(nums[index] > nums[index-1] &&
                nums[index] > nums[index + 1]) {
                    return index;
                }
            else if (nums[index] < nums[index + 1]){
                index++;
            }
            else {
                index += 2;
            }
        }
        if(nums[nums.length - 1] > nums[nums.length - 2]) {
            return nums.length - 1;
        }
        return 0;
	}
image-20210915184419620
image-20210915184419620

这里我最开始想到二分查找,但没想到如何二分,index+=2有点二分的意思,但这里不满足Ologn的时间复杂度(例如{1,2,3,4,5,6,7})

2. 二分查找(转)

public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        for (; left < right; ) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

目的是:在区间内有峰值

首先要注意题目条件,在题目描述中出现了 nums[-1] = nums[n] = -∞(这是关键!),这就代表着 只要数组中存在一个元素比相邻元素大,那么沿着它一定可以找到一个峰值

感觉还是审题没有仔细。。。

172. 阶乘后的零 ⭐⭐

2022/3/28 21:20:00
Math
Foreach
image-20220326102711274
image-20220326102711274

审题

  • 返回的是结果中含有的零的个数(0不算,要尾随)
  • 数学层面:
    • 2 * 5 = 0
  • 思路:
    • 直接:算出数,然后依次 / 10 % 10看0的个数。不行:因为实际运算存在溢出
    • 进阶:
      • 位运算?kcm?dp
      • 👍 因式分解 看2 和 5的个数, 因为是尾随所以可以这样做
      • 零的个数 = 原本有的 + 进位产生的
      • 能否在On 或 Oc的时间复杂度内计算出?

1. 因式分解

我是傻杯之不读题……题的意思是尾随的零的个数,是最后几位全是零的个数,而不是求总的零的个数

故只需要找到 2 和 5的个数即可,取最小值因为除2 * 5外,其他的数相乘都不可能构成尾随零(但有可能构成中间零)

public int trailingZeroes(int n) {
        int temp;
        int a = 0;
        int b = 0;
        while(n >= 2) {
            temp = n;
            while(temp % 5 == 0 && temp /5 != 0) {
                temp /= 5;
                b++;
            }
            while(temp % 2 == 0 && temp / 2 != 0) {
                temp = temp >> 1;
                a++;
            }
            n--;
        }
        return Math.min(a,b);
    }

时间复杂度在On之上

image-20220326112031199
image-20220326112031199

反向优化

说白了是找5的个数,但是迭代时会有重复的5的倍数的记录,因此之类用map去替代,但效果甚至更差

public int trailingZeroes(int n) {
        if(n < 5) {
            return 0;
        }
        int b = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(5,1);
        initHashMap(n, map);
        for(int i = 5; i <= n; i++) {
            b += map.get(i);
        }
        return b;
    }
    void initHashMap(int n , Map<Integer,Integer> map) {
        int origin;
        int temp = 6;
        origin = temp;
        int lastNum = 1;
        while(temp <= n) {
            int div = temp / 5;
            if(temp % 5 == 0 ) {
                if(map.get(div) != null) {
                    lastNum = map.get(div) + 1;
                    map.put(temp, lastNum);
                }else{
                    lastNum = 1;
                    map.put(temp, lastNum);
                }
            }else{
                map.put(temp,0);
            }
            temp = origin++;
        }
    }

优化

其实2的个数是远大于5的个数的,所以只用统计5的个数即可

 public int trailingZeroes(int n) {
        int b = 0;
        int temp = n;
        while(temp > 4) {
            while(temp % 5 == 0 && temp / 5 != 0) {
                temp = temp / 5;
                b++;
            }
            temp = --n;
        }
        return b;
    }
image-20220328192949855
image-20220328192949855

2. 数学公式

心态小炸,但还是想出来了

实际上就是数学问题,找n中含有5的个数,然后把这些N加起来,其实可以更宏观的来看,不用从每个数的角度来看。因为本身基于数学,所以肯定是有数学规律的,规律:

每隔5^n - 1个数,就总计会有n个5出现 (思考思路可以从 额外贡献来看)

class Solution {
	public int trailingZeroes(int n) {
        if(n < 5) {
            return 0;
        }
        int res = 0;
        int temp = n;
        int par = 5;
        while(temp / 5 != 0) {
            res += n / par;
            par *= 5;
            temp /= 5;
        }
        return res;
    }
}

O(log_5{N})的时间复杂度

image-20220328210847131
image-20220328210847131

优化

LeetCode题解,思路相同,但代码简洁许多

    public int trailingZeroes(int n) {
        int ans = 0;
        while (n != 0) {
            n /= 5;
            ans += n;
        }
        return ans;
    }

反思

  • 就估计这道题是数学问题,因为本来最开始使用方法加上优化已经还不错了,但是还是有问题,估计肯定有最简洁的数学公式在Oc的时间复杂度内计算出来
  • 应用模型 👉 数学问题的转化还不能很明显的感知(比如这里找2 和 5 然后再到找5的这个过程是不太快速的)
  • ⚠️ 看问题有时候太细致,不够宏观,有时候从微观到宏观,从迭代到整体考虑,可能会有新的发现
  • 有点死磕.......

189. 轮转数组 ⭐⭐

2022/11.1 21:00:00
image-20221101205933184
image-20221101205933184

审题

  • 需要思考的问题,想通过一次移位来解决,但需要确保移位后的 原来位置的元素的保存以及移位,要解决形成的递归关系难

1. 多次单次移位

超时

void rotate(int* nums, int numsSize, int k){
    for(int i = 0; i < k; i++) {
        rotateByOne(nums, numsSize);
    }
}

void rotateByOne(int *nums, int numsSize) {
    int temp = nums[numsSize - 1];
    for(int i = numsSize - 1; i > 0; i--) {
        nums[i] = nums[i-1];
    }
    nums[0] = temp;
}

2. 标志+双层前进

类似贪婪算法,维护一个当前的指标index,index前的元素都是已经右移k位的。如果对第index位,右移k位后,如果第 (index+k) % size位没有被右移,则将该位右移,依次迭代重复。时间复杂度在On

缺点:需要空间为On的数组来保存当前索引位上是否被右移的标志。

void rotate(int* nums, int numsSize, int k){
    int index = 0;
    int *bucket = (int *) (calloc(numsSize,  sizeof(int)));
    int x1, x2 = 0;
    while(index < numsSize) {
        int cur_index = index;
        x1 = nums[cur_index];
        while(bucket[cur_index] == 0) {
            // exchange relavant nums
            x2 = nums[(cur_index + k)%numsSize];
            nums[(cur_index + k) % numsSize] = x1;
            bucket[cur_index] = 1;
            cur_index = (cur_index + k)%numsSize;
            x1 = x2;
        }
        index++;
    }
}
image-20221101220112436
image-20221101220112436

3. 双层移位+gcd

基于之前的递归类的右移,也就是一次性把一个索引位的元素 以及右移k位的元素 以及右移2k位的元素进行右移,也就是先处理一个循环周期内的元素.....这里主要分两类讨论,设元素个数为n,右移次数为k

  1. n 恰好能被k整除,即能在一趟跑遍 n/k个元素,需要跑k躺:
  2. n不能被k整除,分两种情况(其实合起来是一种情况):
    1. 一趟内跑遍n个元素,例如(n = 7, k=3)
    2. 一趟内跑不遍n个元素,只能跑完部分的元素,之后便会陷入重复(n = 8,k=6)

此时存在的数学关系: $$最终每个趟遍历元素数 = n / gcd(n, k) $$

此时就能在On的时间复杂度和O1的空间复杂度内解决问题(代码部分有待优化)

int gcd(int a, int b) {
    int t = 1;
    while(a % b) {
        t = a%b;
        a = b;
        b = t;
    }
    return t;
}
void rotate(int* nums, int numsSize, int k){
    if(k == 0) {
        return nums;
    }
    int x1, x2, max = 0;
    int out_foreach_count = k;
    if(numsSize % k != 0) {
        max = numsSize / gcd(numsSize, k);
        out_foreach_count = numsSize / max;
    }else{
        max = numsSize / k ;
    }
    for(int i =0 ; i < out_foreach_count; i++) {
        int count = 0;
        int cur_index = i;
        x1 = nums[cur_index];
        
        while(count < max) {
            // exchange relavant nums
            x2 = nums[(cur_index + k)%numsSize];
            nums[(cur_index + k) % numsSize] = x1;
            cur_index = (cur_index + k)%numsSize;
            x1 = x2;
            count++;
        }
    }  
}
image-20221102201002428
image-20221102201002428

4. 数组翻转(R)

LeetCode上提供的一种方法,也非常的巧妙。有时间可以再看一下。

198. 打家劫舍 ⭐⭐

2022/4/14 22:17:00
DP
Greedy
image-20220414200221714
image-20220414200221714

审题

  • 不能在相邻的房间内偷窃,问题转换:判断一个数组在选定数无相邻情况下的和的最大值
  • 特殊情况:可以一次跳多个数字,[6,1,2,9],这种情况就可以跳2格,因为1-2的值小于0
  • 可能的算法:贪心?DP?
  • 思路:
    • 直接:
    • DP:初始化数组,数组中的值还有是否拜访了当前值的标记,第n种的思路可以等于等1 ~ n-1种之和,取n-1时则其不能拜访当前的值

1. DP

贪心和DP的思想:我当前偷到第n户时我都保持了最大能偷的钱数,那么在偷第N+1家时,我需要注意:

  • 是否能偷这家?也就是是否偷了上家
    • 能偷则直接偷了因为肯定偷了比没偷好啊
    • 不能偷,那要么不偷上家偷这家,要么偷上家不偷这家
      • 偷上上家+偷这家的钱 > 偷上家不偷这家的钱,则偷这家钱的最大值就等于前者,并且还要说明偷了这家
      • 偷上上家+偷这家的钱 < 偷上家不偷这家的钱,则偷这家钱的最大值等于后者
   public int rob(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }
        int i;
        int[] isGo = new int[nums.length + 1];
        int[] curMax = new int[nums.length + 1];
        curMax[1] = nums[0];
        isGo[1] = 1;
        for(i = 2; i < nums.length + 1; i++) {
            if(isGo[i - 1] == 1) {
                if(curMax[i - 2] + nums[i - 1] < curMax[i - 1]) {
                    curMax[i] = curMax[i - 1];
                }else{
                    curMax[i] = curMax[i - 2] + nums[i - 1];
                    isGo[i] = 1;
                }
            }else{
                curMax[i] = curMax[i - 1] + nums[i - 1];
                isGo[i] = 1;
            }
        }
        return curMax[i - 1];

O(N)的时间复杂度 O(N)的空间复杂度

image-20220414202724884
image-20220414202724884

优化

DP从数组到常量个变量的经典优化:因为实际计算值只与curMax[i-1]、curMax[i-2]和isGo[i-1]有关,因此均可优化为常量级别的数组,以此降低空间复杂度到O(C) 。

public int rob(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }
        int i;
        int isGo = 0;
        int[] curMax = new int[3];
        curMax[1] = nums[0];
        isGo = 1;
        for(i = 1; i < nums.length; i++) {
            if(isGo == 1) {
                if(curMax[0] + nums[i] < curMax[1]) {
                    curMax[2] = curMax[1];
                }else{
                    curMax[2] = curMax[0] + nums[i];
                    isGo = 1;
                }
            }else{
                curMax[2] = curMax[1] + nums[i];
                isGo = 1;
            }
            curMax[0] = curMax[1];
            curMax[1] = curMax[2];
        }
        return curMax[2];
    }
image-20220414220207768
image-20220414220207768

题解用Math.max优化了分支代码,取消了isGo的遍历,这个优化需要注意!使得代码非常简便

for (int i = 2; i < length; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }

再回首

2023/3/4 11:00:00
public int rob(int[] nums) {
      if(nums.length  == 1) {
          return nums[0];
      }
      // day_x: x-1 days ago
      int day_3, day_2, day_1;
      int i;

      day_3 = nums[0];
      day_2 = Math.max(nums[0], nums[1]);
      day_1 = 0;

      for(i = 2; i < nums.length; i++) {
          day_1 = Math.max(day_3 + nums[i], day_2);
          day_3 = day_2;
          day_2 = day_1;
      }
      return day_2;
  }

思路清晰了很多,先理清偷和不偷今天的盈利,然后考虑DP的数组形式,就能把大致思路想出来,再考虑DP的简化形式

总结

  • 这道题做的很快,因为思路很清楚,为什么思路清楚?因为提到了钱,讨论钱的最大值再加上本身问题有迭代性质因素,所以想到了贪心和DP
  • 然后先想清楚了大致思路才写的代码,把一些坑给避开了,这点很重要

206. 反转链表 ⭐

2021/4/6 09:46:00
Foreach
Recursion

1. 迭代

 public ListNode reverseList(ListNode head) {
      ListNode cur = null;
        ListNode pre = head;
        ListNode temp=null;
        try {

            while (pre != null) {
                temp = pre.next;
                pre.next = cur;
                cur = pre;
                pre = temp;
            }
        }catch (NullPointerException e){

        }
            return cur;
    }
image-20201016183423559
image-20201016183423559

2. 递归

  public ListNode reverseList(ListNode head) {
        ListNode cur=null;
        try{
     if(head.next==null||head==null){
            return head;
        }
        
         cur=reverseList(head.next);
        
        head.next.next=head;
        head.next=null;
        }catch(NullPointerException e){

        }
        return cur;
    }
image-20201016184502839
image-20201016184502839

212. 单词搜索 II ⭐⭐⭐

image-20210916143557702
image-20210916143557702

审题

  • 单词必须按照字母顺序,通过 相邻的单元格 内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
  • 类似DFS?
  • 这里每一个单词首字母寻找肯定要耗费时间,能不能用dp规划出每个字母的相邻位置的字母
  • 注意相同字母可能在表中出现多次

1. 我的代码

这里没有做出来,因为后面涉及到了DFS,没有考虑到

public List<String> findWords(char[][] board, String[] words) {
        int m = board.length;
        int n = board[0].length;
        int shouldExit = -1;
        int index = 0;
        List<String> result = new ArrayList<>();
        char[][] dp = new char[m+2][n+2];

        for(int i = 0 ;i < m+2; i++) {
            for(int j = 0 ;j < n+2 ;j++) {
                if(i==0||i==m+1||j==0||j==n+1){
                    dp[i][j] = ' ';
                }else{
                    dp[i][j] = board[i-1][j-1];
                }
            }
        }
        for(int i = 1 ;i < m+1; i++) {
            if(shouldExit == 1) {
                break;
            }
            for(int j = 1 ;j < n+1 ;j++) {
                if(dp[i][j] == words[index].charAt(0)) {
                    int wordsLength = 1;
                    int x = i;
                    int y = j;
                    int[][] his = new int[words[index].length][2];
                    his[0][0] = i;
                    his[0][1] = j;
                    while(true){
                        if(wordsLength == words[index].length()){
                            result.add(words[index]);
                            index++;
                            i = 0 ;
                            j = 0;
                            break;
                        }
                    
                        int[] twin = isCharInAround(words[index].charAt(wordsLength),dp,x,y,his);
                        if(twin == null){
                            break;
                        }
                        his[wordsLength][0] = twin[0];
                        his[wordsLength][1] = twin[1];
                        x = twin[0];
                        y = twin[1];
                        wordsLength++;

                    }
                }
              
                if(i == m && j == n && index < words.length){
                    i = 0;
                    j = 0;
                    index++;
                   
                }
                  if(index ==  words.length) {
                    shouldExit = 1;
                    break;
                }
                
            }
        }
        return result;
    }

    public int[] isCharInAround(char target, char[][] board, int i, int j,int][] his) {
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if(board[i][j+1] == target) {
            res[0] = i;
            res[1] = j+1;
        }else if(board[i][j-1] == target){
            res[0] = i;
            res[1] = j-1;
        }else if(board[i+1][j] == target){
              res[0] = i+1;
            res[1] = j;
        }else if(board[i-1][j] == target){
              res[0] = i-1;
            res[1] = j;
        }
        for(int i = 0; i< his.length; i++){
            if(his[i][0] == res[0] && his[i][1] == res[1]) {
                
            }
        }
        return res;
    }

2. 前缀树+回溯 (转)

这里前缀树之前没了解过,看了下结构,不错

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

    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
		// 细节,去重
        Set<String> ans = new HashSet<String>();
        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                dfs(board, trie, i, j, ans);
            }
        }

        return new ArrayList<String>(ans);
    }

    public void dfs(char[][] board, Trie now, int i1, int j1, Set<String> ans) {
        if (!now.children.containsKey(board[i1][j1])) {
            return;
        }
        char ch = board[i1][j1];
        now = now.children.get(ch);
        if (!"".equals(now.word)) {
            ans.add(now.word);
        }
		// 避免找到重复的位置(也是我思路中卡壳的地方)
        board[i1][j1] = '#';
        for (int[] dir : dirs) {
            int i2 = i1 + dir[0], j2 = j1 + dir[1];
            if (i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length) {
                dfs(board, now, i2, j2, ans);
            }
        }
        // 还原
        board[i1][j1] = ch;
    }
}

class Trie {
    String word;
    Map<Character, Trie> children;
    boolean isWord;

    public Trie() {
        this.word = "";
        this.children = new HashMap<Character, Trie>();
    }

    public void insert(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (!cur.children.containsKey(c)) {
                cur.children.put(c, new Trie());
            }
            cur = cur.children.get(c);
        }
        cur.word = word;
    }
}
image-20210916155107007
image-20210916155107007

复杂度分析

image-20210916154957941
image-20210916154957941

有时间得看一下前缀树,常用于字符串的查找,以后遇到这种问题可以纳入考虑

3. 删除被匹配的单词

213. 打家劫舍 II ⭐⭐

2021/4/20 18:48:00
DP
image-20220417193550616
image-20220417193550616

审题

  • 房屋围成一圈,不能偷相邻的

1. DP (转)

寄,想复杂了。。。。。

其实只有三种情况:

  • 房间数=1,则就直接偷
  • 房间数=2,选最多钱的偷
  • 房间数>2,看偷不偷第一家
    • 偷第一家,则不能偷最后一家
    • 不偷一家,则能够偷(但不一定会偷)最后一家
class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}
image-20220420184557190
image-20220420184557190

反思

  • 这个题自己想复杂了,想成循环链表又想到如何动态规划
  • 没有关注相比 I 题变换的本质:仅仅是首尾的变换,不影响中间元素。

219. 存在重复元素II ⭐

2021/4/6 09:46:00
Foreach
Hash
Sort
Slide-Window

⏲️ 2022 / 1 / 19 11:30 AM

image-20220119102137168
image-20220119102137168

审题

  • 可能做法: 遍历肯定行;双指针?滑动窗口?栈?
  • 注意:不必完全找出来所有的可能啊!
  • 有点抽屉原理的感觉

1. 遍历

对数组进行遍历,对每一个 i 向前看k个数,最终得到时间复杂度为$$O(N * K)$$

似乎还行?

public boolean containsNearbyDuplicate(int[] nums, int k) {
        for(int i = 0; i < nums.length; i++) {
            for(int j = i+1; j < nums.length && j <= i + k; j++) {
                if(nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
image-20220119102849895
image-20220119102849895

寄,当K接近N的时候,就变成$$O(N^2)$$的时间复杂度了,慢是正常的....考虑下一种

2. 哈希

public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hashmap = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int temp = hashmap.getOrDefault(nums[i], -1);
            if(temp == -1) {
                hashmap.put(nums[i], i);
            }else {
                if(i - temp <= k) 
                    return true;
                hashmap.put(nums[i], i);
            }
        }
        return false;
    }
image-20220119104042709
image-20220119104042709

On的时间复杂度,On以上的空间复杂度(哈希表扩容),时间还是比较慢

优化后

set保证单一
remove保证没有过期元素

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            if(set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }

3. 桶

int max, min;
        max = min = nums[0];
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > max)
                max = nums[i];
            if(nums[i] < min)
                min = nums[i];
        }
        int[] bucket = new int[max - min + 1];
        for(int i = 0; i < bucket.length; i++) {
            bucket[i] = -1;
        }
        for(int i = 0; i < nums.length; i++) {
            int temp = bucket[nums[i] - min];
            if(temp == -1) {
                bucket[nums[i] - min] = i;
            }else {
                if(i - bucket[nums[i] - min] <= k)
                    return true;
                bucket[nums[i] - min] = i;
            }
        }
        return false;

失败,超出内存限制

4. 排序

O(N * (logN))的快排,然后遍历比较就行
还需要一个数组来维护索引的顺序 On的空间复杂度

5. 滑动窗口 + Hash(转)

遍历过程中用哈希表存储元素并同时判断窗口大小是否超过了K。用哈希Set这里也就不用自己判断了

 public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> cache = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (i - k > 0) {
                cache.remove(nums[i - k - 1]);
            }
            if (!cache.add(nums[i])) {
                return true;
            }
        }
        return false;
    }
image-20220119112251084
image-20220119112251084

牛逼.....

总结

这里最开始做的时候思路大体是对的,要数字决定的索引之间的差值关系,就考虑用桶或者哈希,但自己用了哈希后感觉用桶排序会更快,但后面一直纠结实现桶排序但未考虑最大值而超出了内存限制。感觉自己还是一直纠结把索引保存下来,但其实这里不用保存索引关系,考虑了滑动窗口的问题只需要留一段窗口内的值就行了呀......

  • 看到值决定的索引间关系问题考虑用哈希
  • 重复元素判别问题考虑Set,可能比Hash快
  • 数组一定范围内的问题考虑滑动窗口,滑动窗口实现方式可以是多种多样的,不一定是数组哦!

223. 矩形面积 ⭐⭐

image-20210930110121794
image-20210930110121794

审题

  • 两种情况:
    • 未覆盖
    • 覆盖(可能完全包含)
  • 如何判断是否覆盖?
  • 关键: 如何计算覆盖区域的面积?
  • 难道是模拟? 分类太多,直接放弃

260. 只出现一次的数字III ⭐⭐

2021/4/6 09:46:00
Bit
Hash
image-20220307183103546
image-20220307183103546

审题

  • 恰好两个元素只出现一次,其他元素均出现两次;数组 ---> 一次遍历即为较优秀的算法
  • 考虑线性时间复杂度的算法和常数空间复杂度
  • 可能的做法:哈希
  • 想法:
    • 简单:暴力循环。需要O(n^2)的时间复杂度
    • 进阶:哈希两次外循环,需要O(n)时间复杂度和O(n)空间复杂度
    • 高级:On的空间复杂度,想不出来.....

1. 哈希 两次遍历

第一次遍历填值,第二次遍历判断

public int[] singleNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = new int[2];
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i],0) + 1);
        }
        int index = 0;
        for(int i = 0; i < nums.length; i++) {
            if(map.get(nums[i]) == 1) {
                res[index] = nums[i];
                index++;
            }
        }
        return res;
    }
image-20220307183936426
image-20220307183936426

On的时间复杂度,但受到Map扩容方面的问题

2. 位运算(转)

直接忘得一干二净,之前还专门有做过一模一样的题,忘了。比较有技巧性。一个异或的公式说明一切问题:

a \oplus b \oplus a =b$$ 异或具有交换律、结合律、自反律 思路:所有异或结果最终为$a_1 \oplus a_2 $,肯定不等于0。然后再遍历一次,每一次用nums[i]去做&运算,检验是否==1(>0),不等于0则type1^=nums[i],得到一类的数,等于0则type2 ^=nums[i],得到另一类的数。 关键是理解这个两个不同的数通过&运算被分配到两个不同类中 ```java class Solution { public int[] singleNumber(int[] nums) { int xorsum = 0; for (int num : nums) { xorsum ^= num; } // 防止溢出 int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum)); int type1 = 0, type2 = 0; for (int num : nums) { if ((num & lsb) != 0) { type1 ^= num; } else { type2 ^= num; } } return new int[]{type1, type2}; } } // 作者:LeetCode-Solution // 链接:https://leetcode-cn.com/problems/single-number-iii/solution/zhi-chu-xian-yi-ci-de-shu-zi-iii-by-leet-4i8e/ ``` ![image-20220307194816611](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20220307194816611.png) ### 反思 * 主要还是能通过两个相同的数想到异或,这是解题的关键,想不到就直接寄...... * 走投无路时想想基本的方法,这里我dp 队列栈 都考虑过,但因为条件太少,题目简单,还是想不到方法,还忘了基本的位运算,确实条件越少就越该考虑。 ## 263. 丑数 :star: <div class="code-tag-time">2021/4/6 09:46:00</div> <div class="code-tag-label code-tag-label-foreach">Foreach</div> <div class="code-tag-label code-tag-label-recursion">Recursion</div> ![image-20210410093526939](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20210410093526939.png) ### 思考 位运算? ### 1. 简单递归 ```java public boolean isUgly(int n) { if(n == 0) return false; if(n == 1) return true; if((n & 1) == 0) return isUgly(n/2); if((n % 3) == 0) return isUgly(n/3); if((n % 5) == 0) return isUgly(n/5); return false; } ``` ![image-20210410094617676](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20210410094617676.png) 时间复杂度On ### 2. 迭代 ```java public boolean isUgly(int n) { if(n == 0){ return false; } boolean bool = false; while( n!=1 ){ if((n & 1) == 0){ n=n/2; } else if((n % 3) == 0){ n=n/3; } else if((n % 5) == 0){ n=n/5; } else { break; } } if(n == 1){ bool = true; } return bool; } ``` ![image-20210410095627239](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20210410095627239.png) 还是很有感触,这迭代还是很快 ..... 所以能用迭代还是用迭代把 ## 279. 完全平方数 :star::star: <div class="code-tag-time">2021/4/6 09:46:00</div> <div class="code-tag-label code-tag-label-dp">DP</div> <div class="code-tag-label code-tag-label-bfs">BFS</div> <div class="code-tag-label code-tag-label-math">Formula</div> ![image-20220119202324149](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20220119202324149.png) ### 审题 * 完全平方数要最少。可能的组合那就最好是一个大的完全平方数和几个小的完全平方数相加 或者是 几个中等的完全平方数相加 * 对于单个数的判别方法:DFS.原数减去这个数,剩余的数重复之前的操作,若个数多了,则换成较小的继续 * 可能的做法: DFS;树结构?动态规划 ### 1. 动态规划 ```java public int numSquares(int n) { if(n == 0) return 0; int[] methods = new int[n + 1]; methods[0] = 0; methods[1] = 1; for(int i = 2; i <= n; i++) { int min_x = 1; for(int x = 1; x < i; x++) { if(methods[x] + methods[i - x] < methods[min_x] + methods[i - min_x]) { min_x = x; } } int temp = (int) Math.sqrt(i); if(temp * temp == i) { methods[i] = 1; }else{ methods[i] = methods[min_x] + methods[i - min_x]; } } return methods[n]; } ``` ![image-20220119205450918](https://s401177923-1302493622.cos.ap-nanjing.myqcloud.com/mdImages/image-20220119205450918.png) 拉跨拉跨,因为有$O(N^2)$的时间复杂度哟,还有On的空间复杂度,很多数的运算是浪费了的,因为根本用不到 #### 1.2. 优化后的动态规划 (转) 假设最开始都是最多数目的,即都只+1。动态规划方程的意义在于: $$自然数 i 对应的最小数目 = min(当前值, i - 之前的一个完全平方数的最小数目 再 + 1

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // 默认初始化值都为0
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 最坏的情况就是每次+1
            for (int j = 1; i - j * j >= 0; j++) { 
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
            }
        }
        return dp[n];
    }
}
image-20220120113331761
image-20220120113331761

On的空间复杂度 Onlogn的时间复杂度

2. BFS + 剪枝 (转)

BFS确保了当到这一层时,如果为余数为0,则一定是最小的数目。
注意这里visited确保的是不重复,第二层有一个3,第三层又有一个3,那肯定还是第二层的3的数目<走第三层的3的数目,所以没必要要第三层的。

  public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        int level = 1;
        queue.offer(n);
        visited.add(n);
        while(!queue.isEmpty()) {
            int size = queue.size();
            // 经典做法,用来控制每层的循环的
            for(int i = 0; i < size; i++) {
                int head = queue.poll();
                int sq = (int)Math.sqrt(head);
                for(int j = 1; j <= sq; j++) {
                    int tmp = head - j * j;
                    // 找到了第一个全由 完全平方数 组成的组合,减到0了已经
                    if(tmp == 0) {
                        return level;
                    }
                    // 比如同一层,已经有了1个1,那就不需要再放进去了
                    // 因为都在同一层,往后的层数结果肯定是一样的啊,就是剪枝!!!
                    if(!visited.contains(tmp)) {
                        visited.add(tmp);
                        queue.offer(tmp);
                    }
                }
            }
            level++;
        }
        return level;
    }
image-20220120121648349
image-20220120121648349

空间复杂度大于On
时间复杂度On?

3. 数学公式 (转)

四平方和定理:任意一个正整数都可以被表示为至多四个正整数的平方和。当前仅当$$n \neq 4^k \times (8m+7) $$,n可以被表示为至多三个正整数的平方和,而如果相等时,则n仅可以表示为四个正整数的平方和

由以上定理,则N !=...时,有三种情况:

  • 1种,则必为n的完全平方数
  • 2种,n = a^2 + b^2 ,只需要枚举所有的a,判断n - a^2是否为完全平方数即可
  • 3种,排除法
image-20220120120554207
image-20220120120554207

空间复杂度 O1
时间复杂度 $$O(\sqrt n)$$

总结

做这一题的时候思路大概上还是对的,想到了动态规划,之后想到了自定义链表进而想到了DFS,但这道题是BFS解的......

  • 从树的角度:对多叉树的层数解法考虑BFS
  • 从数组的角度:后一个值依赖于前几个值,考虑dp

292. Nim游戏 ⭐⭐

2021/4/6 09:46:00
Inference
image-20210918150909064
image-20210918150909064

审题

  • “你作为先手”
  • 两个人,双方都尽力向拿走全部石头
  • “是否” ,“如果”
  • 递归?树?

Failed:没做出来,一直抓着递归来做,在“如何聪明的判断剩下的石头是否能完全使对方输掉”这个问题上纠结。。

1. 数学推理(转)

/*

让我们考虑一些小例子。显而易见的是,如果石头堆中只有一块、两块、或是三块石头,那么在你的回合,你就可以把全部石子拿走,从而在游戏中取胜;如果堆中恰好有四块石头,你就会失败。因为在这种情况下不管你取走多少石头,总会为你的对手留下几块,他可以将剩余的石头全部取完,从而他可以在游戏中打败你。因此,要想获胜,在你的回合中,必须避免石头堆中的石子数为 44 的情况。

我们继续推理,假设当前堆里只剩下五块、六块、或是七块石头,你可以控制自己拿取的石头数,总是恰好给你的对手留下四块石头,使他输掉这场比赛。但是如果石头堆里有八块石头,你就不可避免地会输掉, ********因为不管你从一堆石头中挑出一块、两块还是三块,你的对手都可以选择三块、两块或一块,以确保在再一次轮到你的时候,你会面对四块石头*********。显然我们继续推理,可以看到它会以相同的模式不断重复 n = 4, 8, 12, 16, \ldotsn=4,8,12,16,…,基本可以看出如果堆里的石头数目为 44 的倍数时,你一定会输掉游戏。

如果总的石头数目为 44 的倍数时,因为无论你取多少石头,对方总有对应的取法,让剩余的石头的数目继续为 44 的倍数。对于你或者你的对手取石头时,显然最优的选择是当前己方取完石头后,让剩余的石头的数目为 44 的倍数。假设当前的石头数目为 xx,如果 xx 为 44 的倍数时,则此时你必然会输掉游戏;如果 xx 不为 44 的倍数时,则此时你只需要取走 x \bmod 4xmod4 个石头时,则剩余的石头数目必然为 44 的倍数,从而对手会输掉游戏。
*/

public boolean canWinNim(int n) {
        return n % 4 != 0;
    }

这里还是通过特殊情况4的判断,咬定了4作为唯一的特殊情况,延伸推理出4的倍数。比较巧妙的是

  • 先手
  • 由于先手,无论你拿几个,只要我保证在4的倍数,就无法取得胜利

300. 最长递增子序列 ⭐⭐

2021/4/6 09:46:00
DP
Greedy
Binary
image-20210330164045435
image-20210330164045435

思考

可以不连续, 动态规划 dp 通项式

1. 自己写的dp

        int[] dp = new int[nums.length];
        int max = Integer.MIN_VALUE;
        dp[0] = 1;

        for(int i = 0; i<nums.length; i++){
            int k = 0;
            int inmax = Integer.MIN_VALUE;
            for(int j = 0;