Tag: 其他解法？

Posted 2022-08-21Updated 2022-08-21LeetCode / Medium / 复习3 minutes read (About 466 words)

659. Split Array into Consecutive Subsequences

Question

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).

All subsequences have a length of 3** or more**.

Return true* if you can split nums according to the above conditions, or false otherwise*.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Solution

用优先级队列储存每个可组成的列表。
优先级队列根据列表的长度排列。

用哈希表记录每个列表的尾数，和其对应的优先级队列。
遍历所有数字，如果存在当前数字num-1为尾数的队列，则获取长度最小的列表，并添加当前数字num在列表中。
然后将新的优先级队列放入哈希表中。

遍历整个哈希表中的数组，如果有数组的长度小于3，则返回false，否则返回true。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<List<Integer>>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<List<Integer>> last = map.getOrDefault(num - 1, null);
            PriorityQueue<List<Integer>> curr = map.getOrDefault(num, new PriorityQueue<List<Integer>>((a,b) -> a.size() - b.size()));

            if(last == null || last.size() == 0){
                List<Integer> arr = new ArrayList<>();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
            else{
                List<Integer> arr = last.poll();
                arr.add(num);
                curr.add(arr);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(List<Integer> arr : map.get(last)){
                if(arr.size() < 3) return false;
            }
        }
        return true;
        
    }
}

Solution 2

不需要保存整个列表，只需要保存对应末尾数字的列表长度即可。

Code

class Solution {
    public boolean isPossible(int[] nums) {
        HashMap<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        
        for(int num : nums){
            PriorityQueue<Integer> last = map.getOrDefault(num - 1, null);
            PriorityQueue<Integer> curr = map.getOrDefault(num, new PriorityQueue<Integer>());

            if(last == null || last.size() == 0){
                curr.add(1);
                map.put(num, curr);
            }
            else{
                int min = last.poll();
                curr.add(min+1);
                map.put(num, curr);
            }
        }                   
                                      
        for(int last : map.keySet()){
            for(int len : map.get(last)){
                if(len < 3) return false;
            }
        }
        return true;

    }
}

Posted 2022-08-03Updated 2022-08-03LeetCode / Medium / 复习2 minutes read (About 361 words)

729. My Calendar I

Question

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.

boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Solution

有更快速的解法，需要用到TreeMap，有时间再研究。

使用一个队列记录已经预定的范围。
添加无穷大到队列中，方便后期计算。

当预定新的时间段时，遍历队列，如果上一个数组的最大值小于start和end且当前遍历数组大于start和end，则可以预定，将当前的数组插入当前位置，并返回true。
如果没有满足条件的，则返回false。

Code

class MyCalendar {
    List<int[]> arr;
    public MyCalendar() {
        arr = new ArrayList<>();
        int[] inf = new int[2];
        inf[0] = Integer.MAX_VALUE;
        inf[1] = Integer.MAX_VALUE;
        arr.add(inf);
    }
    
    public boolean book(int start, int end) {
        int[] last = new int[2];
        for(int i = 0; i < arr.size(); i++){
            int[] curr = arr.get(i);
            if(last[1] < end && last[1] <= start && curr[0] >= end && curr[0] > start){
                int[] n = new int[2];
                n[0] = start;
                n[1] = end;
                arr.add(i, n);
                return true;
            }
            last = curr;
        }
        return false;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

Posted 2022-07-13Updated 2022-07-16LeetCode / Medium / 复习2 minutes read (About 279 words)

473. Matchsticks to Square

Question

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Solution

回溯，用int[] edges记录边长。

先计算所有火柴棍的长度之和是否能被4整除，如果不能则返回false。
将所有火柴排序，以减少回溯时的计算量。

Backtracking 回溯

当遍历越界时（传入index为-1），则返回true。

每次将当前火柴matchsticks[index]添加到一个edges[i]中。
当edges[i] <= sum / 4，且向前回溯前一个位置index-1返回结果为真，则返回true。
然后将当前火柴从edges[i]中取出。

Code

class Solution {
    int[] edges;
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for(int i = 0; i < matchsticks.length; i++) sum += matchsticks[i];
        if(sum % 4 != 0) return false;
        
        edges = new int[4];
        Arrays.sort(matchsticks);
        return backtracking(matchsticks, matchsticks.length-1, sum/4);
    }
    
    public boolean backtracking(int[] matchsticks, int index, int len){
        if(index == -1) return true;

        for(int i = 0; i < 4; i++){
            edges[i] += matchsticks[index];
            if(edges[i] <= len && backtracking(matchsticks, index - 1, len)) return true;
            edges[i] -= matchsticks[index];
        }
        return false;
    }
}

Posted 2022-07-05Updated 2022-07-04LeetCode / Medium / 复习2 minutes read (About 306 words)

128. Longest Consecutive Sequence

Question

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution 1

哈希表，先将所有元素加入哈希表。
然后遍历哈希表，如果表内没有当前数字-1时（没有更小的连续数字），则将temp初始化为1。
当表内有下一个连续数字时，将temp和curNum增加1。

当没有下一个连续数字时，更新结果到res上。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int num : nums){
            set.add(num);
        }
        
        int res = 0;
        
        for(int num : set){
            if(!set.contains(num - 1)){
                int temp = 1;
                int curNum = num;
                while(set.contains(curNum + 1)){
                    temp++;
                    curNum++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}

Solution 2

先排序，再遍历。
维护一个最大长度res。
用一个temp参数记录连续长度。
如果当前值是上一个值+1，则temp+1。
如果当前值等于上一个值，则continue。
其他情况则更新最大长度res，并将temp恢复为1。

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Arrays.sort(nums);
        int res = 0, temp = 1;
        
        for(int i = 1; i < nums.length; i++){
            if(nums[i] == nums[i-1] + 1){
                temp++;
            }
            else if(nums[i] == nums[i-1]){
                continue;
            }
            else{
                res = Math.max(res, temp);
                temp = 1;
            }
        }
        res = Math.max(res, temp);
        
        return res;
    }
}

Posted 2022-07-04Updated 2022-07-04LeetCode / Hard / 复习2 minutes read (About 227 words)

135. Candy

Question

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

双向遍历。
先从左至右遍历数组，如果上一个数值小于当前数值，则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组，同理计算right的数值。
然后保存right与left[]里较大的数值，作为需要分配的糖果数加入到res。

Code

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            if(i > 0 && ratings[i] > ratings[i-1]){
                left[i] = left[i-1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        
        int right = 0, res = 0;
        for(int i = ratings.length-1; i >= 0; i--){
            if(i < ratings.length-1 && ratings[i] > ratings[i+1]){
                right++;
            }
            else{
                right = 1;
            }
            res += Math.max(left[i], right);
        }
        return res;
    }
}

Posted 2022-05-24Updated 2022-05-25LeetCode / Hard / 复习4 minutes read (About 611 words)

32. Longest Valid Parentheses

Question

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Solution

如果有右括号先出现于左括号，则其永远无法配对。
而如果是左括号先出现，则其有可能可以和之后的右括号进行配对。

因此我们可以将左括号的位置入栈，等待配对。
并记录上一个不能配对的右括号的位置。以此来确定当前位置的有效括号长度。

首先将上一个不能组队的右括号lastRightParenthese初始化为-1。
初始化一个最大有效长度best。

然后遍历字符串：

当遇到左括号时：
- 将当前下标i压入栈。（记录等待配对的左括号）
遇到右括号时：
- 如果栈为空，则更新上一个不能组队的右括号的位置为当前下标i。（此时出现的右括号一定无法配对）
- 如果栈不为空，则挤出上一个左括号的下标，与右括号配对。
  - 挤出上一个左括号后，如果栈为空。则将当前的有效括号总长度为i - lastRightParenthese。（当前的右括号和上一个不能配对的右括号的差）
  - 否则当前的有效括号总长度为i - stack.peek()。（当前的右括号和上一个不配对的左括号的差。）

Code

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int best = 0;
        int lastRightParenthese = -1;   //上一个不能配对的右括号位置，初始化为-1
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){ //如果当前位置是左括号，则将下标入栈
                stack.push(i);
            }
            else{   //如果当前位置是右括号...
                if(stack.isEmpty()){    //如果没有可以配对的左括号，则更新不能配对的右括号的位置
                    lastRightParenthese = i;
                }
                else{
                    stack.pop();    //如果有可以配对的右括号，则从栈中挤出
                    if(stack.isEmpty()){    //挤出后如果没有剩余的左括号了，则当前有效括号长度为当前位置减去上一个无法配对的右括号的位置
                        best = Math.max(best, i - lastRightParenthese);
                    }
                    else{   //如果挤出后栈内仍有剩余的左括号存在，则当前有效括号长度为当前位置减去栈顶的左括号的位置
                        best = Math.max(best, i - stack.peek());
                    }
                }
            }
        }
        return best;
    }
}

Posted 2022-05-06Updated 2022-05-05LeetCode / Medium / 复习4 minutes read (About 538 words)

673. Number of Longest Increasing Subsequence

Question

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

本题还有贪心算法+前缀和+二分查找的算法。

本题是300. Longest Increasing Subsequence的拓展。
同样采用动态规划，数组dp[i]记录到i为止最长递增数列长度。
可以用一个新的数组cnt[i]记录到i为止可以组成的最长递增数列的数量。

对于每个新位置i，cnt[i]的最小值为i。
遍历i之前的所有位置j。如果nums[j] < nums[i]，则i可以比dp[j]组成更长的递增数列，其长度为dp[j]+1。
如果dp[i] < dp[j]+1。则可以更新dp[i]。同时，cnt[i]可以从cnt[j]继承其计数。
如果dp[i] == dp[j]+1。则之前已经更新过dp[i]。说明有新的组合同样可以组成更长的递增数列。此时将cnt[j]加入当前的cnt[i]。

遍历完成i以内的所有j后，如果dp[i]大于当前的最长递增数列长度，则更新max。
同时更新长度的总数count为cnt[i]。
如果dp[i]等于max，则将cnt[i]加入计数count。
最后返回count。

Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int max = 0;
        int count = 0;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];    //如果后面的数字大于前面的，且可以组成更长的数列，则继承之前的计数。
                    }
                    else if(dp[j] + 1 == dp[i]){    //如果之前已经更新过dp[i]，则有新的组合长度一直，加和之前的计数。
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > max){    //如果当前的长度大于之前的最大值，则更新。
                max = dp[i];
                count = cnt[i];  //同时将之前计算的计数记录。
            }
            else if(dp[i] == max){  //如果有同样达到最大值的情况，则加和计数。
                count += cnt[i];
            }
        }
        return count;
    }
}

Posted 2022-05-05Updated 2022-05-05LeetCode / Medium / 复习2 minutes read (About 260 words)

973. K Closest Points to Origin

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Solution

此题可以采用快速排序的思想。可以在O(n)时间复杂度里完成排序。

Solution 2

优先级队列，根据每个点距离的平方排序。时间复杂度O(nlogk)。

Code

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int[] point : points){
            pq.add(point);
        }
        for(int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Solution 3

直接排序。时间复杂度为O(nlogn)。

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int i = 0; i < k; i++){
            ret[i] = points[i];
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Posted 2022-05-01Updated 2022-05-01LeetCode / Medium / 复习2 minutes read (About 285 words)

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

动态规划，创建一个数组dp[]，长度为字符串长度+1，记录是否可以达到。
将dp[0]设置为1，表示可以达到。

从可取长度为1开始，遍历直到可取长度为字符串的长度。
用下一个遍历j将字符串分为两部分。（这里j从i-1下降到0会比从0上升到i-1更快。）
当dp[j]可以到达，且当前的哈希表中有(i-j)组成的字符串时，则dp[i]也可以到达。结束第二层循环。
继续搜索更长的字符串是否可以达到。
最后返回dp中的最后一个元素。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        int n = s.length();
        int[] dp = new int[n+1];
        
        for(String word : wordDict){
            set.add(word);
        }
        dp[0] = 1;
        int temp = 0;
        for(int i = 1; i <= n; i++){
            for(int j = i - 1; j >= 0; j--){
                if(dp[j] == 1 && set.contains(s.substring(j, i))){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[n] == 1; 
    }
}

Posted 2022-04-30Updated 2022-04-29LeetCode / Medium2 minutes read (About 259 words)

1249. Minimum Remove to Make Valid Parentheses

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or

It can be written as AB (A concatenated with B), where A and B are valid strings, or

It can be written as (A), where A is a valid string.

用栈储存括号，按顺序将括号压入栈。
如果和上一个括号配对，则挤出上一个括号。

当栈不为空时，如果栈顶的符号为“)”，则优先去掉字符串左侧的括号。
如果栈顶的符号为“(”，则优先去掉字符串右侧的括号。
最后返回字符串。

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuffer sb = new StringBuffer(s);
        
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') stack.push('(');
            else if(s.charAt(i) == ')'){
                if(!stack.isEmpty() && stack.peek() == '(') stack.pop();
                else stack.push(')');
            }
        }
        
        while(!stack.isEmpty()){
            if(stack.pop() == ')'){
                int index = sb.indexOf(")");
                sb.delete(index, index+1);
            }
            else{
                int index = sb.lastIndexOf("(");
                sb.delete(index, index+1);
            }
        }        
        return sb.toString();
    }
}

Posted 2022-04-30Updated 2022-04-29LeetCode / Easy / 复习a minute read (About 203 words)

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.

void pop() removes the element on the top of the stack.

int top() gets the top element of the stack.

int getMin() retrieves the minimum element in the stack.

分别将数据保存在一个Priority Queue和一个栈中。
pop方法pop掉stack的内容，然后将其从优先队列中移除。
top方法返回stack的栈顶。
getMin方法返回优先队列的顶。

class MinStack {
    Queue<Integer> pq;
    Stack<Integer> stack;
    public MinStack() {
        pq = new PriorityQueue<>();
        stack = new Stack<>();
    }
    
    public void push(int val) {
        pq.add(val);
        stack.add(val);
    }
    
    public void pop() {
        int i = stack.pop();
        pq.remove(i);
        
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return pq.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Posted 2022-04-28Updated 2022-04-28LeetCode / Hard / 复习3 minutes read (About 474 words)

25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

采用直接更改节点的方法可以使用O(1)的空间完成操作。

递归，DFS搜索，首先初始化一个哨兵节点。
将哨兵节点记录为first，下一个节点记录为second。

将first与second传入递归方法。
向下递归下一个节点，并将长度k-1。
当长度k等于1时，则递归到当前所需的栈底。将当前节点指向上一个节点，并将当前节点记录为last，下一个节点记录为next，返回true。
当curr为null时，返回false。

当递归返回为true时（即剩余的链表有k个节点以供翻转），上级的节点们都指向其前一个节点。当返回到的栈顶（即k等于最开始的值）时，将first指向last，将second指向next。

继续向下递归first与second。

/**
 * 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 {
    int K;
    ListNode next;
    ListNode prev;
    ListNode last;
    ListNode first;
    ListNode second;
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        
        K = k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        prev = dummy;
        next = null;
        last = null;
        first = prev;
        second = prev.next;
        
        reverse(prev, dummy.next, k);
        
        return dummy.next;
    }
    
    private boolean reverse(ListNode prev, ListNode curr, int k){
        if(curr == null) return false;
        if(k == 1){
            last = curr;
            next = curr.next;
            curr.next = prev;
            return true;
        }
        
        if( reverse(curr, curr.next, k-1) ){
            curr.next = prev;
            if(k == K){
                first.next = last;
                second.next = next;
                first = curr;
                second = curr.next;
            
                reverse(first, second, k);
            }
            return true;
        }
        return false;
    }
    
    private void print(ListNode root){
        while(root != null){
            root = root.next;
        }
    }
}

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-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-23Updated 2022-04-22LeetCode / Medium / 复习3 minutes read (About 519 words)

1091. Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.

由于不能重复搜索，且需要在搜索时将搜索过的位置改变，因此需要采用BFS逐一层级的搜索。
逐层级搜索并记录层级。最后返回层级+1即可。
（还有更快的优化算法A*）

整体没有改变太多，基本还是方法二那种。启发式函数改为切比雪夫距离距离。
距离计算方法有很多，常用启发式函数有这几种。选择合适的启发式函数有利于速度的提升。这题可以用好几种启发式函数，初学都可以试着都写一下。

曼哈顿距离（Manhattan Distance）
一般只能在四个方向上移动时用（右、左、上、下）

对角线距离（Diagonal Distance）：
当我们只允许向八个方向移动时用（国际象棋中的王移动方式那种）

欧几里得距离（Euclidean Distance）：
不受限制，允许向任何方向移动时。

切比雪夫距离（Chebyshev Distance）：
可参考：[https://leetcode-cn.com/problems/minimum-time-visiting-all-points/solution/fang-wen-suo-you-dian-de-zui-xiao-shi-jian-by-le-2/](LeetCode 1266)

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid[0].length;
        int m = grid.length;
        
        Queue<Integer> q = new LinkedList<>();
        int count = 0;
        q.add(0);
        int size = q.size();
        
        while(!q.isEmpty()){
            for(int k = 0; k < size; k++){
                int curr = q.poll();
                int i = curr / n;
                int j = curr % n;

                if(grid[i][j] ==1) continue;                
                if(i == m-1 && j == n-1 && grid[i][j] == 0) return count+1;
            
                if(grid[i][j] == 0){
                    grid[i][j] = 1;
                    if(i+1<n && j+1<n) q.add((i+1) * n + (j+1));
                    if(i+1<n && j-1>=0) q.add((i+1) * n + (j-1));
                    if(i+1<n) q.add((i+1) * n + j);
                    if(i-1>=0 && j-1>=0) q.add((i-1) * n + (j-1));
                    if(i-1>=0 && j+1<n) q.add((i-1) * n + (j+1));
                    if(j+1<n) q.add(i * n + (j+1));
                    if(j-1>=0) q.add(i * n + (j-1));
                    if(i-1>=0) q.add((i-1) * n + j);
                }
            }
            size = q.size();
            count++;
        }
        return -1;
    }
}

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Backtracking 回溯

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Solution 2

Code

Solution 3

Recents

Archives

Links