VIM 常见命令

  • 用 h j k l 表示⬅️⬇️⬆️➡️
  • x → 删除字符
  • dw → 删除单词 (光标需在第一个字母)
  • dd → 删除整行 (会存在 Vim 里)
  • u → 撤回一条命令
  • U → 撤回一行的命令(对一行操作)
  • y → 复制
  • p → 取出 Vim 内容并放在此处 / 粘贴
  • ctrl + g → 查看当前行数
  • G → 跳到尾部 
  • 行数 + G → 跳到xx行
  • gg → 跳到头部
  • / → 搜索
  • 用 n 往下找
  • 用 N 往上找
  • % → 移动光标到对应括弧
  • :s /old / new/g → 替换将该行的
  • :q → 不保存退出
  • :wq → 保存并退出
  • :w → 只保存不退出
  • :help → 打开help 文件
  • ctrl + w → 在文件中转换

141. 环形链表

虽然昨天今天的题目都是简单,但还是记录一下几天这道有点意思的题目

如果用内存为O(N)的话非常简单直接多开一道空间看是否所有的节点都被经过至少一次,大于一次则证明有环的存在。但当我打开题解讨论时,“快慢指针”这个概念提起了我的兴趣

题解区看到的评论

很容易理解,快慢指针就是一块一慢两个指针,通过移动速度但一块一慢在琏表上运动,从而制造值。

像本题就是快慢指针的一个经典应用:判断是否有环

bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode* slow = head; //跑得慢的
        ListNode* fast = slow->next; //跑得快的
        while(fast && fast != slow){ //只要快指针没到尽头
            slow = slow->next; //慢指针跑一步
            if(fast->next) fast=fast->next->next; //快指针跑两步
            else return false; //说明没环
        }
        return fast; //根据fast的值来判断是否有环
    }

在环中,一快一慢两指针必然会相遇,所以可以借此来判断是否有环

除此之外,快慢琏表还在找中间值和删除倒数第N个节点上大有文章

找中间值:

一般来说在琏表中找中间值用的方法是遍历后,记录节点数,再从头找一半的那个节点,但通过快慢琏表就可以很轻松。我们可以吧快指针的速度设为慢指针的两倍,这样以来当快指针跑到重点的时候,慢指针刚好在中间点。

先用网上借的图( ̄▽ ̄),以后再自己画

删除倒数第N节点:和中间值类似,快指针快慢指针N步就可以了

75. 颜色分类

这才是舒舒服服的每日一题吗\(≧▽≦)/ 题目地址

因为是边上ESL边写出来的,所以先提交了最简单的解法:遍历两遍

第一遍

for (int i=0; i<nums.size(); i++) {
            if(nums[i]==0){
                a.push_back(nums[i]);
            }else if(nums[i]==1){
                b.push_back(nums[i]);
            }else{
                c.push_back(nums[i]);
            }
        }

第二遍

for (int i=0; i<a.size(); i++) {
            nums[i]=a[i];
        }
        for (int i=a.size(); i<a.size()+b.size(); i++) {
            nums[i]=b[i-a.size()];
        }
        for (int i=a.size()+b.size(); i<nums.size(); i++) {
            nums[i]=c[i-a.size()-b.size()];
        }

但其实根本不用那么麻烦,完全可以一次遍历就解决:

834. 树中距离之和

久久不刷题,一刷就遇到困难QAQ

题目链接

我提交的解法是参照了题解里的二次DSF的解法,然而官方给的是树形动态规划的解法,我会两种方法都分析:

二次DSF:

第一次DSF:

void dfs1(int child, int parent){
        for (int i=0; i<Graph[child].size(); i++) {
            if (Graph[child][i]!=parent) {
                dfs1(Graph[child][i], child);
                //cout <<Graph[child][i]<<cnt.size()<<endl;
                cnt[child]+=cnt[Graph[child][i]];
                ans[child]+=ans[Graph[child][i]]+cnt[Graph[child][i]];
            }
        }
    }

第二次DFS:

void dfs2(int child, int parent){
        for (int i=0; i<Graph[child].size(); i++) {
            if (Graph[child][i]!=parent) {
                ans[Graph[child][i]] = ans[child]-cnt[Graph[child][i]]+num-cnt[Graph[child][i]];
                dfs2(Graph[child][i], child);
            }
        }
    }