Skip to content
On this page

最长连续序列

  • 用例 1:

    输入:nums = [100,4,200,1,3,2] 输出:4 解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

  • 用例 2:

    输入:nums = [0,3,7,2,5,8,4,6,0,1] 输出:9

暴力解法

遍历每一位数 n,循环查找 n+1 数字是否存在,并且维护一个最长的序列值

哈希表

降低查找时间,将数字存入哈希表

另外对于这个序列 [0,3,7,2,5,8,4,6,0,1],在遍历 3 这个数字并计算最长序列后,遍历 2 时会重复计算

因此我们跳过那些每段序列中不是最小的数字,例如当前遍历元素 n,检查是否存在 n-1,存在就跳过

code

  • Go
go
func longestConsecutive(nums []int) int {
    bucket := make(map[int]bool)
    for _,v := range nums{
        bucket[v]=true
    }
    res := 0
    for _,v := range nums{
        if !bucket[v-1] {
            cur := 1
            t := v+1
            for bucket[t] {
                cur++
                t++
            }
            res = max(res,cur)
        }
    }
    return res
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
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

单调栈

去除重复字母

给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)

示例 1:

输入:s = "bcabc"
输出:"abc"

示例 2:

输入:s = "cbacdcbc"
输出:"acdb"
1
2
3
4
5
6
7
8
9
cpp
class Solution {
public:
    string removeDuplicateLetters(string s) {
        // 字符是否存在栈中
        int vis[26] = {0};
        // 未遍历的字符数量
        int c[26] = {0};

        for (char ch:s){
            c[ch-'a']++;
        }

        string stack;
        for(char ch:s){
            // 栈里不存在当前字符时
            if(!vis[ch-'a']){
                // 栈顶字符大于当前字符时,需要保持单调栈
                while(!stack.empty() && stack.back() > ch){
                    // 栈顶字符在后面不会在出现时,不能将它出栈
                    if(c[stack.back()-'a']>0){
                        vis[stack.back()-'a']=0;
                        stack.pop_back();
                    }else{
                        // 直接终止,栈顶字符不能出栈,无需继续处理
                        break;
                    }
                }
                // 进栈当前字符,并标识当前字符存在栈中
                vis[ch-'a']=1;
                stack.push_back(ch);
            }
            // 字符数量减1,c 存储的是当前未遍历的字符串中每个字符的数量
            c[ch-'a']--;
        }
        return stack;
    }
};
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

动态规划

组合总和_Ⅳ

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
示例 2:

输入:nums = [9], target = 3
输出:0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法一

从上往下看 [1,2,3] 中,target 为 4 的组合

应该为 dp[4-1] + dp[4-2] + dp[4-3]

target 为 3 的组合, 为 dp[3-1] + dp[3-2] + dp[3-3]

cpp
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n=nums.size();
        vector<double> dp(target+1,0);
        dp[0]=1;
        sort(nums.begin(),nums.end());

        for(int i=1;i<=target;i++){
            for(int j=0;j<n;j++){
                if(nums[j]>i)break;
                dp[i]+=dp[i-nums[j]];
            }
        }
        return dp[target];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Released under the MIT License.