wy的leetcode刷题记录_Day22

目录

• wy的leetcode刷题记录_Day22
• • 题目
  • • 题目介绍
    • 思路
    • 代码
    • 收获
  • 2121. 相同元素的间隔之和
  • • 题目介绍
    • 思路
    • 代码
    • 收获

题目

53. 最大子数组和

题目介绍

1. 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
2. 子数组 是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

思路

1. 方法一：暴力解法：嵌套遍历计算出最大的子数组的和
2. 方法二：动态规划：用dp[i]维护遍历到下标i时最大子数组长度，从前往后遍历，转移条件： dp[i]=max(dp[i-1]+nums[i],nums[i]);
3. 方法三：贪心算法：从左向右遍历记录sum，如果sum<0就重新记录，并且时刻更新最大值。
4. 方法四：分治法：首先取数组的中心点作为中心，最大子序列有三种情况，要么全部在左边，要么全部在右边，要么跨中心，如果跨中心的话再分成左侧和右侧的问题。

代码

class Solution
{
public:int maxSubArray(vector &nums){//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值int max = INT_MIN;int numsSize = int(nums.size());for (int i = 0; i < numsSize; i++){int sum = 0;for (int j = i; j < numsSize; j++){sum += nums[j];if (sum > max){max = sum;}}}return max;}
};

class Solution {
public:int maxSubArray(vector& nums) {int n=nums.size();vector dp(n,0);dp[0]=nums[0];int result=dp[0];for(int i=1;idp[i]=max(dp[i-1]+nums[i],nums[i]);result=max(result,dp[i]);}return result;}
};

class Solution
{
public:int maxSubArray(vector &nums){//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值int result = INT_MIN;int numsSize = int(nums.size());int sum = 0;for (int i = 0; i < numsSize; i++){sum += nums[i];result = max(result, sum);//如果sum < 0，重新开始找子序串if (sum < 0){sum = 0;}}return result;}
};

class Solution
{
public:int maxSubArray(vector &nums){//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值int result = INT_MIN;int numsSize = int(nums.size());result = maxSubArrayHelper(nums, 0, numsSize - 1);return result;}int maxSubArrayHelper(vector &nums, int left, int right){if (left == right){return nums[left];}int mid = (left + right) / 2;int leftSum = maxSubArrayHelper(nums, left, mid);//注意这里应是mid + 1，否则left + 1 = right时，会无线循环int rightSum = maxSubArrayHelper(nums, mid + 1, right);int midSum = findMaxCrossingSubarray(nums, left, mid, right);int result = max(leftSum, rightSum);result = max(result, midSum);return result;}int findMaxCrossingSubarray(vector &nums, int left, int mid, int right){int leftSum = INT_MIN;int sum = 0;for (int i = mid; i >= left; i--){sum += nums[i];leftSum = max(leftSum, sum);}int rightSum = INT_MIN;sum = 0;//注意这里i = mid + 1，避免重复用到nums[i]for (int i = mid + 1; i <= right; i++){sum += nums[i];rightSum = max(rightSum, sum);}return (leftSum + rightSum);}
};

收获

首先读完题目使用最简单的暴力算法写出来逻辑正确，但是超时了，想出优化方案，使用动态规划用数组记录之前的值，最后用贪心算法只用一个变量即可记录。分治是最难的（我也是参考别人的）：首先取数组的中心点作为中心，最大子序列有三种情况，要么全部在左边，要么全部在右边，要么跨中心，如果跨中心的话再分成左侧和右侧的问题。

2121. 相同元素的间隔之和

2121. 相同元素的间隔之和

题目介绍

1. 给你一个下标从 0 开始、由 n 个整数组成的数组 arr 。
2. arr 中两个元素的 间隔 定义为它们下标之间的 绝对差 。更正式地，arr[i] 和 arr[j] 之间的间隔是 |i - j| 。
3. 返回一个长度为 n 的数组 intervals ，其中 intervals[i] 是 arr[i] 和 arr 中每个相同元素（与
   arr[i] 的值相同）的 间隔之和 。
4. 注意：|x| 是 x 的绝对值。

示例 1：
输入：arr = [2,1,3,1,2,3,3]
输出：[4,2,7,2,4,4,5]
解释：

• 下标 0 ：另一个 2 在下标 4 ，|0 - 4| = 4
• 下标 1 ：另一个 1 在下标 3 ，|1 - 3| = 2
• 下标 2 ：另两个 3 在下标 5 和 6 ，|2 - 5| + |2 - 6| = 7
• 下标 3 ：另一个 1 在下标 1 ，|3 - 1| = 2
• 下标 4 ：另一个 2 在下标 0 ，|4 - 0| = 4
• 下标 5 ：另两个 3 在下标 2 和 6 ，|5 - 2| + |5 - 6| = 4
• 下标 6 ：另两个 3 在下标 2 和 5 ，|6 - 2| + |6 - 5| = 5

示例 2：
输入：arr = [10,5,10,10]
输出：[5,0,3,4]
解释：

• 下标 0 ：另两个 10 在下标 2 和 3 ，|0 - 2| + |0 - 3| = 5
• 下标 1 ：只有这一个 5 在数组中，所以到相同元素的间隔之和是 0
• 下标 2 ：另两个 10 在下标 0 和 3 ，|2 - 0| + |2 - 3| = 3
• 下标 3 ：另两个 10 在下标 0 和 2 ，|3 - 0| + |3 - 2| = 4

思路

首先浏览完题目后，直接用一个map存贮相同的值对应的下标，key为值，value为对应的下标组成的数组。此时如果我们暴力遍历map一个一个去减的话是超时的。所以我们选择遍历map，解析其中的value，建立一个数组存贮相邻的俩个相同值的距离之差。然后我们发现规律：

相同元素的下标为数组p: p0 p1 p2 p3 p4
两两间隔为: a b c d
ans[0] = p4-p0 + p3-p0 + p2-p0 + p1 - p0
= 0 + 4a+3b+2c+1d
ans[1] = a + 3b+2c+1d
ans[2] = a+2b + 2c+1d
ans[3] = a+2b+3c + 1d
ans[4] = a+2b+3c+4d + 0
从上可以看出规律, 使用前缀和leftSum和后缀和rightSum, 进行优化计算

我们只需要计算出前缀和和后缀和然后进行相加减就ok了。

代码

class Solution {
public:vector getDistances(vector& arr) {int n=arr.size();unordered_map> hash;for(int i=0;i// if(!hash.count(arr[i]))//     hash[arr[i]]=i;// elsehash[arr[i]].push_back(i);}vector ans(n,0);//      int m=hash.size()for(auto [k,v]:hash){int m=v.size();vector diff(m,0);for(int i=0;idiff[i]=v[i+1]-v[i];}long long RightSum=0;long long LeftSum=0;for(int i=m-2;i>=0;i--){RightSum+=diff[i]*(m-i-1);}ans[v[0]]=RightSum;for(int i=1;iLeftSum+=i*diff[i-1];RightSum-=(m-i)*diff[i-1];ans[v[i]]=LeftSum+RightSum;}}return ans;}
};

收获

前缀和、后缀和真的很重要，并且和差分的应用真的有不错的效果！