不同路径

问题描述

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

例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:
输入: m = 7, n = 3
输出: 28

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths

思路

动态规划
当i==0或者j==0时，dp[i][j]=1;
当i>1或者j>1时，dp[i][j]=dp[i][j-1]+dp[i+1][j];
最后返回dp[m-1][n-1]即可。

题解

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

旋转链表

问题描述

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

示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list

思路

• 首先将链表存到vector vec中。
• 对特殊情况进行判断，链表为空，vec.size()==0) return nullptr，向右移动0步，直接return head
• 按照题目要求，将移动后的元素存到一个新的vector tmp中
• 根据tmp建立一个新的链表，并返回其头节点

题解

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        vector<int> vec;
        ListNode *cur = head;
        while (cur != nullptr) {
            vec.push_back(cur->val);
            cur = cur->next;
        }
        if(vec.size()==0)  return nullptr;
        if(k==0) return head;
        k = k % (vec.size());
        vector<int> tmp;
        for (int i = vec.size()-k; i < vec.size(); i++) {
            tmp.push_back(vec[i]);
        }
        for (int i = 0; i <vec.size()-k; i++) {
            tmp.push_back(vec[i]);
        }
        ListNode *p = nullptr;
        ListNode *newnode;
        for (int i = 0; i < tmp.size(); i++) {
            if (p == nullptr) {
                p=new ListNode(tmp[i]);
                newnode=p;
            } else{
                p->next= new ListNode(tmp[i]);
                p=p->next;
            }
        }
        return newnode;
    }
};

下一个排列

问题描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation

思路

使用库函数

题解

class Solution {
public:
    void nextPermutation(vector<int> &nums) {
        if (next_permutation(nums.begin(), nums.end())) {
        }
    }
};

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals

思路

• 首先对特殊情况进行判断，int n=intervals.size(),如果n==0或者n==1那么无需合并，直接返回就可以了
• 然后对intervals进行排序，排序规则为 按照开始位置从小到大进行排序，如果两个元素的开始位置相等，那么结束位置从大到小排序。
• 准备工作做完后，开始正式合并区间。 ret.push_back({intervals[0][0],intervals[0][1]})先在返回结果ret中插入第一个元素，否则第二个无法比较。
• 如果intervals中待合并元素的开始位置intervals[i][0]<ret.back()[1]那么判断，它结束的位置大于等于ret.back()[1]，那么将ret.back()[i]更新为intervals[i][1],否则不做操作。
• 如果intervals中待合并元素的开始位置intervals[i][0]>=ret.back()[1],那么直接将其插入到ret中即可
• 最后，返回ret。

题解

class Solution {
public:
    vector<vector<int>> ret;
    static bool cmp(const vector<int> &a,const vector<int> &b){
        if(a[0]==b[0]){
            return a[1]>b[1];
        } else return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n=intervals.size();
        if(n==0||n==1) return intervals;
        sort(intervals.begin(),intervals.end(),cmp);
        ret.push_back({intervals[0][0],intervals[0][1]});
        for(int i=0;i<n;i++){
            if(ret.back()[1]>=intervals[i][0]){
                if(ret.back()[1]<=intervals[i][1]){
                    ret.back()[1]=intervals[i][1];
                }
            } else{
                ret.push_back({intervals[i][0],intervals[i][1]});
            }
        }
        return ret;
    }
};

不同路径 II

问题描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii

思路

int n = obstacleGrid.size(); int m = obstacleGrid[0].size();
long long dp[n][m];注意这里用long long，用int可能会爆掉
dp[i][j]为到达obstacleGrid[i][j]的路径条数，如果obstacleGrid[i][j]==1,即obstacleGrid[i][j]为障碍物，dp[i][j]置为0；否则obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1]；
要注意先将边界dp[i][j]单独拿出来计算。

题解

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
        int n = obstacleGrid.size();
        if (n == 0) return 0;
        int m = obstacleGrid[0].size();
        long long dp[n][m];
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 1; i < n; i++) {
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
        }
        for (int j = 1; j < m; j++) {
            dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j - 1];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 :dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[n-1][m-1];
    }
};