1302. Deepest Leaves Sum
Posted Updated LeetCode / Mediuma minute read (About 153 words)

1302. Deepest Leaves Sum

Question

Given the root of a binary tree, return the sum of values of its deepest leaves.

Solution

BFS搜索，层序遍历，每次计算每个层级的总和。
最后返回最后一个层级总和。

Code

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> q = new LinkedList<>();
        int res = 0;
        
        q.offer(root);
        
        int level = q.size();
        
        while(!q.isEmpty()){
            int sum = 0;
            for(int i = 0; i < level; i++){
                TreeNode curr = q.poll();
                sum += curr.val;
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
            }
            res = sum;
            level = q.size();
        }
        return res;
    }
}
743. Network Delay Time
Posted Updated LeetCode / Medium / 复习5 minutes read (About 773 words)

743. Network Delay Time

Question

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>), where u<sub>i</sub> is the source node, v<sub>i</sub> is the target node, and w<sub>i</sub> is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Solution

Dijkstra算法

此题可以转化为求起始节点到最远距离的节点的距离。单源最短路径问题，可以采用Dijkstra算法。

采用一个visited[]数组记录初始节点的访问状况。
同时dist[]数组记录到达这一节点的最小距离，初始化为无限大。

进行BFS搜索，每次优先访问当前节点的子节点的最近子节点，并更新子节点与初始节点距离。
最后遍历dist[]数组，如果有元素仍为无限大，则BFS搜索未遍历到，返回-1。
否则返回数组内最大的距离即可。

建立映射

首先通过哈希表，将起始节点与有向边建立起映射关系。列表中储存子节点和对应边上的权值。
注意由于index是-1的，因此在组成列表时需要将当前数字减一。

优先级队列

采用优先级队列组成小根堆，每次将当前的最小距离作为权值加入队列。
初始化队列时需要将起始节点（k-1）放入，此时的总距离为0。

当当前的子节点的cost加上起始节点的距离小于子节点的最小距离时，更新子节点最小距离。
同时将子节点当前最小距离作为比较对象传入优先级队列。

Code

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
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        HashMap<Integer, List<int[]>> edges = new HashMap<>(); 
        
        for(int[] time : times){    //建立有向边
            int source = time[0] - 1, kid = time[1] - 1, cost = time[2];    //注意index需要-1
            List<int[]> list = edges.getOrDefault(source, new ArrayList<>());
            list.add(new int[]{kid, cost});    //建立起点——终点映射
            edges.put(source, list);
        }
        
        int[] visited = new int[n];
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);    //优先级队列，最小堆每次访问距离最近的节点
        
        int start = k-1;
        dist[start] = 0;
        pq.offer(new int[]{start, 0});  //start为初始节点，后面的距离为了实现优先级队列
        
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            int source = curr[0];

            if(visited[source] == 1) continue;
            visited[source] = 1;
            
            List<int[]> children = edges.getOrDefault(source, new ArrayList<>());   //获取当前起点的所有边
            for(int[] child : children){
                int kid = child[0], cost = child[1];
                
                if(cost + dist[source] < dist[kid]){    //如果新的距离小于之前的最小距离，则更新距离并将新的起点加入优先级队列
                    dist[kid] = cost + dist[source];
                    pq.offer(new int[]{kid, dist[kid]});    //更新的距离是从出发节点到当前节点的距离，每次优先访问最近的节点
                }
            }
        }
        
        int res = 0;
        
        for(int d : dist){  //最后遍历，距离的最大值就是结果
            res = Math.max(res, d);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
1641. Count Sorted Vowel Strings
Posted Updated LeetCode / Medium / 复习2 minutes read (About 262 words)

1641. Count Sorted Vowel Strings

Question

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Solution

动态规划，创建数组dp[]记录以每个字符开头能组成的字符串数量。
由于当长度为1时，每个字符串都能组成一次，因此初始化所有值为1。

n增长时，每一个层级都等于该字符后的所有值相加。
最后得出的结果在下一个层级的第一位。（因为第一位是所有上一个层级加和）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int countVowelStrings(int n) {
        int[] dp = new int[]{1,1,1,1,1};
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 5; j++){
                for(int k = j+1; k < 5; k++){
                    dp[j] += dp[k];
                }
            }
        }
        return dp[0];
    }
}

Solution

递归，使用成员变量计算有效递归次数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int count;
    public int countVowelStrings(int n) {
        count = 0;
        count(n, 0);
        return count;
    }
    
    private void count(int n, int start){
        if(n == 0){
            count++;
            return;
        }
        for(int i = start; i < 5; i++){
            count(n-1, i);
        }
    }
}
216. Combination Sum III
Posted Updated LeetCode / Medium2 minutes read (About 260 words)

216. Combination Sum III

Question

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

  • Only numbers 1 through 9 are used.
  • Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Solution

回溯，创建一个成员变量visited[]记录访问情况。

剪枝优化，遍历所有可选择的数字，将其加和，如果加和大于target则返回。
剪枝优化，每层级遍历的范围大于传入列表中的最后一个元素。
回溯，向下递归。

如果k等于0并且sum等于target则添加arr到列表ret中。

Code

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 {
    int[] visited;
    List<List<Integer>> ret;

    public List<List<Integer>> combinationSum3(int k, int n) {
        visited = new int[9];
        ret = new ArrayList<>();
        backTracking(k, n, new ArrayList<>(), 0);
        return ret;
    }
    
    private void backTracking(int k, int target, List<Integer> arr, int sum){
        if(k == 0 && sum == target) ret.add(new ArrayList<>(arr));
        int start = 1;
        if(arr.size() != 0) start =  arr.get(arr.size()-1)+1;
        for(int i = start ; i <= 9; i++){
            if(visited[i-1] == 1) continue;
            sum+=i;
            if(sum > target) return;
            visited[i-1] = 1;
            arr.add(i);
            
            backTracking(k-1, target, arr, sum);
            sum-=i;
            arr.remove(new Integer(i));
            visited[i-1] = 0;
        }
    }
}
341. Flatten Nested List Iterator
Posted Updated LeetCode / Medium3 minutes read (About 391 words)

341. Flatten Nested List Iterator

Question

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

  • NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
  • int next() Returns the next integer in the nested list.
  • boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Solution

将所有的NestedInteger展开后加入全局变量队列。

辅助方法buildQueue():
递归，如果当前元素是列表，则向下递归列表内的所有元素。
如果当前元素是单个整数，则将其加入队列。

next():
返回并挤出队列中的下一个元素，返回其整数。

hasNext():
返回队列是否为空。

Code

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
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Queue<NestedInteger> q;
    public NestedIterator(List<NestedInteger> nestedList) {
        q = new LinkedList<>();
        for(NestedInteger item : nestedList){
            buildQueue(item);
        }
    }
    
    private void buildQueue(NestedInteger ni){
        if(!ni.isInteger()){
            for(NestedInteger item : ni.getList()){
                buildQueue(item);
            }
        }
        else{
            q.offer(ni);
        }
    }

    @Override
    public Integer next() {
        return q.poll().getInteger();
    }

    @Override
    public boolean hasNext() {
        return !q.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
1209. Remove All Adjacent Duplicates in String II
Posted Updated LeetCode / Medium2 minutes read (About 365 words)

1209. Remove All Adjacent Duplicates in String II

Question

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Solution

用一个栈保存当前的字符，同时建立一个cnt[]数组记录当前字符连续出现的次数。

遍历字符串。

如果当前的字符与栈顶的字符相同时，获取数组中记录的当前连续次数lastCount并加一。
如果lastCount等于k，则匹配到了足够的字符，去掉栈顶的k - 1个元素。
否则将字符串加入栈顶，记录当前位置的出现次数lastCount。

如果当前字符与栈顶字符不同，则将字符直接加入栈顶，记录当前位置的cnt[dq.size()]为1。

最后将栈内元素倒序组成字符串。由于需要这一步操作，因此之前的栈采用双端队列实现。

Code

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 String removeDuplicates(String s, int k) {
        Deque<Character> dq = new LinkedList<Character>();
        int[] cnt = new int[s.length()+1];

        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(i > 0 && !dq.isEmpty() && dq.peek() == c){
                int lastCount = cnt[dq.size()];
                lastCount++;
                if(lastCount == k){
                    while(lastCount != 1){
                        dq.removeFirst();
                        lastCount--;
                    }
                }
                else{
                    dq.offerFirst(c);
                    cnt[dq.size()] = lastCount;
                }
            }
            else{
                dq.offerFirst(c);
                cnt[dq.size()] = 1;
            }
        }
        
        StringBuffer sb = new StringBuffer();
        while(!dq.isEmpty()){
            sb.append(dq.removeLast());
        }
        return sb.toString();
    }
}
Posted Updated LeetCode / Easya minute read (About 148 words)

905. Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

双指针，右侧指针之后存放奇数项。
当左侧指针的元素为奇数时，交换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
class Solution {
    int[] arr;
    public int[] sortArrayByParity(int[] nums) {
        arr = nums;
        int left = 0;
        int right = nums.length-1;
        
        while(left < right){
            if(nums[left] % 2 == 1){
                swap(left, right);
                right--;
            }
            else{
                left++;
            }
        }
        return arr;
    }
    
    private void swap(int left, int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
Posted Updated LeetCode / Medium3 minutes read (About 385 words)

785. Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

  • There are no self-edges (graph[u] does not contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
    A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

原题等于问：每个节点与其相连接的节点是否可以颜色不同？
通过BFS搜索，将每一层通过开关flag分组。
创建一个visited数组，记录分组和遍历情况。
当节点被放入错误的分组时，返回false。

注意因为图里的各个节点可能不连接，因此需要遍历对所有节点进行BFS搜索，通过visited的情况进行剪枝。

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 boolean isBipartite(int[][] graph) {
        Queue<int[]> q = new LinkedList<>();
        int[] visited = new int[graph.length];
        
        for(int i = 0; i < graph.length; i++){
            boolean flag = false;
            if(graph[i].length == 0 || visited[i] != 0) continue;
            q.add(graph[i]);
            visited[i] = 1;
            int size = 1;
        
            while(!q.isEmpty()){
                for(int j = 0; j < size; j++){
                    int[] node = q.poll();
                    for(int next : node){
                        if(visited[next] == 0){
                            q.add(graph[next]);
                        }
                        if(flag){
                            if(visited[next] == 2) return false;
                            visited[next] = 1;
                        }
                        else{
                            if(visited[next] == 1) return false;
                            visited[next] = 2;
                        }
                    }
                }
                flag = !flag;
                size = q.size();
            }
        }
        return true;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 409 words)

1631. Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

A*算法，启发式搜索。BFS搜索结合Priority Queue。
采用一个数组储存当前访问点的位置，以及其effort。
采用优先队列，优先搜索effort最小的方向。
每次循环倾倒出队列中所有的元素。
计算上一个节点和当前节点的差值作为nextEffort，并和上一个节点的effort作比较，较大的作为当前节点的effort，
将effort作为权重，优先搜索一个层级内effort较小的路径。
将所有操作加入队列，并排除越界的位置。
当当前节点为最后一个节点时，返回其effort。

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 {
    int min;
    public int minimumEffortPath(int[][] heights) {
        int[][] operations = {{1,0},{-1,0},{0,1},{0,-1}};
        int m = heights.length, n = heights[0].length;
        
        Queue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[] point = {0, 0, 0};
        int size = 1;
        int[][] visited = new int[m][n];
        
        q.add(point);
        while(!q.isEmpty()){
            
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1], currEffort = curr[2];
                if(visited[i][j] == 1) continue;
                visited[i][j] = 1;
                if(i == m-1 && j == n-1) return currEffort;
                for(int[] operation : operations){
                    int nextX = i + operation[0];
                    int nextY = j + operation[1];
                    if(nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) continue;
                    int nextEffort = Math.max(currEffort, Math.abs(heights[i][j] - heights[nextX][nextY]));
                    int[] next = {nextX, nextY, nextEffort};
                    
                    q.add(next);
                }
            }
            size = q.size();
        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 353 words)

1202. Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

并查集，注意要使用路径压缩否则会超时。
先将所有配对联通。然后创建一个数组group记录每个字符串位置的分组情况。
根据分组，借助优先队列保存字符串。
通过哈希表创建group和PriorityQueue的映射。
按当前位置的分组情况和优先队列的顺序来添加字符串。
最后返回字符串。

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
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        StringBuffer sb = new StringBuffer();
        UnionFind uf = new UnionFind(s.length());
        
        for(List<Integer> pair : pairs){
            uf.union(pair.get(0), pair.get(1));    
        }
        
        int[] group = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            group[i] = uf.find(i);
        }
        
        HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
        
        for(int i = 0; i < s.length(); i++){
            PriorityQueue<Character> bin = map.getOrDefault(group[i], new PriorityQueue<Character>());
            bin.add(s.charAt(i));
            map.put(group[i], bin);
        }
        for(int i = 0; i < s.length(); i++){
            sb.append(map.get(group[i]).poll());
        }
        return sb.toString();
    }
    
    class UnionFind {
        int[] parent;
        int[] count;
        public UnionFind(int n){
            parent = new int[n];
            count = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                count[i] = 1;
            }
        } 
        
        private int find(int id){
            if(parent[id] == id) return id;
            parent[id] = find(parent[id]);
            return parent[id];
        }
        
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(count[p1] > count[p2]) parent[p2] = p1;
            else parent[p1] = p2;
            return true;
        }
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 380 words)

1584. Min Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

并查集，最小生成树(Minimum spanning tree)，Kruskal算法。
Edge辅助类，保存并计算两点的id和其曼哈顿距离。
将edges根据其距离排序。

遍历所有的edge，如果edge的两点没有合并，则合并两点，并取这条边作为结果。
加和所有的结果，答案就是最小值。

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 int minCostConnectPoints(int[][] points) {
        List<Edge> edges = new ArrayList<Edge>();
        int min = 0;
        for(int i = 0; i < points.length; i++){
            for(int j = i+1; j < points.length; j++){
                 edges.add(new Edge(points, i, j));
            }
        }
        
        Collections.sort(edges, (a, b) -> a.length - b.length);
        UnionFind uf = new UnionFind(points.length);
        
        for(Edge e : edges){
            if(uf.union(e.id1, e.id2)){
                min += e.length;
            }
        }
        return min;
    }

    class UnionFind{
        private int[] parents;
        private int[] size;
    
        public UnionFind(int n){
            size = new int[n];
            parents = new int[n];
            for(int i = 0; i < n; i++){
                parents[i] = i;
                size[i] = 1;
            }
        }
    
        public int find(int id){
            if(parents[id] == id) return id;
            return find(parents[id]);
        }
    
        public boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            
            if(p1 == p2) return false;
        
            if(size[p1] < size[p2]){
                parents[p1] = p2;
                size[p2] += size[p1];
            }
            else{
                parents[p2] = p1;
                size[p1] += size[p2];
            }
            return true;
        }
    }

    class Edge{
        int id1;
        int id2;
        int length;
        public Edge(int[][] points, int _id1, int _id2){
            id1 = _id1;
            id2 = _id2;
            length = Math.abs(points[id1][0] - points[id2][0]) + Math.abs(points[id1][1] - points[id2][1]);
        }
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 436 words)

1396. Design Underground System

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Implement the UndergroundSystem class:

  • void checkIn(int id, string stationName, int t)
    • A customer with a card ID equal to id, checks in at the station stationName at time t.
    • A customer can only be checked into one place at a time.
  • void checkOut(int id, string stationName, int t)
    • A customer with a card ID equal to id, checks out from the station stationName at time t.
  • double getAverageTime(string startStation, string endStation)
    • Returns the average time it takes to travel from startStation to endStation.
    • The average time is computed from all the previous traveling times from startStation to endStation that happened directly, meaning a check in at startStation followed by a check out from endStation.
    • The time it takes to travel from startStation to endStation may be different from the time it takes to travel from endStation to startStation.
    • There will be at least one customer that has traveled from startStation to endStation before getAverageTime is called.
      You may assume all calls to the checkIn and checkOut methods are consistent. If a customer checks in at time t1 then checks out at time t2, then t1 < t2. All events happen in chronological order.

两个哈希表，第一个暂存id。第二个用来储存“站点——站点”和路线中的总用时，路线中的总人数。
最后返回总用时除以总人数。
（一开始采用的算法没有考虑id重复进站，和id出站进站不同的情况。）

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 UndergroundSystem {
    HashMap<Integer, Pair<String, Integer>> inMap;
    HashMap<String, int[]> outMap;
    public UndergroundSystem() {
        inMap = new HashMap<Integer, Pair<String, Integer>>();
        outMap = new HashMap<String, int[]>();
    }
    
    public void checkIn(int id, String stationName, int t) {
        Pair<String, Integer> data = new Pair(stationName, t);
        inMap.put(id, data);
    }
    
    public void checkOut(int id, String stationName, int t) {
        Pair<String, Integer> data = inMap.get(id);
        String route = data.getKey() + "-" + stationName;
  
        int[] routeData = outMap.getOrDefault(route, new int[2]);
        routeData[0] += t - data.getValue();
        routeData[1]++;
    
        outMap.put(route, routeData);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        String route = startStation + "-" + endStation;
        return outMap.get(route)[0] / (double) outMap.get(route)[1];
    }
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem obj = new UndergroundSystem();
 * obj.checkIn(id,stationName,t);
 * obj.checkOut(id,stationName,t);
 * double param_3 = obj.getAverageTime(startStation,endStation);
 */
Posted Updated LeetCode / Medium2 minutes read (About 252 words)

535. Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.

There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Implement the Solution class:

  • Solution() Initializes the object of the system.
  • String encode(String longUrl) Returns a tiny URL for the given longUrl.
  • String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.

计算传入连接的哈希值。将其作为key放入map中。
解码时将url转换为key，取出map中的value。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Codec {
    HashMap<Integer, String> map = new HashMap<>();
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        int key = longUrl.hashCode();
        map.put(key, longUrl);
        return Integer.toString(key);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return map.get(Integer.parseInt(shortUrl));
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));
Posted Updated LeetCode / Easya minute read (About 181 words)

705. Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

  • void add(key) Inserts the value key into the HashSet.
  • bool contains(key) Returns whether the value key exists in the HashSet or not.
  • void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

计算哈希值，使用数组实现Hash Set。

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
class MyHashSet {
    int PRIME = 1009;
    List<Integer>[] data;
    
    public MyHashSet() {
        data = new List[PRIME];
        for(int i = 0; i < PRIME; i++){
            data[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        if(!contains(key)){
            int h = getHash(key);
            data[h].add(key);
        }
    }
    
    public void remove(int key) {
        int h = getHash(key);
        data[h].remove(new Integer(key));
    }
    
    public boolean contains(int key) {
        int h = getHash(key);
        for( int num : data[h] ){
            if( num == key ){
                return true;
            }
        }
        return false;
    }
    
    private int getHash(int o){
        return o % PRIME;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */
Posted Updated LeetCode / Medium / 复习4 minutes read (About 534 words)

173. Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.
Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

此方法不用将所有节点一次性入栈，而是在获得next时更新栈内的节点，因此更省时间。
将根节点的所有左子节点入栈，此时栈顶为最小值。
next方法：返回当前的栈顶节点。如果栈顶节点存在右子节点，则将其所有的左子节点入栈。
hasNext方法：返回栈是否为空的非值。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        updateStack(root);
    }
    
    public int next() {
        TreeNode node = stack.pop();
        updateStack(node.right);
        return node.val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    private void updateStack(TreeNode root){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

DFS搜索，中序搜索，从右子节点至左子节点，先将所有元素入栈。
next方法：挤出栈顶并返回。
hasNext方法： 返回栈是否为空的非值。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        initiateStack(root);
    }
    
    public int next() {
        return stack.pop().val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    private void initiateStack(TreeNode root){
        if(root == null){
            return;
        }
        initiateStack(root.right);
        stack.push(root);
        initiateStack(root.left);
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
Follow

Recents

Archives

Links

×