发表于 | 分类于

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

解法1：

一个老题。快慢两个指针，等相遇的时候slow继续往前走一个然后继续前行，fast回到原点然后一次一步直到再次相遇就是他们的交点。
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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head.next;
        while (fast != slow) {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = slow.next;
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

发表于 | 分类于

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

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

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

解法1：有向图

这题和Course Schedule II的解法基本一样，就是判断有向图中是否有环。基本的入度出度的解法要掌握。
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
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }
        // no circle in the graph + number of visited nodes == numCourses
        int[] ins = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int[] pre : prerequisites) {
            if (!map.containsKey(pre[1])) {
                map.put(pre[1], new ArrayList<Integer>());
            }
            map.get(pre[1]).add(pre[0]);    // because of no duplicate edges in the input prerequisities
            ins[pre[0]]++;  // add the in-count for the node
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (ins[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int root = queue.poll();
            if (map.containsKey(root)) {
                List<Integer> children = map.get(root);
                for (int child : children) {
                    ins[child] -= 1;
                    if (ins[child] == 0) {
                        queue.offer(child);
                    }
                }
            }
        }
        // check if there is non-zero ins
        for (int i = 0; i < numCourses; i++) {
            if (ins[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

发表于 | 分类于

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

1
4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

1
2
3
4
Hints:
This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

解法1：有向图， 拓扑排序

有向图的问题用入度和出度解决的比较多。这题用BFS解决，push进queue的是所有入度为0的点。
如果有向图有环，则表示图中有互相依赖的课程存在。如果最后没有入度不为0的点，则说明是一个无环有向图。

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
public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res = new int[numCourses];
        if (prerequisites == null || prerequisites.length == 0) {
            for (int i = 0; i < numCourses; i++) {
                res[i] = i;                
            }
            return res;
        }
w
        // Construct the graph
        HashMap<Integer, List<Integer>> graph = new HashMap<>();
        int[] ins = new int[numCourses];
        for (int[] pre : prerequisites) {
            if (!graph.containsKey(pre[1])) {
                graph.put(pre[1], new ArrayList<Integer>());
            }
            graph.get(pre[1]).add(pre[0]);
            ins[pre[0]]++;
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; i++) {
            if (ins[i] == 0) {
                queue.offer(i);
            }
        }
        int pos = 0;
        while (!queue.isEmpty()) {
            int root = queue.poll();
            res[pos++] = root;
            if (graph.containsKey(root)) {
                List<Integer> subs = graph.get(root);
                for (int sub : subs) {
                    ins[sub]--;
                    if (ins[sub] == 0) {
                        queue.offer(sub);
                    }
                }
            }
        }
        for (int i = 0; i < numCourses; i++) {
            if (ins[i] != 0) {
                return new int[0];
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.
Example 1:
Input:

1
2
3
0 0 0
0 1 0
0 0 0

Output:

1
2
3
0 0 0
0 1 0
0 0 0

Example 2:
Input:

1
2
3
0 0 0
0 1 0
1 1 1

Output:

1
2
3
0 0 0
0 1 0
1 2 1

Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

解法1： BFS

这题和那个continental divide的题的思路有点相似的地方。要反过来想问题会变简单。
题意是让我们计算每一个1距离最近的0的距离。如果反过来想，我们从每一个0出发，探查四周，如果当前距离比之前的距离要短，那么更新那个单元格的数值，同时把那个单元格加入到探查的路径中。如果距离要更长，则这一支不需要再探查了。
C++

1

Java

1
2
<!--4-->

发表于 | 分类于

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

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

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:
Given the list [[1,1],2,[1,1]], return 8. (four 1’s at depth 1, one 2 at depth 2)

Example 2:
Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17)

解法1：

一个递归的办法就可以解决。因为weight现在是从bottom到top，所以要先计算出maxdepth。这一步也需要用递归完成。
然后把depth作为一个参数pass到每一层就可以了。
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 int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null || nestedList.size() == 0) {
            return 0;
        }
        // get the max sum;
        int maxDepth = getMaxDepth(nestedList);
        return helper(nestedList, maxDepth);
    }
    private int getMaxDepth(List<NestedInteger> nestedList) {
        int max = 1;    
        for (int i = 0; i < nestedList.size(); i++) {
            NestedInteger item = nestedList.get(i);
            if (item.isInteger()) {
                max = Math.max(max, 1);
            } else {
                max = Math.max(max, getMaxDepth(item.getList()) + 1);
            }
        }    
        return max;        
    }
    private int helper(List<NestedInteger> nestedList, int depth) {
        int sum = 0;
        for (int i = 0; i < nestedList.size(); i++) {
            NestedInteger item = nestedList.get(i);
            if (item.isInteger()) {
                sum += depth * item.getInteger();
            } else {
                sum += helper(item.getList(), depth - 1);
            }
        }
        return sum;
    }
}

发表于 | 分类于

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:
The order of returned grid coordinates does not matter.
Both m and n are less than 150.
Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given the following 5x5 matrix:
  Pacific ~   ~   ~   ~   ~
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

解法1： DFS 两次

也是反向思维。似乎要分别判断能flow到atlantic和pacific的cell。边界上的点是确定的，所以可以从这几个点开始。逆向思维–>让水从边界开始往内陆”流”，只要海拔越来越高就可以。
C++

1

Java

1
2
<!--1-->

发表于 | 分类于

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

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

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

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

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

解法1：Union-Find

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
public class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] root = new int[n];
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        for (int[] edge : edges) {
            int root1 = find(root, edge[0]);
            int root2 = find(root, edge[1]);
            if (root1 != root2) {
                root[root1] = root2;
                n--;
            }
        }
        return n;
    }
    private int find(int[] root, int id) {
        while (root[id] != id) {
            id = root[id];
        }
        return id;
    }
}

解法2：DFS

DFS统计visited的node的个数的一种办法是，维护visited的set，每次执行一次dfs，然后到下一个节点如果没有visit过就++count。最后count就是总的visited的分隔的group的个数。
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
public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (edges == null || edges.length == 0 || edges[0].length == 0) {
            return n;
        }
        int count = 0;
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();    // store the edges
        for (int[] edge : edges) {
            if (!map.containsKey(edge[0])) {
                map.put(edge[0], new ArrayList<Integer>());
            }
            map.get(edge[0]).add(edge[1]);
            if (!map.containsKey(edge[1])) {
                map.put(edge[1], new ArrayList<Integer>());
            }
            map.get(edge[1]).add(edge[0]);
        }
        Set<Integer> visited = new HashSet<Integer>();  // visited nodes
        for (int i = 0; i < n; i++) {
            if (!visited.contains(i)) {
                count++;
                dfs(visited, i, map);             
            }
        }
        return count;
    }
    private void dfs(Set<Integer> visited, int current, Map<Integer, List<Integer>> map) {
        visited.add(current);   // add to visited node list
        if (!map.containsKey(current)) {
            return;
        }
        List<Integer> list = map.get(current);
        for (int node : list) {
            if (!visited.contains(node)) {
                dfs(visited, node, map);            
            }
        }
        return;
    }
}

发表于 | 分类于

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

The length of the given string is ≤ 10000.
Each number will contain only one digit.
The conditional expressions group right-to-left (as usual in most languages).
The condition will always be either T or F. That is, the condition will never be a digit.
The result of the expression will always evaluate to either a digit 0-9, T or F.
Example 1:

1
2
3
4
5
Input: "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

1
2
3
4
5
6
7
8
9
Input: "F?1:T?4:5"
Output: "4"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"

Example 3:

1
2
3
4
5
6
7
8
9
Input: "T?T?F:5:3"
Output: "F"
Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:
             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

解法1： Stack

打破传统思维，从后往前扫描放入stack
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
public class Solution {
    public String parseTernary(String expression) {
        if (expression == null || expression.length() == 0) {
            return "";
        }
        Stack<Character> stack = new Stack<Character>();
        for (int i = expression.length() - 1; i >= 0; i--) {
            char current = expression.charAt(i);
            if (!stack.isEmpty() && stack.peek() == '?') {
                stack.pop();    // get ride of ?
                char left = stack.pop();
                stack.pop();
                char right = stack.pop();
                if (current == 'T') {
                    stack.push(left);
                } else {
                    stack.push(right);
                }
            } else {
                stack.push(current);
            }
        }
        return String.valueOf(stack.peek());
    }
}

发表于 | 分类于

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.

解法1：DFS

首先，如果能摆成正方形，正方形的边长是确定的。也就是所有的数加起来/4。然后就是运行一个DFS。核心思想是，用一个数组代表每一个边长，然后尝试不同的组合，终结条件是每条边长都是target。
这里有一个优化是需要先对所有火柴递减排列：原因是

1
Sorting the input array DESC will make the DFS process run much faster. Reason behind this is we always try to put the next matchstick in the first subset. If there is no solution, trying a longer matchstick first will get to negative conclusion earlier. Following is the updated code. Runtime is improved from more than 1000ms to around 40ms. A big improvement.

也就是说，如果一个组合不能成功拼成正方形的话，先用长的可以更快的得到false的结论，而不用多循环好多次来得到这个结论。这样运行速度就加快了。
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
59
60
public class Solution {
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 4 != 0) {
            return false;
        }
        int target = sum / 4;   // this is the length of square
        Arrays.sort(nums);  // sort the nums descending
        reverse(nums);
        int[] sides = new int[4];
        return dfs(sides, nums, 0, target);
    }
    private void reverse(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
        return;
    }
    private boolean dfs(int[] sides, int[] nums, int pos, int target) {
        if (pos == nums.length) {
            if (sides[0] == target && sides[1] == target && sides[2] == target) {
                return true;
            }
            return false;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + nums[pos] > target) {
                continue;
            }
            sides[i] += nums[pos];
            boolean temp = dfs(sides, nums, pos + 1, target);
            if (temp) {
                return true;
            }
            sides[i] -= nums[pos];
        }
        return false;
    }
}

发表于 | 分类于

Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.

Example 1:
Given points = [[1,1],[-1,1]], return true.

Example 2:
Given points = [[1,1],[-1,-1]], return false.

Follow up:
Could you do better than O(n2)?

解法1：O(N) Time + O(N) Space

这题的题意是对于N个给定的点，找一下是否存在一条平行与y轴的线，使得所有点都对称与此条线。
那么怎么确定这条平行的线是关键。
如果点都是对称存在的，那么最左面的点和最右面的点当中的线就是平行于y轴的对称线。所有其他的点都必须以此为基准。
用一个set存储每一个点，并且找出最左最右两个点。找出以后，对于每一个点，检查他的对称点是否在set中。
放入set的时候用到了Arrays.hashCode(int[])的function。
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
public class Solution {
    public boolean isReflected(int[][] points) {
        if (points == null || points.length == 0) {
            return true;
        }
        HashSet<Integer> set = new HashSet<>();
        int xmin = Integer.MAX_VALUE, xmax = Integer.MIN_VALUE;
        for (int[] point : points) {
            xmin = Math.min(xmin, point[0]);
            xmax = Math.max(xmax, point[0]);
            set.add(Arrays.hashCode(point));
        }
        int sum = xmin + xmax;
        for (int[] point : points) {
            if (!set.contains(Arrays.hashCode(new int[] { sum - point[0], point[1]}))) {
                return false;
            }
        }
        return true;
    }
}