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

知识迁移能力

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

思路：使用二分法查找数字在数组中出现的第一个位置和最后一个位置。

class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int head = getHead(array, k);
        int tail = getTail(array, k);
        if (head != -1 && tail != -1) return tail - head + 1;
        else return 0;
    }

    public int getHead(int[] array, int k) {
        int left = 0, right = array.length-1;
        while (left <= right) {
            int mid = (left + right) / 2 ;
            if (array[mid] < k) left = mid+1;
            else if (array[mid] > k) right = mid-1;
            else if (mid-1 >= 0 && array[mid-1] == k) right = mid-1;
            else return mid;
            }
        return -1;
    }

    public int getTail(int[] array, int k) {
        int left = 0, right = array.length-1;
        while (left <= right) {
            int mid = (left + right) / 2 ;
            if (array[mid] < k) left = mid+1;
            else if (array[mid] > k) right = mid-1;
            else if (mid+1 < array.length && array[mid+1] == k) left = mid+1;
            else return mid;
            }
        return -1;
    }
}

0~n-1中缺失的数字

思路：二分查找，查找第一个数值和下标不相等的元素的下标。

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length-1;
        while (left<=right) {
            int mid = left+(right-left)/2;
            if (nums[mid]==mid) left = mid+1;
            else right = mid-1;
        }
        return left;
    }
}

二叉搜索树的第k大的结点

思路：使用中序遍历二叉搜索树得到的是有序的序列，由于本题要找第k大的节点，可以转变为右子树->根节点->左子树的顺序。

class Solution {

    public int k;
    public TreeNode res;

    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        inorder(root);
        return res.val;
    }

    public void inorder(TreeNode root) {
        if (root==null) return;
        inorder(root.right);
        k--;
        if (k==0) res = root;
        inorder(root.left);
    }
}

二叉树的深度

思路：递归。

class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = TreeDepth(root.left);
        int rightDepth = TreeDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

判断平衡二叉树

思路：平衡二叉树左右子树高度差不超过1。可以递归比较二叉树的深度，但这样做会重复遍历多次子树，因此从下往上遍历，遇到不平衡的子树就返回结果。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }

    public int getDepth(TreeNode root) {
        if (root==null) return 0;
        int left = getDepth(root.left);
        if (left==-1) return -1;
        int right = getDepth(root.right);
        if (right==-1) return -1;
        if (Math.abs(left-right)>1) return -1;
        return 1+Math.max(left, right);
    }
}

数组中只出现一次的两个数字

思路：一个数异或自己等于0。将数组从头到尾依次异或，得到两个只出现一次的数的异或。这个结果一定不为0，因此可根据结果的二进制中某一位“1”的位置将数组分为两组，一组数的二进制对应位置为1，另一组为0，再分别使用异或得到这两个数。

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array.length < 2) return;
        int xor = 0;
        for (int i=0; i<array.length; i++) xor ^= array[i];
        int index = getFirstBit1(xor);
        num1[0] = 0;
        num2[0] = 0;
        for (int i=0; i<array.length; i++) {
            if (isBit1(array[i], index)) num1[0] ^= array[i];
            else num2[0] ^= array[i];
        }
    }

    public int getFirstBit1(int num) {
        int index = 0;
        while ((num & 1) == 0 && index < 32) {
            index++;
            num = num >> 1;
        }
        return index;
    }

    public boolean isBit1(int num, int index) {
        num = num >> index;
        return (num & 1) == 1;
    }
}

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

思路：把数组中所有数字的二进制表示按位相加，如果某一位和能被3整除，说明哪个要找的数字的二进制那一位是0，否则是1。使用一个32位的整形数组来保存二进制位。

class Solution {
    public int singleNumber(int[] nums) {
        int[] bitmap = new int[32];
        for (int num: nums) {
            for (int i=0; i<32; i++) {
                if ((num&1)==1) bitmap[31-i]++;
                num = num>>1;
            }
        }
        int res = 0;
        for (int i=31; i>=0; i--) {
            if (bitmap[i]%3!=0) {
                res += 1<<(31-i);
            }
        }
        return res;
    }
}

和为s的两个数字

思路：对于排序数组，使用前后双指针包夹，如果和大于目标值，则缩右边；小于目标值则扩展左边。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i=0, j=nums.length-1;
        while (i<j) {
            if (nums[i]+nums[j]==target) {
                return new int[]{nums[i],nums[j]};
            } else if (nums[i]+nums[j]<target) {
                i++;
            } else {
                j--;
            }
        }
        return new int[]{};
    }
}

和为s的连续正数序列

思路：使用双指针窗口扫描序列，并不断调整窗口大小。

class Solution {
    public int[][] findContinuousSequence(int target) {
        if (target==0) return new int[][]{{0}};
        ArrayList<int[]> res = new ArrayList<>();
        int l=1, r=1, sum=0;
        while (l<=target/2) {
            if (sum==target) {
                int[] tmp = new int[r-l];
                for (int i=l; i<r; i++) {
                    tmp[i-l] = i;
                }
                res.add(tmp);
                sum-=l;
                l++;
            } else if (sum<target) {
                sum+=r;
                r++;
            } else {
                sum-=l;
                l++;
            }
        }
        int[][] ans = res.toArray(new int[res.size()][]);
        return ans;
    }
}

翻转单词顺序

思路：先旋转整个句子，再旋转单词。

public class Solution {
    public String ReverseSentence(String str) {
        char[] chars= str.toCharArray();
        int n = chars.length;
        Reverse(chars, 0, n-1);
        int i = 0, j = 0;
        while (j<=n) {
            if (j==n || chars[j]==' ') {
                Reverse(chars, i, j-1);
                i = j+1;
            }
            j++;
        }
        return new String(chars);
    }

    public void Reverse(char[] str, int start, int end) {
        while (start<end) {
            char temp = str[start];
            str[start]= str[end];
            str[end] = temp;
            start++;
            end--;
        }
    }
}

左旋转字符串

思路：三次翻转。

public class Solution {
    public String LeftRotateString(String str, int n) {
        char[] strs = str.toCharArray();
        int len = strs.length;
        if (len<1) return str;
        int k = n % len;
        if (k==0) return str;
        reverseString(strs, 0, len-1);
        reverseString(strs, 0, len-1-k);
        reverseString(strs, len-k, len-1);
        return String.valueOf(strs);
    }

    public void reverseString(char[] str, int i, int j) {
        while (i<j) {
            char temp = str[i];
            str[i++] = str[j];
            str[j--] = temp;
        }
    }
}

滑动窗口的最大值

思路：单调队列，保证队列内的元素不递增，队列头部始终为当前滑动窗口的最大值，窗口滑动后，删除队列中所有小于新值的元素下标，并保证队列头部处于窗口中。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length==0||k==0) return new int[]{};
        int[] res = new int[nums.length-k+1];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i=0; i<k; i++) {
            while (!queue.isEmpty() && queue.peekLast()<nums[i]) {
                queue.pollLast();
            }
            queue.offer(nums[i]);
        }
        res[0] = queue.peekFirst();
        for (int i=k; i<nums.length; i++) {
            if (nums[i-k]==queue.peekFirst()) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && queue.peekLast()<nums[i]) {
                queue.pollLast();
            }
            queue.offer(nums[i]);
            res[i-k+1] = queue.peekFirst();
        }
        return res;
    }
}

队列的最大值

思路：单调队列，保证队列内的元素不递增，队列头部始终为当前滑动窗口的最大值，当删除元素时判断max队列头部元素是否是被删除的元素。

class MaxQueue {

    public LinkedList<Integer> queue;
    public LinkedList<Integer> max;

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

    public int max_value() {
        if (queue.isEmpty()) return -1;
        return max.peekFirst();
    }

    public void push_back(int value) {
        queue.offer(value);
        while (!max.isEmpty() && max.peekLast()<value) {
            max.pollLast();
        }
        max.offer(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) return -1;
        int res = queue.poll();
        if (max.peekFirst()==res) max.poll();
        return res;
    }
}

抽象建模能力

n个骰子的点数

思路：动态规划，dp[i][j]表示i个骰子投出j点的组合数，每增加一粒骰子，就在原来的结果上分别加上1～6。n个骰子可以投出$6^n$种等可能组合（即为分母），共有$5\times n+1$种可能的结果。

class Solution {
    public double[] dicesProbability(int n) {
        int[][] dp = new int[n+1][6*n+1];
        for (int i=1; i<=6; i++) {
            dp[1][i] = 1;
        }
        for (int i=2; i<=n; i++) {
            for (int j=i; j<=i*6; j++) {
                for (int k=1; k<=6; k++) {
                    if (j<=k) break;
                    dp[i][j] += dp[i-1][j-k];
                }
            }
        }
        double len = Math.pow(6, n);
        double[] res = new double[5*n+1];
        for (int i=0; i<res.length; i++) {
            res[i] = dp[n][n+i]*1.0/len;
        }
        return res;
    }
}

扑克牌中的顺子

思路：忽略大小王，先看数组中是否存在重复的值，对子必然无法形成顺子；再记录最大值和最小值，比较两者的差值是否小于5。

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

圆圈中最后剩下的数字

思路：约瑟夫环问题，通过分析可以找到递推公式：

1. 最后一轮，剩下的元素下标为0，反推它上一轮（剩下2个元素）的下标：index=(0+m)%2；
2. 倒数第二轮，剩下的元素下标为index，反推它上一轮（剩下2个元素）的下标：(index+m)%3；
3. 以此类推，直到环中元素数量=n为止，就能直到它最初的下标。

class Solution {
    public int lastRemaining(int n, int m) {
        int index = 0;
        for (int i=2; i<=n; i++) {
            index = (index+m)%i;
        }
        return index;
    }
}

也可以使用数组或链表来模拟游戏过程。

class Solution {
    public int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i=0; i<n; i++) list.add(i);
        int index = 0;
        while (list.size()>1) {
            index = (index+m-1)%list.size();
            list.remove(index);
        }
        return list.get(0);
    }
}

股票的最大利润

思路：用一个数保存之前遍历过的最小的数，每日所获得的最大利润等于当日股价减去这个最小值。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int min = prices[0];
        int maxDiff = Math.max(prices[1] - min, 0);
        for (int i=2; i<prices.length; i++) {
            if (prices[i-1] < min) min = prices[i-1];
            if (prices[i] - min > maxDiff) maxDiff = prices[i] - min;
        }
        return maxDiff;
    }
}

发散思维能力

求 1+2+…+n

思路：首先想到利用递归求和。由于无法使用条件语句，可以巧妙利用短路的方法来实现递归终止条件。终止条件是n>=1，当n==0时，发生短路直接返回sum=0，实现递归。

class Solution {
    public int sumNums(int n) {
        boolean b = (n>0) && ((n+= sumNums(n-1))>0);
        return n;
    }
}

不用加减乘除做加法

思路：使用位运算。

1. 二进制按位相加，相当于按位异或，不考虑进位
2. 进位值相当于按位与，再左移一位

class Solution {
    public int Add(int num1,int num2) {
        int sum = num1, carry = num2;
        while (num2 != 0) {
            sum = num1 ^ num2;
            carry = (num1 & num2) << 1;
            num1 = sum;
            num2 = carry;
        }
        return sum;
    }
}

构建乘积数组

思路：先从左到右遍历数组，累乘数组元素；再从右到左遍历数组，累乘数组元素；最后将两个累乘相乘。

class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        B[0] = 1;
        for (int i=1; i<A.length; i++) {
            B[i] = B[i-1] * A[i-1];
        }
        int base = 1;
        for (int j=A.length-1; j>=0; j--) {
            B[j] *= base;
            base *= A[j];
        }
        return B;
    }
}