303. Range Sum Query - Immutable
很简单
typedef struct {
int *pArr;
// int size; // 这个题不需要这个字段
} NumArray;
NumArray *numArrayCreate(int *nums, int numsSize) {
NumArray *obj = malloc(sizeof(NumArray));
obj->pArr = malloc(sizeof(int) * (numsSize + 1));
obj->pArr[0] = 0;
for (int i = 0; i < numsSize; i++) {
obj->pArr[i + 1] = (obj->pArr[i] + nums[i]);
}
return obj;
}
int numArraySumRange(NumArray *obj, int left, int right) {
return obj->pArr[right+1] - obj->pArr[left];
}
void numArrayFree(NumArray *obj) {
free(obj->pArr);
free(obj);
}
326. Power of Three
直观能想到，直接计算一遍
bool isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
while (n) {
if (n == 1) {
return true;
}
if (n % 3) {
return false;
}
n /= 3;
}
return true;
}
！符合条件的数字，一定是 $3^19 = 1162261467$ 的因数
bool isPowerOfThree(int n) {
return n > 0 && !(1162261467 % n);
}
338. Counting Bits
int *countBits(int n, int *returnSize) {
*returnSize = n + 1;
int *res = malloc(sizeof(int) * (n + 1));
res[0] = 0;
for (int i = 1; i < n + 1; i++) {
res[i] = res[i >> 1] + (i & 1); // 注意，这个运算优先级坑爹
}
return res;
}
342. Power of Four
与 326. Power of Three 一模一样，只不过除法可以换成移位
bool isPowerOfFour(int n) {
if (n <= 0) {
return false;
}
while (n) {
if (n == 1) {
return true;
}
if (n & 3) {
return false;
}
n >>= 2;
}
return true;
}
也可以向左移位。看是否为 1073741824 （不过leetcode向左移位溢出后报错，而不是归零）
不能像 326 一样，看看是否被 1073741824 整除，因为 4 是一个合数
从位运算角度
- 必需只能有一个 1，其余都是0。等价于必须是 2 的次幂，也就是
(n & (n - 1)) == 0 - 保证这个唯一的 1，出现在偶数位上。可以借 $mask=(10101010101010101010101010101010)_2$ 的 按位与来判断
bool isPowerOfFour(int n) {
return n > 0 && ((n & (n - 1)) == 0) && ((n & 0xAAAAAAAA) == 0);
}
344. Reverse String
简单
void reverseString(char *s, int sSize) {
char tmp;
for (int i = 0, j = sSize - 1; i < j; i++, j--) {
tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
345. Reverse Vowels of a String
可以把 isVowel 换成 宏（也快不了多少）
bool isVowel(char c) {
return ((c == 'a') || (c == 'e') || (c == 'i') || (c == 'o') || (c == 'u')
|| (c == 'A') || (c == 'E') || (c == 'I') || (c == 'O') || (c == 'U'));
}
char *reverseVowels(char *s) {
char tmp;
for (int i = 0, j = strlen(s) - 1; i < j;) {
if (isVowel(s[i])) {
if (isVowel(s[j])) {
tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
} else {
j--;
}
} else {
i++;
}
}
return s;
}
492. Construct the Rectangle
C有个好处，就是for循环时，结束条件动态调整很方便，w取到i的时候，应当知道 area/i 之后的数字就没有计算的必要了
https://leetcode.cn/problems/construct-the-rectangle/solution/cyu-yan-ji-bai-100-by-guofei9987-tvq6/
1605. Find Valid Matrix Given Row and Column Sums
这个题是练习指针的 https://leetcode.cn/problems/find-valid-matrix-given-row-and-column-sums/solution/cyu-yan-by-guofei9987-j16t/
1615. Maximal Network Rank
2383. Minimum Hours of Training to Win a Competition
简单
int minNumberOfHours(int initialEnergy, int initialExperience, int *energy, int energySize, int *experience,
int experienceSize) {
int res = 0;
for (int i = 0; i < energySize; i++) {
if (initialEnergy <= energy[i]) {
res += (energy[i] - initialEnergy + 1);
initialEnergy = 1;
} else {
initialEnergy -= energy[i];
}
}
for (int i = 0; i < experienceSize; i++) {
if (initialExperience <= experience[i]) {
res += (experience[i] - initialExperience + 1);
initialExperience = (2*experience[i] + 1);
} else {
initialExperience += experience[i];
}
}
return res;
}
- Longest Subsequence With Limited Sum
还可以改进到二分法，没做
int cmp_int(const void *e1, const void *e2) {
return *(int *) e1 - *(int *) e2;
}
int find_one(const int *cumsum, int numsSize, int query) {
if (cumsum[0] > query) {
return 0;
}
for (int i = 0; i < numsSize - 1; i++) {
if (cumsum[i] <= query && cumsum[i + 1] > query) {
return i + 1;
}
}
return numsSize;
}
int *answerQueries(int *nums, int numsSize, int *queries, int queriesSize, int *returnSize) {
int *res = malloc(queriesSize * sizeof(int));
*returnSize = queriesSize;
qsort(nums, numsSize, sizeof(int), cmp_int);
// cumsum
for (int i = 1; i < numsSize; i++) {
nums[i] += nums[i - 1];
}
for (int j = 0; j < queriesSize; j++) {
res[j] = find_one(nums, numsSize, queries[j]);
}
return res;
}
