九章算法高级班笔记1.透析热门互联网公司 FollowUp面试题

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return -1 instead.

Given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

双指针问题

1. 相向型指针
2. 前向型指针(又叫窗口类型指针）

此题思路

开始我们很容易想到的方法是：

此时的时间复杂度是O(n^3),稍作改动记录一下sum, 可以使时间复杂度变为O(n^2)：

变成：

因为数组里的所有数值都是正的，所以算数组0到1位的和即s = 0， t= 1时候如果比7小，第一位的和即s = 1， t = 1的时候就不用看了；同理因为0到2位的和比7小，1到2位的和就不用算了：

所以我们总结了窗口类指针的模板, 重点是根据题目的不同改变需要满足的条件。这个优化有以下特点：

1. 优化思想通过两层for循环而来
2. 外层指针依然是依次遍历
3. 内层指针证明是否需要回退

这种方法的时间复杂度是O(2n)即O(n), 因为每个元素最多被访问两次：

固定了i，知道遇到第一个j使得和大于等于s，记录下来：

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: an integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        // write your code here
        int j = 0, i = 0;
        int sum =0;
        int ans = Integer.MAX_VALUE;
        for(i = 0; i < nums.length; i++) {
            while(j < nums.length && sum < s) {
                sum += nums[j];
                j ++;
            }
            if(sum >=s) {
                ans = Math.min(ans, j - i);
            }
            sum -= nums[i];
        }
        if(ans == Integer.MAX_VALUE)
            ans = -1;
        return ans;
    }
}

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3.

For “bbbbb” the longest substring is “b”, with the length of 1.

用hash记录下走过的characters

public class Solution {
    /**
     * @param s: a string
     * @return: an integer 
     */
     //方法一：
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[256]; // map from character's ASCII to its last occured index

        int j = 0;
        int i = 0;
        int ans = 0;
        for (i = 0; i < s.length(); i++) {
            while (j < s.length() && map[s.charAt(j)]==0) {
                map[s.charAt(j)] = 1;
                ans = Math.max(ans, j-i + 1);
                j ++;
            }
            map[s.charAt(i)] = 0;
        }

        return ans;
    }
}

Minimum Window Substring

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

If there is no such window in source that covers all characters in target, return the emtpy string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in source.

Clarification

Should the characters in minimum window has the same order in target?

Not necessary.

Example

For source = “ADOBECODEBANC”, target = “ABC”, the minimum window is “BANC”

public class Solution {    
//方法一:
    int initTargetHash(int []targethash, String Target) {
        int targetnum =0 ;
        for (char ch : Target.toCharArray()) {
            targetnum++;
            targethash[ch]++;
        }
        return targetnum;
    }
    boolean valid(int []sourcehash, int []targethash) {

        for(int i = 0; i < 256; i++) {
            if(targethash[i] > sourcehash[i])    
                return false;
        }
        return true;
    }
    public String minWindow(String Source, String Target) {
        // queueing the position that matches the char in T
        int ans = Integer.MAX_VALUE;
        String minStr = "";

        int[] sourcehash = new int[256];
        int[] targethash = new int[256];

        initTargetHash(targethash, Target);
        int j = 0, i = 0;
        for(i = 0; i < Source.length(); i++) {
            while( !valid(sourcehash, targethash) && j < Source.length()  ) {
                sourcehash[Source.charAt(j)]++;
                j++;
            }
            if(valid(sourcehash, targethash) ){
                if(ans > j - i ) {
                    ans = Math.min(ans, j - i );
                    minStr = Source.substring(i, j );
                }
            }
            sourcehash[Source.charAt(i)]--;
        }
        return minStr;
    }
}

其中valid函数可以优化，即加上一个count使得时间上O(256n)变成O(n);

我考虑用两个hashset：一个target_hash, 一个source_hash，实现下看看。

Longest Substring with At Most K Distinct Characters

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = “eceba”, k = 3,

T is “eceb” which its length is 4.

j不用退的情况，考虑我们的模板。

public class Solution {
    /**
     * @param s : A string
     * @return : The length of the longest substring 
     *           that contains at most k distinct characters.
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
          // write your code here
      int maxLen = 0;

      // Key: letter; value: the number of occurrences.
      Map<Character, Integer> map = new HashMap<Character, Integer>();
      int i, j = 0;
      char c;
      for (i = 0; i < s.length(); i++) {
        while (j < s.length()) {
          c = s.charAt(j);
          if (map.containsKey(c)) {
            map.put(c, map.get(c) + 1);
          } else {
            if(map.size() ==k) 
              break;
            map.put(c, 1);
          }
          j++;
        }

        maxLen = Math.max(maxLen, j - i);
        c = s.charAt(i);
        if(map.containsKey(c)){
          int count = map.get(c);
          if (count > 1) {
            map.put(c, count - 1);
          } else {
            map.remove(c);
          }
        }
      }
      return maxLen; 
  }  
}

做题及复习方法

定期停下脚步，整理自己做过的题目，对自己提三个问题:

1. 属于哪一类？是动规，哪种动规？背包？是双指针，是哪种双指针？归类到很细分的题目类型中2.同类的题目有什么相似之处？题目的问法啊？所有用dfs啊，最短用bfs啊做题的感觉？

   bfs一层一层啊，动规也是一层一层啊

   3.他们思考的思路是怎么样的？

葵花宝典四决

1. 课前预习课之前浏览一遍当前课需要讲的内容。最好是自己思考一下每道题的解法，如果时间不够，可以浏览一下每个题目的题意。这个非常有助于上课理解。
2. 课中笔记
3. 下课冥想
4. 课后作业作业题先自己想，想不出来看笔记，实在不行看code答案

Kth Smallest Number in Sorted Matrix

Find the kth smallest number in at row and column sorted matrix.

Example

Given k = 4 and a matrix:

[

[1 ,5 ,7],

[3 ,7 ,8],

[4 ,8 ,9],

]

return 5

总结：见到集合求Min/Max，就要想到堆

堆得push和pop是log(n)时间的操作，top即求min/max是O(1)时间的操作

堆有很多种实现方式，priority_queue是常用的一种，还有斐波那契堆之类的。

class Pair {
    public int x, y, val;
    public Pair(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}
class PairComparator implements Comparator {
    public int compare(Pair a, Pair b) {
        return a.val - b.val;
    }
}

public class Solution {
    /**
     * @param matrix: a matrix of integers
     * @param k: an integer
     * @return: the kth smallest number in the matrix
     */
    public int kthSmallest(int[][] matrix, int k) {
        // write your code here
        int[] dx = new int[]{0, 1};
        int[] dy = new int[]{1, 0};
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] hash = new boolean[n][m];
        PriorityQueue minHeap = new PriorityQueue(k, new PairComparator());
        minHeap.add(new Pair(0, 0, matrix[0][0]));

        for(int i = 0; i < k - 1; i ++){
            Pair cur = minHeap.poll();
            for(int j = 0; j < 2; j ++){
                int next_x = cur.x + dx[j];
                int next_y = cur.y + dy[j];
                Pair next_Pair = new Pair(next_x, next_y, 0);
                if(next_x < n && next_y < m && !hash[next_x][next_y]){
                    hash[next_x][next_y] = true;
                    next_Pair.val = matrix[next_x][next_y];
                    minHeap.add(next_Pair);
                }
            }
        }
        return minHeap.peek().val;
    }
}

Kth Largest in N Arrays

You can swap elements in the array

Example

In n=2 arrays [[9,3,2,4,7],[1,2,3,4,8]], the 3rd largest element is 7.

In n=2 arrays [[9,3,2,4,8],[1,2,3,4,2]], the 1st largest element is 9, 2nd largest element is 8, 3rd largest element is 7 and etc.

总结：见到数组先排序

用什么数据结构？

堆

方法：

1. 把N个数组先排序
2. 排序过后把每个数组最大的数字放入堆里面
3. 然后堆里面只维护前N个元素
4. 堆pop k次得到答案。
5. 时间复杂度N*Len*Log(len)+K*logN (len 是平均每个数组的长度)

import java.util.Comparator;  
import java.util.PriorityQueue;  
import java.util.Queue; 

class Node {
    public int value, from_id, index;
    public Node(int _v, int _id, int _i) {
        this.value = _v;
        this.from_id = _id;
        this.index = _i;
    }
}

public class Solution {
    /**
     * @param arrays a list of array
     * @param k an integer
     * @return an integer, K-th largest element in N arrays
     */
    public int KthInArrays(int[][] arrays, int k) {
        // Write your code here
        Queue queue =  new PriorityQueue(k, new Comparator() {  
                public int compare(Node o1, Node o2) {  
                    if (o1.value > o2.value)
                        return -1;
                    else if (o1.value < o2.value)
                        return 1;
                    else
                        return 0;
                }
            }); 

        int n = arrays.length;
        int i;
        for (i = 0; i < n; ++i) {
            Arrays.sort(arrays[i]);

            if (arrays[i].length > 0) {
                int from_id = i;
                int index = arrays[i].length - 1;
                int value = arrays[i][index];
                queue.add(new Node(value, from_id, index));
            }
        }

        for (i  = 0; i < k; ++i) {
            Node temp = queue.poll();
            int from_id = temp.from_id;
            int index = temp.index;
            int value = temp.value;

            if (i == k - 1)
                return value;

            if (index > 0) {
                index --;
                value = arrays[from_id][index];
                queue.add(new Node(value, from_id, index));
            }
        }

        return -1;
    }
}

Kth Smallest Sum In Two Sorted Arrays

Given two integer arrays sorted in ascending order and an integer k. Define sum = a + b, where a is an element from the first array and b is an element from the second one. Find the kth smallest sum out of all possible sums.

Given [1, 7, 11] and [2, 4, 6].

For k = 3, return 7.

For k = 4, return 9.

For k = 8, return 15.

class Pair {
    public int x, y, sum;
    public Pair(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.sum = val;
    }
}
class PairComparator implements Comparator {
    public int compare(Pair a, Pair b) {
        return a.sum - b.sum;
    }
}

public class Solution {
    /**
     * @param A an integer arrays sorted in ascending order
     * @param B an integer arrays sorted in ascending order
     * @param k an integer
     * @return an integer
     */
    public int kthSmallestSum(int[] A, int[] B, int k) {
        int[] dx = new int[]{0, 1};
        int[] dy = new int[]{1, 0};
        boolean[][] hash = new boolean[A.length][B.length];
        PriorityQueue minHeap = new PriorityQueue(k, new PairComparator());
        minHeap.add(new Pair(0, 0, A[0] + B[0]));

        for(int i = 0; i < k - 1; i ++){
            Pair cur = minHeap.poll();
            for(int j = 0; j < 2; j ++){
                int next_x = cur.x + dx[j];
                int next_y = cur.y + dy[j];
                Pair next_Pair = new Pair(next_x, next_y, 0);
                if(next_x < A.length && next_y < B.length &&  !hash[next_x][next_y]){
                    hash[next_x][next_y] = true;
                    next_Pair.sum = A[next_x] + B[next_y];
                    minHeap.add(next_Pair);
                }
            }
        }
        return minHeap.peek().sum;
    }
}

三道题小总结

三道题相似点：

求矩阵/数组的第k大

可以总结的规律

1. 见到需要维护一个集合的最小值/最大值的时候要想到用堆
2. 第k小的元素，Heap用来维护当前候选集合。
3. 见到数组要想到先排序

怎么解决不会做follow up问题

1.定期整理自己做过的题目，Note

2.学会反思:

它属于哪一类？(归类)

和它同类的题目有什么相似之处？（集体特征）

这些题目思考的思路是怎么样的？（这个题属于哪一类）

 

本节要点概览：

1. 窗口问题想两个指针，两个指针中j不用回退想for while模板
2. 看出现次数和重复的时候，可以用set， map和数组，还可以加count记录在案个数
3. 见到需要维护一个集合的最小值/最大值的时候要想到用堆
4. 第k小的元素，Heap用来维护当前候选集合。
5. 见到数组要想到先排序