2025-08-14 学习日记

今日学习记录

1. 判断一个数字是否可以表示成三的幂的和leetcode.1780

关键词：数学 预处理 问题分析：

1. 就是看一个数能不能拆成不同的三的幂之和,跟这题相像,只是底数变为 3 了 2025-08-11,但不同在这题看是否能
   • 列如: $\ 12 = 3^1+3^2$

核心思路

1. 一样,先找到指数然后就会发现如果按照我之前的做法也超时,因为数太大了,所以我想到了预处理,先求出所有在范围内的 3 的幂,然后就过了,毕竟查询很快,所以 0ms,打败 100%

vector<int> arr;
int init = []{
    for(int i = 1;i<=10000000;i*=3){
        arr.push_back(i);
    }
    return 1;
}();
class Solution {
public:
    bool checkPowersOfThree(int n) {
        for(int i = arr.size()-1;i>=0;i--){
            if(n>=arr[i]) n -= arr[i];
        }
        return n==0;
    }
};

2. 背包问题,还是选或不选,然后我就用了这题的模板 2025-08-12,只要方案数不为 0,就是 true,结果超时间限制了,毕竟只是要求存不存在,这样做有太多不必要的遍历了,所以不是最佳选择
3. 来看看灵神的三进制分解,其实就跟平时暴力递归验证 2 的幂一样,只不过对于 3 而言,3 在递归到底时有两个数,1 和 2,(无论任何数对 3 取余都得到 0,1,2),1 是 3 的 0 次幂,2 就是最后无法再除 3 的时候

while(n){
            if(n%3==2) return false;
            n /= 3;
        }
        return true;

学到的点：

1. 三进制分解

2. 排序排列leetcode.3644 来源 462 周赛

关键词：位运算 脑筋急转弯 问题分析：

1. 给了一个数组,数组内只包含有 0 到 n-1 的元素,乱序,交换数组内元素使数组按递增顺序
2. 记录每次交换元素的按位与的值 k,k 是唯一的,每次交换的元素按位与的值都为 k
3. 找到最大的 k

核心思路

1. 初见只知道找最大,结果还要保证每次按位与得到的值都为 k,意思是交换也有不同的方案,想到了之前的那道贪心题,先找几个例子思考一下怎么直接实现,或许很难思考,这个 k 其实很难找到符合条件的,所以有一个保底解,就是 k=0,任何数先与 0 交换,再与对应位子的数交换,得到的 k 都为 0
2. 这道题的关键并非寻找“最大”的 k，而是找到所有需要交换的错位元素（即 nums[i]≠i 的元素）共有的 k，那么要求所有错位元素的共同值,就涉及集合位运算,这样一来就解决了

int sortPermutation(vector<int>& nums) {
        int ans = -1;//-1的补码二进制全是1;
        for(int i = 0;i<nums.size();i++){
            if(nums[i]!=i) ans &= nums[i];
        }
        return max(ans,0);
    }

学到的点：

1. 位运算中的集合论
2. 如何找到集合中共同元素
3. 按位与就是取交集

今日收获

1. 新技巧：

   • 按位与就是取交集
   • 处理三进制分解技巧

2. 待加强：

   • 位运算理论

3. 明日计划：

   • [ ]
   • [ ]