画卷篇

以代码为笔,绘用户界面之韵

事件循环

浏览器有哪些进程和线程

  1. 浏览器进程: 主要负责界面显示、用户交互、子进程管理等。浏览器进程内部会启动多个线程处理不同的任务。
  2. 网络进程: 负责加载网络资源,网络进程内部会启动多个线程处理不同的网络任务
  3. 渲染进程:一个标签页一个进程,渲染进程启动后,会开启一个渲染主线程,主线程负责执行 html、css、js 代码,默认情况下浏览器会为每个标签页开启一个新的渲染进程,以保证不同标签页之间互不影响。

渲染主线程是如何工作的

  • 解析 html
  • 解析 css
  • 计算样式
  • 布局
  • 处理图层
  • 每秒把页面画 60 次
  • 执行全局 js 代码
  • 执行事件处理函数
  • 执行计时器的回调函数

排队

渲染主线程

  1. 最开始的时候渲染主线程会进入一个无限循环
  2. 每一次循环会检查消息对列中是否存有任务存在,如果有,就获取第一个任务执行,执行完一个后进入下一个循环;如果没有,则进入休眠状态
  3. 其他线程(包括其他进程的线程)可以随时向消息队列添加任务。新任务会加到消息队列的末尾。在添加新任务时,如果主线程是休眠状态,则会将其唤醒以继续循环拿取任务。

  这样任务就有条不紊,持续执行下去,整个过程称之为事件循环(消息循环)

代码

何为异步

执行代码中,会遇到一些无法立即处理的任务,比如:

  • 计时完成后需要执行任务:setTimeout、setInterval
  • 网络通信完成后需要执行任务:XHR、 Fetch
  • 用户操作后需要执行的任务: addEventListener 如果让主线程等待这些任务的时机到达,就会导致主线程长期处于阻塞状态,从而导致浏览其卡死。

异步任务 渲染主线程承担着机器重要的工作,无论如何不能阻塞

因此浏览器选择异步任务来解决问题 image

使用异步的方式,渲染主线程用不阻塞

# Q:如何理解 JS 的异步?
Ajs 是一门单线程的语言这是因为它运行在浏览其的渲染主线程中而渲染主线程只有一个
渲染主线程承担着诸多的工作渲染页面执行 js 代码都在其中运行
如果使用同步的方式就有可能导致主线程阻塞从而导致消息队列中的很多其他任务无法得到执行
这样一来一方面导致繁忙的主线程任务白白消耗时间另一个方面无法及时更新给用户造成卡死现象
所以浏览器采用异步的方式来避免具体的做法是当某些任务发生是比如计时器网络事件监听,
主线程江南任务交给其他线程去处理自身立即结束任务执行转而执行后续代码
当其他线程完成是将事先传递的回调函数包装程任务
加入到消息队列的末尾等待主线程调度执行
在这种异步模式下浏览器永不阻塞从而最大限度的保证了单线程的流畅执行

js 为何会阻塞渲染

<html lang="en">

<body>
    <h1>run block</h1>
    <button> change</button>
    <script>
        var h1 = document.querySelector('h1');
        var btn = document.querySelector('button');

        //死循环指定的时间
        function delay(duration) {
            var start = Date.now();
            while (Date.now() - start < duration) { }

        }
        btn.onclick = function () {
            h1.textContent = "blocking";
            delay(3000);
        };
    </script>
</body>

</html>

任务有优先级吗

任务没优先级,消息队列有 FIFO 根据 W3C 解释:

棋谱篇

C语言趣味算法

◀ 返回

汉诺塔

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从上往下按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新排在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

#include <stdio.h>

void move(char x, char y)
{
    static int cnt = 0;
    printf("%d %c => %c\n", ++cnt, x, y);
}

void hanno(int n, char a, char b, char c)
{
    if ( n == 1 )
        move(a, c);
    else {
        hanno(n-1, a, c, b);
        move(a, c);
        hanno(n-1, b, a, c);
    }
}

int main( void )
{
    hanno(3, 'A', 'B', 'C');
    return 0;
}

百鸡百钱

今有鸡翁一,值钱伍;鸡母一,值钱三;鸡鶵三,值钱一。凡百钱买鸡百只,问鸡翁、母、鶵各几何?

#include <stdio.h>

int main( void )
{
    int x;
    int y;
    int z;

    for (x=0; x<=100; x++)
    {
        for (y=0; y<=100; y++)
        {
            z = 100-x-y;
            if (z%3==0 && 5*x+3*y+z/3==100)
            {
                printf("公鸡%d,母鸡%d,小鸡%d\n",
                    x, y, z);
            }
        }
    }

    return 0;
}

常胜将军

现有21根火柴,两人轮流取,每人每次可以取走1至4根,不可多取,也不能不取,谁取最后一楰火柴谁输。请编写一个程序进行人机对弈,要求人先取,计算机后取;计算机一方为“常胜将军”

棋谱篇

路线规划

◀ 返回

Grid-Based Route (Re-)Planning

路线规划用于自主代理的导航,例如自动驾驶车辆、机器人和人类(考虑地图服务)基于网格的路由规划研究在二维空间中,将一个初始单元到一个目标单元的路由划分为阻塞或空的网格单元的问题.图1a显示了一个由10行10列组成的示例网格,第0行和第0列的初始单元格由I表示(是的,我们从零开始计算),第9行和第9列的目标单元格由G表示。绿色箭头显示了从I到G的计划移动,阻塞路段显示为橙色正方形的块。

路线规划图1

随着环境的变化,即块被移除或放置在一些新的单元上,计划的路由可能变得无效如图所示。例如一个机器人,按照计划的路线从图1a到达图1b网格中的单元格I和单元格g,它将被阻塞,故需要并重新规划绕过障碍物,如图1c所示。

Input Data

输入数据从文件中获取,如图2所示,第1行为表格大小,第2行为起始坐标,第3行为目的坐标。第三行开始为路线障碍节点坐标直到读取有“$”。之后行指示的是路线。 路线规划图2

  • Reading and Analyzing Input Data

解决问题的第一步,读取文件数据并分析。将各节点关键信息如下方式显示:

[localhost]>ass2-soln<test0.txt ==STAGE 0======================================= The grid has 10 rows and 10 columns. The grid has 9 block(s). The initial cell in the grid is [0,0]. The goal cell in the grid is [9,9]. The proposed route in the grid is: [0,0]->[0,1]->[0,2]->[0,3]->[0,4]-> [1,4]->[2,4]->[3,4]->[4,4]->[5,4]-> [6,4]->[7,4]->[8,4]->[9,4]->[9,5]-> [9,6]->[9,7]->[9,8]->[9,9]. The route is valid!

Drawing and Replanning

进入第二阶段,当路线中遇到障碍时需要重新规划路线。首先打印路线如图3所示: 重新规划的路线的整体思路是:如何图1f所示,将遇到障碍点为原点扩散,离原点的距离。我们通过上下左右的方式遍历可访问的每个节点放入唯一队列当中,并判别放入的节点是否等于阻塞点的下个节点。如果相等则遍历结束,并获取了重新规划的路线。将队列的课访问路线添加到之前的路线当中。 路线规划图3

  • coding

下列是我遍历路线的代码:

算法圣子

我靠刷题一统春秋

《算法圣子:我靠刷题一统春秋》

小说框架设定

世界观背景

  • 时代:平行宇宙的春秋时期,算法为尊
  • 核心规则:解决问题的算法复杂度决定社会地位
    • O(1) → 圣人境界(可封侯拜相)
    • O(log n) → 宗师境界(各国争抢)
    • O(n) → 高手境界(一方豪强)
    • O(n log n) → 才子境界(受人尊敬)
    • O(n²)及以上 → 凡人境界

主角设定

姬玄(男主):

  • 表面身份:齐国放荡不羁的七王子
  • 真实身份:穿越者+算法系统宿主
  • 系统名称:“天机算法系统”
  • 系统功能:每日发布算法题,完成可获得:
    • 金币(春秋货币)
    • 声望值(影响地位)
    • 算法典籍(如《九章算法》《孙子算经·进阶版》)
    • 特殊道具(“快速幂符”、“动态规划卷轴”)

势力划分

  1. 齐国:算法治国,推崇分治思想(男主所在)
  2. 秦国:暴力算法派,崇尚穷举之力
  3. 楚国:递归深修派,讲究大道归一
  4. 鲁国:伦理算法派,注重算法道德
  5. 江湖算法盟:散修高手聚集地

第一章:链表分治,初露锋芒

剧情大纲

场景一:朝堂风波

齐王宫,算法殿。

齐王(面色凝重):“今日天机系统出题——‘链表分区’。
谁能以最低复杂度解之,赏千金,封上卿!”

大殿中央,悬浮着天机系统的光幕:
【题目:给定链表头结点 head 和整数 x,将链表分隔成两部分,
使得所有小于 x 的节点都在大于等于 x 的节点之前】
【要求:保持节点初始相对位置】
【当前最优解:O(n²),提供者:秦使商鞅】

秦使(傲然):“我大秦‘双重遍历法’,虽复杂度稍高,
但气势磅礴!齐国可有更高明解法?”

满朝文武,面面相觑。

场景二:男主登场

“父王,儿臣有一解。”

众人回头,只见姬玄慵懒地倚在殿柱旁,
手中还把玩着酒樽,一副醉醺醺的模样。

齐王(怒):“玄儿!朝堂重地,休得胡闹!”
宰相田忌(冷笑):“七王子整日流连花丛,
也懂算法?莫要贻笑大方。”

姬玄(晃晃悠悠走上前):“不就是个 O(n) 的事儿嘛...
给我两个虚拟头结点,一次遍历,原地修改...”

他随手拿起笔,在光幕上写下了代码框架:

场景三:算法演绎(关键剧情)

姬玄一边写,一边内心与系统对话:

【系统】:宿主正在解题“链表分区”
【系统】:检测到最优解法思路
【系统】:正在生成算法可视化...

突然,光幕上出现动画:
- 两个透明袋子(dummy1、dummy2)浮现在空中
- 链表节点如珍珠般被分类装入
- 指针如灵蛇游走,精准连接

姬玄(口中念念有词):
“p1管小数袋,p2管大数袋,原链p来遍历...
遇小给p1,遇大给p2,断开重连莫要乱...”

【系统提示】:
时间复杂度:O(n)
空间复杂度:O(1)
击败率:100%

场景四:震惊朝野

光幕绽放金光!
【新纪录诞生!O(n)解法,提供者:齐国七王子姬玄】

秦使(震惊):“一次遍历?!这...这是何等高深算法!”
田忌(难以置信):“你...你何时修得如此造诣?”

姬玄(打个哈欠):
“昨夜梦中有仙人传授,名曰‘双指针分区法’...
哦对了,这算法有几个要点:
1. 虚拟头结点,避免边界判空烦
2. 断开原链接,防止成环惹祸端
3. 最后要拼接,小数链表接大数前...”

【系统】:任务完成!
【奖励】:
- 金币+5000
- 声望+1000
- 获得“链表大师”称号
- 解锁新典籍《算法导论·春秋特别版》

场景五:暗中交易

当晚,姬玄府邸。

神秘商人(黑袍遮面):
“殿下今日的O(n)解法,魏王愿出万金购买专利。”
姬玄(把玩着金币):“不卖。但可以授权使用,
每月抽成...对了,你们魏国最近在搞‘合并K个有序链表’?
我这有O(n log k)的解法,要不要?”

商人(激动):“要!多少钱都行!”
姬玄(微笑):“钱?我要你们魏国的‘优先队列’秘法。
还有...听说你们有个算法天才叫庞涓?
让他来齐国交流交流...”

【系统】:触发支线任务“挖角庞涓”

场景六:女主登场

次日,算法学宫。

楚国公主芈月(女主)前来交流学习,
她以“递归解法”闻名列国。

芈月(挑衅):“听闻七王子擅长迭代,
可敢与我比试‘二叉树直径’一题?”
姬玄(眼前一亮):
“美...不对,芈月公主愿意赐教,荣幸之至。
不过赌点什么?我若赢了...公主陪我游临淄城三日?”
芈月(脸红):“你若输了,当众承认楚国算法天下第一!”

【系统】:新任务发布
【题目】:二叉树直径
【特殊要求】:使用递归但空间复杂度O(1)
【奖励】:若胜利,获得“月公主的好感度+50”

后续章节框架

第二章:递归之美,情愫暗生

  • 姬玄与芈月比试递归 vs 迭代
  • 展示Morris遍历法,O(1)空间震惊四座
  • 两人共同优化“汉诺塔问题”解法
  • 感情线发展:从竞争对手到算法知己

第三章:列国算法大会

  • 各国派遣算法天骄参赛
  • 题目:“寻找旋转排序数组的最小值”
  • 姬玄使用二分查找O(log n)碾压全场
  • 揭露秦国使用“作弊算法”的阴谋

第四章:系统升级,危机显现

  • 天机系统发布“NP完全问题”
  • 列国无人能解O(n^k)以下
  • 姬玄发现系统背后有神秘组织操控
  • 获得“近似算法”特殊能力

第五章:算法治国

  • 姬玄用“贪心算法”优化齐国赋税
  • “图论算法”解决各国交通问题
  • “动态规划”制定战略资源分配
  • 引发“算法伦理”大辩论

每日更新机制

每章结构

  1. 朝堂/江湖出题(现实问题转化为算法题)
  2. 各方势力解法展示(展示不同思路)
  3. 男主降维打击(给出最优解)
  4. 奖励与成长(系统奖励+势力变化)
  5. 感情/权谋支线(丰富剧情)
  6. 下集预告(明日题目剧透)

明日题目预告(第二章):

【芈月的挑战】:
“给定一棵二叉树,求其直径(任意两节点间最长路径)”
【当前最佳】:O(n²)递归,楚国秘法
【姬玄目标】:O(n)一次遍历
【剧情冲突】:比试中有人暗中破坏,篡改测试用例...

算法知识点融入技巧

  1. 招式命名:如“快慢指针法”叫“阴阳双鱼步”
  2. 境界比喻:递归深度=修仙层级
  3. 道具设计:哈希表=“天罗地网符”
  4. 比试场景:擂台赛=在线判题系统(OJ)

人物成长体系

姬玄的算法技能树

基础层(已掌握):
├── 链表操作(O(n))
├── 双指针技巧
└── 虚拟头结点

进阶层(待解锁):
├── 递归优化(尾递归)
├── 动态规划(背包问题)
└── 图论算法(最短路径)

宗师层(后期):
├── 数论算法(加密解密)
├── 近似算法(NP问题)
└── 并行算法(多线程思想)

红颜知己线

  1. 芈月(楚国公主):递归专精,纯真傲娇
  2. 西施(越国间谍):图论高手,身世神秘
  3. 郑旦(算法商人):贪心算法,精明算计

写作建议

每章必备元素

  1. 一道清晰算法题(可在章末附解法)
  2. 至少两个不同复杂度的解法对比
  3. 系统奖励的趣味描述
  4. 一个算法技巧的通俗解释
  5. 埋下后续剧情伏笔

俏皮话术示例

  • “这时间复杂度,比我追姑娘还慢!”
  • “空间复杂度O(1),这就叫‘一叶知秋’!”
  • “暴力解法?那是莽夫行为!”
  • “看我分治思想——‘分而治之,各个击破’!”

读者互动设计

  • 每章结尾让读者猜明日题目
  • 征集现实问题转化为算法题
  • 读者提供解法思路可成书中龙套角色