5253. 找到指定长度的回文数（周赛）

  • 只需要考虑前面一半。后面使用字符串拼接即可

  • 怎么计算多少个最大的回文数呢？最大位加1，总体减1即可。因为前导不能是0，因此最大位+1，而idx是从1开始的，因此减1

    1. class Solution {
    2. public:
    3.   vector<long long> kthPalindrome(vector<int>& queries, int intLength) {
    4.       vector<long long> res;
    5.       int n = queries.size();
    6.       int intLength1 = intLength%2==0? intLength/2:intLength/2+1;//最大位+1，总体减1
    7.       for(int i = 0; i < n; i++) {
    8.           long long idx = queries[i];
    9.           long long val = idx+pow(10,intLength1-1)-1;
    10.           if(val > pow(10,intLength1)-1) {//判断是否超范围
    11.               res.push_back(-1);
    12.               continue;
    13.           }
    14.           string str = to_string(val);
    15.           if(intLength%2==0) {
    16.               string str1 = str;
    17.               reverse(str1.begin(), str1.end());
    18.               str = str+str1;
    19.           } else {
    20.               string str1 = str.substr(0, str.size()-1);
    21.               reverse(str1.begin(), str1.end());
    22.               str = str+str1;
    23.           }//处理
    24.           val = stol(str);
    25.           res.push_back(val);
    26.       }
    27.       return res;
    28.   }
    29. };

    5236. 美化数组的最少删除数（周赛）

  • 这题使用栈来写的

  • 使用栈来模拟更新之后的数组

  • 奇数要摘除栈顶

    1. class Solution {
    2. public:
    3.   int minDeletion(vector<int>& nums) {
    4.       int n = nums.size();
    5.       stack<int> stk;
    6.       stk.push(nums[0]);
    7.       for(int i = 1; i < n; i++){
    8.           int num = stk.top();
    9.           if(stk.size()%2==0||num!=nums[i]) {
    10.               stk.push(nums[i]);
    11.           } 
    12.       }
    13.       return stk.size()%2==0? n-stk.size():n-stk.size()+1; 
    14.   }
    15. };

    954. 二倍数对数组

    是用哈希表来查找是否有为两倍的数，问题在于要一一对应上。

  • 不能一开始就设定好，必须要边找边查。

    1. class Solution {
    2. public:
    3.   bool canReorderDoubled(vector<int> &arr) {
    4.       unordered_map<int, int> cnt;
    5.       for (int x : arr) {
    6.           ++cnt[x];
    7.       }
    8.       if (cnt[0] % 2) {
    9.           return false;
    10.       }
    12.       vector<int> vals;
    13.       vals.reserve(cnt.size());//vals重置为哈希表的长度
    14.       for (auto &[x, _] : cnt) {
    15.           vals.push_back(x);
    16.       }
    17.       sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });//根据绝对值进行排序
    19.       for (int x : vals) {
    20.           if (cnt[2 * x] < cnt[x]) { // 无法找到足够的 2x 与 x 配对
    21.               return false;
    22.           }
    23.           cnt[2 * x] -= cnt[x];
    24.       }
    25.       return true;
    26.   }
    27. };

    区间问题

    699. 掉落的方块（hard）

  • 判断两个区间[l1, r1]，[l2, r2]是否相交

  • r1 >= l2&& r2>=l1

    1. class Solution {
    2. public:
    3.   vector<int> fallingSquares(vector<vector<int>>& positions) {
    4.       int n = positions.size();
    5.       vector<int> heights(n);//heights[i]实际上就是当前范围（i）内的最大高度
    6.       for (int i = 0; i < n; i++) {
    7.           int left1 = positions[i][0], right1 = positions[i][0] + positions[i][1] - 1;
    8.           heights[i] = positions[i][1];//边长
    9.           for (int j = 0; j < i; j++) {//暴力枚举之前的所有方块
    10.               int left2 = positions[j][0], right2 = positions[j][0] + positions[j][1] - 1;//左边起点到右边起点
    11.               if (right1 >= left2 && right2 >= left1) {//情况重叠，注意这里的写法非常重要，这种写法包含了所有的情况。
    12.                   heights[i] = max(heights[i], heights[j] + positions[i][1]);
    13.               }
    14.           }
    15.       }
    16.       for (int i = 1; i < n; i++) {
    17.           heights[i] = max(heights[i], heights[i - 1]);//前面可能出现比当前还高的情况。
    18.       }
    19.       return heights;
    20.   }
    21. };

    54. 螺旋矩阵(重点题目)

    怎么旋转的必须要记住！！！！

    1.       int left=0;
    2.       int right=(matrix[0].size()-1);
    3.       int top=0;
    4.       int bottom=(matrix.size()-1);
    5.       while(right>=left&&bottom>=top){
    6.           for(int i=left;i<=right;i++){
    7.               matrix[left][i] = head->val;
    8.               head = head->next;
    9.               if(!head) return matrix;
    10.           }
    12.           for(int i=(top+1);i<=bottom;i++){
    13.               matrix[i][right] = head->val;
    14.               head = head->next;
    15.               if(!head) return matrix;
    16.           }
    18.            if(right>left&&bottom>top){
    19.           for(int i=(right-1);i>=left;i--){
    20.               matrix[bottom][i] = head->val;
    21.               head = head->next;
    22.               if(!head) return matrix;
    23.           }
    25.           for(int i=(bottom-1);i>top;i--){
    26.               matrix[i][left] = head->val;
    27.               head = head->next;
    28.               if(!head) return matrix;
    29.           }
    30.           }
    31.           left++;
    32.           top++;
    33.           right--;
    34.           bottom--;
    35.       }