LeetCode C++ブラシ問題69-72問題問題問題解

69、xの平方根
タイトル:
int sqrt(int x)関数を実現します.
xの平方根を計算して返します.ここで、xは非負の整数です.
戻りタイプが整数であるため、結果として整数の部分のみが保持され、小数の部分は切り捨てられます.
例1:
入力:4出力:2例2:
入力:8出力:2説明:8の平方根は2.82842...、戻りタイプが整数であるため、小数部は切り捨てられます.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/sqrtx著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題:
にぶん
完全なコード:

class Solution {
public:
    int mySqrt(int x) {
        int l = 0;
        int r = x;
        while(l <= x){
            long mid = (l + r) / 2;
            long temp = mid * mid;
            if(temp == x){
                return mid;
            }else if(temp > x)
            {
                if(mid - 1 >= l && (mid - 1) * (mid - 1) <= x)
                {
                    return mid - 1;
                }
                r = mid - 1;
            }else if(temp < x){
                if(mid + 1 <= r && (mid + 1) * (mid + 1) > x)
                {
                    return mid;
                }
                l = mid + 1;
            }
        }
        return 0;
    }
};

70、階段を登る
タイトル:
階段を登っているとします.屋上に着くにはn階が必要です.
毎回1つか2つの階段を登ることができます.屋上に登る方法はいくつありますか?
注:指定されたnは正の整数です.
例1:
入力:2出力:2解釈:屋上に登るには2つの方法があります.1.1次+1次2.2次例2:
入力:3出力:3解釈:3つの方法で屋上に登ることができます.1.1次+1次+1次2.1次+2次3.2次+1次
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/climbing-stairs著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題:
ダイナミックプランニング
完全なコード:

class Solution {
public:
    int climbStairs(int n) {
        //    
        vector dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i < n + 1; i ++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

71、最大サブシーケンスおよび
タイトル:
Unixスタイルでファイルの絶対パスを与えるには、それを簡略化する必要があります.あるいは、言い換えれば、それを仕様パスに変換する.
Unixスタイルのファイルシステムでは、1つのポイント(.)現在のディレクトリ自体を表します.また、2つのポイント(.)ディレクトリを上位レベル(親ディレクトリを指す)に切り替えることを示します.どちらも複雑な相対経路の構成部分であってもよい.詳細は、「Linux/Unixの絶対パスvs相対パス」を参照してください.
返されるスペシフィケーションパスは常にスラッシュ/先頭で、2つのディレクトリ名の間にスラッシュ/が1つしかないことに注意してください.最後のディレクトリ名(存在する場合)は、/で終わることはできません.また、スペシフィケーションパスは、絶対パスを表す最短文字列でなければなりません.
 
例1:
入力:「/home/」出力:「/home」説明:最後のディレクトリ名の後ろにスラッシュがないことに注意してください.例2:
入力:“/.../”出力:“/”解釈:ルートディレクトリから上位レベルへは実行できません.ルートはあなたが到達できる最上位レベルだからです.例3:
入力:「/home//foo/」出力:「/home/foo」解釈:仕様パスでは、複数の連続スラッシュを1つのスラッシュで置き換える必要があります.例4:
入力:「/a/./b/..//...../c/」出力:「/c」例5:
入力:「/a/...//.../b/.../c//.//」出力:「/c」例6:
入力:“/a//bc/d//.///.............”出力:「/a/b/c」
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/simplify-path著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題:
スタック
完全なコード:

class Solution {
public:
    string simplifyPath(string path) {
        //    
        //  "/"
        vector arr;
        string temp = "";
        for(int i = 0; i < path.size(); i++) {
            if(path[i] == '/') {
                if(temp == "" || temp == ".") {
                    temp = "";
                    continue;
                } else if(temp == "..") {
                    if(arr.size() > 0) {
                        arr.pop_back();
                    }
                } else {
                    arr.push_back(temp);
                }
                temp = "";  //  temp   
            } else {
                temp += path[i];
            }
        }

        //      
         if(temp == "" || temp == ".") {
                   
        }
        else if(temp == "..") {
            if(arr.size() > 0) {
                arr.pop_back();
            }
        } else {
            arr.push_back(temp);
        }

        string result = "";
        for(int i = 0; i < arr.size(); i++) {
            result += "/" + arr[i];
        }

        return result == "" ? "/" : result;
    }
};

72、距離の編集
タイトル:
2つの単語word 1とword 2をあげて、word 1をword 2に変換するために使用する最低限の操作数を計算してください.
1つの単語について、次の3つの操作を行うことができます.
1文字を挿入1文字を削除1文字を置換
例1:
入力:word 1="horse"、word 2="ros"出力:3解釈:horse->rorse('h'を'r')rorse->rose('r')rose->ros('e')例2:
入力:word 1="intention"、word 2="execution"出力:5解釈:intention->inention(削除't')inention->enention('i'を'e')enention->exention('n'を'x')exention->exection('n'を'c')exection->execution('u')
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/edit-distance著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題:
ダイナミックプランニング
完全なコード:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        vector> dp(n + 1, vector(m + 1, 0));

        //      ，    dp[i][0] = i
        for(int i = 1; i <= n; i ++) {
            dp[i][0] = i;
        }

        //      ，    dp[0][i] = i
        for(int i = 1; i <= m; i ++) {
            dp[0][i] = i;
        }

        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                //  word1 word2      
                if(word1[i - 1] ==  word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //       ，      、  、  ，       
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]) , dp[i - 1][j - 1]) + 1;
                }
            }
        }

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