1.排序2.位运算（快速幂）3.bfs4.贪心5.双指针6.贪心7.bfs8.链表9.dp10.dp
1.排序
class Solution {
public:
vector> groupAnagrams(vector& strs) {
unordered_map> hash;
//异构字符串都能按升序排列成同一字符串啊
vector> res;
for(auto& s:strs){
string t=s;
sort(t.begin(),t.end());
hash[t].push_back(s);//同一类异构字符串
}
for(auto& s:hash){
res.push_back(s.second);
}
return res;
}
};
思路
因为同一类型异构字符串其实都是一组相同字母的组合排列，所以只需找一个他们都能转换过去的形式来表示就能统计了。所以可按升序来做比较好，因为sort能排序字符串字母。这样就能归类了，同一类的字符串sort后都是相同的，可采用map来存储。
2.位运算（快速幂）
class Solution {
public:
double myPow(double x, int n) {
typedef long long LL;
double res=1;
bool is_minus=false;
if(n<0) is_minus=true;//符号
for(LL i=abs(LL(n));i;i>>=1){//每次n都去掉最后一位
if(i&1) res*=x;//指数n的最后一位是1，
//n的二进制表示相应的一位就是1，也就是乘上底数的相应的指数次方
//相当于讲n拆成2进制表示，x的n次方就是x的2进展表示次方合起来
x*=x;
}
if(is_minus) return 1/res;//负数
return res;
}
};
思路
将n拆成2进制表示，因为n是指数，要让它相加，只有是res结果每次是相乘啊，快速幂。
3.bfs
class Solution {
public:
vector spiralOrder(vector>& ma) {
vector res;
int n=ma.size();
if(!n) return res;
int m=ma[0].size();
vector> st(n,vector(m));//防重走
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//走到边界就换方向
for(int i=0,x=0,y=0,d=0;i
思路
走到边界就换方向，bfs，向量。
4.贪心
class Solution {
public:
bool canJump(vector& nums) {
for(int i=0,j=0;i
思路
每次要走一步先看看能跳到当前这一步吗，能就更新跳跃能力。
5.双指针
class Solution {
public:
vector> merge(vector>& a) {
vector> res;
if(a.empty()) return res;
sort(a.begin(),a.end());//按起点排序
int l=a[0][0],r=a[0][1];//第一段
for(int i=1;ir){//要到的区间起点比之前的尾要大，那之前的无法合并了，装好之前的段
res.push_back({l,r});
l=a[i][0],r=a[i][1];//双指针换到新来的一段区间上
}
r=max(r,a[i][1]);//r每次都看能不能更大，因为只要尾够大就能合并其他区间进段
}
res.push_back({l,r});//最后一段
return res;
}
};
思路
每次走都能看看嘴能不能继续增大，嘴装不下了就吞再继续塞新来的东西在嘴上。
6.贪心
class Solution {
public:
vector> insert(vector>& a, vector& b) {
vector> res;
int k=0;
while(k
思路
分三段，分情况讨论，插入区间那段就是贪心
7.bfs
class Solution {
public:
vector> generateMatrix(int n) {
vector> res=vector>(n,vector(n));
if(!n) return res;
vector> st(n,vector(n));
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
for(int i=1,x=0,y=0,d=0;i<=n*n;i++){
res[x][y]=i;
st[x][y]=true;
int a=x+dx[d],b=y+dy[d];
if(a<0||b<0||a==n||b==n||st[a][b]){
d=(d+1)%4;
a=x+dx[d],b=y+dy[d];
}
x=a,y=b;
}
return res;
}
};
思路
bfs走到边界就换方向，同前面某题。
8.链表
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head==NULL) return NULL;
ListNode* r;
int n=0;
for(auto i=head;i;i=i->next){
n++;//算共有几个节点
r=i;
}
int k0=k%n;//旋转几个点
if(!k0) return head;
ListNode* l=head;
for(int i=0;inext;
}
r->next=head;//屁股连头
ListNode* res=l->next;//旋转后的头
l->next=NULL;//旋转后的尾断尾
return res;
}
};
思路
画图自己看吧
9.dp
class Solution {
public:
int uniquePaths(int m, int n) {
if(!n) return 0;
vector> f(n,vector(m));
for(int i=0;i
思路
太简单了，dp
10.dp
class Solution {
public:
int uniquePathsWithObstacles(vector>& o) {
int n=o.size();
if(!n) return 0;
int m=o[0].size();
vector> f(n,vector(m));
for(int i=0;i
思路
和上一题一样
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）