Category: LeetCode

Posted 2022-04-26Updated 2022-04-26LeetCode / Mediuma minute read (About 166 words)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

回溯，记录左右括号的出现次数。
每次递归都添加左侧括号。
左侧括号的数量大于右侧括号时递归下一级才可以添加右侧括号。
当左侧括号和右侧括号达到n时，返回字符串。

class Solution {
    int N;
    List<String> ret;
    StringBuffer sb;
    
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        sb = new StringBuffer();
        N = n;
        backtracking(0, 0);
        return ret;
    }
    
    private void backtracking(int left, int right){
        if(left > N || right > N){
            return;
        }
        if(left == N && right == N){
            ret.add(sb.toString());
            return;
        }
        if(left > right){
            sb.append(')');
            backtracking(left, right+1);
            sb.delete(sb.length()-1, sb.length());        
        }
        sb.append('(');
        backtracking(left+1, right);
        sb.delete(sb.length()-1, sb.length());        
    }
}

Posted 2022-04-26Updated 2022-06-25LeetCode / 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的两点没有合并，则合并两点，并取这条边作为结果。
加和所有的结果，答案就是最小值。

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 2022-04-26Updated 2022-04-25LeetCode / Mediuma minute read (About 189 words)

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

回溯，每个回溯层级添加数字对应的字符。

class Solution {
    public List<String> letterCombinations(String digits) {

        
        List<String> ret = new ArrayList<>();
        if(digits.equals("")) return ret;
        
        char[][] bin = new char[8][0];
        bin[0] = new char[]{'a', 'b', 'c'}; 
        bin[1] = new char[]{'d', 'e', 'f'};
        bin[2] = new char[]{'g', 'h', 'i'};
        bin[3] = new char[]{'j', 'k', 'l'};
        bin[4] = new char[]{'m', 'n', 'o'};
        bin[5] = new char[]{'p', 'q', 'r', 's'};
        bin[6] = new char[]{'t', 'u', 'v'};
        bin[7] = new char[]{'w', 'x', 'y', 'z'};
        
        backtracking(ret, new StringBuffer(), bin, digits, 0);
        return ret;
    }
    
    private void backtracking(List<String> ret, StringBuffer sb, char[][] bin, String digits, int i){
        if(sb.length() == digits.length() ){
            ret.add(sb.toString());
            return;
        }
        
        for(char c : bin[digits.charAt(i)-'2']){
            sb.append(c);
            backtracking(ret, sb, bin, digits, i+1);
            sb.delete(sb.length()-1, sb.length());
        }
    }
}

Posted 2022-04-25Updated 2022-04-25LeetCode / Medium / 复习3 minutes read (About 411 words)

142. Linked List Cycle II

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

快慢指针。快指针的移动速度是慢指针的两倍。
设环外长度为a，b是快指针和慢指针相遇的位置，c是环中剩余位置。
可以由此得到公式a + (n + 1)b + nc = 2(a + b)，也就是a = c + (n - 1)(b + c)
由于（b + c）是环的长度。因此，当两个指针相遇时，在头部设置一个新节点。慢指针和新指针将在循环入口处相遇，此时返回节点。

/**
 * 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 || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)) break;
        }
        
        if(fast == null || fast.next == null){
            return null;
        }
        
        ListNode root = head;
        while(!root.equals(slow)){
            slow = slow.next;
            root = root.next;
        }
        return root;
    }
}

哈希表，递归并将节点加入哈希集合，如果重复则返回节点，反之返回null。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    HashSet<ListNode> set;
    public ListNode detectCycle(ListNode head) {
        set = new HashSet<>();
        return findCycle(head, 0);
    }
    
    private ListNode findCycle(ListNode root, int count){
        if(root == null){
            return null;
        }
        if(set.contains(root)){
            return root;
        }
        set.add(root);
        count++;
        return findCycle(root.next, count);
    }
}

Posted 2022-04-25Updated 2022-04-25LeetCode / Medium2 minutes read (About 348 words)

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

递归，每次递归时建立root的next节点，然后将root移动到root.next。
计算两个节点的和并填入root节点。每次计算时需要计算是否进位。
递归两个节点的next节点，并将carry传入。
当一个节点为null时，只递归和计算另一个节点。
当两个节点为null时，如果有carry需要将其放入新节点，如果没有则返回。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode();
        addTwo(l1,l2,root,0);
        return root.next;
    }
    
    private void addTwo(ListNode l1, ListNode l2, ListNode root, int carry){
        if(l1 == null && l2 == null && carry == 0){
            return;
        }
        else if(l1 == null && l2 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = carry;
            return;
        }
        else if(l1 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;
            addTwo(null, l2.next, root, carry);
            return;
        }
        else if(l2 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;
            addTwo(null, l1.next, root, carry);
            return;
        }
        root.next = new ListNode();
        root = root.next;
        root.val = (l1.val + l2.val + carry) % 10;
        carry = (l1.val + l2.val + carry) / 10;

        addTwo(l1.next, l2.next, root, carry);
    }
}

Posted 2022-04-25Updated 2022-04-24LeetCode / Medium2 minutes read (About 229 words)

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

由于有重复性元素，因此先将数组排序。
储存一个数组，记录元素是否被选择。
回溯，遍历选择元素，并计算加和，并记录选择的元素。当选择的元素与上一个元素重复时，则跳过。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, ret, new ArrayList<>(), new int[candidates.length], target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int[] visited, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            if(i > 0 && candidates[i] == candidates[i-1] && visited[i-1] == 0) continue;
            visited[i] = 1;
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, visited, target, sum, i+1);
            visited[i] = 0;
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}

Posted 2022-04-25Updated 2022-04-24LeetCode / Medium2 minutes read (About 240 words)

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

回溯，记录当前加和。
遍历所有数组元素，当sum大于target时返回，等于target时加入数组并返回。
每次遍历并回溯元素时只递归当前元素和其之后的元素。（防止重复。）

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        backtracking(candidates, ret, new ArrayList<>(), target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, target, sum, i);
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}

Posted 2022-04-25Updated 2022-04-24LeetCode / Medium / 复习2 minutes read (About 255 words)

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

首先排序，对于有重复数据的数组，排序可以方便剪枝。
回溯，每次遍历数组内的元素。
创建一个数组记录元素是否已被遍历。
遍历时如果数组已经被记录，或者当前元素与数组中的上一个元素相等，且上一个数组未被选择，则跳过。
（如果上一个同样的数字没被选择，则放弃这个排列。即在元素相同时，优先选择前面的元素进行排列）

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int[] visited = new int[nums.length];
        backtracking(ret, new ArrayList<>(), visited , nums);
 
        return ret;
    }

    private void backtracking(List<List<Integer>> ret, List<Integer> arr, int[] visited, int[] nums){
        if(arr.size() == nums.length){
            ret.add(new LinkedList<>(arr));
            return;
        }
        
        for(int i = 0; i < nums.length; i++){
            if(visited[i] == 1) continue;
            if(i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0) continue;
            arr.add(nums[i]);
            visited[i] = 1;
            backtracking(ret, arr, visited, nums);
            visited[i] = 0;
            arr.remove(arr.size()-1);
        }
    }
}

Posted 2022-04-25Updated 2022-04-24LeetCode / Mediuma minute read (About 217 words)

284. Peeking Iterator

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

PeekingIterator(Iterator nums) Initializes the object with the given integer iterator iterator.

int next() Returns the next element in the array and moves the pointer to the next element.

boolean hasNext() Returns true if there are still elements in the array.

int peek() Returns the next element in the array without moving the pointer.

Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.

使用队列储存迭代器里的数据，根据需要返回队列里的数据。

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Queue<Integer> q;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    q = new LinkedList<>();
        while(iterator.hasNext()){
            q.add(iterator.next());
        }
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return q.peek();
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    return q.poll();
	}
	
	@Override
	public boolean hasNext() {
	    return !q.isEmpty();
	}
}

Posted 2022-04-25Updated 2022-04-24LeetCode / Medium / 复习a minute read (About 214 words)

90. Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

首先对数组进行排序，这样重复的元素将排列在一起。
接下来对每一个层级进行回溯。
进入每一个层级都根据上一级传递来的列表创建新列表。
然后对层级下的所有元素进行回溯。
剪枝，当遍历节点和上一个节点相等时，则跳过。
回溯，从列表中去掉最后一个元素。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        backtrack(ret, new LinkedList<Integer>(), nums, 0);
        return ret;
    }
    
    private void backtrack(List<List<Integer>> ret, List<Integer> arr, int[] nums, int level){
        ret.add(new LinkedList<>(arr));
        
        for(int i = level; i < nums.length; i++){
            if(i != level && nums[i] == nums[i-1]) continue;
            arr.add(nums[i]);
            backtrack(ret, arr, nums, i+1);
            arr.remove(arr.size()-1);
        }
    }
}

Posted 2022-04-24Updated 2022-04-24LeetCode / Medium / 复习2 minutes read (About 351 words)

187. Repeated DNA Sequences

The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’.

For example, “ACGAATTCCG” is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

哈希表 + 滑动窗口 + 位操作。
将四个字符映射到四个二进制字符上。这样字符串就可以用20bit表示。
这样就可以用一个整数来表示这四个字符。
然后采用哈希表记录出现次数。

class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        if(s.length() < L) return ret;
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        int[] bin = new int[26];
        bin['A'-'A'] = 0;
        bin['T'-'A'] = 1;
        bin['C'-'A'] = 2;
        bin['G'-'A'] = 3;
        
        int x = 0;
        for(int i = 0; i < L-1; i++){
            x = (x << 2) | bin[s.charAt(i)-'A'];
        }
        
        for(int i = 0; i <= s.length() - L; i++){
            x = ((x << 2) | bin[s.charAt(i + L -1)-'A']) & ((1 << L * 2) - 1);
            map.put(x, map.getOrDefault(x, 0)+1);
            if(map.get(x) == 2) ret.add(s.substring(i, i+L)); 
        }
        return ret;
    }
}

遍历将字字符串加入哈希表并记录出现次数，然后返回出现次数大于1的字符串。
注意在循环时就可以直接添加结果到列表，这样可以减少操作。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<String>();
        HashMap<String, Integer> map = new HashMap<>();
        int left = 0;
        int right = 10;
        
        while(right <= s.length()){
            String sub = s.substring(left, right);
            map.put(sub, map.getOrDefault(sub, 0)+1);
            if(map.get(sub) == 2) ret.add(sub); 
            left++;
            right++;
        }
        return ret;
    }
}

Posted 2022-04-24Updated 2022-06-08LeetCode / Medium / 复习8 minutes read (About 1136 words)

5. Longest Palindromic Substring

Question

Given a string s, return the longest palindromic substring in s.

Solution

马拉车算法，专门用于计算最大回文子字符串长度。

预处理

首先需要对字符串进行预处理，将每两个字符之间（包括两端）加上一个符号’#’。
然后在字符串的前后加入任意两个不同的符号。（防止中心扩展时继续搜索）

这个操作使得偶数项的回文字符串变为奇数项的回文字符串，便于接下来进行统一的中心扩展操作。

Manacher算法

参考资料：一文让你彻底明白马拉车算法

用一个数组p[]记录处理后字符串位置的中心展开长度。

初始化一个回文中心的下标位置i，和当前回文中心的右侧范围r。
在进行算法时维护这两个参数。

遍历字符串中除了首尾两个字符以外的位置。

初始化i位置关于c的镜像位置m为2*c-i。
由于回文字符串的对称特性，此时p[i]的中心拓展长度应等于p[m]。
有几种特例情况，p[i]不等于p[m]：

如果p[m] + m的和大于r，则以m为中心扩展的范围超过当前c的中心扩展范围的右界。
此时p[i]无法保证等于p[m]。但是可以确保p[i]至少可以扩展到r，因此将p[i]更新为r-i。
如果i的位置等于r，则可扩展距离为0。
如果m的位置为原字符串的左边界，则此时将p[i]赋值为1是不正确的。
因为p[m]的计算是遇到了边界停止的，而p[i]则没有遇到边界，接下来对i位置从i+p[i]与i-p[i]开始继续进行中心扩展即可。

中心扩展

奇数项的回文字符串由中心扩展，只需要保证i+p[i]+1与i-p[i]-1（两个位置分别表示当前中心扩展的边缘再前进1）的字符相同，则可以继续向下扩展，将p[i]++。

c与r的更新

由于要保证i在r的范围之内，当从i出发的中心扩展范围大于c的中心扩展范围r，需要更新c与r。

时间复杂度

在进行扩展时，每次访问过的位置不会进入中心扩展算法。（比较从中心扩展的边缘开始，即i+p[i]+1与i-p[i]-1）
因此总的时间复杂度为O(n)。

Code

class Solution {
    int n;
    int[] p;
    String newString;
    public String longestPalindrome(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        manacher();
        
        int c = 0;
        for(int i = 0; i < sb.length(); i++){
            if(p[i] > p[c]) c = i;
        }
        return s.substring( (c-p[c])/2, (c-p[c])/2+p[c] );
    }
    
    private void manacher(){
        int c = 0, r = 0;
        for(int i = 1; i < p.length - 1; i++){
            int m = 2 * c - i;
            if(i < r){  //当i在r的范围内时，p[i]的值与p[m]相等。
                p[i] = Math.min(r-i, p[m]); //当p[m] + i超过了r时(当前中心拓展边界)，p[i]至少可以取值到r-i
            }
            else{
                p[i] = 0; //当i等于r时，该位置拓展距离为0
            }
            
            while (newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)) {  //中心拓展算法，当两个位置相等时则可拓展距离+1
                p[i]++;
            }
            
            if(i + p[i] > r){   //当当前位置的右侧边界大于现有边界时，更新位置r
                c = i;
                r = i + p[i]; //新的右侧边界为新的中心+拓展长度p[i]
            }
        }
    }
}

Solution 2

getLength方法，计算每一个字符位置的回文长度。（将left填成i+1，right填成i则可以搜索偶数回文的长度。）
如果出现更长的回文，则根据返回的长度，和当前的i计算出字符串的范围。

Code

class Solution {
    public String longestPalindrome(String s) {
        int best = 0;
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            int length = Math.max(getLength(s,i,i), getLength(s,i+1,i));
            if(best < length){
                left = i-((length-1)/2-1);
                right = i+(length/2);
                best = length;
            }
        }
        return s.substring(left,right);
    }
    
    private int getLength(String s, int left, int right){
        while(left >= 0 && right < s.length() && left < s.length()){
            if(s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            else break;
        }

        return right - left + 1;
    }
}

Posted 2022-04-24Updated 2022-04-24LeetCode / 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出站进站不同的情况。）

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 2022-04-24Updated 2022-04-24LeetCode / Mediuma minute read (About 151 words)

78. Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

回溯，先添加一个空集，然后回溯各个单独节点。
递归时传入数组内当前数字之后的节点。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        ret.add(new ArrayList<>());
        
        for(int i = 0; i < nums.length ; i++){
            backtrack(ret, new ArrayList<>(), nums, i);
        }
        return ret;
    }
    
    private void backtrack(List<List<Integer>> ret, List<Integer> arr, int[] nums, int i){
        if(i == nums.length-1){
            arr.add(nums[i]);
            ret.add(new ArrayList<>(arr));
            return;
        }

        arr.add(nums[i]);
        ret.add(new ArrayList<>(arr));
        for(int j = i+1; j < nums.length; j++){
            backtrack(ret, arr, nums, j);
            arr.remove(arr.size()-1);
        }
    }
}

Posted 2022-04-23Updated 2022-04-23LeetCode / Medium / 复习a minute read (About 214 words)

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

两个字符串的位数做乘法，每次计算进位。
当前位等于自身加上计算结果的个位（由于有之前的进位存在。），下一位等于计算结果的十位。

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        if( num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int[] product = new int[m+n];
        
        char[] arr1 = num1.toCharArray();
        char[] arr2 = num2.toCharArray();
        
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >=0; j--){
                int sum = product[i+j+1] + (arr1[i] - '0') * (arr2[j] - '0');
                int curr = sum % 10;
                int carry = sum / 10;
            
                product[i+j] += carry;
                product[i+j+1] = curr;
            }
        }
        StringBuffer sb = new StringBuffer();
        for(int k = 0; k < m+n; k++ ){
            if(k == 0 && product[k] == 0 ) continue;
            sb.append(product[k]);
        }
        return sb.toString();
    }
}

Question

Solution

预处理

Manacher算法

中心扩展

c与r的更新

时间复杂度

Code

Solution 2

Code

Recents

Archives

Links