算法學(xué)習(xí)——LeetCode力扣補(bǔ)充篇11

64. 最小路徑和

64. 最小路徑和 - 力扣（LeetCode）

描述

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說(shuō)明：每次只能向下或者向右移動(dòng)一步。

示例

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因?yàn)槁窂?1→3→1→1→1 的總和最小。

示例 2：

輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

提示

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

代碼解析

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size() , n = grid[0].size();
        vector<vector<int>> dp(m , vector<int>(n , 0) );
        
        dp[0][0] = grid[0][0];
        for(int i=1 ; i<m ;i++)
            dp[i][0] = dp[i-1][0] +  grid[i][0];
        
        for(int j=1 ; j<n ;j++)
            dp[0][j] =  dp[0][j-1]  +  grid[0][j];

        for(int i=1 ; i<m ;i++)
        {
            for(int j=1 ; j<n ; j++)
            {
                dp[i][j] = min( dp[i-1][j], dp[i][j-1] ) + grid[i][j];
            }
        }

        return dp[m-1][n-1];
        
    }
};

48. 旋轉(zhuǎn)圖像

48. 旋轉(zhuǎn)圖像 - 力扣（LeetCode）

描述

給定一個(gè) n × n 的二維矩陣 matrix 表示一個(gè)圖像。請(qǐng)你將圖像順時(shí)針旋轉(zhuǎn) 90 度。

你必須在 原地 旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請(qǐng)不要 使用另一個(gè)矩陣來(lái)旋轉(zhuǎn)圖像。

示例

示例 1：

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

輸入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
輸出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

代碼解析

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i=0 ; i<m ; i++)
        {
            for(int j=i ; j<n ; j++)
            {
                swap(matrix[i][j] , matrix[j][i]);
            }
        }

        for(int i=0 ; i<m ; i++)
        {
            for(int j=0 ; j<n/2 ; j++)
            {
                swap(matrix[i][j] , matrix[i][n-j-1]);
            }
        }

    }
};

169. 多數(shù)元素

169. 多數(shù)元素 - 力扣（LeetCode）

描述

給定一個(gè)大小為 n 的數(shù)組 nums ，返回其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例

示例 1：

輸入：nums = [3,2,3]
輸出：3

示例 2：

輸入：nums = [2,2,1,1,1,2,2]
輸出：2

提示

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

進(jìn)階：嘗試設(shè)計(jì)時(shí)間復(fù)雜度為 O(n)、空間復(fù)雜度為 O(1) 的算法解決此問題。

代碼解析

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> my_map;
        pair<int,int> result(0,0);
        for(int i=0 ; i<nums.size() ; i++)
        {
            my_map[nums[i]]++;
            if(my_map[nums[i]] >= nums.size()/2)
            {
                if(my_map[nums[i]] > result.second)
                {
                    result.first = nums[i];
                    result.second = my_map[nums[i]];
                }
            }
        }
        return result.first;
    }
};

394. 字符串解碼

394. 字符串解碼 - 力扣（LeetCode）

描述

給定一個(gè)經(jīng)過編碼的字符串，返回它解碼后的字符串。

編碼規(guī)則為: k[encoded_string]，表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次。注意 k 保證為正整數(shù)。

你可以認(rèn)為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號(hào)總是符合格式要求的。

此外，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù) k ，例如不會(huì)出現(xiàn)像 3a 或 2[4] 的輸入。

示例

示例 1：

輸入：s = “3[a]2[bc]”
輸出：“aaabcbc”

示例 2：

輸入：s = “3[a2[c]]”
輸出：“accaccacc”

示例 3：

輸入：s = “2[abc]3[cd]ef”
輸出：“abcabccdcdcdef”

示例 4：

輸入：s = “abc3[cd]xyz”
輸出：“abccdcdcdxyz”

提示

1 <= s.length <= 30
s 由小寫英文字母、數(shù)字和方括號(hào) ‘[]’ 組成
s 保證是一個(gè) 有效 的輸入。
s 中所有整數(shù)的取值范圍為 [1, 300]

代碼解析

class Solution {
public:
    string decodeString(string s) {
        string res;
        stack <int> nums;
        stack <string> strs;
        int num = 0;
   
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                num = num * 10 + s[i] - '0';
            }
            else if(s[i] >= 'a' && s[i] <= 'z')
            {
                res += s[i];
            }
            else if(s[i] == '[') //將‘[’前的數(shù)字壓入nums棧內(nèi)， 字母字符串壓入strs棧內(nèi)
            {
                nums.push(num);
                num = 0;
                strs.push(res); 
                res.clear();
            }
            else //遇到‘]’時(shí)，操作與之相配的‘[’之間的字符，使用分配律
            {
                int times = nums.top();
                nums.pop();
                for(int j = 0; j < times; ++ j)
                    strs.top() += res;
                res = strs.top(); //之后若還是字母，就會(huì)直接加到res之后，因?yàn)樗鼈兪峭患?jí)的運(yùn)算
                                  //若是左括號(hào)，res會(huì)被壓入strs棧，作為上一層的運(yùn)算
                strs.pop();
            }
        }
        return res;
    }
};

240. 搜索二維矩陣 II

240. 搜索二維矩陣 II - 力扣（LeetCode）

描述

編寫一個(gè)高效的算法來(lái)搜索 m x n 矩陣 matrix 中的一個(gè)目標(biāo)值 target 。該矩陣具有以下特性：

每行的元素從左到右升序排列。
每列的元素從上到下升序排列。

示例

示例 1：

輸入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
輸出：true

示例 2：

輸入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
輸出：false

提示

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素從左到右升序排列
每列的所有元素從上到下升序排列
-109 <= target <= 109文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-856329.html

代碼解析

常規(guī)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size() , n = matrix[0].size();
        int max_point = 1;

        for(int i=0 ; i<min(m,n) ;i++)
        {
            if(matrix[i][i] > target) break;
            max_point = i;
        }

        for(int i=0 ; i < max_point ; i++)
        {
            for(int j=max_point ; j<n ; j++)
            {
               if(matrix[i][j] == target) return true;
            }
        }

        for(int i=max_point ; i<m ; i++)
        {
            for(int j=0 ; j<n ; j++)
            {
               if(matrix[i][j] == target) return true;
            }
        }

        return false;
    }
};

路徑優(yōu)化

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size() , n = matrix[0].size();
        int x = 0 , y = n-1;
     
        while( x < m && y >= 0)
        {
            // cout<<matrix[x][y]<<endl;
            if(matrix[x][y] == target) return true;
            else if(matrix[x][y] > target) y--;
            else if(matrix[x][y] < target) x++;
        }

        return false;
    }
};

到了這里，關(guān)于算法學(xué)習(xí)——LeetCode力扣補(bǔ)充篇11（64. 最小路徑和、48. 旋轉(zhuǎn)圖像 、169. 多數(shù)元素、394. 字符串解碼、240. 搜索二維矩陣 II ）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！