devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【2021-03】剑指offer 中等题 Java复刷_从一个n*m(n<=m)的矩阵中选出n个数,任意两个数字不能在同一行或同一列,求选出来的

作者：知新_RL | 2024-07-11 18:17:42

赞

踩

从一个n*m(n<=m)的矩阵中选出n个数,任意两个数字不能在同一行或同一列,求选出来的

04 二维数组中的查找

题目描述：
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
题目地址：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
我的想法：
从数组右上角往左下角方向查找，根据数组的性质，如果往左的过程中遇到比target要小的数，就从此列从上往下找。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int rows = matrix.length;
        if(rows==0) return false;
        int cols = matrix[0].length;
        if(cols==0) return false;
        int i=0,j=cols-1;
        while(i<rows && j>=0){
            if(matrix[i][j]==target){
                return true;
            }else if(matrix[i][j]>target){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

07 重建二叉树

题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
题目地址：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
我的想法：
前序遍历的顺序是：根-左-右
中序遍历的顺序是：左-根-右
每次递归，就按照前序遍历的最左边的值（作为根）去中序遍历中查找索引，然后就能把中序遍历划分成：左-根-右

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int num = 0;
    public TreeNode findNode(int[] preorder,int[] inorder,int left,int right){
        if(left>right) return null;
        //查找当前结点在中序遍历的位置
        //当前结点的值为preorder[left]
        int idx;
        //查找根节点在中序遍历中的位置
        for(idx = left;idx<=right;idx++)
            if(inorder[idx]==preorder[num]) break;
        //如果找不到说明当前结点时null
        if(idx>right) return null;
        num++;
        //如果找到了就继续找左右结点
        TreeNode root = new TreeNode(inorder[idx]);
        root.left = findNode(preorder,inorder,left,idx-1);
        root.right = findNode(preorder,inorder,idx+1,right);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if(len==0) return null;
        TreeNode root = findNode(preorder,inorder,0,len-1);
        return root;
    }
}

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

12 矩阵中的路径

题目描述：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径。
[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
题目地址：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
我的想法：
DFS和BFS方法都可以使用，DFS每次就朝上下左右一个方向搜索，宽度搜索每次向四周扩散，搜到返回true。下面代码是DFS的做法。

class Solution {
    private int[] dx = {-1,1,0,0};//上下左右对应的行变化
    private int[] dy = {0,0,-1,1};//列变化
    public boolean search(int x,int y,int idx,String word,char[][] board){
        if(idx==word.length()) return true;//搜索结束返回true
        //越界/已经搜过/字符不对返回false结束搜索
        if(x<0 || y<0 || x>=board.length || y>=board[0].length || board[x][y]=='/' || board[x][y]!=word.charAt(idx)) return false;
        char tmp = board[x][y];
        board[x][y] = '/';//当前到达的点先标记起来
        boolean fnd = false;
        for(int i=0;i<4;i++){
        //每一个单元格往四个方向搜索
            int tx = x + dx[i];
            int ty = y + dy[i];
            fnd = fnd || search(tx,ty,idx+1,word,board);
        }
        board[x][y] = tmp;//记得恢复原来的字符
        return fnd;
    }
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        if(rows==0) return false;
        int cols = board[0].length;
        if(cols==0) return false;
        //因为不知道起点是哪里所以需要遍历二维数组找起点
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                boolean flg = false;
                if(board[i][j]==word.charAt(0))
                    flg = search(i,j,0,word,board);
                if(!flg) continue;
                else return true;
            }
        }
        return false;
    }
}

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

13 机器人的运动范围

题目描述：
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
题目地址：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
我的想法：
类似上题。下面代码是DFS+BFS的做法。

//DFS:
class Solution {
    private int cnt = 0;
    private int[] dx = {-1,1,0,0};
    private int[] dy = {0,0,-1,1};
    private boolean[][] map;
    public int getSum(int num){
        int sum = 0;
        while(num!=0){
            sum += num%10;
            num /= 10;
        }
        return sum;
    }
    public void move(int x,int y,int m,int n,int k){
        if(x<0 || y<0 || x>=m || y>=n || map[x][y]) return ;//越界
        int sum = getSum(x)+getSum(y);
        if(sum>k) return ;//不符要求
        cnt++;
        map[x][y] = true;
        for(int i=0;i<4;i++){
            move(x+dx[i],y+dy[i],m,n,k);
        }
    }
    public int movingCount(int m, int n, int k) {
        map = new boolean[m][n];
        move(0,0,m,n,k);
        return cnt;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
//BFS:
class Solution {
    class Node{
        int x,y;
        public Node(int xx,int yy){this.x = xx;this.y=yy;}
    }
    private int cnt = 0;
    private Queue<Node> q;
    private boolean[][] vis;
    private int[] dx = {-1,1,0,0};
    private int[] dy = {0,0,-1,1};
    public int getSum(int num){
        int sum = 0;
        while(num!=0){
            sum += num%10;
            num /= 10;
        }
        return sum;
    }
    public int movingCount(int m, int n, int k) {
        q = new LinkedList<>();
        vis = new boolean[m][n];
        Node node = new Node(0,0);//起点
        q.add(node);//入队
        while(!q.isEmpty()){
            Node tmp = q.poll();//出队
            if(tmp.x<0 || tmp.y<0 || tmp.x>=m || tmp.y>=n || vis[tmp.x][tmp.y]) continue;
            if(getSum(tmp.x)+getSum(tmp.y)>k) continue;
            vis[tmp.x][tmp.y] = true;
            cnt++;
            for(int i=0;i<4;i++){
                q.add(new Node(tmp.x+dx[i],tmp.y+dy[i]));
            }
        }
        return cnt;
    }
}

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

14 I.剪绳子

题目描述：
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
题目地址：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
我的想法：
注意题目要求的是一根绳子至少被剪成2段。
如果绳子长度≤1就不可能符合要求，因此返回0；
如果绳子长度为2，只能剪成1+1，长度为3，只能剪成1+2；
其他长度，就先看能否剪出长为3的段且剩余长度大于1，再看能否剪出长为2的段且剩余长度大于1，不能满足以上两个条件的说明绳子长度只剩2，其他长度的段（类似4、5…）可以看成是2和3的合成。

class Solution {
    public int cuttingRope(int n) {
        if(n<=1) return 0;
        if(n<4) return n-1;
        int mul = 1;
        while(n>0){
            if(n-3>1){
                n -= 3;
                mul *= 3;
            }else if(n-2>1){
                n -= 2;
                mul *= 2;
            }else{
                mul *= n;
                break;
            }
        }
        return mul;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

14 II.剪绳子

题目描述：
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
【答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。】
题目地址：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
我的想法：
与上一题思路一致，但是需要注意取余，取余之前的值可能溢出，所以要用long存储，返回时再强转。

class Solution {
    public int cuttingRope(int n) {
        if(n<=1) return 0;
        if(n<4) return n-1;
        long mod = 1000000007;
        long mul = 1;
        while(n>0){
            if(n-3>1){
                n -= 3;
                mul *= 3;
                mul %= mod;
            }else if(n-2>1){
                n -= 2;
                mul *= 2;
                mul %= mod;
            }else{
                mul *= n;
                mul %= mod;
                break;
            }
        }
        return (int)mul;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

16 数值的整数次方

题目描述：
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
题目地址：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
我的想法：
用快速幂的方法比较快，需要注意指数可能是-2^31，在取相反数会溢出，需要用long存储指数。

class Solution {
    public double myPow(double x, int n) {
        if(x==1.0) return x;
        if(x==0.0) return 0;
        if(n==0) return 1;
        if(n==1) return x;
        if(n==-1) return 1.0/x;
        boolean flg = (n<0?true:false);
        long n_ = n;
        if(flg) n_ = -n_;
        double mul = 1;
        double bit = x;
        while(n_!=0){
            if((n_&1)==1)//当前位是1
                mul *= bit;
            bit *= bit;
            n_ >>= 1;
        }
        if(flg) return 1.0/mul;
        else return mul;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

20 表示数值的字符串

题目描述：
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。
题目地址：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
我的想法：
用HashMap实现自动机的状态迁移，注意状态的定义及转换规则（通过测试用例测出来的规则…）

class Solution {
    public enum CharType{
        SIGN,//+-符号
        NUM,//数字
        DOT,//小数点
        EXP,//E/e
        SPACE,//空格字符
        ERROR//错误字符
    }
    public enum State{
        STATE_BEGIN,//初始-状态
        STATE_SIGN,//符号-状态
        STATE_PRE_NUM,//小数点前面的数字-状态
        STATE_DOT,//前面有数字的小数点-状态
        STATE_DOT_NOTNUM,//前面没有数字的小数点-状态
        STATE_POS_NUM,//小数点后面的数字-状态
        STATE_EXP,//e/E符号-状态
        STATE_EXP_SIGN,//指数符号-状态
        STATE_EXP_NUM,//指数数字-状态
        STATE_END//结束状态
    }
    public CharType checkType(char c){
        if(c=='+' || c=='-') return CharType.SIGN;
        if(c>='0' && c<='9') return CharType.NUM;
        if(c=='E' || c=='e') return CharType.EXP;
        if(c=='.') return CharType.DOT;
        if(c==' ') return CharType.SPACE;
        else return CharType.ERROR;
    }
    public boolean isNumber(String s) {
        final Map<State,Map<CharType,State>> map = new HashMap<>(){{
            //初始状态的转移
            put(State.STATE_BEGIN,new HashMap<>(){{
                put(CharType.SIGN,State.STATE_SIGN);//符号
                put(CharType.NUM,State.STATE_PRE_NUM);//小数点前数字
                put(CharType.DOT,State.STATE_DOT_NOTNUM);//后面接数字的小数点
            }});
            //符号状态的转移
            put(State.STATE_SIGN,new HashMap<>(){{
                put(CharType.NUM,State.STATE_PRE_NUM);//小数点前数字
                put(CharType.DOT,State.STATE_DOT_NOTNUM);//无前面数字的小数点
            }});
            //小数点前的数字状态的转移
            put(State.STATE_PRE_NUM,new HashMap<>(){{
                put(CharType.NUM,State.STATE_PRE_NUM);//小数点前数字
                put(CharType.DOT,State.STATE_DOT);//有前面数字的小数点
                put(CharType.EXP,State.STATE_EXP);//E/e
                put(CharType.SPACE,State.STATE_END);//结束
            }});
            //有前面数字的小数点状态的转移
            put(State.STATE_DOT,new HashMap<>(){{
                put(CharType.NUM,State.STATE_POS_NUM);//小数点后的数字
                put(CharType.EXP,State.STATE_EXP);//EXP
                put(CharType.SPACE,State.STATE_END);//结束
            }});
            //没有前面数字的小数点状态的转移
            put(State.STATE_DOT_NOTNUM,new HashMap<>(){{
                put(CharType.NUM,State.STATE_POS_NUM);//小数点后的数字
            }});
            //小数点后的数字状态的转移
            put(State.STATE_POS_NUM,new HashMap<>(){{
                put(CharType.NUM,State.STATE_POS_NUM);//小数点后的数字
                put(CharType.EXP,State.STATE_EXP);//EXP
                put(CharType.SPACE,State.STATE_END);//结束
            }});
            //EXP状态的转移
            put(State.STATE_EXP,new HashMap<>(){{
                put(CharType.SIGN,State.STATE_EXP_SIGN);//指数的符号
                put(CharType.NUM,State.STATE_EXP_NUM);//指数的数字
            }});
            //exp符号状态的转移
            put(State.STATE_EXP_SIGN,new HashMap<>(){{
                put(CharType.NUM,State.STATE_EXP_NUM);//指数的数字
            }});
            //exp数字状态的转移
            put(State.STATE_EXP_NUM,new HashMap<>(){{
                put(CharType.NUM,State.STATE_EXP_NUM);//指数的数字
                put(CharType.SPACE,State.STATE_END);//结束
            }});
        }};
        s = s.trim();
        s += ' ';//加一个空格方便判断结束
        int len = s.length();
        State state = State.STATE_BEGIN;//初始状态
        for(int i=0;i<len;i++){
            CharType ct = checkType(s.charAt(i));//获取字符类型
            //字符类型错误
            if(ct==CharType.ERROR) return false;
            //字符类型正确则转移状态
            if(map.get(state)==null) return false;
            if(map.get(state).get(ct)==null) return false;
            state = map.get(state).get(ct);
        }
        if(state==State.STATE_END) return true;
        return false;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

26 树的子结构

题目描述：
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
题目地址：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
我的想法：
先找A树中哪个结点的值跟B树的根结点的值相等，然后通过另一个方法递归看左右子树是否相等，遇到不等返回false，然后再继续找A树的结点。即：先找根，再对点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean check(TreeNode A,TreeNode B){
        if(B==null) return true;//已经找完
        if(A==null || A.val!=B.val) return false;
        return check(A.left,B.left) && check(A.right,B.right);
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null || B==null) return false;
        //根结点匹配则查找剩余结点
        if(A.val==B.val && check(A,B)) return true;
        //不匹配就继续找
        return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

31 栈的压入、弹出序列

题目描述：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
题目地址：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
我的想法：
利用Java的Stack类，模拟栈的压入、弹出过程，如果遇到栈顶与popped数组的索引 j 对应的值就弹出，如果最终栈还有数字说明顺序不符合。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length!=popped.length) return false;
        int len = pushed.length;
        Stack<Integer> s = new Stack<>();
        int j = 0;
        for(int i=0;i<len;i++){
            s.push(pushed[i]);
            while(!s.empty() && s.peek()==popped[j] && j<len){
                s.pop();
                j++;
            }
        }
        if(!s.empty()) return false;
        return true;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

32 从上到下打印二叉树 III

题目描述：
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
题目地址：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
我的想法：
用一个队列存储每层的结点，每次都倒序取出，注意左子结点和右子结点的放入顺序。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new LinkedList<>();
        if(root==null) return list;
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        boolean drc = true;
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> l = new LinkedList<>();
            Deque<TreeNode> tmp = new LinkedList<>();
            for(int i=0;i<size;i++){
                TreeNode node = q.removeLast();
                if(drc){
                    if(node.left!=null) tmp.add(node.left);
                    if(node.right!=null) tmp.add(node.right);
                }else{
                    if(node.right!=null) tmp.add(node.right);
                    if(node.left!=null) tmp.add(node.left);
                }
                l.add(node.val);
            }
            drc = !drc;
            list.add(l);
            q = null;q = tmp;
        }
        return list;
    }
}

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

33 二叉搜索树的后序遍历序列

题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
我的想法：
后序遍历的元素顺序是：左-右-根，每次从两个方向检查，从左到右遍历【左子树部分】时，遇到的数字一定都小于根元素的值，从右到左遍历【右子树部分】时，遇到的数字一定都大于根元素的值（题目已说明元素不重复，所以不考虑相等），最后比较遍历两部分结束时的索引是不是相接的，不是的话说明不是二叉搜索树。

class Solution {
    public boolean check(int[] postorder,int left,int right){
        if(left>=right) return true;
        int i = left,j = right-1;
        while(i<=right && postorder[i]<postorder[right]) i++;
        while(j>=left && postorder[j]>postorder[right]) j--;
        if((i-1)!=j) return false;
        return check(postorder,left,i-1) && check(postorder,i,right-1);
    }
    public boolean verifyPostorder(int[] postorder) {
        int len = postorder.length;
        if(len<=1) return true;
        return check(postorder,0,len-1);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

34 二叉树中和为某一值的路径

题目描述：
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
题目地址：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
我的想法：
按照dfs的做法，题目并没有说所有值都是正数，所以不能用剪枝的方法（遇到>sum立即返回）。
【注意！！】每次走到符合要求的叶子结点后要将list放进二维list里，要用new LinkedList<>(list)的方法，不能直接list.add(list)，因为放进去的是引用，后续会被改变值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void find(List<List<Integer>> list,List<Integer> l,TreeNode root,int sum,int cnt){
        if(root==null) return ;
        if(root.left==null && root.right==null && cnt+root.val==sum){//到达路径末尾
            l.add(root.val);
            list.add(new LinkedList<Integer>(l));
        }
        //还未到达路径末尾
        else{
            l.add(root.val);
            find(list,l,root.left,sum,cnt+root.val);
            find(list,l,root.right,sum,cnt+root.val);
        }
        l.remove(l.size()-1);
    }
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> list = new LinkedList<>();
        List<Integer> l = new LinkedList<>();
        find(list,l,root,sum,0);
        return list;
    }
}

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

35 复杂链表的复制

题目描述：
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
题目地址：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
我的想法：
用HashMap存储原结点及其副本结点，这样一次顺序遍历复制后就可以通过（原结点，副本结点）→（原结点的random结点，副本结点的random结点），需要两次顺序遍历，一次复制顺序连接关系，另一次复制random指向关系。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return null;//头结点为空
        HashMap<Node,Node> map = new HashMap<>();
        Node tmp = new Node(head.val);//复制头结点
        Node s = tmp,p = head.next;
        map.put(head,tmp);
        //顺序复制
        while(p!=null){
            tmp = new Node(p.val);//复制结点
            s.next = tmp;
            s = tmp;
            map.put(p,tmp);
            p = p.next;
        }
        //复制random关系
        p = head;
        while(p!=null){
            Node dpc = map.get(p);//获得副本结点
            Node dpc_random = map.get(p.random);//获得random结点的副本结点
            dpc.random = dpc_random;
            p = p.next;
        }
        return map.get(head);
    }
}

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

36 二叉搜索树与双向链表

题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
题目地址：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
我的想法：
二叉搜索树的中序遍历序列就是按照自然顺序排列的，在访问root.left和root.right中间去操作结点，操作的次序就是按照从小到大顺序。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    private Node head,pre;
    public void dfs(Node cur){
        if(cur==null) return ;
        dfs(cur.left);
        if(head==null) head = cur;//首次标记头结点
        if(pre!=null) pre.right = cur;//把前面结点的right指针指向当前结点
        cur.left = pre;//把当前结点的left指着指向前面的结点
        pre = cur;
        dfs(cur.right);
    }
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        head = pre = null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
}

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

44 数字序列中某一位的数字

题目描述：
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
题目地址：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/
我的想法：
先求出该下标对应的数字是哪一个，再求出对应的数位是哪一个，然后取出该数位对应的数字即可。过程比较麻烦。规律是：
1~9 （共占9×1位）（0可以忽略是因为下标是从0开始计算的）
10~99 （共占90×2位）
100~999 （共占900×3位）
以此类推…

class Solution {
    public int findNthDigit(int n) {
        if(n<10) return n;
        long bits = 1,cnt = 9,pos = (long)n,base = 1;
        while((pos-bits*cnt)>0){
            pos -= (cnt*bits);
            bits++;
            cnt *= 10;
            base *= 10;
        }
        long bit;//第n个数字的第几位
        if(pos%bits==0){
            pos = pos-1;
            bit = (int)bits;
        }else{
            bit = pos%bits;
        }
        long num = pos/bits + base;//对应的数字
        return String.valueOf(num).toCharArray()[(int)bit-1]-48;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

38 字符串的排列

题目描述：
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
题目地址：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
我的想法：
初看题目便知道需要使用回溯的解法，但是我不是很懂如果字符串有重复字母时应该怎么处理。参考了题解，思路是：增加一个排序的步骤，假设str[0]和str[1]为相同字母，在拼凑字符串时如果在某一个位置需要使用str[1]，那么必须保证str[0]要被使用过，这样可以保证存在相同字母时某个位置只能用一次（即排序后的第一个字母）。
同时学到一个新写法，list转为String数组：
list.toArray(new String[0])

class Solution {
    private int len;
    private char[] str;
    private List<String> list;
    private boolean[] vis;
    private StringBuilder sb;
    public void dfs(int idx){
        if(idx==len){
            list.add(sb.toString());
            return ;
        }
        for(int i=0;i<len;i++){
            if(i>0 && str[i]==str[i-1] && !vis[i-1] && !vis[i]) continue;
            if(!vis[i]){
                vis[i] = true;
                sb.append(str[i]);
                dfs(idx+1);
                sb.deleteCharAt(sb.length()-1);
                vis[i] = false;
            }
        }
    }
    public String[] permutation(String s) {
        list = new LinkedList<>();//存储结果
        str = s.toCharArray();//转为字符数组
        Arrays.sort(str);//数组排序
        len = str.length;//字符串长度
        vis = new boolean[len];//是否被访问
        sb = new StringBuilder();//字符串构造
        dfs(0);
        return list.toArray(new String[0]);
    }
}

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

同样的，我们可以解决第47题：带重复数字的数组全排列。题目地址：https://leetcode-cn.com/problems/permutations-ii/

class Solution {
    private List<List<Integer>> list;
    private boolean[] vis;
    private int len;
    private List<Integer> arr;
    public void dfs(int depth,int[] nums){
        if(depth==len){
            list.add(new LinkedList<>(){{addAll(arr);}});//加入结果集
            return ;
        }
        for(int i=0;i<len;i++){
            if(vis[i]) continue;
            if(i>0 && nums[i]==nums[i-1] && !vis[i-1]) continue;
            arr.add(nums[i]);
            vis[i] = true;
            dfs(depth+1,nums);
            vis[i] = false;
            arr.remove(arr.size()-1);
        }
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        list = new LinkedList<>();//结果集
        arr = new LinkedList<>();//单个列表
        Arrays.sort(nums);//排序
        len = nums.length;//数组长度
        vis = new boolean[len];//访问数组
        dfs(0,nums);//回溯
        return list;
    }
}

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

45 把数组排成最小的数

题目描述：
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
题目地址：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
我的想法：
从题目可以知道一定是需要对数组进行排序的，如果对于类似数组[1,2,3,4]，那组成的数字一定是首位较小的排在前面，才能让数字小。但是存在特殊情况使排序不能只按照字符串排序规则进行，例如对于数组[1,10,2]，排序之后元素“1”一定在元素“10”前面，那组成的数字就是“1102”，但其实还能组成更小的数字“1012”，这是因为“10”后面有个0使它可以与“1”组合后形成“101”而不是“110”。
这里的写法参考了一个月前阅读过的题解，要对字符串线组合后排序，对于上述“1”和“10”的例子，如果“1”和“10”两种拼接组合“110”和“101”，如果“101”小于“110”，则“10”应该排在“1”前面，否则就是后面。
同时学到一个新写法，利用Collections.sort()排序集合类：
Collections.sort(list,new Comparator<String>(){
@Override
public int compare(String s1,String s2){
return new String(s1+s2).compareTo(s2+s1);
}
})

class Solution {
    public String minNumber(int[] nums) {
        List<String> list = new LinkedList<>();
        for(int num:nums)
            list.add(String.valueOf(num));
        Collections.sort(list,new Comparator<String>(){
            @Override
            public int compare(String a,String b){
                String a_b = a+b;
                String b_a = b+a;
                return a_b.compareTo(b_a);
            }
        });
        StringBuilder sb = new StringBuilder();
        for(String str:list)
            sb.append(str);
        return sb.toString();
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

45 把数组排成最小的数

题目描述：
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
题目地址：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
我的想法：
类似于dfs的做法，如果当前数字与下一位数字组成的数字范围在10~25以内，步长就以2自加。

class Solution {
    private int cnt = 0;
    public void dfs(int idx,char[] nums){
        if(idx>=nums.length-1){
            cnt++; return ;
        }
        dfs(idx+1,nums);
        if((idx+1)<nums.length && (nums[idx]=='1' || (nums[idx]=='2' && nums[idx+1]<='5')))
            dfs(idx+2,nums);
    }
    public int translateNum(int num) {
        char[] nums = String.valueOf(num).toCharArray();
        dfs(0,nums);
        return cnt;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

47 把数组排成最小的数

题目描述：
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
题目地址：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
我的想法：
比较清晰简单容易看出递推关系的动态规划，既然路径只能往右或者往下，那么对于一个单元格来说，在它之前的礼物总价值只能通过其上方或者左边的单元格计算得到，找到该单元格上面或左边的最大值即可。

class Solution {
    public int maxValue(int[][] grid) {
        int rows = grid.length;
        if(rows==0) return 0;
        int cols = grid[0].length;
        if(cols==0) return 0;
        int[][] dp = new int[rows][cols];
        //对dp数组的第一列、第一行赋值
        for(int i=0;i<cols;i++){
            if(i>0)dp[0][i] = dp[0][i-1] + grid[0][i];
            else dp[0][i] = grid[0][i];
        }
        for(int i=1;i<rows;i++)
            dp[i][0] = dp[i-1][0] + grid[i][0];
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                dp[i][j] = grid[i][j] + (dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]);
            }
        }
        return dp[rows-1][cols-1];
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

48 最长不含重复字符的子字符串

题目描述：
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
题目地址：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
我的想法：
dp数组中的dp[i]用来维护一个不重复字符串的窗口范围，dp[i]=j代表s[j]到s[i]没有出现重复字符，dp[i+1]则需要扫描s[dp[i]]到s[i]有没有重复字符，有的话该窗口的前沿后退一格。一开始在想有没有O(n)的算法，但是感觉应该没有。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0 || s==null) return 0;
        int[] dp = new int[s.length()];
        dp[0] = 0;
        for(int i=1;i<dp.length;i++){
            int idx = -1;
            for(int j=dp[i-1];j<i;j++)
                if(s.charAt(i)==s.charAt(j)){
                    idx = j;break;
                }
            if(idx!=-1) dp[i] = idx + 1;
            else dp[i] = dp[i-1];
        }
        int maxv = 0;
        for(int i=0;i<dp.length;i++)
            if((i-dp[i]+1)>maxv) maxv = (i-dp[i]+1);
        return maxv;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

49 丑数

题目描述：
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
题目地址：https://leetcode-cn.com/problems/chou-shu-lcof/
我的想法：
一开始想的是，每次从三个序列：
（2×1,2×2,2×3,2×4,2×5,2×6,2×7,2×8,…）
（3×1,3×2,3×3,3×4,3×5,3×6,3×7,3×8,…）
（5×1,5×2,5×3,5×4,5×5,5×6,5×7,5×8,…）
中依次挑选出最小值，每次用三个指针标记位置，但其实这样不妥，因为比如2×7这个数字，因子包括7，不符合题意。
所以三个指针应该指向已经取过的数字（然后再去×2,3,5），避免2×7,2×11这种情况发生。

class Solution {
    public int nthUglyNumber(int n) {
        if(n==1) return 1;
        int[] dp = new int[n];
        dp[0] = 1;
        int f2,f3,f5;
        f2 = f3 = f5 = 0;
        int cur = 1;
        for(int i=1;i<n;i++){
            cur = Math.min(dp[f2]*2,Math.min(dp[f3]*3,dp[f5]*5));
            if(cur==dp[f2]*2) f2++;
            if(cur==dp[f3]*3) f3++;
            if(cur==dp[f5]*5) f5++;
            dp[i] = cur;
        }
        return cur;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

56 I. 数组中数字出现的次数

题目描述：
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
题目地址：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
我的想法：
题目要采用位运算，因为出现两个只出现一次的数字，而int一般是32位，那么就必定存在某一位上，数组中所有数字在该位上的数字为0或1，且0或者1的个数是奇数个，那么就可以根据这个将数组划分成两部分（一部分包含偶数个其他数字和一个奇数个数字，另一部分也包含偶数个其他数字和一个奇数个数字），再运用或运算筛选出数字。
例如：对于测试用例[4,1,4,6]，它们的二进制是[0100,0001,0100,0110]，从右到左的第1位是1且总的1的个数是奇数个，就可以将数组分为[0001]和[0100,0100,0110]。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int len = nums.length;
        int bit = 1;//数位筛选
        for(int i=0;i<32;i++){//对每一个数字的32个位都运算
            int cnt = 0;
            for(int j=0;j<len;j++)//遍历数组中每一个数字
                if((nums[j] & bit)==bit) cnt++;
            if(cnt%2==1) break;
            bit <<= 1;//筛选位左移
        }
        int a = -1,b = -1;//两个需要筛选出来的数字
        for(int i=0;i<len;i++){//分组
            if((nums[i]&bit)==0){
                if(a==-1) a = nums[i];
                else a ^= nums[i];
            }else{
                if(b==-1) b = nums[i];
                else b ^= nums[i];
            }
        }
        return new int[]{a,b};
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

56 II. 数组中数字出现的次数 II

题目描述：
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
题目地址：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
我的想法：
同属于位运算题目，因为其他数字出现了3次，所以每一位数字可以统计出现0/1的总数，如果出现某位上1的总次数模3等于1的情况，说明我们要找的那个数字在该位上是1，用一个数组存储各位上出现1的次数是否整除3，然后再加起来（题目说了所有数字都是正整数所以不考虑符号的作用）。

class Solution {
    public int singleNumber(int[] nums) {
        int bit = 1;//用于筛选的数位
        boolean[] bits = new boolean[32];
        for(int i=31;i>=0;i--){
            int cnt = 0;//统计当前位上1的数量
            for(int j=0;j<nums.length;j++)
                if((nums[j]&bit)==bit) cnt++;
            if(cnt%3==0) bits[i] = false;
            else bits[i] = true;
            bit <<= 1;
        }
        int sum = 0;
        int mul = 1;
        for(int i=31;i>=0;i--){
            if(bits[i]) sum += mul;
            if(i!=0) mul *= 2;
        }
        return sum;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

59 II. 队列的最大值

题目描述：
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
题目地址：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
我的想法：
用一个普通队列负责pop和push的职能，再用另一个双端队列保持一个单调不增序列。

class MaxQueue {
    private Queue<Integer> q;
    private Deque<Integer> axg;
    public MaxQueue() {
        q = new LinkedList<>();
        axg = new LinkedList<>();
    }
    public int max_value() {
        if(q.isEmpty()) return -1;
        if(axg.isEmpty()) return q.peek();
        return axg.peek();
    }
    public void push_back(int value) {
        q.add(value);
        while(!axg.isEmpty() && axg.peek()<value) axg.removeFirst();
        while(!axg.isEmpty() && axg.peekLast()<value) axg.removeLast(); 
        axg.addLast(value);
    }    
    public int pop_front() {
        if(q.isEmpty()) return -1;
        int tmp = q.poll();
        if(axg.peek()==tmp) axg.poll();
        return tmp;
    }
}
/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

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

60 n个骰子的点数

题目描述：
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
题目地址：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
我的想法：
用一个类似于动态规划的数组，dp[i][j]表示第i次投骰子时点数总和为j的概率，那么dp[i][j]=dp[i-1][j-k]*0.16667(k∈[1,6]且(j-k)>0)。

class Solution {
    public double[] dicesProbability(int n) {
        double[][] arr = new double[n+1][6*n+1];
        double[] res = new double[5*n+1];
        //先初始化第一次扔骰子的概率
        for(int i=1;i<6*n+1;i++){
            if(i<=6) arr[1][i] = 1.0/6;
            else arr[1][i] = 0;
        }
        for(int i=2;i<=n;i++){
            //第i次扔骰子点数之和的范围是i~6*i
            for(int j=i;j<=6*i;j++){
                for(int k=1;k<=6 && (j-k)>0;k++)
                    arr[i][j] += arr[i-1][j-k] * (1.0/6);
            }
        }
        int idx = 0;
        for(int i=n;i<=6*n;i++)
            res[idx++] = arr[n][i];
        return res;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

63 股票的最大利润

题目描述：
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
题目地址：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
我的想法：
动态规划，转移方程看下放。dp[i]=j表示第i天卖出的股票是第j天买入的。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==1 || prices.length==0) return 0;
        int[] dp = new int[prices.length];
        dp[0] = 0;//dp[i]=j表示第i天卖出的股票是在第j天买入的
        for(int i=1;i<dp.length;i++){
            if(prices[i]<prices[dp[i-1]])
                dp[i] = i;
            else
                dp[i] = dp[i-1];
        }
        int maxn = 0;
        for(int i=1;i<dp.length;i++){
            if(prices[i]-prices[dp[i]]>maxn)
                maxn = prices[i] - prices[dp[i]];
        }
        return maxn;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

64 求1+2+…+n

题目描述：
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
题目地址：https://leetcode-cn.com/problems/qiu-12n-lcof/
我的想法：
用&&运算符实现递归。

class Solution {
    boolean flg = false;
    int sum = 0;
    public int sumNums(int n) {
        flg = ((n>0) && (n += sumNums(n-1))>0);
        return n;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

66 构建乘积数组

题目描述：
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
题目地址：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/
我的想法：
用两个数组存中间运算结果，一个从左往右乘，一个从右往左乘。

class Solution {
    public int[] constructArr(int[] a) {
        if(a.length==0) return new int[]{};
        int[] left = new int[a.length];
        int[] right = new int[a.length];
        int[] res = new int[a.length];
        left[0] = a[0];
        right[a.length-1] = a[a.length-1];
        for(int i=1;i<a.length;i++){
            left[i] = left[i-1] * a[i];
            right[a.length-i-1] = right[a.length-i] * a[a.length-i-1];
        }
        for(int i=1;i<a.length-1;i++)
            res[i] = left[i-1] * right[i+1];
        res[0] = right[1];
        res[a.length-1] = left[a.length-2];
        return res;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

67 把字符串转换成整数

题目描述：
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
题目地址：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/
我的想法：
用自动机状态转移判断字符串是否合法，然后截取符合 要求的那部分去计算数字，为了防止溢出边缘计算时int溢出所以中间结果用long存储。

class Solution {
    public enum CharType{
        CHAR_SIGN,
        CHAR_NUM,
        CHAR_ERROR
    };
    private enum State{
        STATE_BEGIN,
        STATE_SIGN,
        STATE_NUM,
        STATE_END,
        STATE_ERROR
    };
    public CharType getType(char c){
        if(c=='+' || c=='-') return CharType.CHAR_SIGN;
        if(c>='0' && c<='9') return CharType.CHAR_NUM;
        else return CharType.CHAR_ERROR;
    }
    public int getInt(char[] ch,int left,int right){
        long num = 0,base = 1;
        boolean flg = true;
        if(ch[left]=='+') left++;
        else if(ch[left]=='-'){ flg = false;left++;}
        for(int i=left;i<=right;i++){
            if(ch[i]=='0') left++;
            else break;
        }
        for(int i=right;i>=left;i--){
            num += (ch[i]-48)*base;
            if(!flg && (-num<-2147483648 || base>1000000000)) return -2147483648;
            if(flg && (num>2147483647 || base>1000000000)) return 2147483647;
            base *= 10;
        }
        return (flg?(int)num:(int)-num);
    }
    public int strToInt(String str) {
        char[] s = str.trim().toCharArray();//去除空格
        if(s.length==0) return 0;
        Map<State,Map<CharType,State>> map = new HashMap<>();
        //初始状态转移
        map.put(State.STATE_BEGIN,new HashMap<>(){{
            put(CharType.CHAR_SIGN,State.STATE_SIGN);
            put(CharType.CHAR_NUM,State.STATE_NUM);
            put(CharType.CHAR_ERROR,State.STATE_ERROR);
        }});
        //符号状态转移
        map.put(State.STATE_SIGN,new HashMap<>(){{
            put(CharType.CHAR_NUM,State.STATE_NUM);
            put(CharType.CHAR_ERROR,State.STATE_ERROR);
        }});
        //数字状态转移
        map.put(State.STATE_NUM,new HashMap<>(){{
            put(CharType.CHAR_NUM,State.STATE_NUM);
            put(CharType.CHAR_ERROR,State.STATE_END);
            put(CharType.CHAR_SIGN,State.STATE_END);
        }});
        State state = State.STATE_BEGIN;//初始状态
        int i;
        for(i=0;i<s.length;i++){
            CharType type = getType(s[i]);//获得字符类型
            state = map.get(state).get(type);//当前字符应该是什么状态
            if(state==null) return 0;
            if(state==State.STATE_ERROR) return 0;
            if(state==State.STATE_END) break;
        }
        long num = getInt(s,0,i-1);
        return (int)num;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69

34 二叉树中和为某一值的路径

题目描述：
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
题目地址：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
我的想法：
dfs，顺带记住一个深复制list的写法：list1.add(new LinkedList(list2));

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<List<Integer>> list;
    public void dfs(TreeNode root,int target,int sum,List<Integer> l){
        if(root==null) return ;
        if(root.left==null && root.right==null){
            l.add(root.val);
            if(sum+root.val==target)
                list.add(new LinkedList(l));//复制列表
            l.remove(l.size()-1);
            return ;
        }
        l.add(root.val);
        if(root.left!=null)
            dfs(root.left,target,sum+root.val,l);
        if(root.right!=null)
            dfs(root.right,target,sum+root.val,l);
        l.remove(l.size()-1);
    }
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        list = new LinkedList<>();
        List<Integer> l = new LinkedList<>();
        dfs(root,target,0,l);
        return list;
    }
}

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

剑指offer中等题二刷完毕，接下来准备按顺序刷leetcode的1~200题。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/811156
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号