321场周赛

追加字符以获得子序列

只想到O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int appendCharacters(String s, String t) {
    int i=0;
    int j=0;
    int res=0;
    while(i<s.length()){
        if(s.charAt(i)==t.charAt(j)){
            int k=i;
            while(j<t.length()&&k<s.length()){
                if(s.charAt(k)==t.charAt(j)){
                    j++;
                }
                k++;
            }
            res=j>res?j:res;
        }
        i++;
        j=0;
    }
    return t.length()-res;
}

思路：按顺序遍历s串，如果t中的某个字符（下标j）s串中没有，则需要添加的长度为lens(t) - j

就是想复杂了，这道没有做出来，不应该。

拓展：最长公共子序列

使用dp

  • 明确dp数组含义

    dp[i][j]表示s1[0...i]和s2[0...j]最长公共子序列长度。

  • 确定base case

  • 状态转移

从链表中移除节点

我想到的是单调栈获取下一个最大元素

复习单调栈

下一个更大元素 I 时间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
static int[] nextGreaterElement(int[] nums) {
    int n=nums.length;
    int res[]=new int[n];
    Stack<Integer> stack = new Stack<>();
    for(int i=n-1;i>=0;i--){ //从后往前入栈
        while(!stack.isEmpty() && stack.peek()<=nums[i]){  //栈顶元素小于等于当前元素，则栈顶元素弹开
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(nums[i]);
    }
    return res;
}