[dfs] how to deal with duplicates? 491. Increasing Subsequences

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

容易看出这是dfs的问题。
容易写出以下dfs的过程:

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(nums, 0, res, new ArrayList<Integer>());
        return res;
    }
    
    private void helper(int[] nums, int index, List<List<Integer>> res, List<Integer> list) {
        if (list.size() >= 2) {
            res.add(new ArrayList<Integer>(list));
        } 
        
        for (int i = index; i < nums.length; i++) {
            if (list.size() == 0 || nums[i] >= list.get(list.size() - 1)) {
                list.add(nums[i]);
                helper(nums, i + 1, res, list);
                list.remove(list.size() - 1); // 有和没有当前数字参与两种选择
            }
        }
    }

一个问题,如何避免duplicate?例如[4,6,7,7],[4,6,7]已经加上了,如何避免再加一次?
可以用以下简单方法:不同层recursion中,保证单次recursion调用每个数字只循环到一次。例如,[4,6,7,7]中,当前这次调用的循环中,已经循环到了4,6,7,再遇到7,就不管了。看以下code:

    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(nums, 0, res, new ArrayList<Integer>());
        return res;
    }
    
    private void helper(int[] nums, int index, List<List<Integer>> res, List<Integer> list) {
        if (list.size() >= 2) {
            res.add(new ArrayList<Integer>(list));
        } 
        
        Set<Integer> unique = new HashSet<Integer>();
        for (int i = index; i < nums.length; i++) {
            if (list.size() == 0 || nums[i] >= list.get(list.size() - 1)) {
                if (!unique.add(nums[i])) continue;//对当前循环相同数字只能用一次 
                unique.add(nums[i]); //记录当前循环到的数字,用当前list再去递归的不用想
                list.add(nums[i]);
                helper(nums, i + 1, res, list);
                list.remove(list.size() - 1);
            }
        }
    }

[dfs, dp] 494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and – as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

DFS的思路首先想出来,顺利写出来:

    public int findTargetSumWays(int[] nums, int S) {
        return helper(nums, S, 0, 0, 0);
    }
    
    private int helper (int[] nums, int S, int index, int sum, int count) {
        if (index == nums.length) {
            if (sum == S) return count + 1;
            else return count;
        } 
        int count1 = helper(nums, S, index + 1, sum + nums[index], count);
        int count2 = helper(nums, S, index + 1, sum - nums[index], count);
        return count1 + count2;
    }

这种recusion其实都类似,一般都在helper函数里需要给index,记录当前看到哪个元素;原函数需要什么就return什么(需要count就return count,需要所有的排列组合就return list或者set之类的)。

但是,recusion很慢,写的时候也能感觉到,各种排列组合应该有很多重复的时候。

一般,dfs的问题想improve,可以考虑dp。只是这个问题直接从dfs的code改成dp,无从下手。

要及时抛弃已经有的dfs code,重新想思路。

新思路:题目转化找到一个subset都是positive,剩下的subset都是negative,使得 P – N == target. 已知 P + N == sum, 则 2P = target + sum, p = (target + sum) / 2。题目转化成找到一个subset,使其和等于(target + sum) / 2。这个新问题,用dp做。

    private int helper(int[] nums, int target) {
        int[] dp = new int[target + 1]; //存有几种组合可以达到当前目标(1...target)
        dp[0] = 1;
        for (int n : nums) {
            for (int i = target; i >= n; i--) { //倒着看
                dp[i] += dp[i - n]; //新来的数是n,现在只要可以达到i-n就可以达到i
            }
        }
        return dp[target];
    }

可以考虑dp解决这个新问题也是一个模版,而且是典型的dp模版。

[dfs] 473. Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:
Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.
Note:
The length sum of the given matchsticks is in the range of 0 to 10^9.
The length of the given matchstick array will not exceed 15.

想到的部分:把所有数字分为4组,使每组和为sum / 4。如果sum % 4 != 0 或者一共有小于4个数字就不可能形成正方形。分组的过程用dfs。
没想清楚的部分:dfs怎么实现。

public boolean makesquare(int[] nums) {
    if (nums == null || nums.length < 4) return false;
    int total = 0;
    for (int num : nums) total += num;
    if (total % 4 != 0) return false;
    return dfs(nums, total / 4, new int[4], 0);
}
    
private boolean dfs(int[] nums, int target, int[] sums, int index) {
    if (index == nums.length) {
        if (sums[0] == target && sums[1] == target && sums[2] == target) return true;
        return false;
    }
        
    for (int i = 0; i < 4; i++) { //尝试当前数字要加到哪个组
        if (sums[i] + nums[index] > target) continue;
        sums[i] += nums[index];
        if (dfs(nums, target, sums, index + 1)) return true;
        sums[i] -= nums[index];
    }
        
    return false;
}

本题需要找到4个sum,其实相对找到1个sum,增加的复杂度并不大,以下是另外一种实现,更加直接。
另,本来想到了,但是没有好好加进去的optimization:先sort数组,从最大数字开始尝试,这样如果不行会尽早发现。

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) return false;
        int total = 0;
        for (int num : nums) total += num;
        if (total % 4 != 0) return false;
        Arrays.sort(nums);
        long sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
        return dfs(nums, total / 4, sum1, sum2, sum3, sum4, nums.length - 1);
    }
    
    private boolean dfs(int[] nums, int target, long sum1, long sum2, long sum3, long sum4, int i) {
        if (sum1 > target || sum2 > target || sum3 > target || sum4 > target) return false;
        if (i == -1 && sum1 == target && sum2 == target && sum3 == target) return true;
        else if (i == -1) return false;
        
        return dfs(nums, target, sum1+nums[i], sum2, sum3, sum4, i-1) ||
               dfs(nums, target, sum1, sum2+nums[i], sum3, sum4, i-1) ||
               dfs(nums, target, sum1, sum2, sum3+nums[i], sum4, i-1) ||
               dfs(nums, target, sum1, sum2, sum3, sum4+nums[i], i-1);
    }

[bit manipulation] 476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

~num取反 但是把所有leading 0都跟着取反了。例如5: 101, ~5 不是010, 是1111..010。
所以制作一个mask,111, 使~num & mask即可。
如何制作mask?一个可以到处用的trick:

(Integer.highestOneBit(num) << 1) – 1

例如5,Integer.highestOneBit(num) = 0b100, 右移一位变成 1000,再减1变成111

[bit manipulation] 421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n. Could you do this in O(n) runtime? Example: Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28. 分别计算每一位应该是什么

 public int findMaximumXOR(int[] nums) {        int max = 0, mask = 0;        for (int i = 31; i >= 0; i--) { //从最重要的位MSB看起
           mask = mask | 1 << i; // 每次只看一位,用mask控制看哪位
           Set<Integer> set = new HashSet();
           for (int num : nums) {
               set.add(num & mask); //记录所有nums在这一位是什么情况
           }
           int tmp = max | (1 << i); //结果在当前位暂时设为1
           for (int prefix : set) {
               if (set.contains(tmp ^ prefix)) {
                   max = tmp; //如果有在这一位有和max不同的,那么max在这一位就真的可以是1
                   break;
               }
           }
       }
       return max;

    }

[bit manipulation]477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

Brute force: time limit exceed
思路:integer一共32位, int[] count = new int[32]记录每个bit一共在几个数字中on(一共n = nums.length个数字)。对于一个bit,on的次数 k 次,off的次数 n-k 次,则对于total distance的贡献是 k * (n-k),因为每一个(on, off)的组合都会给total distance加1.

    public int totalHammingDistance(int[] nums) {
        int N = nums.length;
        int[] count = new int[32]; // count for when the bit is on
        for (int n : nums) {
            int i = 0;
            while (n > 0) {
                count[i++] += n & 1;
                n >>= 1;
            }
        }
        
        int total = 0;
        for (int i = 0; i < 32; i++) {
            total += count[i] * (N - count[i]);
        }
        return total;
    }

[sliding window] 424. Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string’s length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

用sliding window,但是几点要注意。
什么时候往右扩大window?只要当前 窗口长度 不超过 最大的重复字母count + k(k可以理解为容错度)
什么时候调整window的起始?当以上条件不符时
maxcount代表什么?不是当前窗口内的 最大重复字母count,而是史上最大的重复字母count,我们只关心史上出现的最大valid串长度

public int characterReplacement(String s, int k) {
    int start = 0, maxlen = 0, maxcount = 0; 
    int[] count = new int[26];
    for (int end = 0; end < s.length(); end++) {
        maxcount = Math.max(maxcount, ++count[s.charAt(end) - 'A']);
        while (end - start + 1 > maxcount + k) {
            count[s.charAt(start++) - 'A']--;
        } 
        maxlen = Math.max(maxlen, end - start + 1);
    }
    return maxlen;
}

398. Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

Reservoir Sampling

public class Solution {
    int[] nums;
    Random r;

    public Solution(int[] nums) {
        this.nums = nums;
        r = new Random();
    }
    
    public int pick(int target) {
        int idx = 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != target) continue;
// for the nth target, the prob of returning is 1/n
// for the (n-1)th target, the prob of returning is (n-1)/n * 1/(n-1) = 1/n
            if (r.nextInt(++count) == 0) {
                idx = i; 
            }
        }
        
        return idx;
        
    }
}

[summary] Graph BFS solves problems

210: Course Schedule II
269: Alien Dictionary
题目描述见网站

210: 课程的dependency本来就存在edges数组表示,可以转换成map方便访问,然后对graph进行bfs
269: 从dict中抽出字母先后顺序,字母组成一个graph,对graph进行bfs

bfs的过程:

Queue先存入in degree为0的点
当queue不为空时:
取出点,加入结果
此点在map中指向的所有下一个点,给他们的in degree都减1
此时in degree为0的点重新加入queue

其实是有顺序的bfs,顺序为先访问dependency最小的点。这个方法两道题都可以解决。

132. Palindrome Partitioning II

从夏威夷回来又休息了几天,继续做题继续更博。

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

public int minCut(String s) {
        int n = s.length();
        int[] cut = new int[n+1];
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            // check odd length palindrome
            for (int j = 0; i-j >=0 && i+j < n && s.charAt(i-j) == s.charAt(i+j); j++) {
                cut[i+j+1] = Math.min(cut[i+j+1], 1+cut[i-j]);
            }
            
            // check even length palindrome
            for (int j = 0; i-j >= 0 && i+j+1 < n && s.charAt(i-j) == s.charAt(i+j+1); j++) {
                cut[i+j+2] = Math.min(cut[i+j+2], 1+cut[i-j]);
            }
        }
        
        return cut[n];
    }

DP题目有时候思路很简单很对称。这道题的基本思路如下:
假设 a b a c
用一个数组表示截止到每个字母(字母前)有几个cut
初始值为:
str = [a b a c]
cut = [0 1 2 3]

以第i个字母为中心,check它左右对称位置的字母是否相等,如果相等,则组成了palindrome,那么cut就应该相应的减少。

例如在b的位置, i = 1, str[i-1] == str[i+1], 所以在i+1这个位置的后面,即cut[i+2],cut数变成min(cut[i+2], cut[i-1] + 1)
[a, b, a, c]
[0, 1, 2, 1]

以上palindrome是odd length,再举一个even length的例子
str = [b, a, a, b, c]
cut = [0, 1, 2, 3, 4]
例如在i = 1的位置 str[i-0] == str[i+0+1], str[i-1] == str[i+1+1], 所以在cut[i+3]的位置上,变成min(cut[i+3], cut[i-1] + 1)

总结以上两个例子,
odd length: i-j >= 0 && i+j = 0 && i+j+1 < cut.length && str[i-j] == str[i+j+1]情况下,
cut[i+j+2] = min(cut[i+j+2], 1+cut[i-j])。需要保证i+j+2在cut长度范围内。

注意,如果整个str就是一个palindrome,例如
str = [b, b]
对于i = 0, 只check j = 0的时候,因为需要保证i+j+1在cut长度范围内,这样就找不到palindrome了。所以cut长度选为n+1而不是n,n是str的长度。