单词搜索

212. 单词搜索 II

思路:

虽然明明知道硬写一定会,超时,但还是写了一个。

超时后考虑什么优化:自然想到了字典树。不过没有想透彻:

  • 用字典树构造dfs遍历的路径,❌ :dfs搜索的路径不需要被查询,因为只出现一次

  • 正确做法:用字典树存储所有words,方便查询。或者进一步的,在dfs过程中,可以直接用字典树进行搜索剪枝。

    Orz

Read more

Write a diff command

写一个简单的diff

晚上在看酷壳的 rsync 核心算法,突然感受到算法光芒的笼罩之中,突然想起之前很好奇的一个问题,diff是怎么实现的?

Read more

安全状态

思路

建图后,需要判断一次深搜路径上有无重复点出现,并用涂色法记录整条路径上的安全或者不安全状态。

Read more

go

go generics came here!

在 go1.17 beta 已经实现了go 泛型,虽然它现实在一个不稳定的版本,我已经心心念了好久了,毕竟不是每个人都喜欢自己写一遍各种类型的Min

Read more

之字形标记

1104. 二叉树寻路

思路

思路其实很清晰,翻转出层序的下标,在遍历的时候,把层序下标翻转回之字下标即可。

良好的编程习惯其实蛮重要的,每个变量都有自己的用处。良好的代码对后续的修改友善的。

Read more

二叉树中距离为K的节点

思路

这题还是有点点复杂的,距离为K的节点,完全可以分为两类,target节点构成树的K-dis节点,和其路径经过target祖父节点的节点。分类搜索即可,考虑到后者需要定点采集,所以用回溯的方式获取。

Read more

二叉树的两个错误节点

CD169 找到搜索二叉树中两个错误的节点

如果两个节点交换,那么在中序遍历里就有至少一次降序,可能有两个相邻的节点交换,或者两个不相邻的节点交换,产生一个或两次降序。

Read more

二叉树累加和的最长路径

CD165 在二叉树中找到累加和为指定值的最长路径长度

写的好心酸, 明明只有有类似的题目接触到。又是没思考就动手

  • 先静态化构造二叉树(不要嫌麻烦,一题写好了所有题目都可以用)

  • 前序遍历节点,

    • 记录根节点到当前节点的综合newadd,只记录最短长度的newadd路径。
    • 同时判断,newadd - target之和是否有在当前遍历路径下,是否存在从根节点到同路径的某个节点连成的路径。
    • 最后回溯时,为了下次遍历路径不受这里遍历数据影响,消减掉当次遍历时候设置新路径长度。
Read more

单链表中K节点逆序

思路

超级大杂烩,左程云出的题的风格。

K节点逆序+ K节点检测 + 链表链接

代码

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list()
{
    int val, n;
    scanf("%d", &n);
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}


list_node * reverse_knode(list_node * head1, int K)
{
    list_node whead = {0, head1};
    list_node *before, *pre, *p, *next; // pre, p, next 单单在K个节点逆序起作用; bofore指向逆序链表的前一个节点
    p = head1;
    before = &whead;
    
    while(p) {
        int k = 0;
       list_node *now = before;
        while(k < K){
            k++;
            if (now) now = now->next;
        
        }
        if(now == nullptr) break;
        
        k = 0;
        pre = nullptr;
        list_node *kend = before->next;
        while(k < K) {
            k++;    
            next = p->next;
            p->next = pre;
            pre = p;
            p = next;
            if(next) next = next->next;
        }
        before->next = pre;
        kend->next = p;
        
        before = kend;
        
    }
    return whead.next;

}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    int K;
    scanf("%d", &K);
    list_node * new_head = reverse_knode(head, K);
    print_list(new_head);
    return 0;
}

约瑟夫问题

思路:

实际上是一个非常巧妙的数学问题。

从结果上来看, 如果只剩最后一个人(最后的幸存者),那么被杀掉一定是它。那么它的当前号码为1,问其原坐标?思考一下新旧人列的下标关系:

Old(k+1) : 
1 2 3 4 5 6 7 --- k + 1 
New(k)
4 5 6    m -1 (s) 1 2 3 

可能的一种形式,其中s是old被杀掉的人的下标。 且s = (m - 1 )% (k + 1) + 1

但不难发现有: old = (new + s - 1) % (k + 1) + 1

综上有逆推式: old =(new + m - 1) % (k + 1) + 1

Read more

人生的不幸

人生中最痛苦不是身体残疾,目不能视,耳不能听;也不是原生家庭带来性格扭曲,从小的身微言轻,家境清贫;更不是高考落榜,身陷囹圄,工作遇阻。而是无法接受现状,不能认清自我的能力的边界,贪求不能现在得到的欲望,终日惶惶思索财路,入睡夜夜欲求不止。这种终身收自己精神折磨的人,从不愿意放自己一马的人,才是不幸的人。那些绝望求死的人,至少还有死的勇气。

伤口会自己长好,伤疤会慢慢消除,一切要建立在你先接受自己如果不完美的前提下。如果你每天把自己的伤口翻出来给自己看,给别人看,那么她不仅愈合不了,还可能感染加重。很多时候,无休止的自怜,求怜,反而加重了心态对人的控制。

有时候,挡在我们面前的墙都是我们自己砌上去的,只要你愿意,你就能把他轻轻推倒。只是你愿不愿意的问题。其实人生很简单,只要能去除不必要的负担,和自己将和,摆脱精神的折磨,自主掌握命运。

现在城市里很多年轻父母为了子女不输在起跑线上而操碎了心,实际上,一个人能跑多远,更多地取决于他对自己人生有多大的掌控能力,而这个掌控能力,其中最重要的部分是处理挫折和失败的能力。有时候你觉得自己不成功,并不是环境和机遇的问题,而是你修炼不够。

最大子矩阵

类似于面试题17.24;

不过是每个单元的元素只是一,可以把问题转化为求取面积。

直接用单调栈求取从一个柱子可扩展的的最大面积即可。

代码

#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;
int n , m;
vector<int> height;
int maxarea = 0;

void caculateArea(vector<int>&area){
    for(int i = 0; i < area.size(); ++i){
        if(area[i]) height[i] += area[i];
        else height[i] = 0;

    }
    stack<int> st;
    height.push_back(0);
    
    for(int i = 0; i < height.size(); ++i){

        while(st.size() && height[st.top()] >= height[i]){
            int hei = height[st.top()];
            st.pop();
            int l = st.size() ? st.top() : -1;
            maxarea = max(maxarea, (i - 1 - l)* hei);
          //  cout << l << ' ' << maxarea << ' ' << i - 1  << ' ' << hei<< endl;

        }
        st.push(i);
    }
    height.erase(height.end() - 1);
    
}


int main(){
    cin >> n  >> m;
    vector<int> maze(m);
    height.resize(m);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j) cin >> maze[j];
        caculateArea(maze);
    }
    cout << maxarea << endl;
    return 0;
}

面试题 17.24. 最大子矩阵

面试题 17.24. 最大子矩阵

思路:

本题是最大连续子数组的二维follow up.

一维情况下,可以直接使用多种算法求解:

  1. 累加数组+二维搜索左右边界, $O(N^2)$

  2. 二维搜索左右边界同时累加数字,$O(N^2)$

  3. 分治算法,把问题maxarr(i, j)分解为maxarr(i, mid)maxarr(mid + 1, j)。其中子数组可能在左右两端数组中或者横跨两个段,所以从中间向两边搜索最大连续数组和Sum1,如此解决了一个基本问题,并且递归的将小问题解决,获取总的问题的解。$O(NLogN)$

  4. 线段树做法,同样也是分治的思想,但是考虑的更多。maxarr(i, j)分解为maxarr(i, mid)maxarr(mid + 1, j)。基本问题是arr(i, j)中的sumlsumr, sumisumm,分别代表从左边开始的子数组的和,从右边开始的子数组的和,在中间扩展的子数组的和,和整个数组的和。而我们要大问题的sumi就是所要求的值,巧妙的地方在于问题的分解,sumi可以就是子数组的sumi和左子段的sumr与右子段的suml之和最大值。其他同理。

  5. DP做法,以dp[i]arr[i]为结尾的和最大的连续子数组的和。状态更新方程为
    $$
    dp[i] = max(dp[i - 1] + arr[i], arr[i])
    $$

这很有趣,实际上就是舍弃掉可能为负数的dp[i - 1], 另外在舍弃时也可以记录下数组起点。更进一步的观察,空间可以优化到O(1)

二维情况下,虽然非常相似,但是解法一时想不到直接扩展到二维。但是问题可以化解为一维。

在确定了矩阵行数据,或者首先遍历矩阵的上下界后,顺道求出该矩阵的在各各列的和。之后便可以用一维的做法求出连续列的最大和。

复杂$O(N^3)$。

Read more

二分图匹配

二分图匹配

二分图匹配是个经典问题——两组节点在图上尽可能的匹配。

匈牙利算法以不断寻找增光路的方式,寻找更多的匹配;

思想如下:

  1. 从未匹配的点c开始寻找链接的点v,如果v也是未匹配,则匹配成功。如果该点已经匹配了u,则递归尝试让u匹配其他节点。
  2. 如果v匹配失败,那就找找c的其他点。

题解参考

Read more

割点算法

割点算法Tarjan

割点算法 引入了建立在DFS生成树的遍历节点的时间戳概念,如果一个节点u的子节点v可以找到一条不经过u以外的路径到达u的祖先,那么显然有一条通路可以回到u的祖先。反之,如果存在v找不到这么一条路径回到u的祖先,那么显然u是一个割点,他分割了v所在的子树和其他子树(如果u不是根的话,包括祖先所在子树)。

image-20210509113600747

那么一个割点有多少子树呢?
首先,一个割点的对应的v是独立在各个子树的吗?是的,如果存在v1v2都找到路径,且在一个子树中,那么必然有v1可以通过v2找到u,那么在DFS搜索的时候,必定会一次遍历v1v2。所以每个割点对应的子树只会搜索到一个v
扩展一下, 那么经过去掉割点的图最多有几个连通块?

Read more

312. Burst Balloons

312. Burst Balloons

思路:

Hard题做了才有收获啊!lc上题库里几道经典的具有锻炼思维和思考能力的题。

  1. 拿到手,首先映入脑海里明显应该是贪心或者分治算法:仔细思考一下,贪心发现没有依据,也没有例子;分治算法把考虑把求取问题dp(l, r)——开区间的(l,r)一组气球全部戳爆以后,可以获取最大金币数量。如果第一选取k个气球戳爆,则有子问题(l,k)(k,r),但是可以发现两个子问题是相互依赖的。也就是说一个问题解的选择会影响另一个问题的解的选择。所以这个思路也不行。

  2. Amazing的是,我们可以反过来考虑问题!我们把整个过程逆序,把戳爆存在的气球,变成从一个气球都不存在,添加一个个不存在的气球。dp(l, r)问题就是在寻找,把(l, r)中的所有位置填满气球,可以获得最大金币数量。思考一下如何分解为子问题:
    $$
    dp(l, r) = max_{i = l + 1}^{r - 1}[dp(l , i) + dp(i, r) + nums[i] * nums[l] * nums[r]]
    $$
    具体计算可以用记忆化搜索和DP计算。

看了下大神的解法,居然还有用启发式搜索的!太顶了!

Read more

cmake学习索引

Cmake笔记

Cmake是跨系统,C++现行标准构建标准的build system of build system`.

比较好的学习资源如下:

understand Cmake ✅: 一个简单的接受

cmake official web : 对各个命令有最详细的解释,当字典用

Cmake Tutorial: 💖从零基础解释CMake基础概念,看完这个再看官方教程就很简单了

cmake tutorial ✅ :跟着做比较有意思,可以多多尝试,就是有点花时间。后面部分内容可以看看

Cmake Detailed tutorial ✅: 最详细,有很多项目经验

看完了,直接上手项目或者看其他开源项目如何管理也是有点启发滴。当然对照着一个真实项目学习Cmake也有点帮助。

Read more

438. Find All Anagrams in a String

思路:

双指针,指向模式串str的子串首位s和末尾+1e

遍历思路:

  1. 不断添加e位置上的字符c
  2. 如果c不属于p,则双指针跳过c
  3. 如果c属于p,则更新。
    1. 但是如果包括的c字符太多了,则移动s直至数量符合条件
    2. 如果所有字符数量都添加完全一致,则添加结果。移动s一位,更新即可。

看了其他题解,发现有一个条件我忽略了,指针之间的距离是相等的,也就是说这是一个滑动窗口问题~草了。

那这很简单,维护一下窗口值就行了。

可以说滑动窗口就是一个简单的双指针。

Read more