53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
解：典型的使用动态规划解决的问题，需要掌握动态规划问题设计状态的技巧(无后效性)，知道如何推到状态转移方程，最后优化空间。
方法1：动态规划
关键1：理清题意
找出和最大的连续子数组的值是多少。连续是关键字，不是子序列。只要求结果，不要求最大的连续数组是哪一个。这样的问题描述可以使用[动态规划]解决
关键2：如何定义子问题
设计状态思路：把不确定的因素确定下来，进而把子问题定义清除，把子问题定义的简单。动态规划的思想通过解决一个一个简单的问题，进而把简单的问题的解组成了 复杂的问题的解。
例如，示例1输入数组是 [-2,1,-3,4,-1,2,1,-5,4] ，我们可以求出以下子问题：
- 子问题 1：经过 -2?2 的连续子数组的最大和是多少；
- 子问题 2：经过 11 的连续子数组的最大和是多少；
- 子问题 3：经过 -3?3 的连续子数组的最大和是多少；
- 子问题 4：经过 44 的连续子数组的最大和是多少；
- 子问题 5：经过 -1?1 的连续子数组的最大和是多少；
- 子问题 6：经过 22 的连续子数组的最大和是多少；
- 子问题 7：经过 11 的连续子数组的最大和是多少；
- 子问题 8：经过 -5?5 的连续子数组的最大和是多少；
- 子问题 9：经过 44 的连续子数组的最大和是多少。
这九个问题之间的联系没那么好看出来，因为子问题的描述还有不确定性(这就叫做有后效性)。
例如问题3，不确定的是-3是连续子数组的第几个元素，如果我们把-3定义成连续子数组的最后一个元素，可以列出以下问题： - 子问题 1：以 -2?2 结尾的连续子数组的最大和是多少；
- 子问题 2：以 11 结尾的连续子数组的最大和是多少；
- 子问题 3：以 -3?3 结尾的连续子数组的最大和是多少；
- 子问题 4：以 44 结尾的连续子数组的最大和是多少；
- 子问题 5：以 -1?1 结尾的连续子数组的最大和是多少；
- 子问题 6：以 22 结尾的连续子数组的最大和是多少；
- 子问题 7：以 11 结尾的连续子数组的最大和是多少；
- 子问题 8：以 -5?5 结尾的连续子数组的最大和是多少；
- 子问题 9：以 44 结尾的连续子数组的最大和是多少。
加上了结尾此时，子问题之间就有了联系，例如子问题1，2
以-2结尾的连续子数组是-2，因此最大和就是-2
以1结尾的连续子数组和最大和有[-2, 1]，[1]。其中[-2, 1]就是在子问题1后面加上1得到，子问题2的答案是1.
不难发现，如果编号i的子问题的结果是负数或者0，那么编号[i+1]的子问题就可以把编号为i的子问题的结果舍弃掉(这里i为整数，最小值为1，最大值为8).
定义状态(定义子问题)
dp[i]：表示nums[i]结尾的连续子数组的最大和。
说明：[结尾]和[连续]是关键字。
状态转移方程(描述子问题之间的联系)
根据状态的定义，由于nums[i]一定会被选取，并且以nums[i]结尾的连续子数组与以nums[i-1]结尾的连续子数组只相差一个元素nums[i]。
假设数组nums的值全部严格大于0，那么一定有dp[i]= dp[i -1] + nums[i]
- 如果dp[i-1] > 0，那么可以把nums[i]直接接在dp[i-1]表示的那个数组后面，得到和更大的连续子数组。
- 如果dp[i-1] <= 0,那么nums[i]加上前面的数dp[i-1]以后值不会变大。于是dp[i]另起炉灶，此时单独的一个nums[i]的值，就是dp[i]。
解决方案：
function maxSubArray(nums: number[]): number {
let dp:number[] = [];
dp[0] = nums[0];
for(let i = 1; i < nums.length; i++){
if(dp[i-1] > 0) dp[i] = dp[i-1] + nums[i];
else dp[i] = nums[i];
}
return Math.max(...dp);
};
136.只出现一次的数字
描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例：
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
解法：
异或运算：三个性质
- 任何数和 0 做异或运算，结果仍然是原来的数
- 任何数和其自身做异或运算，结果是 0
- 异或运算满足交换律和结合律，即 a ^ b ^ a=b ^ a ^ a=b ^ (a ^ a)=b ^ 0=b
function singleNumber(nums: number[]): number {
return nums.reduce((pre, next) => pre ^ next);
};
169.多数元素
给定一个大小为 n 的数组?nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于?? n/2 ??的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例
输入：nums = [3,2,3]
输出：3
输入：nums = [2,2,1,1,1,2,2]
输出：2
解法：
function majorityElement(nums: number[]): number {
let n = nums.length / 2;
let hashMap = new Map();
if(nums.length === 1) return nums[0];
for(let i of nums){
if(!hashMap.has(i)){
hashMap.set(i, 1)
}else{
hashMap.set(i, hashMap.get(i) + 1)
if(hashMap.get(i) > n) return i;
}
}
};
|