leetcode解题思路分析（九）57-63题-蒲公英云

插入区间
给出一个无重叠的，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

本质上和上一题是一个东西，但是因为给出的已经是无重叠并且排好序的，所以最简单的是一次遍历然后按情况插入新区间

class Solution { 
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { 
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans{ intervals[0]};
        int n = intervals.size();
        for(int i = 0; i < n; i ++){ 
            if(ans.back()[1] >= intervals[i][0]){ 
                ans.back()[1] = max(intervals[i][1], ans.back()[1]);
                continue;
            }
            else{ 
                ans.push_back(intervals[i]);
                continue;
            }
        }
        return ans;
    }
};

最后一个单次长度
给定一个仅包含大小写字母和空格 ’ ’ 的字符串 s，返回其最后一个单词的长度。
如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。
如果不存在最后一个单词，请返回 0 。

本题思路很简单，从后往前遍历寻找第一个词即可。注意可能一开始就是空格，所以需要判断

class Solution { 
public:
    int lengthOfLastWord(string s) { 
        int i = s.size();
        int cnt = 0;
        bool lastWord = false;
        if (i == 0)
            return 0;       
        i--;
        while (i >= 0)
        { 
            if (s[i] == ' ')
            { 
                if (lastWord)
                    break;
                else
                    i--;
            }
            else
            { 
                lastWord = true;
                cnt++; 
                i--;                               
            }
        }
        return cnt;
    }
};

螺旋矩阵2
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

本题比之前54题螺旋矩阵要相对简单，可以参考54题得解

class Solution { 
public:
vector<vector<int>> generateMatrix(int n) { 
    vector<vector<int>> res(n, vector<int>(n));
    for(int s = 0, e = n - 1, m = 1; s<=e ; s++,e--){ 
        if(s==e) res[s][e] = m++;
        for (int j = s; j <= e-1; j++) res[s][j] = m++;
        for (int i = s; i <= e-1; i++) res[i][e] = m++;
        for (int j = e; j >= s+1; j--) res[e][j] = m++;
        for (int i = e; i >= s+1; i--) res[i][s] = m++;
    }
    return res;
}
};

第K个排列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。给定 n 和 k，返回第 k 个排列。

本题和前面的全排列其实是一个东西，所以可以用回溯剪枝的方式做，返回第k个。但是这样很浪费，因为没必要实现全排列。还有一种做法是根据n!个特点针对性求第k个。简单的说，对于特定的n位，只有(n - 1)!种解。这对每一位均适用。由此我们可以推出第k个排列每一位是多少

class Solution { 
public:
    string getPermutation(int n, int k) { 
        if (n==1) return "1";
        int m = 1;
        vector<char> num;
        for (int i = 1; i < n; i++) { 
            m *= i;
            num.push_back('0' + i);
        }
        num.push_back('0' + n);
        string s = "";
        while (true) { 
            if (k%m==0){ 
                s += num[k/m-1];
                num.erase(num.begin() + k / m - 1);
                reverse(num.begin(), num.end());
                s.insert(s.end(), num.begin(), num.end());
                return s;
            }
            else{ 
                s += num[k/m];
                num.erase(num.begin() + k / m);
                if (n==2) { 
                    s += num.back();
                    return s;
                }
                k %= m;
                n--;
                m /= n;
            }
        }
        return s;
    }   
};

旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

本题的做法是首先迭代找到尾部，然后首尾相连成环，之后K–找到新的尾部断开即可

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution { 
public:
    ListNode* rotateRight(ListNode* head, int k) { 
        if(!head||k==0)return head;
        ListNode *tail=head;
        int size=1;
        while(tail->next){ 
            size++;
            tail=tail->next;
        }
        if(k%size==0)return head;
        //首尾相连，形成环形链表
        tail->next=head;
        int m=size-k%size;
        //tail移动m步，到达新头节点的前驱节点
        while(m--)tail=tail->next;
        //tail的next节点为新的头节点，顺便断开环形链表
        ListNode *res=tail->next;
        tail->next=nullptr;
        return res;
    }
};

不同路径
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

看到求所有解，无非是回溯剪枝或者动态规划求解

class Solution { 
public:
    int uniquePaths(int m, int n) { 
        int x, y;
        int dp[m][n] = { 0};
        for (x = m - 1; x >= 0; x--)
        { 
            for (y = n - 1; y >= 0; y--)
            { 
                if ((x == m - 1 && n - y == 2) || (y == n - 1 && m - x == 2))
                    dp[x][y] = 1;
                else if (x == m - 1 && n - y > 2)
                    dp[x][y] = dp[x][y + 1];
                else if (y == n - 1 && m - x > 2)
                    dp[x][y] = dp[x + 1][y];
                else if (n - y >= 2 && m - x >= 2)
                    dp[x][y] = dp[x + 1][y] + dp[x][y + 1];
                else dp[x][y] = 1;              
            }
        }
        return dp[0][0];
    }
};

不同路径 II
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

此题和上题并无太大区别，只需要在判断中加一个障碍物判断即可

class Solution { 
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { 
        int x, y;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (m == 1 && n == 1)
        { 
            if (obstacleGrid[0][0])
                return 0;
            else return 1;
        }
        long dp[100][100] = { 0};
        for (x = m - 1; x >= 0; x--)
        { 
            for (y = n - 1; y >= 0; y--)
            { 
                if (obstacleGrid[x][y] == 1)
                    dp[x][y] = 0;
                else if ((x == m - 1 && n - y == 2) || (y == n - 1 && m - x == 2))
                    dp[x][y] = dp[m - 1][n - 1];
                else if (x == m - 1 && n - y > 2)
                    dp[x][y] = dp[x][y + 1];
                else if (y == n - 1 && m - x > 2)
                    dp[x][y] = dp[x + 1][y];
                else if (n - y >= 2 && m - x >= 2)
                    dp[x][y] = dp[x + 1][y] + dp[x][y + 1];
                else dp[x][y] = 1;              
            }
        }
        return dp[0][0];        
    }
};