avatar

光和尘

有花满渚、有酒盈瓯

目录检索关于我

🔖 quiz分治追击

问题描述

给定一个长度为 N + 1 的数列 A=\lbrace a_0, a_1, a_2 \cdots, a_N \rbrace.
其中 1 \leqslant a_i \leqslant N,\; 0 \leqslant i \leqslant N,\; N \geqslant 1.

在满足以下限制的前提下找出数组中任意一个重复的数字:

  • 不能修改输入的数组;
  • 只能使用 O(1) 的额外空间;

分治法

分治算法的思想是不断收紧区间范围以确定重复的数字其值所在的区间范围,当区间长度为 1 时,则找到了那个重复的数字(相当于二分答案)。

算法描述

根据鸽巢原理易知,原数组中必然至少有一个重复的数字,即答案所在区间为 [1,N]。不妨取 \displaystyle x = \left\lfloor \frac{1+N}{2} \right\rfloor

🔖 acm算法动态规划背包问题

01背包

N 件物品和一个容量为 C 的背包。
其中,第 i 件物品体积为 v_i [1],价值为 w_i
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析

因为每件物品只有两种选择:放或不放入背包。且每件物品之间相互独立,即无论第 i 件物品怎么选都不影响第 j\;(i < j \leqslant N) 件物品的决策 [2]。故可以考虑前 i 件物品在背包剩余容量为 c 时的最佳决策,即记 f(i, c) 表示当背包剩余容量为 c,在前 i 件物品中做选择时可以获得的最大价值,不难得到状态转移方程:

f(i,c) = \max \big\lbrace f(i-1, c),\; f(i-1, c-v_i) + w_i \big\rbrace

🔖 reactreact reconciliation

预备知识

Reconciliation

使用 React 构建的应用,在初次渲染时 React 会调用的 render() 方法生成一棵 React Elements 树,在下一次 props, state 发生变化时,将重新调用 render() 方法并得到一棵新的 React Elements 树。为了高效地完成更新,需要计算出两棵树之间的差异,然后仅对差异部分应用更新。收集差异的过程被称为 Reconciliation(React@15 及其之前的协调算法又被称为 Stack Reconciler),有些地方也直接将它等同于 diffing 算法

还有一个关于 Reconciliation 的定义:React 拥有多个渲染器,如

🔖 quiz动态规划

问题描述

K 个鸡蛋和 N 层楼,测试最多试验几次可以测出让鸡蛋摔碎的最低楼层。假定鸡蛋无磨损,即如果在第 x 层楼扔下没碎,那么在第 x 层楼重复扔无限次都不会碎。没碎的鸡蛋可以重复使用(用于测试),已碎的鸡蛋无法继续使用。

算法一

N 层楼看作长度为 N 的区间,记 dp(k, n) 表示至多使用 k 个鸡蛋测出区间长度为 n 的楼层里任意楼层是否能摔碎鸡蛋的最少试验次数,则状态转移方程为:

dp(k, n) = \min \big\lbrace \max \lbrace dp(k-1, x-1), dp(k, n-x) \rbrace \; \big\vert \; 1 \leqslant x \leqslant n \big\rbrace + 1

🔖 networkportsshnetstat

本文未完成,长期更新中...

端口和进程

  • 列出所有进程 id 和端口信息

     
    $ sudo netstat -ntlp
  • 杀死占用了指定端口的进程

     
    $ sudo netstat -nltp\
    | grep ':1001\|:1002'\
    | awk '{print $7}'\
    | grep -o '^[0-9]\+'\
    | sort\
    | uniq\
    | xargs kill -9

    其中:

    • sudo netstat -nltp: 列出所有进程 id 和端口信息(如果不使用 root 权限,有些进程 id 不会显示)
    • grep ':1001\|:1002: 过滤出使用了端口号 1001 或 1002 的进程
    • awk '{print $7}'
© 2017-2022 光和尘有花满渚、有酒盈瓯