Leetcode(3)-Summary Ranges

228 Summary Ranges For example, given [0,1,2,4,5,7], return [“0->2”,”4->5”,”7”].

class Solution {
    // 
    string format(int begin, int end)  
    {  
        char buffer[32];  
        if (end == begin)  
        {  
            sprintf(buffer, "%d", begin);  
        }else{  
            sprintf(buffer, "%d->%d", begin, end);  
        }  
        return string(buffer);  
    } 

    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;  
        if (nums.size()<1)  
            return result; 
        int begin, end;  
        begin = nums[0];
        end = nums[0];
        for(int i=1; i<nums.size(); i++)
        {
            if(nums[i] == end || nums[i] == end+1)
                end = nums[i];
            else
            {
                result.push_back(format(begin, end));
                begin = nums[i];
                end = nums[i];
            }
        }
        // ， 
        result.push_back(format(begin, end)); 
        return result;
    }
};

62 Unique Pathsダイナミックプランニング、左上から右下へ;ここでvector 2 Dベクトルの使用に注意してください.

int path[101][101];
for(int i = 0; i < 101; i ++) { for(int j = 0; j < 101; j ++) { path[i][j] = 1; } }

また、前の行を先頭とし、前の列を先頭とする情報を毎回必要とするだけで、1次元配列で前の行の情報、すなわちres[i]+=res[i-1]を格納することもできる

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> path(m, vector<int>(n, 1));
        for(int i = 1; i < m; i ++)
        {
            for(int j = 1; j < n; j ++)
            {
                path[i][j] = path[i-1][j] + path[i][j-1];
            }
        }
        return path[m-1][n-1];
    }
};

63.Unique Paths IIは依然として動的に計画されているが、障害物のため、ロボットは毎回2つの方向の選択があるわけではない.初期化プロセスを追加し、動的計画プロセスでの計算ポリシーを修正します.

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        int i,j;
        vector<vector<int>> path(m, vector<int>(n, 0));
        // ： path=0， 1
        for (i = 0; i < m; i ++) 
        {
            if (obstacleGrid[i][0] == 0) 
                path[i][0] = 1;
            else
                break;
        }
        for (j = 0; j < n; j ++) 
        {
            if (obstacleGrid[0][j] == 0)
                path[0][j] = 1;
            else 
                break;
        }
        // ： path=0
        for(i = 1; i < m; i ++)
        {
            for(j = 1; j < n; j ++)
            {
                if(obstacleGrid[i][j] == 1)
                    path[i][j] = 0;
                else
                    path[i][j] = path[i-1][j] + path[i][j-1];
            }
        }
        return path[m-1][n-1];
    }
};

PS:他の人の答えでは、三目演算子を使用するとコードを簡略化できることがわかりました.

// 。。
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int i,j;
        vector<vector<int> > path(obstacleGrid.size(), vector<int>(obstacleGrid[0].size()));
        // 
        path[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for (i = 1; i < path.size(); i ++) 
            path[i][0] = obstacleGrid[i][0] == 1 ? 0 : path[i-1][0];
        for (j = 1; j < path[0].size(); j ++) 
            path[0][j] = obstacleGrid[0][j] == 1 ? 0 : path[0][i-1];
        // 
        for(i = 1; i < path.size(); i ++)
            for(j = 1; j < path[0].size(); j ++)
                path[i][j] = obstacleGrid[i][j] == 1 ? 0 : path[i-1][j] + path[i][j-1];

        return path[path.size()-1][path[0].size()-1];
    }
};

120 triangle

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        for (int i = triangle.size() - 2; i >= 0; --i)
            for (int j = 0; j <= i; ++j)
                triangle[i][j] += min(triangle[i+1][j+1],triangle[i+1][j]);
        return triangle[0][0];
  }
};

5.最長回文サブストリングsのうち最長回文ストリングはsの逆転s’とsの最長連続共通サブストリングあるいは動的計画を用いてO(N^2)を解くか、Define P[i,j]←true iff the substring Si...Sj is a palindrome,otherwise false.P［i,j］←(P［i＋1,j−1］and Si＝Sj)またはサブストリングを遍歴し,各アルファベットを中心として両側にO(N^2)を拡散した.

class Solution {
public:
    //   
    string expandAroundCenter(string s, int c1, int c2) {  
        int l = c1, r = c2;  
        int n = s.length();  
        while (l >= 0 && r <= n-1 && s[l] == s[r]) {  
            l--;  
            r++;  
        }  
        return s.substr(l+1, r-l-1);  
    }  

    string longestPalindromeSimple(string s) {  
        int n = s.length();  
        if (n == 0) return "";  
        string longest = s.substr(0, 1);  // a single char itself is a palindrome 
        for (int i = 0; i < n-1; i++) {  
            string p1 = expandAroundCenter(s, i, i); //  
            if (p1.length() > longest.length())  
                longest = p1;  

            string p2 = expandAroundCenter(s, i, i+1);//  
            if (p2.length() > longest.length())  
                longest = p2;  
        }  
        return longest;  
    }  
};