2025-08-16 学习日记

今日学习记录

1. 下一个特殊回文数leetcode.3646来源 462 周赛

关键词：回溯 问题分析：

1. 这道题如果正常做很简单,但是这是个困难题,所有肯定不能正常做,比赛时两三下就做出来了,但是超时了,也不知道怎么改进了
2. 比 n 大的回文数,数字中每个数字 k 恰好出现 k 次

核心思路

1. 不能枚举每个比 n 大的数,再检验该数是否满足条件,数太多了,要一个个检验浪费时间,条件太苛刻,符合条件的数应该很少,所以直接去构造符合条件的数看是否大于 n
2. 根据回文的特殊性,肯定是只考虑一半,

最终代码：

学到的点： 1.

2. 6 和 9 组成的最大数字leetcode.1323

关键词：数学 问题分析：

1. 简单,就是把从左数第一个 6 变成 9

核心思路 1.简单

最终代码：

int maximum69Number (int num) {

        int max_base = 0;

        int base = 1;

        for (int x = num; x > 0; x /= 10) {

            if (x % 10 == 6) {

                max_base = base;

            }

            base *= 10;

        }

        return num + max_base * 3;

    }

学到的点：

1. 简单

3. 执行操作后不同元素的最大数量leetcode.3397

关键词：贪心 问题分析：

1. 给定一个数组和一个 k,可对数组中的任意元素进行一次加[-k,k]范围内整数的操作,使数组中拥有不同元素的最大数量

核心思路

1. 看到这个范围应该很熟悉,之前做过相关的题目,就是把每个数字变成加上-k 和 k 的区间,再区间内重合的就是进行加减后重复的元素,我们要使其尽可能不重复,老规矩先排序
2. 排序后,a<b 我们要探查规律,无疑就是 a-k 和 b-k 的大小关系,b-k>a-k,就直接取 b-k,如果相等就取 a-k+1,即 max(b-k,a-k+1),但是这个值一定不能超过 b+k,所以 min(max(b-k,a-k+1),b+k),a 是上一个元素,就是看 a-k+1 是否落在 b-k,b+k 这个区间上
3. 特判,当可修改 k 的范围超过了整个数组,那么所有数都可以改成不一样的,直接返回数组长度

最终代码：

int maxDistinctElements(vector<int>& nums, int k) {

        int n = nums.size();

        if(2*k+1>=n) return n;

        ranges::sort(nums);

        int pre = INT_MIN;

        int ans = 0;

        for(int x:nums){

            x = min(max(pre+1,x-k),x+k);

            if(x>pre){

                ans++;

                pre = x;

            }

        }

        return ans;

    }

学到的点：

1. 复习老东西
2. 如何推理公式

今日收获

1. 新技巧

2. 待加强

3. 明日计划：

   • [ ]
   • [ ]