algorithm

牛客—剑指Offer

宋正兵 更新 on 2021-08-25

剑指Offer_在线编程+题解_牛客题霸_牛客网 (nowcoder.com)

JZ1 二维数组中的查找

题目大意：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

左下开始找，对于左下角的元素 m，m 已经是该行的最小值，该列的最大值

  • target > m ==》 m 是该列最大的元素，想要更大只能考虑右边一列
  • target < m ==》 m 是该行最小的元素，想要更小只能考虑上边一行

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public boolean Find(int target, int [][] array) {
        int m = array.length - 1, n = 0;
        if (m == 0 || target > array[m][array[0].length - 1]) {
            return false;
        }
        // 左下开始找，对于左下角的元素m，m已经是该行的最小值，该列的最大值
        // target > m ==》 m是该列最大的元素，想要更大只能考虑右边一列
        // target < m ==》 m是该行最小的元素，想要更小只能考虑上边一行
        while (m >= 0 && n < array[0].length) {
            if (target == array[m][n]) {
                return true;
            } else if (target > array[m][n]) {
                n++;
            } else {
                m--;
            }
        }
        return false;
    }
}

JZ2 替换空格

题目大意：

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：

利用 StringBuffer 来拼接，遇上空格就替换成 “%20”。

代码：

1
2
3
4
5
6
7
8
9
10
import java.util.*;
public class Solution {
    public String replaceSpace (String s) {
        StringBuffer sb = new StringBuffer();
        for (char ch : s.toCharArray()) {
            sb.append(ch == ' '? "%20" : ch);
        }
        return sb.toString();
    }
}

JZ3 从尾到头打印链表

题目大意：

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思路：

翻转链表 + List 插入：翻转链表然后再插入到 ArrayList 当中。之所以不用 list.add(0, listNode) 是因为 ArrayList 插入的时间复杂度是 $O(n)$，n 个元素插入就是 $O(n^{2})$，翻转链表后再插入会快些。

方法二：类似于二叉树的中序遍历时找到第一个节点，进行递归。

代码：

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        listNode = reverse(listNode);
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
    public ListNode reverse(ListNode listNode) {
        ListNode headNode = new ListNode(0);
        while (listNode != null) {
            ListNode nextNode = listNode.next;
            listNode.next = headNode.next;
            headNode.next = listNode;
            listNode = nextNode;
        }
        return headNode.next;
    }
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> resList = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode != null) {
            printListFromTailToHead(listNode.next);
            resList.add(listNode.val);
        }
        return resList;
    }
}

JZ4 重建二叉树

题目大意：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：

模拟我们根据前序和中序构建二叉树的过程。

根据前序遍历和中序遍历重建二叉树：
1、根据前序序列第一个结点确定根结点
2、根据根结点在中序序列中的位置分割出左右两个子序列
3、对左子树和右子树分别递归使用同样的方法继续分解

前序遍历的顺序就是我们从中序遍历中每次找到当前子树根节点的顺序 1->2->3…
中序遍历中被我们每次选择的根节点划分为 [左子树, root, 右子树]
同样的 左子树 和 右子树 当中也符合上述规则
于是递归的进行

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (pre[0] == in[i]) {
                // 左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return root;
    }
}

JZ5 用两个栈实现队列

题目大意：

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：

  • 入队：都往 stack1 中入栈
  • 出队：
    • 如果 stack2 不为空，从 stack2 中出栈
    • 如果 stack2 为空，将 stack1 全部迁移到 stack2，再从 stack2 出栈

即最先入队的元素一定会放在 stack2 的栈顶或者 stack1 的栈底，最后入队的元素一定会在 stack1 的栈顶或者是 stack2 的栈底。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

JZ6 旋转数组的最小数字

题目大意：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：

二分。我们要找最小的数字，且数组是升序的，左边小右边大，所以选择和右边的边界比较，当然左边也行，只不过右边方便些。

  • array[mid] > array[right]：最小值在 (mid,right] 内出现，所以 left = mid + 1；
  • array[mid] < array[right]：最小值在 [left,mid] 内出现，注意这里的 array[mid] 也有可能是最小值，所以 right = mid；
  • array[mid] == array[right]：因为是升序的，右边的会大一些，所以直接去掉 array[right] 来排除一个可能的选项，继续进行二分查找。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int mid = 0, left = 0, right = array.length - 1;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (array[mid] > array[right]) {
                left = mid + 1;
            } else if (array[mid] < array[right]) {
                right = mid;
            } else {
                right--;
            }
        }
        return array[left];
    }
}

JZ7 斐波那契数列

没什么好说的。

代码：

1
2
3
4
5
6
7
8
public class Solution {
    public int Fibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

JZ8 跳台阶

题目大意：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

代码：

1
2
3
4
5
6
7
8
9
public class Solution {
    public int jumpFloor(int target) {
        // f(n) = f(n-1) + f(n-2)
        if (target == 1 || target == 2) {
            return target;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}

优化：因为只用到了上一个状态 f(n-1) 和上上一个状态 f(n-2)，所以可以把递归修改为空间复杂度为 $O(1)$ 的递推。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int jumpFloor(int target) {
        // f(n) = f(n-1) + f(n-2)
        int a = 1, b = 1;
        for (int i = 2; i <= target; i++) {
            // f(i) = f(i-1) + f(i-2)
            a = a + b;
            // f(i-1) = f(i) - f(i-2)
            b = a - b;
        }
        return a;
    }
}

JZ9 变态跳台阶

题目大意：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路：

对于第 n 级的台阶，跳法有 n+1 种，即从第 0 阶跳 n 级台阶，从第 1 阶跳 n-1 级台阶……，于是就有 $f(n) = \sum\limits_{i = 0}^{n-1}f(i)$ ，如代码一所示。

优化 $f(0)=1$，$f(1)=f(0)=1$，$f(2)=f(0)+f(1)=2$，$f(3)=f(0)+f(1)+f(2)=2*f(2)=4$……列出多项后发现，这其实是一个等比数列，有 $f(n)=2^{n-1}$，于是可以优化为代码二。

代码：

代码一

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int jumpFloorII(int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j];
            }
        }
        return dp[target];
    }
}

代码二

1
2
3
4
5
public class Solution {
    public int jumpFloorII(int target) {
        return 1 << (target - 1);
    }
}

JZ10 矩形覆盖

题目大意：

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

思路：

扩充矩形的方法一共有两种，1）竖着摆放一个，矩形增加 2*1；2）横着摆放两个，矩形增加 2*2。假设我们现在要覆盖一个 2*n 的矩形，有多少种方法？

对于第一种扩充方法，需要从 2*(n-1) 的矩形增加一个竖着摆放的小矩形；对于第二种扩充方法，需要从 2*(n-2) 的矩形增加两个横着摆放的小矩形。

于是覆盖一个 2*n 的矩形的方法数 $f(n)=f(n-1) + f(n-2)$

代码：

1
2
3
4
5
6
7
8
public class Solution {
    public int rectCover(int target) {
        if (target < 4) {
            return target;
        }
        return rectCover(target - 1) + rectCover(target - 2);
    }
}

JZ11 二进制中1的个数

题目大意：

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

思路：

每次都通过位运算移除末尾的最后一个 0，统计操作的次数，直到这个数为 0，操作的次数就是 1 的个数。

代码：

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

JZ12 数值的整数次方

题目大意：

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。

思路：

快速幂的思路。先将 exponent 转换为正数，并记录原始的正负状态 isNegative。然后快速幂的思想是：如果指数是偶数 2n，那么就分解成 $num^{n} num^{n}$，如果指数是奇数，那么就分解成 $num^{n-1}num$，转换为偶数的情况处理。最后根据 isNegative 的值判断是否需要把结果写成 $\frac{1}{res}$。

代码：

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
public class Solution {
    public double Power(double base, int exponent) {
        // 快速幂
        boolean isNegative = false;
        // exponent 转换为正数的原因为：
        // 在 exponent 为奇数时，负数减1，越减越小了
        if (exponent < 0) {
            isNegative = true;
            exponent = - exponent;
        }
        double res = getPower(base, exponent);
        return isNegative ? 1 / res : res;
    }
    public double getPower(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent % 2 == 0) {
            double temp = getPower(base, exponent / 2);
            return temp * temp;
        } else {
            return getPower(base, exponent - 1) * base;
        }
    }
}

JZ13 调整数组顺序使奇数位于偶数前面

题目大意：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：

冒泡排序，将判断条件从大小换成奇偶

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Solution {
    public int[] reOrderArray (int[] array) {
        // 冒泡
        int n = array.length;
        boolean changed = true;
        for (int i = n - 1; i > 0 && changed; i--) {
            changed = false;
            for (int j = 0; j < array.length - 1; j++) {
                if (array[j] % 2 == 0 && array[j + 1] % 2 == 1) {
                    changed = true;
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }
}

狗日的牛客改判题条件了，冒泡过不了，换成将奇数往前移，偶数放到新建数组 odd[] 中，然后再将 odd[] 数组中的内容复制到 array[] 中奇数序列的后面。

JZ14 链表中倒数第k个结点

题目大意：

输入一个链表，输出该链表中倒数第k个结点。

如果该链表长度小于k，请返回空。

思路：

快慢指针。如果输出倒数第 1 个结点，则快指针应该比慢指针快一个结点，这样当快指针指向 null 的时候，慢指针刚好指向最后一个结点。那么可以划分为以下几步：

  • 快指针先走 k 步
  • 快慢指针同时往后走，直到快指针为 null
  • 返回慢指针

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode slowNode = pHead, fastNode = pHead;
        while (fastNode != null && k > 0) {
            k--;
            fastNode = fastNode.next;
        }
        while (fastNode != null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        return k > 0 ? null : slowNode;
    }
}

JZ15 反转链表

题目大意：

输入一个链表，反转链表后，输出新链表的表头。

思路：

头插，没啥好说的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode dummyNode = new ListNode(0);
        // 头插
        while (head != null) {
            ListNode next = head.next;
            head.next = dummyNode.next;
            dummyNode.next = head;
            head = next;
        }
        return dummyNode.next;
    }
}

JZ16 合并两个排序的链表

题目大意：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode dummyNode = new ListNode(0);
        ListNode curNode = dummyNode;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                curNode.next = list1;
                list1 = list1.next;
            } else {
                curNode.next = list2;
                list2 = list2.next;
            }
            curNode = curNode.next;
        }
        curNode.next = (list1 == null ? list2 : list1);
        return dummyNode.next;
    }
}

JZ17 树的子结构

题目大意：

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：

遍历二叉树 A，以每一个节点作为子树的根节点和二叉树 B 进行比较 isSubTree(root1, root2)，判断以当前节点为根节点的子树和二叉树 B 是否相同。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        // 空树不是任意一个树的子结构 || root1为空那么肯定不包含root2结构
        if (root2 == null || root1 == null) {
            return false;
        }
        return isSubTree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }
    public boolean isSubTree(TreeNode root1, TreeNode root2) {
        // root2遍历到了空节点，不用管root1此时空不空
        if (root2 == null) {
            return true;
        }
        // root1为空，root2不为空，肯定不是
        if (root1 == null) {
            return false;
        }
        return root1.val == root2.val &&
            isSubTree(root1.left, root2.left) &&
            isSubTree(root1.right, root2.right);
    }
}

JZ18 二叉树的镜像

题目大意：

操作给定的二叉树，将其变换为源二叉树的镜像。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;
public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot != null) {
            TreeNode tempNode = pRoot.left;
            pRoot.left = pRoot.right;
            pRoot.right = tempNode;
            Mirror(pRoot.left);
            Mirror(pRoot.right);
        }
        return pRoot;
    }
}

JZ19 顺时针打印矩阵

题目大意：

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字.

思路：

设置上下左右边界，按照顺序去打印，没打印一行或者一列则把相应的边界挪动一位。

代码：

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
import java.util.*;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> resList = new ArrayList<>();
        int left = 0, right = matrix[0].length - 1, up = 0, down = matrix.length - 1;
        while (true) {
            // 顶部那行
            for (int i = left; i <= right; i++) {
                resList.add(matrix[up][i]);
            }
            up++;
            if (up > down) {
                break;
            }
            // 右边那列
            for (int i = up; i <= down; i++) {
                resList.add(matrix[i][right]);
            }
            right--;
            if (left > right) {
                break;
            }
            // 下边那行
            for (int i = right;i >= left; i--) {
                resList.add(matrix[down][i]);
            }
            down--;
            if (up > down) {
                break;
            }
            // 左边那列
            for (int i = down; i >= up; i--) {
                resList.add(matrix[i][left]);
            }
            left++;
            if (left > right) {
                break;
            }
        }
        return resList;
    }
}

JZ20 包含min函数的栈

题目大意：

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。

思路：

stack1 正常入栈出栈，stack2 在 stack1 入栈的时候陪着入栈最小元素。这样在同样深度的时候就能直接从 stack2 中拿到最小元素。

也可以用内部类 Node (int val, int minVal)，让每一个元素不仅存储原来的值，还存储从自己到最先入队的元素中的最小值。

代码：

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
import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    public void push(int node) {
        stack1.push(node);
        if(stack2.isEmpty()) {
            stack2.push(node);
        } else {
            if (node < stack2.peek()) {
                stack2.push(node);
            } else {
                stack2.push(stack2.peek());
            }
        }
    }  
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    public int top() {
        return stack1.peek();
    }  
    public int min() {
        return stack2.peek();
    }
}

JZ21 栈的压入、弹出序列

题目大意：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

思路：

直接新建一个栈去模拟这个过程，如果栈不为空且栈顶元素等于要出栈的元素，那么出栈。最后判断栈是否为空即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int num : pushA) {
            stack.push(num);
            while (!stack.isEmpty() && stack.peek() == popA[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

JZ22 从上往下打印二叉树

题目大意：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：

层序遍历。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            resList.add(curNode.val);
            if (curNode.left != null) {
                queue.offer(curNode.left);
            }
            if (curNode.right != null) {
                queue.offer(curNode.right);
            }
        }
        return resList;
    }
}

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

题目大意：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回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
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return isBST(sequence, 0, sequence.length - 1);
    }
    public boolean isBST(int[] seq, int start, int end) {
        if (start >= end) {
            return true;
        }
        int root = seq[end];
        int split = start;
        // 找到左右子树分界
        for (; split < end && seq[split] < root; split++);
        // 右子树中若有小于根节点的，直接返回false
        for (int i = split; i < end; i++) {
            if (seq[i] < root) {
                return false;
            }
        }
        return isBST(seq, start, split - 1) && isBST(seq, split, end - 1);
    }
}

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

题目大意：

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路：

DFS 思想，从根节点开始往下搜索，每遍历一个节点就将其加入路径当中。如果当前节点是叶子节点，则检查当前路径和是否和 targer 相等，相等则找到一条路径。

需要注意的地方：如果按照 if (root == null) 的时候再去检查路径和是否和 target 相等，不能及时的从当前叶子节点退出，会进入叶子节点的左右子节点，造成两次判断生效加入 resList 路径集合操作，导致答案重复。

代码：

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
import java.util.ArrayList;
public class Solution {
    ArrayList<ArrayList<Integer>> resList = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> tempList = new ArrayList<>();
    int target = 0;
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null) {
            return resList;
        }
        this.target = target;
        checkPath(root, 0);
        return resList;
    }
    
    public void checkPath(TreeNode root, int sum) {
        if (root.left == null && root.right == null) {
            if (sum + root.val == target) {
                tempList.add(root.val);
                resList.add(new ArrayList<>(tempList));
                tempList.remove(tempList.size() - 1);
            }
            return;
        }
        // 剪枝，还没走到叶子节点就大于targer，继续走只会让sum更大
        if (sum + root.val > target) {
            return;
        }
        tempList.add(root.val);
        if (root.left != null) {
            checkPath(root.left, sum + root.val);
        }
        if (root.right != null) {
            checkPath(root.right, sum + root.val);
        }
        tempList.remove(tempList.size() - 1);
    }
}

JZ25 复杂链表的复制

题目大意：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点

思路：

分为两步：

  1. 【复制】为所有节点创建备份，存到 map 中，此时复制出来的节点的 next 和 random 字段都为 null

  2. 【完善链表结构】根据原始链表的结构，构建复制出来的新链表的结构。

    比如原始链表的节点 A，对应复制出来的节点 A*。A 的next是 B，random 是 C，那么对应的 A* 的 next 是 B*，random 是 C*。如何找到 B* 和 C* 呢，就是通过 map 来获取，因为在第一步的时候就把每个节点对应的复制节点存放到了 map 当中。

代码：

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
import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode curNode = pHead;
        // 将所有值都存入map，每一个结点都被new了【复制】
        while (curNode != null) {
            map.put(curNode, new RandomListNode(curNode.label));
            curNode = curNode.next;
        }
        // 完善链表的结构
        RandomListNode target = new RandomListNode(pHead.label);
        curNode = pHead;
        RandomListNode p = target;
        // 移动 p 和 curNode 来完善链表的结构
        while (curNode != null) {
            p.next = map.get(curNode.next);
            p.random = map.get(curNode.random);
            curNode = curNode.next;
            p = p.next;
        }
        return target;
    }
}

JZ26 二叉搜索树与双向链表

题目大意：

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

思路：

二叉搜索树的一个性质之一是：中序遍历的顺序是有序的，所以我们可以明确的是这道题目需要用到中序遍历。将节点的左指针指向中序遍历的前一个节点，右指针指向中序遍历的后一个节点。

我们可以利用一个 preNode 节点来完成这件事情。当我们遍历到某个节点的时候，它的左指针应该指向它的前一个节点 preNode，同时将 preNode 节点的右指针指向当前节点，完成前一个节点的左右指针调整。等遍历下一个节点的时候，再来完善当前节点的右指针。所以需要把当前节点左右 preNode 节点，去处理下一个节点。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    TreeNode targetNode = null;
    TreeNode preNode = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Convert(pRootOfTree.left);
        if (targetNode == null) {
            targetNode = pRootOfTree;
        } else {
            preNode.right = pRootOfTree;
            pRootOfTree.left = preNode;
        }
        preNode = pRootOfTree;
        Convert(pRootOfTree.right);
        return targetNode;
    }
}

JZ27 字符串的排列

题目大意：

输入一个字符串,按字典序打印出该字符串中字符的所有排列

思路：【排列树】

从上图可以看到，如果我们先固定 A 不懂，然后交换 B 与 C，可以得到 ABC 和 ACB，同样的对于 B、C 是同样的道理。

代码：

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
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       ArrayList<String> resList = new ArrayList<>();
        if (str != null) {
            char[] arr = str.toCharArray();
            backtrace(arr, 0, resList);
            Collections.sort(resList);
        }
        return resList;
    }
    public void backtrace(char[] arr, int t, ArrayList<String> resList) {
        if (t >= arr.length) {
            String tempStr = String.copyValueOf(arr);
            if (!resList.contains(tempStr)) {
                resList.add(tempStr);
            }
            return;
        }
        for (int i = t; i < arr.length; i++) {
            swap(arr, t, i);
            backtrace(arr, t + 1, resList);
            swap(arr, t, i);
        }
    }
    public void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

JZ28 数组中出现次数超过一半的数字

题目大意：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

思路：

  • 从前往后遍历，记录当前候选数字 condition 出现的次数 count，相同则出现次数 +1，不相同则 -1。
  • 当次数 count 被减到 0 时，表示从 0 到当前元素的区间内，候选数字 condition 不是众数。
  • 最后留下来的候选数字 condition 有可能是众数，进行验证

代码：

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
import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        // 该方法是基于如果存在众数，那么遍历数组之后众数k出现的次数一定是大于数组长度一半的
        // 从前往后遍历，记录当前候选数字condition出现的次数count
        // 相同则出现次数+1，不相同则-1
        // 当次数count被减到0时，表示从0到当前元素的区间内，候选数字condition不是众数
        // 最后留下来的候选数字condition有可能是众数，进行验证
        int condition = -1, count = 0;
        for (int num : array) {
            if (count == 0) {
                condition = num;
            }
            if (num == condition) {
                count++;
            } else {
                count--;
            }
        }
        // 验证
        count = 0;
        for (int num : array) {
            if (num == condition) {
                count++;
            }
        }
        return count > array.length / 2 ? condition : 0;
    }
}

▲JZ29 最小的k个数

题目大意：

给定一个数组，找出其中最小的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
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (k <= input.length) {
        	heapSort(input, k, resList);
        }
        return resList;
    }
    
    public void heapSort(int[] arr, int k, ArrayList<Integer> resList) {
        // 构建堆，从第一个非叶子节点开始，从下到上，从右往左
        for (int i = arr.length / 2 -1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        // 调整堆结构，并加入结果集
        for (int i = 0; i < k; i++) {
            resList.add(arr[0]);
            swap(arr, 0, arr.length - i - 1);
            adjustHeap(arr, 0, arr.length - i - 1);
        }
    }
    
    public void adjustHeap(int[] arr, int i, int length) {
        // 取出当前元素
        int temp = arr[i];
        // 从第i个节点的左孩子节点开始
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            // 右孩子更小则指向右孩子节点
            if (k + 1 < length && arr[k] > arr[k + 1]) {
                k++;
            }
            // 如果子节点小于父节点（当前元素），则将子节点赋值给父节点
            // 子节点最后由temp来填充
            // 【从这里能看出来是小根堆】
            if (arr[k] < temp) {
                arr[i] = arr[k];
                i = k;
            }
        }
        // 将temp放置到最终的位置
        arr[i] = temp;
    }
    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

JZ30 连续子数组的最大和

题目大意：

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

思路：

正数负数都有的情况下，连续子数组相加小于零的时候，一定不会是最大子数组。此时可以直接将 sum 清零，开始重新计算子数组的和。

但是当数组元素全是负数的时候该方法就存在问题，得到的结果为 0。解决的办法是 0 + 当前数字，然后先与最大子数组和比较，再去判断小于零则清零。这样做能够在求和的同时，把当前为负数的元素拎出来单独比较。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int sum = 0, maxSum = array[0];
        for (int num : array) {
            sum += num;
            if (sum > maxSum) {
                maxSum = sum;
            }
            if (sum <= 0) {
                sum = 0;
            }
        }
        return maxSum;
    }
}

JZ31 整数中1出现的次数（从1到n整数中1出现的次数）

题目大意：

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数

思路：

面试题43. 1～n 整数中 1 出现的次数（清晰图解） - 1～n 整数中 1 出现的次数 - 力扣（LeetCode） (leetcode-cn.com)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        // https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
        int oneFreq = 0;
        for (int digit = 1; digit <= n; digit *= 10) {
            int cur = n / digit % 10;
            int high = n / digit / 10;
            int low = n % digit;
            if (cur == 0) {
                oneFreq += high * digit;
            } else if (cur == 1) {
                oneFreq += high * digit + low + 1;
            } else {
                oneFreq += (high + 1) * digit;
            }
        }
        return oneFreq;
    }
}

JZ32 把数组排成最小的数

题目大意：

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

思路：

把问题转化为：如何给这个数组排序，使其看做一个数字的时候最小。

两个字符串 s1, s2，将它们拼接起来看 s1+s2 和 s2+s1 哪个大，如果 s1+s2 大，那么说明 s2 应该放前面。按照我们定义的标准排好序，然后依次拼接起来就是答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                int s1 = Integer.valueOf(numbers[i]+ "" +numbers[j]);
                int s2 = Integer.valueOf(numbers[j]+ "" +numbers[i]);
                if (s1 > s2) {
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
        // 拼接
        String res = new String("");
        for (int num : numbers) {
            res += num;
        }
        return res;
    }
}

▲JZ33 丑数

题目大意：

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路：

首先从丑数的定义我们知道，一个丑数的因子只有 2，3，5，那么丑数 $p = 2 ^ x 3 ^ y 5 ^ z$，换句话说一个丑数一定由另一个丑数乘以 2 或者乘以 3 或者乘以 5 得到，那么我们从 1 开始乘以 2，3，5，就得到 2，3，5 三个丑数，在从这三个丑数出发乘以 2，3，5 就得到 4，6，10，6，9，15，10，15，25 九个丑数，我们发现这种方法得到重复的丑数，而且我们题目要求第 N 个丑数，这样的方法得到的丑数也是无序的。那么我们可以维护三个队列：

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
（1）丑数数组： 1
乘以2的队列：2
乘以3的队列：3
乘以5的队列：5
选择三个队列头最小的数2加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（2）丑数数组：1,2
乘以2的队列：4
乘以3的队列：3，6
乘以5的队列：5，10
选择三个队列头最小的数3加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（3）丑数数组：1,2,3
乘以2的队列：4,6
乘以3的队列：6,9
乘以5的队列：5,10,15
选择三个队列头里最小的数4加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（4）丑数数组：1,2,3,4
乘以2的队列：6，8
乘以3的队列：6,9,12
乘以5的队列：5,10,15,20
选择三个队列头里最小的数5加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（5）丑数数组：1,2,3,4,5
乘以2的队列：6,8,10，
乘以3的队列：6,9,12,15
乘以5的队列：10,15,20,25
选择三个队列头里最小的数6加入丑数数组，但我们发现，有两个队列头都为6，所以我们弹出两个队列头，同时将12,18,30放入三个队列；
……………………

疑问：

1.为什么分三个队列？

丑数数组里的数一定是有序的，因为我们是从丑数数组里的数乘以 2，3，5 选出的最小数，一定比以前未乘以 2，3，5 大，同时对于三个队列内部，按先后顺序乘以 2，3，5 分别放入，所以同一个队列内部也是有序的；

2.为什么比较三个队列头部最小的数放入丑数数组？

因为三个队列是有序的，所以取出三个头中最小的，等同于找到了三个队列所有数中最小的。

实现思路：

我们没有必要维护三个队列，只需要记录三个指针显示到达哪一步；“|” 表示指针，arr 表示丑数数组；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
（1）1
|2
|3
|5
目前指针指向0,0,0，队列头arr[0] * 2 = 2,  arr[0] * 3 = 3,  arr[0] * 5 = 5
（2）1 2
2 |4
|3 6
|5 10
目前指针指向1,0,0，队列头arr[1] * 2 = 4,  arr[0] * 3 = 3, arr[0] * 5 = 5
（3）1 2 3
2| 4 6
3 |6 9
|5 10 15
目前指针指向1,1,0，队列头arr[1] * 2 = 4,  arr[1] * 3 = 6, arr[0] * 5 = 5

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index <= 0) {
            return 0;
        }
        int p2 = 0, p3 = 0, p5 = 0; // 三个潜在成为最小丑数的位置
        int[] res = new int[index];
        res[0] = 1;
        for (int i = 1; i < index; i++) {
            // 找到该轮次最小的那个丑数
            res[i] = Math.min(res[p2] * 2, Math.min(res[p3] * 3, res[p5] * 5));
            if (res[i] == res[p2] * 2) {
                p2++;
            }
            if (res[i] == res[p3] * 3) {
                p3++;
            }
            if (res[i] == res[p5] * 5) {
                p5++;
            }
        }
        return res[index - 1];
    }
}

JZ34 第一个只出现一次的字符位置

题目大意：

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

思路：

已知 ASCII 码表字符一共有 128 个。那么我们可以维护一个 count[] 数组，用来记录字符串 str 中每个字符出现的次数。对于字符 ch 有：

  • count[ch] == 0，字符 ch 没有出现过；
  • count[ch] == 1，字符 ch 出现过 1 次；
  • count[ch] > 2，字符 ch 出现过多次。

于是我们在统计完字符串 str 中字符出现的次数后，在根据字符串 str 中字符出现的顺序去找到第一个只出现一次的字符的位置即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        // 0：没出现 1：出现过1次 >1：出现过多次
        int[] count = new int[128];
        int len = str.length();
        for (int i = 0; i < len; i++) {
            count[str.charAt(i)]++;
        }
        for (int i = 0; i < len; i++) {
            if (count[str.charAt(i)] == 1) {
                return i;
            }
        }
        return -1;
    }
}

▲JZ35 数组中的逆序对

题目大意：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。

思路：

利用归并排序的思想，递归划分整个区间为基本相等的左右区间。比如需要合并的两个有序区间为 [3, 4] 和 [1, 2]，在合并的过程中发现 $3 > 1$，说明 3 后面的所有数都是大于 1 的，对于 2 来讲同理。所以我们在合并的时候可以利用这个规则，假设合并有序区间 A 和有序区间 B，长度分别为 n 和 m，有：

  • A[i] < B[j]，说明没有逆序对发生。
  • A[i] > B[j]，说明 A[i...n] 都大于 B[j]，构成逆序对，数量为 n - i + 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
42
43
44
45
public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        mergeSort(array, 0, array.length - 1);
        return count;
    }
    
    public void mergeSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(array, start, mid);
        mergeSort(array, mid + 1, end);
        merge(array, start, end, mid);
    }
    
    public void merge(int[] array, int start, int end, int mid) {
        int[] temp = new int[end - start + 1];
        int p1 = start, p2 = mid + 1, k = 0;
        while (p1 <= mid && p2 <= end) {
            if (array[p1] <= array[p2]) {
                // 前面的元素小于后面的元素，不能构成逆序对
                temp[k++] = array[p1++];
            } else {
                // 前面的元素大于后面的元素
                // 那么前面的元素以及之后的元素（[p1, mid]）都能和p2构成逆序对
                temp[k++] = array[p2++];
                count = (count + (mid - p1 + 1)) % 1000000007;
            }
        }
        
        while (p1 <= mid) {
            temp[k++] = array[p1++];
        }
        
        while (p2 <= end) {
            temp[k++] = array[p2++];
        }
        
        for (int i = 0; i < temp.length; i++) {
            array[i + start] = temp[i];
        }
    }
}

JZ36 两个链表的第一个公共结点

题目大意：

输入两个无环的单链表，找出它们的第一个公共结点。

思路：

指针 p1 走 a 步到达第一个公共节点，指针 p2 走 b 步到达公共节点，那么如果我们能够让 p1 到第一个公共节点的距离等于 p2 到公共节点的距离，就能够用简单的比较判断来找到第一个公共节点。

所以我们可以利用 a+b=b+a 来构建相同的距离，两个链表变为 pHead1+pHead2 和 pHead2+pHead1，这样当走到他们的第一个公共节点时，都经过了 a+b+公共节点长度 的距离。

代码：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = p1 == null ? pHead2 : p1.next;
            p2 = p2 == null ? pHead1 : p2.next;
        }
        return p1;
    }
}

JZ37 数字在排序数组中出现的次数

题目大意：

统计一个数字在升序数组中出现的次数。

思路：

二分查找，找到指定数字后，分别向前和向后统计出现的次数。

代码：

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
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int num = 0;
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (k == array[mid]) {
                num++;
                // 往左
                for (int i = mid - 1; i >= 0; i--) {
                    if(k == array[i]) {
                        num++;
                    }
                }
                // 往右
                for (int i = mid + 1; i < array.length; i++) {
                    if(k == array[i]) {
                        num++;
                    }
                }
                return num;
            }
            if (k < array[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }            
        }
        return num;
    }
}

JZ38 二叉树的深度

题目大意：

输入一棵二叉树，求该树的深度。

思路：

max(左子树的深度，右子树的深度) + 1 = 当前节点为根节点的深度

代码：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        int result = (left > right ? left : right) + 1;
        return result;
    }
}

JZ39 平衡二叉树

题目大意：

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

思路：

以每个节点为根，判断当前子树的左右字数的高度差是否大于1。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return treeDepth(root) != -1;
    }
    public int treeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = treeDepth(root.left);
        if (left == -1) {
            return -1;
        }
        int right = treeDepth(root.right);
        if (right == -1) {
            return -1;
        }
        if (left - right > 1 || left - right < -1) {
            return -1;
        }
        return 1 + (left > right ? left : right);
    }
}

JZ40 数组中只出现一次的数字

题目大意：

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：将该问题拆分为一个数组里只有一个数字出现了一次的子问题。那么如何做到呢？

可以通过第一遍异或求得异或结果 xor 为只出现一次的两个数字 a，b 之和。然后取出 xor 的最后一位 1，因为是异或得到的结果，所以 a，b 在这一位上不同，令其为 mask。于是可以通过数字在该位上是 1 还是 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
import java.util.*;
public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        // 异或结果 xor 为只出现一次的两个数字a，b之和
        int xor = 0;
        for (int num : array) {
            xor ^= num;
        }
        // 取 xor 最后一位 1，因为是异或得到的结果，所以a和b在这一位上不同
        int mask = (xor & (xor - 1)) ^ xor;
        // 将数组分为两个部分，一个包含 a，一个包含 b，且数组中其他数字都是成对出现
        // 如何保证其他数字都是在同一个数组中成对出现？
        // 相同的数字一定在同一位上是相同的，那么在 mask 位上同为1或者同为0
        // 一个被分到了某组上，另一个一定会分到同一个组上
        // 问题转换成为“有一个数组每个数字都出现两次，有一个数字只出现了一次，求出该数字”
        int[] result = new int[2];
        for (int num : array) {
            if ((num & mask) == 0) {
                result[0] ^= num;
            }
        }
        // xor 为两数之和，xor 异或上其他一个就能得到另外一个
        result[1] = xor ^ result[0];
        if (result[0] > result[1]) {
            int temp = result[0];
            result[0] = result[1];
            result[1] = temp;
        }
        return result;
    }
}

JZ41 和为S的连续正数序列

题目大意：

找到所有和为S的连续正数序列。

思路：

连续正数序列，可以看作是一个区间的和，求一个区间的和可以利用前缀和来解决。

维护一个变量的值代表当前区间的和，区间和小于 sum 则需要扩大右边界，区间和大于 sum 则需要缩小左边界，等于则记录当前序列。

代码：

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
import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        int left = 1, right = 2, temp = 1;
        while (left <= sum / 2) {
            if (temp < sum) {
                temp += right;
                right++;
            } else if (temp > sum) {
                temp -= left;
                left++;
            } else {
                ArrayList<Integer> tempList = new ArrayList<>();
                for (int i = left; i < right; i++) {
                    tempList.add(i);
                }
                resList.add(tempList);
                temp -= left;
                left++;
            }
        }
        return resList;
    }
}

JZ42 和为S的两个数字

题目大意：

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。

思路：

二分查找。因为序列是递增有序的，所以可以使用二分查找的思想。当左右边界的和等于 sum 时去比较乘积，来判断用不用更新答案。

代码：

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
import java.util.*;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        int left = 0, right = array.length - 1, product = Integer.MAX_VALUE;
        ArrayList<Integer> resultList = new ArrayList<>();
        int[] res = new int[2];
        while (left < right) {
            int temp = array[left] + array[right];
            if (temp == sum && array[left] * array[right] < product) {
                res[0] = array[left];
                res[1] = array[right];
                product = array[left] * array[right];
                left++;
            } else if (temp > sum) {
                right--;
            } else {
                left++;
            }
        }
        if (product != Integer.MAX_VALUE) {
            resultList.add(res[0]);
            resultList.add(res[1]);
        }
        return resultList;
    }
}

JZ43 左旋转字符串

题目大意：

对于一个给定的字符序列 S，请你把其循环左移 K 位后的序列输出（保证 K 小于等于 S 的长度）

思路：

找到旋转后字符串的第一位，然后直接利用 substring 把前面的部分截取放到后面去就好了。

代码：

1
2
3
4
5
6
7
8
public class Solution {
    public String LeftRotateString(String str,int n) {
        if (str == null || str.length() == 0) {
            return str;
        }
        return str.substring(n, str.length()) + str.substring(0, n);
    }
}

JZ44 翻转单词序列

题目大意：

“nowcoder. a am I”翻转成“I am a nowcoder.”

思路：

两种思路。

思路一 翻转整个字符串变为 “I ma a .redocwon”，然后再翻转每一个单词成为正常顺序，两次翻转。

思路二 利用栈，按照空格将字符串分割，然后存入栈中。全部存入后再从栈中取出即为正常顺序。

代码：

思路一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public String ReverseSentence(String str) {
        int len = str.length();
        char[] array = new char[len + 2];
        array[0] = ' ';
        array[array.length - 1] = ' ';
        // 翻转第一次，整个翻转
        for (int i = 0; i < len; i++) {
            array[1 + i] = str.charAt(len - 1 - i);
        }
        for (int i = 1, start = 0; i < array.length; i++) {
            if (array[i] == ' ') {
                // 翻转第二次，单词翻转
                for (int j = 0; j < (i - start - 1) / 2; j++) {
                    char ch = array[start + 1 + j];
                    array[start + 1 + j] = array[i - 1 - j];
                    array[i - 1 - j] = ch;
                }
                start = i;
            }
        }
        return new String(array).substring(1,array.length - 1);
    }
}

思路二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
public class Solution {
    public String ReverseSentence(String str) {
        StringBuffer sb = new StringBuffer();
        // 按照空格分割字符串
        String[] temp = str.split(" ");
        // 全是空格的清空
        if (temp.length == 0) {
            return str;
        }
        Stack<String> stack = new Stack<>();
        for (String s : temp) {
            stack.push(s);
            stack.push(" ");
        }
        // 去掉多余的空格
        stack.pop();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}

JZ45 扑克牌顺子

题目大意：

给一个长度为 5 的序列，判断是不是顺子，数字范围是 [0, 13]，0 是癞子牌。

思路：

思路1 0 作为癞子牌可以充当任意数值的牌。将序列排序之后，从后往前遍历：

  • 相邻的两个元素之间差值为 1，符合顺子的定义
  • 相邻的两个元素之间差值为 0，说明出现了重复，直接返回 false
  • 相邻的两个元素之间差值大于 1，说明不连续，需要用癞子牌来填充

在遍历的过程中记录需要的癞子牌数量以及序列中已有的癞子牌数量，最后判断癞子牌的数量是否大于等于 0，大于等于 0 说明可以组成顺子，如果小于 0 说明癞子牌不够不能组成顺子。

思路2 利用 set 来保证不重复，出现重复就表示不是顺子。将非零的元素添加到 set 当中，并且记录最大值和最小值，如果最大值和最小值之差大于等于 5 说明无论怎样都不可能是顺子。

代码：

思路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
import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        if (numbers == null || numbers.length == 0) {
            return false;
        }
	    Arrays.sort(numbers);
        int zero = 0;
        for (int i = numbers.length - 1; i > 0; i--) {
            if (numbers[i - 1] == 0) {
                // 下一个是0，则添加一张癞子
                zero++;
            } else {
                int temp = numbers[i] - numbers[i - 1];
                if (temp > 0) {
                    // 差值-1 即代表两张牌中间差几张牌
                    zero = zero - (temp - 1);
                } else {
                    // 两张牌相等一定不是顺子
                    return false;
                }
            }
        }
        return zero >= 0;
    }
}

思路2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        if (numbers == null || numbers.length == 0) {
            return false;
        }
        Set<Integer> set = new HashSet<>();
        int max = 0, min = 14;
        for (int num : numbers) {
            if (num > 0) {
                if (!set.add(num)) {
                    return false;
                }
                max = Math.max(max, num);
                min = Math.min(min, num);
            }
        }
        return max - min < 5;
    }
}

JZ46 孩子们的游戏（圆圈中最后剩下的数）

题目大意：

随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的出列，并且不再回来。从他的下一个小朋友开始,继续0…m-1报数，直到剩下最后一个小朋友，确定最后一个小朋友的编号。

思路：

另外一个思路就是去模拟，用一个 List 去存放序列，模拟报数，喊到 m-1 的就删除，最后一个就是答案。

假设 f(n,m) 表示最终留下元素的序号。长度为 n 的序列会先删除第 m % n 个元素，然后剩下一个长度为 n-1 的序列。递归的去求解 f(n-1,m)，得到最终留下的元素是第 x 个元素。由于是删除了第 m % n 个元素得到的长度为 n-1 的序列，那么长度为 n 的序列最终留下元素应该是从 m % n 开始的第 x 个元素。

所以 f(n,m) = (m % n + f(n-1,m)) % n = (m + f(n-1,m)) % n。

当 n=1 时，f(1,m)=0。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n == 0) {
            return -1;
        }
        if (n == 1) {
            return 0;
        }
//         int k = m % n;
//         return (LastRemaining_Solution(n - 1, m) + k) % n;
        // 优化算式
        return (LastRemaining_Solution(n - 1, m) + m) % n;
    }
}

JZ47 求1+2+3+…+n

题目大意：

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：

求和公式什么的肯定不能用了，考虑递归，但是需要找到如何实现终止条件。正好 && 操作具有短路的作用，让 n>1 的情况下才会接着往下递归求和，n==1 的情况就直接返回。

代码：

1
2
3
4
5
6
public class Solution {
    public int Sum_Solution(int n) {
        boolean x = (n > 1 && ((n += Sum_Solution(n - 1)) > 0); // boolean x只是为了不报错
        return n;
    }
}

JZ48 不用加减乘除做加法

题目大意：

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

思路：

异或操作对应不进位的加法，与操作对应进位的结果。于是我们先按照不带进位的加法求出一个结果，然后如果需要进位的话，把进位结果继续用不带进位的加法加上去，再来看当前操作还需不需要进位，直到不需要进位为止。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int Add(int num1,int num2) {
        int result = 0, carry = 0;
        do {
            //不带进位的加法
            result = num1 ^ num2;
             //进位
            carry = (num1 & num2) << 1;
            // 进位不为0则继续执行加法处理进位
            num1 = result;
            num2 = carry;
        } while(carry != 0);
        return result;
    }
}

JZ49 把字符串转换成整数

题目大意：

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

思理：

参考 JDK 的 Integer.parseInt() 源码

代码：

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
public class Solution {
    // 转换成负数处理
    public int StrToInt(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int symbol = -1;
        char[] arr = str.toCharArray();
        int index = 0;
        // 处理开头的符号位
        if (arr[index] == '+' || arr[index] == '-') {
            if (arr[index] == '-') {
                symbol = 1;
            }
            index++;
        }
        int ans = 0, radix = 10;
        while (index < arr.length) {
            char ch = arr[index];
            // 非法数值
            if (!Character.isDigit(ch)) {
                return 0;
            }
            int temp = ch - '0';
            // 溢出，表明*10后就会溢出
            if (ans < Integer.MIN_VALUE / 10) {
                return 0;
            }
            ans *= radix;
            // 溢出，表明减去temp就会溢出
            if (ans < Integer.MIN_VALUE + temp) {
                return 0;
            }
            ans -= temp;
            index++;
        }
        return ans * symbol;
    }
}

JZ50 数组中重复的数字

题目大意：

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 请找出数组中任一一个重复的数字，存在不合法的输入的话输出-1。

思路：

因为数字内的所有数字都在 0 到 n-1 的范围内，所以定义一个长度为 n 的数组用来记录数字是否出现过一定不会越界。遍历数组。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Solution {
    public int duplicate (int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return -1;
        }
        boolean[] table = new boolean[numbers.length];
        for (int num : numbers) {
            if (table[num] == true) {
                return num;
            }
            table[num] = true;
        }
        return -1;
    }
}

JZ51 构建乘积数组

题目大意：

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

思路：

分为两部分来计算，先计算 A[0]*A[1]**...*A[i-1] 再计算 A[i+1]*...*A[n-1]，将它们乘起来就是最终结果，这样通过两次遍历就能求的结果。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        if (A == null || A.length == 0) {
            return null;
        }
        int length = A.length;
        int[] B = new int[length];
        // 计算 A[i] 左边的乘积
        B[0] = 1;
        for (int i = 1; i < length; i++) {
            B[i] = B[i - 1] * A[i - 1];
        }
        // 补全右边的乘积，就可以得到最终结果
        int temp = 1;
        for (int i = length - 2; i >= 0; i--) {
            temp *= A[i + 1];
            B[i] *= temp;
        }
        return B;
    }
}

JZ52 正则表达式匹配

题目大意：

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。

思路：

见注释，记一记这种类型。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
        if (str.isEmpty() && pattern.isEmpty()) {
            return true;
        }
        if (!str.isEmpty() && pattern.isEmpty()) {
            return false;
        }
        // 第一个是否匹配上
        boolean firstMatch = (!str.isEmpty()) && (str.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '.');
        // 下一个pattern为*
        if (pattern.length() > 1 && pattern.charAt(1) == '*') {
                   // 匹配0个
            return match(str, pattern.substring(2))
                   // 匹配多个
                || (firstMatch && match(str.substring(1), pattern));
        } else {
            // 下一个pattern不为*
            return firstMatch && match(str.substring(1), pattern.substring(1));
        }
    }
}

JZ53 表示数值的字符串

题目大意：

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

思路：

确保几点：

  • 小数点只能有一个，并且必须在e前面
  • e只能有一个，并且不能在首位和末位
  • e左边运算符只能有一个，并且只能在第一位
  • e右边运算符只能有一个，并且只能紧挨e后面
  • 不能出现.+-eE和数字以外的字符

代码：

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
import java.util.*;
public class Solution {
    public boolean isNumeric (String str) {
        char[] chars = str.toCharArray();
        boolean point = false;//表示小数点是否已存在
        boolean e = false;//表示e是否已存在
        boolean lOperator = false;//表示e左边运算符是否已存在
        boolean rOperator = false;//表示e右边运算符是否已存在
        int len = chars.length;
        int eIndex = len;//e出现的位置
        for (int i = 0; i < len; i++) {
            if (chars[i] == '.'){
                if (point || i > eIndex) return false;//小数点只能有一个，并且必须在e前面
                point = true;
            }else if (chars[i] == 'e' || chars[i] == 'E'){
                if (e || i == 0 || i == len-1) return false;//e只能有一个，并且不能在首位和末位
                eIndex = i;
                e = true;
            }else if (chars[i] == '+' || chars[i] == '-'){
                if (i < eIndex){
                    if (lOperator || i != 0) return false;//e左边运算符只能有一个，并且只能在第一位
                    lOperator = true;
                }else {
                    if (rOperator || i - eIndex != 1) return false;//e右边运算符只能有一个,并且只能紧挨e后面
                    rOperator = true;
                }
            }else if (chars[i] >= '0' && chars[i] <= '9'){//数字出现在哪都可以
                continue;
            }else {//不能出现.+-eE和数字以外的字符
                return false;
            }
        }
        return true;
    }
}

JZ54 字符流中第一个不重复的字符

题目大意：

请实现一个函数用来找出字符流中第一个只出现一次的字符。

思路：

利用一个队列来存储当前轮次，第一个只出现一次的字符；一个数组用来统计出现的次数。

代码：

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
import java.util.*;
public class Solution {
    Queue<Character> queue = new LinkedList<>();
    int[] table = new int[128];
    public void Insert(char ch)
    {
        // 第一次出现
        if (++table[ch] == 1) {
            queue.offer(ch);
        }
    }
    public char FirstAppearingOnce()
    {
        while (!queue.isEmpty()) {
            char ch = queue.peek();
            if (table[ch] == 1) {
                return ch;
            } else {
                // 说明队列头出现了不止一次，出队
                queue.poll();
            }
        }
        // 队列为空说明不存在出现一次的字符
        return '#';
    }
}

JZ55 链表中环的入口节点

题目大意：

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

思路：

利用快慢指针的思想。如果存在环，假设头结点为 A，环的入口节点为 B，当快慢指针相遇的时候，相遇在节点 C。由快指针比慢指针多走了一倍的距离，有：$2(AB + BC) = AB + BC + CB + BC$，化简后得到 $AB = CB$。由此可以推出，此时我们新建一个入口节点，从头结点开始往后遍历，慢节点也继续往后遍历。

当慢节点从 C 走到 B后，入口节点也从 A 走到了 B，此时它们在入口节点相遇。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead, slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode entryNode = pHead;
                while (entryNode != slow) {
                    entryNode = entryNode.next;
                    slow = slow.next;
                }
                return entryNode;
            }
        }
        return null;
    }
}

JZ56 删除链表中重复的结点

题目大意：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

思路：

为了方便处理头结点重复的情况，添加哑元节点 dummyNode。需要删除结点，所以为了保证链表连续，肯定需要一个 preNode 来记录上一个结点。外加一个当前结点 curNode，所以一共需要定义两个结点变量。

判断 curNode 和 curNode.next 的值是否一样，一样的话删除 curNode，然后一直找到值不等于的结点，再将 preNode.next 置为该节点。

代码：

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
import java.util.*;
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode outputNode = new ListNode(Integer.MAX_VALUE);
        ListNode preNode = outputNode, curNode = pHead;
        preNode.next = curNode;
        while (curNode != null) {
            int val = curNode.val;
            boolean isRepeat = false;
            // 存在下一个节点，且节点值重复，删掉
            while (curNode.next != null && curNode.next.val == val) {
                isRepeat = true;
                ListNode tempNode = curNode.next.next;
                curNode.next.next = null;
                curNode.next = tempNode;
            }
            // 节点重复了，删掉
            if (isRepeat) {
                ListNode tempNode = curNode.next;
                curNode.next = null;
                curNode = tempNode;
                preNode.next = curNode;
            } else {
                preNode = preNode.next;
                curNode = curNode.next;
            }
        }
        return outputNode.next;
    }
}

JZ57 二叉树的下一个结点

题目大意：

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。

思路：

这类问题需要根据二叉树的性值，分情况讨论。

代码：

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
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return pNode;
        }
        // 1. 有右子树，下一个节点就是右子树中的最左节点
        if (pNode.right != null) {
            pNode = pNode.right;
            while (pNode.left != null) {
                pNode = pNode.left;
            }
            return pNode;
        }
        // 2. 无右子树，当前节点是父节点的左子树，下一个节点就是其父节点
        if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        }

        // 3. 无右子树，当前节点是父节点的右节点，则沿着父节点追溯
        //    直到某个节点是其父节点的左子树
        if (pNode.next != null)
            while (pNode.next != null) {
                if (pNode.next.left == pNode) {
                    return pNode.next;
                }
                pNode = pNode.next;
            }
        // 4. 没有找到
        return null;
    }
}

JZ58 对称的二叉树

题目大意：

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：

镜像相同，说明需要满足：

  1. p1.val == p2.val
  2. p1.left == p2.right
  3. p1.right == p2.left

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        return judgeTree(pRoot, pRoot);
    }
    boolean judgeTree(TreeNode p1, TreeNode p2) {
        if (p1 == null && p2 == null) {
            return true;
        }
        if (p1 == null || p2 == null) {
            return false;
        }
        return p1.val == p2.val && judgeTree(p1.left, p2.right) && judgeTree(p1.right, p2.left);
    }
}

JZ59 按之字形顺序打印二叉树

题目大意：

给定一颗二叉树，假设根节点为第一层，按照奇数层，从左到右打印，偶数层，从右到左打印。

思路：

层次遍历打印二叉树，用队列实现。这道题是层次遍历二叉树+确定当前遍历到哪一层两种模板的结合。

代码：

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
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (pRoot == null) {
            return resList;
        }
        queue.offer(pRoot);
        int level = 0;
        while(!queue.isEmpty()) {
            level++;
            int size = queue.size();
            ArrayList<Integer> tempList = new ArrayList<>();
            while (size > 0) {
                size--;
                TreeNode tempNode = queue.poll();
                if (level % 2 == 0) {
                    tempList.add(0, tempNode.val);
                } else {
                    tempList.add(tempNode.val);
                }
                
                if (tempNode.left != null) {
                    queue.offer(tempNode.left);
                }
                if (tempNode.right != null) {
                    queue.offer(tempNode.right);
                }
            }
            resList.add(tempList);
        }
        return resList;
    }
}

JZ60 把二叉树打印成多行

题目大意：

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路：

确定当前遍历到哪层的模板，每一层加入到集合中。

代码：

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
import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (pRoot == null) {
            return resList;
        }
        queue.offer(pRoot);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> tempList = new ArrayList<>();
            for (; size > 0; size--) {
                TreeNode tempNode = queue.poll();
                tempList.add(tempNode.val);
                if (tempNode.left != null) {
                    queue.offer(tempNode.left);
                }
                if (tempNode.right != null) {
                    queue.offer(tempNode.right);
                }
            }
            resList.add(tempList);
        }
        return resList;
    }
}

JZ61 序列化二叉树

题目大意：

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

思路：

序列化主要就是通过将这颗树以一种方式进行顺序化。我们就将这颗二叉树进行先序遍历，得到访问这颗二叉树的一个访问顺序。

反序列化时，根据 str 提供的先序访问顺序，遍历 str 去构建各个二叉树结点，然后根据先序的顺序来构建结点之间的关系。

代码：

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
import java.util.*;
public class Solution {
    int index = -1;
    String[] list = null;
    //序列化主要就是通过将这颗树以一种方式进行顺序化。我们就将这颗二叉树进行先序遍历，得到访问这颗二叉树的一个访问顺序
    String Serialize(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        if (root == null) {
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }
    
    TreeNode Deserialize(String str) {
        index++;
        if (list == null) {
            list = str.split(",");
        }
        if (index >= list.length) {
            return null;
        }
        if (list[index].equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(list[index]));
        root.left = Deserialize(str);
        root.right = Deserialize(str);
        return root;
    }
}

JZ62 二叉搜索树的第k个节点

题目大意：

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。

思路：

二叉搜索树的中序遍历是有序的，所以利用中序遍历，找到第k个节点即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        TreeNode resNode = null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode tempNode = pRoot;
        while (!stack.isEmpty() || tempNode != null) {
            while (tempNode != null) {
                stack.push(tempNode);
                tempNode = tempNode.left;
            }
            tempNode = stack.pop();
            k--;
            if (k == 0) {
                resNode = tempNode;
                break;
            }
            tempNode = tempNode.right;
        }
        return resNode;
    }
}

JZ63 数据流中的中位数

题目大意：

得到一个数据流中的中位数。

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
import java.util.*;
public class Solution {
    List<Integer> list = new ArrayList<>();
    public void Insert(Integer num) {
        if (list.size() == 0) {
            list.add(num);
            return;
        }
        int left = 0, right = list.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        list.add(left, num);
    }

    public Double GetMedian() {
        int size = list.size();
        if (size % 2 == 0) {
            return new Double(list.get(size / 2) + list.get(size / 2 - 1)) / 2;
        } else {
            return new Double(list.get(size / 2));
        }
    }
}

JZ64 滑动窗口的最大值

题目大意：

思路：

利用双端队列来保存窗口内的最大值的下标，最大值保存在头部。

每次插入的时候，从后往前依次弹出比当前 num 小的元素，因为当前 num 比栈中元素大，说明栈中元素和当前元素在同一区间内时，它们没有资格称为最大的元素，所以弹出。

当下标大于 size 时，找到第一个下标在区间内的元素即为当前区间内最大的元素。

代码：

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
import java.util.*;
public class Solution {
    // https://cuijiahua.com/blog/2018/02/basis_64.html
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (size > num.length || size == 0) {
            return resList;
        }
        // 保存下标，使用双端队列 缓存滑动窗口，最大值保存在头部
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < num.length; i++) {
            // 从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标
            while (!queue.isEmpty() && num[queue.peekLast()] < num[i]) {
                queue.pollLast();
            }
            // 当队首元素坐标对应的num不在窗口中，需要弹出
            if (!queue.isEmpty() && i - queue.peekFirst() >= size) {
                queue.pollFirst();
            }
            // 把每次滑动的num下标加入队列
            queue.offerLast(i);
            // 当滑动窗口首地址i大于等于size时才开始写入窗口最大值
            if (i + 1 >= size) {
                resList.add(num[queue.peekFirst()]);
            }
        }
        return resList;
    }
}

JZ65 矩阵中的路径

题目大意：

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

思路：

dfs 遍历图，类似孤岛问题。

代码：

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
import java.util.*;
public class Solution {
    public boolean hasPath (char[][] matrix, String word) {
        int n = matrix.length, m = matrix[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (judge(matrix, i, j, new boolean[n][m], word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean judge(char[][] matrix, int i, int j, boolean[][] visited, String word, int index) {
        if (!inArea(matrix, i, j) || visited[i][j] || index > word.length()) {
            return false;
        }
        boolean res = false;
        if (matrix[i][j] == word.charAt(index)) {
            if (index == word.length() - 1) {
                return true;
            }
            visited[i][j] = true;
            res = judge(matrix, i + 1, j, visited, word, index + 1)
                       || judge(matrix, i, j + 1, visited, word, index + 1)
                       || judge(matrix, i - 1, j, visited, word, index + 1)
                       || judge(matrix, i, j - 1, visited, word, index + 1);
            visited[i][j] = false;
        }
        return res;
    }
    public boolean inArea(char[][] matrix, int i, int j) {
        return i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length;
    }
}

JZ66 机器人的运动范围

题目大意：

地上有一个rows行和cols列的方格。坐标从 [0,0] 到 [rows-1,cols-1]。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于threshold的格子。 例如，当threshold为18时，机器人能够进入方格[35,37]，因为3+5+3+7 = 18。但是，它不能进入方格[35,38]，因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：

用一维数组去表示矩阵，每次通过 i、j 来计算在数组中的具体哪个位置。

然后类似海岛问题，dfs 去数个数。

代码：

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
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        boolean[] visited = new boolean[rows * cols];
        return count(visited, threshold, rows, cols, 0, 0);
    }
    public int count(boolean[] visited, int threshold, int rows, int cols, int i, int j) {
        int index = i * cols + j;
        if (!judge(threshold, rows, cols, i, j) || visited[index]) {
            return 0;
        }
        visited[index] = true;
        return 1
            + count(visited, threshold, rows, cols, i + 1, j)
            + count(visited, threshold, rows, cols, i - 1, j)
            + count(visited, threshold, rows, cols, i, j + 1)
            + count(visited, threshold, rows, cols, i, j - 1);
    }
    public boolean judge(int threshold, int rows, int cols, int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= cols) {
            return false;
        }
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /=10;
        }
        while (j != 0) {
            sum += j % 10;
            j /=10;
        }
        return sum <= threshold;
    }
}

JZ67 剪绳子

题目大意：

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？

思路：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int cutRope(int target) {
        if (target < 2 || target > 61) {
            return 0;
        }
        // 数学规律：将 target 贪心分解，优先分解为3，其次是2能达到最大乘积
        int result = 1;
        int element = 3;
        while (target > 0) {
            // 上一轮 target=4，4 应该被分解为 2+2
            if (target == 1) {
                result = result / element * 2 * 2;
                break;
            } else if (target == 2){
                result *= 2;
                break;
            } else {
                target -= element;
            }
            result *= element;
        }
        return result;
    }
}



标签
algorithm