【剑指】5.2 优化时间效率

面试的时候要展现敏捷的思维能力和追求完美的激情，第一时间告诉面试官最直观的想法能体现出思维的敏捷，同时在寻找更优的办法的路上也不能轻言退缩，要有解决问题的态度和激情。

面试题39：数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

拿到题目可能直观的思路是对数组进行排序，这时出现次数超过一半的数字一定出现在中间位置，这种方法需要O(nlogn)的时间；或者使用哈希表进行计数，最后选出次数最多的，这需要使用额外的O(n)空间和O(2n)的时间。

我们可以根据数组的性质考虑这个问题，统计时使用一个计数和max变量保存当前出现最多的数字和出现次数，超过半数的数的影响最大，最终一定是超过半数的数字留到最后。

public int MoreThanHalfNum_Solution(int [] array) {
    if (array==null||array.length==0) return 0;
    int count = 1, maxAppear = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] == maxAppear) {
            count++;
        } else if (count > 0) {
            count--;
        } else {
            count=1;
            maxAppear = array[i];
        } 
    }
    count = 0;
    for (int num : array) {
        if (num==maxAppear) count++;
    }
    return count > array.length / 2 ? maxAppear : 0;
}

面试题40：最小的K个数

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

解题思路

拿到题目最直接的思路就是最输入数组进行排序，这时最前面的K个数就是最小的K个数，时间复杂度为O(nlogn)。但对于可能输入的海量数据不能全部同时加载到内存的，可以使用大小为K一个最大堆，当堆满了之后，对于每一个到达的数字，如果它大于堆顶则不可能在前K小的数中，否则删除堆顶并插入该元素。这种方法的时间复杂度为O(nlogk)。

现在可以采用类似快速排序的思想，每次进行partition，我们能确认小于枢轴的数有几个，如果枢轴大于k则继续对左半边执行partition，否则对右半边执行，知道piviot=k-1为止。该方法的时间复杂度为O(n)。

public class LeastKNums {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || k <= 0 || k > input.length) return list;
        int left = 0, right = input.length;
        while (left < right) {
            int pivot = partition(input, left, right);
            if (pivot == k-1) {
                for (int i = 0; i <= pivot; i++) {
                    list.add(input[i]);
                }
                return list;
            }
            if (pivot < k-1) {
                left = pivot + 1;
            } else {
                right = pivot;
            }
        }
        return list;
    }

    private int partition(int[] array, int left, int right) {
        int pivot = array[right - 1];
        int index = left;
        for (int i = left; i < right - 1; i++) {
            if (array[i] < pivot) {
                swap(array,index,i);
                index++;
            }
        }
        swap(array, index, right - 1);
        return index;
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

面试题41：数据流的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路

不同于数据流中第K大的数，由于是要找中位数所以需要保留所有的数据。如果读入时不作排序，那么可以使用partition函数在O(n)的时间内获得中位数；如果读入时就进行插入排序，那么需要O(n)的时间进行插入。这里我们使用两个总大小为O(n)的堆来实现O(logn)的插入时间复杂度和O(1)的查询时间。

当已有偶数个数时，我们把新插入的数插入到最大堆中，再从最大堆堆顶取出最大值放入最小堆中；当已有奇数个数时，我们把新插入的数插入到最小堆中，再从最小堆顶取出最小值放入最大堆中。这样就保证了最小堆中元素的数量和最大堆中元素的数量要么相同，要么多1，并且最小堆中的最小值总是大于等于最大堆中的最大值。

这样当已有奇数个数字时，最小堆顶就是中位数；已有偶数个数字时，两个堆顶的平均数就是中位数。

public class MedianOfStream {
    private int count=0;
    PriorityQueue<Integer> minQueue=new PriorityQueue<>();
    PriorityQueue<Integer> maxQueue=new PriorityQueue<>((o1, o2) -> o2-o1);

    public void Insert(Integer num) {
        if ((count & 1) == 0) {
            maxQueue.offer(num);
            minQueue.offer(maxQueue.poll());
        } else {
            minQueue.offer(num);
            maxQueue.offer(minQueue.poll());
        }
        count++;
    }

    public Double GetMedian() {
        if ((count & 1) == 1)
            return (double) minQueue.peek();
        else
            return ((double)minQueue.peek()+(double)maxQueue.peek())/2;
    }
}

面试题42：连续子数组的最大和

题目描述

输入一个整形数组，数组中有正数也有负数，求所有子数组和的最大值。

解题思路

使用动态规划的思路，我们要来考虑这题的状态是什么，显然是随着i的增加，以i结尾的子数组的最大和，因为只有知道第i个元素包含在子数组内才能进一步决定子数组是否包含第i+1个元素。当以第i个元素结尾的子数组和值大于0时，第i+1个元素对应的子数组才包含前面的子数组。否则以第i+1个元素为结尾的和最大的子数组就是第i+1个元素本身。

我们使用dp[i]来表示以第i个元素为结尾的子数组的最大和，base case 为dp[0]=array[0]。

public int FindGreatestSumOfSubArray(int[] array) {
    if (array==null||array.length==0) return 0;
    int[] dp = new int[array.length];
    dp[0] = array[0];
    for (int i = 1; i < array.length; i++) {
        if (dp[i-1]<=0)
            dp[i]=array[i];
        else
            dp[i]=array[i]+dp[i-1];
    }
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < array.length; i++) {
        max = Math.max(max, dp[i]);
    }
    return max;
}

面试题43：1~n整数中1出现的次数

题目描述

输入一个整数n，求1~n这n个整数的十进制表示中1出现出现的次数。例如1~12中包含数字1的数字有1、10、11、12，1一共出现了5次。

解题思路

拿到题目可能最直接的想法就是从1到n遍历，统计每个数字中1出现的次数。数字n有logn位，每次统计要不断做求余和除法操作，需要O(logn)时间，则总时间复杂度为O(nlogn)。该暴力法不能令人满意。

public int NumberOf1Between1AndN_Solution(int n) {
    int digit = 1, result = 0;
    int high = n / 10, low = 0, cur = n % 10;
    while (high != 0 || cur != 0) {
        if (cur == 0) result += high * digit;
        else if (cur == 1) result += high * digit + low + 1;
        else result += (high + 1) * digit;

        low += cur * digit;
        cur = high % 10;
        high /= 10;
        digit *= 10;
    }
    return result;
}

面试题45：把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路

由于拼接数字可能产生整形溢出的问题，所以我们需要使用字符串来表示数字。暴力法使用搜索所有全排列的结果找出最小值，显然时间复杂度O(N!)过大。

无论怎样排，最后结果的总长度是相同的，这就要求我们把使结果最小的元素放到前面。那怎么使结果最小呢？就想到自定义比较规则，这种思路就是贪心。

public String PrintMinNumber(int [] numbers) {
    int n = numbers.length;
    String[] nums = new String[n];
    for (int i = 0; i < n; i++) {
        nums[i] = String.valueOf(numbers[i]);
    }
    Arrays.sort(nums,(a,b)->(a+b).compareTo(b+a));
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        sb.append(nums[i]);
    }
    return sb.toString();
}

面试题46：把数字翻译成字符串

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

解题思路

将数字的每一位填充到一个数组中，每1位数字有1种翻译方式，对于2位数字，如果在10~25之间则有两种翻译方式（拆开翻译和合起来翻译），否则只有一种翻译方式（拆开来翻译）。使用动态规划思想，如果当前扫描到的数组的最后2位数在10~25之间，则翻译方式为dp[i-2]+dp[i-1]，否则为dp[i-1]。

class Solution {
    public int translateNum(int num) {
        int length=0;
        int n=num;
        do {
            n/=10;
            length++;
        }while (n!=0);
        int[] array=new int[length];
        for (int i = length - 1; i >= 0; i--) {
            array[i]=num%10;
            num/=10;
        }
        return getResult(array);
    }

    public int getResult(int[] num) {
        //1位或2位数字时直接返回结果
        switch (num.length) {
            case 1:
                return 1;
            case 2:
                int value = num[0] * 10 + num[1];
                return (value > 9 && value < 26) ? 2 : 1;
        }

        //3位以上时使用dp数组保存结果
        int[] dp=new int[num.length+1];
        dp[1]=1;
        int value = num[0] * 10 + num[1];
        dp[2]= (value > 9 && value < 26) ? 2 : 1;

        for (int i = 3; i < dp.length; i++) {
            int last2num=num[i-2]*10+num[i-1];
            dp[i]=(last2num > 9 && last2num < 26)?dp[i-2]+dp[i-1]:dp[i-1];
        }
        return dp[dp.length-1];
    }
}

面试题47：礼物的最大价值

题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

解题思路

典型的动态规划求解问题：

public int maxValue(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];

    dp[0][0] = grid[0][0];
    for(int i = 1; i < m; i++){
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    for(int j = 1; j < n; j++){
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

考虑到dp数组中进行状态转移时，每次使用的数据只来源于上方和左侧，则可以进行状态压缩，使用一维的dp数组：

public int maxValue(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];

    dp[0] = grid[0][0];
    for(int j = 1; j < n; j++){
        dp[j] = dp[j-1] + grid[0][j];
    }

    for(int i = 1; i < m; i++){
        dp[0] += grid[i][0];
        for(int j = 1; j < n; j++){
            dp[j] = Math.max(dp[j], dp[j-1]) + grid[i][j];
        }
    }
    return dp[n-1];
}

面试题48；最长不含重复字符的子字符串

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，假设字符串中只包含'a'~'z'的字符计算该最长子字符串的长度。

示例

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

使用一个哈希数组储存某个字符是否出现过，使用left和right标记子字符串的两侧，一直向右搜索增加right直到字符串结束或者发现重复字符。

public int lengthOfLongestSubstring(String s) {
    if (s==null||s.length()==0) return 0;
    boolean[] hashIndex = new boolean[128];

    int right=-1,maxLen=0;
    for (int left=-1; left<s.length();left++ ) {
        if (left != -1) {
            hashIndex[s.charAt(left)]=false;
        }
        while (right + 1 < s.length() && !hashIndex[s.charAt(right + 1)]) {
            hashIndex[s.charAt(right + 1)]=true;
            right++;
        }
        maxLen=Math.max(maxLen,right-left);
    }
    return maxLen;
}