【剑指】6.3 知识迁移能力

面试中有许多隐性考察的能力，沟通和学习的能力往往是相互交织的。知识迁移的能力则是把已经掌握的知识和举一反三应用到新的场景和问题上。

面试题53：在排序数组中查找数字

题目描述

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

解题思路

如果采用线性搜索的方法，时间复杂度为O(n)，没有利用到数组有序的性质。该性质令人联想到二分查找，我们使用二分查找找到目标数之后，如何寻找左右可能存在相同的数的边界？如果向两侧线性查找，那么时间复杂度又会提升至O(n)。所以在二分查找时如果找到目标数不应该停下，而是应该固定一侧已知边界继续寻找另一侧边界。这里的思路可以参考之前做过的二分查找相关的问题。

public int GetNumberOfK(int [] array , int k) {
    if (array == null || array.length == 0) return 0;
    if (k < array[0] || k > array[array.length - 1]) return 0;
    int right = findBoundary(array, k, false);
    if (right == -1) return 0;
    return right - findBoundary(array, k, true) + 1;
}

private int findBoundary(int[] array, int target, boolean findLeft) {
    int left = 0, right = array.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (array[mid] == target) {
            if (findLeft)
                right = mid - 1;
            else
                left = mid + 1;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else if (array[mid] < target) {
            left = mid + 1;
        }
    }
    if (findLeft && left < array.length && array[left] == target)
        return left;
    if (!findLeft && right >= 0 && array[right] == target)
        return right;
    return -1;
}

类似的二分查找知识迁移相关的问题有：

• 0~n-1这n个数中缺少了某数后排序存在长度为n-1的数组中，找出这个缺少的数字：我们知道这个数字左边的所有数本身和下标都是相同的，这个数右边的所有数和下标都是不同的，那么可以用二分查找去寻找这个数。
• 找出排序数组中数值和下标相等的元素（数组元素唯一）：如果数组中一个数的值x大于下标i，那么它右边的数最小为x+1，必定大于i+1，同理可以推到x右边的所有数的值都会大于它们的下标；同理若x小于i，则其左边所有的数的值都会小于其下标。找到相同的数返回即可，不相同则用二分查找的思想继续查找。

面试题54：二叉搜索树的第k小节点

题目描述

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

解题思路

二叉搜素树的中序遍历结果就是其中元素的排序结果，所以每访问到父亲节点的内容就将计数加一，直到和k相同。

public class No54_KthNodeOfBST {
    private int count = 0;
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k < 1) return null;
        TreeNode answer = null;
        if (pRoot.left != null) answer = KthNode(pRoot.left, k);
        if (answer != null) return answer;
        if (++count == k) return pRoot;
        if (pRoot.right != null) answer = KthNode(pRoot.right, k);
        return answer;
    }
}

面试题55：二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

如果使用基于迭代的遍历（任一种方式都可以），自顶向下都能直到当前的节点的深度，向下遍历时将深度+1传递过去就可以了，每当遇到叶子节点就将其深度和最大深度比较并更新最大深度。

如果使用递归那么思路更简单直观，当得到两个子树的深度后，当前根节点所在树的深度就是二者的最大值+1。

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

【扩展】题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路：在前面递归思路的基础上，设置一个全局布尔变量初始为true，在递归过程中一旦发现左右子树高度差超过1则将变量值改为false。

public class Solution {
    private boolean isBalanced = true;

    public boolean IsBalanced_Solution(TreeNode root) {
        getDepth(root);
        return isBalanced;
    }
    
    private int getDepth(TreeNode root){
        if(root == null) return 0;
        int leftDepth = getDepth(root.left), rightDepth = getDepth(root.right);
        if(Math.abs(leftDepth - rightDepth) > 1) isBalanced = false;
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

面试题56：数组中只出现1次的两个数字

题目描述

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

解题思路

可以使用哈希表来统计每个数字出现的次数，这样需要O(n/2)大小的额外空间，时间复杂度为O(n)。或者排序后扫描一遍相邻的数就能找到出现1次的数，这样需要O(nlogn)的时间和O(1)的空间。

此题由于其特殊性可以使用异或来解决，异或方法的时间复杂度为O(n)，空间复杂度为O(1)。利用一个数和自身的异或结果为0，0和任何数的异或结果都是该数本身的性质。在连续进行异或运算后，相同的数对最终的结果会抵消影响。本题中的数组元素进行异或后得到的是两个唯一的数异或得到的结果，我们从地位往高位找到该结果的第一个为1的位，通过这一位来筛选数组中的数就能把这两个数区分开来。另外由于相同的数每一位都相同，使用某一位来筛选也能确保相同的数被筛选到同一组中。

//num1[0]和num2[0]用于存储结果
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    int xor = 0, bitOf1 = 0;
    for (int num : array)
        xor ^= num;
    while ((xor & 1) != 1) {
        bitOf1++;
        xor >>= 1;
    }
    for (int num : array) {
        if (((num >> bitOf1) & 1) == 1)
            num1[0] ^= num;
        else
            num2[0] ^= num;
    }
}

扩展：数组中除了1个数字只出现1次外，其他数字都出现了3次，找出那个数。

由于这里出现3次的数做完异或后还是得到原数字，所以不能直接用上面的思路，我们可以统计32位整形数字，每一位上1出现的次数，如果某一位上的数能被3整除，则出现1次的数字在该位上是0，否则该位上是1。

面试题57：和为s的数字

题目描述

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

解题思路

暴力思路是固定每一个小的值，向右寻找可能的大值，这种方式时间复杂度为O(n^2)。我们可以使用双指针法缩小搜索范围，一开始将搜索范围设为数组的边界。假设发现left+right大于目标值，则对于left右边的任意值x，x+right都大于目标值，因此可以将right排除到搜索范围之外；同理left+right小于目标值时可以将left排除到搜索范围之外，这样就从两边向中间逐渐缩小了搜索范围。

由于和相同的两个数字越接近乘积越大，则首次找到符合条件的两个数直接返回就可以了，该方法每个数只扫描一遍，时间复杂度为O(n)。

public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
    ArrayList<Integer> list = new ArrayList<>();
    if (array == null || array.length < 2) return list;
    int left = 0, right = array.length - 1;
    while (left < right) {
        if (array[left] + array[right] == sum) {
            list.add(array[left]);
            list.add(array[right]);
            return list;
        }
        if (array[left] + array[right] < sum)
            left++;
        if (array[left] + array[right] > sum)
            right--;
    }
    return list;
}

扩展：和为s的连续整数序列。输入一个正数s，打印出所有和为s的连续正整数序列（至少含有两个数）。

思路依然是使用双指针表示连续序列的最小值和最大值，当序列的和小于sum时则增加右边边界，大于sum时则去掉较小的值（增加左边界），等于sum时添加到结果集并继续调整边界搜索，直到右边界超过sum/2+1，因为至少需要两个连续数，这两个数不可能都超过sum的一半。

public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();
    int left = 1, right = 2, totalVal = 3;
    while (right <= sum / 2 + 1 && left < right) {
        if (totalVal == sum) {
            ArrayList<Integer> result = new ArrayList<>();
            for (int i = left; i <= right; i++)
                result.add(i);
            results.add(result);
            //找到一组后移动边界继续寻找，这里用totalVal -= left++;也可以
            totalVal += ++right;
        } else if (totalVal < sum) {
            totalVal += ++right;
        } else {
            totalVal -= left++;
        }
    }
    return results;
}

面试题58：翻转字符串

题目描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路

如果可以直接使用API，那么可以将其分割成单词数组，再逆序拼接。

public String reverseWords(String s) {
    if (s == null || s.length() == 0) return "";
    String[] words = s.split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        if (!words[i].equals(""))
            sb.append(words[i]).append(" ");
    }
    return sb.toString().trim();
}

还可以使用全翻转一遍加按单词再翻转一遍的方法，不过这题在LeetCode上新增了可能单词间有多个空格的限制（导致字符串长度会变化），想要完全不用API中的trim()、subString()等方法在Java里面就需要花点功夫处理。

public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length();) {
        while (i < s.length() && s.charAt(i) == ' '){
            i++;
        }
        while (i < s.length() && s.charAt(i) != ' ') {
            sb.append(s.charAt(i));
            i++;
        }
        sb.append(' ');
    }
    if (sb.length() == 0) return "";
    while (sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ')
        sb.deleteCharAt(sb.length() - 1);

    partialReverse(sb, 0, sb.length() - 1);
    int left = 0, right = 0;
    while (right < sb.length()) {
        while (right < sb.length() && sb.charAt(right) != ' ') {
            right++;
        }
        partialReverse(sb, left, right - 1);
        left = right + 1;
        right++;
    }
    return sb.toString();
}

private void partialReverse(StringBuilder sb, int left, int right) {
    while (left < right) {
        char c = sb.charAt(right);
        sb.setCharAt(right, sb.charAt(left));
        sb.setCharAt(left, c);
        left++;
        right--;
    }
}

面试题59：滑动窗口或队列的最大值

见075_滑动窗口的最大值。