跟著公眾號刷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)元素之和進行調(diào)整，時間復雜度為O(n)
    還有一個O(nlogn)的算法，待補（?）可能有什么特殊的方法需要學習吧

2020.9.10

  • 螺旋矩陣 2
    明明是一道很簡單的模擬題，被我做出了高考數(shù)學最后一個大題的感覺，說到底還是細節(jié)把握的不好，編程習慣可能也不好，總之就是都不好，要多練練啊，腦子想的和動手編程的結果真的不一樣。
    我犯的幾個錯誤：
  1. 題目輸出要求的是vector，我在定義vector的時候沒有初始化，后面直接采用數(shù)組的形式進行賦值，oh～
  2. 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

2020.9.21

2020.9.24

2020.9.27

2020.9.28

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

2020.9.29

2020.9.30

數(shù)組的解題方法

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

hash:

最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容