303. 区域和检索 - 数组不可变

愣是没看明白这个输入该咋处理
然后发现不用处理
…

class NumArray {
public:vector num;NumArray(vector& nums) {num=nums;}int sumRange(int left, int right) {int sum=0;for(int i=left;i<=right;i++)sum+=num[i];return sum;}
};

毫无闪光点的直白做法
这道题当然不是考察这个的
而是考察动态规划问题
在初始化对象时就可以计算前缀和sum，这样只要计算sum[right]-sum[left]就可以了

class NumArray {
public:vector sum;NumArray(vector& nums) {sum.resize(nums.size()+1);sum[0]=0;for(int i=1;isum[i]=sum[i-1]+nums[i-1];}}int sumRange(int left, int right) {return sum[right+1]-sum[left];}
};

主要是要处理好游标的问题，前缀和游标的含义是前项的和，从前0个和到前n个和，那么数组总的长度是n+1，和原始数组不一样
原来整型vector数组要加sum.resize(n)才能让sum[0]=0
否则就会报错
runtime error: reference binding to null pointer of type ‘int’
评论区大佬给出了另一个方法：懒计算

class NumArray {
private:vector sumArr;int count = 0;
public:NumArray(vector& nums) {sumArr = nums;}int sumRange(int i, int j) {if(count <= j){while(count <= j){sumArr[count] = sumArr[count] + (count > 0? sumArr[count - 1] : 0);++count;}}return sumArr[j] - (i > 0? sumArr[i - 1] : 0);}
};

326. 3 的幂

231题是2的幂

class Solution {
public:bool isPowerOfThree(int n) {if(n==0)return false;while(n%3==0)n/=3;if(n!=1)return false;return true;}
};

要求不用循环不用递归
这就需要用到数论的知识了。由于3²⁰ 超过了 int 的范围了，所以 3¹⁹ 次方就是 int 类型中最大的值。
只需要判断 n 是否是 3¹⁹ 的约数即可。
但也需要判断n是否为负数的情况

class Solution {
public:bool isPowerOfThree(int n) {return n > 0 && 1162261467 % n == 0;}
};

338. 比特位计数

总觉得这道题似曾相识
评论区大佬的讲解：

分奇数和偶数：

偶数的二进制1个数超级简单，因为偶数是相当于被某个更小的数乘2，乘2怎么来的？在二进制运算中，就是左移一位，也就是在低位多加1个0，那样就说明dp[i] = dp[i / 2]
奇数稍微难想到一点，奇数由不大于该数的偶数+1得到，偶数+1在二进制位上会发生什么？会在低位多加1个1，那样就说明dp[i] = dp[i-1] + 1，当然也可以写成dp[i] = dp[i / 2] + 1

代码可写为

class Solution {
public:vector countBits(int num) {int i = 1;vector ans(num + 1);for (int i = 0; i <= num; i++) {if (i % 2 == 0) ans[i] = ans[i / 2];else ans[i] = ans[i / 2] + 1;}return ans;}
};

也是一道动态规划题