Leetcode刷题笔记15
724. 寻找数组的中心下标
解法一：暴力解法
解法二：前缀和
1.
dp[i] = dp[i-1] + arr[i]
dp[i] -> 0到i位置所有元素的和
dp[i-1] -> 0到i-1所有元素的和
arr[i] -> 当前位置的元素
f表示前缀和数组：
f[i]表示：[0,i-1]区间，所有元素的和
f[i-1]表示[0,i-2]区间，所有元素的和
f[i] = f[i-1] + nums[i-1]
g表示后缀和数组：
g[i]表示：[i+1,n-1]区间，所有元素的和
g[i] = g[i+1] + nums[i+1]
2.
0~n-1：枚举所有元素的中心下标
然后判断是否相等：f[i] == g[i]
3. 细节问题
处理越界：
f[0] = 0
g[n-1] = 0
填表顺序：
f: 从左向右
g: 从右向左
代码：C++
class Solution {
public:
int pivotIndex(vector<int>& nums)
{
int n = nums.size();
vector<int> f(n), g(n); // 大小为n
// 1. 预处理前缀和和后缀和数组
for(int i=1; i<n; i++)
{
f[i] = f[i-1] + nums[i-1];
}
for(int i=n-2; i>=0; i--)
{
g[i] = g[i+1] + nums[i+1];
}
// 2. 使用
// 枚举所有下标
for(int i=0; i<n; i++)
{
if(f[i] == g[i]) // 找到中心下标
{
return i;
}
}
return -1; // 没有中心下标
}
};238. 除自身以外数组的乘积
238. 除自身以外数组的乘积 - 力扣（LeetCode）
解法一：暴力解法 -> 枚举
时间复杂度：O(N^2)
不能用双指针来做优化（存在0和负数）
解法二：前缀和 + 哈希表
以i位置为结尾的所有子数组
本质上就是：在[0,i-1]区间内，有多少个前缀和等于 sum[i] - k
哈希表：<int,int>
第一个int存前缀和，第二个int存前缀和出现的次数
细节问题：
1. 前缀和加入哈希表的时机？
在计算i位置之前，哈希表里面只保存[0,i-1]位置的前缀和
2. 不用真的创建一个前缀和数组
用一个变量sum，来标记前一个位置的前缀和即可
3. 如果整个前缀和等于k呢？
先把hash[0] = 1 丢到哈希表里面，相当于默认有一个前缀和等于0
代码：C++
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums)
{
int n = nums.size();
vector<int> f(n), g(n); // 不需要考虑溢出
// 1. 预处理
f[0] = g[n - 1] = 1; // 细节问题
for (int i = 1; i < n; i++)
{
f[i] = f[i - 1] * nums[i - 1];
}
for (int i = n - 2; i >= 0; i--)
{
g[i] = g[i + 1] * nums[i + 1];
}
// 2. 使用
vector<int> ret(n);
for (int i = 0; i < n; i++)
{
ret[i] = f[i] * g[i];
}
return ret;
}
};974. 和可被 K 整除的子数组
974. 和可被 K 整除的子数组 - 力扣（LeetCode）
解法一：暴力枚举
补充知识：
1. 同余定理
(a-b) / p = k ... 0，如果a-b的差能被p整除，那么 a%p = b%p。
比如
(26 - 12) / 7 = 2 -> 26 % 7 = 12 % 7 = 5
(1 + 2*3) % 2 = 1
(a + p*k) % p = a % p
2. c++ [负数 % 正数] 的结果以及修正
负数取模：
负 % 正 = 负 --> 修正：a % p + p --> 正负统一: (a%p + p) % p
解法二：前缀和 + 哈希表
在[0,i-1]区间内，找到有多少个前缀和的余数等于 (sum % k + k) % k
哈希表<int,int>
第一个int表示前缀和余数，第二个int表示出现的次数
代码：C++
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k)
{
unordered_map<int,int> hash;
hash[0 % k] = 1; // 存的是0这个数的余数
int sum = 0, ret = 0;
for(auto x : nums)
{
sum += x; // 算出当前位置的前缀和
int r = (sum % k + k) % k; // 修正后的余数
if(hash.count(r))
{
ret += hash[r]; // 统计结果
}
hash[r]++;
}
return ret;
}
};原文地址：https://blog.csdn.net/weixin_54634208/article/details/144017098
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！