Hexo

2024

February

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int pos = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != val) nums[pos++] = nums[i];
        }
        return pos;
    }
};

March

1090

由于题目中的 $\textit{values}$ 和 $\textit{labels}$ 是分成两个数组给出的，直接排序会比较困难。我们可以额外开辟一个同样长度为 $n$ 的数组，存储下标，并直接在该数组上进行排序即可。

int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
    int n = values.size();
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j) {
        return values[i] > values[j];
    });
    ...
}

April

2810 故障键盘

1. 使用双端队列进行模拟

   class Solution {
   public:
       string finalString(string s) {
           deque<char> q;
           bool head = false;
           for (char ch: s) {
               if (ch != 'i') {
                   if (head) {
                       q.push_front(ch);
                   }
                   else {
                       q.push_back(ch);
                   }
               }
               else {
                   head = !head;
               }
           }
           string ans = head ? string{q.rbegin(), q.rend()} : string{q.begin(), q.end()};
           return ans;
       }
   };

2020

October

0005 最长回文子串

解法一：动态规划

string longestPalindrome(string s) {
    int n = s.size();
    if(n < 2) return s;
    int maxLen = 1;
    int begin = 0;
    vector<vector<int>> dp(n, vector<int>(n));
    for(int i=0; i<n; i++) {
    	dp[i][i]=true;
    }
    for(int L=2; L<=n; L++) { // 枚举字串长度
        for(int i=0; i<n; i++) {
            int j = L+i-1;
            if(j >= n) break;
            if(s[i] != s[j]) dp[i][j] = false;
            else {
                if(j-i < 3) dp[i][j] = true;
                else dp[i][j] = dp[i+1][j-1];
            }
            if(dp[i][j] && j-i+1>maxLen) {
                maxLen = j-i+1;
                begin = i;
            }
        }
    }
    return s.substr(begin, manLen);
}

解法二：中心拓展算法

0011 盛最多水的容器

没有优化的两层 for 循环：TLE

解法一：双指针法【移动两边的指针，以找到最优解】

0015 三数之和

解法一：排序 + 双指针

• 失败的做法：试图同时移动两个指针；
• 正确的做法：先确定一个元素的位置，然后移动两个指针；

0045 跳跃游戏

贪心算法：通过局部最优解得到全局最优解

解法一：反向查找出发位置（时间复杂度较高）

// 此处使用 C++ 会 TLE
public int jump(int[] nums) {
    int position = nums.length()-1;
    int steps = 0;
    while(position > 0) {
        for(int i=0; i<position; i++) {
            if(i+nums[i] >= position) {
                position = i;
                steps++;
                break;
            }
        }
    }
    return steps;
}

解法二：正向查找可达到的最大位置

1419 数青蛙

记录每只青蛙叫到哪里（c r o a k）
遇到 c 时，判断是否有青蛙空闲（k），否则添加新的青蛙