394. 字符串解码

题解

count栈存储次数，stackString存储之前的字符串，遍历字符串
数字：累加构建重复次数 k
[：将当前重复次数和当前积累的字符串分别压入对应栈中，然后重置计数器和当前字符串
]：从栈中弹出重复次数和之前积累的字符串，将当前字符串重复指定次数，然后拼接到之前的字符串后面
字母：直接添加到当前字符串

代码

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
class Solution {
public:
    string decodeString(string s) {
        stack<int>count;
        stack<string>strackString;
        string current;
        int k=0;
        for(char c:s){
            if(isdigit(c)){
                k=k*10+(c-'0');
            }else if(c=='['){
                count.push(k);
                strackString.push(current);
                k=0;
                current.clear();
            }else if(c==']'){
                int repCount=count.top();
                count.pop();
                string prevString=strackString.top();
                strackString.pop();
                string temp=current;
                current=prevString;
                for(int i=0;i<repCount;i++){
                    current+=temp;
                }
            }else{
                current+=c;
            }
        }
        return current;
    }
};

739. 每日温度

date:2025-3-12

题解

用栈存放天数的索引，遍历temperatures，温度大于栈顶索引的温度时，找到了栈顶元素的下一个更高温度。然后计算天数差
否则将索引加入到栈中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int>sta;
        int n=temperatures.size();
        vector<int>result(n,0);
        for(int i=0;i<n;i++){
            while(!sta.empty()&&temperatures[i]>temperatures[sta.top()]){
                int prevDay=sta.top();
                sta.pop();
                result[prevDay]=i-prevDay;
            }
            sta.push(i);
        }
        return result;
    }
};

55. 跳跃游戏

date:2025-3-12

题解

用maxReach代表能够到达的最远位置，每次遍历nums,更新maxReach,提前大于nums大小时，返回true;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach=0;
        for(int i=0;i<nums.size();i++){
            if(maxReach<i)return false;
            maxReach=max(maxReach,i+nums[i]);
            if(maxReach>nums.size()-1){
                return true;
            }
        }
        return true;
    }
};

283. 移动零

date:2025-3-15

题解

用m来代表非0元素的位置并修改。m之后的元素都为0.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int m=0,n=nums.size();
        for(int i=0;i<n;i++){
            if(nums[i]!=0){
                nums[m]=nums[i];
                m++;
            }
        }
        for(int j=m;j<n;j++){
            nums[j]=0;
        }
    }
};
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
#include<iostream>
#include<vector>
using namespace std;
moveZeroes(vector<int>&nums);
int main(){
    int n;
    cin>>n;
    vector<int>nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    moveZeroes(nums);
    for(int i=0;i<n;i++){
        if(i==n-1){
            cout<<nums[i]<<endl;
        }else{
            cout<<nums[i]<<',';
        }
    }
}
void moveZeroes(vector<int>& nums) {
    int m = 0, n = nums.size();
    for (int i = 0; i < n; i++) {
        if (nums[i] != 0) {
            nums[m] = nums[i];
            m++;
        }
    }
    for (int j = m; j < n; j++) {
        nums[j] = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
func moveZeroes(nums []int)  {
    left,right,n:=0,0,len(nums)
    for right<n{
        if nums[right]!=0{
            nums[left],nums[right]=nums[right],nums[left]
            left++
        }
        right++
    }
}

11. 盛最多水的容器

date:2025-3-15

题解

用result存储最大的水量，left和right分别指向0和尾部，当未相遇时，比较left和right位置的高度，移动小的线。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1,result=0;
        while(left<right){
            if(height[left]<height[right]){
                result=max(result,(right-left)*height[left]);
                left++;
            }else{
                result=max(result,(right-left)*height[right]);
                right--;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxArea(height []int) int {
    left,right,result:=0,len(height)-1,0
    for left<right{
        if height[left]<height[right]{
            result=max(result,(right-left)*(height[left]))
            left++
        }else{
            result=max(result,(right-left)*(height[right]))
            right--
        }
    }
    return result
}
func max(a,b int)int{
    if a>b{
        return a
    }else{
        return b
    }
}

3. 无重复字符的最长子串

date:2025-3-16

题解

用哈希表存放字符的下表，维护一个滑动窗口，left和right，
遇到重复字符，将left移动到重复字符的下一个位置，没遇到就right右移。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.length();
        unordered_map<char,int>char_index;
        int res=0,left=0;
        for(int right=0;right<n;right++){
            if(char_index.find(s[right])!=char_index.end()&&char_index[s[right]]>=left){
                left=char_index[s[right]]+1;
            }
            res=max(res,right-left+1);
            char_index[s[right]]=right;
        }
        return res;
    }
};

438. 找到字符串中所有字母异位词

date:2025-3-16

题解

用哈希表加滑动窗口解题，字符-‘a’转化为int型，初始化哈希表并判断此时是否相等。
遍历字符串，右边界增加字符计数，左边界减少字符计数，再进行判断。

代码

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
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int s_len=s.length(),p_len=p.length();
        vector<int>count_p(26,0);
        vector<int>window(26,0);
        vector<int>result;
        if(s_len<p_len){
            return {};
        }
        for(char c:p){
            count_p[c-'a']++;
        }
        for(int i=0;i<p_len;i++){
            window[s[i]-'a']++;
        }
        if(count_p==window){
            result.push_back(0);
        }
        for(int i=p_len;i<s_len;i++){
            window[s[i]-'a']++;
            window[s[i-p_len]-'a']--;
            if(count_p==window){
                result.push_back(i-p_len+1);
            }
        }
        return result;
    }
};