Hexo

Posted 2022-05-01Updated 2022-08-07LeetCode / Medium / 复习4 minutes read (About 589 words)

Question

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Solution

贪心算法

创建一个数组记录达到升序的长度时升序数列的最小末尾值。
如果想要增加数组的长度（即增加最大的升序数列长度），则新的数字必须要大于该数组最后一位的大小。
因此在这种情况下，该数组必然是单调递增的。

二分搜索

将第一个数字填入数组。
然后遍历数组，当新一项大于数组的最后一个值时，最大长度加一，并将其加入数组的尾部。
当新一项小于数组的最后一个值时，该数字需要与之前的数组组成新的升序数列。
我们可以替换掉之前数组中比该数字大的第一个数字，代表新组成的数组。（最长数组之间的数字无所谓，只记录最小的末尾值即可。）
我们可以用二分搜索查到该数字需要加入的index。然后替换掉数组中的数字。
单次二分搜索的时间复杂度为O($logn$)。总的时间复杂度为O($nlogn$)。

Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int len = 1;
        ans.add(nums[0]);
    
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > ans.get(ans.size()-1)){
                ans.add(nums[i]);
                len++;
            }
            else{
                int index = Collections.binarySearch(ans, nums[i]);
                if(index < 0){
                    ans.set(-(index+1), nums[i]);
                }
            }
        }
        return len;
    }
}

Solution 2

动态规划，创建一个数组dp[]用来记录最大长度，创建max记录最大值。
遍历，先将数组dp[]上的所有位置都填上1。
从0到i-1遍历j。当nums[i] > nums[j]时，更新dp[i]为dp[i]与dp[j]+1中的较大值。
当更新dp[i]时将其和max比较，如果比max大则更新max。
最后返回max值。时间复杂度为O($n_2$)

Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = i-1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    if(max < dp[i]){
                        max = dp[i];
                        break;
                    }
                }
            }
        }
        return max;
    }
}

Posted 2022-05-01Updated 2022-06-25LeetCode / Medium / 复习6 minutes read (About 841 words)

399. Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

这道题的核心是边上带权的并查集。
如何在find以及union时计算并更新权重是最重要的。
组合过后，根节点的权重依然为1，以其为标准更新其他节点的权重。

先通过一个哈希表建立字符串与id的映射关系，为每个字符串生成一个单独的id。

然后将一个equation里的两个字符串进行union操作。
并查集初始化时，所有权重为1。

在find时，执行路径压缩时需要用当前的权重weight[id]更新为其自身乘以其上一级的权重weight[origin]。
这里需要注意计算的顺序需要从根上的权重，以递归的形式计算到当前权重。
因此我们需要先单独保存parents[id]的位置。然后find(parents[id])，先计算出其上级的weight。
最后再将weight[id]更新为更新后的上一级的权重乘以自身权重。

1
2
3

int origin = parents[id];
parents[id] = find(parents[id]);
weight[id] *= weight[origin];

在union时，将两个集合中的一个的根指向另一个。
例如当结合a与b两个节点时，我们已经计算过了(a -> b)的权重关系，以及(d -> c)的权重关系。
我们将(b -> d)。这时我们可以通过values[i]得到(a -> d)的权重关系。因此我们可以据此得出以下公式：

weight[(b->c)] = weight[(d->c)] × values[(a->d)]/weight[(a->b)]

1 2	parents[p1] = parents[p2]; weight[p1] = weight[id2]*val/weight[id1];

最后，当所有节点都被合并后，我们可以遍历queries。
从哈希表获得对应字符串的id。
当有字符串未在哈希表中时，返回-1.0。
否则计算两个id对应的权重，并添加到答案中。

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] ret = new double[queries.size()];
        HashMap<String, Integer> map = new HashMap<>();
        UnionFind uf = new UnionFind(equations.size() * 2);
        int id = 0;
        for(int i = 0; i < equations.size(); i++){
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);
            if( !map.containsKey( var1 ) ){
                map.put( var1, id );
                id++;
            }
            if( !map.containsKey( var2 ) ){
                map.put( var2, id );
                id++;
            }
            uf.union(map.get(var1), map.get(var2), values[i]);
        }
        for(int i = 0 ; i < queries.size(); i++){
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);
            Integer id1 = map.get(var1);
            Integer id2 = map.get(var2);
            if(id1 == null || id2 == null) ret[i] = -1.0;
            else ret[i] = uf.isConnected(id1, id2);
        }
        return ret;
    }
    
    class UnionFind{
        int[] parents;
        double[] weight;
        public UnionFind(int n){
            parents = new int[n];
            weight = new double[n];
            for(int i = 0; i < parents.length; i++){
                parents[i] = i;
                weight[i] = 1.0;
            }
        }
        public int find(int id){
            if (id != parents[id]) {
                int origin = parents[id];
                parents[id] = find(parents[id]);
                weight[id] *= weight[origin];
            }
            return parents[id];
        }
        public boolean union(int id1, int id2, double val){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            parents[p1] = parents[p2];
            weight[p1] = weight[id2]*val/weight[id1];
            return true;
        }
        public double isConnected(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return weight[id1] / weight[id2];
            else return -1.0;
        }
    }
}

Posted 2022-04-30Updated 2022-04-292 minutes read (About 322 words)

1823. Find the Winner of the Circular Game

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1.Start at the 1st friend.

2.Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.

3.The last friend you counted leaves the circle and loses the game.

4.If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.

5.Else, the last friend in the circle wins the game.
Given the number of friends, n, and an integer k, return the winner of the game.

约瑟夫环问题。
根据题目要求，当去除一个成员时，下一个节点的编号为k+1。
当新的循环开始时，总人数n-1，同时k+1变为新循环中的1。

因此可以采用递归，当n剩下一个人时，返回其编号1。
对应上层这个成员的位置为k+1，向上递归。
由于k+1可以越界，因此每次返回需要对其取模。

class Solution {
    public int findTheWinner(int n, int k) {
        if(n == 1) return 1;
        int ans = findTheWinner(n-1, k) + k;
        return ans % n == 0 ? n : ans % n;
    }
}

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();
 */

Question

Solution

贪心算法

二分搜索

Code

Solution 2

Code

Recents

Archives

Links