niiish32x 's blog

原题链接:https://leetcode.cn/problems/count-special-integers/ 数位dp 虽然只要是枚举的过程 但需要考虑的情况比较多 且融合非常多的知识点 非常细致主要需要注意以下几个点： 枚举过的数 不能再枚举 可以用一个vis数组 但为了方便可以用二进制的方法 采用一个mask 进行解决 每个位置枚举的数 会受到前一个位置的限制 比如说 n=123 那么如果 当前已经枚举的情况位 12_ 那么最后一位只能枚举1 2 3 否则就会超过123 那么生成的数 就不符合答案标准了 如果前一个数位为0 那么当前位置枚举数可能会存在重复 比如说 9 09 009 则三个数都会出现重复 需要这种特殊情况进行判读那 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758class Solution: def countSpecialNumbers(self, n: i ...

循环队列概念很早接触了 但在细节方面一直有些迷糊正好今天的每日一题是循环队列 总结了一下关键以下两点:1.对于front 和 rear的定义要明确 ​ font指向的是队头有效元素的位置 而rear则指向的是队尾下一个有效元素的位置 这就导致一些差异 ​ 最主要的就是进行队尾插入时 要先进行赋值 q[rear] = value 而后移动rear 指针 因为根据rear指针的定义之前rear指针所指向的位置 正是此时元素应该插入的有效位置 ​ 然后根据rear 定义 那么返回队尾元素时 返回应该时rear-1这个位置的元素 而并非rear2.空出一个有效位置作为哨兵 主要是为了区分队空和队满两种状态 ​ 这和rear指针的定义是紧密关联的 ​ 当 (rear + 1 % capacity) == front 代表 此时队列已满 可以这样理解 rear 代表下一个元素的有效位置 即下一个元素的有效位置已经是front了那么这样就代表队满了 ​ 同时根据上述定义 真正队满是 front != rear 所以队空的情况只能是 front = ...

原题链接https://leetcode.cn/problems/maximum-xor-after-operations/非常巧妙的一道题 123456789101112131415161718192021/** * 首先这个任意的非负x 不需要是在数组内出现的 就是一个任意数 * nums[i] and (nums[i] xor x) * 则 x 可以选一个 x 的二进制为 1 的位置 而 nums[i] 为0 x的二进制位置为0 nums[i]为0 的数 (即起到保留x所有的1的效果) * 则可将 nums[i] xor x 化简为 x * 从而得到 原式 = nums[i] and x = x * 最终答案求 MaxSum(nums[0..n]) xor x * 最终求的结果中1 越多则其值就越大 即在异或运算的过程中 尽可能多的 留1 * 即 只要 nums[0..n] 中 一位 有1 不管是奇数还是偶数 都可以 使用x进行调整从而将1 保留 (偶数 则 x 在这位取1 否则取0) * 从而演变为 nums[0..n] 的 或运算 (因为或运算只要有 ...

基本上任何情况都可以使用这种方法存N = 1e5 的时候就一定要这么存了N = 1e3 左右可以偷懒一下 使用邻接矩阵来存、 模板: 12345678910111213141516171819202122232425262728const int N = 1e5 + 10;int h[N]; //存储表头int e[N], ne[N], idx; //邻接表的基本参值//将b插入a后void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx, idx++;}//然后要注意初始化和遍历的问题/** 总的来说就是把 头节点 h[] 全部初始化为-1 用什么方法都行 C++的话 用memset会快一些 其他语言直接遍历一遍就行了*/memset(h,-1,sizeof h);/** 遍历*/// u 为初始遍历的点for(int i=h[u] ; i!=-1 ;i = ne[i]){ // 取出链表中存在的值 通常为节点值 int j = e[i] ...

组合数基础定理 基本公式 : C(n,r) = n! / r!(n-r)! (从n中选r个的方案) 123456789def C(n,m): """ 从n个球中 选取m个球的方案数 """ res = 1 for i in range(m): res = res * (n - i) res = res // (i + 1) return res 递推公式 : C(m,n) = C(m-1,n) + C(m-1,n-1)如果只在求答案的时候用的话 就用第一条就可以了但如果需要大量计算组合数 则需要对组合数进行预处理 因为求组合数事实上是在求阶乘 还是比较慢这个时候需要用到 递推公式 组合数预处理(递推法)这种情况N = 1000 左右 123456789// c[a][b] 表示从a个苹果中选b个的方案数for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ) // 从i ...