发表于 | 分类于

Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example:

1
2
3
4
5
6
7
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,
Result: [3, 9, 15, 33]
nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5
Result: [-23, -5, 1, 7]

解法1： Two pointers + Math

如果a是正数，那么在边缘的x所对应的数字是最大的，而最小值在中间。
如果a是负数，那么在边缘的x所对应的数字是最小的，最大值在中间。
可以改变要写入的位置来精简代码。

lang: 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
class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] res = new int[n];
        int i = 0, j = n - 1;
        int index = a >= 0 ? n - 1 : 0;
        while (i <= j) {
            int left = calc(nums[i], a, b, c);
            int right = calc(nums[j], a, b, c);
            if (a >= 0) {
                if (left >= right) {
                    res[index--] = left;
                    i++;
                } else {
                    res[index--] = right;
                    j--;
                }
            } else {
                if (left >= right) {
                    res[index++] = right;
                    j--;
                } else {
                    res[index++] = left;
                    i++;
                }
            }
        }
        return res;        
    }
    private int calc(int num, int a, int b, int c) {
        return a * num * num + b * num + c;
    }
}

发表于 | 分类于

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

解法1： Bit Manipulation

这题挺好的。思维很巧妙。
首先还是要用XOR， 如果我们先把所有数字XOR一遍，那么结果就是A ^ B. 其中A，B就是我们要找的两个数。而这个结果一定不是0.那么如果我们随便找一个setbit， 就可以把原来的数组分成这个bit被set和不被set的两组。要求的数一定分别在这两组里面。对每一组分别求XOR就可以得到要求的结果。
其中求一个number的一个bit可以用一个小技巧

1
number & (-number)

可以得到rightmost setbit

lang: 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
class Solution {
    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int[] res = new int[2];
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        int setBit = xor & (-xor);
        for (int num : nums) {
            if ( (num & setBit) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;        
    }
}

发表于 | 分类于

Numbers can be regarded as product of its factors. For example,

1
2
8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Examples:
input: 1
output:

1
[]

input: 37
output:

1
[]

input: 12
output:

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

input: 32
output:

1
2
3
4
5
6
7
8
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

解法1： Backtracking

lang: 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
class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        if (n <= 2) return res;
        helper(n, 2, current, res);
        return res;
    }
    private void helper(int n, int start, List<Integer> current, List<List<Integer>> res) {
        if (n <= 0) {
            return;
        }
        if (n == 1) {
            if (current.size() > 1) {
                res.add(new ArrayList<Integer>(current));
                return;
            }
        }
        for (int i = start; i <= n; i++) {
            if (n % i == 0) {
                current.add(i);
                helper(n / i, i, current, res);
                current.remove(current.size() - 1);
            }
        }
        return;
    }
}

发表于 | 分类于

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2

解法1： Sweep Line / 扫描线

扫描线的基础题。基本的思路是把所有的线段的两个断点都归类并且排序，然后碰到起点就+1，碰到终点就-1，按照时间的顺序遍历，相当于有一根线在从左面扫到右面。
实际在写code的时候可以有不同的写法，第一种是用了一种比较少用的数据结构，TreeMap。这个hashmap存储的是对于每一个时间点的计数，不同的是，对于起点计数+1，对于终点计数-1， 表现的就是如果一个会议结束了当前的room就释放出来不需要了，所以自然需要的room的个数-1。然后需要按照时间顺序遍历每一个时间点，把所有的room的变化加和，在加和的过程中保留下遇见过的最大值）。TreeMap的key是按照natural order排序的，所以很适合这个问题。

lang: 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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        //
        Map<Integer, Integer> map = new TreeMap<>();    // Treat start and end as the natural time point
        // Takes O(logN) for each operation
        for (Interval it : intervals) {
            map.put(it.start, map.getOrDefault(it.start, 0) + 1);
            map.put(it.end, map.getOrDefault(it.end, 0) - 1);
        }
        int rooms = 0;
        int res = 0;
        for (int timePoint : map.keySet()) {
            // timePoint is sorted in ascending order
            rooms += map.get(timePoint);
            res = Math.max(res, rooms);
        }
        return res;
    }
}

解法2： Sorting Array

同样的思路，不同的写法。也可以维护两个数组，start, end. 把对应的时间点放进去进行排序。然后用两个指针指向两个数组，当start < end的时候需要的room+1， 反之则room-1. 然后在更新的过程中统计出现过的最大的room的个数。

lang: 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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        int n = intervals.length;
        int[] start = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i].start;
            end[i] = intervals[i].end;
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int endptr = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (start[i] < end[endptr]) {
                res++;
            } else {
                endptr++;
            }
        }
        return res;
    }
}

发表于 | 分类于

Implement an iterator to flatten a 2d vector.

For 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].

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

解法1： Non-Iterator, List + Pointer

用一个list来存储原来的数据。同时维护两个指针，一个指向当前的子list，另一个指向该list中的位置。在hasNext函数中，判断是否还有数据查看elemenPointer是不是在list尾巴，同时检查是否还有下一个list。

lang: 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
public class Vector2D implements Iterator<Integer> {
    List<List<Integer>> data;
    int listPos;
    int elemPos;
    public Vector2D(List<List<Integer>> vec2d) {
        this.data = vec2d;
        listPos = 0;
        elemPos = 0;
    }
    @Override
    public Integer next() {
        return data.get(listPos).get(elemPos++);
    }
    @Override
    public boolean hasNext() {
        while (listPos < data.size()) {
            if (elemPos < data.get(listPos).size()) {
                return true;
            } else {
                listPos++;
                elemPos = 0;
            }
        }
        return false;
    }
}
/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

解法2： Iterator

用一个queue来存储每一个list对应的iterator。同时维护一个iterator指向当前的iterator。hasNext就需要判断当前是否还有iterator同时这个iterator是否有下一个元素。

lang: 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
public class Vector2D implements Iterator<Integer> {
    Queue<Iterator<Integer>> queue;
    Iterator<Integer> current = null;
    public Vector2D(List<List<Integer>> vec2d) {
        queue = new LinkedList<>();
        for (List<Integer> list : vec2d) {
            queue.offer(list.iterator());
        }
        current = queue.poll();
    }
    @Override
    public Integer next() {
        return current.next();
    }
    @Override
    public boolean hasNext() {
        while (current == null || !current.hasNext()) {
            if (!queue.isEmpty()) {
                current = queue.poll();
            } else {
                return false;
            }
        }
        return true;
    }
}
/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

发表于 | 分类于

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

1
"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: [“abc”, “bcd”, “acef”, “xyz”, “az”, “ba”, “a”, “z”],
A solution is:

1
2
3
4
5
6
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

解法1： HashMap

基本的思路是要构造一个hash function，使得属于一个sequence的字符串可以group到一起。一个思路是把每一个字符转换成对于与第一个字符的位置。
这里要处理的是负数的情况，比如ba,az，这里用到的trick是用(diff + 26) % 26 来转换成正整数。
同时要注意的是需要分隔开不同的数字，因为对于012不能区分是0-12还是0-1-2.

lang: 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
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<>();
        if (strings == null || strings.length == 0) {
            return res;
        }
        // Design a hash function
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strings) {
            // construct the hash key
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
                sb.append(Integer.toString((str.charAt(i) - str.charAt(0) + 26) % 26));
                sb.append(".");
            }
            String key = sb.toString();
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<String>());
            }
            map.get(key).add(str);
        }
        for (String key : map.keySet()) {
            res.add(map.get(key));
        }
        return res;
    }
}

发表于 | 分类于

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return [“11”,”69”,”88”,”96”].

解法1： Recursion

承接I的思路，当数字长度大于1的时候，都需要配对存在。
要注意的是00配对只可能存在内层中，所以在递归的时候需要用一个变量记录原来n的长度。这样当不是最外层的时候就可以把0加上了。

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    private List<String> helper(int n, int m) {
        if (n == 0) return new ArrayList<String>(Arrays.asList(""));
        if (n == 1) return new ArrayList<String>(Arrays.asList("0","1","8"));
        List<String> next = helper(n - 2, m);
        List<String> res = new ArrayList<>();
        for (String str : next) {
            if (n != m) res.add("0" + str + "0");
            res.add("1" + str + "1");
            res.add("6" + str + "9");
            res.add("8" + str + "8");
            res.add("9" + str + "6");
        }
        return res;
    }
}

发表于 | 分类于

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

1
2
3
4
5
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]

Example 2

1
2
3
4
5
6
7
8
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

解法1：

用Divide & Conquer的思想，按照每一个运算符号分成左右两边。每边计算一下结果然后按照运算符号结合起来。当只有数字的时候所生成的res一定为空，这个时候就把数字加入res即可。

lang: 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
class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*') {
                String left = input.substring(0, i);
                String right = input.substring(i + 1);
                List<Integer> leftRes = diffWaysToCompute(left);
                List<Integer> rightRes = diffWaysToCompute(right);
                for (int l : leftRes) {
                    for (int r : rightRes) {
                        switch (input.charAt(i)) {
                            case '+' :
                                res.add(l + r);
                                break;
                            case '-':
                                res.add(l - r);
                                break;
                            case '*':
                                res.add( l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (res.size() == 0) {
            res.add(Integer.parseInt(input));
        }
        return res;
    }
}

发表于 | 分类于

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

rectangle area
Assume that the total area is never beyond the maximum possible value of int.

解法1：

lang: 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
class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int left = (C - A) * (D - B);
        int right = (G - E) * (H - F);
        // on the left or right side
        if (E >= C || G <= A) {
            return left + right;
        }
        // above or below
        if (F >= D || H <= B ) {
            return left + right;
        }
        // overlap
        int ldx = Math.max(A, E);
        int ldy = Math.max(B, F);
        int rux = Math.min(C, G);
        int ruy = Math.min(D, H);
        int cross = (rux - ldx) * (ruy - ldy);
        return left + right - cross;        
    }
}

发表于 | 分类于

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

解法1： TreeSet, O(nlog(k, n))

这里用到一个比较特殊的数据结构treeset。
实际上这是一个self-balancing binary search tree, 他的基本操作都是O(logN)的。而且他还有两个额外的功能很有用
set.ceiling(T)和set.floor(T)
ceiling返回的是大于等于T的最小的元素，而floor返回的是小于等于T的最大元素。
那么我们维护一个大小为k的set，这样就满足了一个条件。
那第二个条件满足的条件就是对于每一个num，找出他的ceiling和floor，看是否在范围内即可。

lang: 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
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            int current = nums[i];
            Integer ceiling = set.ceiling(current);
            Integer floor = set.floor(current);
            if (ceiling != null && ceiling <= current + t) {
                return true;
            }
            if (floor != null && current <= floor + t) {
                return true;
            }
            set.add(current);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

解法2： O(N) using Bucket

lang: 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
class Solution {
    private long getBucketId(long num, long w) {
        return num < 0 ? (num + 1) / w - 1 : num / w;
    }
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0 ) return false;
        if (nums == null || nums.length == 0) {
            return false;
        }    
        long w = (long)t + 1;
        Map<Long, Long> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long id = getBucketId((long)nums[i], w);
            if (map.containsKey(id)) {
                return true;
            }
            if (map.containsKey(id - 1) && Math.abs(map.get(id - 1) - nums[i]) < w) {
                return true;
            }
            if (map.containsKey(id + 1) && Math.abs(map.get(id + 1) - nums[i]) < w) {
                return true;
            }
            map.put(id, (long)nums[i]);
            if (i >= k) {
                map.remove(getBucketId(nums[i - k], w));
            }
        }
        return false;
    }
}