发表于 | 分类于

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： O(N) HashMap

用一个hashmap存储每一个子串sum当前出现过的最早的位置（因为只要求最长的一段，所以只需要保存这个就可以了）。
然后对于每一个新球出来的sum，看是否存在sum - k存在在map中，如果存在则更新结果。要注意的是还要考虑当前的sum是否正好为k。

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 int maxSubArrayLen(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) res = i + 1;
            else if (map.containsKey(sum - k)) {
                res = Math.max(res, i - map.get(sum - k));
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return res;
    }
}

发表于 | 分类于

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

解法1： O(NlogN)

比较基本的解法就是先排序，然后就可以重新建一个数组，从前半部分去一个然后后半部分取一个交替进行。
要注意的是，因为array可能有重复的数字出现，所以不能从两边往当中，这样最后可能会碰到两个数字一样，比如[4,5,5,6]。
这是需要注意的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        Arrays.sort(nums);
        int left = (nums.length - 1) / 2;
        int right = nums.length - 1;
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = (i % 2 == 0) ? nums[left--] : nums[right--];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
        return;
    }
}

Follow up: O(N), virtual indexing

这个还没看懂。。。

发表于 | 分类于

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

解法1： HashMap + Deque

O(1)的put和get，hashmap应该是逃不了的。问题是还要维护每一个value的access的时间的先后顺序，一般的解法给出来的办法是用一个deque，最近access过的东西放在deque的最后面，而head就存放将要被删除的value。
那么自己要实现的deque的操作就是move_to_head还有一个是remove_from_head，写的时候别忘了当capacity满了之后，需要从deque和hashmap两个地方都删除掉才行。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class LRUCache {
    class Node {
        int key;
        int val;
        Node prev;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    };
    private int capacity;
    private HashMap<Integer, Node> map = new HashMap<>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        // Remove from the list
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // move to tail
        move_to_tail(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (get(key) != -1) {
            map.get(key).val = value;
            return;
        }
        if (map.size() == capacity) {
            map.remove(head.next.key);
            remove_from_head();
        }
        Node target = new Node(key, value);
        map.put(key, target);
        move_to_tail(target);
    }
    private void move_to_tail(Node node) {
        node.prev = tail.prev;
        tail.prev = node;
        node.prev.next = node;
        node.next = tail;
    }
    private void remove_from_head() {
        head.next = head.next.next;
        head.next.prev = head;
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

发表于 | 分类于

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

解法1：

和Ugly Number II的解法一样，只是这里要用一个数组来维护每一个对应的primes相乘的ugly number的位置。要注意这里用到的去重的方法是一旦当前的ugly number确定了就把可能产生的小于等于他的所有备选答案跳过（也就是对应的和prime相乘的index要++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ugly = new int[n];
        int[] idx = new int[primes.length];
        ugly[0] = 1;
        for (int i = 1; i < n; i++) {
            //find next
            ugly[i] = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++)
                ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);
            //slip duplicate
            for (int j = 0; j < primes.length; j++) {
                while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
            }
        }
        return ugly[n - 1];
    }
}

发表于 | 分类于

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:

1
2
3
4
5
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

解法1： Segment Tree

Segment Tree的直接应用。
Segment Tree 的node需要记录range的start，end以及对应的sum。
tree需要有一个node作为root。tree提供如下几个基本的method：

1
build，update，sumRange

每一个函数基本都是通过recursion实现的。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class NumArray {
    class SegmentTreeNode {
        int start;
        int end;
        int val;
        SegmentTreeNode left;
        SegmentTreeNode right;
        public SegmentTreeNode(int start, int end, int val) {
            this.start = start;
            this.end = end;
            this.val = val;
            left = null;
            right = null;
        }
    };
    class SegmentTree {
        SegmentTreeNode root;
        public SegmentTree(int[] nums) {
            root = build(nums, 0, nums.length - 1);
        }
        public SegmentTreeNode build(int[] nums, int start, int end) {
            if (start > end) return null;
            if (start == end) {
                return new SegmentTreeNode(start, end, nums[start]);
            }
            int mid = start + (end - start) / 2;
            SegmentTreeNode left = build(nums, start, mid);
            SegmentTreeNode right = build(nums, mid + 1, end);
            int val  = (left == null ? 0 : left.val ) + (right == null ? 0 : right.val);
            SegmentTreeNode root = new SegmentTreeNode(start, end, val);
            root.left = left;
            root.right = right;
            return root;
        }
        public void update(int i, int val) {
            update(root, i, val);
        }
        public void update(SegmentTreeNode current, int i, int val) {
            if (current.start == i && current.end == i) {
                current.val = val;
                return;
            }
            int mid = current.start + (current.end - current.start) / 2;
            if (i <= mid) {
                update(current.left, i, val);
            } else {
                update(current.right, i, val);
            }
            current.val = current.left.val + current.right.val;
            return;
        }
        public int sumRange(int i, int j) {
            return sumRange(root, i, j);
        }
        public int sumRange(SegmentTreeNode current, int i, int j) {
            if (current.start >= i && current.end <= j) return current.val;
            int mid = current.start + (current.end - current.start) / 2;
            if (j <= mid) {
                return sumRange(current.left, i, j);
            } else if (i > mid) {
                return sumRange(current.right, i, j);
            } else {
                return sumRange(current.left, i, mid) + sumRange(current.right, mid + 1, j);
            }
        }
    }
    SegmentTree tree;
    public NumArray(int[] nums) {
        tree = new SegmentTree(nums);
    }
    public void update(int i, int val) {
        tree.update(i, val);
    }
    public int sumRange(int i, int j) {
        return tree.sumRange(i, j);
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

发表于 | 分类于

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
“112358” is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
“199100199” is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

解法1： Recursion

思想比较简单，就是不停的尝试两个可能的number，然后看是否可以满足additive number的条件。用recursion就可以解决。
要注意的是，第一个i的循环只需要到(n - 1) / 2就可以了，因为两个数相加最少也会和较长的数长度相等。
假设第二个数字到位置j，那么第三个数字（两个数字之和的长度）就是n - j, n - j要满足的条件也就是j要满足的条件。

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 boolean isAdditiveNumber(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }
        int n = num.length();
        for (int i = 1; i <= (n - 1) / 2; i++) {
            if (num.charAt(0) == '0' && i > 1) return false;
            for (int j = i + 1; n - j >= Math.max(i, j - i); j++) {
                if (num.charAt(i) == '0' && j - i > 1) break;
                long first = Long.parseLong(num.substring(0, i));
                long second = Long.parseLong(num.substring(i, j));
                String rest = num.substring(j);
                if (helper(rest, first, second)) return true;
            }
        }
        return false;
    }
    public boolean helper(String num, long first, long second) {
        if (num.length() == 0) return true;
        Long sum = first + second;
        String s = sum.toString();
        if (!num.startsWith(s)) return false;
        return helper(num.substring(s.length()), second, sum);
    }
}

发表于 | 分类于

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解法1： Backtracking

典型的backtracking + 去重的问题。
主要的容易错的地方是怎么去重，当确定了其中一个数字的位置i之后，在变动left和right时，每当找到一个满足条件的解都要跳过之后所有和left或者right指向的相同的数字。

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i -1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    res.add(temp);
                    left++;
                    right--;
                    while (left < right && nums[left - 1] == nums[left]) left++;
                    while (left < right && nums[right + 1] == nums[right]) right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

1
2
3
4
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

1
2
3
4
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4

解法1： DFS

这题也是变换了一下思路。要找每一个room对应的最近的gate，那么反过来可以从每一个gate出发，更新每一个他可以够着的room的距离。用DFS就可以解决了。

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
class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) {
            return;
        }
        int n = rooms.length;
        int m = rooms[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (rooms[i][j] == 0) {
                    dfs(rooms, i, j, 0);
                }
            }
        }
    }
    private void dfs(int[][] rooms, int i, int j, int d) {
        if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) return;
        rooms[i][j] = d;
        dfs(rooms, i + 1, j, d + 1);
        dfs(rooms, i - 1, j , d + 1);
        dfs(rooms, i, j + 1, d + 1);
        dfs(rooms, i, j - 1, d + 1);
    }
}

发表于 | 分类于

解法1：

此题看起来就是用backtracking，但是如果直接用会TLE。
首先观察，如果一个字符串出现奇数次的字符的个数>1，那一定不能组成回文串。
所以奇数个次数的字符最多一个。并且如果有的话最中间的一定是他。
所以偶数回文串可以分成前后两段，奇数回文串可以分成前中后三段。
我们把所有的字符出现的次数/2，加上中段和reverse过的前段就可以得到一个回文串。
那么问题就转变成了求/2过后的子串的所有的permutation。具体的解法如下

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int odd = 0;
        for (char key : map.keySet()) {
            if (map.get(key) % 2 != 0) {
                odd++;
            }
        }
        if (odd > 1) return res;
        String mid = "";
        // Create the to-be-appended string
        StringBuilder sb = new StringBuilder();
        for (char key : map.keySet()) {
            for (int i = 0; i < map.get(key) / 2; i++) {
                sb.append(key);
            }
            if (map.get(key) % 2 != 0) {
                mid = Character.toString(key);
            }
        }
        // Generate permutations for the sb.toStirng()
        List<String> perm = new ArrayList<>();
        boolean[] visited = new boolean[sb.length()];
        String template = sb.toString();
        char[] temparray = template.toCharArray();
        Arrays.sort(temparray);        
        helper(new String(temparray), "", perm, visited);
        for (String temp : perm) {
            res.add(temp + mid + (new StringBuilder(temp)).reverse().toString());
        }
        return res;
    }
    private void helper(String s, String current, List<String> res, boolean[] visited) {
        if (current.length() == s.length()) {
            res.add(current);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (!visited[i]) {
                if (i != 0 && s.charAt(i) == s.charAt(i - 1) && !visited[i - 1]) continue;
                visited[i] = true;
                helper(s, current + s.charAt(i), res, visited);
                visited[i] = false;
            }
        }
    }
}

发表于 | 分类于

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:
HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301);
Follow up:
What if the number of hits per second could be very large? Does your design scale?

解法1： Deque

用一个deque来记录5分钟以内的hit。而当查询gitHit的时候，把deque前面的超出范围的node全部弹出就可以了。
如果getHit比较少的话，可以在hit的函数里放上弹出的操作。
class HitCounter {

/** Initialize your data structure here. */
Deque<Integer> deque;
public HitCounter() {
    deque = new LinkedList<>();
}

/** Record a hit.
    @param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
    deque.offerLast(timestamp);
}

/** Return the number of hits in the past 5 minutes.
    @param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
    while (!deque.isEmpty() && timestamp - deque.peekFirst() >= 300) {
        deque.pollFirst();
    }
    return deque.size();
}

}

/**

  • Your HitCounter object will be instantiated and called as such:
  • HitCounter obj = new HitCounter();
  • obj.hit(timestamp);
  • int param_2 = obj.getHits(timestamp);
    */
lang: java
1
2