th686785.jpg

217. 存在重復(fù)元素

原題鏈接：https://leetcode-cn.com/problems/contains-duplicate/

利用 Set 的唯一性。判斷去重之后的數(shù)組長度是否與原來相等，如果相等，則數(shù)組中不存在重復(fù)元素。反之，則存在。

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/

第一步：定義子問題

動態(tài)規(guī)劃是將整個數(shù)組歸納考慮，假設(shè)我們已經(jīng)知道了以第 i-1 個數(shù)結(jié)尾的連續(xù)子數(shù)組的最大和 dp[i-1]，顯然以第i個數(shù)結(jié)尾的連續(xù)子數(shù)組的最大和的可能取值要么為 dp[i-1]+nums[i]，要么就是 nums[i] 單獨成一組，也就是 nums[i] ，在這兩個數(shù)中我們?nèi)∽畲笾怠?/p>

第二步：實現(xiàn)需要反復(fù)執(zhí)行解決的子子問題部分

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. 兩數(shù)之和

原題鏈接：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] ，求解結(jié)束

遍歷結(jié)束，則 nums 中沒有符合條件的兩個數(shù)，返回 []

時間復(fù)雜度：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. 合并兩個有序數(shù)組

原題鏈接：https://leetcode-cn.com/problems/merge-sorted-array/

利用雙指針，不斷由后向前遍歷。在遍歷的過程中，比較數(shù)字的大小

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. 兩個數(shù)組的交集 II

原題鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

對第一個數(shù)組進行遍歷，用一張表記錄數(shù)組中每一個數(shù)字出現(xiàn)的次數(shù)

第二個數(shù)組進行遍歷時，判斷是否存在于第一個數(shù)組中。如果存在，則利用之前統(tǒng)計的次數(shù)，計算應(yīng)該加入的次數(shù)

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.大問題與小問題的關(guān)系

1）狀態(tài)定義：我們定義max_profit為第i天的最大收益

2）狀態(tài)轉(zhuǎn)移方程： 第i天的最大收益和第i-1天的最大收益之間的關(guān)系：

i) 最大收益不是第i天拋出的， ---最大收益和第i天的價格無關(guān)

ii）最大收益是在第i-1天前某天買入的，并在第i天拋出的， ---與第i天的價格有關(guān)

因此第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 時， 沒有辦法帶入轉(zhuǎn)移公式中，需要特殊處理。

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 = [];
  // 將二維數(shù)組轉(zhuǎn)化為一維數(shù)組
  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數(shù)組
      item.push(newMat.shift(newMat[i]));
    }
    // 當前行收集完畢，推入新數(shù)組的尾部
    newMat.push(item);
  }
  return newMat;
};