LeetCode刷题笔记——《剑指Offer》面试题（1）

算法
, , ,

刷题地址：

牛客网

LeetCode

编程语言

实现单例模式

思路：实现单例模式5种方法：饱汉式；饿汉式；双重校验锁；静态内部类；枚举类。其中常考的是双重校验锁和静态内部类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 双重校验锁
class Singleton {

    private volatile static Singleton instance;

    private Singleton() {}

    public static Singleton getInstance() {
        //第一次判空，若存在实例就不需要获取锁，减少性能开销
        if (instance==null) {
            synchronized(Singleton.class) {
                //第二次判空，避免生成多个Singleton实例
                if (instance==null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

// 静态内部类
class Singleton {

    private static class SingletonHolder {
        private static final Singleton INSTANCE = new Singleton();
    }

    private Singleton() {}

    public static Singleton getInstance() {
        return SingletonHolder.INSTANCE;
    }
}

数组

数组中重复的数字

思路：设下标为i，下标i对应的数字为nums[i]，如果nums[i]==i，接着扫描下一个数字；如果nums[i]!=i，则将nums[i]交换到i的位置上。如果该位置上已经存在正确摆放的值，则这个值是重复的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i=0; i<nums.length; i++) {
            if (nums[i]!=i) {
                if (nums[nums[i]]==nums[i]) return nums[i];
                swap(nums, i, nums[i]);
            }
        }
        return -1;
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

二维数组中的查找

思路：从左下角或者右上角开始遍历（左下角的数，为该行最小值和该列最大值；右上角相反）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int n = matrix.length;
        if (n==0) return false;
        int m = matrix[0].length;
        if (m==0) return false;
        int i = 0, j = m-1;
        while (i<n && j>=0) {
            if (matrix[i][j]==target) return true;
            else if (matrix[i][j]<target) i++;
            else j--;
        }
        return false;
    }
}

字符串

替换空格

思路：先遍历一遍字符串，遇到空格就要使字符串的容量+2。一个指针p指向字符串有字符的末尾，一个指针q指向字符串容器的末尾，从后往前扫描，若p遇到空格，后指针依次填充02%，否则填充p指针指向的字符。当两指针相遇或者p扫描到字符串头部，结束遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String replaceSpace(StringBuffer str) {
        int p = str.length()-1;
        for (int i=0; i<=p; i++) {
            if (str.charAt(i) == ' ') str.append("  ");
        }
        int q = str.length()-1;
        while (p<q && p>=0) {
            char c = str.charAt(p--);
            if (c==' ') {
                str.setCharAt(q--, '0');
                str.setCharAt(q--, '2');
                str.setCharAt(q--, '%');
            } else str.setCharAt(q--, c);
        }
        return str.toString();
    }
}

链表

从尾到头打印链表

思路：利用栈后进先出的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] reversePrint(ListNode head) {
        if (head==null) return new int[]{};
        Stack<Integer> s = new Stack<>();
        while (head!=null) {
            s.push(head.val);
            head = head.next;
        }
        int len = s.size();
        int[] res = new int[len];
        for (int i=0; i<len; i++) {
            res[i] = s.pop();
        }
        return res;
    }
}

树

重建二叉树

思路：前序遍历的第一个值为根节点，中序遍历序列中位于根节点左边的是左子树的中序遍历，位于右边的是右子树的中序遍历。递归求解左右两子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0 || preorder.length!=inorder.length) return null;
        return reBuild(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }

    public TreeNode reBuild(int[] pre, int[]in, int pl, int pr, int il, int ir) {
        if (pl>pr || il>ir) return null;
        TreeNode root = new TreeNode(pre[pl]);
        if (pl==pr) return root;
        int h = 0;
        while (in[il+h]!=root.val) {
            h++;
        }
        root.left = reBuild(pre, in, pl+1, pl+h, il, il+h-1);
        root.right = reBuild(pre, in, pl+h+1, pr, il+h+1, ir);
        return root;
    }
}

二叉树的下一个结点

思路：

  1. 如果一个节点有右子树，则它的中序遍历的下一个节点是它右子树的最左子节点；
  2. 如果它没有右子树，且它是其父节点的左子节点，它的下一个节点是它的父节点；
  3. 如果它没有右子树，且它是其父节点的右子节点，向上遍历找到一个是它父节点的左子节点的节点，所求的节点是其父节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode == null) return pNode;
        if (pNode.right != null) {
            TreeLinkNode pRight = pNode.right;
            while (pRight.left != null) pRight = pRight.left;
            return pRight;
        }
        while (pNode.next != null) {
            if (pNode == pNode.next.left) return pNode.next;
            pNode = pNode.next;
        }
        return null;
    }
}

栈和队列

用两个栈实现队列

思路：一个栈stack1负责入栈，一个栈stack2负责出栈。当需要出栈时，元素先全部进入stack2栈，此时弹出的顺序与队列相同。

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

    public Stack<Integer> stack1;
    public Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if (!stack2.isEmpty()) return stack2.pop();
        if (stack1.isEmpty()) return -1;
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

递归和循环

斐波那契数列

思路：可使用递归解决问题，但效率会非常低。本题只需要记录两个值即可。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int n) {
        if (n<2) return n;
        int a = 0, b = 1;
        for (int i=2; i<=n; i++) {
            int temp = b;
            b = a+b;
            a = temp;
        }
        return b;
    }
}

青蛙跳台阶

思路：本质上还是斐波那契数列问题。

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

查找和排序

旋转数组的最小数字

思路：二分查找，判断数组的旋转点在左半边还是右半边。注意处理特殊情况例如[1, 1, 1, 0, 1]，此时让右边界-1。

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

回溯法

矩阵中的路径

思路：使用DFS，递归查找该格子上下左右格子的数字是否符合要求，注意短路逻辑运算符能减少计算时间。

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

    public char[][] board;
    public String word;
    public int M;
    public int N;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        this.M = board.length;
        this.N = board[0].length;
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                boolean flag = dfs(i, j, 0);
                if (flag) return true;
            }
        }
        return false;
    }

    public boolean dfs(int i, int j, int k) {
        if (i<0 || j<0 || i>=M || j>=N) return false;//边界判断
        if (k<word.length() && board[i][j] != word.charAt(k)) return false;
        if (k==word.length()-1) return true;//找到路径
        char tmp = board[i][j];
        board[i][j] = '#';//将当前格子替换成其他字符，防止重复进入
        boolean flag = dfs(i-1, j, k+1) || dfs(i+1, j, k+1) || dfs(i, j-1, k+1) || dfs(i, j+1, k+1);
        board[i][j] = tmp;//回溯
        return flag;
    }
}

机器人的运动范围

思路：深度优先搜索，标记所有能进入的格子，然后遍历其数量。

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

    public int[][] matrix;
    public int M;
    public int N;
    public int K;

    public int movingCount(int m, int n, int k) {
        this.M = m;
        this.N = n;
        this.K = k;
        this.matrix = new int[m][n];
        dfs(0, 0);
        int res = 0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (matrix[i][j]==1) res++;
            }
        }
        return res;
    }

    public void dfs(int i, int j) {
        if (i<0 || j<0 || i>=M || j>=N) return;//边界判断
        if (!check(i, j)) return;//不符合要求的格子
        if (matrix[i][j]==1) return;//防止重复进入
        matrix[i][j] = 1;//标记可以进入此格
        dfs(i-1, j);
        dfs(i+1, j);
        dfs(i, j-1);
        dfs(i, j+1);
    }

    public boolean check(int i, int j) {
        int t=0;
        while (i>0) {
            t += i%10;
            i/=10;
        }
        while (j>0) {
            t += j%10;
            j/=10;
        }
        return t<=K;
    }
}

动态规划和贪婪算法

剪绳子

思路：贪心算法。通过分析发现应当尽可能多的剪出长度为3的绳子；若全部剪成3的绳子之后剩余长度为1，则需要少剪一次3，改剪成2段长度为2的绳子。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int cuttingRope(int n) {
        if (n<=3) return n-1;
        int exp = n/3;
        int rem = n%3;
        if (rem==0) {
            return (int)Math.pow(3, exp);
        } else if (rem==1) {
            return (int)Math.pow(3, (exp-1)) * 4;
        } else return (int)Math.pow(3, exp) * 2;
    }
}

位运算

二进制中1的个数

思路：n&(n-1)会把n最低位的1变成0。

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