力扣学习录03--剑指Offer刷题记录（下）

Huang Zhiwei
  2023-06-02 22:16:54 2023-06-02 22:16 创建   2023-09-02 23:41:40 2023-09-02 23:41 更新    

剑指Offer刷题记录，共75题，目前尚有若干困难题未完成，先放一放

剑指 Offer（第 2 版） - 力扣（LeetCode）

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
/**
 * @description: 栈的压入、弹出序列
 * 使用模拟法，创建一个栈，进入循环；循环的终止条件是两个数组下标一起越界了；当栈为空且pushed数组下标未越界，那就压栈一个数字；
 * 比较poped数组下标位置元素和栈顶元素，如果相同，就出栈，否则继续压栈；
 * 也有官网给出的简洁写法
 * @author: Huang Zhiwei
 * @time: 2023/4/30 17:05
 */
public class Offer31 {
    public static void main(String[] args) {
        int[] pushed = {1,2,3,4,5};
        int[] poped = {4,5,3,2,1};
//        int[] pushed = {0,2,1};
//        int[] poped = {0,1,2};
        System.out.println(validateStackSequences(pushed, poped));
    }
    public static boolean validateStackSequences(int[] pushed, int[] popped){
        if(pushed.length != popped.length){
            return false;
        }
        if(pushed.length == 0){
            return true;
        }
        if(pushed.length == 1){
            return pushed[0] == popped[0];
        }
        Stack<Integer> stack = new Stack<>();
        int popindex = 0;
        int pushindex = 0;
        stack.push(pushed[pushindex++]);
        while(pushindex < pushed.length || popindex <popped.length){
            if(stack.isEmpty()){
                if(pushindex >= pushed.length){
                    return false;
                }
                stack.push(pushed[pushindex++]);
            }
            if(stack.peek() != popped[popindex]){
                if(pushindex >= pushed.length){
                    return false;
                }
                stack.push(pushed[pushindex++]);
            }else {
                popindex++;
                stack.pop();
            }
        }
        return true;
    }
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int n = pushed.length;
        for (int i = 0, j = 0; i < n; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @description: 从上到下打印二叉树
 * 不能使用递归，用栈模拟即可
 * @author: Huang Zhiwei
 * @time: 2023/4/30 20:12
 */
public class Offer32_1 {
    public static void main(String[] args) {

    }
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[]{};
        Deque<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        int[] ans = new int[1000];
        int temp = 0;
        while (!treeNodes.isEmpty()){
            TreeNode out = treeNodes.pop();
            if(out.left != null) treeNodes.add(out.left);
            if(out.right != null) treeNodes.add(out.right);
            ans[temp++] = out.val;
        }
        return Arrays.copyOfRange(ans,0,temp-1);
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @description: 从上到下打印二叉树 II
 * 和102题层序遍历相同，我们使用一个List<List<Integer>>存放答案；内部嵌套的就是每一层构成的List<Integer>；
 * 这里我使用一个标记nextLayercount标记
 * @author: Huang Zhiwei
 * @time: 2023/4/30 20:30
 */
public class Offer32_2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //特殊情况，为空时直接返回
        if(root==null)return new ArrayList<>();
        //tempLayercount表示当前层还剩余几个节点需要打印；nextLayercount表示下一层共有几个节点需要打印
        int tempLayercount = 1;
        int nextLayercount = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> innerans = new ArrayList<>();
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            innerans.add(node.val);
            //左右节点不为空就将当前节点的左右节点加入队列，且下一层的计数加一
            if(node.left!=null) {queue.add(node.left);nextLayercount+=1;}
            if(node.right!=null) {queue.add(node.right);nextLayercount+=1;}
            //当前层的计数器减一，如果减到零了就将当前层加入到总的答案list中去
            tempLayercount -= 1;
            if(tempLayercount == 0){
                tempLayercount = nextLayercount;
                if(!innerans.isEmpty()){ans.add(innerans);}
                innerans = new ArrayList<>();
                nextLayercount = 0;
            }
        }
        if(!innerans.isEmpty()){ans.add(innerans);}
        return ans;
    }
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * @description: 从上到下打印二叉树 III
 * 之字形打印，和前一题非常类似，但是需要区分奇偶层，相当于再添加一个标志位，如果是奇数就直接添加；如果是偶数层就反序以下再添加；
 * 这是最简单的修改方式
 * @author: Huang Zhiwei
 * @time: 2023/4/30 20:40
 */
public class Offer32_3 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //特殊情况，为空时直接返回
        if(root==null)return new ArrayList<>();
        //tempLayercount表示当前层还剩余几个节点需要打印；nextLayercount表示下一层共有几个节点需要打印
        int tempLayercount = 1;
        int nextLayercount = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> innerans = new ArrayList<>();
        //层数计数器
        int countlevel = 0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            innerans.add(node.val);
            //左右节点不为空就将当前节点的左右节点加入队列，且下一层的计数加一
            if(node.left!=null) {queue.add(node.left);nextLayercount+=1;}
            if(node.right!=null) {queue.add(node.right);nextLayercount+=1;}
            //当前层的计数器减一，如果减到零了就将当前层加入到总的答案list中去
            tempLayercount -= 1;
            if(tempLayercount == 0){
                tempLayercount = nextLayercount;
                countlevel ++;
                if(!innerans.isEmpty()){
                    //奇数层正序，偶数层反序
                    if(countlevel %2 == 1){
                        ans.add(innerans);
                    }else {
                        Collections.reverse(innerans);
                        ans.add(innerans);
                    }

                }
                innerans = new ArrayList<>();
                nextLayercount = 0;
            }
        }
        if(!innerans.isEmpty()){ans.add(innerans);}
        return ans;
    }

}

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

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 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
/**
 * @description: 二叉搜索树的后序遍历序列
 * 分两步，第一步是划分左右子树，第二步是递归检查是否是二叉搜索树
 * 划分左右子树，根据二叉搜索树的定义，左子树小于根节点，右子树大于根节点
 * 递归调用时，有两个检验，第一个检验是出现一次大于根节点的值后就应该始终大于根节点了；第二个检验就是递归检验
 * @author: Huang Zhiwei
 * @time: 2023/4/30 20:57
 */
public class Offer33 {
    public static void main(String[] args) {
        int[] input = {1,3,2,6,5};
        System.out.println(verifyPostorder(input));
    }
    public static boolean verifyPostorder(int[] postorder) {
        //划分左右子树，根据二叉搜索树的定义，左子树小于根节点，右子树大于根节点
        return verifyhelper(postorder,0,postorder.length-1);
    }
    public static boolean verifyhelper(int[] postorder,int start,int end){
        if(start >= end){
            return true;
        }
        boolean flagFirst = true;
        int mid = start;
        int midout = start;
        //后续遍历时末尾的就是根节点
        int rootval = postorder[end];
        while(mid < end){
            if(postorder[mid] > rootval){
                //第一次大于根节点的位置就是右子树起点位置，用midout保存
                if(flagFirst){
                    midout = mid;
                }
                //出现一次大于根节点的值后就应该始终大于根节点了，将标志位置为false
                flagFirst = false;
                mid++;
                //小于根节点且标志位为真：表示一直都是小于根节点的
            }else if(postorder[mid] < rootval && flagFirst){
                mid++;
            }else {
                return false;
            }
        }
        //递归调用
        return verifyhelper(postorder,start,midout-1)&&verifyhelper(postorder,midout,end-1);
    }
}

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

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

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
/**
 * @description: 二叉树中和为某一值的路径
 * 由于需要返回List<List<Integer>>类型的量，所以不能将父亲节点的值直接加到左右节点上
 * 使用三个全局变量，sum、innerans、ans辅助
 * 用一个helper函数作为递归函数，分别递归左右子树，需要注意的是innerans的清理时机、深拷贝innerans加到ans中去
 * @author: Huang Zhiwei
 * @time: 2023/5/1 16:25
 */
public class Offer34 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(pathSum(root, 3));
    }
    static int sum = 0;
    static LinkedList<Integer> innerans = new LinkedList<>();
    static List<List<Integer>> ans = new ArrayList<>();

    public static List<List<Integer>> pathSum(TreeNode root, int target) {
        //由于innerans和ans是static的，在测试中多次调用函数，所以需要先将它清理
        ans.clear();
        innerans.clear();
        //为空时直接返回空
        if(root == null) return new ArrayList<>();
        pathSumHelper(root,target);
        return ans;
    }
    public static void pathSumHelper(TreeNode root, int target){
        //当前值一定不为空，就先加上
        sum += root.val;
        innerans.add(root.val);
        if(root.right != null || root.left != null){
            //分别对左右子树做递归
            if(root.right !=null){
                pathSumHelper(root.right,target);
            }
            if(root.left != null){
                pathSumHelper(root.left,target);
            }
            //减去当前节点的信息
            sum -= root.val;
            innerans.removeLast();
        }else {
            //比较当前和与目标，如果相同就加入答案，需要深拷贝一份
            if(sum == target){
                ans.add(new LinkedList<Integer>(innerans));
            }
            sum -= root.val;
            innerans.removeLast();
        }
    }
}

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @description: 复杂链表的复制
 * 难点在于对random的实现；可以使用哈希表存放random节点对应的拷贝节点；
 * 递归调用，让节点的random和next分开创建
 * @author: Huang Zhiwei
 * @time: 2023/5/1 17:12
 */
public class Offer35 {
    public static void main(String[] args) {

    }
    Map<Node, Node> cachedNode = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if(head == null) return null;

        if (!cachedNode.containsKey(head)){
            Node dummy = new Node(head.val);
            cachedNode.put(head,dummy);
            dummy.next = copyRandomList(head.next);
            dummy.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

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
/**
 * @description: 二叉搜索树与双向链表
 * 一种做法是将搜索树的值进行排列后再构造树；但是由于不能创建新的节点，所以这个方法不是很好；
 * 先使用中序遍历，对于搜索树来说序列就是递增序列，相当于排好序了，可以用queue来辅助；
 * 然后用链表的pre、cur操作这个queue
 * leetcode给出了递归的解法，比上述思路好很多
 * @author: Huang Zhiwei
 * @time: 2023/5/1 17:22
 */
public class Offer36 {
    TreeNode pre, head;
    public TreeNode treeToDoublyList(TreeNode root) {
        if(root == null) return null;
        //中序遍历，操作中间的所有节点
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(TreeNode cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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
/**
 * @description: 序列化二叉树
 * 构造一个辅助栈存放父节点
 * 需要注意的是如果父节点的左右子树为空，那么需要将null添加进StringBuilder中
 * @author: Huang Zhiwei
 * @time: 2023/5/1 20:13
 */
public class Offer37_2 {
    public static void main(String[] args) {
        String input ="1 2 3 null null 4 5 null null null null";
        TreeNode out = deserialize(input);
        System.out.println("finished");
        System.out.println(serialize(out));
    }
    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        if(root == null){
            return "null ";
        }
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);
        while (!treeNodes.isEmpty()){
            TreeNode temp = treeNodes.pop();
            if(temp == null){
                sb.append("null ");
                continue;
            }
            sb.append(temp.val);
            sb.append(" ");
            if(temp.left != null){
                treeNodes.add(temp.left);
            }else {
                treeNodes.add(null);
            }
            if(temp.right !=  null){
                treeNodes.add(temp.right);
            }else {
                treeNodes.add(null);
            }

        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        if(data.equals("null ")){
            return null;
        }
        String[] dataqueue = data.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(dataqueue[0]));
        //构造辅助栈
        Deque<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);

        TreeNode fatherNode = treeNodes.peek();
        TreeNode tempNode = null;
        for(int i = 1;i<dataqueue.length;i++){
            fatherNode = treeNodes.peek();
            if(dataqueue[i].equals("null") ){
                if((i+1) %2 == 0){
                    fatherNode.left = null;
                }else {
                    fatherNode.right = null;
                    treeNodes.pop();
                }
                continue;
            }
            tempNode = new TreeNode(Integer.parseInt(dataqueue[i]));
            if((i+1) %2 == 0){
                fatherNode.left = tempNode;
                treeNodes.add(tempNode);
            }else {
                fatherNode.right = tempNode;
                treeNodes.add(tempNode);
                treeNodes.pop();
            }
        }
        return root;
    }
}

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

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
/**
 * @description: 字符串的排列
 * 和全排列一样使用回溯法，但效率非常低，其中的重大缺陷在于hashset、Stringbuilder、递归调用的巨大耗时上
 * @author: Huang Zhiwei
 * @time: 2023/5/1 20:40
 */
public class Offer38 {
    public static void main(String[] args) {
        String input = "aab";
        System.out.println(Arrays.toString(permutation(input)));
    }

    public static String[] permutation(String s) {

        if(s.length() == 1) return new String[]{s};
        HashSet<String> ans = new HashSet<>();
        for(int i = 0;i<s.length();i++){
            String temp = String.valueOf(s.charAt(i));
            String newString = s.replaceFirst(temp,"");
            String[] thistime = permutation(newString);
            for (String item:thistime){
                StringBuilder stringBuilder = new StringBuilder(item);
                stringBuilder.append(temp);
                ans.add(stringBuilder.toString());
            }
        }
        String[] re = new String[ans.size()];
        int i = 0;
        for(String x:ans){
            re[i++] = x;
        }
        return re;
    }
}

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

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
/**
 * @description: 数组中出现次数超过一半的数字
 * 由于一定存在多数元素，用两军交战的思想，哪边人数多就是哪边胜出；
 * 用一个计数器保存一方的数量，如果数量为0，那么下一个进入的元素就会夺得target，只需要一次遍历即可找出多数元素，且消耗较小
 * @author: Huang Zhiwei
 * @time: 2023/5/2 13:38
 */
public class Offer39 {
    public static void main(String[] args) {
        int[] inputs = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(majorityElement(inputs));
    }
    public static int majorityElement(int[] nums) {
        //计数器
        int count = 0;
        //相当于军旗，标志
        int target = nums[0];
        for(int item:nums){
            if(count == 0){
                target = item;
            }
            if(item == target){
                count +=1;
            }else{
                count -=1;
            }
        }
        return target;
    }
}

剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @description: 最小的k个数
 * 首先想到的是维护一个小顶堆，使用优先级队列即可，此方法的空间复杂度较大，因为需要申请大量额外空间
 * 也可以取巧，直接使用排序后的数组
 * @author: Huang Zhiwei
 * @time: 2023/5/2 13:48
 */
public class Offer40 {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int x:arr){
            queue.add(x);
        }
        int[] ans = new int[k];
        for(int i = 0;i<k;i++){
            ans[i] = queue.poll();
        }
        return ans;
    }
}

剑指 Offer 41. 数据流中的中位数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class MedianFinder {
    // 用两个优先级队列存放大于中位数和小于中位数的数
    // 我们假设minQueue中的个数比maxQueue多1，即先添加到minQueue中
    // 这样如果size是奇数，那就直接返回minQueue的队头，否则返回两个队列队头的平均值
    // java优先级队列默认是小顶堆
    PriorityQueue<Integer> maxQueue;
    PriorityQueue<Integer> minQueue;
    /** initialize your data structure here. */
    public MedianFinder() {
        maxQueue = new PriorityQueue<>();
        minQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
    }

    public void addNum(int num) {
        //表示第一个，加入minQueue
        if(minQueue.size() == 0){
            minQueue.add(num);
            return;}
        if(maxQueue.size() == 0 && num > minQueue.peek()){
            maxQueue.add(num);
            return;
        }
        //不是第一个就走正常流程
        if(num > minQueue.peek()){
            maxQueue.add(num);
            if(maxQueue.size() != minQueue.size()){
                minQueue.add(maxQueue.poll());
            }
        }else {
            minQueue.add(num);
            if(minQueue.size() != maxQueue.size()+1){
                maxQueue.add(minQueue.poll());
            }
        }
    }

    public double findMedian() {
        if(minQueue.size() > maxQueue.size()){
            return (double) minQueue.peek();
        }else {
            return ((double) minQueue.peek()+maxQueue.peek())/2;
        }
    }
}

剑指 Offer 42. 连续子数组的最大和 

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
/**
 * @description: 连续子数组的最大和
 * 动态规划问题，如果前面的子串和小于0，那不如不加，即重置子串和为当前元素；如果前面子串和大于0，那就可以加上
 * @author: Huang Zhiwei
 * @time: 2023/5/2 13:55
 */
public class Offer42 {
    public static void main(String[] args) {
        int[] inputs = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(inputs));
    }
    public static int maxSubArray(int[] nums) {
        int temp = nums[0];
        int max = Math.max(Integer.MIN_VALUE,temp);
        for(int i = 1;i<nums.length;i++){
            if(temp<0){
                temp = nums[i];
            }else {
                temp = nums[i]+temp;
            }
            max = Math.max(temp,max);
        }
        return max;
    }
}

剑指 Offer 43. 1～n 整数中 1 出现的次数

剑指 Offer 44. 数字序列中某一位的数字 

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
/**
 * @description: 数字序列中某一位的数字
 * 分段问题，从位数较低的地方开始看起：
 * 0-9：即第0-9位，直接返回
 * 10-99：即第10-（10+90*2）=189
 * 100-999：即第190-（190+3*900）=2890
 * 那么可以总结一个规律：位数占用会逐步增长：1*9，2*90，3*99，4*999.。。。。。
 * 根据查询的位数可以知道属于那个位数区间
 * @author: Huang Zhiwei
 * @time: 2023/5/2 19:41
 */
public class Offer44 {
    public int findNthDigit(int n) {
        //d表示位数，count表示当前位数的数占据了多少位数
        int d = 1, count = 9;
        while (n > (long) d * count) {
            //从第一位算起
            n -= d * count;
            d++;
            count *= 10;
        }
        int index = n - 1;
        int start = (int) Math.pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }
}

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

剑指 Offer 46. 把数字翻译成字符串

剑指 Offer 47. 礼物的最大价值

剑指 Offer 48. 最长不含重复字符的子字符串

剑指 Offer 49. 丑数

剑指 Offer 50. 第一个只出现一次的字符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @description: 第一个只出现一次的字符
 * 只出现小写字母，就创建长度为26的数组；两次遍历，第一次遍历，计数；第二次遍历，找到第一个出现的字符
 * @author: Huang Zhiwei
 * @time: 2023/5/2 14:18
 */
public class Offer50 {
    // 计数数组
    public char firstUniqChar(String s) {
        //只出现小写字母，就创建长度为26的数组
        int[] count = new int[26];
        char[] chars = s.toCharArray();
        //第一次遍历，计数
        for (char c : chars) count[c - 'a']++;
        //第二次遍历，找到第一个
        for (char c : chars) {
            if (count[c - 'a'] == 1) return c;
        }
        return ' ';
    }
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @description: 两个链表的第一个公共节点
 * 双指针法，两个指针一开始指向A的头和B的头，如果指向同一个节点了，那就返回这个节点，无论是否为空；
 * 如果一个指针指向空了，如果是A就将A指向B的头，是B就将B指向A的头；
 * @author: Huang Zhiwei
 * @time: 2023/5/2 14:33
 */
public class Offer52 {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @description:  在排序数组中查找数字 I
 * 遍历计数
 * @author: Huang Zhiwei
 * @time: 2023/5/2 15:28
 */
public class Offer53_1 {
    public static void main(String[] args) {
        int[] inputs = {5,7,7,8,8,10};
        System.out.println(search(inputs, 8));
    }
    public static int search(int[] nums, int target) {
        int count = 0;
        for(int x:nums){
            if(x > target){
                break;
            }else if(x == target){
                count++;
            }
        }
        return count;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @description: 0～n-1中缺失的数字
 * 二分查找法，在第i位的数字应当是等于i的，如果第i位的数字等于i-1了，说明应该去前面的区间找；反之去后面的区间找；
 * @author: Huang Zhiwei
 * @time: 2023/5/2 15:31
 */
public class Offer53_2 {
    public static void main(String[] args) {
        int[] inputs = {1};
        System.out.println(missingNumber(inputs));
    }
    public static int missingNumber(int[] nums) {
        int l = 0, h = nums.length-1, m = (l+h)/2;

        while (l <= h) {
            if (m != nums[m]) { // 缺失的数字在m位置前
                h = m-1;
            } else { // 缺失的数字在m位置后
                l = m+1;
            }
            m = (l+h)/2;
        }
        return l;
    }
}

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

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

import static com.jianzhioffer.Offer37_2.deserialize;

/**
 * @description: 二叉搜索树的第k大节点
 * 解1：
 * 二叉搜索树的中序遍历就是单调递增的，如果使用后、中、前的顺序那就是单调递减的；利用这个性质可以直接吐出第k大的值
 * 解2：
 * 维护一个大根堆，将树的所有节点送入，然后挨个弹出，弹出的第k个既是目标；但是这个方式效率极低；
 * @author: Huang Zhiwei
 * @time: 2023/5/1 22:58
 */
public class Offer54 {
    public static void main(String[] args) {
        String input ="5 3 6 2 4 null null 1";
        TreeNode out = deserialize(input);
        System.out.println(kthLargest2(out,3));
    }
    public int kthLargest(TreeNode root, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        Deque<TreeNode> treeNodeDeque = new LinkedList<>();
        treeNodeDeque.add(root);
        while (!treeNodeDeque.isEmpty()){
            TreeNode temp = treeNodeDeque.pop();
            priorityQueue.add(temp.val);
            if(temp.left != null){
                treeNodeDeque.add(temp.left);
            }
            if(temp.right !=  null){
                treeNodeDeque.add(temp.right);
            }
        }
        while (k>1){
            priorityQueue.poll();
            k --;
        }
        return priorityQueue.poll();
    }
    public static int kthLargest2(TreeNode root, int k) {
        lastrank(root,k);
        int re = ranked.getLast();
        ranked.clear();
        return re;
    }
    static LinkedList<Integer> ranked = new LinkedList<>();
    public static void lastrank(TreeNode root,int k){
        if(root == null) return;
        lastrank(root.right,k);
        if(ranked.size() == k) return;
        ranked.add(root.val);
        lastrank(root.left,k);
    }
}

剑指 Offer 55 - I. 二叉树的深度 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @description: 二叉树的深度
 * 构造一个辅助函数findMaxDepth，传入节点和当前层数，然后递归调用findMaxDepth，比较左右子树中深度较大的那个。
 * @author: Huang Zhiwei
 * @time: 2023/5/1 23:26
 */
public class Offer55_1 {
    public static void main(String[] args) {
        String input ="5 3 6 2 4 null null 1";
        TreeNode out = deserialize(input);
        System.out.println(maxDepth(out));
    }
    public static int maxDepth(TreeNode root) {
        return findMaxDepth(root,0);
    }
    public static int findMaxDepth(TreeNode node,int layer){
        if(node != null){
            layer +=1;
        }else return layer;
        return Math.max(findMaxDepth(node.left,layer),findMaxDepth(node.right,layer));
    }
}

剑指 Offer 55 - II. 平衡二叉树 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @description: 平衡二叉树
 * 本题解法抄自leetcode官方题解，自己的做法由于平衡二叉树的理解出错了，所以出现了根本性错误
 * 自顶向下的递归，类似于二叉树的前序遍历
 * @author: Huang Zhiwei
 * @time: 2023/5/2 0:04
 */
public class Offer55_2new {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

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

/**
 * @description: 平衡二叉树
 * [1,2,2,3,3,3,3,4,4,4,4,4,4,null,null,5,5]
 * @author: Huang Zhiwei
 * @time: 2023/5/1 23:38
 */
public class Offer55_2 {
    public static void main(String[] args) {
        String input ="1 2 2 3 3 3 3 4 4 4 4 4 4 null null 5 5";
        TreeNode out = deserialize(input);
        System.out.println(isBalanced(out));
    }
    public static boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return balanceHelper(root,0,0);
    }
    static int min = Integer.MAX_VALUE;
    public static boolean balanceHelper(TreeNode node,int temp,int max){
        //层数差大于等于2就返回false
        if(max - min >=2) return false;
        //第一次出现null时，就固定下min的层数值
        if(node.right == null || node.left == null) {
            min = Math.min(min,temp);
        }
        if(node.right == null && node.left == null){
            return max - min < 2;
        }
        boolean right = true;
        boolean left = true;
        if(node.right != null){
            right = balanceHelper(node.right,temp+1,max+1);
        }
        if(node.left != null){
            left = balanceHelper(node.left,temp+1,max+1);
        }
        return right&&left;
    }
}

剑指 Offer 56 - I. 数组中数字出现的次数

剑指 Offer 56 - II. 数组中数字出现的次数 II

剑指 Offer 57. 和为s的两个数字 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @description: 和为s的两个数字
 * 经典两数之和问题，使用哈希表，遍历一次即可
 * @author: Huang Zhiwei
 * @time: 2023/5/2 15:50
 */
public class Offer57_1 {
    public static void main(String[] args) {
        int[] inputs = {10,26,30,31,47,60};
        System.out.println(Arrays.toString(twoSum(inputs, 40)));
    }
    public static int[] twoSum(int[] nums, int target) {
        HashSet<Integer> set = new HashSet<>();
        for(int x:nums){
            if(set.contains(x)){
                return new int[]{x,target-x};
            }else {
                set.add(target-x);
            }
        }
        return null;
    }
}

剑指 Offer 57 - II. 和为s的连续正数序列 

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
/**
 * @description: 和为s的连续正数序列
 * 暴力法，终止条件是i<=target/2和j<=target/2+1；其中类型转换是一个比较麻烦的问题
 * @author: Huang Zhiwei
 * @time: 2023/5/2 15:58
 */
public class Offer57_2 {
    public static void main(String[] args) {
        int[] inputs = {10,26,30,31,47,60};
        System.out.println(Arrays.toString(findContinuousSequence(9)));
    }
    public static int[][] findContinuousSequence(int target) {
        List<Integer[]> ans = new ArrayList<>();
        int sum = 0;
        for(int i = 1;i<=target/2;i++){
            sum = i;
            for(int j = i+1;j<=target/2+1;j++){
                sum+=j;
                if(sum == target){
                    Integer[] innerans = new Integer[j-i+1];
                    for(int u = 0;u<innerans.length;u++){
                        innerans[u] = i+u;
                    }
                    ans.add(innerans);
                }else if(sum > target){
                    break;
                }
            }
        }
        int[][] re = new int[ans.size()][];
        int z= 0;
        for(Integer[] x:ans){
            re[z++] = Arrays.stream(x).mapToInt(Integer::valueOf).toArray();
        }
        return re;
    }
}

剑指 Offer 58 - I. 翻转单词顺序 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @description: 翻转单词顺序
 * 先将首尾空格去除，再构造StringBuilder，最后输出的时候去除尾部空格
 * @author: Huang Zhiwei
 * @time: 2023/5/2 16:44
 */
public class Offer58_1 {
    public static void main(String[] args) {
        String input = "a good   example";
        System.out.println(reverseWords(input));
    }
    public static String reverseWords(String s) {
        s = s.trim();
        String[] sString = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = sString.length-1;i>=0;i--){
            if(sString[i].equals("")) continue;
            sb.append(sString[i]+" ");
        }
        return sb.toString().trim();
    }
}

剑指 Offer 58 - II. 左旋转字符串 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @description: 左旋转字符串
 * StringBuilder构造字符串，非常简单
 * @author: Huang Zhiwei
 * @time: 2023/5/2 16:53
 */
public class Offer58_2 {
    public static void main(String[] args) {
        String s = "abcdefg";
        System.out.println(reverseLeftWords(s, 2));
    }
    public static String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder(s.substring(n));
        sb.append(s.substring(0,n));
        return sb.toString();
    }
}

剑指 Offer 59 - I. 滑动窗口的最大值

剑指 Offer 59 - II. 队列的最大值

剑指 Offer 60. n个骰子的点数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * @description: 扑克牌中的顺子
 * 本体难度很低，就是在条件判断中需要搞清楚一些
 * 用一个赖子计数器计数0；然后从count+1位置开始遍历，出现相同的返回false，赖子小于0返回false，没赖子可用且相差大于1返回false；
 * @author: Huang Zhiwei
 * @time: 2023/5/2 17:04
 */
public class Offer61 {
    public static void main(String[] args) {
//        int[] inputs = {3,10,8,9,10};
        int[] inputs = {9,0,6,0,10};
        System.out.println(isStraight(inputs));
    }
    public static boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        //赖子计数器
        int count = 0;
        for(int x:nums){
            count = x == 0 ? count+1:count;
        }
        if(count == 5)return true;
        int former = nums[count];
        for(int i = count+1;i<nums.length;i++){
            if(nums[i] == former+1){
                former = nums[i];
            }else if(nums[i] == former){
                return false;
            }else if(count>0) {
                count = count - (nums[i] - former)+1;
                if (count < 0) {
                    return false;
                }
                former = nums[i];
            }else {
                return false;
            }
        }
        return true;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @description: 圆圈中最后剩下的数字
 * 基本约瑟夫环问题，由于不能使用链表，用数组模拟这个队列；用到了数学解法，看看就好了，一般出现的问题都是这个的变体
 * @author: Huang Zhiwei
 * @time: 2023/5/2 16:56
 */
public class Offer62 {
    public static void main(String[] args) {

    }
    public int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i) {
            f = (m + f) % i;
        }
        return f;
    }
}

剑指 Offer 63. 股票的最大利润 

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
/**
 * @description:
 * @author: Huang Zhiwei
 * @time: 2023/6/13 13:39
 */
public class Offer63 {
    public static void main(String[] args) {
        int[] input = {5,6};
        System.out.println(getMaxDiff(input, 2));
    }
    public static int getMaxDiff(int[] A, int n) {
        int max_diff = 0;
        int min_val = A[0];
        for (int i = 1; i < n; i++) {
            int diff = A[i] - min_val;
            max_diff = Math.max(max_diff, diff);
            min_val = Math.min(min_val, A[i]);
        }
        return max_diff;
    }
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 快慢指针找到链表的中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 将链表的后半部分压入栈中
        Stack<Integer> stack = new Stack<>();
        ListNode cur = slow.next;
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }

        // 遍历链表的前半部分，同时从栈中弹出元素进行比较
        cur = head;
        while (!stack.isEmpty()) {
            if (cur.val != stack.pop()) {
                return false;
            }
            cur = cur.next;
        }

        return true;
    }
}

剑指 Offer 64. 求1+2+…+n

剑指 Offer 65. 不用加减乘除做加法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @description: 不用加减乘除做加法
 * 位运算，没啥意思，自己写肯定还是很捞的写法
 * @author: Huang Zhiwei
 * @time: 2023/5/2 17:23
 */
public class Offer65 {
    public int add(int a, int b) {
        while (b != 0) {
            //进位
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

剑指 Offer 66. 构建乘积数组

剑指 Offer 67. 把字符串转换成整数

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @description: 二叉搜索树的最近公共祖先
 * 一次遍历，假设要找a和b的公共祖先，对于遍历到的当前节点c，考虑以下三种判断条件 ：
 * c>a&&c>b:应当向c的左子树搜索
 * c<a&&c<b:应当向c的右子树搜索
 * 其他:c就是公共祖先
 * @author: Huang Zhiwei
 * @time: 2023/5/2 0:06
 */
public class Offer68_1 {
    public static void main(String[] args) {

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

剑指 Offer 68 - II. 二叉树的最近公共祖先 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @description: 二叉树的最近公共祖先
 * 对于不是二叉搜索树的情况，同样可以使用递归
 * 题解摘自leetcode评论区
 * @author: Huang Zhiwei
 * @time: 2023/5/2 13:30
 */
public class Offer68_2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        如果根节点为空直接返回null
        if(root == null){
            return null;
        }
//        第一个找到的节点为q说明q比p深度小,位于p上方,直接返回q
        if(root.val == q.val){
            return q;
//        第一个找到的节点为p说明p比q深度小,位于q上方,直接返回p
        }else if(root.val == p.val){
            return p;
        }else {
//            left和right分别表示向左右递归得到的结果
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right = lowestCommonAncestor(root.right,p,q);
//            如果left和right都不为空说明两个节点在根节点左右,直接返回根节点
            if(left != null && right != null){
                return root;
//            如果左边递归为空说明两个节点都在右边,且right节点一定是p,q的根节点,直接返回right节点
            }else if(left == null){
                return right;
            }else {
//            如果右递归为空说明两个节点都在左边,且left节点一定是p,q的根节点,直接返回left节点
                return left;
            }
        }
    }
}
  • 标题: 力扣学习录03--剑指Offer刷题记录（下）
  • 作者: Huang Zhiwei
  • 创建于: 2023-06-02 22:16:54
  • 更新于: 2023-09-02 23:41:40
  • 链接: https://huangzhw0221.github.io/2023/06/02/Leetcode03/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
 评论
此页目录
力扣学习录03--剑指Offer刷题记录（下）
  1. 剑指 Offer 31. 栈的压入、弹出序列
  2. 剑指 Offer 32 - I. 从上到下打印二叉树
  3. 剑指 Offer 32 - II. 从上到下打印二叉树 II
  4. 剑指 Offer 32 - III. 从上到下打印二叉树 III
  5. 剑指 Offer 33. 二叉搜索树的后序遍历序列
  6. 剑指 Offer 34. 二叉树中和为某一值的路径
  7. 剑指 Offer 35. 复杂链表的复制
  8. 剑指 Offer 36. 二叉搜索树与双向链表
  9. 剑指 Offer 37. 序列化二叉树
  10. 剑指 Offer 38. 字符串的排列
  11. 剑指 Offer 39. 数组中出现次数超过一半的数字
  12. 剑指 Offer 40. 最小的k个数
  13. 剑指 Offer 41. 数据流中的中位数
  14. 剑指 Offer 42. 连续子数组的最大和
  15. 剑指 Offer 43. 1～n 整数中 1 出现的次数
  16. 剑指 Offer 44. 数字序列中某一位的数字
  17. 剑指 Offer 45. 把数组排成最小的数
  18. 剑指 Offer 46. 把数字翻译成字符串
  19. 剑指 Offer 47. 礼物的最大价值
  20. 剑指 Offer 48. 最长不含重复字符的子字符串
  21. 剑指 Offer 49. 丑数
  22. 剑指 Offer 50. 第一个只出现一次的字符
  23. 剑指 Offer 51. 数组中的逆序对
  24. 剑指 Offer 52. 两个链表的第一个公共节点
  25. 剑指 Offer 53 - I. 在排序数组中查找数字 I
  26. 剑指 Offer 53 - II. 0～n-1中缺失的数字
  27. 剑指 Offer 54. 二叉搜索树的第k大节点
  28. 剑指 Offer 55 - I. 二叉树的深度
  29. 剑指 Offer 55 - II. 平衡二叉树
  30. 剑指 Offer 56 - I. 数组中数字出现的次数
  31. 剑指 Offer 56 - II. 数组中数字出现的次数 II
  32. 剑指 Offer 57. 和为s的两个数字
  33. 剑指 Offer 57 - II. 和为s的连续正数序列
  34. 剑指 Offer 58 - I. 翻转单词顺序
  35. 剑指 Offer 58 - II. 左旋转字符串
  36. 剑指 Offer 59 - I. 滑动窗口的最大值
  37. 剑指 Offer 59 - II. 队列的最大值
  38. 剑指 Offer 60. n个骰子的点数
  39. 剑指 Offer 61. 扑克牌中的顺子
  40. 剑指 Offer 62. 圆圈中最后剩下的数字
  41. 剑指 Offer 63. 股票的最大利润
  42. 剑指 Offer 64. 求1+2+…+n
  43. 剑指 Offer 65. 不用加减乘除做加法
  44. 剑指 Offer 66. 构建乘积数组
  45. 剑指 Offer 67. 把字符串转换成整数
  46. 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
  47. 剑指 Offer 68 - II. 二叉树的最近公共祖先