LeetCode hot-100 简单and中等难度，21-30.

程序员文章站 2024-01-02 20:22:40

46. 全排列难度中等829给定一个没有重复数字的序列，返回其所有可能的全排列。示例:输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]class Solution {public: unordered_map visit; vector tmp; void get(int n,int...

46. 全排列

难度中等829

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

class Solution {
public:
    unordered_map<int,bool> visit;
    vector<int> tmp;
    void get(int n,int sum,vector<int> nums,vector<vector<int>> &ans){
        if(n>sum) return;
        if(n==sum){
            ans.push_back(tmp);return;
        }
        for(int i=0;i<nums.size();i++){
            if(visit[nums[i]]==false){
                tmp.push_back(nums[i]);
                visit[nums[i]]=true;
                get(n+1,sum,nums,ans);
                visit[nums[i]]=false;
                tmp.pop_back();
            }
        }

    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        for(int i=0;i<nums.size();i++) visit[nums[i]]=false;
        get(0,nums.size(),nums,ans);
        return ans;
    }
};

48. 旋转图像

难度中等517

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

先转置再翻转。

 void rotate(vector<vector<int>>& matrix) {
        //简单！！
        //从i,j变成了j ,n-1-i怎么办
        //不能用新的矩阵！！！
        int n=matrix.size();
        //三角的形状注意一些
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        //每一行直接转动..
        for(int i=0;i<n;i++){
            for(int j=0;j<n/2;j++)
                swap(matrix[i][j],matrix[i][n-j-1]);
        }
    }

49. 字母异位词分组

难度中等420收藏分享切换为英文关注反馈

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

//排序+map表即可。
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map <string,vector<string> > m;
        for(string& s : strs)
        {
            string t = s;
            sort(t.begin(),t.end());
            m[t].push_back(s);   //t为单词的按顺序排列，作为key值，m[t]则为该单词的异位词构成的vector，作为value值
        }
        for(auto& n : m)                //n为键和值组成的pair
            res.push_back(n.second);
        return res;
    }
};

优化解法

对26个字母分别赋予对应的质数值，因为不同的质数和必定为不同的数字结果，所以可以用来作为map的key值
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map <double,vector<string> > m;
        double a[26]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
        for(string& s : strs)
        {
            double t = 1;
            for(char c : s)
            t *= a[c - 'a'];

            m[t].push_back(s);          //t为单词对应的质数乘积，m[t]则为该单词的异位词构成的vector
        }
        for(auto& n : m)                //n为键和值组成的pair
            res.push_back(n.second);
        return res;
    }
};

作者：zrita
链接：https://leetcode-cn.com/problems/group-anagrams/solution/c-map-stringvectorstring-z-by-zrita/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

53. 最大子序和

难度简单2271收藏分享切换为英文关注反馈

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxn=nums[0];
        vector<int> dp(nums.size());
        for(int i=0;i<nums.size();i++){
            dp[i]=nums[i];
        }
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            if(dp[i]>maxn) maxn=dp[i];
        }
        return maxn;
    }
};

55. 跳跃游戏

难度中等763收藏分享切换为英文关注反馈

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

//这种方法所依据的核心特性：如果一个位置能够到达，那么这个位置左侧所有位置都能到达。 想到这一点，解法就呼之欲出了~
class Solution {
public:
    //贪心！！！！！
    //实时维护每次能跳到的最远位置
    bool canJump(vector<int>& nums) 
{
	int k = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (i > k) return false;
		k = max(k, i + nums[i]);
	}
	return true;
}

};

56. 合并区间

难度中等541收藏分享切换为英文关注反馈

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

示例 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] 可被视为重叠区间。

排序加个双指针，双指针能合并的更快些~

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> ans;
        if(intervals.size()<=1) return intervals;
        // 以下是一个一个合并，等到结尾or无法合并时push_back.
        /*
        int x=intervals[0][0];
        int y=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            int tx=intervals[i][0];
            int ty=intervals[i][1];
            if(tx>y){
                ans.push_back({x,y});
                if(i==intervals.size()-1) ans.push_back({tx,ty});
                x=tx;y=ty;
            }else{
                x=min(x,tx);
                y=max(y,ty);
                if(i==intervals.size()-1) ans.push_back({x,y});
            }
        }
        */
        for(int i=0;i<intervals.size();){//注意没有动作。
            //区间左端点确定为intervals[i][0],寻找右端点
            int t=intervals[i][1];
            int j=i+1;
            while(j<intervals.size()&&intervals[j][0]<=t){
                t=max(t,intervals[j][1]);j++;
            }
            ans.push_back({intervals[i][0],t});
            i=j;
        }
        return ans;
    }
};

62. 不同路径

难度中等634收藏分享切换为英文关注反馈

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

LeetCode hot-100 简单and中等难度，21-30.

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

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

示例 2:

输入: m = 7, n = 3
输出: 28

class Solution {
public:
    //其实是排列组合啦！
    int uniquePaths(int m, int n){
        vector<vector<int>> v(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(i==1&&j==1) v[i][j]=1;
                else if(i==1||j==1) v[i][j]=1;
                else v[i][j]=v[i-1][j]+v[i][j-1];
            }
        }
        return v[m][n];
    }
};
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int>dp(n, 1);
        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
};

64. 最小路径和

难度中等614收藏分享切换为英文关注反馈

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        for(int i=0;i<m;i++){
            for(int j =0;j<n;j++){
                if(i==0&&j==0) continue;
                if(i==0) grid[i][j]+=grid[i][j-1];
                else if(j==0) grid[i][j]+=grid[i-1][j];
                else grid[i][j]=min(grid[i-1][j],grid[i][j-1])+grid[i][j];
            }
        }
        return grid[m-1][n-1];
    }
};

70. 爬楼梯

难度简单1181收藏分享切换为英文关注反馈

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        vector<int> v(n+1);
        v[1]=1;
        v[2]=2;
        for(int i=3;i<=n;i++) v[i]=v[i-1]+v[i-2];
        return v[n];
    }
};

本文地址：https://blog.csdn.net/qq_42671442/article/details/107873515

LeetCode hot-100 简单and中等难度，21-30.