2022-19th-week-剑指offer

剑指offer

序言
- 5.16 -> 1题
- - 10- I. 斐波那契数列
  - - 个人思路（suc）
    - 个人解法
    - 官方解法（滚动数组）
- 5.17 -> 6题
- - 10- II. 青蛙跳台阶问题
  - - 个人思路
    - 个人解法（suc）（滑动数组）
    - 官方解法
  - 63. 股票的最大利润
  - - 个人思路（遍历）
    - 个人解法
    - 官方解法
    - 个人的dp解法
  - 第三题 42. 连续子数组的最大和
  - - 个人思路
    - 个人解法
    - 官方解法
  - 第四题 47. 礼物的最大价值
  - - 个人思路
    - 个人解法（dp）（suc）
    - 官方解法
  - 第五题 46. 把数字翻译成字符串
  - - 个人思路
    - 个人解法（HashSet)
    - 官方解法
  - 第六题 48. **最长不含重复字符的子字符串**
  - - 个人思路
    - 个人解法
    - 官方解法
- 5.18 -> 8题
- - 第一题 18. 删除链表的节点
  - - 个人思路
    - 个人解法
    - 官方解法
  - 第二题 22. 链表中倒数第k个节点
  - - 个人思路
    - 个人解法
    - 官方解法
  - 第三题 25. 合并两个排序的链表
  - - 个人思路
    - 个人解法（双指针）
    - 官方解法
  - 第四题 52. **两个链表的第一个公共节点**
  - - 个人思路
    - 个人解法（wrong）
    - 官方解法
  - 第五题 21. 调整数组顺序使奇数位于偶数前面
  - - 个人思路
    - 个人解法（LinkedList）
    - 官方解法（双指针）
    - 我的双指针
  - 第六题 57. 和为s的两个数字
  - - 个人思路
    - 个人解法
    - 官方解法
  - 第七题 58 - I. 翻转单词顺序
  - - 个人思路
    - 个人解法
    - 官方解法
    - 我的StringBuilter
  - 第八题 09. 用两个栈实现队列
  - - 个人思路
    - 个人解法
    - 官方解法
- 5.19 -> 8题搜索与回溯算法
- - 第一题 28. **对称的二叉树**
  - - 个人思路
    - 个人解法（wrong）
    - 官方解法
    - 重写递归算法
  - 第二题 27. 二叉树的镜像
  - - 个人思路
    - 个人解法
    - 官方解法 - 递归法
    - 我的递归解法
  - 第三题 26. 树的子结构
  - - 个人思路
    - 个人解法（wrong）
    - 官方解法
    - 我的递归算法
  - 第四题 12. 矩阵中的路径
  - - 个人思路
    - 个人解法（wrong）
    - 官方解法
    - 我的递归解法
  - 第五题 13. 机器人的运动范围
  - - 个人思路
    - 个人解法
    - 官方解法
    - - BFS
      - DFS
- 5.20 -> 8题
- 5.21 -> 8题
- 5.22 -> 8题
- - 第一题
  - - 个人思路
    - 个人解法
    - 官方解法
  - 第一题
  - - 个人思路
    - 个人解法
    - 官方解法
  - 第一题
  - - 个人思路
    - 个人解法
    - 官方解法

序言

剑指offer还剩下7天和60道题，

争取做完！

5.16 -> 1题 10- I. 斐波那契数列

个人思路（suc）

其实就是状态转移公式
直接带入就可以

个人解法

class Solution {
    public int fib(int n) {

        List list = new ArrayList<>();
        list.add(0);
        list.add(1);

        for (int i = 2; i <= n; i++) {
            list.add((list.get(i-1) + list.get(i-2))% 1000000007);
        }

        return (list.get(n));
    }
}

官方解法（滚动数组）

class Solution {
    public int fib(int n) {
        int a = 0,b=1, sum;
        for(int i=0; i
            sum = ( a + b )% 1000000007;;
            a = b;
            b = sum;
        }
        return a;
    }
}

5.17 -> 6题 10- II. 青蛙跳台阶问题

个人思路

个人解法（suc）（滑动数组）

class Solution {
    public int numWays(int n) {
        int sum = 0, pre = 1, cur = 1;
        for (int i = 0; i < n; i++) {
            sum = (pre + cur)%1000000007;
            pre = cur;
            cur = sum;
        }
        return pre;
    }
}

官方解法 63. 股票的最大利润个人思路（遍历）

遍历所有，寻找最大值；
简单直接，但是计算复杂度很高

个人解法

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int max = 0;
        for (int i = 0; i < len; i++) {
            int cur_P = prices[i];
            for (int j = i+1; j < len; j++) {
                if(prices[j]>cur_P && (prices[j] - cur_P)>max){
                    max = prices[j] - cur_P;
                }
            }
        }
        return max;
    }
}

官方解法

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

个人解法

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

官方解法

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

个人解法（dp）（suc）

class Solution {
    public int maxValue(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(i==0&&j==0){
                    dp[0][0] = grid[0][0];
                }else if(i==0){
                    dp[i][j] = dp[i][j-1]+grid[i][j];
                }else if(j==0){
                    dp[i][j] = dp[i-1][j]+grid[i][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j]);
                }
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

官方解法

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) continue;
                if(i == 0) grid[i][j] += grid[i][j - 1] ;
                else if(j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[m - 1][n - 1];
    }
}


class Solution {
    public boolean isSymmetric(TreeNode root) {
        Queue queue = new LinkedList<>();
        if(root!=null){
            queue.add(root);
        }
        int time=0;
        while(!queue.isEmpty()){

            List arr = new LinkedList<>();
            //双指针
            for (int i = queue.size(); i > 0; i--) {
                root = queue.poll();
                arr.add(root);
                if(root.left!=null)queue.add(root.left);
                if(root.right!=null)queue.add(root.right);
            }
            if(arr.size()%2!=0&&time>0){
                return false;
            }
            for (int i = 0; i < arr.size(); i++) {
                TreeNode last = arr.get(arr.size() -1 - i);
                TreeNode pre = arr.get(i);
                if(last.val==pre.val){
                    continue;
                }else{
                    return false;
                }

            }
            arr.clear();
            time++;
        }
        return true;
    }
}

官方解法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

作者：jyd

重写递归算法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return juedge( root.left, root.right);
    }
    
    public boolean juedge(TreeNode L, TreeNode R){
        if(L==null&&R==null)return true;
        if((L==null&&R!=null)||(L!=null&&R==null)||(L.val!=R.val)) return false;
        //如果val=val，就继续向下递归，进行判断，这里其实就是广度优先遍历的思想
        return juedge(L.left, R.right)&&juedge(L.right, R.left);
    }

}

第二题 27. 二叉树的镜像个人思路个人解法

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null) return root;
        if(root.left!=null){
            root.right = root.left;
            root.left = temp;
        }
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}

官方解法 - 递归法

方法一：递归法
根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。

https://pic.leetcode-cn.com/c252a2c9792a0998d0560be8e882db3ad1f2e106b0d56c76fdfef219e55e4ea3-Picture2.png

链接: link

我的递归解法

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null) return null;
        //这里的temp只是为了保存上一步root.left的地址
 
        TreeNode temp = root.left;
        //递归，让左右互换;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        //每次递归的结束都会返回上一级；，最终到达根节点root
        return root;
    }
}

可以这样理解

第三题 26. 树的子结构

个人思路

遍历：在A中找到B的根节点，
判定：进行接下来的判定，

个人解法（wrong）

    class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        Queue queue = new LinkedList<>();
        if(A!=null){
            queue.add(A);
        }
        if(B==null)return false;
        List bool = new ArrayList<>();
        while(!queue.isEmpty()){
            for (int i = queue.size(); i > 0; i--) {
                TreeNode temp = queue.poll();
                if(temp.left!=null)queue.add(temp.left);
                if(temp.right!=null)queue.add(temp.right);
                if(temp.val==B.val){
                    bool.add(judge(temp, B));
                }
            }
        }
        for(int i=0; i
            if(bool.get(i)==true){
                return true;
            }else{
                return  false;
            }
        }
        return false;
    }
    public Boolean judge(TreeNode temp, TreeNode B){
        if(B==null){
            return true;
        }
        if((temp==null)||(temp.val!=B.val))return false;
        return judge(temp.right,B.right)&&judge(temp.left,B.left);
    }
    
}

官方解法

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

作者：jyd

我的递归算法

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(B==null){
            return false;
        }
        // A在不为空的时候进行判定，这里应该是广度优先遍历，遍历所有的节点，进行比较-递归；
        return (A!=null ) && ( judge(A,B) || ( isSubStructure(A.left,B)||isSubStructure(A.right,B)) );
    }
    public boolean judge(TreeNode A, TreeNode B){
        if(B==null)return true;
        if(A==null||A.val!=B.val)return false;
        return judge(A.right,B.right)&&judge(A.left,B.left);
    }
}

第四题 12. 矩阵中的路径

个人思路

我的思路和官方思想是一致的

个人解法（wrong）

    @Test
    public void exist(){
        char[][] board = {
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'},
                };
        String word = "ABCCED";

        //找到头字符
        char head = word.charAt(0);
        int len = word.length();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j] == head){
                    // 递归进行判定
                    System.out.println(judgeHead(board, word, i, j, len, head));
                }
            }
        }
    }

    public Boolean judgeHead(char[][] board, String word, int i, int j, int len,char head){
        if(len==0){
            return true;
        }
        len--;
        head = word.charAt(word.length()-len);
        //其实这里我的思路有问题了，这样做的话，每次就直接返回了，没有进行下一步
        //如果想要走到头可以试试
       
        if((head == board[i+1][j])&&(i+1<=board.length)){
            return judgeHead(board, word, i+1, j, len, head);
        }else if(head == board[i-1][j]&&i-1>=0){
            return judgeHead(board, word, i-1, j, len, head);
        }else if(head == board[i][j+1]&&j+1<=board[0].length){
            return judgeHead(board, word, i, j+1, len, head);
        }else if(head == board[i][j-1]&&j-1>=board[0].length){
            return judgeHead(board, word, i, j-1, len, head);
        }
        

        return false;
    }

官方解法

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}

作者：jyd

我的递归解法

class Solution {
    public boolean exist(char[][] board, String word) {
        //遍历找到头字母, 然后进行判定
        char[] arr = word.toCharArray();
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j] == arr[0]){
                    // 递归进行判定 这个条件一加，算法复杂度提升一个量级；
                    if(judgeHead(board, arr, i, j, 0)==true){
                        return true;
                    }
                }
            }
        }
        return false;
    }


    public boolean judgeHead(char[][] board, char[] word, int i, int j, int len){
        
        if(i>=board.length||i<0||j>=board[0].length||j<0 || word[len]!=board[i][j])return false;
        if(word.length-1 == len)return true;
        board[i][j] = '';
        boolean result = (judgeHead(board, word, i+1, j, len+1)||
                            judgeHead(board, word, i-1, j, len+1) ||
                            judgeHead(board, word, i, j+1, len+1) ||
                            judgeHead(board, word, i, j-1, len+1));
        //这里要修复原来的矩阵; 这里有点想不懂
           //递归搜索匹配字符串过程中，需要 board[i][j] = '/' 来防止 ”走回头路“ 。
        // 当匹配字符串不成功时，会回溯返回，此时需要board[i][j] = tmp
        // 来”取消对此单元格的标记”。 在DFS过程中，每个单元格会多次被访问的， 
        // board[i][j] = '/'只是要保证在当前匹配方案中不要走回头路。
        board[i][j] = word[len];
        return result;
    }
}

第五题 13. 机器人的运动范围

个人思路个人解法

class Solution {
    public int movingCount(int m, int n, int k) {
        int sum = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i<10 && j<10&&i + j <= k){
                    sum++;
                }else if (i>9 && j<10){
                    if(i%10 +  (Integer)(i/10) + j <= k ) {
                        sum++;
                    }
                }else if (j>9 && i<10){
                    if(j%10 +  (Integer)(j/10) + i <= k ) {
                        sum++;
                    }
                }else {
                    if(j%10 +  (Integer)(j/10) + i%10 +  (Integer)(i/10) <= k ) {
                        sum++;
                    }
                }
            }
        }
        return sum;
    }
}

官方解法 BFS

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue queue= new LinkedList();
        queue.add(new int[] { 0, 0, 0, 0 });
        while(queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res ++;
            queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
            queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
        }
        return res;
    }
}

作者：jyd

DFS

class Solution {
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}

作者：jyd

5.20 -> 8题 5.21 -> 8题 5.22 -> 8题第一题个人思路个人解法官方解法第一题个人思路个人解法官方解法第一题个人思路个人解法官方解法

2022-19th-week-剑指offer

C/C++/C#相关栏目本月热门文章