剑指offer(针对hot100补充)

# 03. 数组中重复的数字 (opens new window)

方法一：原地哈希

class Solution {
    public int findRepeatDocument(int[] nums) {
        int n = nums.length;
        // 把nums[i]放在i位置上
        for(int i=0;i<n;i++){
            if(nums[i]!=nums[nums[i]]){
                swap(nums,i,nums[i]);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i){
                return nums[i];
            }
        }
        return -1;
    }
    void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

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

方法二：HashMap

class Solution {
    public int findRepeatDocument(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            if(set.contains(num))
                return num;
            set.add(num);
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 14. 剪绳子 (opens new window)

class Solution {
    public int cuttingBamboo(int n) {
        int[] dp = new int[n+1];//长度为i的绳子减为m段最大乘积
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                // 前j段剪或不剪
                dp[i] = Math.max(Math.max(dp[j]*(i-j),j*(i-j)),dp[i]);
            }
        }
        return dp[n];
    }
}

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

# 16. 数值的整数次方 (opens new window)

class Solution {
    public double myPow(double x, int n) {
        if(n==0)
            return 1;
        // Integer.MIN_VALUE的相反数还是他自己
        if(n==Integer.MIN_VALUE)
            return myPow(1/x,-(n+1))/x;
        if(n<0)
            return myPow(1/x,-n);

        if(n%2==1){
            return x*myPow(x,n-1);
        }else{
            double sub = myPow(x,n/2);
            return sub*sub;
        }
    }
}

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

# 17. 打印从1到最大的n位数 (opens new window)

方法一：模拟

class Solution {
    public int[] printNumbers(int n) {
        int max = 0;
        for(int i=0;i<n;i++){
            max = 10*max+9;
        }
        int[] res = new int[max];
        for(int i=1;i<=max;i++){
            res[i-1] = i;
        }
        return
    }
}

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

考虑大数：

class Solution {
    char[] loop = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8' ,'9'};
    StringBuilder sb = new StringBuilder();
    public int[] printNumbers(int n) {
        dfs(0,n,"",true);
        sb.deleteCharAt(0);
        sb.deleteCharAt(sb.length()-1);
        String s = sb.toString();
        return Arrays.stream(s.split(",")).mapToInt(Integer::parseInt).toArray();
    }
    //i:当前要填的位，n：总位数，path：一个符合的结果，isPre：是否有前导0
    private void dfs(int i,int n,String path,boolean isPre){
        if(i==n){
            sb.append(path+",");
            return ;
        }
        for(char c:loop){
            if(isPre && c=='0'){//有前导0
                dfs(i+1,n,path,true);
            }else{//不含前导0
                dfs(i+1,n,path+c,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

# 21. 调整数组顺序使奇数位于偶数前面 (opens new window)

class Solution {
    public int[] trainingPlan(int[] nums) {
        int i=0,j=nums.length-1;
        while(i<j){
            while(i<j && (nums[i]&1)==1)
                i++;
            while(i<j && (nums[j]&1)==0)
                j--;
            // i与j的位置都到了需要交换的地方
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

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

# 08.06. 汉诺塔问题 (opens new window)

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int n = A.size();
        dfs(n,A,B,C);
    }
    // 将n个从start移动到end
    void dfs(int i,List<Integer> start,List<Integer> other,List<Integer> end){
        if(i==1)
            end.add(start.remove(start.size()-1));
        else{
            // 将n-1个从start移动到other
            dfs(i-1,start,end,other);
            // 将第n个从start移动到end
            end.add(start.remove(start.size()-1));
            // 将n-1个从other移动到end
            dfs(i-1,other,start,end);
        }
    }
}

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

# 26. 树的子结构 (opens new window)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 特例，也为false
        if(A==null && B==null)
            return false;
        // 只有一个为空，肯定false
        if(A==null || B==null)
            return false;
        // 从根节点开始判断是不是子树，不是从A的左右子树递归
        return isChild(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    // 判断root为b的树是否root为a的子树
    boolean isChild(TreeNode a,TreeNode b){
        if(b==null)
            return true;
        // 简化了a为空，b不为空
        if(a==null || a.val!=b.val)
            return false;
        return isChild(a.left,b.left) && isChild(a.right,b.right);
    }
}

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

# 100. 相同的树 (opens new window)

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null)
            return true;
        if(p==null || q==null)
            return false;
        if(p.val!=q.val)
            return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 31. 栈的压入、弹出序列 (opens new window)

class Solution {
    public boolean validateBookSequences(int[] pushed, int[] poped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int e:pushed){
            stack.push(e);
            while(!stack.isEmpty() && stack.peek()==poped[j]){
                stack.pop();
                j++;
            }
        }
        return j==pushed.length;
    }
}

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

# 33. 二叉搜索树的后序遍历序列 (opens new window)

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        return dfs(postorder,0,postorder.length-1);
    }
    // 后序  左子树  右子树  根节点
    boolean dfs(int[] postorder,int i,int j){
        // 归并到只有一个节点，肯定为true
        if(i>=j) 
            return true;
        int p = i;
        while(postorder[p]<postorder[j]){
            p++;
        }
        // 第一个比根节点大的 为右子树的左边界
        int m = p;
        // 右子树应该左右的值都比 根节点的值大，正常遍历到最后p==j
        while(postorder[p]>postorder[j]){
            p++;
        }
        return p==j && dfs(postorder,i,m-1) && dfs(postorder,m,j-1);
    }
}

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

# 36. 二叉搜索树与双向链表 (opens new window)

class Solution {
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if(root==null)
            return root;
        dfs(root);
        pre.right = head;
        head.left = pre;
        return head;
    }
    void dfs(Node cur){
        if(cur==null)
            return ;
        dfs(cur.left);
        if(pre==null)
            head = cur;
        else
            pre.right = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

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

# 45. 把数组排成最小的数 (opens new window)

class Solution {
    public String crackPassword(int[] nums) {
        String[] ss = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            ss[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(ss,(x,y)->{
            return (x+y).compareTo(y+x);
        });
        StringBuilder sb = new StringBuilder();
        for(String s:ss){
            sb.append(s);
        }
        return sb.toString();
    }
}

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

更改x+y的位置变成最大数

# 46. 把数字翻译成字符串 (opens new window)

class Solution {
    public int crackNumber(int num) {
        String s = String.valueOf(num);
        int[] dp = new int[s.length()+1];// 以i结尾的字符串由dp[i+1]中解法
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=s.length();i++){
            String tmp = s.substring(i-2,i);
            if(tmp.compareTo("10")>=0 && tmp.compareTo("25")<=0){
                dp[i] = dp[i-1]+dp[i-2];
            }else{
                dp[i] = dp[i-1];
            }
        }
        return dp[s.length()];
    }
}

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

# 49. 丑数 (opens new window)

方法一：set+pq

class Solution {
    public int nthUglyNumber(int n) {
        int[] factors = {2,3,5};
        Set<Long> set = new HashSet<>();
        Queue<Long> pq = new PriorityQueue<>();
        set.add(1L);
        pq.offer(1L);
        int ans = 0;
        for(int i=0;i<n;i++){
            long cur = pq.poll();
            ans = (int)cur;
            for(int f:factors){
                long nxt = cur*f;
                if(set.add(nxt))
                    pq.offer(nxt);
            }
        }
        return ans;
    }
}

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

方法二：数组

class Solution {
    public int nthUglyNumber(int n) {
        int a=0,b=0,c=0;
        int[] res = new int[n];
        res[0] = 1;
        for(int i=1;i<n;i++){
            int n2=res[a]*2;
            int n3=res[b]*3;
            int n5=res[c]*5;
            res[i] = Math.min(Math.min(n2,n3),n5);
            if(res[i]==n2) a++;
            if(res[i]==n3) b++;
            if(res[i]==n5) c++;
        }
        return res[n-1];
    }
}

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

# 50. 第一个只出现一次的字符 (opens new window)

class Solution {
    public char dismantlingAction(String arr) {
        int[] cnt = new int[26];
        for(int i=0;i<arr.length();i++){
            cnt[arr.charAt(i)-'a']++;
        }
        for(int i=0;i<arr.length();i++){
            char c = arr.charAt(i);
            if(cnt[c-'a']==1){
                return c;
            }
        }
        return ' ';
    }
}

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

# 51. 数组中的逆序对 (opens new window)

class Solution {
    int ans;
    public int reversePairs(int[] nums) {
        merge(nums,0,nums.length-1);
        return ans;
    }
    void merge(int[] nums,int l,int r){
        int m = l+(r-l)/2;
        if(l<r){
            merge(nums,l,m);
            merge(nums,m+1,r);
            mergeSort(nums,l,m,r);
        }
    }
    void mergeSort(int[] nums,int l,int m,int r){
        int[] tmp = new int[r-l+1];
        int idx = 0;
        int t1=l,t2=m+1;
        while(t1<=m&&t2<=r){
            if(nums[t1]<=nums[t2]){
                tmp[idx++] = nums[t1++];
            }else{
                //统计逆序对个数
                ans += (m-t1+1);
                tmp[idx++] = nums[t2++];
            }
        }
        //左边剩余数移入数组
        while(t1<=m){
            tmp[idx++] = nums[t1++];
        }
        //右
        while(t2<=r){
            tmp[idx++] = nums[t2++];
        }
        //tmp覆盖nums
        for(int k=0;k<tmp.length;k++){
            nums[k+l] = tmp[k];
        }
    }
}

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

# 55 - II. 平衡二叉树 (opens new window)

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        return Math.abs(getDepth(root.left)-getDepth(root.right))<=1
        && isBalanced(root.left) && isBalanced(root.right);
    }
    int getDepth(TreeNode root){
        if(root==null) return 0;
        return Math.max(getDepth(root.left),getDepth(root.right))+1;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 56 - I. 数组中数字出现的次数 (opens new window)

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int n = 0,m=1;
        for(int num:sockets){
            n ^= num;
        }
        // 找到一个单值
        while((n&m)==0){
            m<<=1;
        }
        // 将数组分为两部分
        int x=0,y=0;
        for(int num:sockets){
            if((num&m)!=0){
                x ^= num;
            }else{
                y ^= num;
            }
        }
        return new int[]{x,y};
    }
}

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

# 56 - II. 数组中数字出现的次数 II (opens new window)

class Solution {
    public int trainingPlan(int[] actions) {
        int[] cnt = new int[32];
        for(int num:actions){
            for(int i=0;i<32;i++){
                cnt[i] += num&1;
                num>>=1;
            }
        }
        int res = 0;
        for(int i=31;i>=0;i--){
            res<<=1;
            res|=cnt[i]%3;
        }
        return res;
    }
}

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

# 57 - II. 和为 s 的连续正数序列 (opens new window)

class Solution {
    public int[][] fileCombination(int target) {
        int i=1,j=2,s=3;
        List<int[]> res = new ArrayList<>();
        while(i<j){
            if(s==target){
                int[] ans = new int[j-i+1];
                for(int k=i;k<=j;k++){
                    ans[k-i] = k;
                }
                res.add(ans);
            }
            if(s>=target){
                s-=i;
                i++;
            }else{
                j++;
                s+=j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

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

# 59 - II. 队列的最大值 (opens new window)

class Checkout {
    Queue<Integer> queue;
    Deque<Integer> deque;
    public Checkout() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    
    public int get_max() {
        return deque.isEmpty()?-1:deque.peekFirst();
    }
    
    public void add(int value) {
        queue.offer(value);
        while(!deque.isEmpty() && deque.peekLast()<value){
            deque.pollLast();
        }
        deque.offerLast(value);
    }
    
    public int remove() {
        if(queue.isEmpty()) return -1;
        if(queue.peek().equals(deque.peekFirst())){
            deque.pollFirst();
        }
        return queue.poll();
    }
}

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

# 61. 扑克牌中的顺子 (opens new window)

0为癞子，最大值-最小值<5返回true

方法一：

class Solution {
    public boolean isStraight(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int max = 0,min = 14;
        for(int num:nums){
            if(num==0){
                continue;
            }
            max = Math.max(num,max);
            min = Math.min(num,min);
            if(set.contains(num)) return false;
            set.add(num);
        }
        return max-min<5;
    }
}

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

方法二：

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums);
        for(int i=0;i<4;i++){
            if(nums[i]==0){
                joker++;
            }else if(nums[i]==nums[i+1]){
                return false;
            }
        }
        return nums[4]-nums[joker]<5;
    }
}

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

# 65. 不用加减乘除做加法 (opens new window)

class Solution {
    public int encryptionCalculate(int dataA, int dataB) {
        while(dataB != 0){
            int c = (dataA & dataB)<<1;// 进位
            dataA ^= dataB;// 非进位和
            dataB = c;
        }
        return dataA;
    }
}

1
2
3
4
5
6
7
8
9
10

# 68 - I. 二叉搜索树的最近公共祖先 (opens new window)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val>p.val && root.val>q.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val<p.val && root.val<q.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# 68 - II. 二叉树的最近公共祖先 (opens new window)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null || root==p || root==q){
            return root;
        }
        TreeNode l = lowestCommonAncestor(root.left,p,q);
        TreeNode r = lowestCommonAncestor(root.right,p,q);
        if(l==null && r==null){
            return null;
        }
        if(l==null) return r;
        if(r==null) return l;
        return root;//l!=null&&r!=null
    }
}

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

← 经典150(针对hot100补充) 数组→