如果避免失敗成為你做事的動機，你就會陷入消極怠工的壯態。
前言
這幾天比較忙，所以晚了一點總結。這周的題是隨機抽取，沒有特定的主題。算法題解沒有特定的思路，可能一人有一個思路，例如有的題既可以使用動規，又可以使用分治。殊途同歸，算法的目的就是提升效率。
連續數列給定一個整數數組，找出總和最大的連續數列，並返回總和。
示例：
輸入： [-2,1,-3,4,-1,2,1,-5,4]
輸出： 6
解釋： 連續子數組 [4,-1,2,1] 的和最大，為 6。進階：
如果你已經實現複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。
用數組的每一個元素和其他元素組成一個子序列。再判斷每個子序列和的大小。
var maxSubArray = function (nums) {
let arr = nums[0]
for (let i = 0; i < nums.length; i++) {
let sum = nums[i]
arr = Math.max(nums[i],arr)
for (let j = i + 1; j < nums.length; j++) {
sum += nums[j]
if (arr < sum) {
arr = sum
}
}
}
return arr
};
最大子序和是動規的經典例題，因為它會遇到子問題的重疊性。我們可以把問題簡化為累加和與當前值的比較。
找到最優子結構，把每個子問題簡化為
num[i]=Math.max(nums[i-1]+nums[i],nums[i])
記錄歷史狀態，找到最優解。
max=Math.max(max,nums[i])
var maxSubArray = function (nums) {
let max = nums[0];
for (let i = 1; i < nums.length; i++) {
nums[i] = Math.max(nums[i - 1] + nums[i], nums[i])
max = Math.max(max, nums[i])
}
return max
};
sum記錄當前累加和，如果當前累加和小於0，就重置sum。
var maxSubArray = function (nums) {
let sum=-Infinity,max=-Infinity;
for(let i=0;i < nums.length;i++){
if(sum<0){
sum = nums[i]
}else{
sum += nums[i]
}
max=Math.max(sum,max)
}
return max
};
創建一個dp數組，裡面保存著所有dp[i]的最大子序列和。
var maxSubArray = function (nums) {
const dp = new Array(nums.length)
dp[0] = nums[0]
dp[1] = nums[0]
for (let i = 2,
len = nums.length;
i <= len; i++) {
dp[i] = Math.max(
nums[i - 1],
dp[i - 1] + nums[i - 1])
}
return Math.max(...dp)
};
分治法把數組分成兩個相互獨立的子問題來解決。
var maxSubArray = function (nums) {
// 分治法
if(nums.length == 0) return -Infinity;
const divide=(nums, left, right) => {
if(left == right) return nums[left];
let mid = (left + right) / 2 | 0;
// 1. 最大數列和在左邊
let sumLeft = divide(nums,left,mid);
// 2. 最大數列和在右邊
let sumRight = divide(nums,mid+1,right);
// 3. 最大數列和在中間
// 先求左邊的最大和
let leftSum = 0,leftMaxSum = -Infinity;
for(let i = mid; i >= left; i--){
leftSum += nums[i];
leftMaxSum = Math.max(leftMaxSum,leftSum);
}
// 求右邊的最大和
let rightSum = 0,rightMaxSum = -Infinity;
for(let i = mid + 1; i <= right; i++){
rightSum += nums[i];
rightMaxSum = Math.max(rightMaxSum,rightSum);
}
return Math.max(
Math.max(sumLeft,sumRight),
leftMaxSum+rightMaxSum);
}
return divide(nums,0,nums.length-1);
};
主要元素如果數組中多一半的數都是同一個，則稱之為主要元素。給定一個整數數組，找到它的主要元素。若沒有，返回-1。
示例 1：
輸入：[1,2,5,9,5,9,5,5,5]
輸出：5示例 2：
輸入：[3,2]
輸出：-1示例 3：
輸入：[2,2,1,1,1,2,2]
輸出：2題解：
這題比較簡單，有點類似找字符串中出現次數最多的字符。
var majorityElement = function(nums) {
let obj = {}
for(let i of nums){
obj[i] =!obj[i] ? 1 : ++obj[i]
}
for(let i in obj){
if(obj[i] > (nums.length/2 | 0) ){
return i
}
}
return -1
};
合併兩個排序列表輸入兩個遞增排序的鍊表，合併這兩個鍊表並使新鍊表中的節點仍然是遞增排序的。
示例1：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4限制：
0 <= 鍊表長度 <= 1000
題解：
需要注意的是遞歸結束條件，以及判斷條件中的返回值。
var mergeTwoLists = function(l1, l2) {
if (l1 === null) return l2;
if (l2 === null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};
借用一個鍊表來存儲。
var mergeTwoLists = function(l1, l2) {
let current = new ListNode();
const dummy = current;
while (l1 || l2) {
//迭代結束條件
if (!l1) {
current.next = l2;
return dummy.next;
} else if (!l2) {
current.next = l1;
return dummy.next;
}
//迭代進行
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
return dummy.next;
};
數組中出現次數超過一半的數字數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。你可以假設數組是非空的，並且給定的數組總是存在多數元素。
示例 1:
輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
輸出: 2限制：
1 <= 數組長度 <= 50000
題解：
此題與主要元素是相似。
var majorityElement = function (nums) {
let hash = {}, max = 0, num = nums[0];
for (let i = 0; i < nums.length; i++) {
hash[nums[i]]=!hash[nums[i]]?1:++hash[nums[i]]
}
for (let key in hash) {
max = Math.max(max, hash[key])
if (max == hash[key]) {
num = key
}
}
return num
};
var majorityElement = function (nums) {
return nums.sort(((a, b) => a - b))[(nums.length / 2) | 0]
};
最小的k個數輸入整數數組 arr ，找出其中最小的 k 個數。例如，輸入4、5、1、6、2、7、3、8這8個數字，則最小的4個數字是1、2、3、4。
示例 1：
輸入：arr = [3,2,1], k = 2
輸出：[1,2] 或者 [2,1]示例 2：
輸入：arr = [0,1,2,1], k = 1
輸出：[0]限制：
題解：
var getLeastNumbers = function(arr, k) {
return arr.sort((a, b) => a - b).slice(0, k);
};
利用快排的思想，每經過一輪排序，pivot 左邊的一定是較小的，右邊的一定是較大的。var getLeastNumbers = function (arr, k) {
if (arr.length === k) return arr;
const left = [], right = [];
const pivot = arr.pop();
for (let i = 0; i < arr.length; ++i) {
if (arr[i] <= pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return left.length < k ?
left.concat([pivot])
.concat(
getLeastNumbers(
right, k - left.length - 1))
: getLeastNumbers(left, k);
};
希望有更多的小夥伴加入
感謝大家一路的陪伴與堅持
本活動旨在提高群成員的算法思維，每天一道leetcode算法題，需要你註冊https://leetcode-cn.com/力扣官網，程式語言不限。
群管理小雪，每天會監督每位成員，為了提高本成員的自律性。
1、不許發與技術無關的話題，可以討論每天的算法題；
2、成員之間相互尊重；
3、每個工作日早上10點發題，截止晚上10點，每個成員必須發出截圖打卡，約束自己；
4、管理員小雪，每天10點統計，沒有發截圖（打卡）者，會發5元紅包作為統計費用；
5、每周六和周日兩天作為回顧整理，不會發題，不做限制，如果有成員回顧整理成文章，文章精美者，可以獲得10元的獎勵，被收錄在公眾號驚天碼盜。
6、目前leetcode算法題有1055道題，希望大家能一直堅持下來。
1、每個題來自leetcode題庫，出題從簡單到困難；
2、每天管理員會把題的編號和題名，以及截圖發在群裡，成員可以在題庫搜索編號或題名即可查到相應題目；
1、截圖只為約束，如果算法題太難，可以直接查看別人的題解，掌握其思維方式，截圖即可；
2、如果成員覺得題太簡單，可以自行找其他題做，發截圖即可；如果你有更好的解題思路，請不要吝嗇，歡迎在下方評論。你的參與是最有力的支持，學習重在習慣。
如果你也想參與，公眾號內回復 算法，拉你進群。