程序员面试金典

01

面试题 01.01. 判定字符是否唯一

面试题 01.01. 判定字符是否唯一

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isUnique(String astr) {
        int[] hash = new int[26];
        for (int i = 0; i < astr.length(); i++) {
            if (hash[astr.charAt(i) - 'a'] != 0) {
                return false;
            } else {
                hash[astr.charAt(i) - 'a']++;
            }
        }
        return true;
    }
}

面试题 01.02. 判定是否互为字符重排

面试题 01.02. 判定是否互为字符重排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            hash1[s1.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s2.length(); i++) {
            hash2[s2.charAt(i) - 'a']++;
        }
        // 看两个hash的值是不是都一样
        for (int i = 0; i < hash1.length; i++) {
            if (hash1[i] != hash2[i]) {
                return false;
            }
        }
        return true;
    }
}

面试题 01.03. URL化

面试题 01.03. URL化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String replaceSpaces(String S, int length) {
        char[] chars = S.toCharArray();
        int i = length - 1, j = S.length() - 1;
        while (i >= 0) {
            // 倒序去看，不为空格就在新数组倒序去插，为空格就插入%20先
            if (chars[i] == ' ') {
                // 倒序插入%20，保证空间够
                chars[j--] = '0';
                chars[j--] = '2';
                chars[j--] = '%';
            } else {
                chars[j--] = chars[i];
            }
            i--;
        }
        // i的位置是不需要的位置，不一定刚好到头的
        char[] result = new char[S.length() - 1 - j];
        for (int t = 0; t < result.length; t++) {
            result[t] = chars[++j];
        }
        return new String(result);
    }
}

面试题 01.04. 回文排列

面试题 01.04. 回文排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean canPermutePalindrome(String s) {
        // 不一定全为小写字母
        HashMap<Character, Integer> map = new HashMap<>();
        // 一个为奇数，其余为偶数或者全为偶数
        boolean flag = false;
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                if (flag) {
                    return false;
                }
                flag = true;
            }
        }
        return true;
    }
}

面试题 01.05. 一次编辑

面试题 01.05. 一次编辑

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
class Solution {
    public boolean oneEditAway(String first, String second) {
        // 长度不同的遇到不同的就只能删除（增加）操作了，这两个操作都一样的；长度相同的遇到不同的就只能替换操作了
        if (Math.abs(first.length() - second.length()) > 1) {
            return false;
        }
        //一个为空的情况
        if ((first.length() == 0 && second.length() == 1) || (first.length() == 1 && second.length() == 0)
                || (first.length() == 0 && second.length() == 0)) {
            return true;
        }
        // 相同，只能执行替换
        if (first.length() == second.length()) {
            int i = 0;
            // 前面是否执行了操作了
            boolean flag = false;
            while (i < first.length()) {
                if (first.charAt(i) != second.charAt(i)) {
                    if (!flag) {
                        flag = true;
                    } else {
                        return false;
                    }
                }
                i++;
            }
            return true;
        }
        // 长度不同，可以增加或删除，都是长的串指针+1
        else {
            int i = 0, j = 0;
            boolean flag = false;
            // 防止越界，前面操作过一定会一起到结尾，没操作过最后有个会多一个，删除就好，长度相差超过2的一开始排除了
            while (i < first.length() && j < second.length()) {
                if (first.charAt(i) != second.charAt(j)) {
                    if (!flag) {
                        flag = true;
                        // 看哪个长，哪个的下标+1
                        if (first.length() > second.length()) {
                            i++;
                        } else {
                            j++;
                        }
                    } else {
                        return false;
                    }
                } else {
                    i++;
                    j++;
                }
            }
            return true;
        }
    }
}

面试题 01.06. 字符串压缩

面试题 01.06. 字符串压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String compressString(String S) {
        if (S.length() <= 2) {
            return S;
        }
        StringBuilder builder = new StringBuilder();
        int i = 0;
        while (i < S.length()) {
            int j = i + 1;
            while (j < S.length() && S.charAt(i) == S.charAt(j)) {
                j++;
            }
            // 到这里就是拿到字母相同的字符串
            builder.append(S.charAt(i));
            builder.append(j - i);
            i = j;
        }
        return builder.toString().length() < S.length() ? builder.toString() : S;
    }
}

面试题 01.07. 旋转矩阵

面试题 01.07. 旋转矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void rotate(int[][] matrix) {
        // 写过类似的了，沿斜线折叠翻转，然后上下翻转就好
        int n = matrix.length;
        // 沿斜线折叠翻转,沿右下斜线规律好找,i和j交换就是对应位置,i和j相等不用处理
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 左右翻转
        for (int j = 0; j < n / 2; j++) {
            for (int i = 0; i < n; i++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

面试题 01.08. 零矩阵

面试题 01.08. 零矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public void setZeroes(int[][] matrix) {
        // 某行需要清空
        boolean[] isRowClear = new boolean[matrix.length];
        // 某列是否需要清空
        boolean[] isColumnClear = new boolean[matrix[0].length];
        // 看哪行哪列需要删除，不是删除的行和列就不用动
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    isRowClear[i] = true;
                    isColumnClear[j] = true;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (isRowClear[i] || isColumnClear[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

面试题 01.09. 字符串轮转

面试题 01.09. 字符串轮转

contains()其实就是模式匹配，这里不想手写kmp了

1
2
3
4
5
6
7
8
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        if (!s1.equals("") && s2.equals("")) {
            return false;
        }
        return (s1 + s1).contains(s2);
    }
}

手写kmp，速度没库函数高

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
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        // if (!s1.equals("") && s2.equals("")) {
        // return false;
        // }
        // return (s1 + s1).contains(s2);

        // kmp实现一下
        if (s1.length() != s2.length()) {
            return false;
        }
        return solve(s1 + s1, s2);
    }

    public boolean solve(String s1, String s2) {
        if (s1.equals("")) {
            return s2.equals("");
        }
        if (s2.equals("")) {
            return s1.equals("");
        }
        // 生成next数组
        int[] next = new int[s2.length()];
        // 初始化,0没得回退,i从1下标开始生成next数组，因为0下标肯定是0了
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s2.length(); i++) {
            // 回退直到0不能回退或者回退到相等的位置就一定是最长的，动规
            while (j > 0 && s2.charAt(i) != s2.charAt(j)) {
                j = next[j - 1];
            }
            // 看回退的最后一个位置是否相等
            if (s2.charAt(i) == s2.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        // 一遍循环,这里j控制模式串
        j = 0;
        for (int i = 0; i < s1.length(); i++) {
            // 两个位置相等的话就直接都加1就好，不等就回退
            while (j > 0 && s1.charAt(i) != s2.charAt(j)) {
                j = next[j - 1];
            }
            // 看两个位置是否想等
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
            }
            // 外层控制s1的循环
            if (j == s2.length()) {
                return true;
            }
        }
        return false;
    }
}

02

面试题 02.01. 移除重复节点

面试题 02.01. 移除重复节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        // 范围在0-20000
        int[] hash = new int[20001];
        if (head == null) {
            return null;
        }
        // 加一个头节点
        ListNode newHead = new ListNode(head.val + 1, head), last = newHead;
        while (head != null) {
            if (hash[head.val] == 0) {
                // 拼接就好
                hash[head.val] = 1;
                last.next = head;
                last = head;
            } else {
                head = head.next;
            }
        }
        last.next = null;
        return newHead.next;
    }
}

面试题 02.02. 返回倒数第 k 个节点

面试题 02.02. 返回倒数第 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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        // 经典问题了，快慢指针，题目保证k有效了
        ListNode node = head;
        while (k != 0) {
            node = node.next;
            k--;
        }
        while (node != null) {
            node = node.next;
            head = head.next;
        }
        return head.val;
    }
}

面试题 02.03. 删除中间节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        // 其实是将传入的节点变为下一个，删除下一个
        ListNode next = node.next;
        // next一定不为空，题目定义中间节点就是不为头和尾
        node.val = next.val;
        node.next = next.next;
    }
}

面试题 02.04. 分割链表

面试题 02.04. 分割链表

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // 加两头节点
        ListNode smallHead = new ListNode(), smallLast = smallHead;
        ListNode bigHead = new ListNode(), bigLast = bigHead;
        while (head != null) {
            ListNode next = head.next;
            // 断开连接
            head.next = null;
            // 比较大小
            if (head.val < x) {
                smallLast.next = head;
                smallLast = smallLast.next;
            } else {
                bigLast.next = head;
                bigLast = bigLast.next;
            }
            head = next;
        }
        if (smallHead.next == null) {
            return bigHead.next;
        }
        if (bigHead.next == null) {
            return smallHead.next;
        }
        // 两个链表都有内容
        smallLast.next = bigHead.next;
        return smallHead.next;
    }
}

面试题 02.05. 链表求和

面试题 02.05. 链表求和

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 正序就用下面先逆序计算转回来就行
        ListNode head = new ListNode(), last = head;
        // 合并计算
        int flag = 0;
        while (l1 != null && l2 != null) {
            int temp = l1.val + l2.val + flag;
            last.next = new ListNode(temp % 10);
            last = last.next;
            flag = temp / 10;
            l1 = l1.next;
            l2 = l2.next;
        }
        // 看谁还有就继续
        while (l1 != null) {
            int temp = l1.val + flag;
            last.next = new ListNode(temp % 10);
            last = last.next;
            flag = temp / 10;
            l1 = l1.next;
        }

        while (l2 != null) {
            int temp = l2.val + flag;
            last.next = new ListNode(temp % 10);
            last = last.next;
            flag = temp / 10;
            l2 = l2.next;
        }

        // 最后进位不为0还要加一个
        if (flag != 0) {
            last.next = new ListNode(flag);
            last = last.next;
        }

        return head.next;
    }

    // 翻转
    // public ListNode reverse(ListNode node) {
    // ListNode last = null;
    // while (node != null) {
    // ListNode next = node.next;
    // node.next = last;
    // last = node;
    // node = next;
    // }
    // return last;
    // }
}

面试题 02.06. 回文链表

面试题 02.06. 回文链表

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 翻转一半来比较就好
        // 计算个数
        int size = 0;
        ListNode temp = head, left = head;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        // 一个或者为空
        if (size <= 1) {
            return true;
        }
        // 计算到一半，翻转
        size /= 2;
        ListNode right = left;
        for (int i = 0; i < size - 1; i++) {
            right = right.next;
        }
        // 断开right连接
        ListNode next = right.next;
        right.next = null;
        // 翻转right
        right = reverse(next);
        // 比较
        int t = 1;
        while (t <= size && right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
            t++;
        }
        return true;
    }

    public ListNode reverse(ListNode node) {
        ListNode last = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = last;
            last = node;
            node = next;
        }
        return last;
    }

}

面试题 02.07. 链表相交

面试题 02.07. 链表相交

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != null | B != null) {
            if (A == B) {
                return A;
            }
            if (A == null) {
                A = headB;
            } else {
                A = A.next;
            }
            if (B == null) {
                B = headA;
            } else {
                B = B.next;
            }
        }
        // 没有相交点
        return null;
    }
}

面试题 02.08. 环路检测

面试题 02.08. 环路检测

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 也是经典题目，模拟一遍假设慢指针走了k，快指针走了2k，刚好快指针比慢指针走多一圈，有环环长为2k-k=k，而环之前的距离+环内慢指针走的也为k，这时候快指针在环内走的步数刚好为慢指针进入到距离，这时候慢指针回到头，快指针继续走，刚好走的距离加上慢指针在圈内的距离就是一圈
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        // 不为空,slow回头部，之前slow和fast走一步交点就是入口
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

03

面试题 03.01. 三合一

面试题 03.01. 三合一

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
class TripleInOne {

    int[] ints;
    int[] sizes = new int[3];
    int stackSize;

    public TripleInOne(int stackSize) {
        this.stackSize = stackSize;
        ints = new int[stackSize * 3];
    }

    public void push(int stackNum, int value) {
        if (sizes[stackNum] != stackSize) {
            ints[stackSize * stackNum + sizes[stackNum]] = value;
            sizes[stackNum]++;
        }
    }

    public int pop(int stackNum) {
        if (sizes[stackNum] > 0) {
            int result = ints[stackSize * stackNum + sizes[stackNum] - 1];
            sizes[stackNum]--;
            return result;
        } else {
            return -1;
        }
    }

    public int peek(int stackNum) {
        if (sizes[stackNum] > 0) {
            return ints[stackSize * stackNum + sizes[stackNum] - 1];
        } else {
            return -1;
        }
    }

    public boolean isEmpty(int stackNum) {
        return sizes[stackNum] == 0;
    }
}

/**
 * Your TripleInOne object will be instantiated and called as such:
 * TripleInOne obj = new TripleInOne(stackSize);
 * obj.push(stackNum,value);
 * int param_2 = obj.pop(stackNum);
 * int param_3 = obj.peek(stackNum);
 * boolean param_4 = obj.isEmpty(stackNum);
 */

面试题 03.02. 栈的最小值

面试题 03.02. 栈的最小值

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
class MinStack {

    // 也是经典题目，双栈模拟
    Deque<Integer> stack;
    Deque<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        int x = stack.pop();
        // 放心，抛出大的无所谓，大的不会是小的，对minStack没影响
        if (x == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

面试题 03.03. 堆盘子

面试题 03.03. 堆盘子

往之前抛出的栈加后面抛出顺序就是不对的！！！脑抽了

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
class StackOfPlates {

    // 一个List保存所有子栈的数量
    List<Deque<Integer>> stacks;
    int cap;

    public StackOfPlates(int cap) {
        this.cap = cap;
        stacks = new ArrayList<>();
    }

    public void push(int val) {
        if (cap <= 0) {
            return;
        }
        // 检查最后一个栈是否未满就好了，因为再往前放抛出有问题！！！
        if (!stacks.isEmpty() && stacks.get(stacks.size() - 1).size() < cap) {
            // 加入最后一个
            stacks.get(stacks.size() - 1).push(val);
        } else {
            // 新开栈
            Deque<Integer> stack = new LinkedList<>();
            stack.push(val);
            stacks.add(stack);
        }
    }

    public int pop() {
        if (cap <= 0 || stacks.isEmpty()) {
            return -1;
        }
        int i = stacks.size() - 1, j = stacks.get(i).size();
        int result = stacks.get(i).pop();
        if (j - 1 == 0) {
            stacks.remove(i);
        }
        return result;
    }

    public int popAt(int index) {
        // 从某个栈抛出
        if (cap <= 0 || stacks.isEmpty() || index < 0 || index >= stacks.size()) {
            return -1;
        }
        int j = stacks.get(index).size();
        int result = stacks.get(index).pop();
        if (j - 1 == 0) {
            stacks.remove(index);
        }
        return result;
    }
}

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates obj = new StackOfPlates(cap);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAt(index);
 */

面试题 03.04. 化栈为队

面试题 03.04. 化栈为队

也是经典题目了

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 MyQueue {

    Deque<Integer> stack1;
    Deque<Integer> stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack2.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (stack1.isEmpty()) {
            while (!stack2.isEmpty()) {
                stack1.push(stack2.pop());
            }
        }
        return stack1.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (stack1.isEmpty()) {
            while (!stack2.isEmpty()) {
                stack1.push(stack2.pop());
            }
        }
        return stack1.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

面试题 03.05. 栈排序

面试题 03.05. 栈排序

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 SortedStack {

    Deque<Integer> stack;
    Deque<Integer> helpStack;

    public SortedStack() {
        stack = new LinkedList<>();
        helpStack = new LinkedList<>();
    }
    
    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(val);
        }else{
            while(!stack.isEmpty()&&val>stack.peek()){
                //小的按顺序出栈放入另外一个栈
                helpStack.push(stack.pop());
            }
            //放入当前的
            stack.push(val);
            //将辅助栈的全移进stack
            while(!helpStack.isEmpty()){
                stack.push(helpStack.pop());
            }
        }
    }
    
    public void pop() {
        if(!stack.isEmpty()){
            stack.pop();
        }
    }
    
    public int peek() {
        return stack.isEmpty() ? -1 : stack.peek();
    }
     
    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

/**
 * Your SortedStack object will be instantiated and called as such:
 * SortedStack obj = new SortedStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.isEmpty();
 */

面试题 03.06. 动物收容所

面试题 03.06. 动物收容所

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
class AnimalShelf {

    LinkedList<int[]> queue;

    public AnimalShelf() {
        queue = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        queue.offerLast(animal);
    }

    public int[] dequeueAny() {
        return queue.isEmpty() ? new int[] { -1, -1 } : queue.pollFirst();
    }

    public int[] dequeueDog() {
        for (int i = 0; i < queue.size(); i++) {
            if (queue.get(i)[1] == 1) {
                int[] result = queue.get(i);
                queue.remove(i);
                return result;
            }
        }
        return new int[] { -1, -1 };
    }

    public int[] dequeueCat() {
        for (int i = 0; i < queue.size(); i++) {
            if (queue.get(i)[1] == 0) {
                int[] result = queue.get(i);
                queue.remove(i);
                return result;
            }
        }
        return new int[] { -1, -1 };
    }
}

/**
 * Your AnimalShelf object will be instantiated and called as such:
 * AnimalShelf obj = new AnimalShelf();
 * obj.enqueue(animal);
 * int[] param_2 = obj.dequeueAny();
 * int[] param_3 = obj.dequeueDog();
 * int[] param_4 = obj.dequeueCat();
 */

04

面试题 04.01. 节点间通路

面试题 04.01. 节点间通路

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
class Solution {

    boolean isSuccess = false;

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        // 有向边，这里用邻接表表示图
        List<List<Integer>> grid = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            grid.add(new LinkedList<>());
        }
        // 记录是否访问过
        boolean[] isVisited = new boolean[n];
        // 遍历完善图
        for (int[] ints : graph) {
            grid.get(ints[0]).add(ints[1]);
        }
        // 开始深搜
        isVisited[start] = true;
        dfs(grid, isVisited, target, start);
        return isSuccess;
    }

    public void dfs(List<List<Integer>> grid, boolean[] isVisited, int target, int point) {
        if (point == target) {
            isSuccess = true;
            return;
        }
        if (isSuccess) {
            return;
        }
        for (int i : grid.get(point)) {
            if (!isVisited[i]) {
                isVisited[i] = true;

                dfs(grid, isVisited, target, i);

                isVisited[i] = false;
            }
        }
    }
}

面试题 04.02. 最小高度树

面试题 04.02. 最小高度树

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums,0,nums.length-1);
    }

    public TreeNode build(int[] nums,int start,int end){
        if(start>end){
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = build(nums,start,mid-1);
        node.right = build(nums,mid+1,end);
        return node;
    }
}

面试题 04.03. 特定深度节点链表

面试题 04.03. 特定深度节点链表

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        List<ListNode> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (tree != null) {
            queue.add(tree);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 当前轮的节点
            ListNode newHead = new ListNode(), last = newHead;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                last.next = new ListNode(node.val);
                last = last.next;
            }
            // 加入结果
            list.add(newHead.next);
        }
        // ListNode[] result = new ListNode[list.size()];
        // for (int i = 0; i < list.size(); i++) {
        // result[i] = list.get(i);
        // }
        // return result;
        // 转为object类型数组，list.toArray()，转为具体类型list.toArray(new String[0])
        return list.toArray(new ListNode[0]);
    }
}

面试题 04.04. 检查平衡性

面试题 04.04. 检查平衡性

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        //当前节点的左右最大高度差是否不超过1并且左右都符合要求
        return Math.abs(heightOfTree(root.left) - heightOfTree(root.right)) <= 1 && isBalanced(root.left)
                && isBalanced(root.right);
    }

    //计算某棵子树的最大高度
    public int heightOfTree(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(heightOfTree(node.left), heightOfTree(node.right)) + 1;
    }
}

面试题 04.05. 合法二叉搜索树

面试题 04.05. 合法二叉搜索树

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

    List<Integer> list = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        inOrder(root);
        if (list == null) {
            return true;
        }
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= list.get(i - 1)) {
                return false;
            }
        }
        return true;
    }

    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        list.add(node.val);
        inOrder(node.right);
    }
}

没想到递归做法

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    // 递归确实没想到，好睿智
    public boolean isValidBST(TreeNode root) {
        return isLegal(root, null, null);
    }

    public boolean isLegal(TreeNode root, Integer min, Integer max) {
        if (root == null) {
            return true;
        }
        if ((min != null && root.val <= min) || (max != null && root.val >= max)) {
            return false;
        }
        return isLegal(root.left, min, root.val) && isLegal(root.right, root.val, max);
    }

}

面试题 04.06. 后继者

面试题 04.06. 后继者

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Deque<TreeNode>stack = new LinkedList<>();
        while(!stack.isEmpty()||root!=null){
            if(root!=null){
                stack.push(root);
                root = root.left;
            }else{
                //一直往左，最后处理中间的，然后再处理右边
                root = stack.poll();
                if(root.val>p.val){
                    return root;
                }
                root = root.right;
            }
        }
        return 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
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    TreeNode result = null;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        inOrder(root, p);
        return result;
    }

    public void inOrder(TreeNode node, TreeNode p) {
        if (node == null || result != null) {
            return;
        }
        inOrder(node.left, p);
        //控制只赋值一次
        if (node.val > p.val && result == null) {
            result = node;
        }
        inOrder(node.right, p);
    }
}

面试题 04.08. 首个共同祖先

面试题 04.08. 首个共同祖先

后续递归返回结果并处理的过程就相当于从底到顶的处理了，为空或者遇到要求的直接返回就好了，然后后序递归处理，如果左右都不为空就返回根，不然返回不为null的那个，都为空就随便返回了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        if (left == null) {
            return right;
        } else {
            return left;
        }
    }
}

面试题 04.09. 二叉搜索树序列

面试题 04.09. 二叉搜索树序列

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
class Solution {
    //这题不太看得懂，大概就是父节点要在子节点的前面
    public List<List<Integer>> BSTSequences(TreeNode root) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            result.add(Collections.EMPTY_LIST);
            return result;
        }
        
        Deque<TreeNode> deq = new LinkedList<>();
        deq.offer(root);
        dfs(deq, new ArrayList<Integer>(), result);
        return result;

    }

    private void dfs(Deque<TreeNode> deq, List<Integer> arr, List<List<Integer>> result) {
        //选完了，有一种情况出来了
        if (deq.size() == 0) {
            result.add(new ArrayList<Integer>(arr));
            return;
        }
        int size = deq.size();

        //遍历所有可选的情况，父节点选了，这里面的都是可以选的，选哪个先都可以
        while (size-- > 0) {
            //选择，移除这个，后面回回溯
            TreeNode cur = deq.poll();
            //加入可选
            if (cur.left != null) deq.offer(cur.left);
            if (cur.right != null) deq.offer(cur.right);

            //加入临时结果
            arr.add(cur.val);
            //递归
            dfs(deq, arr, result);
            //回溯
            arr.remove(arr.size() - 1);

            //回溯
            if (cur.right != null) deq.pollLast();
            if (cur.left != null) deq.pollLast();
            deq.offer(cur);
        }
    }

}

这里的Deque用List当前也可以，反正能回溯就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {

    List<Integer> temp = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> BSTSequences(TreeNode root) {
        if (root == null) {
            result.add(temp);
            return result;
        }
        // 递归回溯
        List<TreeNode> canSelect = new ArrayList<>();
        canSelect.add(root);
        backTracking(canSelect);
        return result;
    }

    public void backTracking(List<TreeNode> canSelect) {
        if (canSelect.isEmpty()) {
            // 加入结果
            result.add(new ArrayList<>(temp));
            return;
        }
        // 从所有可选里面选择一个
        for (int i = 0; i < canSelect.size(); i++) {
            // 选择
            TreeNode select = canSelect.get(i);
            canSelect.remove(i);
            temp.add(select.val);

            // 选择后子孩子都可先
            if (select.left != null) {
                canSelect.add(select.left);
            }
            if (select.right != null) {
                canSelect.add(select.right);
            }

            // 递归
            backTracking(canSelect);

            // 回溯回原始状态，看选择的左右还是是不是空决定移除多少个
            if (select.left != null) {
                canSelect.remove(canSelect.size() - 1);
            }
            if (select.right != null) {
                canSelect.remove(canSelect.size() - 1);
            }
            canSelect.add(i, select);
            temp.remove(temp.size() - 1);
        }
    }
}

面试题 04.10. 检查子树

面试题 04.10. 检查子树

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

class Solution {
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2 == null;
        }
        return isSame(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }

    // 看两棵树是否一样
    public boolean isSame(TreeNode node1, TreeNode node2) {
        if (node1 != null && node2 != null) {
            return node1.val == node2.val && isSame(node1.left, node2.left)
                    && isSame(node1.right, node2.right);
        } else if (node1 == null && node2 == null) {
            return true;
        }
        return false;
    }
}

面试题 04.12. 求和路径

面试题 04.12. 求和路径

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
class Solution {

    int result = 0;

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        getSum(root, sum, 0);
        if (root.left != null) {
            pathSum(root.left, sum);
        }
        if (root.right != null) {
            pathSum(root.right, sum);
        }
        return result;
    }

    public void getSum(TreeNode root, int target, int temp) {
        if (root == null) {
            return;
        }
        if (root.val + temp == target) {
            result++;
        }
        getSum(root.left, target, temp + root.val);
        getSum(root.right, target, temp + root.val);
    }
}

05

面试题 05.01. 插入

面试题 05.01. 插入

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
class Solution {
    public int insertBits(int N, int M, int i, int j) {
        // 应该可以通过位运算解决的，暂时没头绪，先暴力模拟吧
        int bit = 0, temp = N;
        if (temp == 0) {
            bit = 1;
        } else {
            while (temp != 0) {
                temp /= 2;
                bit++;
            }
        }
        // 看位数够不够，不够修正为足够的
        if (bit <= j) {
            bit = j + 1;
        }
        // 新建bit长度的数组
        int[] bits = new int[bit];
        // 填充
        int t = bit - 1;
        while (N != 0) {
            bits[t--] = N % 2;
            N /= 2;
        }
        // 填充完成，准备替换
        int start = bit - i - 1, end = bit - j - 1;
        while (M != 0 && start >= end) {
            bits[start--] = M % 2;
            M /= 2;
        }
        // 看start和end是否到头，未到头全部赋0
        while (start >= end) {
            bits[start--] = 0;
        }
        // 返回新数字
        int result = 0;
        for (int m = 0; m < bit; m++) {
            result = result * 2 + bits[m];
        }
        return result;
    }
}

上面不优雅，研究一下位运算怎么解决

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int insertBits(int N, int M, int i, int j) {
        // 位运算确实没思考出来，低位保留思考不出来，看完答案恍然大悟
        // 保留高位,右移动后为0回来就好，中间和后面为0
        int hight = N >> j >> 1;
        hight = hight << j << 1;
        // 保留低位,这是最强的，全1左移动位数后减1，那么就有i位的，最前面一位为0，&得到最右边的，前面和中间为0
        int low = N & ((1 << i) - 1);
        // 要替换的部分，中间部分现在为0，最后|就好
        int middle = M << i;
        return hight | low | middle;
    }
}

面试题 05.02. 二进制数转字符串

面试题 05.02. 二进制数转字符串

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
```



## 08

- **<a href="#面试题 08.01. 三步问题">面试题 08.01. 三步问题</a>**
- **<a href="#面试题 08.02. 迷路的机器人">面试题 08.02. 迷路的机器人</a>**
- **<a href="#面试题 08.03. 魔术索引">面试题 08.03. 魔术索引</a>**
- **<a href="#面试题 08.04. 幂集">面试题 08.04. 幂集</a>**
- **<a href="#面试题 08.05. 递归乘法">面试题 08.05. 递归乘法</a>**
- **<a href="#面试题 08.06. 汉诺塔问题">面试题 08.06. 汉诺塔问题</a>**
- **<a href="#面试题 08.07. 无重复字符串的排列组合">面试题 08.07. 无重复字符串的排列组合</a>**
- **<a href = "#面试题 08.08. 有重复字符串的排列组合">面试题 08.08. 有重复字符串的排列组合</a>**
- **<a href="#面试题 08.09. 括号">面试题 08.09. 括号</a>**
- **<a href="#面试题 08.10. 颜色填充">面试题 08.10. 颜色填充</a>**
- **<a href="#面试题 08.11. 硬币">面试题 08.11. 硬币</a>**
- **<a href="#面试题 08.12. 八皇后">面试题 08.12. 八皇后</a>**



<a name="面试题 08.01. 三步问题"></a>

**面试题 08.01. 三步问题**

[面试题 08.01. 三步问题](https://leetcode.cn/problems/three-steps-problem-lcci/)

```java
class Solution {
    public int waysToStep(int n) {
        // 初始化的时候1 1;2 2;3 4，也就是一级楼梯只要一种跳法，两级只有两种，三级开始就有4中，之后就是类斐波那契了
        if (n <= 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        long first = 1, second = 2, third = 4;
        for (int i = 4; i <= n; i++) {
            long sum = (first + second + third) % 1000000007;
            first = second;
            second = third;
            third = sum;
        }
        return (int) (third);
    }
}

面试题 08.02. 迷路的机器人

面试题 08.02. 迷路的机器人

深搜过不了，只能dp了

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
class Solution {
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        int len1 = obstacleGrid.length,len2 = obstacleGrid[0].length;
        int[][] dp = new int[len1][len2];
        dp[0][0] = 1;
        for(int i = 0;i<len1;i++){
            for(int j = 0;j<len2;j++){
                if(obstacleGrid[i][j]==1){
                    dp[i][j] = 0;
                }else{
                    //0 0默认1即可，不处理
                    if(i==0&&j!=0){
                        dp[i][j] = dp[i][j-1]==0?0:1;
                    }else if(i!=0&&j==0){
                        dp[i][j] = dp[i-1][j]==0?0:1;
                    }else if(i!=0&&j!=0){
                        dp[i][j] = dp[i-1][j]+dp[i][j-1];
                    }
                }
            }
        }
        //保存结果
        List<List<Integer>>result = new ArrayList<>();
        //看最后有没有办法到达
        if(dp[len1-1][len2-1]==0){
            return result;
        }
        //根据dp回退查找路径
        int i = len1-1,j = len2-1;
        while(i>=0&&j>=0){
            List<Integer>temp = new ArrayList<>();
            temp.add(i);
            temp.add(j);
            result.add(temp);
            //向上或向左找一个位置能到达的
            int left = 0,right = 0;
            if(i-1>=0){
                left = dp[i-1][j];
            }
            if(j-1>=0){
                right = dp[i][j-1];
            }
            if(left>right){
                i = i - 1;
            }else{
                j = j-1;
            }   
        }
        Collections.reverse(result);
        return result;
    }
}

面试题 08.03. 魔术索引

面试题 08.03. 魔术索引

不知道二分能不能写的，On很简单

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findMagicIndex(int[] nums) {
        
        for(int i = 0;i<nums.length;i++){
            if(nums[i] == i){
                return i;
            }
        }
        return -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
 // int result = -1;

​    // //二分

​    // int left = 0,right = nums.length-1;

​    // while(left<=right){

​    //   int mid = left + (right-left)/2;

​    //   if(nums[mid]<mid){



​    //   }else if(nums[mid]>mid){

​        

​    //   }else{

​    //     result = result==-1?mid:(Math.min(result,mid));

​    //     right = mid-1;

​    //   }

​    // }

面试题 08.04. 幂集

面试题 08.04. 幂集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // 回溯
        List<List<Integer>> ans = new ArrayList<>();
        backTracking(ans, new ArrayList<>(), 0, nums);
        return ans;
    }

    public void backTracking(List<List<Integer>> result, List<Integer> temp, int deep, int[] nums) {
        result.add(new ArrayList<>(temp));
        // 不能重复选,不回头
        for (int i = deep; i < nums.length; i++) {
            temp.add(nums[i]);
            backTracking(result, temp, i + 1, nums);
            temp.remove(temp.size() - 1);
        }
    }
}

面试题 08.05. 递归乘法

面试题 08.05. 递归乘法

有取巧的，两数相乘就是A个B相加

1
2
3
4
5
6
7
8
9
class Solution {
    public int multiply(int A, int B) {
        int sum = 0;
        for (int i = 1; i <= B; i++) {
            sum += A;
        }
        return sum;
    }
}

面试题 08.06. 汉诺塔问题

面试题 08.06. 汉诺塔问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        // 1个操作数为1，之后规律为2*上轮操作数+2，模拟下来上轮操作4过去的话，要把4放空，这时候3 2 1要回到1，跟上轮3 2
        // 1从第一个到第三个操作一模一样，然后4到三，又执行上轮的操作，3 2 1到第三个（刚好是递归到头回来的过程）
        move(A, B, C, A.size());
    }

    // A为原本位置，C为目标位置，B为帮助位置
    public void move(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        // 剩下一个的时候直接移到最后一个就好
        if (n == 1) {
            C.add(A.remove(A.size() - 1));
            return;
        }
        // 将n-1个借助最后一个移动到中间的
        move(A, C, B, n - 1);
        C.add(A.remove(A.size() - 1));
        // 将n-1借助第一个移动到最后
        move(B, A, C, n - 1);
    }
}

面试题 08.07. 无重复字符串的排列组合

面试题 08.07. 无重复字符串的排列组合

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
class Solution {
    public String[] permutation(String S) {
        List<String> result = new ArrayList<>();
        backTracking(result, new StringBuilder(), S, new boolean[S.length()]);
        return result.toArray(new String[0]);
    }

    public void backTracking(List<String> result, StringBuilder builder, String S, boolean[] isSelected) {
        if (builder.length() == S.length()) {
            result.add(builder.toString());
            return;
        }
        // 遍历每一位没选过的选
        for (int i = 0; i < S.length(); i++) {
            if (!isSelected[i]) {
                builder.append(S.charAt(i));
                isSelected[i] = true;
                backTracking(result, builder, S, isSelected);
                // 回溯
                builder.delete(builder.length() - 1, builder.length());
                isSelected[i] = false;
            }
        }
    }
}

面试题 08.08. 有重复字符串的排列组合

面试题 08.08. 有重复字符串的排列组合

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
class Solution {
    public String[] permutation(String S) {
        List<String> result = new ArrayList<>();
        char[] str = S.toCharArray();
        Arrays.sort(str);
        backTracking(result, new StringBuilder(), str, new boolean[S.length()]);
        return result.toArray(new String[0]);
    }

    public void backTracking(List<String> result, StringBuilder builder, char[] str, boolean[] isSelected) {
        if (builder.length() == str.length) {
            result.add(builder.toString());
            return;
        }
        // 遍历每一位没选过的选
        for (int i = 0; i < str.length; i++) {
            // 剪枝，选择过或者本轮相同的选过了一次了就不能选了（也可以Set直接去重），隔层选肯定可以选，如果a a b中a没选择过尝试选第二个a肯定重了（在解空间树里面同样）
            if (isSelected[i] || (i > 0 && str[i] == str[i - 1] && isSelected[i - 1])) {
                continue;
            }
            builder.append(str[i]);
            isSelected[i] = true;
            // 递归
            backTracking(result, builder, str, isSelected);
            // 回溯
            builder.deleteCharAt(builder.length() - 1);
            isSelected[i] = false;
        }
    }
}

面试题 08.09. 括号

面试题 08.09. 括号

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
class Solution {
    public List<String> generateParenthesis(int n) {
        // 两个变量控制当前左右括号的个数
        List<String> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }
        backTracking(result, new StringBuilder(), n, n);
        return result;
    }

    public void backTracking(List<String> result, StringBuilder builder, int left, int right) {
        if (left == 0 && right == 0) {
            result.add(builder.toString());
            return;
        }

        // 只能选择左括号
        if (left >= right) {
            builder.append("(");
            backTracking(result, builder, left - 1, right);
            builder.deleteCharAt(builder.length() - 1);
        }
        // 只能选择右括号
        else if (left == 0) {
            builder.append(")");
            backTracking(result, builder, left, right - 1);
            builder.deleteCharAt(builder.length() - 1);
        }
        // 都能选
        else {
            builder.append("(");
            backTracking(result, builder, left - 1, right);
            builder.deleteCharAt(builder.length() - 1);

            builder.append(")");
            backTracking(result, builder, left, right - 1);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

面试题 08.10. 颜色填充

面试题 08.10. 颜色填充

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
class Solution {

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        // 可以深搜也可以广搜
        // return bfs(image, sr, sc, newColor);
        dfs(image, sr, sc, newColor, image[sr][sc], new boolean[image.length][image[0].length]);
        return image;
    }

    // 广搜
    public int[][] bfs(int[][] image, int sr, int sc, int newColor) {
        // 看这个点是否访问过，访问过就不能再访问了，加入队列就要设置为访问过了
        boolean[][] isVisited = new boolean[image.length][image[0].length];
        // 控制处理方向
        // int[][] dir = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
        Queue<int[]> queue = new LinkedList<>();
        int target = image[sr][sc];
        queue.offer(new int[] { sr, sc });
        isVisited[sr][sc] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            // 处理
            image[cur[0]][cur[1]] = newColor;
            for (int[] ints : dir) {
                int i = cur[0] + ints[0], j = cur[1] + ints[1];
                if (i >= 0 && i < image.length && j >= 0 && j < image[0].length && !isVisited[i][j]
                        && image[i][j] == target) {
                    // 加入队列
                    queue.offer(new int[] { i, j });
                    isVisited[i][j] = true;
                }
            }
        }
        return image;
    }

    // 深搜
    public static int[][] dir = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

    public void dfs(int[][] image, int sr, int sc, int newColor, int target, boolean[][] isVisited) {
        // 改色
        image[sr][sc] = newColor;
        isVisited[sr][sc] = true;
        // 看周围哪个没处理过，去处理他
        for (int[] ints : dir) {
            int i = sr + ints[0], j = sc + ints[1];
            if (i >= 0 && i < image.length && j >= 0 && j < image[0].length && !isVisited[i][j]
                    && image[i][j] == target) {
                // 递归处理,不回溯
                dfs(image, i, j, newColor, target, isVisited);
            }
        }
    }
}

面试题 08.11. 硬币

面试题 08.11. 硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int waysToChange(int n) {
        // 完全背包,dp表示在i剩余时有多少种找法，组合，先物品后背包
        int[] dp = new int[n + 1];
        dp[0] = 1;
        int[] money = new int[] { 1, 5, 10, 25 };
        for (int i : money) {
            for (int j = i; j <= n; j++) {
                dp[j] = (dp[j] + dp[j - i]) % 1000000007;
            }
        }
        return dp[n];
    }
}

面试题 08.12. 八皇后

面试题 08.12. 八皇后

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
class Solution {
    public List<List<String>> solveNQueens(int n) {
        // 回溯
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        List<List<String>> result = new ArrayList<>();
        backTracking(result, board, new boolean[n], 0);
        return result;
    }

    public void backTracking(List<List<String>> result, char[][] board, boolean[] isSelected, int deep) {
        if (deep >= board.length) {
            // 加入答案
            List<String> temp = new ArrayList<>();
            for (char[] chars : board) {
                temp.add(new String(chars));
            }
            result.add(temp);
            return;
        }
        for (int j = 0; j < board.length; j++) {
            if (!isSelected[j] && isLegal(board, deep, j)) {
                board[deep][j] = 'Q';
                isSelected[j] = true;
                backTracking(result, board, isSelected, deep + 1);
                board[deep][j] = '.';
                isSelected[j] = false;
            }
        }
    }

    // 检查当前位置是否合法，检查斜线就好了，每行只选一个，行不用管，列可以通过isSelected是否选择来看
    public boolean isLegal(char[][] board, int row, int column) {
        // 左斜上
        int i = row, j = column;
        while (i >= 0 && j >= 0) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j--;
        }
        // 右斜上
        i = row;
        j = column;
        while (i >= 0 && j < board.length) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j++;
        }
        return true;
    }

}

10

面试题 10.01. 合并排序的数组

面试题 10.01. 合并排序的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        // 从大到小填充
        int t = A.length - 1;
        m -= 1;
        n -= 1;
        while (m >= 0 && n >= 0) {
            if (A[m] >= B[n]) {
                A[t--] = A[m--];
            } else {
                A[t--] = B[n--];
            }
        }
        // m就不动了，都是相对有序的，说明前面都比B数组第一个小了，顺序对了
        while (n >= 0) {
            A[t--] = B[n--];
        }
    }
}

面试题 10.02. 变位词组

面试题 10.02. 变位词组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 一个个去比很麻烦，可以用技巧比较，排序后新建字符串，看两个字符串是否相等，用HashMap保存是否出现过
        List<List<String>> result = new ArrayList<>();
        HashMap<String, Integer> map = new HashMap<>();
        for (String s : strs) {
            // 排序后转换为字符串
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String cur = new String(chars);
            // 看是否出现过，出现直接从map获取到reuslt对应的下表
            if (map.containsKey(cur)) {
                result.get(map.get(cur)).add(s);
            } else {
                List<String> temp = new ArrayList<>();
                temp.add(s);
                map.put(cur, result.size());
                result.add(temp);
            }
        }
        return result;
    }
}

感受到算法的魅力，暴力遍历字符串每位保存到hash看a-z的个数是否相等判断非常耗时间！！！1100ms -> 7ms

面试题 10.05. 稀疏数组搜索

面试题 10.05. 稀疏数组搜索

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int findString(String[] words, String s) {
        for(int i = 0;i<words.length;i++){
            if(words[i].equals(s)){
                return i;
            }
        }
        return -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
class Solution {
    public int findString(String[] words, String s) {
        // 用二分来做
        int left = 0;
        int right = words.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            while (mid > left && words[mid].compareTo("") == 0) {
                mid--;
            }
            if (s.compareTo(words[mid]) == 0) {
                return mid;
            }

            if (s.compareTo(words[mid]) < 0) {
                right = mid - 1;
            }

            if (s.compareTo(words[mid]) > 0) {
                left = mid + 1;
            }

        }
        return -1;
    }
}

面试题 10.09. 排序矩阵查找

面试题 10.09. 排序矩阵查找

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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            if (isCanFindRow(matrix, target, i)) {
                return true;
            }
        }
        return false;
    }

    // 横向查找
    public boolean isCanFindRow(int[][] matrix, int target, int row) {
        int left = 0, right = matrix[row].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] > target) {
                right = mid - 1;
            } else if (matrix[row][mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

还是突破不了到最优，不管了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 为空
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        // 只有一行
        else if (matrix.length == 1) {
            return isCanFindRow(matrix, target, 0);
        }
        // 只有一列
        else if (matrix[0].length == 1) {
            return isCanFindColumn(matrix, target, 0);
        }
        // 看在哪一行二分
        else {
            for (int i = 0; i < matrix.length; i++) {
                if (target == matrix[i][0] || target == matrix[i][matrix[0].length - 1]) {
                    return true;
                }
                if (target > matrix[i][0] && target < matrix[i][matrix[0].length - 1]) {
                    if (isCanFindRow(matrix, target, i)) {
                        return true;
                    }
                }
            }
            return false;
        }
    }

    // 横向查找
    public boolean isCanFindRow(int[][] matrix, int target, int row) {
        int left = 0, right = matrix[row].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] > target) {
                right = mid - 1;
            } else if (matrix[row][mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    // 竖向查找
    public boolean isCanFindColumn(int[][] matrix, int target, int column) {
        int left = 0, right = matrix.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[mid][column] > target) {
                right = mid - 1;
            } else if (matrix[mid][column] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

16

面试题 16.01. 交换数字

面试题 16.01. 交换数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] swapNumbers(int[] numbers) {
        // 第二个加到第一个位置 a+b b
        numbers[0] += numbers[1];
        // 第二个位置要为a，就要a+b-b，第一个位置减第二个位置
        numbers[1] = numbers[0] - numbers[1];
        // 第一个位置要为b,就要a+b-a，就是第一个位置减第二个位置
        numbers[0] -= numbers[1];

        //借助异或运算的特性，两个相同的数异或运算等于0，任何数异或0等于自身
        numbers[0] = numbers[0] ^ numbers[1];
        numbers[1] = numbers[0] ^ numbers[1];
        numbers[0] = numbers[0] ^ numbers[1];
        return numbers;
    }
}

面试题 16.02. 单词频率

面试题 16.02. 单词频率

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

    HashMap<String, Integer> map;

    public WordsFrequency(String[] book) {
        map = new HashMap<>();
        for (String s : book) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
    }

    public int get(String word) {
        return map.getOrDefault(word, 0);
    }
}

/**
 * Your WordsFrequency object will be instantiated and called as such:
 * WordsFrequency obj = new WordsFrequency(book);
 * int param_1 = obj.get(word);
 */

面试题 16.04. 井字游戏

面试题 16.04. 井字游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class Solution {
    public String tictactoe(String[] board) {
        // 这是N*N的棋盘，可以优化为原地操作的，但是感觉操作字符串好麻烦，charAt好麻烦
        int n = board[0].length();
        char[][] allBoard = new char[n][n];
        for (int i = 0; i < n; i++) {
            allBoard[i] = board[i].toCharArray();
        }
        boolean isEnd = isEnding(allBoard);
        String result = getWiner(allBoard, n);
        if (isEnd) {
            if (result == null) {
                // 平局
                return "Draw";
            } else {
                // 返回获胜者
                return result;
            }
        } else {
            if (result == null) {
                // 没有获胜者，未完成
                return "Pending";
            } else {
                // 返回获胜者
                return result;
            }
        }
    }

    // 是否结局
    public boolean isEnding(char[][] allBoard) {
        for (char[] chars : allBoard) {
            for (char c : chars) {
                if (c == ' ') {
                    return false;
                }
            }
        }
        return true;
    }

    // 是否有获胜的
    public String getWiner(char[][] allBoard, int n) {
        if (n == 1) {
            if (allBoard[0][0] == ' ') {
                return null;
            } else {
                return String.valueOf(allBoard[0][0]);
            }
        }

        // 按行查看是否有某一行全一样
        for (int i = 0; i < n; i++) {
            char c = allBoard[i][0];
            // 为空跳过本轮，一定没结果
            if (c == ' ') {
                continue;
            }
            for (int j = 1; j < n; j++) {
                if (allBoard[i][j] != c) {
                    break;
                }
                if (j == n - 1) {
                    return String.valueOf(c);
                }
            }
        }
        // 按列查看是否有某一列全一样
        for (int j = 0; j < n; j++) {
            char c = allBoard[0][j];
            // 为空跳过本轮，一定没结果
            if (c == ' ') {
                continue;
            }
            for (int i = 1; i < n; i++) {
                if (allBoard[i][j] != c) {
                    break;
                }
                if (i == n - 1) {
                    return String.valueOf(c);
                }
            }
        }
        // 按左下斜线查看是否全一样
        char c1 = allBoard[0][n - 1];
        if (c1 != ' ') {
            for (int i = 1; i < n; i++) {
                if (allBoard[i][n - i - 1] != c1) {
                    break;
                }
                if (i == n - 1) {
                    return String.valueOf(c1);
                }
            }
        }

        // 按右下斜线查看是否全一样
        char c2 = allBoard[0][0];
        if (c2 != ' ') {
            for (int j = 1; j < n; j++) {
                if (allBoard[j][j] != c2) {
                    break;
                }
                if (j == n - 1) {
                    return String.valueOf(c2);
                }
            }
        }

        return null;
    }
}

面试题 16.06. 最小差

面试题 16.06. 最小差

暴力会超时间限制，注意int范围

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
class Solution {
    public int smallestDifference(int[] a, int[] b) {
        // 先排序
        Arrays.sort(a);
        Arrays.sort(b);
        // 双指针,小的跟小的减，大的跟大的减，这样能得出最小的
        int i = 0, j = 0, result = Integer.MAX_VALUE;
        while (i < a.length && j < b.length) {
            // 注意溢出
            int temp = Math.abs(a[i] - b[j]);
            result = Math.min(result, temp >= 0 ? temp : Integer.MAX_VALUE);
            // i指向比j指向小，移动i逼近j
            if (a[i] < b[j]) {
                i++;
            }
            // i指向比j指向大，移动j逼近i
            else if (a[i] > b[j]) {
                j++;
            }
            // 相等直接break，0肯定最小
            else {
                break;
            }
        }
        return result;
    }
}

面试题 16.07. 最大数值

面试题 16.07. 最大数值

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maximum(int a, int b) {
        //计算a-b的符号位，符号位决定了a和b的大小关系
        long diff = (long) a - (long) b;
        //long是64位，右移63位得到符号位，&1是只保留1为，k=0说明a-b>=0，反正为1说明a-b<0
        int k = (int) ((diff >> 63) & 1);
        //最后就跟a和b做运算返回
        return a * (1 - k) + b * k;
    }
}

面试题 16.10. 生存人数

面试题 16.10. 生存人数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
        // 最小选择为1900，最大选择为2000，因为出生不会超过2000，那么选择超过2000不会有任何增加，只会减少，1900之前选择没意义，都还没人出生呢
        int[] livePeopleCount = new int[2001];
        for (int i = 0; i < birth.length; i++) {
            for (int j = birth[i]; j <= death[i]; j++) {
                livePeopleCount[j]++;
            }
        }
        // 统计
        int min = livePeopleCount[1900], year = 1900;
        for (int i = 1901; i <= 2000; i++) {
            if (livePeopleCount[i] > min) {
                min = livePeopleCount[i];
                year = i;
            }
        }
        return year;
    }
}

优化

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
class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
        // 最小选择为1900，最大选择为2000，因为出生不会超过2000，那么选择超过2000不会有任何增加，只会减少，1900之前选择没意义，都还没人出生呢
        // help数组是帮助统计有多少人存活的，比如要统计1910有多少人存活就将1900-1910的help数组每个元素求和
        // 当年生当年死亡应该算当年+1的，死亡影响下一年
        int[] help = new int[2002];
        for (int i = 0; i < birth.length; i++) {
            // 出生年+1
            help[birth[i]]++;
            // (死亡年+1)-1,影响下一年
            help[death[i] + 1]--;
        }
        // 前缀合
        for (int i = 1900; i <= 2000; i++) {
            help[i] += help[i - 1];
        }
        int max = 0, result = 0;
        for (int i = 1900; i <= 2000; i++) {
            if (help[i] > max) {
                result = i;
                max = help[i];
            }
        }
        return result;
    }
}

面试题 16.11. 跳水板

面试题 16.11. 跳水板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        // 一开始全用小的，不用大的，逐渐减少用小的数量，增大用大的数量，每次求和就是结果了
        if (k == 0) {
            return new int[0];
        }
        if (shorter == longer) {
            return new int[] { k * shorter };
        }
        int[] result = new int[k + 1];
        int a = k, b = 0, t = 0;
        while (b <= k) {
            result[t++] = a * shorter + b * longer;
            a--;
            b++;
        }
        return result;
    }
}

面试题 16.15. 珠玑妙算

面试题 16.15. 珠玑妙算

统计猜中位置的数量，还统计颜色出现的次数，看出现相同颜色的次数是多少次，出现相同颜色的次数-猜中位置的次数就是伪猜中的次数

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 Solution {
    public int[] masterMind(String solution, String guess) {
        int guessCurrent = 0, guessColorCurrent = 0;
        int[][] colors = new int[4][2];
        for (int i = 0; i < 4; i++) {
            char c1 = solution.charAt(i), c2 = guess.charAt(i);
            if (c1 == c2) {
                guessCurrent++;
            }
            switch (c1) {
                case 'R':
                    colors[0][0]++;
                    break;
                case 'Y':
                    colors[1][0]++;
                    break;
                case 'G':
                    colors[2][0]++;
                    break;
                case 'B':
                    colors[3][0]++;
                    break;
                default:
                    break;
            }
            switch (c2) {
                case 'R':
                    colors[0][1]++;
                    break;
                case 'Y':
                    colors[1][1]++;
                    break;
                case 'G':
                    colors[2][1]++;
                    break;
                case 'B':
                    colors[3][1]++;
                    break;
                default:
                    break;
            }
        }
        for (int i = 0; i < 4; i++) {
            if (colors[i][0] != 0 && colors[i][1] != 0) {
                guessColorCurrent += (colors[i][0] >= colors[i][1] ? colors[i][1] : colors[i][0]);
            }
        }
        return new int[] { guessCurrent, guessColorCurrent - guessCurrent };
    }
}

面试题 16.16. 部分排序

面试题 16.16. 部分排序

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
class Solution {
    public int[] subSort(int[] array) {
        // 用例：[1,2,4,7,10,11,7,12,6,7,16,18,19]，结果：[3,9]
        // 贪心+双指针
        int len = array.length;
        if (len <= 1) {
            return new int[] { -1, -1 };
        }

        // 确认右指针最后的位置
        // 观察最后右指针指向的是12要还原的位置，也就是找到乱序里面的最大值，后面比他小的第要更新index
        int end = -1, max = array[0];
        for (int i = 1; i < len; i++) {
            if (array[i] >= max) {
                max = array[i];
            } else {
                end = i;
            }
        }

        // 确认左指针最后的位置
        int start = -1, min = array[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            if (array[i] <= min) {
                min = array[i];
            } else {
                start = i;
            }
        }

        if (start == -1 || end == -1) {
            return new int[] { -1, -1 };
        }

        return new int[] { start, end };
    }
}

试题 16.17. 连续数列

试题 16.17. 连续数列

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        //贪心
        int temp = nums[0], result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            temp+=nums[i];
            temp = nums[i] > temp ? nums[i] : temp;
            result = Math.max(result,temp);
        }
        return result;
    }
}

面试题 16.18. 模式匹配

面试题 16.18. 模式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class Solution {
    public boolean patternMatching(String pattern, String value) {
        // 看官方题解，很巧妙
        // 先统计有多少个a和b，保证a比b多是优化
        int count_a = 0, count_b = 0;
        for (char c : pattern.toCharArray()) {
            if (c == 'a') {
                count_a++;
            } else {
                count_b++;
            }
        }

        // 保证a比b多是优化，可以减少遍历次数，并且不会进入死循环，如果全b下面循环可能卡死
        if (count_a <= count_b) {
            char[] array = pattern.toCharArray();
            for (int i = 0; i < pattern.length(); i++) {
                if (array[i] == 'a') {
                    array[i] = 'b';
                } else {
                    array[i] = 'a';
                }
            }

            pattern = new String(array);

            // 交换count_a和count_b
            // int temp = count_a;
            // count_a = count_b;
            // count_b = temp;
            count_a ^= count_b;
            count_b ^= count_a;
            count_a ^= count_b;
        }

        // 为空可以直接返回
        if (value.length() == 0) {
            // a全为null就可以了，看有没有b就行
            return count_b == 0;
        }
        // 到这里说明value不为""，但是pattern为""
        if (pattern.length() == 0) {
            return false;
        }

        // len_a表示统计a的长度，a的长度乘上a的个数肯定不能超过value的长度
        for (int len_a = 0; len_a * count_a <= value.length(); len_a++) {
            // 看除去a花费掉的长度剩下的长度是否够b使用
            int balance_len = value.length() - len_a * count_a;
            if ((count_b == 0 && balance_len == 0) || (count_b != 0 && balance_len % count_b == 0)) {
                // 符合条件,b的数量为0剩余也要为0，b的数量不为0，那么剩余长度要够b整除
                int len_b = count_b != 0 ? balance_len / count_b : 0;
                // 下面开始切分字符串看是否满足要求
                boolean isCurrent = true;
                // 保存划分出来的a和b对应的字符串
                String str_a = "", str_b = "";
                // 当前划分要的index
                int index = 0;
                for (char c : pattern.toCharArray()) {
                    if (c == 'a') {
                        // 还没选择a就直接切分赋值给a，否则要跟上次选择结果比较是否一样
                        if (str_a.length() == 0) {
                            str_a = value.substring(index, index + len_a);
                            index += len_a;
                        } else {
                            String temp = value.substring(index, index + len_a);
                            if (!temp.equals(str_a)) {
                                isCurrent = false;
                                break;
                            }
                            index += len_a;
                        }
                    } else {
                        // 还没选择b就直接切分赋值给b，否则要跟上次选择结果比较是否一样
                        if (str_b.length() == 0) {
                            str_b = value.substring(index, index + len_b);
                            index += len_b;
                        } else {
                            String temp = value.substring(index, index + len_b);
                            if (!temp.equals(str_b)) {
                                isCurrent = false;
                                break;
                            }
                            index += len_b;
                        }
                    }
                }
                // 看是不是找到结果了，提前返回，这里的坑是a和b表示的字符串要不同，不然全a才对啊
                if (isCurrent && !str_a.equals(str_b)) {
                    return true;
                }
            }
        }

        return false;
    }
}

面试题 16.19. 水域大小

面试题 16.19. 水域大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
    // 广搜和深搜都可以
    public int[] pondSizes(int[][] land) {
        // 深搜
        int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 },
                { 1, 1 } };
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                // 为水域
                if (land[i][j] == 0) {
                    int[] count = new int[] { 0 };
                    dfs(land, i, j, count, dirs);
                    list.add(count[0]);
                }
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        Arrays.sort(result);
        return result;

        // 广搜
        // return bfs(land);
    }

    // 深搜
    public void dfs(int[][] land, int x, int y, int[] count, int[][] dirs) {
        count[0]++;
        // 统计完变为陆地
        land[x][y] = 1;
        // 看四周，这里斜对角也算的
        for (int[] dir : dirs) {
            int i = x + dir[0], j = y + dir[1];
            // 范围内并且为水域递归深搜
            if (i >= 0 && i < land.length && j >= 0 && j < land[0].length && land[i][j] == 0) {
                dfs(land, i, j, count, dirs);
            }
        }
    }

    // 广搜
    public int[] bfs(int[][] land) {
        // 方向
        int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 },
                { 1, 1 } };
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                // 为水域
                if (land[i][j] == 0) {
                    int count = 0;
                    Queue<int[]> queue = new ArrayDeque<>();
                    queue.add(new int[] { i, j });
                    land[i][j] = 1;
                    while (!queue.isEmpty()) {
                        int[] temp = queue.poll();
                        land[temp[0]][temp[1]] = 1;
                        count++;
                        // 看四周，这里斜对角也算的
                        for (int[] dir : dirs) {
                            int x = temp[0] + dir[0], y = temp[1] + dir[1];
                            // 范围内并且为水域加入队列广搜
                            if (x >= 0 && x < land.length && y >= 0 && y < land[0].length && land[x][y] == 0) {
                                queue.add(new int[] { x, y });
                                // 在加入队列就要入队，不然有些点取出再置为陆地会被前面的点处理的时候入队，就重复入队了
                                land[x][y] = 1;
                            }
                        }
                    }
                    // 广搜一个完成，加入结果
                    list.add(count);
                }
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        Arrays.sort(result);
        return result;
    }
}

面试题 16.20. T9键盘

面试题 16.20. T9键盘

最下面的解法时间复杂度还是很高

下面递归超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class Solution {
    public List<String> getValidT9Words(String num, String[] words) {
        // 判断某个元素是否存在
        HashSet<String> dic = new HashSet<>();
        for (String s : words) {
            dic.add(s);
        }
        //递归
        List<String>result = new ArrayList<>();
        if(num==null){
            return result;
        }
        backTracking(result,dic,0,num,new StringBuilder());
        return result;
    }

    // 递归获取所有可能
    public void backTracking(List<String> result, HashSet<String> dic, int deep, String num, StringBuilder builder) {
        if (deep >= num.length()) {
            // 检查是否存在，加入集合
            String s = builder.toString();
            if (dic.contains(s)) {
                result.add(s);
            }
            return;
        }
        // 取出当前的按键字符
        char press = num.charAt(deep);
        switch (press) {
            // 不包含0和1的数字
            case '2':
                for (char temp = 'a'; temp <= 'c'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            case '3':
                for (char temp = 'd'; temp <= 'f'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            case '4':
                for (char temp = 'g'; temp <= 'i'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            case '5':
                for (char temp = 'j'; temp <= 'l'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            case '6':
                for (char temp = 'm'; temp <= 'o'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            case '7':
                for (char temp = 'p'; temp <= 's'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            case '8':
                for (char temp = 't'; temp <= 'v'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            case '9':
                for (char temp = 'w'; temp <= 'z'; temp++) {
                    builder.append(temp);
                    // 递归
                    backTracking(result, dic, deep + 1, num, builder);
                    // 回溯
                    builder.deleteCharAt(deep);
                }
                break;
            default:
                break;
        }
    }
}

从words回构

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
class Solution {
    // 根据给定数字构建时间复杂度很高，根据给定words构建按键看是不是一样
    public List<String> getValidT9Words(String num, String[] words) {
        List<String> result = new ArrayList<>();
        for (String s : words) {
            StringBuilder builder = new StringBuilder();
            for (char c : s.toCharArray()) {
                builder.append(getNum(c));
            }
            if (builder.toString().equals(num)) {
                result.add(s);
            }
        }
        return result;
    }

    public int getNum(char c) {
        if (c >= 'a' && c <= 'c') {
            return 2;
        } else if (c >= 'd' && c <= 'f') {
            return 3;
        } else if (c >= 'g' && c <= 'i') {
            return 4;
        } else if (c >= 'j' && c <= 'l') {
            return 5;
        } else if (c >= 'm' && c <= 'o') {
            return 6;
        } else if (c >= 'p' && c <= 's') {
            return 7;
        } else if (c >= 't' && c <= 'v') {
            return 8;
        } else if (c >= 'w' && c <= 'z') {
            return 9;
        } else {
            return -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
class Solution {
    // 根据给定数字构建时间复杂度很高，根据给定words构建按键看是不是一样
    public List<String> getValidT9Words(String num, String[] words) {
        List<String> result = new ArrayList<>();
        for (String s : words) {
            boolean isCurrent = true;
            for (int i = 0; i < s.length(); i++) {
                if (getNum(s.charAt(i)) != num.charAt(i)) {
                    isCurrent = false;
                    break;
                }
            }
            // 看是否正确
            if (isCurrent) {
                result.add(s);
            }
        }
        return result;
    }

    public char getNum(char c) {
        if (c >= 'a' && c <= 'c') {
            return '2';
        } else if (c >= 'd' && c <= 'f') {
            return '3';
        } else if (c >= 'g' && c <= 'i') {
            return '4';
        } else if (c >= 'j' && c <= 'l') {
            return '5';
        } else if (c >= 'm' && c <= 'o') {
            return '6';
        } else if (c >= 'p' && c <= 's') {
            return '7';
        } else if (c >= 't' && c <= 'v') {
            return '8';
        } else if (c >= 'w' && c <= 'z') {
            return '9';
        } else {
            return '0';
        }
    }
}

面试题 16.21. 交换和

面试题 16.21. 交换和

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
class Solution {
    public int[] findSwapValues(int[] array1, int[] array2) {
        // 记录两个数组是否存在某个元素
        HashSet<Integer> set2 = new HashSet<>();
        // 求和求差，感觉会超范围，发现用例没超
        int sum1 = 0;
        int sum2 = 0;
        for (int i : array1) {
            sum1 += i;
        }
        for (int i : array2) {
            set2.add(i);
            sum2 += i;
        }
        int balance = Math.abs(sum1 - sum2);
        if (balance % 2 != 0) {
            return new int[0];
        }
        balance /= 2;
        // 遍历其中一个数组，遍历第一个，发现用两个set时间复杂度变高，排序取数组相同不再比较去重，发现时间复杂度上升了
        for (int i : array1) {
            if (set2.contains(i - balance)) {
                return new int[] { i, i - balance };
            }
            if (set2.contains(i + balance)) {
                return new int[] { i, i + balance };
            }
        }
        return new int[0];
    }
}

面试题 16.24. 数对和

面试题 16.24. 数对和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> pairSums(int[] nums, int target) {
        // 排序后双指针
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int left = 0, right = nums.length - 1;
        while (left < right) {
            // 看两数和跟target的关系，小了让left往右走，反之让right往左走，相等加入结果集合
            int sum = nums[left] + nums[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                result.add(Arrays.asList(nums[left], nums[right]));
                // 避免重复，左右同时移动
                left++;
                right--;
            }
        }
        return result;
    }
}

面试题 16.25. LRU 缓存

面试题 16.25. LRU 缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
class LRUCache {

    // 容量
    int capacity;
    // 哈希表
    HashMap<Integer, Node<Integer, Integer>> map;
    // LruCache双向链表
    MyLRUCacheLinkedList<Integer, Integer> lruCacheLinkedList;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        lruCacheLinkedList = new MyLRUCacheLinkedList<>();
        map = new HashMap<>();
    }

    /**
     * 获取
     *
     * @param key 键
     * @return value
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            Node<Integer, Integer> node = map.get(key);
            // 移除旧位置
            lruCacheLinkedList.remove(node);
            // 放入最近访问
            lruCacheLinkedList.offerLast(node);
            return node.value;
        } else {
            return -1;
        }
    }

    /**
     * 放入
     *
     * @param key   键
     * @param value 值
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            // 移除旧位置
            lruCacheLinkedList.remove(node);
            // 放入最近访问
            lruCacheLinkedList.offerLast(node);
        } else {
            Node<Integer, Integer> node = new Node<>();
            node.key = key;
            node.value = value;
            lruCacheLinkedList.offerLast(node);
            map.put(key, node);
            if (lruCacheLinkedList.size > capacity) {
                // 移除最旧的
                Node<Integer, Integer> poll = lruCacheLinkedList.pollFirst();
                map.remove(poll.key);
            }
        }
    }

    /**
     * 双向链表节点
     *
     * @param <K> 键类型
     * @param <V> 值类型
     */
    public static class Node<K, V> {
        Node<K, V> pre;
        Node<K, V> last;
        K key;
        V value;

        public Node() {
        }

        public Node(Node<K, V> pre, Node<K, V> last) {
            this.pre = pre;
            this.last = last;
        }

        public Node(Node<K, V> pre, Node<K, V> last, K key, V value) {
            this.pre = pre;
            this.last = last;
            this.key = key;
            this.value = value;
        }
    }

    public static class MyLRUCacheLinkedList<K, V> implements IMyLRUCacheLinkedList<Node<K, V>> {

        // 头
        Node<K, V> head = new Node<>();
        // 尾
        Node<K, V> tail = new Node<>();
        // 节点数量
        int size;

        public MyLRUCacheLinkedList() {
            // 初始头尾相连
            head.last = tail;
            tail.pre = head;
            size = 0;
        }

        @Override
        public void remove(Node<K, V> kvNode) {
            // 不会为空，外部拿不到为空的，因为有头尾哨兵节点
            Node<K, V> kvNode1 = kvNode.pre;
            Node<K, V> kvNode2 = kvNode.last;
            kvNode1.last = kvNode2;
            kvNode2.pre = kvNode1;
            size--;
        }

        @Override
        public void offerLast(Node<K, V> kvNode) {
            Node<K, V> kvNode1 = tail.pre;
            kvNode1.last = kvNode;
            kvNode.pre = kvNode1;
            kvNode.last = tail;
            tail.pre = kvNode;
            size++;
        }

        @Override
        public Node<K, V> pollFirst() {
            if (head.last == tail) {
                return null;
            } else {
                // 移除节点
                Node<K, V> poll = head.last;
                head.last = poll.last;
                poll.last.pre = head;
                size--;
                return poll;
            }
        }
    }

    /**
     * 表示LRUCache存储的双向链表的一些操作方法
     */
    public interface IMyLRUCacheLinkedList<E> {
        void remove(E e);

        void offerLast(E e);

        E pollFirst();
    }

}

面试题 16.26. 计算器

面试题 16.26. 计算器

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
class Solution {
    public int calculate(String s) {
        // 这里没有括号的，只有+-*/四种符号
        int index = 0, lastSolve = 0;
        List<String> solve = new ArrayList<>();
        // 划分每个部分出来先
        while (index < s.length()) {
            char c = s.charAt(index);
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                String str = s.substring(lastSolve, index).trim();
                if (!str.equals("")) {
                    solve.add(str);
                    solve.add(String.valueOf(c));
                }
                lastSolve = index + 1;
            }
            index++;
        }
        // 最后一个
        String latPart = s.substring(lastSolve, index).trim();
        if (!latPart.equals("")) {
            solve.add(latPart);
        }
        // 栈模拟，后面+-需要正序，*/逆序取出，用双端更合适
        Deque<String> stack = new LinkedList<>();
        for (int i = 0; i < solve.size(); i++) {
            String str = solve.get(i);
            // 为乘或除需要抛出先处理
            if (str.equals("*") || str.equals("/")) {
                int first = Integer.valueOf(stack.pollLast());
                int second = Integer.valueOf(solve.get(i + 1));
                if (str.equals("*")) {
                    stack.offerLast(String.valueOf(first * second));
                } else {
                    stack.offerLast(String.valueOf(first / second));
                }
                i++;
            } else {
                stack.offerLast(str);
            }
        }

        // 不是只剩一个就需要继续处理
        while (stack.size() != 1) {
            int first = Integer.valueOf(stack.pollFirst());
            String str = stack.pollFirst();
            int second = Integer.valueOf(stack.pollFirst());
            if (str.equals("+")) {
                stack.offerFirst(String.valueOf(first + second));
            } else {
                stack.offerFirst(String.valueOf(first - second));
            }
        }

        return Integer.valueOf(stack.pollLast());
    }
}

优化最后的计算过程，去掉判空，因为题目说一定符合计算要求，考虑去掉空格就好

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
class Solution {
    public int calculate(String s) {
        // 这里没有括号的，只有+-*/四种符号
        int index = 0, lastSolve = 0;
        List<String> solve = new ArrayList<>();
        // 划分每个部分出来先
        while (index < s.length()) {
            char c = s.charAt(index);
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                String str = s.substring(lastSolve, index).trim();
                solve.add(str);
                solve.add(String.valueOf(c));
                lastSolve = index + 1;
            }
            index++;
        }
        // 最后一个
        String latPart = s.substring(lastSolve, index).trim();
        solve.add(latPart);
        // 栈模拟，后面+-需要正序，*/逆序取出，用双端更合适
        Deque<String> stack = new LinkedList<>();
        for (int i = 0; i < solve.size(); i++) {
            String str = solve.get(i);
            // 为乘或除需要抛出先处理
            if (str.equals("*") || str.equals("/")) {
                int first = Integer.valueOf(stack.pollLast());
                int second = Integer.valueOf(solve.get(i + 1));
                if (str.equals("*")) {
                    stack.offerLast(String.valueOf(first * second));
                } else {
                    stack.offerLast(String.valueOf(first / second));
                }
                i++;
            } else {
                stack.offerLast(str);
            }
        }

        // 不为空继续处理
        int result = Integer.valueOf(stack.pollFirst());
        while (!stack.isEmpty()) {
            String str = stack.pollFirst();
            int second = Integer.valueOf(stack.pollFirst());
            if (str.equals("+")) {
                result += second;
            } else {
                result -= second;
            }
        }

        return result;
    }
}

感觉不用栈模拟，直接在List上遍历处理应该也可以，但还是栈直接，直接遍历操作list容易写错

17

面试题 17.01. 不用加号的加法

面试题 17.01. 不用加号的加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int add(int a, int b) {
        // 前置只是就是异或运算，异或运算是一种无符号进位的加法，那加法就是无符号进位+进位就行，又有加号又要不用加处理就是循环处理了，知道其中一个数为0
        while (b != 0) {
            // 进位信息
            int temp = (a & b) << 1;
            // 异或运算
            a = a ^ b;
            // 又要相加，但是不能用加法，赋值继续循环
            b = temp;
        }
        return a;
    }
}

面试题 17.04. 消失的数字

面试题 17.04. 消失的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingNumber(int[] nums) {
        int[] hash = new int[nums.length + 1];
        for (int i : nums) {
            hash[i]++;
        }
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

面试题 17.05. 字母与数字

面试题 17.05. 字母与数字

dp超时

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
class Solution {
    public String[] findLongestSubarray(String[] array) {
        // 原本用二维dp，dp[i][j]表示从i到j的字母的个数-数字的个数的差，发现从底部往上推刚好就是下层决定上层，变为一维dp就好，然后贪心保存最长值和开始结束下标
        // 遇到相等的也需要更新，因为需要保存左端点下标最小的子数组
        int start = 0, end = -1, maxLen = 0;
        int[] dp = new int[array.length];
        // 从底往上推
        for (int i = array.length - 1; i >= 0; i--) {
            for (int j = i; j < array.length; j++) {
                // 看是字母还是数字下层进行相应操作就行，这里一维直接在数组操作
                //看当前新加的一个是什么，就一个，直接取出，
                char c = array[i].charAt(0);
                if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                    dp[j] += 1;
                } else if (c >= '0' && c <= '9') {
                    dp[j] -= 1;
                }
                // 差值为0就是相等
                if (dp[j] == 0 && j - i + 1 >= maxLen) {
                    start = i;
                    end = j;
                    maxLen = j - i + 1;
                }
            }
        }
        // 组织答案
        String[] result = new String[maxLen];
        int index = 0;
        for (int i = start; i <= end; i++) {
            result[index++] = array[i];
        }
        return result;
    }
}

前缀和

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
class Solution {
    public String[] findLongestSubarray(String[] array) {
        // 前缀和
        // start为目标区间开始下标，maxLen为长度，temp表示当前从0到当前位置的串的差值
        int start = 0, maxLen = 0, temp = 0;
        // map存储字母和数字的项的差值要去寻找的下标，一开始存0
        // 0，后面比如差值为5，前面也有一个差值为5的，说明差值从那里的导致的，从下个位置开始到当前就是0差值，
        // 不然不会导致差值一样，为了方便直接在map存储查找区间下标
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        // 遍历
        for (int i = 0; i < array.length; i++) {
            char c = array[i].charAt(0);
            if (c >= '0' && c <= '9') {
                temp--;
            } else {
                temp++;
            }
            // 看前面是否出现过这个差值
            if (map.containsKey(temp)) {
                int t = map.get(temp);
                if (i - t + 1 > maxLen) {
                    maxLen = i - t + 1;
                    start = t;
                }
            } else {
                // 为了方便直接在map存储查找区间下标
                map.put(temp, i + 1);
            }
        }
        // 组织答案
        String[] result = new String[maxLen];
        // public static void arraycopy(Object src, int srcPos, Object dest, int
        // destPos, int length)
        System.arraycopy(array, start, result, 0, maxLen);
        return result;
    }
}

面试题 17.06. 2出现的次数

面试题 17.06. 2出现的次数

数位dp

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
class Solution {

    int[][][] memory;

    // 数位dp题目，当然也有数学技巧，但没看过想不出来其实
    public int numberOf2sInRange(int n) {
        String target = String.valueOf(n);
        // 这里的前两个维度的长度都为target的长度，第二个维度是因为每个位置都为2是最大的情况
        memory = new int[target.length()][target.length()][2];

        // 初始化为-1，后续不为-1说明搜索过
        for (int[][] temp : memory) {
            for (int[] init : temp) {
                Arrays.fill(init, -1);
            }
        }

        return digitDp(0, target, 0, false);
    }

    // digit为当前处理到第几位，count为传递给下一次递归的当前统计到的2的个数，target为求到的最大数字转换为字符串
    public int digitDp(int digit, String target, int count, boolean isCanSelectRandom) {
        if (digit == target.length()) {
            return count;
        }

        // 看记忆化搜索是否搜索过，比如低数位搜索过，下次就直接取出搜索结果就行，避免重复搜索
        if (memory[digit][count][isCanSelectRandom ? 1 : 0] != -1) {
            return memory[digit][count][isCanSelectRandom ? 1 : 0];
        }

        // 看是否可以任选，如果当前可以任选就可以选择0-9，不然就看当前的位置的值是多少，最多只能选择到那个值
        int limit = isCanSelectRandom ? 9 : target.charAt(digit) - '0';

        int res = 0;

        for (int i = 0; i <= limit; i++) {
            int cnt = count + ((i == 2) ? 1 : 0);
            // 递归，下轮的是否任选取决于当前是否可以任选并且当前这个数是否小于限制值
            res += digitDp(digit + 1, target, cnt, isCanSelectRandom || i < limit);
        }

        // 保存搜索结果
        memory[digit][count][isCanSelectRandom ? 1 : 0] = res;

        return res;

    }
}

面试题 17.07. 婴儿名字

面试题 17.07. 婴儿名字

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
class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {

        // 先构建并查集
        Disjoint disJoint = new Disjoint();
        for (String s : synonyms) {
            int index = s.indexOf(',');
            String u = s.substring(1, index);
            String v = s.substring(index + 1, s.length() - 1);
            disJoint.join(u, v);
        }

        // 处理名字和频率
        HashMap<String, Integer> dic = new HashMap<>();
        for (String s : names) {
            int index = s.indexOf('(');
            int freq = Integer.valueOf(s.substring(index + 1, s.length() - 1));
            String father = disJoint.find(s.substring(0, index));
            // 由于先处理了之间的图关系，这里父亲一定是最远的root
            dic.put(father, dic.getOrDefault(father, 0) + freq);
        }

        // 组织答案
        String[] result = new String[dic.size()];
        int index = 0;
        for (Map.Entry<String, Integer> entry : dic.entrySet()) {
            StringBuilder builder = new StringBuilder();
            builder.append(entry.getKey());
            builder.append('(');
            builder.append(entry.getValue());
            builder.append(')');
            result[index++] = builder.toString();
        }

        return result;
    }

    class Disjoint {
        // 并查集变种，用数组表示很复杂，这里用HashMap，映射名字和名字之间的父亲关系
        HashMap<String, String> parents = new HashMap<>();

        public String find(String name) {
            // 看是否存在，不存在就先加入
            if (!parents.containsKey(name)) {
                parents.put(name, name);
            }
            String father = parents.get(name);
            // 寻找到的父亲和自己相等就是根节点了了，返回
            if (!father.equals(name)) {
                father = find(father);
                // 路径压缩
                parents.put(name, father);
            }
            return father;
        }

        public void join(String u, String v) {
            u = find(u);
            v = find(v);
            int compare = u.compareTo(v);
            if (compare == 0) {
                // 相等不处理
                return;
            } else if (compare < 0) {
                // 字典顺序，u先
                parents.put(v, u);
            } else {
                parents.put(u, v);
            }
        }
    }
}

面试题 17.08. 马戏团人塔

面试题 17.08. 马戏团人塔

dp超时

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
class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int count = height.length;
        int[][] people = new int[count][2];
        for (int i = 0; i < count; i++) {
            people[i][0] = height[i];
            people[i][1] = weight[i];
        }
        // 按照高度排序，从小到大
        Arrays.sort(people, (int[] o1, int[] o2) -> {
            return o1[0] - o2[0];
        });
        // dp二维表示i->j能放多少个，下面一维优化
        int[] dp = new int[count];
        // 初始全为1，肯定能放一个
        Arrays.fill(dp, 1);
        for (int i = 0; i < count; i++) {
            // 跟自己没必要比较了，肯定能放一个
            for (int j = 0; j < i; j++) {
                // 比之前的重可以放下面，看是自己大还是哪个加上1大,身高一样排除掉
                if (people[i][1] > people[j][1] && people[i][0] != people[j][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        // 看哪个最大
        int max = 0;
        for (int i : dp) {
            max = Math.max(max, i);
        }
        return max;
    }
}

优化，贪心（LIS，最长递增子序列）+二分

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
class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int count = height.length;
        int[][] people = new int[count][2];
        for (int i = 0; i < count; i++) {
            people[i][0] = height[i];
            people[i][1] = weight[i];
        }

        // 按照身高升序排列，若身高相同，按体重降序排列
        Arrays.sort(people, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

        // arr存储长度为i+1的LIS的最小末尾
        int[] arr = new int[count];
        // 初始化，长度为1的最长递增序列的最小末尾就是第一个人的体重
        arr[0] = people[0][1];
        // cur记录当前递增序列的最大长度
        int cur = 1;
        // 遍历，更新arr
        // 对于任意长度的 LIS，其末尾值越小，越容易被后续的元素扩展。
        for (int i = 1; i < count; i++) {
            int next = people[i][1];
            // 下一个体重比arr记录的所有值大（看最长，也就是cur-1,cur为长度的值就行，前面肯定比这个小的）
            if (next > arr[cur - 1]) {
                arr[cur] = next;
                cur++;
            }
            // 出现小的体重，寻找可以替换的较大的 arr[j] 值，从而维护 LIS 的最优状态
            else {
                int index = binarySearch(arr, next, cur);
                // cur不用变，回头找的长度肯定不会超出，cur，这里好细，但是可以更新arr的值
                arr[index] = next;
            }
        }

        return cur;
    }

    // 二分查找，寻找比目标值大于等于的位置
    public int binarySearch(int[] arr, int target, int cur) {
        int left = 0, right = cur - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

面试题 17.09. 第 k 个数

面试题 17.09. 第 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
class Solution {
    public int getKthMagicNumber(int k) {
        // 小顶堆实现，哈希去重
        PriorityQueue<Long> queue = new PriorityQueue<>();
        HashSet<Long> hash = new HashSet<>();
        // 一开始1放进去
        queue.offer(1L);
        hash.add(1L);
        // 要乘上的因子
        int[] factors = new int[] { 3, 5, 7 };
        // 结果
        int result = 0;
        // 遍历到k
        for (int i = 0; i < k; i++) {
            long cur = queue.poll();
            result = (int) cur;
            // 乘上因子，没出现过就加入队列
            for (int t : factors) {
                long temp = cur * t;
                if (hash.add(temp)) {
                    queue.offer(temp);
                }
            }
        }
        return result;
    }
}

动态规划优化

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
class Solution {
    public int getKthMagicNumber(int k) {
        // 动态规划优化
        // dp[i]表示第i大的是哪个数字
        int[] dp = new int[k + 1];
        // 初始化
        dp[1] = 1;
        // 三个指针，分别指向乘上3、5、7可用的最小可能数字(下标)，每轮选取一个最小的数字
        int p3 = 1, p5 = 1, p7 = 1;
        for (int i = 2; i <= k; i++) {
            int num3 = dp[p3] * 3, num5 = dp[p5] * 5, num7 = dp[p7] * 7;
            // 选取最小的
            dp[i] = Math.min(Math.min(num3, num5), num7);
            // 遇到相等的跳过，避免重复
            if (dp[i] == num3) {
                p3++;
            }
            if (dp[i] == num5) {
                p5++;
            }
            if (dp[i] == num7) {
                p7++;
            }
        }
        return dp[k];
    }
}

面试题 17.10. 主要元素

面试题 17.10. 主要元素

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
class Solution {
    public int majorityElement(int[] nums) {
        // 可以哈希，要时间复杂度就是摩尔投票了
        if (nums.length == 0) {
            return -1;
        }
        int result = nums[0], flag = 1;
        for (int i = 1; i < nums.length; i++) {
            // 有人相同就支持，+1，不然就-1，当为0票数换人，最后超过一半的肯定当选
            if (nums[i] == result) {
                flag++;
            } else {
                flag--;
            }
            if (flag == 0) {
                flag = 1;
                result = nums[i];
            }
        }
        // 检查result是否超过一半
        int count = 0;
        for (int i : nums) {
            if (i == result) {
                count++;
            }
        }
        if (count <= nums.length / 2) {
            return -1;
        }
        return result;
    }
}

面试题 17.11. 单词距离

面试题 17.11. 单词距离

暴力，后面再优化吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        List<Integer> first = new ArrayList<>();
        List<Integer> second = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                first.add(i);
            }
        }
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word2)) {
                second.add(i);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i : first) {
            for (int j : second) {
                min = Math.min(Math.abs(i - j), min);
            }
        }
        return min;
    }
}

面试题 17.12. BiNode

面试题 17.12. BiNode

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {

    // 上一个遍历到的节点
    TreeNode last = null;
    // 头节点
    TreeNode head = null;

    public TreeNode convertBiNode(TreeNode root) {
        inOrder(root);
        // 最后一个节点right和left置空
        if (last != null) {
            last.left = null;
            last.right = null;
        }
        return head;
    }

    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        // 中序就是顺序的，last不为空就连接
        if (last != null) {
            last.left = null;
            last.right = node;
        }
        last = node;
        // 比头节点小或者头节点为空那这个就是头节点
        if (head == null || node.val <= head.val) {
            head = node;
        }
        inOrder(node.right);
    }
}

面试题 17.16. 按摩师

面试题 17.16. 按摩师

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int massage(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        // i位置的时候最大选择和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            //要么选这个，和为前前个的最大值，要么不选这个，和为前一个最大值
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}