面试题【53-59】知识迁移能力

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

题目一：数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3, 3, 3, 4, 5}和数字3，由于3在这个数组中出现了4次，因此输出4。

算法：二分查找-循环
- 寻找最左边第一个target的位置时，middle = (low + high) >> 1在和为奇数时已经向左偏移了
  - nums[middle]的值比target小，则一定在middle右边，low=middle+1
  - 否则，high=middle
- 寻找最右边最后一个target的位置时，middle需要进行一下偏移否则可能会死循环，middle = ((low + high) >> 1) + 1
  - nums[middle]的值比target大，则一定在middle左边high=middle-1
  - 否则，low=middle

public int[] searchRange(int[] nums, int target) {
    int[] result = new int[]{-1,-1};
    if (nums == null || nums.length == 0) {
        return result;
    }

    int low = 0;
    int high = nums.length - 1;
    while (low < high) {
        int middle = (low + high) >> 1;
        if (nums[middle] < target) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    if (nums[low] != target) {
        return result;
    } else {
        result[0] = low;
    }

    high = nums.length - 1;
    while (low < high) {
        int middle = ((low + high) >> 1) + 1;   // 向右偏移避免当low=high-1时low=middle导致死循环
        if (nums[middle] > target) {
            high = middle - 1;
        } else {
            low = middle;
        }
    }
    if (nums[high] != target) {
        return result;
    } else {
        result[1] = high;
    }
    return result;
}

算法：二分查找-递归
- 寻找最左边第一个target的位置时：看代码if-else
- 寻找最右边最后一个target的位置时：看代码if-else

public int search(int[] nums, int target) {
    checkArguments(nums);

    int first = getFirstTarget(nums, target, 0, nums.length-1);
    int last = getLastTarget(nums, target, 0, nums.length-1);
    if (first != -1 && last != -1) {
        return last - first + 1;
    }
    return 0;
}

private int getFirstTarget(int[] nums, int target, int start, int end) {
    if (start > end) {
        return -1;
    }

    int middle = (start + end) >> 1;
    if (nums[middle] == target) {
        if (middle == 0 || middle != 0 && nums[middle-1] < target) {
            return middle;
        }
        end = middle - 1;
    } else if (nums[middle] > target) {
        end = middle - 1;
    } else {
        start = middle + 1;
    }
    return getFirstTarget(nums, target, start, end);
}

private int getLastTarget(int[] nums, int target, int start, int end) {
    if (start > end) {
        return -1;
    }

    int middle = (start + end) >> 1;
    if (nums[middle] == target) {
        if (middle == nums.length - 1 || (middle != nums.length - 1 && nums[middle+1] > target)) {
            return middle;
        }
        start = middle + 1;
    } else if (nums[middle] < target) {
        start = middle + 1;
    } else {
        end = middle - 1;
    }
    return getLastTarget(nums, target, start, end);
}

题目二：0到n-1中缺失的数字

题目：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

算法：二分查找
- middle的值如果和middle的下标相等：继续寻找右半边
- middle的值如果和middle的下标不等：
  - 如果middle已经到了最左边就返回0，或者middle-1的值刚好和middle-1的下标相等就返回middle
  - 否则继续寻找左半边
- 如果最后left寻找到了最右边跳出循环了，则缺失的就是nums.length

public int missingNumber(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int middle = (left + right) >> 1;
        if (nums[middle] == middle) {
            left = middle + 1;
        } else {
            if (middle == 0 || nums[middle-1] == middle - 1) {
                return middle;
            }
            right = middle - 1;
        }
    }
    if (left == nums.length) {
        return left;
    }
    return -1;
}

题目三：数组中数值和下标相等的元素

题目：假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等。

算法：二分查找

public int getNumberSameAsIndex(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int middle = (left + right) >> 1;
        if (nums[middle] == middle) {
            return middle;
        } else if (nums[middle] > middle) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }
    return -1;
}

面试题54：二叉搜索树的第K个结点

求第K大的结点先遍历右子树
求第K小的结点先遍历左子树

题目一：第K小的结点

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

算法：二分查找
- 计算左子树的节点数目进行二分查找

public int kthSmallest(TreeNode root, int k) {
    if (root == null || k <= 0) {
        return -1;
    }

    return kthSmallestBinarySearch(root, k);
}

public int kthSmallestBinarySearch(TreeNode root, int k) {
    int count = countNodes(root.left);
    if (k < count + 1) {
        return kthSmallestBinarySearch(root.left, k);
    } else if (k > count + 1) {
        return kthSmallestBinarySearch(root.right, k-1-count);          // 1 is counted as current node
    } else {
        return root.val;   
    }
}

public int countNodes(TreeNode node) {
    if (node == null) {
        return 0;
    }

    return 1 + countNodes(node.left) + countNodes(node.right);
}

算法：DFS中序遍历
- 用全局变量保存结果和次序

private static int number = 0;
private static int count = 0;
public int kthSmallest(TreeNode root, int k) {
    if (root == null || k <= 0) {
        return -1;
    }

    count = k;
    dfs(root);
    return number;
}

public void dfs(TreeNode node) {
    if (node.left != null)
        dfs(node.left);
    count--;
    if (count == 0) {
        number = node.val;
        return;
    }
    if (node.right != null)
        dfs(node.right);
}

算法：栈
- 首先往栈里死命添加左节点
- 然后每次出栈时都检查右节点并再次往栈里死命添加左节点

public int kthSmallest(TreeNode root, int k) {
    if (root == null || k <= 0) {
        return -1;
    }

    Stack<TreeNode> stack = new Stack<>();
    while (root != null) {
        stack.push(root);
        root = root.left;
    }
    while (k != 0) {
        TreeNode node = stack.pop();
        k--;
        if (k == 0)
            return node.val;
        TreeNode right = node.right;
        while (right != null) {
            stack.push(right);
            right = right.left;
        }
    }
    return -1;      // k > numberOf(TreeNode)
}

题目二：第K大的结点

算法：
- 同'第K小的结点'
- 代码略：将'第K小的结点'中left与right互换
算法：
- 另一种DFS中序遍历的方式，少一个全局变量

private static int count = 0;
public int kthLargest(TreeNode root, int k) {
    if (root == null || k <= 0) {
        return -1;
    }
    count = k;
    return kthLargestNode(root).val;
}

private TreeNode kthLargestNode(TreeNode node) {
    TreeNode target = null;
    if (node.right != null) {
        target = kthLargestNode(node.right);
    }
    if (target == null) {
        if (count == 1) {
            target = node;
        }
        count--;
    }
    if (target == null && node.left != null) {
        target = kthLargestNode(node.left);
    }
    return target;
}

算法：
- 同'第K小的结点'
- 代码略：将'第K小的结点'中left与right互换

面试题55：二叉树的深度

题目一：二叉树的深度

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

算法：BFS
- 经典左右子树递归

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return 1 + (left > right ? left : right);
}

算法：BFS

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int depth = 0;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        depth++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode temp = queue.poll();
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
    }
    return depth;
}

题目二：平衡二叉树

题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

算法：递归左右子树

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    int diff = left - right;
    if (diff > 1 || diff < -1) {
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
}

算法：DFS
- 可看作后序遍历，
- 先遍历左子树，左子树不是平衡树直接返回
- 再遍历右子树，右子树不是平衡树直接返回
- 判断父节点是否是平衡树

public boolean isBalanced(TreeNode root) {
    return getHeight(root) != -1;
}

public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = getHeight(root.left);
    if (left == -1) {
        return -1;
    }
    int right = getHeight(root.right);
    if (right == -1) {
        return -1;
    }

    if (Math.abs(left - right) > 1) {
        return -1;
    }
    return 1 + Math.max(left, right);
}

面试题56：数组中只出现一次的数字

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

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

算法：
- 1.依然亦或所有数字
- 2.根据亦或结果的二进制中第一个1的位置把数组分成两部分再亦或即可

public int[] singleNumber(int[] nums) {
    if (nums == null || nums.length < 2) {
        return new int[]{-1, -1};
    }

    int xor = 0;
    for (int x : nums) {
        xor ^= x;
    }
    xor &= (-xor);          // xor变成最低位为1其他位为0的数字
    int n1 = 0, n2 = 0;
    for (int x : nums) {
        if ((x & xor) == 0) {
            n1 ^= x;
        } else {
            n2 ^= x;
        }
    }
    return new int[]{n1, n2};
}

题目二：数组中唯一只出现一次的数字

题目：在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请找出那个吃出现一次的数字。

算法：
- 用bitSum辅助数组统计每位出现的次数
- 最后bitSum对3取余再二进制转十进制即是结果

public int singleNumber(int[] nums) {
    checkArguments(nums);

    int[] bitSum = new int[32];
    for (int x : nums) {
        int bitMask = 1;
        for (int j = 31; j >= 0; j--) {
            if ((x & bitMask) != 0) {
                bitSum[j]++;
            }
            bitMask <<= 1;
        }
    }
    int result = 0;
    for (int x : bitSum) {
        result <<= 1;
        result += (x % 3);
    }
    return result;
}

算法：
- 1.举一反三，同类问题
- 2.简洁解答，代码如下

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

面试题57：和为s的数字

题目一：和为s的两个数字

题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。

算法：双指针
- 左右开弓

public int[] twoSum(int[] nums, int target) {
    checkArguments(nums);

    int behind = 0, ahead = nums.length - 1;
    while (ahead >= behind) {
        int sum = nums[ahead] + nums[behind];
        if (sum == target) {
            return new int[]{nums[ahead], nums[behind]};
        } else if (sum > target){
            ahead--;
        } else {
            behind++;
        }
    }
    return null;
}

题目二：和为s的连续正数序列

题目：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

算法：双指针
- 前后开工

public int[][] findContinuousSequence(int target) {
    if (target < 3) {
        return null;
    }

    List<List<Integer>> result = new ArrayList<List<Integer>>();
    int small = 1;
    int big = 2;
    int middle = (1 + target) / 2;
    int curSum = small + big;
    while (small < middle) {
        if (curSum == target) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int i = small; i <= big; i++) {
                temp.add(i);
            }
            result.add(temp);
            big++;
            curSum += big;
        } else if (curSum < target) {
            big++;
            curSum += big;
        } else {
            curSum -= small;
            small++;
        }
    }

    int[][] ret = new int[result.size()][];
    for (int i = 0; i < result.size(); i++) {
        List<Integer> temp = result.get(i);
        ret[i] = new int[temp.size()];
        for (int j = 0; j < temp.size(); j++) {
            ret[i][j] = temp.get(j);
        }
    }
    return ret;
}

面试题58：翻转字符串

题目一：翻转单词顺序

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

不处理单词之间和句子头尾的多个空格

算法：
- 两次翻转

public String reverseWords(String s) {
    if (s == null) {
        return null;
    }

    StringBuilder sb = new StringBuilder(s);
    int begin = 0;
    int end = sb.length() - 1;
    reverse(sb, begin, end);

    end = 0;
    while (begin < sb.length() - 1) {
        if (sb.charAt(begin) == ' ') {
            begin++;
            end++;
        } else if(sb.charAt(end) == ' ' || end == sb.length() - 1){
            reverse(sb, begin, end-1);
            begin = ++end;
        } else {
            end++;
        }
    }
    return sb.toString();
}

处理单词之间和句子头尾的多个空格

算法：
- split函数+正则表达式

public String reverseWords(String s) {
    if (s == null) {
        return null;
    }

    String[] strArr = s.trim().split("\\s+");
    StringBuilder result = new StringBuilder();
    for (int i = strArr.length - 1; i > 0; i--) {
        result.append(strArr[i]);
        result.append(" ");
    }
    result.append(strArr[0]);
    return result.toString();
}

算法：
- 两次翻转

public String reverseWords(String s) {
    if (s == null) {
        return null;
    }

    StringBuilder sb = new StringBuilder(s.trim());
    int begin = 0;
    int end = sb.length() - 1;
    reverse(sb, begin, end);

    end = 0;
    while (begin < sb.length() - 1) {
        // 利用到逻辑运算符短路的特性
        if (sb.charAt(end) == ' ' && sb.charAt(end-1) == ' ') {
            sb.deleteCharAt(end);
        } else if(end == sb.length() - 1 || sb.charAt(end+1) == ' '){
            reverse(sb, begin, end);
            begin = end + 2;
            end = begin;
        } else {
            end++;
        }
    }
    return sb.toString();
}

算法：
- 数组+while的使用

public String reverseWords(String s) {
    if (s == null) 
        return null;

    char[] a = s.toCharArray();
    int n = a.length;
    // step 1. reverse the whole string
    reverse(a, 0, n - 1);
    // step 2. reverse each word
    reverseWords(a, n);
    // step 3. clean up spaces
    return cleanSpaces(a, n);
}

void reverseWords(char[] a, int n) {
    int begin = 0, end = 0;
    while (begin < n) {
        while (begin < end || (begin < n && a[begin] == ' '))         // skip spaces
            begin++;
        while (end < begin || (end < n && a[end] != ' '))         // skip non spaces
            end++;
        reverse(a, begin, end - 1);                      // reverse the word
    }
}

String cleanSpaces(char[] a, int n) {
    int begin = 0, end = 0;
    while (end < n) {
        while (end < n && a[end] == ' ')
            end++;                          // skip spaces
        while (end < n && a[end] != ' ')
            a[begin++] = a[end++];          // keep non spaces
        while (end < n && a[end] == ' ')
            end++;                          // skip spaces
        if (end < n)
            a[begin++] = ' ';               // keep only one space
    }
    return new String(a).substring(0, begin);
}

题目二：左旋转字符串

题目：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串"abcdefg"和数字2，该函数将返回左旋转2位得到的结果"cdefgab"。

算法：
- 两次旋转

public String reverseLeftWords(String s, int n) {
    if (s == null) {
        return null;
    }
    if (s.length() == 0) {
        return "";
    }

    char[] charArr = s.toCharArray();
    if (n > 0 && n < s.length()) {
        reverse(charArr, 0, charArr.length-1);
        reverse(charArr, 0, charArr.length-1-n);
        reverse(charArr, charArr.length-n, charArr.length-1);
    }
    return new String(charArr, 0, charArr.length);
}

面试题59：队列的最大值

题目一：滑动窗口的最大值

题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如,如果输入数组{2, 3, 4, 2, 6, 2, 5, 1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4, 4, 6, 6, 6, 5}，

算法：双端队列
- 在队列中只保存可能是滑动窗口中最大值的索引
- 每次遍历做两个检查，使得队首一直是最大值的索引
  - 队列末尾的值小于遍历值，不可能是最大值了，尾部出队
  - 队列头部的位置不在滑动窗口内了，头部出队

public int[] maxSlidingWindow(int[] nums, int k) {
    checkArguments(nums, k);

    int[] result = new int[nums.length-(k-1)];
    ArrayDeque<Integer> indexOfMax = new ArrayDeque<Integer>();
    for (int i = 0; i < k; i++) {
        while (!indexOfMax.isEmpty() && nums[i] > nums[indexOfMax.peekLast()]) {
            indexOfMax.pollLast();
        }
        indexOfMax.offer(i);
    }
    for (int i = k; i < nums.length; i++) {
        result[i-k] = nums[indexOfMax.peekFirst()];
        while (!indexOfMax.isEmpty() && nums[i] > nums[indexOfMax.peekLast()]) {
            indexOfMax.pollLast();
        }
        if (!indexOfMax.isEmpty() && indexOfMax.peekFirst() <= i - k) {
            indexOfMax.pollFirst();
        }
        indexOfMax.offer(i);
    }
    result[nums.length-k] = nums[indexOfMax.peekFirst()];
    return result;
}

public void checkArguments(int[] array, int k) {
    if (array == null) {
        throw new RuntimeException("Null array");
    }
    if (array.length == 0) {
        throw new RuntimeException("Empty array");
    }
    if(k <= 0 || k > array.length) {
        throw new RuntimeException("Invalid size of window");
    }
}

算法：
- 朴素比较
- 每次遍历值，把进入窗口的值和出去窗口的值作比较

public int[] maxSlidingWindow(int[] nums, int k) {
    checkArguments(nums, k);

    int[] result = new int[nums.length-(k-1)];
    int max = Integer.MIN_VALUE;
    int index = 0;
    for (int i = 0; i < k; i++) {
        if (nums[i] > max) {
            max = nums[i];
        }
    }
    result[index++] = max;
    for (int i = k; i < nums.length; i++) {
        if (nums[i] == nums[i-k] ) {
            result[index++] = max;
        } else if (nums[i] > nums[i-k]) {
            if (nums[i] > max) {
                result[index++] = nums[i];
                max = nums[i];
            } else {
                result[index++] = max;
            }
        } else {
            if (nums[i-k] != max) {
                result[index++] = max;
            } else {
                max = nums[i];
                for (int j = i-k+1; j < i; j++) {
                    if (nums[j] > max) {
                        max = nums[j];
                    }
                }
                result[index++] = max;
            }
        }
    }
    return result;
}

题目二：队列的最大值

题目：给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组{2, 3, 4, 2, 6, 2, 5, 1}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4, 4, 6, 6, 6, 5}，

算法：
- 维护一个双端队列，保存可能是最大值的元素
- 维护一个队列，保存所有元素

class MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> deque;

    public MaxQueue() {
        queue = new LinkedList<>();  // 队列：插入和删除
        deque = new LinkedList<>();  // 双端队列：获取最大值
    }

    public int max_value() {
        return deque.size() > 0 ? deque.peek() : -1;  // 双端队列的队首为queue的最大值
    }

    public void push_back(int value) {
        queue.offer(value);         // value入队
        while(!deque.isEmpty() && value > deque.peekLast()){
            deque.pollLast();       // 将deque队尾小于value的元素删掉
        }
        deque.offerLast(value);     // 将value放在deque队尾
    }

    public int pop_front() {
        int temp = queue.size() > 0 ? queue.poll() : -1;    // 获得队首元素
        if(deque.size() > 0 && temp == deque.peek()){
            deque.poll();                                   // 如果出队的元素是当前最大值，将deque的队首出队
        }
        return temp;
    }
}

算法：
- 维护一个max双端队列，保存可能是最大值的元素
- 维护一个main（双端）队列，保存所有元素
- 保存一个index变量，记录当前元素的位置

class MaxQueue {
    class InternalData {
        public InternalData(int number_, int index_) { number = number_; index = index_; }
        int number;
        int index;
    }

    Deque<InternalData> main;
    Deque<InternalData> max;
    int index;

    public MaxQueue() {
        main = new LinkedList<InternalData>();
        max = new LinkedList<InternalData>();
        index = 0;
    }

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

    public void push_back(int value) {
        while (!max.isEmpty() && value >= max.peekLast().number) {
            max.pollLast();
        }
        max.offer(new InternalData(value, index));
        main.offer(new InternalData(value, index));
        index++;
    }

    public int pop_front() {
        if (!max.isEmpty()) {
            if (max.peekFirst().index == main.peekFirst().index) {
                max.pollFirst();
            }
            return main.pollFirst().number;
        } else {
            return -1;
        }
    }
}