本文為js版本演算法視頻筆記 找了很多演算法這個up主講的真的非常好 適合小白去聽 演算法都是力扣難度中等和簡單的
b站視頻鏈接
1、島嶼最大面積（求兩數最大和）
決議：提供一個陣列，給了一個target 要求是在陣列中找到兩個數的和為target
思路：
1.創建一個map
2、for回圈遍歷nums陣列
3、用target減nums[i]以計算哪個數跟當前數字相加等于target
4、檢查map里有沒有這個數，有的話就放回結果，沒有就把num[I]當做key， i單做value放入map中
代碼實作：
var towSum = function(nums, target){
const map = new Map();
for (let i = 0; i <nums.length;i++){
const complement = target-nums[i];
if(map.has(complement){
return [map.get(complement).i];
}else {
map.set(num[i],i);
}
}
return [];
};
2、兩鏈表相加
視頻鏈接
關鍵的地方處理好進位的問題，兩個鏈表相加會生成一個新的鏈表
代碼實作：
// 兩數相加
var addTwoNumbers = function (l1,l2){
// 定義一個新的節點
let dummy = new listNode();
// curr是用來遍歷串列用的
let curr = dummy;
let carry = 0; //處理進位用
while(l1 !== null || l2 !== null){
let sum = 0;
if(l1 !==null{
sum += l1.val;
l1 = l1.next;
}
if(l2 !== null){
sum +=l2.val;
l2= l2.next;
}
sum += carry; //檢carry有沒有進位
curr.next = new listNode( sum %10); //把得到的sum值各位作為新的list的節點
carry = Math.floor(sum/10); //如果有carry值 就暫存carry的值 carry的值是sum/10之后取整
}
if(carry>0){
curr.next = new listNode(carry);// 如果最后的carry值大于0，需要單獨做一個新節點
}
return dummy.next;//最后return出去
}
3、找到無重復字符的最長子串
思路：
1、創建一個set 用來存放新的字串 還需要知道這個字串的長度
2、兩個指標第一個指標指向字串的開頭-j，第二個隨著for回圈遍歷字串-i
3、如果set里面有s【i】，則從set里開始傷處s【j】，并且遞增j，在檢查set里是否有s【j】，如此反復直到set里沒有s【i】為止
5、重復步驟3和4直到完成遍歷整個字串
·代碼實作：
var lengthOfLongSubstring = function(s){
const set = new Set();
let i = 0;
let j = 0;
maxLength = 0;
if(s.length === 0){
return 0;
}
for (i; i<s.length;i++){
if (!set.has(s[i])){
set.add(s.[i]);
maxLength = Math.max(maxLength,set.size);
}else{
while(set.has(s[i])){
set.delete(s[j]);
j++;
}
set.add(s[i]);
}
}
return maxLength;
}
4 求三數之和
求陣列里面找三個數相加等于0 答案里面必須是唯一的
求解思路：
1、給陣列排序
2、遍歷陣列，從0遍歷到length-2
3、如果當前的數字等于前一個數字，則跳過這個數字（去重）
4、如果數字不同，則設定start = i +1,
end =length -1,查看i start和end三個數的和比零大還是小 如果比0小 start++ 如果比0大 end–；如果等于0 則把這三個數加到結果中 繼續下一次遍歷
5、回傳結果 不能重復
代碼實作：
var threeSum = function (nums){
const result = [];
nums.sort(function(a,b){
return a -b;
})
for(let i =0;i<length-2;i++){
//去重 b重復的就不需要在判斷
if(i === 0 || nums[i] !== nums[i-1]){
let start = i+1;
let end = nums.length -1;
while(start<end){
//三種結果 大于等于小于0
if(nums[i] + nums[start] + nums[end] === 0){
result.push ([nums[i],nums[start],nums[end]]);
start ++;
end--;
//判斷是否重復
while(start <end && nums[start] === nums[start -1]){
start ++;
}
while(start <end && nums[start] === nums[start +1]){
end --;
}
}else if(nums[i] + nums[start] + nums[end] < 0){
start ++;
}else{
end --;
}
}
}
}
return result;
}
5、最長回文字串
思想是中心擴散的思想
遍歷每一個字符 把每一個字符當做中心點像兩邊擴散看兩邊是否相等，知道不相等為止
回文字串有兩種情況：中間一個不同 兩邊相同如abcacba a為中心點
另外一個是abccba 兩邊都相等 沒有中間點直接像兩邊擴散
解題思想：
1、如果字串長度小于2 直接回傳原字串
2、定義兩個變數 一個start存盤當前找到的最大會問字串的起始位置，另一個maxLength記錄字串的長度 終止位置就是start+maxLength
3、創建一個helper function 判斷左邊和右邊是否越界 同時左邊的字串是否等于右邊的字串，如果以上三個條件都滿足，則判斷是否需要更新回文字串最大長度以及字串的起始位置，然后將left-- right++，繼續判斷 直到不滿足三個條件之一，
4遍歷字串 每個位置呼叫helper function兩遍
第一遍檢查i-1，i+1，第二遍檢查i i+1(兩種回文）
代碼實作：
var longestPalindrome = function(s){
//如果之后一個字符直接回傳
if(s.length<2){
return s;
}
let start = 0;
let maxLength = 1; //當有兩個字符的時候，回傳的回文字串至少是其中一共字符 所以length應該初始化為1
//helper函式因為要被反復用到 所以這點提出來
function expandAroundCenter(left,right){
//上述提到的三個條件同時滿足
while(left > =0 && right <s.length && s[left] === s[right]){
//比較字串長度 如果新的字串比之前的大 則進行更新
if(right - left + 1 >maxLength){
maxLength = right -left +1;
start = left
}
left --;
right ++;
}
}
// 遍歷的時候把每一個當做中心 這里需要考慮兩種回文字串 因此需要在回圈中執行兩次函式
for(let i = 0; i < s.length; i++){
expandAroundCenter(i-1,i+1);
expandAroundCenter(i ,i+1);
}
//最后放回的是截取的字串
return s.substring(start.start+maxLength);
}
6、洗掉鏈表的倒數第N個節點
題目描述：給定一個鏈表 洗掉鏈表的倒數第n個節點 并回傳鏈表的頭節點
思路 使用雙指標的思路定位到我們要洗掉的元素
單項鏈表是 走到3的時候直接指向5 不通過4了
邊界問題 如果之后1個節點
代碼實作：
var removeNthFromEnd = function (head, n){
let dummy = new ListNode();
dummy.next = head;
let n1 = dummy;
let n2 = dummy;
for (let i=0;i<=n;i++){
n2 = ne.next;
}
while(n2.next !== null){
n1 = n1.next;
n2 = n2.next;
}
n1.next = n1.next.next;
return dummy.next;
}
7、有效的括號
括號應該是正括號和反括號相對應的 怎么找出錯誤的括號
實作思路：
利用到堆疊的概念
1、創建一個HsapMap，把括號配對放進去，
2、創建一個stack （array）for回圈遍歷字串
對于每一個字符，如果map里有這個key 那說明他是一個左括號 從map里取得對應的右括號，把他push進stack里面 否則的話他就是右括號，需要pop出stack李的第一個字符然后看他是否等于當前字符 如果不相等 則回傳false
3、回圈結束 如果stack不為空 則說明還剩余一些左括號，沒有被閉合 回傳false 否則回傳true
代碼實作：
var isValid = function(s){
//創建函式把配對情況放進去
const mappings = new Map();
mappings.set ("(",")");
mappings.set("[","]");
mappings.set("{","}");
//創建一個堆疊
const stack = [];
for(let i = 0; i<s.lenght;i++){
//如果mapping里有key的話就要從mappings里面取得這個i push到stack里面
if(mappings.has(s[i])){
stack.push(mappings.get(s[i]));
}else{
//先判斷他是否等于i 如果不等于的話回傳false
if(stack.pop() !== s[i]){
return false;
}
}
}
//回圈結束之后需要檢查stack是否為空 不為慷訓傳false
if(stack.length !== 0){
return false;
}
}
8、合并兩個有序鏈表
題目描述：將兩個有序鏈表合并為一個新的有序鏈表并回傳 新鏈表是通過拼接給定的兩個鏈表的所有節點組成的
思路總結：
兩個陣列 開一個新的陣列 在兩個陣列的開頭放一個i和j 找到比較小的push到新陣列里面 i++或者J++ 在比較兩個數 小的push到新陣列直到結束；
鏈表中只有next操作，所以有局限性 要注意這個點所以需要使用dummy來進行空的占位
代碼實作：
var mergeTwoLists = function(l1,l2){
//定義一個頭部空節點 用他來生成結果 通過next串成一個鏈表
let curr = new listNode();
let dummy = curry;//
//對兩個鏈表進行回圈比較 需要判斷兩個鏈表不為空
while (l1 !== null && l2 !== null ){
if(li.val <l2.val){
curr.next = l1;
l1 = l1.next;//這一步相當于i++的操作 鏈表這樣表示
}else{
curr.next = l2;
l2 = l2.next;
}
//上面的操作新鏈表德 指標沒有動 我們需要手動移動指標.下次添加的時候就繼續從后面添加
curr = curr.next
}
// 其中一共鏈表為空的時候 把剩余鏈表加到后面
if(l1 !==null){
curr.next = l1;
}
if(l2 !==null){
curr.next = l2;
}
//第二個指標 dummy占住了頭部的位置 curr可以隨便走（因為單項鏈表不能回傳）后面不用他了
return dummy.next;
//curr在最開始我們使用的是空節點，所以最后回傳的應該是dummy.next 也就是空節點后面的第一個節點
}
9、兩兩交換鏈表中的節點
題目描述：給定一個鏈表 兩兩交換其中相鄰的節點 并回傳交換后的鏈表
解題思路：
一共需要六步 需要三個指標 交換n1和n2需要在n1n2前面設定一個p指標
1、n1 = p.next
2、 n2 = p.next.next
3、p.next = n2 從第三步開始操作
4、n1.next = n2.next
5、 n2.next = n1
6、 p = n1
原圖：
在走第二遍：因為上一步p和n1交換了 可以直接一直持續 直到結束
開頭處理：第一種方法使用dummy去處理（空頭） 第二種用if單獨去處理
return的時候使用dummy.next
代碼實作：
var swaPairs = function(head){
//創建一個dummy空節點在最開始
let dummy = new ListNode();
dummy.next = head ;
//遍歷鏈表定義的指標 這里的current其實就是上面說的p
let current = dummy;
//保證n1和n2存在 單個節點不需要交換
while(current.next !== null && current.next.next !== null){
//開始六個步驟
let n1 = current.next
let n2 = current.next.next;
current.next = n2;
n1.next = n2.next;
n2.next = n1;
current = n1;
}
return dummy.next;
//最后為啥使用dummy.next前面說過
}
10、字符異位詞分組
解釋 兩個單詞 打亂順序之后還能組成新的單詞
思路：
兩種方法：第一種是把陣列進行排序 然后比較兩個陣列單詞是否相同 最優解第二種是 空間換時間，使用26位陣列
1、檢查是否為空陣列
2、簡歷一個長度為26的陣列 起始值為0 26個0
3、遍歷所欲字串 將字母出現的頻率放到陣列中對應的位置上 利用ascii碼
4遍歷陣列 按照相同字母出現頻率進行分組歸類（使用hashMap）
5、遍歷map 將結果回傳
代碼實作：
var groupAnagrams = function (strs) {
//檢查陣列是否為空
if (strs.length === 0) {
return [];
}
const map = new Map();
//遍歷字串陣列 遍歷兩次 遍歷元素 或者元素出現多少次
for (const str of strs) {
const characters = Array(26).fill(0); //在長度為26的陣列里面填充fill 值為0的陣列
for (let i = 0; i < str.length; i++) {
const ascii = str.charCodeAt(i) - 97; //取到ascii碼
characters[ascii]++;
}
const key = characters.jion(","); //生成key并轉化成字串
// 分類操作
if (map.has(key)) {
//把key放到新的map里面
// map.set(key,map.get(key).push(str)) //這是es5的方法
map.set(key, [...map.get(key), str]) //es6擴展方法
} else {
// 沒有key的話就把key放到里面
map.set(key, [str])
}
}
//遍歷map并回傳結果
const result = [];
for(const arr of map){
result.push(arr[1])
}
return result;
}
11、最大子序和（動態規劃）
題目描述：給定一個整數陣列nums 找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和
思路： 有兩種 動態規劃和分治法，這里采用動態規劃
這題還思路還有點不是很明確后期補上
代碼實作：
//最大子序和
var maxSubArray = function(nums){
const memo = [];
memo[0] = nums[0];
for(let i=1; i<nums.length;i++){
memo[i]= Math.max(nums[i]+memo[i-1],nums[i]);
}
for(let i= 1; i<memo.length;i++){
max = Math.max(max, memo[i]);
}
return max;
}
12、螺旋矩陣
思路：把二維陣列走完 需要幾個變數 記錄走的方向
1、如果陣列為空 回傳空陣列
2.定義4個邊界以及當前方向
3、當左邊界小于等于右邊界，且上邊界小于等于下邊界的時候，執行while回圈 按照右下左上的順序 依次將路徑上的字符添加到結果里
4、while回圈結束后 回傳結果
代碼實作：
//螺旋矩陣
var spiralOrder = function(matrix){
if(matrix.length === 0){
return [];
}
//定義四邊界以及當前的方向 這四個都比較好理解
let top = 0;
let bottom = matrix.length -1;
let left = 0;
let right = matrix[0].length -1;
let direction = "right";//一開始是right
let result = [];//最侄訓傳的陣列放在里面
// 滿足這個條件開始回圈 順序應該是右下左上
while(left <= right && top <= bottom){
if(direction === "right"){
for(let i = left; i<= right;i++){
result.push(matrix[top][i]);//把路線當中的每一個數字都push到result里面
//[top][i] 往左的時候top是不變的 變的是i [top][i]這個是他的二維坐標放在這個位置
}
top++; //第一行執行完成 top++ 變成第二行
direction = "down"//改變方向
}
//后面的就是剩下三個方向寫法
else if (direction === "down"){
for(let i = top; i<=bottom; i++){
result.push(matrix[i][right]);
}
right --;
direction = "left";
}
else if (direction === "left"){
for(let i = right; i<=left; i--){
result.push(matrix[bottom][i]);
}
bottom --;
direction = "top";
}
else if (direction === "top"){
for(let i = bottom; i<=top; i--){
result.push(matrix[i][left]);
}
left ++;
direction = "right";
}
}
return result;
}
13、跳躍游戲
描述：給定一個非負整數 你最初位于陣列的第一個位置，陣列中的每個元素代表你在該位置可以跳躍的最大長度，判斷你是否能夠到達最后一個位置
給定的陣列中 跳到這個位置上的數表示你最多能跳多少步 比如在2的位置上可以跳一步或者兩部 只要最后到達最后一個位置即可；
貪心演算法/動態規劃 所有的動態規劃的方法都比貪心演算法慢
動態規劃有兩種一種是從上而下 從下往上
解題思路：利用樹遞回的解法
怎么把動態規劃加入到遞回里面
如果知道1是死路 這個點標記為死點直接放回 比如0 使用這樣一個表
代碼實作1：動態規劃從上到下
// 跳躍游戲
var canJump = function (nums){
const totalLength = nums.length; //獲取陣列的長度
const memo = Array (totalLength).fill(0);//初始化陣列都為0
memo[totalLength-1]= 1;//最后一個數是1 1是可以通道終點的
function jump(position){
// 判斷當前的位置是否被標記1 如果被標記的話就回傳true
if(memo[position] === 1){
return true;
// 判斷當前的位置是否被標記2 如果被標記的話就回傳false
}else if(memo[position] === -1){
return false;
}
//maxJump記錄一個數 最大只能到totalLength-1
const maxJump = Math.min(position + nums[position],totalLength-1)//防止下標越界
for(let i = position+1; i<=maxJump;i++){
// 每一條的分支都會記錄結果
const jumpResult = jump(i);
// 只要有其中一潭訓傳true就回傳true
if(jumpResult === true){
memo[position] = 1;
return true;
}
}
memo[position] = -1;
return false;
}
let result = jump(0);
return result;
}
代碼實作2 從后到前：
思路是一樣的只是順序是反的
我們最終要到4這個點 2能到4 ，就可以簡化為只要能到2就能到4這樣的思路，依次往前面推 0不行 1不行 3OK 那么只要能到3就能到4
// 跳躍游戲
var canJump = function (nums){
const totalLength = nums.lenght;
const memo = Array (totalLength).fill(0);
memo[totalLength -1] = 1;//最后一位標記為1
for(let i= totalLength-2; i=0;i--){//從后往前 -2是最后一位不用看了
const maxJump = Math.min(i+nums[i],totalLength-1);//防止陣列越界
for(let j= i+1;j<=maxJump;j++){
if(memo[j] === 1){
memo[i]=1;
break;//找到1之后其他的就不用看了
}
}
}
if(memo[0] === 1){
return true;
}else{
return false;
}
}
代碼實作3：貪心演算法
不用陣列 使用變數 maxJump =4 從后往前遍歷 每一個點判斷他當前的數值加上他的index值，如果是大于等于maxJump的 就一定能走到maxJump的位置， 繼續下一個 maxJump=3 判斷方法如上，如果小于maxJump，則放棄這個點，繼續下一個，for回圈遍歷完成之后，判斷如果maxJump等于0，return為true 如果不等于0 則回傳false
// 跳躍游戲貪心演算法實作
var canJump = function (nums){
let maxJump = nums.lenght -1;//初始化maxJump
//倒著回來回圈 i倒數第二個 （最后一個不考慮）
for(let i=nums.length-2;i>=0;i--){
if(i+nums[i] >= maxJump){
maxJump = i;
}
}
return maxJump === 0;
}
14、合并區間
題目描述：給了很多的區間 要盡可能的去合并這些區間，最后產出合并后的區間
解題思路：
1.將陣列中的區間按照起始位置排序
2、用curr陣列記錄當前合并的最大區間 遍歷陣列中的每一個區間 如果當前區間的起始位置小于等于curr的終點位置 則可以繼續合并 所以合并 并更新curr的起始位置和終止位置，如果當前區間的起始位置大于curr的終止位置 則無法合并 所以把curr加到result里面 并用當前的區間替換curr的值
3.最后放回result的值
代碼實作：
var merge = function (interVals){
//如果只有一個區間 回傳就OK了
if(!interVals.length<2){
return interVals;
}
//如果區間不止一個 那就得需要去排序一下數字 按照起始位置進行排序
interVals.sort(function(a,b){
return a[0] - b[0]//按照起始位置排序
})
// curr陣列里面只有起始位置和終止位置兩個數
let curr = interVals[0]; //curr記錄當前合并的最大區間 先初始化為第一個元素
let result = [];//最侄訓傳的陣列
for (let interval of interVals){//這里使用的for of 回圈
if(curr[1] >= interVals[0]){//終止位置大于起始位置
curr[1] = Math.max(curr[1],interval[1]);//擴展curr的終止位置 起始位置不變
}else{
result.push(curr);
curr= interVals//存放curr之后把curr更新為下一個區間
}
}
// 最后需要判斷一下 如果curr還存在 就需要吧curr放到result里面
// 這里的curr其實就是最后一個陣列（沒有比較）
if(curr.lenght !== 0){
result.push(curr);
}
return result;
}
15、不同路徑（動態規劃）
描述:
思路分析：要注意的是路徑不是步數
棋盤類似于陣列 我們應該如何計算其中一個格子的路徑其實就是此格子到上面的格子和左邊的格子的路線總和
這個陣列是二維的
代碼實作：
var uniquePaths = function (m,n){
//在陣列里面使用for回圈 里面放空陣列 就變成二維陣列
const memo = [];
for(let i = 0;i<n;i++){
memo.push([]);
}
//第一行路徑都是1 只有一條路徑
for(let row = 0; row <n; row ++){
memo[row][0] = 1;
}
// 這個是第一列
for (let col = 0; col<m; col ++){
memo[0][col] = 1;
}
// 這個才是正式開始算后面格子的路徑
// 兩層回圈就是行列二維陣列
for (let row = 1; row <n; row ++){
for (let col = 1; col <m ;col++){
// 最終路徑等于他上面的格子的路徑加左面格子的路徑
memo[row][col]= memo[row-1][col]+memo[row][col-1];
}
}
return memo[n-1][m-1]; //最后終點的值是n-1，m-1 所以回傳這
}
16、陣列最后位加一
題目描述：
思路實作：
兩種情況 如果最后一位不是9的話直接加一 如果是9的話需要進位 如果是999的話就需要多一位
我們在回圈的時候應該逆序回圈 判斷最后一位是否是9 如果是9 的話重置為零 在繼續回圈
代碼實作：
var plusOne = function (digits){
//逆序遍歷
for (let i=digits.lenght -1;i>=0;i--){
//如果不是9 直接最后一位++ 回傳結果即可
if(digits[i] !==9){
digits[i]++;
return digits;
}else{
digits[i]= 0;//變成0之后后面不用處理 能直接跳轉到前一位加一 實作進位
}
}
// 如果全是9的時候 需要多加一位
//這里不需要單獨去判斷了 因為上面的if判斷中，如果全是9 就會回圈之后跳出for回圈
const result = [1,...digits];//創建一個新的陣列 第一位是1 后面全是0
//[1].concat(digits) 也可以使用ES5的寫法
return result;
}
17.爬樓梯（動態規劃）
描述：
解法分析：思路就是到n個臺階位置需要多少次 然后動態記錄這個點 后面在這個基礎上繼續去寫 那就要用到遞回
代碼實作：
var climbStairs = function (n){
const memo = [];
memo[1]= 1;
memo[2]= 2;
//3 = memo[1]+memo[2] 后面的回圈從3開始
for(let i =3 ; i <= n; i++){
memo[i]= memo[i-2] + memo[i-1];
}
return memo [n];
}
18、矩陣置零
描述：一個矩陣里面有0 那么把0這行和列都變成0
解法思路：（不能開新的陣列 只能使用原陣列）每一行或者一列只要有0 就把行列變成0
1.檢查并標記第一行和第一列是否有0 （firstColHasZero）和（firstRowHasZero）
2、使用第一行和第一列 來標記其余行列是否含有0
3、接下來 利用第一行和第一列的標0情況 將matrix中的數字標0
4、最后 處理第一行和第一列
如果firstColHasZero 等于true 第一列全設為0
如果firstRowHasZero 等于true ，將第一行全設為0
代碼實作：
// 矩陣置零
var setZeroes = function (matrix){
// 定義兩個變數標記第一行或者第一列是否有0 有就改變為ture最后要根據他來變化第一行列的0
let firstColHasZero = false;
let firstRowHasZero = false;
//檢查第一列是否有0
for(let i = 0; i<matrix.lenght;i++){
if (matrix[i][0] === 0){
firstColHasZero = true;
}
}
//檢查第一行是否有0
for(let i = 0; i<matrix.lenght;i++){
if (matrix[0][i] === 0){
firstRowHasZero = true;
}
}
// 使用第一行和第一列 來標記其余行列是否含有0
for(let row = 1; row < matrix.length; row ++){
for (let col = 1;col < matrix[0].length;col++){
if(matrix[row][col] === 0){
matrix[row][0] = 0;
matrix[0][rol] = 0;
}
}
}
//接下來處理第一行和第一列中的標0情況 將matrix中的數字標0
for(let row = 1; row < matrix.length; row ++){
for (let col = 1;col < matrix[0].length;col++){
if(matrix[row][0] === 0 || matrix [0] [col] === 0){
matrix[row][col] === 0;
}
}
}
// 最后 處理第一行和第一列
// 如果firstColHasZero等于true 將第一列全設為0
if(firstColHasZero){
for(let i= 0;i<matrix.length;i++){
matrix[i][0] = 0;
}
}
// 如果firstRowHasZero等于true 將第一行全設為0
if(firstRowHasZero){
for(let i= 0;i<matrix[0].length;i++){
matrix[0][i] = 0;
}
}
return matrix;
}
##19、洗掉排序鏈表的重復元素
描述：（簡單）
給定一個排序鏈表 洗掉所有元素 使得每個元素只出現一次
思路分析：
1我自己的想法：設定一個新的陣列 把元素組的每一個數遍歷進去 如果之前有重復的就不進去新的陣列 這樣就能篩選出來（不太成功哈）注意到是鏈表，
老畢想法：因為是排序好的陣列 只需要一個指標 起始位置和下一個位置比較 重復的元素就刪去設定成后面一個節點；
代碼實作：
// 洗掉排序串列鏈表中的重復元素
var deleteDuplicates = function(head){
//定義一個head 指標
let current = head;
while(current !== null && current.next !==null){
// 如果當前節點和下一個節點相同時 ，當前節點指向后面第二個節點 跳過
if(current.val === current.next.val){
current.next = current.next.next;
}else{
// 不相等就指標移動一下就OK
current = current.next;
}
}
return head;
}
19、反轉鏈表m到n之間
題目描述：反轉從位置m到n的鏈表 請使用一趟掃描完成
解題思路：
1、反轉m到n之間的鏈表
2、將反轉后的鏈表與原鏈表拼接
代碼實作：
// 反轉鏈表2
var reverseBetween = function(head,m,n){
let prev = null;
let curr = head ;
let next = head;
// 快進到m開始的位置
for (let i = 1; i < m ;i++){
prev = curr;
curr= curr.next;
}
// 占住prev和curr的位置 后面要用到
let prev2 = prev;
let curr2 = curr;
// 開始反轉
for (let i =m; i<=n;i++){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 拼接起來
if(prev2 !== null){ // m>1
prev2.next = prev;
}else{//當m等于1 的時候 沒有前端 head也改變了
head = prev;
}
curr2.next =curr;
return head;
}
20、買賣股票的最佳時期1
給定一陣列，代表每天股票的價位 獲取最大利潤 低點買進高點賣出（最后回傳最大利潤）
解題思路：賣出點應該在買入點的后面 所以我們應該是找到一個點然后找到他左邊區域的最低點算出最大利潤 區最大值 也就是遍歷每一個點 然后找到他前面的最低點 相減之后進行比較
把最大變數存在一個值中每次比較產生的利潤和這個變數比較 留下大的
代碼實作：
//g股票買賣
// prices就是給定的陣列
var maxProfit = function (prices){
// 陣列長度為0直接回傳
if(prices.length === 0){
return 0;
}
//d定義兩個變數 一個是左半邊的最小值
let minPrice = prices[0],
maxProfit = 0;
for (let i = 0; i < prices.length; i ++){
//判斷當前的價格是否小于最小的價格
if(prices[i] < minPrice){
minPrice = prices[i];
// 當前價格減去最小價格 是否大于之前存盤的最大利潤
}else if ((prices[i] - minPrice) > maxPrice){
maxPrice = prices[i] -minPrice;
}
}
return maxProfit;
}
21、買賣股票的最佳時期 2
題目描述：給定一個陣列 他的第i個元素是一只給定股票的第i天的價格，設計一個演算法 來計算你所能獲取的最大利潤， 你可以盡可能的完成多多筆交易 多次買賣一支股票
注意：每次只能持有一支股票 必須在再次買入之前出手之前的股票
思路分析：
在向上的趨勢下 從底端買入 上端賣出 下跌的時候 不買入也不賣出
所以只需要找出向上的趨勢買入 向下或者平的時候不做操作 根據節點比較左右的大小！！！
代碼撰寫：
// 股票買賣2
var maxProfit = function (prices){
if(prices.length === 0){
return 0;
}
// profit最大利潤 底端最小值valley 頂端值peak（初始化后面會變）
let profit = 0,valley = prices [0],peak = prices[0];
let i = 0;
//回圈 當前的數和陣列的后面一個數進行對比
while (i<prices.length -1){
// 第一種情況 跌平 i>=i+1 i++不用管
while(i<prices.length -1 && prices[i] >= prices[i+1]){
i++;
}
valley = prices[i];//不是跌或者平就說明是谷底把valley設定成為當前i的價格
// 第二種情況 i< i +1的時候是在漲 讓他繼續漲
while(i<prices.length -1 && prices[i] <= prices[i+1]){
i++;
}
peak = prices[i];//漲結束之后的i值 就是波峰的值 使用peak記錄
profit += peak - valley; //之前的profit和現在profit都加起來
}
return profit;
}
23 、買賣股票的最佳時期3（困難）
這道題比較困難 后面在看
描述：給定一個陣列 他的第i的元素是一支給定的股票在第i天的價格
設計一個演算法來計算你所能獲取的最大利潤，你最多可以完成兩筆交易
注意：你不能同時參與多筆交易 （你必須在再次購買簽出售掉之前的股票）
24、驗證回文串 valid PalindRome
描述：忽略費字符 空格等 還有大小寫 只判斷字母是否是回文串
解題思路：
1.用正則運算式去掉非數字和字母
2.如果字串小于2，直接回傳true，
3、定義兩個指標 一個在字串開頭 一個在字串結尾
4.簡歷一個while回圈 當left<right時執行回圈，如果在任意地點S[left] !=== s[right] return false.否則執行left++ right --，繼續執行回圈，
5、當回圈完成之后沒有return false的時候 則return false
代碼實作：
// 字串判斷：
var isPalindrome = function (s) {
// 正則字串轉變小寫
s = s.toLowerCase().replace(/[\W_]/g, "");
//小于2直接回傳
if (s.length <2){
return true;
}
// 定義left和right雙指標
let left = 0;
let right = s.length-1;
while(left<right){
if(s[left] !== s[right]){
return false;
}
left++;
right --;
}
// 如果沒有回傳false 那么后面也不用再去判斷了 直接回傳true
return true;
}
25、加油站
描述：現在一潭訓路上有N個加油站 其中第i個加油站有汽油gass[i]升，
你有一輛油箱容量無線的汽車 從第i個加油站往第i+1個加油站需要消耗汽油cost[i]升， 你從其中的一個加油站出發 開始時油箱為空 如果你可以繞環路行駛一周 則回傳出發時加油站的編號 否則則回傳-1.
解題思路：
1、每一個點都是起點 模擬去做 這就是暴力解法
2、動態規劃 繞一圈就OK了 把所有油加起來 路程消耗的油 如果所有油大于等于路程消耗的油 那么一定是有至少一個解 否則直接回傳、
重點：走不通的時候以這個點為起點 繼續完后面走這樣的話一圈就可以完事了
代碼實作：
//加油站
var canCompleteCircuit = function (gas, cost){
//初始化所有的油和路程
let totalGas = 0;
let totalCost = 0;
for(let i= 0; i < gas.length;i++){
//總的Gas和cost
totalGas += gas[i];
totalCost += cost[i];
}
//總油量小于總耗油量
if(totalGas < totalCost){
return -1;
}
//定義兩個變數
let currentGas = 0;
let start = 0;
for (let i = 0; i<gas.length; i++){
//當前點的油= 之前的油量-路程消耗的油量+這個加油站加的油量
currentGas = currentGas - cost [i] +gas [i];
// 如果油量小于0 則把currentGas設定為0 更新start的位置
if(currentGas < 0){
currentGas = 0 ;
start = i+1;
}
}
return start;
}
26、環形鏈表（判斷）
題目描述：給定一個鏈表 判斷鏈表中知否有環
為了表示給定鏈表中的環 我們使用整數pos來表好似鏈表尾連接到鏈表中的位置（索引從0開始） 如果pos是-1 則該鏈表中有環
思路：
需要兩個指標 一個快指標一個慢指標 慢指標一次走一步 快指標一次走兩步 如果相遇則就是有環 （如果到達終點則結束）
代碼實作：
// 環形鏈表判斷
var hasCycle = function(head){
//空陣列直接回傳
if(head === null){
return false;
}
let slow = head ;
let fast = head;
while(fast.next !== null && fast.next.next !==null){
//slow是一步一步走 fast是一次走兩步
slow = slow.next;
fast = fast.next.next
//如果兩個相等 就直接回傳true
if(slow === fast){
return true;
}
}
return false;
}
27、環形鏈表||
描述：給定一個鏈表 回傳鏈表開始入環的第一個節點 如果鏈表無環 則回傳null
為了表示給定鏈表中的環 我們使用整數pos來表示鏈表尾連接到鏈表中的位置 （索引從0開始） 如果pos是-1 則該鏈表中沒有環；
思路決議：
先判斷一個鏈表是否有環（可以借用1的代碼）
然后在判斷環開始的位置
快慢兩個指標 快指標兩步 慢指標一步
兩個指標相遇的時候 就說明他是環形鏈表，接下來需要做的是把快指標放回頭部 讓快指標也一步一步走，當他們相遇的時候 相遇的點 就是就是鏈表環的起始位置
演算法正確原因：弗洛伊德演算法
代碼實作：
// 環形鏈表2
var detectCycle = function (head){
if(head === null ){
return null;
}
let slow = head ;
let fast = head;
let isCycle = false;
while(fast.next !== null & fast.next.next !== null ){
//慢指標走一步 快指標走兩步
slow = slow.next;
fast = fast.next.next;
if(slow === fast){
isCycle = true;
break;
}
}
if(!isCycle){
return null;
}
//把快指標放回頭部重新開始
fast = head;
while(slow !== fast ){
slow =slow.next;
//快指標也一步一步的走
fast = fast.next;
}
return fast;
}
27、乘積最大子序列（動態規劃）
描述 ：給定一個整數陣列nums 找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）
解題思想：需要兩個新的陣列，遍歷原陣列中的了每一個數 大的放在新陣列中大陣列，小的放在新陣列中小陣列（因為可能是負的 兩個負數乘積為正）
不但要保留最大乘積的子陣列 還需要保留最小乘積的子陣列（負數）
代碼實作：
// 最大子序和乘積
var maxProduct = function(nums){
//定義兩個陣列 一個大的一個小的 初始化為原陣列的第一個
const maxProductMemo = [];
const minProductMemo = [];
maxProductMemo[0]= nums[0];
minProductMemo[0]=nums[0];
let max = nums[0];//最大值初始化也是nums的第一個數
for (let i =1;i<nums.length; i++){
// 需要比較三個數 最后一個最小的也需要去比較一下
maxProductMemo[i] = Math.max(nums[i],nums[i]*maxProductMemo[i-1],nums[i]*minProductMemo[i-1])
// 保留min乘積 后面可能也要用到
minProductMemo[i] = Math.min(nums[i],nums[i]*maxProductMemo[i-1],nums[i]*minProductMemo[i-1])
max = Math.max(max,maxProductMemo[i]);
}
return max;
}
28、尋找旋轉排序陣列中的最小值
描述：有一個被旋轉過的排序陣列 排序書序的定義就是從某個樹進行反轉到前面或者后面 在這個陣列中尋找一個最小的元素
解題思路：陣列分成兩部分 都是上升的 左半邊應該完全大于右半邊（如果被反轉過后）
1.如果陣列長度為1 回傳唯一值的一個數
2、定義兩個指標 第一個left指向陣列開頭 第二個right指向陣列結尾
3、檢查陣列是否翻轉 如果沒有 則回傳陣列里的第一個數（有可能）
4.當left小于right時 取中間作為mid進行二分搜索如果mid的左邊一個數大于mid 或者mid的右邊一個數小于mid 則回傳mid
5、否則的話 如果left所在的數小于mid 則將left右移動至mid+1的位置 砍掉左半邊
6、否則的話 將right左移值mid-1的位置（砍掉右半邊）
代碼實作：
//旋轉排序陣列中的最小值
var findMin = function (nums){
if(nums.length === 1){
return nums[0]
}
let left = 0,right = nums.length - 1;
//這種情況是沒有被反轉的陣列 直接可以回傳第一個數
if(nums[right] > nums[0]){
return nums[0];
}
while(left < right ){
let mid = Math.floor(left + (right -left)/2);
//判斷幾種情況
if(nums[mid] > nums[mid+1]){
return nums[mid +1];
}
if (nums[mid - 1] > nums[mid]){
return nums[mid];
}
if(nums[mid] > nums[left]){
left = mid +1;
}else{
right = mid +1;
}
}
}
29、相交鏈表
撰寫一個程式 找到兩個單鏈表相交的起始節點
解題思路：指定兩個指標 從a鏈表 n1和b鏈表 n2同步走到鏈表最后 對比n1是否等于n2，
走到最后之后在進行交換 n1到b鏈表開頭 n2到a鏈表開頭，最侄訓在交匯點相聚 相當與每個指標走了兩次鏈表，
代碼實作：
var getIntersectionNode = function (headA,headB){
// 不直接操作head的原因是head在后面還需要用到
let n1 = headA;
let n2 = headB;
while(n1 !== n2){
//n1走到最后在把n1放到headB走一遍
if(n1 === null){
n1 = headB;
}else{
n1 = n1.next;
}
//n2走到最后也放到headA走一遍
if(n2 === null){
n2 = headA;
}else{
n2 = n2.next;
}
}
return n1;
}
30、重復的NDA序列
描述：所有的DNA都有一系列的所謂為ACGT的核苷酸組成 列如：ACGAATTCCG. 在DNA 的研究中 識別DNA 中的重復序列有時會對研究非常有幫助
撰寫一個函式來查找字串 目標子串的長度為10 在DNA字串S中出現的次數超過一次， 超過一次的就是重復DNA 可以使用 吧出現次數超過一次的字串放到map中
代碼撰寫：
//尋找重復DNA序列
var findRepeatedDnaSequences = function (s){
// 定義一個map result和指標
const map = new Map();
const result = [];
let i = 0;
while(i+10<=s.length){
// 取出子字串
const dna = s.substring(i,i+10);
//如果map中沒有dna放入map中
if(map.get(dna) === undefined){
map.set(dna,1);//dna出現的次數是1
}else if(map.get(dna) === 1){
map.set(dna,2)//出現一次的話就把dna的次數變為2
result.push(dna)//超過兩次就加入到result中
}else{
//出現次數大于2次
map.set(dna,map.get(dna)+1);
}
i++;
}
return result;
}
31 打家劫舍
你是一個專業的小偷 計劃投錢沿街的房屋，每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通防盜系統 （所以不能偷相鄰的兩家）
給定一個代表每個房屋能存放金額的非負整數陣列 計算你在不觸動警報裝置下 能偷到的最高金額，
這周作業任務有點重，下半部分周末看完在繼續寫！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/349647.html
標籤：其他
上一篇：java版Spring Cloud+Spring Boot+mybatis+uniapp b2b2c 多商戶入駐商城品牌管理