九章算法高级班笔记7.Follow Up Question

Overview: cs3k.com 

1. Subarray sum 3 follow up
2. Continuous Subarray Sum 2 follow up
3. Wiggle Sort 2 follow up
4. Partition 3 follow up
5. Iterator 3 follow up

Subarray Sum

cs3k.com 

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Notice

There is at least one subarray that it’s sum equals to zero.

Have you met this question in a real interview? Yes
Example
Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        // write your code here
       
        int len = nums.length;
       
        ArrayList<Integer> ans = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       
        map.put(0, -1);
       
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
           
            if (map.containsKey(sum)) {
                ans.add(map.get(sum) + 1);
                ans.add(i);
                return ans;
            }
            
            map.put(sum, i);
        }
       
        return ans;
    }
}

Submatrix Sum

cs3k.com 

Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

Example
Given matrix

  [1 , 5 , 7]
  [3 , 7 ,-8]
  [4 ,-8 , 9]

return [(1,1), (2,2)]

可以for循环暴力做

for lx = 0 ~ n
    for ly = 0 ~ n
        for rx = lx ~ n
            for ry = ly ~ n

时间复杂度是O(n^4)

接着我们可以想枚举行， 对于

  [1 , 5 , 7]
  [3 , 7 ,-8]
  [4 ,-8 , 9]

的第0行和第1行来说，我们算出每列的sum：

   [1 , 5 ,  7]
      [3 , 7 , -8]
  sum [4 , 12, -1]

然后我们就把每个列变成了一个列的和的值；
所以寻找二维的子矩阵就变成了寻找一维的子数组问题。

public class Solution {
    /**
     * @param matrix an integer matrix
     * @return the coordinate of the left-up and right-down number
     */
    public int[][] submatrixSum(int[][] matrix) {
        int[][] result = new int[2][2];
        int M = matrix.length;
        if (M == 0) return result;
        int N = matrix[0].length;
        if (N == 0) return result;
        // pre-compute: sum[i][j] = sum of submatrix [(0, 0), (i, j)]
        int[][] sum = new int[M+1][N+1];
        for (int j=0; j<=N; ++j) sum[0][j] = 0;
        for (int i=1; i<=M; ++i) sum[i][0] = 0;
        for (int i=0; i<M; ++i) {
            for (int j=0; j<N; ++j)
                sum[i+1][j+1] = matrix[i][j] + sum[i+1][j] + sum[i][j+1] - sum[i][j];
        }
        for (int l=0; l<M; ++l) {
            for (int h=l+1; h<=M; ++h) {
                Map<Integer, Integer> map = new HashMap<Integer, Integer>();
                for (int j=0; j<=N; ++j) {
                    int diff = sum[h][j] - sum[l][j];
                    if (map.containsKey(diff)) {
                        int k = map.get(diff);
                        result[0][0] = l;   result[0][1] = k;
                        result[1][0] = h-1; result[1][1] = j-1;
                        return result;
                    } else {
                        map.put(diff, j);
                    }
                }
            }
        }
        return result;
    }
}

Subarray Sum II

cs3k.com 

Given an integer array, find a subarray where the sum of numbers is in a given interval. Your code should return the number of possible answers. (The element in the array should be positive)
Example
Given [1,2,3,4] and interval = [1,3], return 4. The possible answers are:

[0, 0]
[0, 1]
[1, 1]
[2, 2]

对于数组，我们需要计算一个presum数组：

       [1,  2,  3,  4]
pre   [0,  1,  3,  6, 10]

如果一个子数组在1和3之间，就相当于我们有了等式：

1 <= pre[j+1] - pre[i] <= 3

然后我们可以进行两步：

1. for j = 0 ~ n
2. 找对应范围内[pre[j+1]-3, pre[j+1]-1]曾经遍历的个数

我们可以二分法优化， 找>=pre[j+1]-3的最小元素和小于等于pre[j+1]-1的最小元素，时间变成(n*logn)。

public class Solution {
    /**
     * @param A an integer array
     * @param start an integer
     * @param end an integer
     * @return the number of possible answer
     */
    int find(int[] A, int len, int value) {
        if (A[len-1] < value )
            return len;
        
        int l = 0, r = len-1, ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (value <= A[mid]) {
                ans = mid;
                r = mid - 1;
            }  else
                l = mid + 1;
        }
        return ans;
    }

    public int subarraySumII(int[] A, int start, int end) {
        // Write your code here
        int len = A.length;
        for (int i = 1; i <len; ++i)
            A[i] += A[i-1];

        int cnt = 0;
        for (int i = 0; i <len; ++i) {
            if (A[i] >= start && A[i] <= end)
                cnt ++;
            int l = A[i] - end;
            int r = A[i] - start;
            cnt += find(A, len, r+1) - find(A, len, l); 
        }
        return cnt;
    }
}

Continuous Subarray Sum

cs3k.com 

Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)

Example
Give [-3, 1, 3, -3, 4], return [1,4].

public class Solution {
    /**
     * @param A an integer array
     * @return  A list of integers includes the index of the first number and the index of the last number
     */
    public ArrayList<Integer> continuousSubarraySum(int[] A) {
        // Write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(0);
        result.add(0);

        int len = A.length;
        int start = 0, end = 0;
        int sum = 0;
        int ans = -0x7fffffff;
        for (int i = 0; i < len; ++i) {
            if (sum < 0) {
                sum = A[i];
                start = end = i;
            } else {
                sum += A[i];
                end = i;
            }
            if (sum >= ans) {
                ans = sum;
                result.set(0, start);
                result.set(1, end);
            }
        }
        return result;
    }
}

Maximum Subarray

cs3k.com 

Given an array of integers, find a contiguous subarray which has the largest sum.

Notice

The subarray should contain at least one number.

Example
Given the array [?2,2,?3,4,?1,2,1,?5,3], the contiguous subarray [4,?1,2,1] has the largest sum = 6.

就是f[i]以i作为结尾的子数组的和最大是多少， 对于每个i都有两种情况，取和不取。

public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum);
            sum = Math.max(sum, 0);
        }

        return max;
    }
}

// Version 2: Prefix Sum

public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        
        int max = Integer.MIN_VALUE, sum = 0, minSum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
        }

        return max;
    }
}



public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        if(nums.length == 0){
            return 0; 
        }
        int n = nums.length;
        int[] global = new int[2];
        int[] local = new int[2];
        global[0] = nums[0];
        local[0] = nums[0];
        for(int i = 1; i < n; i ++) {  
            local[i % 2] = Math.max(nums[i], local[(i - 1) % 2] + nums[i]);  
            global[i % 2] = Math.max(local[i % 2], global[(i - 1) % 2]);  
        }  
        return global[(n-1) % 2];  
    }
}

Continuous Subarray Sum II

cs3k.com 

Given an circular integer array (the next element of the last element is the first element), find a continuous subarray in it, where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number.

If duplicate answers exist, return any of them.

Example
Give [3, 1, -100, -3, 4], return [4,1].

循环子数组的处理方式为三种：

1. 分裂
2. 倍增
3. 取反

这道题分裂貌似不太好分，倍增可以做， 假如栗子是：

[-3,  1,  3,  -3,  4]

我们把这个数组后面再接一个自己：

[-3,  1,  3,  -3,  4, -3,  1,  3,  -3,  4]

然后约束长度为n， 找答案，可以做，但是时间复杂度比较高， 是O(n^2).

还有一个做法就是取反，我们不是求最大的连续子数组么？
有两种情况：

 |————————---|  max  |———————————|
             start     end

和

 |     max   |-------|    max    |
              end     start

第一种情况很容易， 第二种情况呢， 因为整个数组的和是固定的，我们要求两边数组的最大值， 就求中间区间的最小值就好了。

public class Solution {
    /**
     * @param A an integer array
     * @return  A list of integers includes the index of the first number and the index of the last number
     */
    public List<Integer> continuousSubarraySumII(int[] A) {
        // Write your code here
        List<Integer> result = new ArrayList<Integer>();
        result.add(0);
        result.add(0);
        int total = 0;
        int len = A.length;
        int start = 0, end = 0;
        int local = 0;
        int global = -0x7fffffff;
        for (int i = 0; i < len; ++i) {
            total += A[i];
            if (local < 0) {
                local = A[i];
                start = end = i;
            } else {
                local += A[i];
                end = i;
            }
            if (local >= global) {
                global = local;
                result.set(0, start);
                result.set(1, end);
            }
        }
        local = 0;
        start = 0;
        end = -1;
        for (int i = 0; i < len; ++i) {
            if (local > 0) {
                local = A[i];
                start = end = i;
            } else {
                local += A[i];
                end = i;
            }
            if (start == 0 && end == len-1) continue;
            if (total - local >= global) {
                global = total - local;
                result.set(0, (end + 1) % len);
                result.set(1, (start - 1 + len) % len);
            }
        }
        return result;
    }
}
    

Kth Largest Element

cs3k.com 

Find K-th largest element in an array.

Notice

You can swap elements in the array

Example
In array [9,3,2,4,8], the 3rd largest element is 4.

In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

1. PriorityQueue

• 时间复杂度O(nlogk)
• 更适合Topk

2. QuickSelect

• 时间复杂度O(n)
• 更适合第k大

partition问题模板

quick sort模板

import java.util.Random;

public class Solution {
    /*
     * @param A: an integer array
     * @return: 
     */
    public Random rand;
    public void sortIntegers2(int[] A) {
        rand = new Random();
        // write your code here
        quickSort(A, 0, A.length - 1);
    }
    
    public void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }

        int index = rand.nextInt(end - start + 1)  + start;
        int pivot = A[index];
        int left = start;
        int right = end;
        
        while (left <= right) {
            while (left <= right && A[left] < pivot) {
                left ++;
            }
            while (left <= right && A[right] > pivot) {
                right --;
            }
            
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                
                left ++;
                right --;
            }
        }
        // A[start... right] 
        quickSort(A, start, right);
        // A[left ... end]
        quickSort(A, left, end);
    }
}

merge sort：

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // use a shared temp array, the extra memory is O(n) at least
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }
    
    private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        
        int left = start, right = end;
        int mid = (start + end) / 2;

        mergeSort(A, start, mid, temp);
        mergeSort(A, mid+1, end, temp);
        merge(A, start, mid, end, temp);
    }
    
    private void merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid+1;
        int index = start;
        
        // merge two sorted subarrays in A to temp array
        while (left <= mid && right <= end) {
            if (A[left] < A[right]) {
                temp[index++] = A[left++];
            } else {
                temp[index++] = A[right++];
            }
        }
        while (left <= mid) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }
        
        // copy temp back to A
        for (index = start; index <= end; index++) {
            A[index] = temp[index];
        }
    }
}

class Solution {
    /*
     * @param k : description of k
     * @param nums : array of nums
     * @return: description of return
     */
    public int kthLargestElement(int k, int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (k <= 0) {
            return 0;
        }
        return helper(nums, 0, nums.length - 1, nums.length - k + 1);
        
    }
    public int helper(int[] nums, int l, int r, int k) {
        if (l == r) {
            return nums[l];
        }
        int position = partition(nums, l, r);
        if (position + 1 == k) {
            return nums[position];
        } else if (position + 1 < k) {
            return helper(nums, position + 1, r, k);
        }  else {
            return helper(nums, l, position - 1, k);
        }
    }
    public int partition(int[] nums, int l, int r) {
        // 初始化左右指针和pivot
        int left = l, right = r;
        int pivot = nums[left];
        
        // 进行partition
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        
        // 返还pivot点到数组里面
        nums[left] = pivot;
        return left;         
    }
};


class Solution {
    /*
     * @param k : description of k
     * @param nums : array of nums
     * @return: description of return
     */
    public int kthLargestElement(int k, int[] nums) {

        // write your code here
        int low = 0, high = nums.length -1;
        while(low <= high){  
            int pivot = nums[high];
            int index = low-1;
            for(int i = low; i < high; i++){
                if(nums[i] > nums[high]){
                    swap(nums, i, ++index);
                }
            }
            swap(nums, ++index, high);
            if(index == k - 1){
                return nums[index];
            }
            if(index < k -1){
                low = index + 1;
            }else{
                high = index - 1;
            }
        }
        return -1;
    }
    
    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
};

quick select时间复杂度平均是O(2*n), 最坏可能达到O(n^2)
quick sort的时间平均是O(nlogn), 因为quick select分两半之后是丢一半， 排一半。而quick sort是两边都要分别排序。quick sort最差也可能是O(n^2)。

Wiggle Sort

cs3k.com 

Given an unsorted array nums, reorder it in-place such that

nums[0] <= nums[1] >= nums[2] <= nums[3]…

Please complete the problem in-place.
Example
Given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

public class Solution {
    /**
     * @param nums a list of integer
     * @return void
     */
    public void wiggleSort(int[] nums) {
        // Write your code here
        for(int i=1; i<nums.length; i++) {
            if((i%2==1 && (nums[i] < nums[i-1]) || 
              (i%2==0) && (nums[i] > nums[i-1]))) {
                swap(nums, i-1, i);
            }
        }
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Wiggle Sort II

cs3k.com 

Given an unsorted array nums, reorder it such that

nums[0] < nums[1] > nums[2] < nums[3]…
Notice

You may assume all input has valid answer.
Example
Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].

Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

首先， 可能回想先排个序， 然后两个指针取元素。
其次如果优化的话， 可以partition找中位数， 然后左边取一个， 右边取一个。

public class Solution {
    public static void wiggleSort(int[] nums) {
        int[] tem = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            tem[i] = nums[i];
        }
        int mid = partition(tem, 0, nums.length-1, nums.length/2);
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = mid;
        }
        int l, r;
        if (nums.length % 2 == 0) {
            l = nums.length - 2;
            r = 1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < mid) {
                    ans[l] = nums[i];
                    l -= 2;
                } else if (nums[i] > mid) {
                    ans[r] = nums[i];
                    r += 2;
                }
            }
        } else {
            l = 0;
            r = nums.length - 2;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < mid) {
                    ans[l] = nums[i];
                    l += 2;
                } else if (nums[i] > mid) {
                    ans[r] = nums[i];
                    r -= 2;
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = ans[i];
        }
    }
    public static int partition(int[] nums, int l, int r, int rank) {
        int left = l, right = r;
        int now = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= now) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= now) {
                left++;
            }
            nums[right] = nums[left];
        }
        if (left - l == rank) {
            return now;
        } else if (left - l < rank) {
            return partition(nums, left + 1, r, rank - (left - l + 1));
        } else {
            return partition(nums, l, right - 1, rank);
        }
    }
}

Nuts & Bolts Problem

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.

We will give you a compare function to compare nut with bolt.
Example
Given nuts = [‘ab’,‘bc’,‘dd’,‘gg’], bolts = [‘AB’,‘GG’, ‘DD’, ‘BC’].

Your code should find the matching bolts and nuts.

one of the possible return:

nuts = [‘ab’,‘bc’,‘dd’,‘gg’], bolts = [‘AB’,‘BC’,‘DD’,‘GG’].

we will tell you the match compare function. If we give you another compare function.

the possible return is the following:

nuts = [‘ab’,‘bc’,‘dd’,‘gg’], bolts = [‘BC’,‘AA’,‘DD’,‘GG’].

So you must use the compare function that we give to do the sorting.

The order of the nuts or bolts does not matter. You just need to find the matching bolt for each nut.

用nuts给bolts来partition， 再用bolts给nuts来partition.

public class Solution {
    /**
     * @param nuts: an array of integers
     * @param bolts: an array of integers
     * @param compare: a instance of Comparator
     * @return: nothing
     */
    public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
        if (nuts == null || bolts == null) return;
        if (nuts.length != bolts.length) return;

        qsort(nuts, bolts, compare, 0, nuts.length - 1);
    }

    private void qsort(String[] nuts, String[] bolts, NBComparator compare, 
                       int l, int u) {
        if (l >= u) return;
        // find the partition index for nuts with bolts[l]
        int part_inx = partition(nuts, bolts[l], compare, l, u);
        // partition bolts with nuts[part_inx]
        partition(bolts, nuts[part_inx], compare, l, u);
        // qsort recursively
        qsort(nuts, bolts, compare, l, part_inx - 1);
        qsort(nuts, bolts, compare, part_inx + 1, u);
    }
    
    private int partition(String[] str, String pivot, NBComparator compare, 
                          int l, int u) {
        for (int i = l; i <= u; i++) {
            if (compare.cmp(str[i], pivot) == 0 || 
                compare.cmp(pivot, str[i]) == 0) {
                swap(str, i, l);
                break;
            }
        }
        String now = str[l];
        int left = l; 
        int right = u;
        while (left < right) {
            while (left < right && 
            (compare.cmp(str[right], pivot) == -1 || 
            compare.cmp(pivot, str[right]) == 1)) {
                right--;
            }
            str[left] = str[right];
            
            while (left < right && 
            (compare.cmp(str[left], pivot) == 1 || 
            compare.cmp(pivot, str[left]) == -1)) {
                left++;
            }
            str[right] = str[left];
        }
        str[left] = now;

        return left;
    }

    private void swap(String[] str, int l, int r) {
        String temp = str[l];
        str[l] = str[r];
        str[r] = temp;
    }
}

Flatten List

cs3k.com 

Given a list, each element in the list can be a list or integer. flatten it into a simply list with integers.

Notice

If the element in the given list is a list, it can contain list too.

Example
Given [1,2,[1,2]], return [1,2,1,2].

Given [4,[3,[2,[1]]]], return [4,3,2,1].

递归来解。

plus：c++ vector的reverse时间复杂度是O(n), 对称位置swap来做。

public class Solution {

    // @param nestedList a list of NestedInteger
    // @return a list of integer
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        // Write your code here
        List<Integer> result = new ArrayList<Integer>();
        for (NestedInteger ele : nestedList)
            if (ele.isInteger())
                result.add(ele.getInteger());
            else
                result.addAll(flatten(ele.getList()));
        return result;
    }
}

//non-recursive version
public class Solution {

    // @param nestedList a list of NestedInteger
    // @return a list of integer
    public List<Integer> flatten(List<NestedInteger> nestedList) {
        boolean isFlat = true;
        List<NestedInteger> ls = nestedList;
        while (isFlat) {
            isFlat = false;
            List<NestedInteger> newLs = new ArrayList<>();
            for (NestedInteger ni : ls) {
                if (ni.isInteger()) {
                    newLs.add(ni);
                } else {
                    newLs.addAll(ni.getList());
                    isFlat = true;
                }
            }
            ls = newLs;
        }
        List<Integer> r = new ArrayList<>();
        for (NestedInteger ni : ls) {
            r.add(ni.getInteger());
        }
        return r;
    }
}

Flatten Nested List Iterator

cs3k.com 

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Notice

You don’t need to implement the remove method.

Example
Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Given the list [1,[4,[6]]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

可以用递归来解。iterator和递归比起来，有个好处。是递归的时候，你中间不能做其它事情，而iterator用非递归的方式来实现，可以被打断。
这道题，不能预先存下来，然后再用个指针。因为iterator的意义是不到打印或者其它用的时候，不遍历。
解法就是用栈，思路不难，写法麻烦点：

1. next函数自己要调用hasNext
2. 栈的处理放在hasNext里面好一些

Iterator要点

cs3k.com 

1. List 转 Stack
2. 主函数逻辑放在HasNext里面
3. Next只做一次pop处理

模板：

import java.util.Iterator;

public class NestedIterator implements Iterator<Integer> {

    private Stack<NestedInteger> stack;
    
    private void pushListToStack(List<NestedInteger> nestedList) {
        Stack<NestedInteger> temp = new Stack<>();
        for (NestedInteger nested : nestedList) {
            temp.push(nested);
        }
        
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }
    
    public NestedIterator(List<NestedInteger> nestedList) {
        stack = new Stack<>();
        pushListToStack(nestedList);
    }

    // @return {int} the next element in the iteration
    @Override
    public Integer next() {
        if (!hasNext()) {
            return null;
        }
        return stack.pop().getInteger();
    }

    // @return {boolean} true if the iteration has more element or false
    @Override
    public boolean hasNext() {
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            pushListToStack(stack.pop().getList());
        }
        
        return !stack.isEmpty();
    }
    
    @Override
    public void remove() {}
}

Flatten 2D Vector

cs3k.com 

Implement an iterator to flatten a 2d vector.

Example
Given 2d vector =

  [1,2],
  [3],
  [4,5,6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

和上一道题类似，用栈。

public class Vector2D implements Iterator<Integer> {
    Stack<List<Integer>> stack = new Stack<>();
    Stack<Integer> stackj;
    
    void pushListListToStack(List<List<Integer>> vec2d) {
    Stack<List<Integer>> temp = new Stack<>();
        for (List<Integer> nested : vec2d) {
            temp.push(nested);
        }
        
        while (!temp.isEmpty()) {
            stack.push(temp.pop());
        }
    }
    
    void pushListToStack(List<Integer> vec) {
    Stack<Integer> temp = new Stack<>();
        for (Integer nested : vec) {
            temp.push(nested);
        }
        
        while (!temp.isEmpty()) {
            stackj.push(temp.pop());
        }
    }
    
    public Vector2D(List<List<Integer>> vec2d) {
        pushListListToStack(vec2d);
        // Initialize your data structure here
        stackj = new Stack<>();
    }

    public Integer next() {
        // Write your code here
        if(!hasNext()) {
            return null;
        }
        return stackj.pop();
    }

    public boolean hasNext() { // 准备下一个元素
        // Write your code here
        while (stackj.isEmpty() && !stack.isEmpty())
            pushListToStack(stack.pop());
        return !stackj.isEmpty();
    }
    
    public void remove() {}
}

Binary Search Tree Iterator

cs3k.com 

Design an iterator over a binary search tree with the following rules:

Elements are visited in ascending order (i.e. an in-order traversal)
next() and hasNext() queries run in O(1) time in average.

Example
For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 /    1      11
 \         6       12

把节点和节点所有的左儿子加入栈里面。
时间复杂度平摊是O(n)

public class BSTIterator {
    private Stack<TreeNode> stack = new Stack<>();
    TreeNode next = null;
    void AddNodeToStack(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    } 
    
    // @param root: The root of binary tree.
    public BSTIterator(TreeNode root) {
        next = root;
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        if (next != null) {
            AddNodeToStack(next);
            next = null;
        }
        return !stack.isEmpty();
    }
    
    //@return: return next node
    public TreeNode next() {
        if (!hasNext()) {
            return null;
        }
        TreeNode cur = stack.pop();
        next = cur.right;
        return cur;
    }
}

Follow Up 常见方式

cs3k.com 

1. 一维转二维

• 可以套相同的思路试一试
  • Find Peak Element I/II
  • Trapping Water I/II
  • Subarray Sum/Submatrix Sum

2. 数组变成循环数组

• 循环数组小技巧: 分裂 倍增 取反
  • Continuous Subarray Sum

3. 题目条件加强

• 可能题目的解题方法会变化，如果所有条件都不变，就一个条件变了，那基本要重新分析，不能套老方法。
  • Wiggle Sort I/II

4. 换马甲(变一个描述，本质不变)

• 本质不变
  • Number of airplane on the Sky/ Meeting Room
  • BackPack Problem

5. 描述完全不一样，但是方法相同

• 这种题目得去分析
  • 前向型指针的题目
  • Quick Sort/ Bolt Nuts Problem

九章算法高级班笔记7.Follow Up Question

原文：https://www.cnblogs.com/jiuzhangsuanfa/p/9895699.html