精华内容
下载资源
问答
  • 刷题

    2021-03-04 10:59:35
    刷题 刷那么多题目,如果没有记录就等于白刷,真正弄懂一题,胜过copy十题。刷题记录,不定时更新,大概 转载请注明出处 poj 3169 差分约束 spfa 差分约束组 最短路 笔记: spfa 跑最短路可以判断是否存在负环和...

    刷题

    刷那么多题目,如果没有记录就等于白刷,真正弄懂一题,胜过copy十题。刷题记录,不定时更新,大概
    转载请注明出处
    

    poj 3169

    差分约束 spfa 差分约束组 最短路
    笔记:
    spfa
    跑最短路可以判断是否存在负环和是否连通。但跑一遍spfa只能判断1~n是否连通,而不能判断是否没有负环。
    因为当图不连通的时候,只访问了图的一部分,另一部分的负环无法检测。
    如果要检测是否存在负环,需要设置一个超级源,跑一边。
    这里容易设陷阱,输出存在负环(-1)的级别高于图不连通(-2),如果没有注意到,会掉坑里。
    差分约束组建图
    求1~n的最大值,小于等于号。
    x1-x2<=w 则x1到x2有一条值为w的边,w可为负数
    求1~n的最小值,大于等于号。
    x1-x2>=w,则x1到x2有一条值为w的边,跑最远路。
    

    题目大意:

    有一群牛排队,每只牛有一个编号,牛的排队顺序由编号确定,但在X轴的位置不确定。
    比如:1号牛在0点 2号牛在3点,3、4号牛在7点,5号牛在12点……
    现在给出一些限制条件:
    x  y d1
    x和y牛最远距离不超过d1
    x y d2
    x和y牛最近距离不小于d2
    求:
    1号牛和N号牛的最远距离
    如果不可行 输出-1
    如果1号牛和N号牛的距离任意 输出-2
    其他:输入可行的最远距离
    

    解题思路:

    牛的编号从x1、x2 ……xn从小到大排列
    根据x1和x2牛最远距离不超过d1可以写出不等式
    x2-x1<=d1
    x1-x2<=-d1
    设x2到x1的距离为d1,x1到x2的距离为-d1
    同理根据x和y牛最近距离不小于d2,可以列出两个距离。得到差分约束组。
    利用差分约束求最远(近)解的思路,求得答案。
    注意:不可行:出现负环
    任意:最大距离为0x3f3f3f3f3f

    代码:

    https://pastebin.ubuntu.com/p/MV2Pj835Yq/

    CodeForces 1295D

    最大公因数,欧拉函数,欧拉函数性质,最大公因数性质
    笔记:欧拉函数性:
    

    题目大意

    给出两个数a,m,求有多少个x,x∈(0,m),满足gcd(a,m)==gcd(a+x,m)
    

    数据范围:0<a<m<=1010

    解题思路

    题目抽象化,一般化
    a<=y<a+m,gcd(y,m)==gcd(a,m)==k 问有多少个y?
    根据公约数的性质
    1,gcd(y,m)==k,可变为gcd(y/k,m/k)==1
    a'=a/k 向上取整
    b'=(a+m)/k 向上取整。
    y'=y/k,m'=m/k
    2,[a,b)中y'的个数gcd(y',m')==1。
    3,用m'的质因子去筛选[a,b]中的数,考虑容斥问题。
    
    具体化 0<x<m,
    因为gcd(a,b)==gcd(a-b,b) (a>b)
    所以gcd(a+x,m)==gcd((a+x)%m,m)==k
    此题中的[a,b)也变成了[0,m/k];
    即:求[0,m/k]中与m/k互质的数
    因此变为了关于欧拉函数
    
    

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0kAUxmae-1614826768248)(https://bkimg.cdn.bcebos.com/formula/ba40ed514646510df8a1033ff30701aa.svg)]

    代码:

    https://pastebin.ubuntu.com/p/zYS88b4zMs/

    Fibonacci again and again

    博弈 sg函数 Nim博弈
    

    题目大意:

    两个博弈,有三堆石头,每堆不超过1000.
    每次只能从一堆中取走斐波那契数的石头
    直到不能取的人输。
    

    解题思路:

    用sg函数求解
    

    代码:

    https://pastebin.ubuntu.com/p/rbRT77yk67/

    Gym - 236916C

    线段树 维护 区间最大连续和 更新 区间连续和 单点修改 区间输入坑 a,b a>b
    

    题目大意:

    每一个点有一个值,一共有[1,n]个点。
    每次询问给出a,b 问区间[a,b](或[b,a])中最长的连续和
    

    做法:

    难点在于维护线段树每个节点的区间最大连续和
    node {
    	sum:区间长度
    	llagre:包含左端点的最大连续和
    	rlagre:包含右端点的最大连续和
    	large:区间的最大连续和
    	lt,rt:左右子树
    }
    更新:
    区间最大值lagre=max(lt.large/*左子树最大值*/,rt.large/*右子树最大值*/,lt.rlagre+rl.large/*包含区间中点的最大值*/)
    区间左端点最大值llarge=max(lt.llarge/*左子树左端点最大值*/,lt.sum+rt.llagre/*左端点最大值包含区间中点*/)
     区间右端点最大值llarge=max(rt.rlarge/*右子树右端点最大值*/,rt.sum+lt.rlagre/*右端点最大值包含区间中点*/)
     查询:
     查询的时候,每次利用到的lt,rt的信息不知一个,所以返回的不是数值,而是返回一个节点。沿用更新
    

    代码

    Ubuntu Pastebin

    LibreOJ - 2130

    树链剖分 dfs序 树结点值动态改变 
    

    题目大意

    给一棵树数结点值只有0,1,有两种操作,
    第一种,加:给一个结点,把从根到该结点的所有结点变为1,问变了多少个结点
    第二种,减:给一个结点,把该节点到这棵树的叶子之间的结点全部变为0,问变了多少个结点。
    

    解题思路

    用树链剖分,操作包裹两种
    第一种加:从根结点到选定结点的一条链上全部置为1, 树链剖分完成
    第二种减,选定结点的所有子数结点全部置为0,同时先查询1的个数,dfs 子树在同一段区间内
    

    代码

    https://pastebin.ubuntu.com/p/4MypCP9Yj4/

    树剖大毒瘤 150行调bug一小时

    CodeForces - 983A

    二进制 多进制 进制转换 分数 gcd 最大公约数 互质 无限小数 用gcd 求质因数 a的质因数是否是b的质因数 两个数拥有相同质因子
    

    题目大意

    给出一个分数a/b 问是否可以被k进制在有限位表示
    比如1/3 不能在10进制中表示infinity
    1/4呢一在10进制中表示finity
    

    解题思路

    根据进制小数转换方式
    

    a/b=x1/21+x2/22+x3/23……+xn/2n:如果a/b可以被表示则可以找到这些x。
    思考一下,也就是1/b 可以被表示,a 是什么无关紧要。只要不是0(0一定能被表示)
    在对右边通分一下变成了:1/b=(y1+y2+y3……+yn)/2n,转换一下:b=(2n)/(y1+y2+y3……+yn),所以2n是b倍数,那么只要找到这个2n就解决了,或者判定这个2n是否存在就可以了
    举例思考:如果b是3 就不能存在2n满足是3的倍数 ,但可以存在6n是3的倍数 ,b是25,则10n可以是b的倍数:

    b=5X5 而10n=(2X5)n,只要n=2,就会有两个因子5,所以b可以被表示

    思路1:

    只要b的所有质因子是进制k的因子。代码:前面约分省略。

    int ans=1;//判断是否满足
    for(ll i=2;i*i<=b;i++){//枚举i,直到为质因数
        if(b%i==0){//找到b的质因子
            if(k%i!=0){//不是k的质因子
                ans=0;break;
            }
            while(b%i==0)b/=i;//降低接下来搜索范围
        }
    }
    if(b>1&&k%b!=0){ans=0;}//补一刀
    

    卡在了test 10,超时了。

    思路2:

    优化:不去枚举i,先预处理所有的质数,得出质数数组prime[],但只枚举1~2e5+10以内的字数,因为所给的1018太大了。

    int ans=1;//判断是否满足
    for(int i=0;i<cnt&&prime[i]<=b;i++){//枚举质因子
        if(b%prime[i]==0){//找到b的质因子
            if(k%prime[i]!=0){//不是k的质因子
                ans=0;break;
            }
            while(b%prime[i]==0)b/=prime[i];
        }
    }
    if(b>1&&(k%b!=0)){ans=0;}//补一刀
    

    也卡在了test 10 ,超时,又翻车了。

    思路3

    优化:之后选着了去做别的题,第三,四题,转换思路,做完之后,灵光一闪,可不可以用gcd求出k和b的最大公约数,每次用b除以他,直到b除到1(满足)或者公约数为1,不唯一(不满足)

    k=-1;
    while(k!=1&&b!=1){//直到b除到1(满足)或者公约数为1,不唯一(不满足)
        k=gcd(max(b,c),min(b,c));
        b/=k;
    }
    if(b==1)……
    

    卡在了test 13 晕死了。决定去看答案

    思路4

    答案和我最后的思路是一样的,但又进一步优化了

    k=-1;
    while(b!=1){//直到b除到1(满足)或者公约数为1,不唯一(不满足)
        k=gcd(max(b,c),min(b,c));
        if(k==1)break;//当为k==1的时候,为了防止下面进入死循环,先推出
        while(b%k==0)b/=k;//一次去掉多组一样的质因子
    }
    if(b==1)……
    

    终于过了

    完整代码:

    https://pastebin.ubuntu.com/p/TCKF5D6Nmg/

    CodeForces - 962B

    排座位 简单思维题
    

    题目大意

    又一串座位***...*...
    *:已经有人坐了 .:没有人坐。现在有a,b两组人,分别有a,b个。同组人座位不能相邻,问可以坐下人(a+b)有多少?
    

    解题思路

    三种情况
    *.*:一个座位连续x,应该让人数多的组坐这个位置,为了防止后面人数:3a4b *.*...... :*a*abab.b不如*b*ababab好
    *..*:两个座位连续xy:怎么放都一样
    *...*:三个座位连续xyx:其实变成了第一种情况,让多的人当x
    

    分析直到a和b其实互换名称。只要将多的命名为a,那么久可以简化代码量。

    代码:

    https://pastebin.ubuntu.com/p/T5W58JwWWY/

    WA4发原因

    ans没有初始化,在本机调试的时候竟然得出了正确答案,导致卡了好久,心疼。习惯不好,定义时一定要初始化提醒自己

    CodeForces - 962C

    贪心 排列组合 平方数 广度搜索。平方数判定
    

    题目大意

    给出一个数2X10^9以内(保证无前导零),每次删掉一个数,称为一次操作。要把这个数变成一个平方数比如25,625,问最少要经过多少次操作
    比如:数10025 答案为2 10025-->1005-->100
    

    解题思路

    第一种

    枚举所有平方数,用平方数去测试是不是在所给的数的可能通过某种方式达到。
    复杂度10^5*(分解和比对的时间)sqrt(10^9)≈10^5
    

    第二种

    根据所给的数,分解后重构,枚举所有操作,第一次9种不同的操作,第二次8种……
    复杂度10!*(分解和重组的时间)==3628800*(分解和重组的时间)
    

    现在分析,好像第一种更快,比赛的我选择了第二种,绝对是脑抽了,但还好过来:用广度搜索做。

    第二种ac代码

    https://pastebin.ubuntu.com/p/JPNsrNRxfw/

    WA了一发

    原因判断是否是平方数的时候

    float sq=sqrt(now);
    if(sq-(int)sq==0){//是平方数}//应该是那里了的浮点误差导致了WA
    修改后:
    ll sq=sqrt(now);
    if(sq*sq==now){}//这么做避免了浮点误差,然后就过了
    

    CodeForces - 962D

    构造 1248游戏变化 思维 map数据结构
    

    题目大意

    给出一组数[3,4,1,2,2,1,1],当出现两个相同的数字的时候,左边的去掉,右边变成两倍,问最后剩下的数组是什么样的。
     [3,4,1,2,2,1,1] → [3,4,2,2,2,1] → [3,4,4,2,1] → [3,8,2,1].
     n<150000, 1<=ai<10^9
    

    解题思路

    如果每次寻找一组,肯定会超时,而且 2 1 1 可以变为 2 2 ->4,像是消去游戏一样
    定义一个数组num[maxn],记录所有输入的数据,然后用个map[num[i]]=tp,记录之前未出现过的数字,如果当前数字的map已经被填了,那么就说明有两个相同的数字,更新:
    循环查看mp[num[i]]直到不再出现
    num[mp[num[i]]]=0(删掉前面的数),map[num[i]]=0(num[i]消去出现证明);num[i]*=2(num[i]翻倍);
    不再出现之后
    mp[num[i]]=i(记录新出现的数)
    复杂度O(n*ln(k))
    

    代码:

    https://pastebin.ubuntu.com/p/v9BPt5ksPs/

    E - Create The Teams

    思维 组合 构造
    

    题目大意

    有n个人组队,每一个人有一个价值x,求可能的最大队伍数(队伍人数不能为0)
    队伍满足:队伍人数*队伍所有人中的最小价值xmin<k
    给出n k
    x1 x2 x3 …… xn
    

    解题思路

    如果说某个人的能力值但与k ,他完全可以一个人组队1*x>k
    其他人的能力值小于k:从大到小根据价值排列 y1 y2 y3 ……yn
    y1*1<k 那么尝试[y1 y2] 2*y2? >k:组队成功 <k:继续拉下一个人 3*y
    组队成功之后队伍人数变为0 从下一个数开始组队。
    这种方式保证了,每次选择不会变劣。
    

    代码:

    https://pastebin.ubuntu.com/p/qQ6RM6M2CS/

    WA了一发

    看错题意,队伍人数 the number of programmers in the team, 把the number【队伍人数】 理解成了 skill number【队伍每个人的能力者。】
    英语不行

    为0)
    队伍满足:队伍人数*队伍所有人中的最小价值xmin<k
    给出n k
    x1 x2 x3 …… xn

    
    ### 解题思路
    
    

    如果说某个人的能力值但与k ,他完全可以一个人组队1x>k
    其他人的能力值小于k:从大到小根据价值排列 y1 y2 y3 ……yn
    y1
    1<k 那么尝试[y1 y2] 2y2? >k:组队成功 <k:继续拉下一个人 3y
    组队成功之后队伍人数变为0 从下一个数开始组队。
    这种方式保证了,每次选择不会变劣。

    
    ### 代码:
    
    https://pastebin.ubuntu.com/p/qQ6RM6M2CS/
    
    ### WA了一发
    
    看错题意,队伍人数 the number of programmers in the team, 把the number【队伍人数】 理解成了 skill number【队伍每个人的能力者。】
    英语不行 
    
    
    展开全文
  • 刷题刷题总结

    2021-03-11 22:10:18
    C++ - 刷题错误总结 文章目录C++ - 刷题错误总结前言一、数据结构与算法1.单链表总结 前言 这是一个错题本,将刷题中犯的一些错误总结下来。 一、数据结构与算法 1.单链表 C语言写链表 //链表销毁 void ...

    刷题总结



    前言

    这是一个错题本,将刷题中犯的一些错误总结下来。文章会不断更新,欢迎收藏转发。


    一、刷题原则(每天刷多少、按照什么顺序、要不要看答案、刷题建议)

    LeetCode、NowCode刷题,要按什么顺序刷,每道题刷几遍,每道题目刷到什么程度。我阅读了大量资料,同时一边刷题一边总结经验,将自己的整理经验记录下来,供自己日后查阅,也分享给大家。

    1.每天刷多少
    每天刷多少道题视自己的时间而定,不同难度的题目对时间消耗有很大区别,但至少每天一道,让自己保持手感,并且持续积累。切记,重在坚持。
    2.按照什么顺序
    不要按照默认的顺序。
    可以按照题目类型去刷,在没有掌握题目类型的情况下,一个类型刷三五道直到掌握,掌握相应方法后,就间歇性的刷这个类型1的题目。
    3.要不要看答案,自己做多久做不出来就看答案,做出来了要不要看答案
    第一遍做题的目的是为了见大量题型,积累做题思路,所以十几二十分钟没有思路就可以看答案,看答案可以浏览几个效率高,点赞多的答案,掌握稳定解法,积累优秀解法。做出来的题目也建议看答案,花几分钟浏览一下常用的思路,遇到好的思路、知识盲区就积累下来。
    4.参考链接

    5.刷题建议
    首先上结论:刷完200常见题,每道题都能保证 20min内bug-free写出暴力解 + 20min内bug-free写出(次优解 / 最优解)就非常稳了

    我觉得题数完全没用处
    对算法的理解&熟练度 / 周赛成绩更能说明面试表现

    我就刷了160题 (https://leetcode.com/yiyangiliu/ )
    但是我周赛最好成绩是1.2k/11k(对应中国站450名左右)
    别的周赛平均做出2道,名次[1.5k-3.5k]/10k吧

    找实习时面了很多家,有三家出的题没见过(腾讯 滴滴 字节),有一家出了hard题(滴滴)(btw这道hard写了20min),都写出来了,最后从了方向最喜欢的字节。
    我觉得攀比刷题数真的是个误区,从来不是刷题多=nb,而是面试能做出来=nb。

    如果训练的话,应该这样练习:限时20min,不能写出bug-free代码就算不会。明天继续尝试
    (以上也是我的刷题方法)
    因为此时如果在面试,你和面试官已经大眼瞪小眼20分钟了,要多尴尬有多尴尬

    再说一下时间分配吧,我一般刷题半下午+半晚上吧,有时候上午也刷刷。

    以上说的当然不是为了卷或鸡汤,因为我在数量这一方面其实挺“失败”的,我这样刷了两个月才刷到160题,其中还包括6次周赛一天4题的“跃进”,如果去掉打周赛做的题,为了面试刷的题可能低于130道。

    结果就是俩月130题,平均每天2题稍多点,这速度已经弟弟得不行了。

    但是其实无所谓,因为我的刷题方法比较“solid”,并且我周赛成绩不错,所以我在找工之前就比较有安全感。我觉得面试题不会比周赛第二/三题更难,结果也确实如此。

    二、还没看答案题目

    2.1 不会做没看答案

    2.2 做了没看答案

    三、牛客

    1. JZoffer错误

    • JZ14 链表中倒数第k个结点
      正确思路
      网络思路:双指针,一根指针先走k步(边走边判断是否为空,因为链表长可能小于k),最后两根指针一起走,前面那根指针为空时后面的指针所指即为所求 。
      我的思路:第一次循环获取链表长度 Len,将倒数第k个转化为整数第 Len-k+1 个,顺向去找,直到达到位置。
      提交错误
      assert(pHead);
      这行代码导致如下错误,去掉这行代码即可
      运行错误:请检查是否存在数组、列表等越界非法访问,内存非法访问等情况
      a.out: ./solution.h:22: ListNode *Solution::FindKthToTail(ListNode *, int): Assertion `pHead’ failed.

    • JZ15 反转链表
      总结
      指针就是指向数据的一个标志,本身并没有数据的内存空间,但通过指针可以操作数据,改变数据结构关联关系。使用指针时要注意指针赋值的先后关系,避免对一个指针操作时造成后续无法操作的情况。

    例如删除链表头结点时,先让指针指向下一位置,避免指针找不到链表
    SLinkList* p; //p指向了一个链表
    SLinkList* cur = p;
    p = p->_pNext;
    free(cur);
    cur = NULL;
    return p;
    
    • JZ55 链表中环的入口结点
    **** 第一次编写时的错误记录
        SListNode* EntryNodeOfLoop(SListNode* pHead) {
            SListNode* cur1 = pHead;
            vector<SListNode*> saveV;
            while(cur1){
                for(int isV=0;isV<saveV.size();isV++){
                    if(saveV[isV]==cur1){return cur1;}
                    ///错误的保存方式,根本无法进入循环
                    if(isV==saveV.size()-1)
                    	{saveV.push_back(cur1);}
                }
                cur1 = cur1->_pNext;
            }
            return NULL;
        }
    
    **** 修改后
        SListNode* EntryNodeOfLoop(SListNode* pHead) {
            SListNode* cur1 = pHead;
            vector<SListNode*> saveV;
            while(cur1){
                for(int isV=0;isV<saveV.size();isV++){
                    if(saveV[isV]==cur1){return cur1;}
                }
                ///将添加移动到这里
                saveV.push_back(cur1);
                cur1 = cur1->_pNext;
            }
            return NULL;
        }
        
    **** 网络解答 一
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        {
            unordered_set<ListNode*> st;
            while (pHead) {
                if (st.find(pHead) == st.end()) {
                    st.insert(pHead);
                    pHead = pHead->next;
                }
                else {
                    return pHead;
                }
            }
            return nullptr;
        }
    };
    
    **** 网络解答 二(偏数学)
    初始化:快指针fast指向头结点, 慢指针slow指向头结点
    让fast一次走两步, slow一次走一步,第一次相遇在C处,停止
    然后让fast指向头结点,slow原地不动,让后fast,slow每次走一步,当再次相遇,就是入口结点。
    理解方法,在C点快慢指针相差一圈,且快指针走了两圈,慢指针走了一圈;而慢指针又是从头结点出发,此时慢指针距节点入口距离就是头结点至节点入口距离。
    
    

    在这里插入图片描述

    • 容器里保存的是变量的值而不是变量,变量变化(甚至变量不复存在)时,容器中对应的值不发生变化
    //例一
    int a;
    vector<int> save;
    a=1;
    save.push_back(a);
    a=2;
    save.push_back(a);
    //此时,save里面保存的是[1, 2];
    
    //例二
    vector<int> save;
    forint i=0;i<5;i++{
    	int a;
    	a=i;
    	save.push_back(a);
    }
    //循环结束后,a不复存在,但容器中的值仍然存在,为[1, 2, 3, 4, 5]
    	
    
    • JZ48_不用加减乘除做加法
    不会做
    
    参考官方思路
    	无进位和运算就是按位异或结果,进位就是与运算结果但是需要左移一位,因为进位影响下一位的运算。
    所以s = a + b,其实就是无进位和+进位的结果。
    算法步骤:
    	计算a和b的无进位和,和进位
    	如果进位不为0,则说明a+b的结果等于无进位和+进位,此时,把无进位和作为a,进位作为b,继续计算
    	如果进位等于0, 说明此时a+b的结果就等于无进位和,返回无进位和即可。
    
    题解
        int Add(int num1, int num2) {
    
            int he = num1^num2;
            int jw = (num1&num2)<<1;
    
            if(jw==0)
                return he;
            return Add(he, jw);
        }
    
    • JZ47 求1+2+3+…+n
      题目:求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
    //网络思路:使用·短路与实现if,使用递归实现while
    
    //网络题解一:
        int Sum_Solution(int n) {
            int ans = n;
            ans && (ans += Sum_Solution(n - 1));
            return ans;
        }
    //网络题解二:
        int Sum_Solution(int n) {
            return (pow(n,2)+n)>>1;
        }
    
    • JZ60 把二叉树打印成多行
      出现如下错误:(段错误:您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起。)
      可能原因:
      1.递归无法结束,循环无法结束;
      2.遇到输入数据量为零的情况没有直接返回。

    • 剑指 Offer 54. 二叉搜索树的第k大节点

    //题目本身不难,但做题过程中出现一个错误,积累下这个知识点:
    //函数的形参指针,作为指针变量可以将其所指地址保存的内容传出来。
    //但是!如果在函数内部直接修改指针内容,即指针所指向的地址是无法传出的。
    
    //例一(正确):(如果root->val=4,则输出4)
        int kthLargest(TreeNode* root, int k) {
            int a=3;
            int* myout=&a;
            Reverse_traversal(root, myout);
            cout<<*myout<<endl;
    	}
    	int Reverse_traversal(TreeNode* root, int* myout)
        {
        	*myout = root->val;//将指针对应地址内容赋值
        	return 1;
        }
    
    //例二(错误):(如果root->val=4,仍然输出3)
        int kthLargest(TreeNode* root, int k) {
            int a=3;
            int* myout=&a;
            Reverse_traversal(root, myout);
            cout<<*myout<<endl;
    	}
    	int Reverse_traversal(TreeNode* root, int* myout)
        {
        	myout = &root->val;//改变指针指向的地址,但出了函数不起作用
        	return 1;
        }
    

    2. 研发常考题目

    我的答案

    //快慢指针
    

    参考网络思路

    //哈希表保存访问过的结点
        bool hasCycle(ListNode *head) {
            ListNode* cur=head;
            unordered_map<ListNode*, int> save;
            while(cur)
            {
                if(save.find(cur)!=save.end())
                    return 1;
                save[cur] = 1;
                cur = cur->next;
            }
            return 0;
        }
    

    网络答案思路

    //set,不可插入新内容则有重复,链表为环
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if(head==NULL)
                return false;
            set<ListNode *> s;
            ListNode *p = head;
            while(p!=NULL)
            {
    !!!!!! 注意这句话
                if(!s.insert(p).second)//不可插入新内容则有重复,链表为环
     
                {
                     return true;
                }
                else
                    p=p->next; //指向下个节点
            }
            return false;
        }
    };
    
        void merge(int A[], int m, int B[], int n) {
            int posM=m-1, posN=n-1;
            for(int i=m+n-1; i>=0;i--)
            {
                if(posN==-1)
                {
                    A[i]=A[posM];
                    posM--;
                    continue;
                }
                if(posM==-1)
                {
                    A[i]=B[posN];
                    posN--;
                    continue;
                }
                
                if(A[posM]>B[posN])
                {
                    A[i]=A[posM];
                    posM--;
                }else if(A[posM]<=B[posN]){
                    A[i]=B[posN];
                    posN--;
                }
            }
        }
    

    网络答案(代码优化)

    /*
         * 最优解:从后往前处理,不需要开辟额外空间
         * Runtime: 0 ms.Your runtime beats 45.38 % of java submissions.
         */
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int i = m - 1, j = n - 1, index = m + n - 1;
            while (i >= 0 && j >= 0)
                nums1[index--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
            while (j >= 0)
                nums1[index--] = nums2[j--];
        }
    

    四、LeetCode

    1.解答学习

    //我的方法:定义1两个队列,一个保存孩子结点,一个保存层数
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int> > out;
            levelPrint(root, out);
            return out;
        }
    
        int levelPrint(TreeNode* root, vector<vector<int> >& out)
        {
            if(root==NULL)
                return 0;
            queue<TreeNode*> TreeNodeSave;
            queue<int> TreeLeyer;
    
            vector<int> CurLayerVal;
    
            TreeNodeSave.push(root);
            TreeLeyer.push(1);
            int lastLayer = 1;
            while(TreeNodeSave.size())
            {
                if(TreeLeyer.front()==lastLayer+1)
                {
                    out.push_back(CurLayerVal);
                    CurLayerVal.clear();
                }
                CurLayerVal.push_back(TreeNodeSave.front()->val);
                if(TreeNodeSave.front()->left)
                {
                    TreeNodeSave.push(TreeNodeSave.front()->left);
                    TreeLeyer.push(TreeLeyer.front()+1);
                }    
                if(TreeNodeSave.front()->right)
                {
                    TreeNodeSave.push(TreeNodeSave.front()->right);
                    TreeLeyer.push(TreeLeyer.front()+1);    
                }
                lastLayer=TreeLeyer.front();
                TreeNodeSave.pop();
                TreeLeyer.pop();
            }
            out.push_back(CurLayerVal);
            return 1;
        }
    };
    
    //网络题解:只定义一个队列,通过一个小循环,
    //使得每次大循环访问到所有同层孩子结点,
    //通过最开始保存一个size变量实现同层孩子数量记录的
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int>> ans;
            if(root == nullptr)     return ans;
            queue<TreeNode*> myQue;
            myQue.push(root);
            while(!myQue.empty()){
                vector<int> tmp;
                int size = myQue.size();
                for(;size--;myQue.pop()){
                    auto node = myQue.front();
                    if(node->left)      myQue.push(node->left);
                    if(node->right)     myQue.push(node->right);               
                    tmp.push_back(node->val);
                }
                ans.push_back(tmp);
            }
            return ans;
        }
    };
    
    //我的思路:递归循环到每个叶子结点,把存的所有二进制数转为十进制,提取所有十进制数,求和;
    
    //网络思路:
    class Solution {
    public:
        int sumRootToLeaf(TreeNode* root) {
            return findNum( root, 0);
        }
    
        int findNum(TreeNode* root, int sum)
        {
            if(root==NULL)
                return 0;
            sum = sum*2+root->val;
            if(root->left==NULL&&root->right==NULL)
                return sum;
            return (findNum(root->left, sum)+findNum(root->right, sum));
        }
    };
    
    //我的思路:
    //首先保证首节点没有左子树;
    //然后,访问cur和curNext,if(curNect->left) 重组链接关系;
    
    //网络解析:
    class Solution {
        /**
         * 递增顺序查找树
         *
         * @param root
         * @return
         */
        TreeNode head = new TreeNode(0);
        TreeNode real = head;
        public TreeNode increasingBST(TreeNode root) {
            if (root == null) {
                return null;
            }
    
            increasingBST(root.left);
            real.right = new TreeNode(root.val);
            real = real.right;
            increasingBST(root.right);
            return head.right;
        }
    }
    
    • 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
      题目描述:给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
    我的思路:访问节点,查询其左子树是否包含pq,右子树是否包含pq直到左或右不同时包含pq,当前节点为目标。由于调用查找结点函数,时间复杂度很高。
    
    网络思路:二叉搜索树性质,左子树的数小于节点,右子树的数大于节点,循环判断。
    
    我的解法(复杂):
    class Solution {
    public:
        TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
            if(!root1)
                return root2;
            if(!root2)
                return root1;
            if(root1&&root2)
                root1->val += root2->val;
            Hebing( root1,  root2);
            return root1;
        }
    
        void Hebing(TreeNode* root1, TreeNode* root2)
        {
            if(root1->left && root2->left)
            {
                root1->left->val = root1->left->val + root2->left->val;
                Hebing(root1->left, root2->left);
            }else if(!root1->left && root2->left)
            {
                root1->left = root2->left;
            }
    
            if(root1->right && root2->right)
            {
                root1->right->val = root1->right->val + root2->right->val;
                Hebing(root1->right, root2->right);
            }else if(!root1->right && root2->right)
            {
                root1->right = root2->right;
            }
        }
    };
    
    网络解法(简单):
    class Solution {
        public TreeNode mergeTrees_1(TreeNode t1, TreeNode t2) {
            if (t1 == null) {
                return t2;
            }
            if (t2 == null) {
                return t1;
            }
            // 先合并根节点
            t1.val += t2.val;
            // 再递归合并左右子树
            t1.left = mergeTrees(t1.left, t2.left);
            t1.right = mergeTrees(t1.right, t2.right);
            return t1;
        }
         /**
         * 不修改原二叉树的解法
         */
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            if (t1 == null && t2 == null) {
                return null;
            }
            // 先合并根节点
            TreeNode root = new TreeNode((t1 == null ? 0 : t1.val) + (t2 == null ? 0 : t2.val));
            // 再递归合并左右子树
            root.left = mergeTrees(t1 == null ? null : t1.left, t2 == null ? null : t2.left);
            root.right = mergeTrees(t1 == null ? null : t1.right, t2 == null ? null : t2.right);
            return root;
        }
    }
    
    • 面试题 04.06. 后继者
      题目描述:设计一个算法,找出二叉搜索树中指定节点的“下一个”节点(也即中序后继)。如果指定节点没有对应的“下一个”节点,则返回null。
    网络解答一:先来个直观一点的, 找到p, 然后取p的后一个节点。
    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            TreeNode * res = nullptr, * prev = nullptr;
            inorderTraversal(root, prev, p, res);
            return res;
        }
        void inorderTraversal(TreeNode * root, TreeNode*& prev, TreeNode *p, TreeNode*& res ){
            if(root == nullptr || res != nullptr) return;
            inorderTraversal(root->left, prev, p, res);
            if(prev == p) res = root;
            prev = root;
            inorderTraversal(root->right, prev, p, res);
        }
    };
    网络解答二:再来个简洁一点的,我们要找的是第一个大于p->val的节点, 所以遇到第一个大于p->val的即可返回。
    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            if(root == nullptr) return nullptr;
            TreeNode * res = inorderSuccessor(root->left, p);
            if(res != nullptr) return res;
            if(root->val > p->val) return root;
            return inorderSuccessor(root->right, p);
        }
    };
    
    我的答案:
    class Solution {
    public:
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            int Flag = 0;
            int* pFlag = &Flag;
            if(!root)
                return NULL;
            TreeNode* out = NULL;
            out = Inorder(root, p, pFlag);
            return out;
        }
        TreeNode* Inorder(TreeNode* root, TreeNode* p, int* pFlag)
        {
            if(root->left)
            {
                TreeNode* out = Inorder(root->left, p, pFlag);
                if(out!=NULL)
                    return out;
            }
            if(*pFlag==1)
            {
                cout<<"**2:"<<root->val<<endl;
                return root;
            }
            if(root==p)
            {
                *pFlag = 1;
                cout<<"**"<<root->val<<endl;
            }
            if(root->right)
            {
                TreeNode* out = Inorder(root->right, p, pFlag);
                if(out!=NULL)
                    return out;
            }
            cout<<"**x:"<<root->val<<endl;
            return NULL;
        }
    };
    
    网络解答:深度优先
    class Solution {
        int deep1, deep2;
        TreeNode *pra1,  *pra2;
        void node_deep(TreeNode* root, TreeNode* pra,int deep, int x, int y)
        {
            if(!root) return;
            if(root->val == x)
            {
                pra1 = pra;
                deep1 = deep+1;
            }
            if(root->val == y)
            {
                pra2 = pra;
                deep2 = deep+1;
            }
            node_deep(root->left,root,deep+1,x,y);
            node_deep(root->right,root,deep+1,x,y);
        }
    public:
        bool isCousins(TreeNode* root, int x, int y) {
            if(!root) return false;
            node_deep(root,NULL,0,x,y);
            return (deep1 == deep2) && (pra1 != pra2);
        }
    };
    
    网络答案:
    class Solution {
    public:
        vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {   
            vector<int> v1, v2, ret;
            mid(root1, v1);
            mid(root2, v2);
            merge(v1.begin(),v1.end(), v2.begin(), v2.end(), back_inserter(ret));//注意
            return ret;
        }
        void mid(TreeNode* root, vector<int> &v) {
            if(root) {
            if(root->left) mid(root->left, v);
            v.push_back(root->val);
            if(root->right) mid(root->right, v);
            }
        }
    };
    
    • _53. 最大子序和
      题目描述:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    以下是网络解答

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int res = nums[0];
            int sum = 0;
            for (int num : nums) {
                if (sum > 0)
                    sum += num;
                else
                    sum = num;
                res = max(res, sum);
            }
            return res;        
        }
    };
    

    以下是我的答案

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if(nums.size()==0)
                return -1;
    
            int maxSum=nums[0];
            for(int i=0;i<nums.size();i++)
            {
                if(nums[i]>maxSum)
                    maxSum = nums[i];
            }
            if(maxSum>0)
            {
                maxSum = 0;
                int sum=0;
                for(int i=0;i<nums.size();i++)
                {
                    sum += nums[i];
                    if(sum<0)
                    {
                        sum = 0;
                    }
                    if(sum>maxSum)
                    {
                        maxSum = sum;   
                    }
                }
            }
            return maxSum;
        }
    };
    
    • _70. 爬楼梯
      这道题目可以用递归,动态规划,数学解析等方法实现。
    //递归
    //可以直接递归,也可以做有缓存的递归
    
    //动态规划
    //从1循环到n
    //分别存储每次的解
    
    //网络答案
        //分治Time:O(NlogN) Space:O(logN)
        public int maxSubArray(int[] nums) {
            return divide(nums, 0, nums.length - 1);
        }
        private int divide(int[] nums, int st, int ed) {
            if(st == ed) return nums[st];
            int mid = (st + ed) / 2;
            //最大连续数列在mid的左边
            int left = divide(nums, st, mid);
            //最大连续数列在mid的右边
            int right = divide(nums, mid + 1, ed);
            //最大连续数列在中间包括mid
            //[i...mid...j]为最大练习数列
            int maxLeft = Integer.MIN_VALUE; // 记录[i...mid]最大和
            int sumLeft = 0;
            int maxRight = Integer.MIN_VALUE; // 记录[mid+1..j]最大和
            int sumRight = 0;
            for(int i = mid; i >= st; i--) {
                sumLeft += nums[i];
                maxLeft = Math.max(maxLeft, sumLeft);
            }
            for(int j = mid + 1; j <= ed; j++) {
                sumRight += nums[j];
                maxRight = Math.max(maxRight, sumRight);
            }
            //返回上面三种情况的最大值即可
            return Math.max(Math.max(left, right), maxLeft + maxRight);
        }
    
        //动态规划
        public int maxSubArray2(int[] nums) {
            int sum = 0;
            int max = Integer.MIN_VALUE;
            for(int num : nums) {
                max = Math.max(max, sum + num);
                if(sum + num < 0){
                    sum = 0;
                }else {
                    sum += num;
                }
            }
            return max;
        }
        //暴力Time:O(N^2) Space:O(N)
        public int maxSubArray1(int[] nums) {
            int max = Integer.MIN_VALUE;
            int[] preSum = new int[nums.length + 1];
            //前缀和
            for(int i = 1; i <= nums.length; i++) {
                preSum[i] = preSum[i-1] + nums[i-1];
            }
            for(int i = 0; i < nums.length; i++) {
                for(int j = 0; j <= i; j ++) {
                    max = Math.max(max, preSum[i+1] - preSum[j]);
                }
            }
            return max;
        }
    
    //双指针
    bool isSubsequence(char * s, char * t){
        while (*s && *t) {
            if (*s == *t) {
                s++;
            }
            t++;
        }
        if (*s == '\0') {
            return true;
        } else {
            return false;
        }
    }
    
    //思路一:库函数
    class Solution:
        def isSubsequence(self, s: str, t: str) -> bool: 
            loc = -1
            for a in s:
                loc = t.find(a, loc + 1)
                if loc == -1:
                    return False
            return True
    
    //思路二:生成迭代器
    class Solution:
        def isSubsequence(self, s: str, t: str) -> bool:
            t = iter(t)
            return all(c in t for c in s)
    
    //思路四:二分法
    class Solution:
        def isSubsequence(self, s: str, t: str) -> bool:  
            from collections import defaultdict
            import bisect
            lookup = defaultdict(list)
            for idx, val in enumerate(t):
                lookup[val].append(idx)
            # print(lookup)
            loc = -1
            for a in s:
                j = bisect.bisect_left(lookup[a], loc + 1)
                if j >= len(lookup[a]): return False
                loc = lookup[a][j]
            return True
    
    //网络方法
        int largestSumAfterKNegations(vector<int>& A, int K) 
        {
            sort(A.begin(),A.end());
            int j = 0;
            int i = 0;
            
            for(; i < A.size()&& A[i] <0 && K>0;i++)
            {
                A[i] = -A[i];
                K--;
            }
            sort(A.begin(),A.end());
            while(K)
            {
                A[0] = -A[0];
                K--;
            }
            int sum = accumulate(A.begin(),A.end(),0);
            return sum;
        }
    
    //我的方法
    class Solution {
    public:
        int largestSumAfterKNegations(vector<int>& A, int K) {
            sort(A.data() , A.data()+A.size());
            if(A[0]>=0)
            {    
                if(K%2==1)
                    A[0]=-A[0];
            }else
            {
                for(int i=0;i<A.size()&&K;i++)
                {
                    if(A[i]<0)    
                    {
                        A[i]=-A[i];
                        K--;
                    }else{
                        if(K%2==1)
                        {
                            if(A[i]<A[i-1])
                                A[i]=-A[i];
                            else
                                A[i-1]=-A[i-1];
                        }
                        K=0;
                    }
                }
            }
    
            int sum=0;
            for(int i=0;i<A.size();i++)
                sum+=A[i];
            return sum;
        }
    };
    
    
    //我的答案(超时  )
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<int> CurP(2,0);
            return Ways(CurP, -1, m, n);
        }
    
        int Ways(vector<int> CurP, int Move, int m, int n )
        {
            if(Move==0)
                CurP[0] ++;
            if(Move==1)
                CurP[1] ++;
    
            if(CurP[0]==m-1&&CurP[1]==n-1){
                return 1;
            }
    
            if(CurP[0]>m-1||CurP[1]>n-1){
                return 0;
            }
            return Ways(CurP , 0 , m, n)+Ways(CurP, 1, m, n);
        }
    
    };
    
    //网络答案
        vector<vector<int>> generate(int numRows) {
            vector<vector<int>> res={
            {1},
            {1,1},
            {1,2,1},
            {1,3,3,1},
            {1,4,6,4,1},
            {1,5,10,10,5,1},
            {1,6,15,20,15,6,1},
            {1,7,21,35,35,21,7,1},
            {1,8,28,56,70,56,28,8,1},
            {1,9,36,84,126,126,84,36,9,1},
            {1,10,45,120,210,252,210,120,45,10,1},
            {1,11,55,165,330,462,462,330,165,55,11,1},
            {1,12,66,220,495,792,924,792,495,220,66,12,1},
            {1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1},
            {1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1},
            {1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1},
            {1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1},
            {1,17,136,680,2380,6188,12376,19448,24310,24310,19448,12376,6188,2380,680,136,17,1},
            {1,18,153,816,3060,8568,18564,31824,43758,48620,43758,31824,18564,8568,3060,816,153,18,1},
            {1,19,171,969,3876,11628,27132,50388,75582,92378,92378,75582,50388,27132,11628,3876,969,171,19,1},
            {1,20,190,1140,4845,15504,38760,77520,125970,167960,184756,167960,125970,77520,38760,15504,4845,1140,190,20,1},
            {1,21,210,1330,5985,20349,54264,116280,203490,293930,352716,352716,293930,203490,116280,54264,20349,5985,1330,210,21,1},
            {1,22,231,1540,7315,26334,74613,170544,319770,497420,646646,705432,646646,497420,319770,170544,74613,26334,7315,1540,231,22,1},
            {1,23,253,1771,8855,33649,100947,245157,490314,817190,1144066,1352078,1352078,1144066,817190,490314,245157,100947,33649,8855,1771,253,23,1},
            {1,24,276,2024,10626,42504,134596,346104,735471,1307504,1961256,2496144,2704156,2496144,1961256,1307504,735471,346104,134596,42504,10626,2024,276,24,1},
            {1,25,300,2300,12650,53130,177100,480700,1081575,2042975,3268760,4457400,5200300,5200300,4457400,3268760,2042975,1081575,480700,177100,53130,12650,2300,300,25,1},
            {1,26,325,2600,14950,65780,230230,657800,1562275,3124550,5311735,7726160,9657700,10400600,9657700,7726160,5311735,3124550,1562275,657800,230230,65780,14950,2600,325,26,1},
            {1,27,351,2925,17550,80730,296010,888030,2220075,4686825,8436285,13037895,17383860,20058300,20058300,17383860,13037895,8436285,4686825,2220075,888030,296010,80730,17550,2925,351,27,1},
            {1,28,378,3276,20475,98280,376740,1184040,3108105,6906900,13123110,21474180,30421755,37442160,40116600,37442160,30421755,21474180,13123110,6906900,3108105,1184040,376740,98280,20475,3276,378,28,1},
            {1,29,406,3654,23751,118755,475020,1560780,4292145,10015005,20030010,34597290,51895935,67863915,77558760,77558760,67863915,51895935,34597290,20030010,10015005,4292145,1560780,475020,118755,23751,3654,406,29,1}};
            res.resize(numRows);
            return res;
        }
    
    //网络答案
        string removeOuterParentheses(string S) {
            string out="";
            int layer=0;
            for(int i=0;i<S.length();i++)
            {
                if(S[i]=='(')
                    ++layer;
                if(layer!=1)
                    out+=S[i];
                if(S[i]==')')
                    --layer;
                
            }
            return out;
        }
    
    //c语言
    char* simplifyPath(char *path) {
        int length = 0;
        while (path[length] != '\0') {
            length++;
        }
        char *stack = (char *)malloc(sizeof(char) * (length + 2));
        int top = -1;
        stack[++top] = '/';
        for (int i = 0; i <= length; i++) {
            if (path[i] == '/' || (path[i] == '.' && (path[i + 1] == '/' || path[i + 1] == '\0'))) {
                continue;
            } else if (path[i] == '.' && path[i + 1] == '.' && (path[i + 2] == '/' || path [i + 2] == '\0')) {
                while (top > 0 && stack[--top] != '/');
                i++;
            } else {
                do {
                    stack[++top] = path[i];
                } while(i < length && path[i] != '/' && ++i);
            }
        }
        if (top != 1 && stack[top - 1] == '/') {
            stack[--top] = '\0';
        }
        return stack;
    }
    
    方法三:用翻转代替旋转
    我们还可以另辟蹊径,用翻转操作代替旋转操作。先将其通过水平轴翻转,再根据主对角线翻转,就得到了答案。这是为什么呢?对于水平轴翻转而言,我们只需要枚举矩阵上半部分的元素,和下半部分的元素进行交换,即对于主对角线翻转而言,我们只需要枚举对角线左侧的元素,和右侧的元素进行交换
    
        vector<int> countBits(int num) {
            vector<int> bits(num + 1);
            int highBit = 0;
            for (int i = 1; i <= num; i++) {
                if ((i & (i - 1)) == 0) {
                    highBit = i;
                }
                bits[i] = bits[i - highBit] + 1;
            }
            return bits;
        }
    
    //网络解答,集合
        int missingNumber(vector<int>& nums) {
            int ans=0;
            set<int>s(nums.begin(),nums.end());
            for(int i=0;i<=nums.size();i++)
                if(!s.count(i)) ans=i;
            return ans;
        }
    
    //网络解答,直接修改A,和处理边界这种思想很妙
        public int minFallingPathSum(int[][] A) {
            int N = A.length;
            for (int r = N-2; r >= 0; --r) {
                for (int c = 0; c < N; ++c) {
                    // best = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1])
                    int best = A[r+1][c];
                    if (c > 0)
                        best = Math.min(best, A[r+1][c-1]);
                    if (c+1 < N)
                        best = Math.min(best, A[r+1][c+1]);
                    A[r][c] += best;
                }
            }
            int ans = Integer.MAX_VALUE;
            for (int x: A[0])
                ans = Math.min(ans, x);
            return ans;
        }
    

    网络解答一

    /*
    利用 isdigit() 函数判断字符串中的数字部分;
    利用set接收结果,自动去重;
    全部接收后获得其中的最大值,移除该最大值;
    判断集合是否为空,若为空则不存在第二大,直接输出-1;
    若不为空,则再次取最大值,此值即为第二大的值;
    */
        int secondHighest(string s) {
            set<int>res;
            for(int i=0;i<s.size();i++){
                if(isdigit(s[i])) ///注意这个函数
                res.insert(s[i]-'0');
            }
            int max_num=*max_element(res.begin(),res.end());
            res.erase(max_num);
            if(res.size()==0) return -1;
            else 
            return *max_element(res.begin(),res.end());
        }
    

    网络解答二,注意迭代器的使用

        int secondHighest(string s) 
        {   
            set<int> a;
            for (auto c: s)
            {
                if (isdigit(c) != 0)
                    a.insert(c - '0');
            }
            if (a.size() < 2)
                return -1;
            
            auto it = a.rbegin();
            it ++;
            return *it;
        }
    

    网络解答

        int numSpecialEquivGroups(vector<string>& words) {
            int res=0;
            unordered_map<string , int> save;
    
            for(int i=0;i<words.size();i++){
                vector<int> count(52);        
                for(int j=0;j<words[i].length();j++){
                    count[words[i][j]-'a'+(j%2)*26]++;
                }
                stringstream ss;
                string counS;
                copy(count.begin(), count.end(), ostream_iterator<int>(ss, ""));
                counS = ss.str();
                save[counS]=0;
            }
    /*
            unordered_map<string , int>::iterator it = save.begin();
            while(it != save.end()){
                cout<<it->first<<" "<<it->second<<endl;
                it++;
            }
    */
            return save.size();
        }
    

    网络解答一

        int firstUniqChar(string s) {
            unordered_map<int, int> frequency;
            for (char ch: s) {
                ++frequency[ch];
            }
            for (int i = 0; i < s.size(); ++i) {
                if (frequency[s[i]] == 1) {
                    return i;
                }
            }
            return -1;
        }
    

    网络解答二

    /*
    */
        int firstUniqChar(string s) {
            unordered_map<int, int> position;
            int n = s.size();
            for (int i = 0; i < n; ++i) {
                if (position.count(s[i])) {
                    position[s[i]] = -1;
                }
                else {
                    position[s[i]] = i;
                }
            }
            int first = n;
            for (auto [_, pos]: position) {
                if (pos != -1 && pos < first) {
                    first = pos;
                }
            }
            if (first == n) {
                first = -1;
            }
            return first;
        }
    

    网络解答三

    /*
    在维护队列时,我们使用了「延迟删除」这一技巧。
    也就是说,即使队列中有一些字符出现了超过一次,但它只要不位于队首,
    那么就不会对答案造成影响,我们也就可以不用去删除它。
    只有当它前面的所有字符被移出队列,它成为队首时,我们才需要将它移除。
    */
        int firstUniqChar(string s) {
            unordered_map<char, int> position;
            queue<pair<char, int>> q;
            int n = s.size();
            for (int i = 0; i < n; ++i) {
                if (!position.count(s[i])) {
                    position[s[i]] = i;
                    q.emplace(s[i], i);
                }
                else {
                    position[s[i]] = -1;
                    while (!q.empty() && position[q.front().first] == -1) {
                        q.pop();
                    }
                }
            }
            return q.empty() ? -1 : q.front().second;
        }
    

    简单解法

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> combinations;
            if (digits.empty()) {
                return combinations;
            }
            unordered_map<char, string> phoneMap{
                {'2', "abc"},
                {'3', "def"},
                {'4', "ghi"},
                {'5', "jkl"},
                {'6', "mno"},
                {'7', "pqrs"},
                {'8', "tuv"},
                {'9', "wxyz"}
            };
            string combination;
            backtrack(combinations, phoneMap, digits, 0, combination);
            return combinations;
        }
    
        void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
            if (index == digits.length()) {
                combinations.push_back(combination);
            } else {
                char digit = digits[index];
                const string& letters = phoneMap.at(digit);
                for (const char& letter: letters) {
                    combination.push_back(letter);
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.pop_back();
                }
            }
        }
    };
    

    2.不会做的题目

    解题思路
    
    求按摩师的最长预约时间,nums为按摩师的预约请求序列,求一个最优时间和,可以通过动态规划的方式来求,下面按照动态规划的步骤一步一步进行。
    状态定义:
    
    通过定义dp数组来记录最长时间 dp[i]0 到 i 的最长预约时间
    状态转移方程:
    
    对于dp[i]可以有两种状态,一种是接受当前预约,那么昨天肯定就不能预约,我们需要取得 i-2 天的时间加上当前的时间 dp[i-2] + nums[i]。
    另一种就是不接受当前预约,那么就只取前一天的预约时间 i - 1 dp[i-1],我们需要求最大的时长 max(dp[i-1],dp[i-2]+nums[i])
    状态初始化:
    
    根据状态定义我们需要从i=2的位置开始计算,所以我们需要初始化01位置的时长,如果只有一天的话那么dp[0]这个位置我们必须要接受预约,如果有两天的话dp[1]的位置我们需要求两个时长的最大,所以dp[1] = Math.max(dp[0],nums[1]);
    状态输出:
    
    dp[len-1] 就是我们最终的状态。
    看来动态规划的状态定义和转移方程 真的是需要不断的去练习。
    代码
    
    class Solution {
        public int massage(int[] nums) {
            int len  = nums.length;
            if(len == 0){
                return 0;
            }
            if(len == 1){
                return nums[0];
            }
    
            int[] dp = new int[len];
            dp[0] = nums[0];
            dp[1] = Math.max(dp[0],nums[1]);
            for(int i = 2; i < len;i++){
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            }
            return dp[len-1];
        }
    }
    
    //看答案后做的
    class Solution {
    public:
        int massage(vector<int>& nums) {
            if(nums.size()==0)
                return 0;
            if(nums.size()==1)
                return nums[0];
            
            int DP[nums.size()][2];
            DP[0][0] = 0;
            DP[0][1] = nums[0];
            DP[1][0] = nums[0];
            DP[1][1] = nums[1];
            for(int i=2;i<nums.size();i++)
            {
                DP[i][0] = max(DP[i-1][0],DP[i-1][1]);
                DP[i][1] = (DP[i-1][0])+nums[i];
            }
            return max(DP[nums.size()-1][0],DP[nums.size()-1][1]);
        }
    };
    
    //不会做,网络答案
        int maxProfit(vector<int>& prices, int fee) {
            int n = prices.size();
            vector<int> f(2);
            // 0 : 不持股   1 : 持股
            f[0] = 0;
            f[1] = -prices[0];
            for(int i = 1; i<n; i++){
                f[0] = max(f[0], f[1] + prices[i] - fee);
                f[1] = max(f[1], f[0] - prices[i]);
            }
            return f[0];
        }
    
    • _1047. 删除字符串中的所有相邻重复项
      题目描述:给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。在 S 上反复执行重复项删除操作,直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。输入:“abbaca”;输出:“ca”;

    解法一:原地算法

        string removeDuplicates(string S) {
            int top = 0;
            for (char ch : S) {
                if (top == 0 || S[top - 1] != ch) {
                    S[top++] = ch;
                } else {
                    top--;
                }
            }
            S.resize(top);
            return S;
        }
    

    解法二:C++ string 也能当栈用

        string removeDuplicates(string S) {
            string ret;
            for(auto c:S){
                if(ret.empty()||c!=ret.back()){
                    ret.push_back(c);
                }else{
                    ret.pop_back();
                }
            }
            return ret;
        }
    

    解法三:空字符串哨兵

        def removeDuplicates(self, S: str) -> str:
            stack = [""]
            for ch in S:
                if ch == stack[-1]:
                    stack.pop()
                else:
                    stack.append(ch)
            return "".join(stack)
    

    解法四:

    //网络答案
        public String removeDuplicates(String S) {
            int now =S.length();
            int next = 1;
            while(now != next){
               now =  S.length();      S=S.replace("aa","").replace("bb","").replace("cc","").replace("dd","").replace("ee","").replace("ff","").replace("gg","").replace("hh","").replace("ii","").replace("jj","").replace("kk","").replace("ll","").replace("mm","").replace("nn","").replace("oo","").replace("pp","").replace("qq","").replace("rr","").replace("ss","").replace("tt","").replace("uu","").replace("vv","").replace("ww","").replace("xx","").replace("yy","").replace("zz","");
               next =  S.length();       
                }
            return S;
        }
    

    网络答案:动态规划

    /*
    解题思路:
    状态
    f[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中,最长的回文序列长度是多少。
    
    转移方程
    如果 s 的第 i 个字符和第 j 个字符相同的话
    f[i][j] = f[i + 1][j - 1] + 2
    如果 s 的第 i 个字符和第 j 个字符不同的话
    f[i][j] = max(f[i + 1][j], f[i][j - 1])
    然后注意遍历顺序,i 从最后一个字符开始往前遍历,j 从 i + 1 开始往后遍历,这样可以保证每个子问题都已经算好了。
    
    初始化
    f[i][i] = 1 单个字符的最长回文序列是 1
    
    结果
    f[0][n - 1]
    */
    class Solution {
        public int longestPalindromeSubseq(String s) {
            int n = s.length();
            int[][] f = new int[n][n];
            for (int i = n - 1; i >= 0; i--) {
                f[i][i] = 1;
                for (int j = i + 1; j < n; j++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        f[i][j] = f[i + 1][j - 1] + 2;
                    } else {
                        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    }
                }
            }
            return f[0][n - 1];
        }
    }
    

    五、赛码

    https://www.acmcoder.com/index

    六、技巧与结论总结

    6.1 技巧总结

    • 异或运算(XOR)满足结合律,并且对一个数进行两次完全相同的异或运算会得到原来的数,因此我们可以通过异或运算找到缺失的数字。
      例题:268. 丢失的数字官方答案方法三
    • 调用C++自带的排序函数:sort(s.begin(), s.end());
      例题:242. 有效的字母异位词官方答案
    • 对于回溯题目,引用相比参数传递能节省很大时间开销

    6.2 结论总结

    • 旋转矩阵
      假设矩阵边长为len,则操作的部分是:
      Row:[0,(len+1)/2],Column:[0,len/2],如下图所示
      在这里插入图片描述
      在这里插入图片描述

    6.3 极端输入情况总结

    笔试时看不到输入用例,因此无法根据不通过的结果调整代码,需要总结积累。

    • 注意链表头节点为空的特殊情况

    • 石子游戏
      题目:今天,度度熊和牛妹在玩取石子的游戏,开始的时候有堆石头,第堆有个石头,两个人轮流动作,度度熊先走,在每个回合,玩家选择一个非空堆,并从堆中移除一块石头。如果一个玩家在轮到他之前所有的石碓都是空的,或者如果在移动石头之后,存在两个堆包含相同数量的石头(可能为都为),那么他就会输。假设两人都在游戏时选择最佳方式,度度熊和牛妹谁会赢?如果度度熊获胜,输出“man”,如果牛妹获胜,输出“woman”(输出不包含双引号)。
      分析:先对数组排序,然后剔除特殊情况,之后轮流取直至变成0,1,2,3…形态。
      判断先手能否走第一步,以下情况不能:
      1)仅有一个数且为0;
      2)前两个数为0;
      3)如果一个数出现了3次;
      4)至少有2个数字出现两次;
      5)一个数字出现两次且其前一个数比他小一;

    • 最小公倍数与最大公约数
      题目:度度熊请你找出两个数a,b,满足1<=a,b<=n,且lcm(a,b)-gcd(a,b)尽量大。输出最大的lcm(a,b)-gcd(a,b)。其中lcm(a,b)表示a和b的最小公倍数,gcd(a,b)表示a和b的最大公约数。
      结论:对于可能超出范围的情况,要使用范围更大的数据类型。

    • 40. 组合总和 II
      用例一:
      [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
      27

    • 212. 单词搜索 II
      遗漏情况:起始位置不是board[0][0];
      极端输入:
      [[“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”],[“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”],[“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”],[“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”],[“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”],[“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”],[“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”],[“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”],[“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”],[“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”,“a”,“b”]]
      [“ababababaa”,“ababababab”,“ababababac”,“ababababad”,“ababababae”,“ababababaf”,“ababababag”,“ababababah”,“ababababai”,“ababababaj”,“ababababak”,“ababababal”,“ababababam”,“ababababan”,“ababababao”,“ababababap”,“ababababaq”,“ababababar”,“ababababas”,“ababababat”,“ababababau”,“ababababav”,“ababababaw”,“ababababax”,“ababababay”,“ababababaz”,“ababababba”,“ababababbb”,“ababababbc”,“ababababbd”,“ababababbe”,“ababababbf”,“ababababbg”,“ababababbh”,“ababababbi”,“ababababbj”,“ababababbk”,“ababababbl”,“ababababbm”,“ababababbn”,“ababababbo”,“ababababbp”,“ababababbq”,“ababababbr”,“ababababbs”,“ababababbt”,“ababababbu”,“ababababbv”,“ababababbw”,“ababababbx”,“ababababby”,“ababababbz”,“ababababca”,“ababababcb”,“ababababcc”,“ababababcd”,“ababababce”,“ababababcf”,“ababababcg”,“ababababch”,“ababababci”,“ababababcj”,“ababababck”,“ababababcl”,“ababababcm”,“ababababcn”,“ababababco”,“ababababcp”,“ababababcq”,“ababababcr”,“ababababcs”,“ababababct”,“ababababcu”,“ababababcv”,“ababababcw”,“ababababcx”,“ababababcy”,“ababababcz”,“ababababda”,“ababababdb”,“ababababdc”,“ababababdd”,“ababababde”,“ababababdf”,“ababababdg”,“ababababdh”,“ababababdi”,“ababababdj”,“ababababdk”,“ababababdl”,“ababababdm”,“ababababdn”,“ababababdo”,“ababababdp”,“ababababdq”,“ababababdr”,“ababababds”,“ababababdt”,“ababababdu”,“ababababdv”,“ababababdw”,“ababababdx”,“ababababdy”,“ababababdz”,“ababababea”,“ababababeb”,“ababababec”,“ababababed”,“ababababee”,“ababababef”,“ababababeg”,“ababababeh”,“ababababei”,“ababababej”,“ababababek”,“ababababel”,“ababababem”,“ababababen”,“ababababeo”,“ababababep”,“ababababeq”,“ababababer”,“ababababes”,“ababababet”,“ababababeu”,“ababababev”,“ababababew”,“ababababex”,“ababababey”,“ababababez”,“ababababfa”,“ababababfb”,“ababababfc”,“ababababfd”,“ababababfe”,“ababababff”,“ababababfg”,“ababababfh”,“ababababfi”,“ababababfj”,“ababababfk”,“ababababfl”,“ababababfm”,“ababababfn”,“ababababfo”,“ababababfp”,“ababababfq”,“ababababfr”,“ababababfs”,“ababababft”,“ababababfu”,“ababababfv”,“ababababfw”,“ababababfx”,“ababababfy”,“ababababfz”,“ababababga”,“ababababgb”,“ababababgc”,“ababababgd”,“ababababge”,“ababababgf”,“ababababgg”,“ababababgh”,“ababababgi”,“ababababgj”,“ababababgk”,“ababababgl”,“ababababgm”,“ababababgn”,“ababababgo”,“ababababgp”,“ababababgq”,“ababababgr”,“ababababgs”,“ababababgt”,“ababababgu”,“ababababgv”,“ababababgw”,“ababababgx”,“ababababgy”,“ababababgz”,“ababababha”,“ababababhb”,“ababababhc”,“ababababhd”,“ababababhe”,“ababababhf”,“ababababhg”,“ababababhh”,“ababababhi”,“ababababhj”,“ababababhk”,“ababababhl”,“ababababhm”,“ababababhn”,“ababababho”,“ababababhp”,“ababababhq”,“ababababhr”,“ababababhs”,“ababababht”,“ababababhu”,“ababababhv”,“ababababhw”,“ababababhx”,“ababababhy”,“ababababhz”,“ababababia”,“ababababib”,“ababababic”,“ababababid”,“ababababie”,“ababababif”,“ababababig”,“ababababih”,“ababababii”,“ababababij”,“ababababik”,“ababababil”,“ababababim”,“ababababin”,“ababababio”,“ababababip”,“ababababiq”,“ababababir”,“ababababis”,“ababababit”,“ababababiu”,“ababababiv”,“ababababiw”,“ababababix”,“ababababiy”,“ababababiz”,“ababababja”,“ababababjb”,“ababababjc”,“ababababjd”,“ababababje”,“ababababjf”,“ababababjg”,“ababababjh”,“ababababji”,“ababababjj”,“ababababjk”,“ababababjl”,“ababababjm”,“ababababjn”,“ababababjo”,“ababababjp”,“ababababjq”,“ababababjr”,“ababababjs”,“ababababjt”,“ababababju”,“ababababjv”,“ababababjw”,“ababababjx”,“ababababjy”,“ababababjz”,“ababababka”,“ababababkb”,“ababababkc”,“ababababkd”,“ababababke”,“ababababkf”,“ababababkg”,“ababababkh”,“ababababki”,“ababababkj”,“ababababkk”,“ababababkl”,“ababababkm”,“ababababkn”,“ababababko”,“ababababkp”,“ababababkq”,“ababababkr”,“ababababks”,“ababababkt”,“ababababku”,“ababababkv”,“ababababkw”,“ababababkx”,“ababababky”,“ababababkz”,“ababababla”,“abababablb”,“abababablc”,“ababababld”,“abababable”,“abababablf”,“abababablg”,“abababablh”,“ababababli”,“abababablj”,“abababablk”,“ababababll”,“abababablm”,“ababababln”,“abababablo”,“abababablp”,“abababablq”,“abababablr”,“ababababls”,“abababablt”,“abababablu”,“abababablv”,“abababablw”,“abababablx”,“abababably”,“abababablz”,“ababababma”,“ababababmb”,“ababababmc”,“ababababmd”,“ababababme”,“ababababmf”,“ababababmg”,“ababababmh”,“ababababmi”,“ababababmj”,“ababababmk”,“ababababml”,“ababababmm”,“ababababmn”,“ababababmo”,“ababababmp”,“ababababmq”,“ababababmr”,“ababababms”,“ababababmt”,“ababababmu”,“ababababmv”,“ababababmw”,“ababababmx”,“ababababmy”,“ababababmz”,“ababababna”,“ababababnb”,“ababababnc”,“ababababnd”,“ababababne”,“ababababnf”,“ababababng”,“ababababnh”,“ababababni”,“ababababnj”,“ababababnk”,“ababababnl”,“ababababnm”,“ababababnn”,“ababababno”,“ababababnp”,“ababababnq”,“ababababnr”,“ababababns”,“ababababnt”,“ababababnu”,“ababababnv”,“ababababnw”,“ababababnx”,“ababababny”,“ababababnz”,“ababababoa”,“ababababob”,“ababababoc”,“ababababod”,“ababababoe”,“ababababof”,“ababababog”,“ababababoh”,“ababababoi”,“ababababoj”,“ababababok”,“ababababol”,“ababababom”,“ababababon”,“ababababoo”,“ababababop”,“ababababoq”,“ababababor”,“ababababos”,“ababababot”,“ababababou”,“ababababov”,“ababababow”,“ababababox”,“ababababoy”,“ababababoz”,“ababababpa”,“ababababpb”,“ababababpc”,“ababababpd”,“ababababpe”,“ababababpf”,“ababababpg”,“ababababph”,“ababababpi”,“ababababpj”,“ababababpk”,“ababababpl”,“ababababpm”,“ababababpn”,“ababababpo”,“ababababpp”,“ababababpq”,“ababababpr”,“ababababps”,“ababababpt”,“ababababpu”,“ababababpv”,“ababababpw”,“ababababpx”,“ababababpy”,“ababababpz”,“ababababqa”,“ababababqb”,“ababababqc”,“ababababqd”,“ababababqe”,“ababababqf”,“ababababqg”,“ababababqh”,“ababababqi”,“ababababqj”,“ababababqk”,“ababababql”,“ababababqm”,“ababababqn”,“ababababqo”,“ababababqp”,“ababababqq”,“ababababqr”,“ababababqs”,“ababababqt”,“ababababqu”,“ababababqv”,“ababababqw”,“ababababqx”,“ababababqy”,“ababababqz”,“ababababra”,“ababababrb”,“ababababrc”,“ababababrd”,“ababababre”,“ababababrf”,“ababababrg”,“ababababrh”,“ababababri”,“ababababrj”,“ababababrk”,“ababababrl”,“ababababrm”,“ababababrn”,“ababababro”,“ababababrp”,“ababababrq”,“ababababrr”,“ababababrs”,“ababababrt”,“ababababru”,“ababababrv”,“ababababrw”,“ababababrx”,“ababababry”,“ababababrz”,“ababababsa”,“ababababsb”,“ababababsc”,“ababababsd”,“ababababse”,“ababababsf”,“ababababsg”,“ababababsh”,“ababababsi”,“ababababsj”,“ababababsk”,“ababababsl”,“ababababsm”,“ababababsn”,“ababababso”,“ababababsp”,“ababababsq”,“ababababsr”,“ababababss”,“ababababst”,“ababababsu”,“ababababsv”,“ababababsw”,“ababababsx”,“ababababsy”,“ababababsz”,“ababababta”,“ababababtb”,“ababababtc”,“ababababtd”,“ababababte”,“ababababtf”,“ababababtg”,“ababababth”,“ababababti”,“ababababtj”,“ababababtk”,“ababababtl”,“ababababtm”,“ababababtn”,“ababababto”,“ababababtp”,“ababababtq”,“ababababtr”,“ababababts”,“ababababtt”,“ababababtu”,“ababababtv”,“ababababtw”,“ababababtx”,“ababababty”,“ababababtz”,“ababababua”,“ababababub”,“ababababuc”,“ababababud”,“ababababue”,“ababababuf”,“ababababug”,“ababababuh”,“ababababui”,“ababababuj”,“ababababuk”,“ababababul”,“ababababum”,“ababababun”,“ababababuo”,“ababababup”,“ababababuq”,“ababababur”,“ababababus”,“ababababut”,“ababababuu”,“ababababuv”,“ababababuw”,“ababababux”,“ababababuy”,“ababababuz”,“ababababva”,“ababababvb”,“ababababvc”,“ababababvd”,“ababababve”,“ababababvf”,“ababababvg”,“ababababvh”,“ababababvi”,“ababababvj”,“ababababvk”,“ababababvl”,“ababababvm”,“ababababvn”,“ababababvo”,“ababababvp”,“ababababvq”,“ababababvr”,“ababababvs”,“ababababvt”,“ababababvu”,“ababababvv”,“ababababvw”,“ababababvx”,“ababababvy”,“ababababvz”,“ababababwa”,“ababababwb”,“ababababwc”,“ababababwd”,“ababababwe”,“ababababwf”,“ababababwg”,“ababababwh”,“ababababwi”,“ababababwj”,“ababababwk”,“ababababwl”,“ababababwm”,“ababababwn”,“ababababwo”,“ababababwp”,“ababababwq”,“ababababwr”,“ababababws”,“ababababwt”,“ababababwu”,“ababababwv”,“ababababww”,“ababababwx”,“ababababwy”,“ababababwz”,“ababababxa”,“ababababxb”,“ababababxc”,“ababababxd”,“ababababxe”,“ababababxf”,“ababababxg”,“ababababxh”,“ababababxi”,“ababababxj”,“ababababxk”,“ababababxl”,“ababababxm”,“ababababxn”,“ababababxo”,“ababababxp”,“ababababxq”,“ababababxr”,“ababababxs”,“ababababxt”,“ababababxu”,“ababababxv”,“ababababxw”,“ababababxx”,“ababababxy”,“ababababxz”,“ababababya”,“ababababyb”,“ababababyc”,“ababababyd”,“ababababye”,“ababababyf”,“ababababyg”,“ababababyh”,“ababababyi”,“ababababyj”,“ababababyk”,“ababababyl”,“ababababym”,“ababababyn”,“ababababyo”,“ababababyp”,“ababababyq”,“ababababyr”,“ababababys”,“ababababyt”,“ababababyu”,“ababababyv”,“ababababyw”,“ababababyx”,“ababababyy”,“ababababyz”,“ababababza”,“ababababzb”,“ababababzc”,“ababababzd”,“ababababze”,“ababababzf”,“ababababzg”,“ababababzh”,“ababababzi”,“ababababzj”,“ababababzk”,“ababababzl”,“ababababzm”,“ababababzn”,“ababababzo”,“ababababzp”,“ababababzq”,“ababababzr”,“ababababzs”,“ababababzt”,“ababababzu”,“ababababzv”,“ababababzw”,“ababababzx”,“ababababzy”,“ababababzz”]

    6.4 模板总结

    表格内单词搜索():

    七、刷题分类

    1.动态规划

    「滚动数组思想」是一种常见的动态规划优化方法,在我们的题目中已经多次使用到,例如「剑指 Offer 46. 把数字翻译成字符串」、「70. 爬楼梯」等,当我们定义的状态在动态规划的转移方程中只和某几个状态相关的时候,就可以考虑这种优化方法,目的是给空间复杂度「降维」。如果你还不知道什么是「滚动数组思想」,一定要查阅相关资料进行学习哦。
    回顾这道题,其实这类动态规划的题目在题库中也出现过多次,例如「221. 最大正方形」、「1162. 地图分析」等。他们都以二维坐标作为状态,大多数都可以使用滚动数组进行优化。如果我们熟悉这类问题,可以一眼看出这是一个动态规划问题。当我们不熟悉的时候,怎么想到用动态规划来解决这个问题呢?我们需要从问题本身出发,寻找一些有用的信息,例如本题中:

    (i,j)(i, j)(i,j) 位置只能从 (i−1,j)(i - 1, j)(i−1,j) 和 (i,j−1)(i, j - 1)(i,j−1) 走到,这样的条件就是在告诉我们这里转移是 「无后效性」 的,f(i,j)f(i, j)f(i,j) 和任何的 f(i′,j′)(i′>i,j′>j)f(i', j')(i' > i, j' > j)f(i′,j′)(i′>i,j′>j) 无关。
    动态规划的题目分为两大类,一种是求最优解类,典型问题是背包问题,另一种就是计数类,比如这里的统计方案数的问题,它们都存在一定的递推性质。前者的递推性质还有一个名字,叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解,后者类似,当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时,我们可以往动态规划的方向考虑。
    

    通常如果我们察觉到了这两点要素,这个问题八成可以用动态规划来解决。读者可以多多练习,熟能生巧。

    2.分治算法

    3.回溯

    • 网络总结
      C++在做递归回溯算法相关题目时,递归函数形参传值和传引用运行速度有很大的差异。这是我这道题dfs函数的声明,主要区别是visited和word,一个是传值,一个是传引用。前者执行超时,后者在本题是32ms.
      个人理解为传值时每次递归调用都要在内存中新建立一个vector 来保存visit传入的值,但是传引用直接在visited原始位置操作,不需要进行新建变量与赋值,节省了代码运行的空间与时间开销。
      参见:79. 单词搜索

    八、基本语法

    • 对于vector变量,直接使用时,下标表示对应元素,使用一些函数时应该用其指针(迭代器),而不是下标
    //正确书写
    PaiLie.erase(PaiLie.begin()+k);
    //错误书写
    PaiLie.erase(k);
    
    //正确书写
    PaiLie.insert(PaiLie.begin()+iPL, cur);
    //错误书写
    PaiLie.insert(iPL, cur);
    
    • 对指针指向的变量进行操作要加括号
    (*pNum) ++;
    

    九、复习进度与总结

    JZ offer

    • 1
      错误注意:
      1.越界,j>=n,i<0;
      2.让起始位置从左下角或者右上角开始
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
      注意:是f(n-1)+f(n-2)而不是f(n-1)+2*f(n-2)
    • 11
    • 12
    • 13
    • 14
      错误注意:是要把前面所有的加起来,循环里需要再套循环;

    JZ1

    十、错误原因解析

    • 错误一
      错误描述:运行错误:请检查是否存在数组、列表等越界非法访问,内存非法访问等情况
    • 错误二
      错误描述:段错误:您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起。
      可能原因:
      1.递归无法结束,循环无法结束;
      2.遇到输入数据量为零的情况没有直接返回。
    • 错误三
      错误描述:In file included from main.cc:2: ./solution.h:39:5: error: non-void function does not return a value in all control paths [-Werror,-Wreturn-type]
      可能原因:
      1.“not all control paths return a value”, 这句话的意思是函数并不是所有分支都有返回值,所以需要增加判断并返回相应值;或增加总的返回值。
    • 错误四
      错误描述:runtime error: member access within null pointer of type ‘TreeNode’
      错误解释:运行时错误:'TreeNode’类型的空指针中的成员访问。
      解决方案:出现这种问题是访问了空指针的成员,在前面用if语句判断指针是否为空即可。
    • 错误五
      错误描述:AddressSanitizer:DEADLYSIGNAL43ERROR: AddressSanitizer: stack-overflow on address 0x7ffd4beabff8 (pc 0x00000034a876 bp 0x7ffd4beac010 sp 0x7ffd4beac000 T0)
      43ABORTING
    • 错误六
      错误描述:Line 5: Char 17: runtime error: variable length array bound evaluates to non-positive value 0
      解决方案:数组长度定义为了负数,不正确。

    总结


    三道题套路解决递归问题

    展开全文
  • 刷题攻略

    2020-01-03 17:31:44
    盲目刷题不可取,因此,刷题要一定要搞清楚刷题的目的和原因。其实无外乎4种: 如果想提升自己的思维能力,可以按照AC率由低到高二分查找匹配自己当前水平难度的题目,然后适当挑战高难度题(二分时间复杂度是O(logn...

    1, Leetcode

    https://blog.csdn.net/qq_39521554/article/details/79160815
    Leetcode刷题修炼手册
    一、刷题选择
    盲目刷题不可取,因此,刷题要一定要搞清楚刷题的目的和原因。其实无外乎4种:

    • 如果想提升自己的思维能力,可以按照AC率由低到高二分查找匹配自己当前水平难度的题目,然后适当挑战高难度题(二分时间复杂度是O(logn),至少比从易到难的O(n)节省时间)
    • 如果想巩固某一专题,那自然应该按照tag来刷题,但是因为所用的方法在求解前已知,不太利于思维能力的提升
    • 如果什么都不懂,那么建议随机刷题,一来可以涨见识,二来进步空间比较大
    • 如果想提高AC率或者增加自信,那么建议刷水题
      人与人之间还是有天赋差别的,但区别在于经验可以慢慢积累、
    再有个建议,题目如果太难超过当前自己能力的话,尝试一定时间后还是老老实实看题解吧

    二、刷题方法

    方法一:顺序法

    建议未刷过题的新人按着顺序(AC)来。前 150 题覆盖了很多经典题目和知识点,指针法类如『3 sum』系列,动规类如『regex matching』,搜索类题目如『Sodoku Solver』。

    基本熟悉知识点(图、树、堆、栈、链表、哈希表、记忆搜索、动态规划、指针法、并查集等)后,可以一类类标签强攻。Leetcode 右侧的标签系统虽然未必 100% 完整,但是大致分类做得还不错。

    面试前的一个月可以只做『Hard』标签的题目,因为一般两遍之后对于大部分『Medium』难度以下的题目都是肌肉记忆了。多练习『Hard』类题目可以让自己的思路更开阔,因为很多题目使用的奇淫巧技让人惊讶,比如 Leetcode 精心设计连续题号的『84. Largest Rectangle in Histogram』、『85. Maximal Rectangle』。

    方法二:标签法

    按照网站给大家排列的不同tags,起到模块化的复习和学习作用。举个例子:比如复习链表的内容,就选Linked List这部分的23个题目。刷完之后可以再总结一下常用的方法和数据结构与构造方式。请不要为了刷题而刷题,一定是为了弥补一部分的知识去做。

    三、刷题攻略

    TIP 2:

    善用收藏夹,要养成『一道题第二次练习尚不能解就加入收藏夹』的习惯,且需要定期清空收藏夹:每道题不需提示下通过两次后才能移出收藏夹。


    另一强帖

    https://www.jianshu.com/p/7bfbaf893a34

    LeetCode 刷题指南(一):

    为什么要刷题

    下面是我刷 LeetCode 的一些收获,希望能够引诱大家有空时刷刷题目。

    问题:抽象思维
    波利亚用三本书:《How To Solve It》、《数学的发现》、《数学与猜想》来试图阐明人类解决问题的一般性的思维方法,总结起来主要有以下几种:

    • 时刻不忘未知量。即时刻别忘记你到底想要求什么,问题是什么。(动态规划中问题状态的设定)
    • 试错。对题目这里捅捅那里捣捣,用上所有的已知量,或使用所有你想到的操作手法,尝试着看看能不能得到有用的结论,能不能离答案近一步(回溯算法中走不通就回退)。
    • 求解一个类似的题目。类似的题目也许有类似的结构,类似的性质,类似的解方案。通过考察或回忆一个类似的题目是如何解决的,也许就能够借用一些重要的点子(比较 Ugly Number 的三个题目:263. Ugly Number, 264. Ugly Number II, 313. Super Ugly Number)。
    • 用特例启发思考。通过考虑一个合适的特例,可以方便我们快速寻找出一般问题的解。
    • 反过来推导。对于许多题目而言,其要求的结论本身就隐藏了推论,不管这个推论是充分的还是必要的,都很可能对解题有帮助。

    刷 LeetCode 的最大好处就是可以锻炼解决问题的思维能力,相信我,如何去思考本身也是一个需要不断学习和练习的技能。

    此外,大量高质量的题目可以加深我们对计算机科学中经典数据结构的深刻理解,从而可以快速用合适的数据结构去解决现实中的问题。我们看到很多ACM大牛,拿到题目后立即就能想出解法,大概就是因为他们对于各种数据结构有着深刻的认识吧。LeetCode 上面的题目涵盖了几乎所有常用的数据结构:

    讨论:百家之长

    如果说 LeetCode 上面的题目是一块块金子的话,那么评论区就是一个点缀着钻石的矿山。多少次,当你绞尽脑汁终于 AC,兴致勃发地来到评论区准备吹水。结果迎接你的却是大师级的代码。于是,你高呼:尼玛,竟然可以这样!然后闭关去思考那些优秀的代码,顺便默默鄙视自己。

    除了优秀的代码,有时候还会有直观的解题思路分享,方便看看别人是如何解决这个问题的。@MissMary在“两个排序数组中找出中位数”这个题目中,给出了一个很棒的解释:Share my o(log(min(m,n)) solution with explanation,获得了400多个赞。

    你也可以评论大牛的代码,或者提出改进方案,不过有时候可能并非如你预期一样改进后代码会运行地更好。在 51. N-Queens 的讨论 Accepted 4ms c++ solution use backtracking and bitmask, easy understand 中,@binz 在讨论区中纳闷自己将数组 vector (取值非零即一)改为 vector 后,运行时间变慢。@prime_tang 随后就给出建议说最好不要用 vector,并给出了两个 StackOverflow 答案。

    当你逛讨论区久了,你可能会有那么一两个偶像,比如@StefanPochmann。他的一个粉丝 @agave 曾经问 StefanPochmann 一个问题:


    更强的,估计一般人看不懂

    http://mindhacks.cn/2008/04/18/learning-from-polya/

    跟波利亚学解题(rev#3)

    亚历山大学派最后一位伟大的几何学家,就曾在他恢弘的八卷本《数学汇编》中描述了其中的一种法则,他将它称为“分析与综合”,大意如下:

    • 首先我们把需要求解的问题本身当成条件,从它推导出结论,再从这个结论推导出更多的结论,直到某一个点上我们发现已经出现了真正已知的条件。
    • 这个过程称为分析。有了这条路径,我们便可以从已知条件出发,一路推导到问题的解。

    波利亚在他的三卷本中把这种做法叫做Working Backwards(倒过来解)。

    • 反过来推导

    很多我们熟知的经典题目也都是这种思路的典范,譬如《How To Solve It》上面举的例子:通过一个9升水的桶和一个4升水的桶在河里取6升水。这个题目通过正向试错,很快也能发现答案,然而通过反向归约,则能够不偏不倚的命中答案。另一些我们耳熟能详的题目也是如此,譬如:100根火柴,两个人轮流取,每个人每次只能取1~ 7根,谁拿到最后一根火柴谁赢;问有必胜策略吗,有的话是先手还是后手必胜?这个问题通过试错就不是那么容易发现答案了。同样,这个问题的推广被收录在《编程之美》里面:两堆橘子,各为m和n个,两人轮流拿,拿的时候你只能选择某一堆在里面拿(即不能跨堆拿),你可以拿1~这堆里面所有剩下的个橘子,谁拿到最后一个橘子谁赢;问题同上。算法上面很多聪明的算法也都是通过考察所求结论隐藏的性质来减小复杂度的,譬如刚才提到的单纯形问题,譬如经典面试题“名人问题”、“和最小(大)的连续子序列”等等。倒推法之所以是一种极为深刻的思维方法,本质上是因为它充分利用了题目中一个最不易被觉察到的信息——结论。结论往往蕴含着丰富的条件,譬如对什么样的解才是满足题意的解的约束。一般来说,借助结论中蕴含的知识,我们便可以更为“智能地”搜索解空间。

    5. 练习,练习

    本质上,练习并不产生新能力。然而练习最重要的一个作用就是将外显记忆转化为内隐记忆。用大白话来说就是将平时需要用脑子去想(参与)的东西转化为内在的习惯。譬如我们一开始学骑自行车的时候需要不断提醒自己注意平衡,但随着不断的联系,这种技能就内化成了所谓的程序式记忆(内隐记忆的一种),从而就算你一边骑车一边进行解题这样需要消耗大量脑力的活动,也无需担心失去平衡(不过撞树是完全可能的,但那是另一回事)。

    同样,对于解题中的思维方法来说,不断练习这些思维方法就能做到无意识间就能运用自如,大大降低了意识的负担和加快了解题速度。

    不过,并非所有的练习方法都是等效的,有些练习方法肯定要比另一些更有效率。譬如就解题来说,解题是一项涉及到人类最高级思维机制的活动,其中尤其是推理(归纳和演绎)和联想。而后者中又尤数联想是最麻烦的,前面提到,绝大多数时候启发式方法实质上都是在为联想服务——为了能像晃筛子那样把你脑袋里那个关键的相关知识抖落出来。并且,为了方便以后能够联想,在当初吸收知识的时候就需要做最恰当的加工才行,譬如前面提到的“抽象”加工,除此之外还有将知识与既有的知识框架整合,建立最多的思维连接点(或者说“钩子”)。对于知识的深浅加工所带来的影响,《找寻逝去的自我》里面有精彩的介绍(里面也提到了提取线索对回忆的影响——从该意义上来说运用启发式思维方法来辅助联想,其实就是进行策略性记忆提取的过程)。最后,人类的无意识思维天生有着各种各样的坏习惯,譬如前面提到的范畴陷阱就是创新思维的杀手,譬如根据表面相似性进行类比也是知识转移的一大障碍。更遑论各种各样的思维捷径了(我们平常进行的绝大多数思考和决策,都是通过认知捷径来进行的)。所以说,如果任由我们天生的思维方式发展,也许永远都避不开无意识中的那些陷阱,好在我们除了无意识之外还多出了一层监督机制——意识。通过不断反省思维本身,时时纠正不正确的思考方式,我们就能够对其进行淬炼,最终养成良好的思维习惯。反之被动的练习虽然也能熟能生巧,但势必花的时间更多,而且对于涉及复杂的思维机制的解题活动来说,远远不是通过钱眼往油壶里面倒油这样简单的活动所能类比的,倒油不像思维活动那样有形形色色的陷阱,倒油不需要联想和推理,倒油甚至几乎完全不需要意识的辅助性参与,除了集中注意力(而解题活动就算对于极其熟练的人来说也不断需要大量的意识参与)。所以对于前者,良好的思维习惯至关重要,而反省加上运用正确的思维方法则是最终养成良好思维习惯的途径。

    练习还有另外一个很重要的作用,就是增加领域知识(关于知识在问题解决中的作用,前面已经提到过)。我们看到很多人,拿到一道题目立即脑子里就反应出解法,这个反应快到他自己都不能意识到背后有什么逻辑。这是因为既有的知识(我们常说的“无他,实在是题做得太多了”)起到了极大的作用,通过对题目中几个关键元素或结构的感知,大脑中的相关知识迅速被自动提取出来。而对于知道但不熟悉相应知识(譬如很早我们就知道归纳法,但是很久以后我们才真正能够做到面对任何一道可能用归纳法的题目就立即能够想到运用归纳法),或者干脆就不知道该知识的人来说,就需要通过启发法来辅助联想或探索了。后者可以一定程度上代偿对知识的不够熟悉,但在一些时候知识的缺失则是致命的(参见上面第2点)。不过要注意的是,那种看到题目直接反应出答案的或许也不是纯粹的好事,因为这样的解题过程严重依赖于既有知识,尤其是做过的类似的题目,其思维过程绝大部分运用的是联想或类比,而非演绎或归纳。更重要的是,联想也分两种,被动联想和策略性联想(参考《找寻逝去的自我》),这里用的却是被动联想。所以,能直接反应出答案并不代表遇到真正新颖的题目的时候的解决能力,后者由于不依赖于既有领域知识,就真正需要看一个人的思维能力和习惯究竟如何了。

    7. 总结的意义

    解题练习的最重要目的不是将特定的题目解出来,而是在于反思解题过程中的一般性的,跨问题的思维法则。简单的将题目解出来(或者解不出来看答案,然后 “恍然大悟”),只能得到最少的东西,解出来固然能够强化导致解出来的那个思维过程和方法,但缺少反思的话便不能抽取出一般性的东西供更多的题目所用。而解不出来,看答案然后“哦”的一声更是等同于没有收获,因为“理解”和“运用”相差何止十万八千里。

    • 每个人都有过这样的经历:一道题目苦思冥想不得要领,经某个人一指点其中的关键一步,顿时恍然大悟——这是理解。但这个理解是因为别人已经将新的知识(那个关键的一步)放到你脑子里了,故而你才能理解。而要运用的话,则需要自己去想出那关键的一步。因此,去揣测和总结别人的思维是如何触及那关键的一步,而你自己的思维又为什么触及不到它,有一些一般性的原则可以指导你下次也能想到那个“关键的一步”吗,是很有意义的。我们很多时候会发现,一道题目,解不出来,最终在提示下面解出来之后,发现其中并没有用到任何自己不知道的知识,那么不仅就要问,既然那个知识是在脑子里的,为什么我们当时愣是提取不出来呢?而为什么别人又能够提取出来呢?我怎么才能像别人那样也提取出相应的知识呢?实际上这涉及到关于记忆的最深刻的clip_image012原理,实际上文中已经提到了一些。
    • 有兴趣的建议参考以下几本书:《追寻记忆的痕迹》,《找寻逝去的自我》,《Synaptic Self》,《Psychology of Problem Solving》
    • 一般性的思维法则除了对于辅助联想(起关键的知识)之外,另一个作用就是辅助演绎/归纳(助探),一开始学解题的时候,我们基本上是先读懂题目条件,做可能的一些显然的演绎。如果还没推到答案的话,基本就只能愣在那里等着那个关键的步骤从脑子里冒出来了。而所谓的启发式思维方法,就是在这个时候可以运用一些一般性的,所有题目都适用的探索手法,进一步去探索问题中蕴含的知识,从而增大成功解题的可能性。

    启发式的思维方法有很多,从一般到特殊,最具一般性的,在波利亚的《How to Solve It》中已经基本全部都介绍了。一些更为特殊性的(譬如“如果全局搜索空间没有递归结构,那么考虑分割搜索空间”,譬如那些“看到XX,要想到YY”的联系),则需要自己在练习中不断抽象总结。

    展开全文
  • PAT刷题技巧

    千次阅读 多人点赞 2018-12-29 17:02:37
    PAT刷题技巧PAT 刷题技巧PAT 是什么PAT 注意事项PAT 题型PAT 代替机试PAT 刷题技巧PAT刷题模板写在后面 PAT 刷题技巧 PAT 是什么 计算机程序设计能力考试(Programming Ability Test,简称PAT)旨在通过统一组织的...

    PAT 刷题技巧


    PAT 是什么

    计算机程序设计能力考试(Programming Ability Test,简称PAT)旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力,科学地评价计算机程序设计人才,为企业选拔人才提供参考标准。目前PAT已成为IT界的标准化能力测试,得到包括Google中国、Microsoft、雅虎、网易、百度、腾讯等在内的百余家大中小型各级企业的认可和支持,他们纷纷开辟了求职绿色通道,主动为PAT成绩符合其要求的考生安排面试,免除计算机能力设计方面的笔试环节。同时,PAT(甲级)一年内的成绩可作为浙江大学计算机学院硕士研究生招生考试上机复试成绩


    PAT 注意事项

    • 由考试中心负责考试的组织、日常管理和具体实施工作。
    • 每年分春、秋、冬季组织3次统一考试,考试时间根据场地可用的具体时间而定,大约分别在2-3月、8-9月、11-12月举行。
    • 每场考试分三个不同的难度级别:顶级(Top Level)、甲级(Advanced Level)、乙级(Basic Level)。三级别的考试在同一考场、同时举行。 考生须提前10分钟到达考场。
    • 正式考试为3小时、闭卷、上机编程测试。考生只可携带铅笔或水笔进入考场。
    • 考试成绩实时可查,证书立等可取。考试结束1小时后,考生即可在考场外指定地点领取证书。

    PAT 题型

    • 考试总分100 分。
    • 顶级考试一般出3题,题目描述语言为英文;甲级考试一般出4题,题目描述语言为英文;乙级考试一般出5题,题目描述语言为中文。
    • 每题要求考生按照严格的输入输出要求提交程序解决问题。程序须经过若干测试用例的测试,每个测试用例分配一定分数。
    • 每题的得分为通过的测试用例得分之和;整场考试得分为各题得分之和。提交错误不扣分。
    • 名次根据总得分决定,相同分数对应并列名次。
    • 每题分数的分布与题目难度成正比。顶级考试的分数分布一般为:30、35、35;甲级考试的分数分布一般为:20、25、25、30;乙级考试的分数分布一般为:15、20、20、20、25。

    PAT 代替机试

    一年内的顶级(Top Level) 和 甲级(Advanced Level) 可替代浙大考研复试的机试成绩。如果用PAT替代,必须在机试前向浙大申请使用PAT成绩替换,否则默认参加机试。申请使用PAT成绩替换者,不可参加复试机试。复试的机试成绩满分100分,甲级的成绩按照1:1的比例换算至机试成绩,而顶级的比例为1:1.5,即如果你使用PAT成绩进行替换,若甲级考了60分,机试成绩就是60分,若顶级考了60分,则你的机试成绩应当是60*1.5=90分,如果顶级成绩换算之后超出100分,机试最多也只能拿到100分,多出的分数不会计算到其他地方。


    PAT 刷题技巧

    这一章节应该是大家最关心的,在浙大考研群里,私底下或是公开也都有不少学弟学妹在问。我在这里提供一种我自认为的最方便的刷题方式。
    1.关于语言,我推荐使用cpp刷题,它的STL库非常适合刷题,而且运行速度也比python快,c语言也很快,但是它连个字符串类型都没有(字符数组刷题累死人),所以我直接放弃。
    2.对每个题我都使用同一个刷题模板,刷题模板是根据自己刷题经验来的,使自己可以尽快地到达解答问题的状态,而不是拘泥于使用库函数,代码风格的问题。
    3.对于PAT考场,考场的电脑太过老旧,装的编译器都不一定是最适合你的,所以你在报名的时候就要了解自己的考场情况,官网有各个考场编译器的配置情况。
    4.对于考研学生,初始结束之后可以尽快刷题了,没有基础的可以去买《晴神笔记》对照着学,这本书可以说是PAT刷题者必备了,其作者晴神也在考研群里每年也会给大家提供PAT模拟竞赛。当然,你基础很好的话,也可以买这本书参照一下。
    5.每天刷4-5题,一开始可能每天只能A一两题,到后面会越来越熟练的,一开始一定不要心急,要有自信,心态要稳。循序渐进,逐渐给自己加大难度。
    6.对于自己刷题的代码一定要留好并做好注释,一定要定期复习自己的代码,学习对于某一题使用了什么知识点,这样才能温故而知新。


    PAT刷题模板

    其实前面的话大家基本自己心里都清楚,关键是自己刷题的时候有没有经常因为输入的数据量太大,格式太繁琐,每次调试都得自己输入数据,调试的20%以上的时间都放在输入数据上面了,有的时候黑框框还不会复制,那这场考试基本就崩了。
    别着急,这些其实根本不是什么问题,用这个刷题模板就可以完全解决,你的精力完全放在解题上,而且你看这个模板又短又精,完全够你背下来!
    Here we go

    #include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<string.h>
    #include<algorithm> 
    #include<map>
    #include<vector>
    #include<queue>  
    using namespace std;   
        
    
    int main(){    
    #ifdef ONLINE_JUDGE    
    #else    
        freopen("1.txt", "r", stdin);    
    #endif    
    
    
    	/* your code */
      
        return 0;    
    }
    

    就这么短,怎么用呢?先在这个模板的同一级目录下建一个’1.txt’的文件,然后把输入全部放进去保存,然后就好了!之后你运行代码完全不用输入任何数据,模板会自行把文件中的数据读进来当做输入,不会有任何格式的差错,如果你在写’1.txt’的时候没错的话。
    之后每换一道题就只需要修改1.txt的内容,如果你还是要在黑窗口里复制粘贴的话,可以再黑窗口右键,然后你就知道了。

    好了,这就是老学长的刷题模板,其实非常简单,对于那些没有使用过这种刷题方式的人来说,希望对你们有帮助。


    写在后面

    个人刷题只刷了前面85题左右,相比较那些刷了好几遍题库的大佬还是有很大差距,我没买也没使用晴神笔记,如果买了我可能就会浪费少一点时间在网上查找资料了。
    我是2018年3月份考的PAT,当时题目虽然简单,但是我还是犯了个小错误,最后一分钟注意到的时候已经晚了,只考了97分,我在刷题的时候一直使用这么模板,其中的库函数也都是我经常用到的,所以在此推荐给大家。
    从2019年开始,每年考研复试机试成绩只能由前一年的PAT成绩来抵,例如,2019年的考生,只能用2018年3月、9月、12月的成绩来抵。而2018级3月份则是最后一次可以抵当年的考研机试(庆幸我赶上了末班车)。我个人猜测是因为2018年复试时间拖的太晚,是因为需要等机试考完,而机试又需要等PAT考完,这样就被拖迟了,所以今年干脆改了政策。这样以后的复试时间应该不会再那么晚了。


    好了,关于PAT的事情就是这么多,祝愿大家会有个好成绩!我自己刷题时候的代码都还留着,如果想要,可以私聊我或评论。

    展开全文
  • 如果不是为了面试AI工程师刷题有用吗?把时间都放在项目上不香嘛?作为一个战五渣,我特地去观察和询问了身边很多精通此道的大神,他们对于“刷题”还是保持着认可的态度:很清晰地理解问题的本质,...
  • 力扣刷题顺序

    2021-01-13 18:29:12
    力扣刷题顺序 力扣题目分类
  • // 设置两个指针,分别指向数组外围外1个单位,因为这个代码是不管怎样,先让指针移动一个位置 int j = r + 1; while (i < j) { while (q[++i] < x); while (q[--j] > x); if (i < j) swap(q[i]...
  • leetcode刷题心得

    万次阅读 多人点赞 2020-03-04 18:14:36
    本人以前大概搞过半年的算法,不是什么大佬,学得也不怎么样,一般般。leetcode只刷了200左右(没有水题),leetcode简单、中等级别的题目大部分都可以做。大部分公司的笔试题也还行,当然了像字节、腾讯那种就太难...
  • 这篇文章算是一个刷题的开端,主要写写为什么选择leetcode刷题怎样刷题等问题。 1.为什么刷题? 我觉得要想成为一名合格的程序员需要具备这么几块能力: 计算机基础知识:主要包括计算机专业本科学的一些课程...
  • 刷题计划

    2019-09-24 16:52:46
    Description Input Output Sample Input 10000 12 2 1 3 2 9999 3 1 1 3 2 1 3 2 10000 3 2 9999 3 Sample Output 1 9999 1 9999 9999 10000 9999 9999 10000 ......
  • sql刷题

    2019-09-07 08:48:24
    每个组各返回一个结果(不管它内部逻辑是怎样的) 。如下,小黄有两个,但是 并且,针对group by返回一个这个特性,可以用来 查询最高/最低 SELECT dept, MAX(salary) AS MAXIMUM FROM sheet GROUP BY ...
  • 我该怎样高效刷题

    千次阅读 2016-04-24 13:41:31
    这些天,我一直在想,我该怎样高效的去刷题,而不是一味的只追求数量。我觉得这不只是我一个人的问题,我相信这对于很多人来说,这都是必须去明白的。因为这取决于你能在这条路上走多远,能够爬上多高的高度。对于每...
  • 关于leetcode刷题详细介绍

    万次阅读 多人点赞 2018-10-01 14:39:12
      虽然刷题一直饱受诟病,不过不可否认刷题确实能锻炼我们的编程能力,相信每个认真刷题的人都会有体会。现在提供在线编程评测的平台有很多,比较有名的有 hihocoder,LintCode,以及这里我们关注的 LeetCode。 ...
  • LeetCode 按照怎样的顺序来刷题比较好?

    千次阅读 多人点赞 2020-06-08 11:01:19
    LeetCode 按照怎样的顺序来刷题比较好? 首先,这个问题是不完整的。问题只问了一半,事情也只能做到一半。我们要看到更深层的需求,比别人多想一点,才能比别人优秀一点。 刷题效果 = 刷题路径 * 刷题方法。 ...
  • C++刷题秘籍

    2019-03-16 09:44:17
    C++刷题秘籍 在经过一个暑假的刷题过程中(只刷了pat乙级和洛谷新手村),总结了一下一些很有用的知识和函数,了解这些可以再刷题的时候避免自己写一大堆不必要的代码,在做题的时候节省时间。不同的函数也可以开阔...
  • 再也不用c刷题了!!——c++刷题必备

    千次阅读 多人点赞 2020-05-02 16:01:31
    还记得大一上学期含泪用c刷题,那感觉简直爽的不行,后来结识c++发现我错过了一个亿,所以分享一下用c++刷题所用到的基础知识。 结识算法和OJ就是在大学阶段,当时老师提到OJ,我也是一脸懵,啥是OJ? [外链图片转存...
  • 在线上刷题练习的过程中,会设置刷题模式。那么怎样开启刷题功能呢,本教程介绍了如何进行线上刷题练习的操作方法。
  • coding刷题体会

    2021-04-13 06:19:04
    刷哪些题目? 按照我每个类型的给的题目在Lintcode或者Leetcode中找到对应的题目刷就行。题目题号是和Lintcode对应的,找起来更方便,但是Leetcode的社区做的更...怎么检验自己刷的怎么样了,是否可以参加面试? 随便找
  • 力扣刷题记录

    2020-11-18 21:41:04
    这里写自定义目录标题力扣刷题记录134加油站题目1432. 改变一个整数能得到的最大差值 力扣刷题记录 马上要进入大三下学期,准备考研的生活。为了提高考研复试的竞争力,准备在这段时间做一些算法题目,目标是每天...
  • 力扣刷题插件

    2020-08-18 19:37:15
    点击蓝色“力扣加加”关注我哟加个“星标”,带你揭开算法的神秘面纱!❝这是力扣加加第「14」篇原创文章❞之前我做了一个视频, 介绍我的刷题浏览器扩展插件,视频地址:https://www....
  • 课小观准备了一些题目,准备参加教师资格证笔试的各位小可爱快来检验一下自己学得怎么样!记得刷完题点击文末在看或者在留言区打卡。PS:公众号后台回复【提分】可免费领取教师资格证考前速效提分包,材料分析题答题...
  • 蓝桥杯题库刷题

    2020-08-23 01:10:14
    蓝桥杯题库刷题 基础篇 11.十六进制转十进制 (1)题目 (2) 代码 #include<iostream> #include<cstring> #include<cmath> using namespace std; typedef long long LL; string str; int main...
  • 首先,刷题是为了了解思路;...开始刷题时,确实是无从下手,因为从序号开始刷,刷到几道题就遇到 hard 的题型,会卡住很久,后面去评论区看别人怎么刷题,也去 Google 搜索最好的刷题方式,发现按题型刷.
  • 力扣刷题总结

    2020-10-15 17:52:11
    力扣刷题总结 1.两数之和(题号1) 1.第一种思路:暴力破解,遍历两个数组,第二次循环从J=i+1开始 2.第二种思路:利用HashMap减少查找的次数,用containkey将查找出来的值放进数组 2.一维数组的动态和(题号...
  • 科四刷题笔记

    2019-01-22 13:17:01
    科四刷题笔记
  • 前缀和刷题

    2021-01-27 23:14:48
    前缀和刷题一维前缀和二维前缀和领地选择连续自然数求和股票买卖激光炸弹借教室 一维前缀和 定义:原数组 a1、a2、a3...a_1、a_2、a_3...a1​、a2​、a3​... 下标从1开始 ​ 前缀和 Si=a1+a2+...+aiS_i=a_1+a_2+....
  • 力扣刷题手册

    2020-08-03 16:06:22
    前言: 随缘刷题,认真记录 文章目录字符串相加K次操作转字符串找出数组游戏的赢家粉刷天花板整理字符串 字符串相加 8/3力扣415字符串相加. 用字符串的方法来模拟加法过程,使用双指针从尾部开始遍历,逐个相加: ...
  • 洛谷刷题总结

    千次阅读 2019-05-18 22:35:54
    虽然提交不能AC,但是在刷题的时候也能从中学到很多东西,今下午了解了几个重要的点, 第一点:就是itoa(char *,int ,int)函数,这个函数的作用三个参数分别是字符数组,整数,最后一位是指明进制数, 该函数的 作用...
  • LeetCode刷题笔记

    2019-05-19 18:06:25
    - 数据结构设计 数据结构设计 单词查找树 题目:https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/ 通过/提交:0/4 思路: 错误:没太明白题干要求的addWords要求是怎么样的,搜索的...
  • 今天不刷题

    2014-08-30 23:30:10
    如题,今天不刷题。 今天感觉到有点累,早上从飞机

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,245
精华内容 4,898
关键字:

怎样刷题