217. 存在重复元素
原题链接：https://leetcode-cn.com/problems/contains-duplicate/
利用 Set 的唯一性。判断去重之后的数组长度是否与原来相等，如果相等，则数组中不存在重复元素。反之，则存在。
var containsDuplicate = function (nums) {
let set = new Set()
for (let i = 0; i < nums.length; i++) {
set.add(nums[i])
}
if (set.size === nums.length) {
return false
} else {
return true
}
};
53. 最大子序和
原题链接：https://leetcode-cn.com/problems/maximum-subarray/
第一步：定义子问题
动态规划是将整个数组归纳考虑，假设我们已经知道了以第
i-1个数结尾的连续子数组的最大和dp[i-1]，显然以第i个数结尾的连续子数组的最大和的可能取值要么为dp[i-1]+nums[i]，要么就是nums[i]单独成一组，也就是nums[i]，在这两个数中我们取最大值。第二步：实现需要反复执行解决的子子问题部分
dp[n] = Math.max(dp[n−1]+nums[n], nums[n])第三步：识别并求解出边界条件
dp[0]=nums[0]
var maxSubArray = function (nums) {
let max = -Infinity
let dp = []
let n = nums.length
for (let i = -1; i < n; i++) {
dp[i] = 0
}
for (let i = 0; i < n; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
max = Math.max(max, dp[i])
}
return max
}
1. 两数之和
原题链接：https://leetcode-cn.com/problems/two-sum/
初始化一个
map = new Map()从第一个元素开始遍历
nums获取目标值与
nums[i]的差值，即k = target - nums[i]，判断差值在map中是否存在不存在
map.has(k)为false，则将nums[i]加入到map中（key为nums[i],value为i，方便查找map中是否存在某值，并可以通过get方法直接拿到下标）存在
map.has(k)，返回[map.get(k), i]，求解结束遍历结束，则
nums中没有符合条件的两个数，返回[]时间复杂度：O(n)
var twoSum = function (nums, target) {
let map = new Map()
for (let i = 0; i < nums.length; i++) {
let k = target - nums[i]
if (map.has(k)) {
return [map.get(k), i]
}
map.set(nums[i], i)
}
return [];
};
88. 合并两个有序数组
原题链接：https://leetcode-cn.com/problems/merge-sorted-array/
利用双指针，不断由后向前遍历。在遍历的过程中，比较数字的大小
var merge = function (nums1, m, nums2, n) {
let len1 = m - 1
let len2 = n - 1
let len = m + n - 1
while (len2 >= 0) {
if (len1 < 0) {
nums1[len--] = nums2[len2--]
continue
}
nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--] : nums2[len2--]
}
};
350. 两个数组的交集 II
原题链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
对第一个数组进行遍历，用一张表记录数组中每一个数字出现的次数
第二个数组进行遍历时，判断是否存在于第一个数组中。如果存在，则利用之前统计的次数，计算应该加入的次数
var intersect = function (nums1, nums2) {
const map = new Map()
let result = []
for (let i = 0; i < nums1.length; i++) {
let value = map.get(nums1[i])
if (value) {
map.set(nums1[i], ++value)
} else {
map.set(nums1[i], 1)
}
}
for (let i = 0; i < nums2.length; i++) {
let value = map.get(nums2[i])
if (value >= 1) {
map.set(nums2[i], --value)
result.push(nums2[i])
}
}
return result
};
121. 买卖股票的最佳时机
原题链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
1.大问题与小问题的关系
1）状态定义：我们定义max_profit为第i天的最大收益
2）状态转移方程： 第i天的最大收益和第i-1天的最大收益之间的关系：
i) 最大收益不是第i天抛出的， ---最大收益和第i天的价格无关
ii）最大收益是在第i-1天前某天买入的，并在第i天抛出的， ---与第i天的价格有关
因此第i天的最大收益等于：第i天抛出所造成的最大收益 和 第i-1天之前的最大收益 中的最大值
即： 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
其中： 前i-1天中的最小价格需时时更新并记录
2.初始条件：
min 和 max_profit min可以等于第一天的price max_profit可以等于0， 因为最大收益的最小值就是0， 用人话叫，最低也不能赔了
3.小于最小问题的特殊情况： 当list的长度为0 和 1 时， 没有办法带入转移公式中，需要特殊处理。
var maxProfit = function (prices) {
let max = 0, min = prices[0]
for (let i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i])
max = Math.max(max, prices[i] - min)
}
return max
};
566. 重塑矩阵
原题链接：https://leetcode-cn.com/problems/reshape-the-matrix/
var matrixReshape = function (mat, r, c) {
const newMat = [];
// 将二维数组转化为一维数组
for (let i = 0; i < mat.length; i++) {
newMat.push(...mat[i]);
}
// 判断能否重塑成功
if (r * c !== newMat.length) return mat;
// 一共有r行
for (let i = 0; i < r; i++) {
const item = [];
// 每行c个
for (let j = 0; j < c; j++) {
// 将c个元素从头部拿出，并放入暂存的item数组
item.push(newMat.shift(newMat[i]));
}
// 当前行收集完毕，推入新数组的尾部
newMat.push(item);
}
return newMat;
};
