LeetCode力ボタンブラシ問題記録熱問題HOT 100(62,64,70,72,75)問題+アルゴリズム分析+Cpp解答
GitHubリンク:https://github.com/WilliamWuLH/LeetCode
いいと思うなら⭐StarとFork❤
62.Unique Paths
動的計画:
各ロケーションがそのロケーションに到達する可能性のあるパスの数を保存します.
64.Minimum Path Sum
動的計画:
各位置に到達する最小経路と、最終的に目標位置に到達する最小経路とを記録する.
70.Climbing Stairs
動的計画:
各階段に登る経路の数を記録し、層数が2以上である場合、その層の経路数は前の層の経路数と前の2層の経路数に等しい.
72.Edit Distance
動的計画:
難しそうに見えますが、実は解法がかなり巧みです.大きな問題が小さな問題になります.最適なサブ構造の性質です.
いずれかの文字列の長さが0の場合、答えは別の文字列の長さです.
2つの文字列の現在の文字について説明します.現在の2文字が同じであれば、何の操作も必要ないので、このときの編集数は、この2文字を入れる前の2文字列の編集数です. 現在の2文字が異なる場合、操作が必要であることを説明するには、このときの3つの操作(挿入文字dp[i][j-1]、文字dp[i-1][j]を削除し、置換文字dp[i-1][j-1])の中で編集数が最も少ないものを、このときの2つの文字列の編集数として選択する必要がある.
75.Sort Colors
統計色数+再配置:
3つのポインタ:
1つのポインタは0の末尾を指し、1つのポインタは2の先頭を指し、1つのポインタは遍歴する.
いいと思うなら⭐StarとFork❤
62.Unique Paths
動的計画:
各ロケーションがそのロケーションに到達する可能性のあるパスの数を保存します.
class Solution {
public:
int uniquePaths(int m, int n) {
int map[m][n];
for(int i=0; i64.Minimum Path Sum
動的計画:
各位置に到達する最小経路と、最終的に目標位置に到達する最小経路とを記録する.
class Solution {
public:
int minPathSum(vector>& grid) {
int m = grid.size(), n = grid[0].size();
for(int i=0; i 70.Climbing Stairs
動的計画:
各階段に登る経路の数を記録し、層数が2以上である場合、その層の経路数は前の層の経路数と前の2層の経路数に等しい.
class Solution {
public:
int climbStairs(int n) {
int path[n+1];
path[0] = 1;
path[1] = 1;
for(int i=2; i<=n; i++){
path[i] = path[i-1] + path[i-2];
}
return path[n];
}
};
72.Edit Distance
動的計画:
難しそうに見えますが、実は解法がかなり巧みです.大きな問題が小さな問題になります.最適なサブ構造の性質です.
いずれかの文字列の長さが0の場合、答えは別の文字列の長さです.
2つの文字列の現在の文字について説明します.
class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.length();
int len2 = word2.length();
int dp[len1+1][len2+1];
for(int i=0; i<=len1; i++)
dp[i][0] = i;
for(int i=0; i<=len2; i++)
dp[0][i] = i;
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
if(word1[i-1] == word2[j-1])
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]))+1;
}
}
return dp[len1][len2];
}
};
75.Sort Colors
統計色数+再配置:
class Solution {
public:
void sortColors(vector& nums) {
int count[3] = {0,0,0};
int len = nums.size();
for(int i=0; i 3つのポインタ:
1つのポインタは0の末尾を指し、1つのポインタは2の先頭を指し、1つのポインタは遍歴する.
class Solution {
public:
void sortColors(vector& nums) {
int len = nums.size();
int left = 0, right = len-1, curr = 0;
while(curr <= right){
if(nums[curr] == 0)
swap(nums[curr++], nums[left++]);
else if(nums[curr] == 2)
swap(nums[curr], nums[right--]);
else
curr++;
}
}
};