【力扣打卡--day4】【有注释有思路】

【力扣打卡--day4】【有注释有思路】

目录

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 
思路
 
和上一题一样					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5718420.html