发表于 | 分类于

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

1
2
3
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

1
2
3
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

解法1：

很好的一题，用到了2sum = zero的特殊解法（用hashmap）， 也用到了变换条件使得题目变得更有利。
把0变成-1的话这题的条件就变成找一个continuous array使得加和为1并且最长。
加和为0很好办，看sum是否出现过，如果出现过，更新最长距离。要注意初始条件，第一个点是设成map.put(0, -1)
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    public int findMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                nums[i] = -1;
            }
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        int sum = 0, max = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                // prefix sum exists, meaning sum[i, j] = 0 => equal number of 1 and 0 (now -1)
                max = Math.max(max, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return max;
    }
}

发表于 | 分类于

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

1
2
3
4
5
6
7
8
9
Input:
[[1,2,2,1],
 [3,1,2],
 [1,3,2],
 [2,4],
 [3,1,2],
 [1,3,1,1]]
Output: 2
Explanation:

picture

Note:
The width sum of bricks in different rows are the same and won’t exceed INT_MAX.
The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.

解法1：

自己想的很复杂，模模糊糊的有一个轮廓。
答案给的很brilliant， 就是说我们yaocut的位置一定是在砖块对齐最多的位置。这个位置是most common right position of bricks
要注意循环的时候是到size() - 1, 为的是避免右面的边界。
C++

1

Java

1

发表于 | 分类于

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

1
2
Input: nums = [1,2,2,4]
Output: [2,3]

Note:
The given array size will in the range [2, 10000].
The given array’s numbers won’t have any order.

解法1：

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int[] findErrorNums(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        }
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) > 1) {
                res[0] = num;
            }
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!map.containsKey(i)) {
                res[1] = i;
                return res;
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ? k ? number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

解法1： heap

比较直接的写法就是用heap，不过还有一种bucket sort的办法似乎更快，可以做到O(N)
C++

1

Java
有一个Java8的compare写法可以掌握一下(a,b) -> a.getValue() - b.getValue()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        // map with keySet
        // [1,1,1,2,2,3]
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // Put each elements into priorityqueue
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((a,b) -> a.getValue() - b.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.offer(entry);
            if (queue.size() > k) {
                queue.poll();   // poll the smallest entry based on the frequency
            }
        }
        while (!queue.isEmpty()) {
            res.add(queue.poll().getKey());
        }
        return res;
    }
}

解法2： Bucket 思想

基本的思路是，先用一个hashmap存储每一个num出现的次数。
然后最大的可能出现的次数就是nums的长度，所以可以用一个数组，每一个元素是一个list，记录当前频率下的所有数字。
这样以来，最后只需要从大到小的扫描一遍就可以得到答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<Integer> topKFrequent(int[] nums, int k) {
	List<Integer>[] bucket = new List[nums.length + 1];
	Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
	for (int n : nums) {
		frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
	}
	for (int key : frequencyMap.keySet()) {
		int frequency = frequencyMap.get(key);
		if (bucket[frequency] == null) {
			bucket[frequency] = new ArrayList<>();
		}
		bucket[frequency].add(key);
	}
	List<Integer> res = new ArrayList<>();
	for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
		if (bucket[pos] != null) {
			res.addAll(bucket[pos]);
		}
	}
	return res;
}

发表于 | 分类于

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.
Credits:

解法1：HashMap

能写成分数的一定是有理数，有理数一定是有限的或者是无限循环小数。
先计算整数部分，然后看余数是否为0。如果不是零，那么把每一个数放入map中，记录他们出现的位置。然后乘以10再取余，

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        sb.append(((numerator > 0) ^ (denominator > 0)) ? "-" : "");
        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);
        // Get integral part
        sb.append(num / den);
        num %= den;
        if (num == 0) {
            return sb.toString();
        }
        // process fraction
        Map<Long, Integer> map = new HashMap<Long, Integer>();    // Record the position that each digit exist
        sb.append(".");
        map.put(num, sb.length());
        while (num != 0) {
            num *= 10;
            sb.append(num / den);
            num %= den;
            if (map.containsKey(num)) {
                int index = map.get(num);
                sb.insert(index, "(");
                sb.append(")");
                break;  // end the search
            } else {
                map.put(num, sb.length());
            }
        }
        return sb.toString();
    }
}

发表于 | 分类于

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn’t one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

解法1：

用prefix sum数组解决， 用一个map记录每一个accumulate sum对应的位置。然后线性扫描一遍加和数组，对于没有见过的数直接加入map，对于见过的就可以判断是否存在dp[i] - k, 注意。这题没有说是否有duplicate，实际是可能的，而我们push进map的都是第一次出现的位置，这样保证了如果找到一个解，一定是最长的一个subarray。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 0);  // don't forget to put this into hashmap
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int remain = dp[i] - k;
            if (map.containsKey(remain)) {
                max = Math.max(max, i - map.get(remain));
            }
            if (!map.containsKey(dp[i])) {
                map.put(dp[i], i);
            }
        }
        return max;
    }
}

发表于 | 分类于

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = “makes”, word2 = “coding”, return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

解法1：

先用hashmap没有疑问，之后在map中寻找最近的一对pair的时候可以用O(m+n)的复杂度解决，诀窍就是two pointers
按照大小顺序移动两个pointer

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class WordDistance {
    HashMap<String, List<Integer>> map = null;
    public WordDistance(String[] words) {
        map = new HashMap<String, List<Integer>>();   
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (!map.containsKey(word)) {
                map.put(word, new ArrayList<Integer>());
            }
            map.get(word).add(i);
        }
    }
    public int shortest(String word1, String word2) {
        List<Integer> index1 = map.get(word1);
        List<Integer> index2 = map.get(word2);
        int res = Integer.MAX_VALUE;
        int i = 0, j = 0;
        while (i < index1.size() && j < index2.size()) {
            int ii = index1.get(i);
            int jj = index2.get(j);
            res = Math.min(res, Math.abs(jj - ii));
            if (ii < jj) {
                i++;
            } else {
                j++;
            }
        }
        return res;
    }
}
/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */

发表于 | 分类于

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples:

1
2
3
4
5
6
7
8
Given binary tree [3,9,20,null,null,15,7],
   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7

return its vertical order traversal as:

1
2
3
4
5
6
[
  [9],
  [3,15],
  [20],
  [7]
]

Given binary tree [3,9,8,4,0,1,7],

1
2
3
4
5
6
7
    3
   /\
  /  \
  9   8
 /\  /\
/  \/  \
4  01   7

return its vertical order traversal as:

1
2
3
4
5
6
7
[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

Given binary tree [3,9,8,4,0,1,7,null,null,null,2,5] (0’s right child is 2 and 1’s left child is 5),

1
2
3
4
5
6
7
8
9
10
    3
   /\
  /  \
  9   8
 /\  /\
/  \/  \
4  01   7
   /\
  /  \
  5   2

return its vertical order traversal as:

1
2
3
4
5
6
7
[
  [4],
  [9,5],
  [3,0,1],
  [8,2],
  [7]
]

解法1：

一种BFS的增强用法
在每次push一个node到一个queue的同时，维护另外一个queue，记录相对应的node的信息
用一个hashmap记录每一个col对应的答案。
然后min，max记录col的范围，之后把map里的数字再按顺序读取就可以了
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();  // record each column's result
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); // used for bfs search
        Queue<Integer> column = new LinkedList<Integer>();  // used for bfs search, update each node's column number
        queue.offer(root);
        column.offer(0);
        int min = 0;
        int max = 0;
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            int col = column.poll();
            min = Math.min(col, min);
            max = Math.max(col, max);
            if (!map.containsKey(col)) {
                map.put(col, new ArrayList<Integer>());
            }
            map.get(col).add(current.val);
            if (current.left != null) {
                queue.offer(current.left);
                column.offer(col - 1);
            }
            if (current.right != null) {
                queue.offer(current.right);
                column.offer(col + 1);
            }
        }
        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }
        return res;
    }
}

发表于 | 分类于

解法1：

很简洁的一个写法，用了divide&conquer的思想
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double temp = myPow(x, n / 2);
        if (n % 2 == 0) {
            return temp * temp;
        } else {
            if (n > 0) {
                return temp * temp * x;
            } else {
                return temp * temp / x;
            }
        }
    }
}

发表于 | 分类于

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解法1: O(N^2)

就是two sum的解法
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        // N^3logN
        if (A.length == 0) {
            return 0;
        }
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = A.length;
        // O(N^2)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = A[i] + B[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = C[i] + D[j];
                if (map.containsKey(0 - sum)) {
                    count += map.get(0 - sum);
                }
            }
        }
        return count;
    }
}