栈 重载 C++ 队列 unordered_map 二叉搜索树 单链表 回调函数 虚函数
作者：Lew's Personal Blog 发布于：2020-6-14 17:41 Sunday
给定一个整数数组，找出总和最大的连续数列，并返回总和。
思路：
1、动态规划 状态： dp[i]表示以i结尾的最大连续子序列 状态转移： 对于当前的nums[i] 如果nums[i-1] >= 0 则 dp[i] = dp[i-1] + nums[i]; 否则 dp[i] = nums[i];
其实我们可以把nums当做dp数组，直接在原数组上面操作，这样可以省掉O(n)的空间
code
// 动态规划
int maxSubArray(vector<int>& nums) {
if(nums.size() == 0) return INT_MIN;
int maxSum = nums[0];
for(int i = 1; i < nums.size(); i++)
{
if(nums[i-1] >= 0)
nums[i] += nums[i-1];
maxSum = max(maxSum, nums[i]);
}
return maxSum;
}
时间复杂度：O(N) 空间复杂度：O(1)
2、分治
// 分治法
int maxSubArray(vector<int>& nums)
{
if(nums.size() == 0) return INT_MIN;
return divide(nums,0,nums.size()-1);
}
int divide(vector<int>& nums, int left, int right)
{
if(left == right) return nums[left];
int mid = (left + right) / 2;
// 1. 最大数列和在左边
int sumLeft = divide(nums,left,mid);
// 2. 最大数列和在右边
int sumRight = divide(nums,mid+1,right);
// 3. 最大数列和在中间
// 先求左边的最大和
int leftSum = 0,leftMaxSum = INT_MIN;
for(int i = mid; i >= left; i--)
{
leftSum += nums[i];
leftMaxSum = max(leftMaxSum,leftSum);
}
// 求右边的最大和
int rightSum = 0,rightMaxSum = INT_MIN;
for(int i = mid + 1; i <= right; i++)
{
rightSum += nums[i];
rightMaxSum = max(rightMaxSum,rightSum);
}
return max(max(sumLeft,sumRight),leftMaxSum+rightMaxSum);
}
时间复杂度：O(NlogN) 空间复杂度：O(1) 考虑函数栈开销的话就是O(N)
3、贪心算法
从前往后遍历数组 如果之前的和sum加上此时数组元素值小于此时数组元素，说明此前的sum小于0了，应该舍去，重新累积计算sum=0 然后执行sum+=nus[i] 判断下和max谁更大
class Solution {
public int maxSubArray(int[] nums) {
int max=Integer.MIN_VALUE,i=0,sum=0;
while(i<nums.length){
if(sum+nums[i]<nums[i])
sum=0;
sum+=nums[i];
max=Math.max(sum,max);
++i;
}
return max;
}
}
给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
输入：[23,2,4,6,7], k = 6 输出：True 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
1、暴力法（不考虑）
考虑所有长度大于等于 2 的子数组，我们将子数组遍历一遍求和，并判断和是否是给定整数 kk 的倍数。
public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
for (int start = 0; start < nums.length - 1; start++) {
for (int end = start + 1; end < nums.length; end++) {
int sum = 0;
for (int i = start; i <= end; i++)
sum += nums[i];
if (sum == k || (k != 0 && sum % k == 0))
return true;
}
}
return false;
}
}
复杂度分析
时间复杂度： O(n^3)O(n3) 。 3 重嵌套的 for 循环遍历数组。
空间复杂度： O(1)O(1) 。只用了常数个额外变量。
2、改进的暴力法
class Solution {
bool checkSubarraySum(vector<int> nums, int k) {
if(!nums.size())
return false;
vector<int> temp(nums.size(), 0);
temp[0] = nums[0];
for(int i = 1; i < nums.size(); ++i)
{
temp[i] = temp[i - 1] + nums[i];
}
for(int start = 0; start < nums.size() - 1; ++start)
{
for(int end = start + 1; end < nums.size(); ++end)
{
int sum = temp[end] - temp[start] + nums[start];
if((k != 0 && sum % k == 0) || sum == k)
return true;
}
}
return false;
}
};
3、使用 HashMap
在这种方法中，我们使用 HashMap 来保存到第 ii 个元素为止的累积和，但我们对这个前缀和除以 kk 取余数。原因如下：
我们遍历一遍给定的数组，记录到当前位置为止的 sum%ksum 。一旦我们找到新的 sum%ksum 的值（即在 HashMap 中没有这个值），我们就往 HashMap 中插入一条记录 (sum%k, i)(sum 。
现在，假设第 ii 个位置的 sum%ksum 的值为 remrem 。如果以 ii 为左端点的任何子数组的和是 kk 的倍数，比方说这个位置为 jj ，那么 HashMap 中第 jj 个元素保存的值为 (rem + nk)\%k(rem+n∗k)%k ，其中 nn 是某个大于 0 的整数。我们会发现 (rem + nk)\%k = rem(rem+n∗k)%k=rem ，也就是跟第 ii 个元素保存到 HashMap 中的值相同。
基于这一观察，我们得出结论：无论何时，只要 sum%ksum 的值已经被放入 HashMap 中了，代表着有两个索引 ii 和 jj ，它们之间元素的和是 kk 的整数倍。因此，只要 HashMap 中有相同的 sum%ksum%k ，我们就可以直接返回\teat{True} 。
public class Solution
{
public boolean checkSubarraySum(int[] nums, int k)
{
int sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, -1);
for (int i = 0; i < nums.length; i++)
{
sum += nums[i];
if (k != 0)
sum = sum % k;
if (map.containsKey(sum))
{
if (i - map.get(sum) > 1)
return true;
}
else
map.put(sum, i);
}
return false;
}
}
复杂度分析
时间复杂度： O(n)O(n) 。仅需要遍历 numsnums 数组一遍。 空间复杂度： O(min(n,k))O(min(n,k)) 。 HashMap 最多包含 min(n,k)min(n,k) 个不同的元素。
三个版本的C++代码：
class Solution {
public:
//1、时间复杂度O(N^2)
bool checkSubarraySum(vector<int>& nums, int k) {
int sum = 0;
unordered_map<int, int> map;
map[sum] = -1;
for (int i = 0; i < nums.size(); ++i)
{
sum += nums.at(i);
//遍历map
for (auto& pair : map)
{
if ((k == 0 && sum - pair.first == 0) || (k != 0 && (sum - pair.first) % k == 0)) //注意：k可能等于0
{
int len = i - pair.second;
if (len >= 2)
{
return true;
}
}
}
map.insert(make_pair(sum, i));
}
return false;
}
//2、时间复杂度O(N)
bool checkSubarraySum(vector<int>& nums, int k) {
int sum = 0;
unordered_map<int, int> map;
map[sum] = -1;
for (int i = 0; i < nums.size(); ++i)
{
sum += nums.at(i);
if (k != 0)
{
sum %= k;
}
auto iter = map.find(sum);
if (iter != map.end())
{
if (i - iter->second >= 2)
{
return true;
}
}
else
{
map[sum] = i;
}
}
return false;
}
};
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。
1、动态规划
定义dp表示以A[i]和B[j]为结尾的公共子数组的最长长度（注意公共子数组一定分别包含A[i]和B[j]作为末元素，类比最大子段和问题） 当A[i]!=B[j]时，dp=0, 因为以A[i]和B[j]结尾的公共子数组不存在，因为它们的末元素不等 当A[i]==B[j]时，dp=dp+1, 因为A[i]和B[j]相等，以它们俩为结尾的最长公共子数组的长度就是以A[i-1]和B[j-1]结尾的最长公共子数组的长度加1
之所以这样定义状态是因为原问题所要求的最长公共子数组如果存在，它一定是以某一个A的元素结尾，也以某一个B的元素结尾，现在就是遍历所有可能的分别以哪两个元素结尾的情况，取其中的最长的情况即可
类比1143.最长公共子序列问题：因为该问题中是子数组，元素要求是连续的，所以当A[i]!=B[j]时，直接置dp=0即可，此时以A[i]和B[j]结尾的最长子数组压根不存在，而最长公共子序列问题中，即使A[i]!=B[j]，也要将前面求出来的最长子序列长度继承下来
class Solution
{
public int findLength(int[] A, int[] B)
{
int len_a=A.length;
int len_b=B.length;
if(len_a==0||len_b==0) return 0;
int res=0;
int [][] dp=new int[len_a][len_b];
for(int i=0;i<len_a;i++) {
if(A[i]==B[0]) {res=1;dp[i][0]=1;}
}
for(int j=1;j<len_b;j++) {
if(A[0]==B[j]) {res=1;dp[0][j]=1;}
}
for(int i=1;i<len_a;i++){
for(int j=1;j<len_b;j++){
if(A[i]==B[j]) {
dp[i][j]=dp[i-1][j-1]+1;
if(dp[i][j]>res) res=dp[i][j];
}else{
dp[i][j]=0;
}
}
}
return res;
}
};
C++ 工程实践 下一篇»
Читайте прикольные анекдоты про разведчика Штирлица на <a href="https://dzen.ru/a/ZtmfdXQjNXiBl_T8">https://dzen.ru/a/ZtmfdXQjNXiBl_T8</a>
Secure your social media presence with accounts from SellAccs.net. Our PVA accounts are created using multiple server IPs, offering you reliable and safe access to your platforms.
Act Now:
https://SellAccs.net
Онлайн казино для победителей <a href=https://t.me/s/starz_888_official>888starz bet скачать бесплатно</a> https://t.me/s/starz_888_official
Сайт онлайн казино <a href=https://t.me/s/casino7kzerkalo>7k casino зеркало</a> рабочее https://t.me/s/casino7kzerkalo