目录

• —、第一题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 二、第二题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 三、第三题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 四、第四题
• • 1. 原题链接
  • 2. 解题思路
  • 3. 代码
• 五、星球推荐

坚持每一天，提升自己，坚持刷题！！！

—、第一题

1. 原题链接

        原题链接：1480. 一维数组的动态和

        给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

        请返回 nums 的动态和。

2. 解题思路

        前缀和，nums[i]值依次累加赋给新建数组。

3. 代码

int* runningSum(int* nums, int numsSize, int* returnSize){   int lend = 0;   int * ans = malloc(sizeof(int) * numsSize);   for(int i = 0; i < numsSize; ++i){lend += nums[i];ans[i] = lend;   }   * returnSize = numsSize;   return ans;}

二、第二题

1. 原题链接

        原题链接：1588. 所有奇数长度子数组的和

        给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

        子数组 定义为原数组中的一个连续子序列。

        请你返回 arr 中 所有奇数长度子数组的和 。

2. 解题思路

        使用前缀和作差得出奇数项子数组和，并进行累加

3. 代码

int sumOddLengthSubarrays(int* arr, int arrSize){   int i, j;   int sum = 0;   for(i = 1; i < arrSize; ++i){arr[i] += arr[i-1];   }   for(i = 0; i < arrSize; i += 2){sum += arr[i];   }   for(i = 0; i < arrSize; ++i){for(j = 1; i+j < arrSize; j +=2){    sum += arr[i+j] - arr[i];}   }   return sum;}

解法二：滑动窗口 ，使用滑动窗口对奇数项3、5、7、9....对每个窗口的值进行累加。

int prefix(int* arr, int n, int m){   int i;   int ret = 0;   for(i = n; i < m; ++i){ret += arr[i];   }   return ret;}int sumOddLengthSubarrays(int* arr, int arrSize){   int i;   int flag = 3;   int n = 0, m = 0;   int ret = 0;   for(i = 0; i < arrSize; ++i)ret += arr[i];   m = flag;   while(flag <= arrSize){n = 0;while(m <= arrSize){    ret += prefix(arr, n, m);    ++n;    ++m;}m = (flag += 2);   }   return ret;}

三、第三题

1. 原题链接

        原题链接：1442. 形成两个异或相等数组的三元组数目

        给你一个整数数组 arr 。

        现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。

        a 和 b 定义如下：

        a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
        b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
        注意：^ 表示 按位异或 操作。

        请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

2. 解题思路

        由a == b得出a ^ b == 0，既arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]^arr[j] ^ arr[j + 1] ^ … ^ arr[k] == 0。当上式成立时，[i + 1 : k] 的范围内的任意 j 都是符合要求的，对应的三元组个数为 k - i。因此我们只需枚举下标 i 和 k。

3. 代码

int countTriplets(int* arr, int arrSize){   int i, k;   int ret;   int ans = 0;   for(i = 0; i < arrSize; ++i){ret = arr[i];for(k = i+1; k < arrSize; ++k){    ret ^= arr[k];    if(ret == 0) ans += k-i;}   }   return ans;}

四、第四题

1. 原题链接

        原题链接：1094. 拼车

        车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

        给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

        当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

2. 解题思路

        把上车和下车的位置进行线性标记并记录上下车人数。前缀和，遍历数组统计上下车人数当大于给定座位返回false，否则返回true。

3. 代码

bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity){   int station[1001] = {0};   int i;   int sum = 0;   for(i = 0; i < tripsSize; ++i){int numPassengersi = trips[i][0];int fromi = trips[i][1];int toi = trips[i][2];station[fromi] += numPassengersi;station[toi] -= numPassengersi;   }   for(i = 0; i < 1001; ++i){sum += station[i];if(sum > capacity) return false;   }   return true;}

五、星球推荐

        星球链接：英雄算法联盟

星球里有什么?
        【朋友圈】一个极致精准的自律、编程、算法的小圈子。
        【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
        【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
        【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
        【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
        目前星球人数达到310+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。