基礎(chǔ)算法總結(jié)

一、鏈表問題

鏈表問題一定要進行舉例畫圖，輔助思考！
使用快慢指針遍歷鏈表。因為鏈表無法得知長度，所以嘗試用這種方法來達到某種效果（鏈表中點，檢測環(huán)等）。
警惕指針丟失?？梢允褂靡恍┡R時變量來存儲next指針，在鏈表插入節(jié)點時應(yīng)先連接后邊節(jié)點，避免斷鏈表造成指針丟失。
設(shè)置虛擬節(jié)點（哨兵），簡化實現(xiàn)難度。對于插入和刪除等操作，往往需要一個額外的指針來記錄其前面的節(jié)點（前驅(qū)節(jié)點）。
單鏈表遞歸實現(xiàn)。對一些依賴于后面節(jié)點才可以完成的操作，使用遞歸的方式來解決。
注意留意常見的邊界條件處理：鏈表為空，鏈表有一個或者兩個節(jié)點，頭結(jié)點（例如旋轉(zhuǎn)鏈表）和尾節(jié)點。

環(huán)問題

1、141判斷鏈表有環(huán)：【快慢指針】
2、環(huán)的長度：【快慢指針判斷有還，并記錄相交的點，再遍歷計數(shù)計算環(huán)入口/環(huán)長度】
3、142環(huán)的入口節(jié)點：【快慢指針，再從頭遍歷鏈表】
4、287尋找重復(fù)數(shù)：弗洛伊德算法找環(huán)入口

重構(gòu)鏈表

1、206反轉(zhuǎn)鏈表：【迭代 遞歸】【1->2->3->?】 --->> 【?<-1<-2<-3】

鏈表反轉(zhuǎn).jpg
鏈表反轉(zhuǎn)(遞歸實現(xiàn)).jpg

2、92反轉(zhuǎn)鏈表II：
3、24交換鏈表中的相鄰節(jié)點
4、143重排鏈表
5、61旋轉(zhuǎn)鏈表

拆分/組合

1、86分隔鏈表：
2、21歸并兩個有序鏈表：
3、鏈表求和
4、兩鏈表的交點
5、排序鏈表：【147插入、148歸并、快速】

刪除類型

1、83刪除已排好序鏈表的重復(fù)元素
2、203刪除鏈表元素

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return nil
    }
    dummnyhead := &ListNode{
        Val:-1,
        Next:head,  // 創(chuàng)建一個指向head的虛擬頭節(jié)點
    }               // 否則，第一個節(jié)點的刪除會有問題
    curr := dummnyhead
    for curr.Next != nil {
        if curr.Next.Val == val {
            curr.Next = curr.Next.Next
        } else {
            curr = curr.Next
        }
    }
    return dummnyhead.Next
}

3、19刪除鏈表的倒數(shù)第 n 個節(jié)點

二、dp動態(tài)規(guī)劃

動態(tài)規(guī)劃，無非就是利用歷史記錄，來避免我們的重復(fù)計算。而這些歷史記錄，我們得需要一些變量來保存，一般是用一維數(shù)組或者二維數(shù)組來保存。下面我們先來講下做動態(tài)規(guī)劃題很重要的三個步驟，

第一步驟：定義數(shù)組元素的含義，上面說了，我們會用一個數(shù)組，來保存歷史數(shù)組，假設(shè)用一維數(shù)組 dp[] 吧。這個時候有一個非常非常重要的點，就是規(guī)定你這個數(shù)組元素的含義，例如你的 dp[i] 是代表什么意思？

第二步驟：找出數(shù)組元素之間的關(guān)系式，我覺得動態(tài)規(guī)劃，還是有一點類似于我們高中學(xué)習(xí)時的歸納法的，當(dāng)我們要計算 dp[n] 時，是可以利用 dp[n-1]，dp[n-2].....dp[1]，來推出 dp[n] 的，也就是可以利用歷史數(shù)據(jù)來推出新的元素值，所以我們要找出數(shù)組元素之間的關(guān)系式，例如 dp[n] = dp[n-1] + dp[n-2]，這個就是他們的關(guān)系式了。而這一步，也是最難的一步，后面我會講幾種類型的題來說。

最優(yōu)子結(jié)構(gòu)，把大的問題拆分成小的問題。
第三步驟：找出初始值。學(xué)過數(shù)學(xué)歸納法的都知道，雖然我們知道了數(shù)組元素之間的關(guān)系式，例如 dp[n] = dp[n-1] + dp[n-2]，我們可以通過 dp[n-1] 和 dp[n-2] 來計算 dp[n]，但是，我們得知道初始值啊，例如一直推下去的話，會由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我們必須要能夠直接獲得 dp[2] 和 dp[1] 的值，而這，就是所謂的初始值。

由了初始值，并且有了數(shù)組元素之間的關(guān)系式，那么我們就可以得到 dp[n] 的值了，而 dp[n] 的含義是由你來定義的，你想求什么，就定義它是什么，這樣，這道題也就解出來了。

二、直接上leetcode真題

  • LC2、無重復(fù)字符的最長子串

    int lengthOfLongestSubstring(string s) {
    int start = 0;  // 1、當(dāng)前處理的子串，看看子串，是否有重復(fù)的字符
    int max = 0;

    unordered_map<char, int> hash;  //用來記錄 當(dāng)前字符的 下標(biāo)位置。
    for (int end = 0; end < s.size(); end++) {
        char tmp = s[end];
        // 2、從start 到 end 子串 如果有重復(fù)字符，需要更新start
        if ( hash.find(tmp) != hash.end() && hash[tmp] >= start) {
            start = hash[tmp] + 1;
        }
        hash[tmp] = end;
        // 3、查看最大長度，是否更新.  start 到 end  
        if(end - start + 1 > max) {
            max = end - start + 1;
        }   
    }
    return max;
}

  • LC5、最長回文子串

    string longestPalindrome(string s) {
        int len = s.size();
        if (len == 0) return s;
    
        bool dp[len][len];
        //定義一個二維數(shù)組bool dp[len-1][len-1]來記錄遍歷字符串所得的狀態(tài)，
        //  dp[left][right]為true表示"從left到right的子串為回文串"，false表示不是回文串
        int start = 0, end = 0;
        //初始化二維數(shù)組，單個字符為回文串，所以定義dp[i][i] = true
        for (int i = 0; i <len; i++)
            dp[i][i] = true;
        for (int right = 1; right < len; right++)
            for (int left = 0; left < right; left++)

                if (s[right]==s[left] && (right-left==1 || dp[left+1][right-1])) {
       //dp[left][right] = 
       //(s[right]==s[left] && (right-left==1 || dp[left+1][right-1])) ? 
       //                   true : false
       // s[right]==s[left] && (right-left==1)       情況一：bb 這種
       // s[right]==s[left] && dp[left+1][right-1]   情況二：bab 
       //  如果我們已經(jīng)知道 “bab” 是回文，那么很明顯，“ababa” 一定是回文，
       //   因為它的左首字母和右尾字母是相同的。
                    dp[left][right] = true;
                    if (right-left > end-start) {
                        start = left; 
                        end = right;
                    }
                    continue;
                } else {
                    dp[left][right] = false;
                }     
        return s.substr(start, end-start+1);
    }

  • LC53、連續(xù)子串和最大

    int maxSubArray(int* nums, int numsSize){
    //1、定義dp[i] 以第i個數(shù)字結(jié)尾的連續(xù)子串的和。作為狀態(tài) 
    int *dp = NULL;
    dp = (int *)malloc(sizeof(int) * numsSize);
    memset(dp, 0, sizeof(int) * numsSize);
    //2、初始化零界值
    dp[0] = nums[0];

    for(int i = 1; i < numsSize; i++){
        dp[i] = (dp[i-1] + nums[i] > nums[i]) ? (dp[i-1] + nums[i]) : nums[i];    
        // max(dp[i-1] + nums[i], nums[i]);
    }
    int maxNum = dp[0];
    for(int j = 0; j < numsSize; j++){
        if(dp[j] > maxNum)
            maxNum = dp[j];
    }
    return maxNum;
}

    int maxNum(int a, int b){
    if (a >= b)
        return a;
    else
        return b;
}
int maxSubArray(vector<int>& nums) {
    int sum = 0x80000001;    //最小的32位整數(shù)
    int max = 0;
    for (int i = 0; i < nums.size(); i++) {
        max = maxNum(max + nums[i], nums[i]);
        if (max > sum) {
            sum = max;
        }
    }
    return sum;
}

  • LC64、編輯距離

    /*
對一個單詞進行如下三種操作：插入一個字符\刪除一個字符\替換一個字符
將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
case:
輸入：word1 = "intention", word2 = "execution"
輸出：5
解釋：
intention -> inention (刪除 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')
*/
int minDistance(string word1, string word2) {
    int size1 = word1.size();
    int size2 = word2.size();
    // int dp[i][j] 表示字符串 word1 的長度為 i，字符串 word2 的長度為 j 時，
    //              將 word1 轉(zhuǎn)化為 word2 所使用的最少操作次數(shù)為 dp[i] [j]。
    //1、插入一個字符
    //2、刪除一個字符
    //3、替換一個字符
    int dp[size1+1][size2+1] = {0};
    for(int i = 1; i <= size1; i++){
        dp[i][0] = i;
    }
    for(int j = 1; j <= size2; j++){
        dp[0][j] = j;
    }

    for(int i = 1; i <= size1; i++){
        for(int j = 1; j <= size2; j++){
            // // 關(guān)系一：
            // if(word1[i] == word2[j]){
            //     dp[i][j] = dp[i-1][j-1];
            // }else{
            //     關(guān)系二: dp[i][j-1]表示在word1尾部插入一個字母， 
            //     dp[i-1][j]表示在word1尾部刪除一個字母,(相當(dāng)于在word2尾部插入一個字母)，
            //     dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
            // }
            // // 關(guān)系一：
            dp[i][j] = min(dp[i][j-1], dp[i-1][j])+1;                                           //插入 刪除 時
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + (word1[i-1]==word2[j-1] ? 0:1));             //替換時
        }
    }
    return dp[size1][size2];
}

  • LC152、乘積最大子序列

    int maxProduct(vector<int>& nums) {
    // 1、dp[i] : 表示以以下標(biāo)i結(jié)束的子序列，的最大值和最小值。
    vector<int> dpMax(nums.size(), 0);
    vector<int> dpMin(nums.size(), 0);

    //2、初始化邊界
    dpMax[0] = nums[0];
    dpMin[0] = nums[0];
    int ans = nums[0];
    for(int i = 1; i < nums.size(); i++){
        dpMax[i] = (dpMax[i-1] * nums[i] >= dpMin[i-1] * nums[i]) ? dpMax[i-1] * nums[i] : dpMin[i-1] * nums[i];
        dpMax[i] = dpMax[i] >= nums[i] ? dpMax[i] : nums[i];

        dpMin[i] = (dpMax[i-1] * nums[i] < dpMin[i-1] * nums[i]) ? dpMax[i-1] * nums[i] : dpMin[i-1] * nums[i];
        dpMin[i] = dpMin[i] < nums[i] ? dpMin[i] : nums[i];
        if(ans < dpMax[i]){
            ans = dpMax[i];
        }
    }
    return ans;
}

  • LC673、最長遞增子序列的個數(shù)

    int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();
    if(n == 0){
        return  0;
    }
    int LIS = 1;
    vector<pair<int, int> > dp(n, {1, 1});
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[i].first < dp[j].first + 1) {
                    dp[i] = {dp[j].first + 1, dp[j].second};
                } else if (dp[i].first == dp[j].first + 1) {
                    dp[i].second += dp[j].second;
                }
            }
        }
        if(LIS < dp[i].first){
            LIS = dp[i].first;
        }
    }
    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (dp[i].first == LIS) {
            res += dp[i].second;
        }
    }
    return res;
}

  • LC300、最長遞增子序列<<給你一個整數(shù)數(shù)組 nums ，找到其中最長嚴(yán)格遞增子序列的長度>>。

    int lengthOfLIS(vector<int>& nums) {
    int size = nums.size();
    if(size < 2){
        return size;
    }
    int maxLen = 1;
    vector<int> dp(size, 1);  //1、 DP[i] 定義以i為結(jié)尾的最長上升子序列的長度
    // 2、從第二個元素開始處理
    for(int i = 1; i < size; i++){
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j] && dp[i] < dp[j] + 1){
                dp[i] = dp[j] + 1;
            }
        }
        if(maxLen < dp[i]){
            maxLen = dp[i];
        }
    }

    return maxLen;
}

  • LC120、三角形最小路徑和

    /*
輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出：11
解釋：如下面簡圖所示：
   2
  3 4
 6 5 7
4 1 8 3
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11）。
*/
int minimumTotal(vector<vector<int>>& triangle) {
    int m = triangle.size();
    if(m == 0) {
        return 0;
    }
    int dp[m] = {0}; 
    //1. 動態(tài)規(guī)劃：構(gòu)造一個三角形 dp記錄當(dāng)前行從上往下的和
    //每個元素只能走到它的下方或者右下方
    //也就是每個元素只能來自它的上方或者左上方
    //注意特殊情況：左腰上的元素，只能來自它的上方；右腰只能從左上方來。
    dp[0] = triangle[0][0];     // 2. 邊界處理
    for(int i = 1; i < m; i++){           // 依次處理每一行，
        dp[i] = triangle[i][i] + dp[i-1]; // 每一行的第一個元素。
        for(int j = i - 1; j > 0; j--)  //為了避免數(shù)據(jù)覆蓋，從后往前填充
            dp[j] = triangle[i][j] + min(dp[j-1], dp[j]);
        dp[0] += triangle[i][0];
    }
    int ans = dp[0];
    for(int i = 1; i < m; i++)
        ans = min(dp[i], ans);
    return ans;
}

  • LC121、賣買股票的最佳時機

    /*
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，
     在第 5 天（股票價格 = 6）的時候賣出，
     最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。
*/
/*
思路還是挺清晰的，還是DP思想：
記錄【今天之前買入的最小值】
計算【今天之前最小值買入，今天賣出的獲利】，也即【今天賣出的最大獲利】
比較【每天的最大獲利】，取最大值即可
*/
int maxProfit(vector<int>& prices) {
    int dayNum = prices.size();
    if(dayNum <= 0){
        return 0;
    }
    int buyIn = prices[0];           // 定義一個最值，做為買入股票的最佳時機。
    int max = 0;                     // 定義為最大的收益
    for(int i = 1; i < dayNum; i++){
        if(buyIn > prices[i - 1]){    // 買入價如果不是最大值的話，要更新買入價
            buyIn = prices[i - 1];
        }
        if(prices[i] - buyIn > max){  // 收入最大化
            max = prices[i] - buyIn;
        }
    }
    return max;
}

  • LC128 最長連續(xù)序列

    /*
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數(shù)字連續(xù)序列是 [1, 2, 3, 4]。它的長度為 4。
*/
int longestConsecutive(vector<int>& nums) {
    if (nums.size() < 2) {
        return nums.size();
    }
    sort(nums.begin(), nums.end());                              // 先排序
    nums.erase(unique(nums.begin(), nums.end()), nums.end());    // 去掉重復(fù)元素

    int res = 1;
    int n = nums.size();
    vector<int> dp(n, 1);
    // dp 問題： dp[i] 表示以當(dāng)前元素結(jié)尾的連續(xù)序列的長度。
    for (int i = 1; i < n; i++) {
        if (nums[i-1] + 1 == nums[i]) {                         
            dp[i] = dp[i-1] + 1;
        }
        res = max(res, dp[i]);
    }
    return res;
}

// 最終結(jié)果
var result [][]int

// 回溯核心
// nums: 原始列表
// pathNums: 路徑上的數(shù)字
// used: 是否訪問過
func backtrack(nums, pathNums []int, used[]bool) {
    // 結(jié)束條件：走完了，也就是路徑上的數(shù)字總數(shù)等于原始列表總數(shù)
    if len(nums) == len(pathNums) {
        tmp := make([]int, len(nums))
        // 切片底層公用數(shù)據(jù)，所以要copy
        copy(tmp, pathNums)
        // 把本次結(jié)果追加到最終結(jié)果上
        result = append(result, tmp)
        return
    }

    // 開始遍歷原始數(shù)組的每個數(shù)字
    for i:=0; i<len(nums); i++ {
        // 檢查是否訪問過
        if !used[i] {
            // 沒有訪問過就選擇它，然后標(biāo)記成已訪問過的
            used[i] = true
            // 做選擇：將這個數(shù)字加入到路徑的尾部，這里用數(shù)組模擬鏈表
            pathNums = append(pathNums, nums[i])
            backtrack(nums,pathNums,used)
            // 撤銷剛才的選擇，也就是恢復(fù)操作
            pathNums = pathNums[:len(pathNums) -1]
            // 標(biāo)記成未使用
            used[i] = false
        }
    }
}

func permute(nums []int) [][]int {
    var pathNums []int
    var used = make([]bool, len(nums))
    // 清空全局?jǐn)?shù)組（leetcode多次執(zhí)行全局變量不會消失）
    result = [][]int{}
    backtrack(nums, pathNums, used)
    return result
}

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, result, 0);  //從第一個開始處理
        return result;
    }
    void backtrack(vector<int> & nums, vector<vector<int>> & result, int loc){
        if (loc == nums.size()) {
            result.push_back(nums);   //所有數(shù)據(jù)都處理完成，退出
            return;
        }
        // 從下標(biāo)位置0 開始處理到 size - 1    loc下標(biāo)是nums的指針
        //                                   i 下標(biāo)零時一個排列的下標(biāo)
        for (int i = loc; i < nums.size(); i++) {
            if (loc != i) {
                swap(nums[i], nums[loc]);    //使用交換的話，就不用標(biāo)記這個元素使用過了
            }
            backtrack(nums, result, loc + 1);

            if (loc != i) {
                swap(nums[loc], nums[i]);
            }
        }
    }
};

判斷一顆樹是否是平衡二叉樹

題思路
后續(xù)遍歷+DFS

dfs計算思路：

對于空結(jié)點，深度為0
當(dāng)前深度是左右子樹深度的最大值+1， 有效情況直接返回深度
一旦發(fā)現(xiàn)左右子樹的深度差異超過1，則認(rèn)為無效，返回-1
一旦發(fā)現(xiàn)返回是-1， 直接返回-1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return dfs(root) != -1;
    }

    int dfs(TreeNode* node)
    {
        if (node != nullptr)
        {
            int left = dfs(node->left);
            if (left == -1)
            {
                return -1;
            }
            int right = dfs(node->right);
            if (right == -1)
            {
                return -1;
            }

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

相關(guān)閱讀更多精彩內(nèi)容

  • 設(shè)原始數(shù)據(jù)規(guī)模為n，需要采樣的數(shù)量為k 先選取數(shù)據(jù)流中的前k個元素，保存在集合A中； 從第j（k + 1 <= j...
    Impossible安徒生閱讀 335評論 0贊 0
  • 和分治法一樣，動態(tài)規(guī)劃（dynamic programming）是通過組合子問題而解決整個問題的解。 分治法是將問...
    Teci閱讀 5,782評論 0贊 70
  • 一趟結(jié)束后能夠確定一個元素的最終位置的排序方法有： 簡單選擇排序、快速排序、冒泡排序、堆排序 穩(wěn)定性定義：排序前后...
    Zak1閱讀 330評論 0贊 0
  • 排序算法幾種分類方式： 1，穩(wěn)定排序和不穩(wěn)定排序 如果a==b， 當(dāng)排序之前a在b的前面，排序后，a仍然在b...
    fly_ever閱讀 495評論 0贊 0
  • 夜鶯2517閱讀 128,087評論 1贊 9

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