跟著公眾號刷leetcode算法

https://github.com/youngyangyang04/leetcode-master

數(shù)組部分

2020.9.8

搜索插入位置
一道簡單的二分題目亲铡，提到有序數(shù)組，就可以用二分試一試蜘拉。我目前用的是C++统台，在評論區(qū)看到一個代碼臭觉，
```
return lower_bound(nums.begin(),nums.end(),target) - nums.begin();
```
lower_bound適用于排過序的數(shù)組卤橄，且底層算法的時間復雜度為O(n)
??與二分查找相關的三個函數(shù)警医，函數(shù)內(nèi)部使用二分查找實現(xiàn)
#include<algorithm> 前提：有序數(shù)組
1??lower_bound(起始地址乌妒，結束地址，查找元素) 左閉右開的區(qū)間猴仑，查找第一個大于等于指定元素的位置（第一個可插入的位置）审轮，若無，則返回end（超界）
2??upper_bound(起始地址辽俗，結束地址疾渣，查找元素)左閉右開，查找第一個大于指定元素的位置（最后一個可插入的位置）崖飘，若無榴捡，則返回end（超界）
3??binary_search(起始地址，結束地址朱浴，查找元素)左閉右開區(qū)間吊圾，返回bool值
移除元素
雙指針方法，沒什么特別的
刪除排序數(shù)組中的重復項
同上題翰蠢，雙指針法
長度最小的子數(shù)組
雙指針或者滑動窗口法项乒，兩個指針start、end梁沧，end遍歷整個數(shù)組檀何，求以end為最后一個元素的滿足子數(shù)組元素之和大于s的數(shù)組最小長度，start隨著滑動窗口內(nèi)元素之和進行調整廷支，時間復雜度為O(n)
還有一個O(nlogn)的算法频鉴，待補（?）可能有什么特殊的方法需要學習吧

2020.9.10

螺旋矩陣 2
明明是一道很簡單的模擬題，被我做出了高考數(shù)學最后一個大題的感覺恋拍，說到底還是細節(jié)把握的不好垛孔，編程習慣可能也不好，總之就是都不好施敢，要多練練啊周荐，腦子想的和動手編程的結果真的不一樣。
我犯的幾個錯誤：

題目輸出要求的是vector僵娃，我在定義vector的時候沒有初始化羡藐，后面直接采用數(shù)組的形式進行賦值，oh～
for循環(huán)中用于控制循環(huán)次數(shù)的變量i悯许，我保留了它仆嗦，用到下一個for循環(huán)中，卻忘記了上一個循環(huán)是因為i不滿足循環(huán)條件了才退出的先壕，把i當成是符合條件的最后一個數(shù)值進行運算瘩扼，導致數(shù)據(jù)越界，shift垃僚！
基本的思路就是一圈一圈填充集绰，我是用每一圈的寬度來控制計算坐標值，在題解區(qū)看到有人定義四個變量來控制邊界谆棺，真的很簡潔栽燕，代碼也很簡潔罕袋，需要學習～


class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n - 1, t = 0, b = n - 1;
        int[][] mat = new int[n][n];
        int num = 1, tar = n * n;
        while(num <= tar){
            for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.
            t++;
            for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
            r--;
            for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.
            b--;
            for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
            l++;
        }
        return mat;
    }
}

2020.9.11

大清早來，我決定先把“螺旋矩陣2”再寫一遍碍岔，是煩躁的一天還是開心的一天就看它的了——早上比較清醒浴讯，一遍過，開心~開始科研

二維數(shù)組并不是n*m的連續(xù)地址空間組成的

二維數(shù)組
忽然看到了一個熟悉的題目就做了一下編輯距離
一發(fā)A蔼啦，感覺自己dp基礎知識掌握的還不錯榆纽，這題有點像最長公共子串的長度
必須掌握的數(shù)組理論知識

2020.9.12

今日份睡覺和科研任務比較重

四數(shù)之和和之前做過的三數(shù)之和幾乎完全一樣
環(huán)形鏈表 II 雙指針法
環(huán)形列表需要使用雙指針法，兩指針相遇則存在環(huán)捏肢，這題可能不需要數(shù)學推導奈籽，知道快慢指針由于速度不同終將相遇即可，而對于 II 這道題需要判斷環(huán)的入口位置鸵赫，我雖然能想到雙指針衣屏，但不知道需要數(shù)學推導出相遇位置與入口位置之間的關系（吃一塹長一智，我覺得在做題的時候辩棒，如果知道了大體的方法勾拉，但方法的結束點和最終要達成的目的看似沒什么聯(lián)系，先想想貪心算法蒙一下盗温，實在不行藕赞，看看有沒有什么數(shù)學上的值的關系，當時我能手動模擬一下也好啊卖局，說不定就發(fā)現(xiàn)了斧蜕，后悔）

模擬圖

官方題解的公式我覺得有點問題，下面是我的公式：
2(F+a)=F+n(a+b)+a (n表示快指針比慢指針多走的圈數(shù))
F=n(a+b)-a=(n-1)(a+b)+b
也就是說無論n取何值砚偶，從head出發(fā)的速度為1的指針和從相遇點出發(fā)的速度為1的指針批销，一定會在入口處相遇

/*寫給自己：注意fast和low的起點必須一樣，和之前的程序有一點小小的不同染坯，之前不用考慮是否起點一致均芽，只要能相遇就行
在這里如果起點不一致的話，不能同時出發(fā)然后相遇于入口點单鹿，需要添加一些常數(shù)來補充*/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL || head->next==NULL) return NULL;
        ListNode* low=head;
        ListNode* fast=head;
        
        while(fast!=NULL && fast->next!=NULL){
            
            low=low->next;
            fast=fast->next->next;
            if(fast==low) break;
        }

        if(fast==NULL|| fast->next==NULL) return NULL;

        ListNode* p=head;
        while(p!=low){
            p=p->next;
            low=low->next;
        }
        return low;
    }
};

2020.9.15

這幾天因為科研上的一些問題掀宋，沒有做題，今天抽出點時間仲锄，準備刷leetcode的數(shù)組分類下的題目劲妙，就從簡單的開始吧。

轉置矩陣行列交換
??主要元素
摩爾投票法（默認存在眾數(shù)的情況下）本題最后要加上一個循環(huán)來進行驗證
有序數(shù)組的平方
一定不要忽略“有序”這個詞儒喊，使用雙指針法
三個數(shù)的最大乘積
貪心镣奋，排序后，最大乘積只可能出現(xiàn)在兩種情況下
存在連續(xù)三個奇數(shù)的數(shù)組
存在重復元素 II
是一個處理不好就會超時的題怀愧，O(nlogn)排序后就會超時
解決方法：k的滑動窗口侨颈，Set（hashset）
?總結：
題型：查找是否存在值為x的元素余赢，可能還需要確定它的位置
方法：map——我目前做的題不多，我認為用到map的地方都有一個相似的地方：與數(shù)組相比哈垢，map將數(shù)組的值作為索引妻柒，而將數(shù)組的下標作為map的數(shù)值，這樣查找某個元素的速度就會很快温赔。
不能簡單的用數(shù)組來實現(xiàn)蛤奢，因為測試樣例中可能有負值鬼癣，例如[-1,-1]
種花問題
模擬陶贼；另一個思路，數(shù)連續(xù)0的位置待秃，然后直接計算之間可以放多少花
翻轉圖像聽我的拜秧，直接翻
找出井字棋的獲勝者模擬

2020.9.18

?合并兩個有序數(shù)組雙指針從后往前
統(tǒng)計好三元組
數(shù)組序號轉換
拼寫單詞使用數(shù)組會比hash更快一些
二維網(wǎng)格遷移
訪問所有點的最小
斐波那契數(shù)
?矩陣冪求解這種方法需要學習一下

2020.9.21

?所有奇數(shù)長度子數(shù)組的和
思維方式很重要，考慮如何才能組成一個長度為奇數(shù)的數(shù)組

2020.9.24

至少是其他數(shù)字兩倍的最大數(shù) 除法的時候小心除數(shù)可能為0章郁，應該轉成乘法
劍指 Offer 04. 二維數(shù)組中的查找旋轉一下就像一棵二叉搜索樹
第 k 個缺失的正整數(shù)
沒什么特別的就是讓我體會到了c好快枉氮，c++寫的時間擊敗4%，c寫的擊敗100%
另一個方法：二分查找
按奇偶排序數(shù)組 II 內(nèi)存可以為O(1)
解壓縮編碼列表
兩數(shù)之和 II - 輸入有序數(shù)組
移動零

2020.9.28

美麗的早晨從刷幾道題開始暖庄；用java寫幾道簡單題

一維數(shù)組的動態(tài)和
有多少小于當前數(shù)字的數(shù)字
去掉最低工資和最高工資后的工資平均值
?? 面試題 17.04. 消失的數(shù)字有一個很巧妙的方法聊替，希望我下次可以想起來
方陣中戰(zhàn)斗力最弱的 K 行
重新排列數(shù)組
最小絕對差
玩籌碼
綴點成線

2020.9.29

查找常用字符
和為零的N個唯一整數(shù)

2020.9.30

缺失數(shù)字
公平的糖果交換
查詢后的偶數(shù)和
楊輝三角
楊輝三角 II

數(shù)組的解題方法

1、暴力再尋求優(yōu)化
2培廓、二分（或者需要先自行排序惹悄，再使用二分）
3、遞歸
4肩钠、（窗口方法）
5泣港、雙指針法（快慢指針法，兩個指針的前進速度不同价匠，前進的判斷條件不同当纱，在一個for循環(huán)中完成兩個for循環(huán)的工作量）考慮同時從左邊開始，同時從右邊開始踩窖，一左一右開始坡氯，都想一遍，不要限制思維
6洋腮、摩爾投票法
（隨著刷題持續(xù)增加）
7廉沮、hash或者數(shù)組，更換索引和數(shù)值的關系
8徐矩、貪心方法：思考如何從當前元素出發(fā)滞时，構造出符合題目條件的樣子，在這個過程中滤灯，再考慮把其他的方法（排列組合等）用進來

hash:

數(shù)組拆分 I
數(shù)組的相對排序
set: 用空間換時間坪稽，查看某個元素是否在集合內(nèi)
公平的糖果交換