我要评论难度中等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;
}
};
难度中等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]);
}
}
难度中等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） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。难度简单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;
}
};
难度中等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;
}
};
难度中等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;
}
};
难度中等634收藏分享切换为英文关注反馈
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个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];
}
};
难度中等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];
}
};
难度简单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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论