la la la

原题链接 题目描述 给定一个由 nnn 个节点组成的网络，用 nxnn x nnxn 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j]=1graph[i][j] = 1graph[i][j]=1 时，节点 iii 能够直接连接到另一个节点 jjj。 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。 我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。 请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。 示例 1： 输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] 输出：0 示例 2： 输入：graph = [[1,1,0],[1,1,1],[0,1,1]], i ...

原题链接 题目描述 给出了一个由 nnn 个节点组成的网络，用 n×nn × nn×n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 iii 能够直接连接到另一个节点 jjj。 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。 假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。 如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。 请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。 示例 1： 输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] 输出：0 示例 2： 输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial ...

解决的问题 并查集解决了两个问题： 迅速将两个集合合并成一个集合。 迅速查询两个元素是否在同一集合中。 原理 将一个集合看成一棵树，树根的编号就是整个集合的编号。每一个节点都可以找到自己的父节点，p[x]表示x的父节点。 问题 如何判断树根：p[x] == x。 如何求x的集合编号：while ( p[x] != x ) x = p[x];。 如何合并两个集合：只需要修改其中一个集合根元素的编号就可以了。假设p[x]、p[y]是x、y集合的编号，只需要p[x] = y或者p[y] = x即可。 路径压缩优化 如何一个集合树比较高，查找路径会比较长，最差可退化成 O(N)O(N)O(N) 。所以在查询的时候，可以将路径中每一个节点直接指向根节点。 这样优化后，查询效率几乎逼近 O(1)O(1)O(1) 。 问题是如何解决的 修改两个集合中任意一个根节点的值即可。 对于节点x、y，只需判断x、y节点的根节点是否相等即可。 例子 原题链接 题目描述 一共有 nnn 个数，编号是 1∼n1∼n1∼n，最开始每个数各自在一个集合中。 现在要进行 mmm 个操作，操作共有 ...

原题链接 题目描述 不使用任何内建的哈希表库设计一个哈希映射（HashMap）。 实现 MyHashMap 类： MyHashMap() 用空映射初始化对象 void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。 int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。 void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。 示例： 输入： ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2 ...

原题链接 题目描述 不使用任何内建的哈希表库设计一个哈希集合（HashSet）。 实现 MyHashSet 类： void add(key) 向哈希集合中插入值 key 。 bool contains(key) 返回哈希集合中是否存在这个值 key 。 void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。 示例： 输入： ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] 输出： [null, null, null, true, false, null, true, null, false] 解释： MyHashSet myH ...

原题链接 题目描述 一场比赛中共有 nnn 支队伍，按从 000 到 n−1n - 1n−1 编号。每支队伍也是 有向无环图（DAG） 上的一个节点。 给你一个整数 nnn 和一个下标从 000 开始、长度为 mmm 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从 uiu_iui​ 队到 viv_ivi​ 队的有向边。 从 aaa 队到 bbb 队的有向边意味着 aaa 队比 bbb 队 强 ，也就是 bbb 队比 aaa 队 弱 。 在这场比赛中，如果不存在某支强于 aaa 队的队伍，则认为 aaa 队将会是 冠军 。 如果这场比赛存在 唯一 一个冠军，则返回将会成为冠军的队伍。否则，返回 −1-1−1 。 注意 环 是形如 a1,a2,...,an,an+1a_1, a_2, ..., a_n, a_{n+1}a1​,a2​,...,an​,an+1​ 的一个序列，且满足：节点 a1a_1a1​ 与节点an+1a_{n+1}an+1​ 是同一个节点；节点 a1,a2,...,ana_1, a_2, ..., a_ ...

原题链接 题目描述 你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。 给你一个下标从 000 开始的字符串 s ，请你用故障键盘依次输入每个字符。 返回最终笔记本屏幕上输出的字符串。 示例 1： 输入：s = "string" 输出："rtsng" 解释： 输入第 1 个字符后，屏幕上的文本是："s" 。 输入第 2 个字符后，屏幕上的文本是："st" 。 输入第 3 个字符后，屏幕上的文本是："str" 。 因为第 4 个字符是 'i' ，屏幕上的文本被反转，变成 "rts" 。 输入第 5 个字符后，屏幕上的文本是："rtsn" 。 输入第 6 个字符后，屏幕上的文本是： "rtsng" 。 因此，返回 "rtsng" 。 示例 2： 输入：s = "poiinter" 输出："ponter ...

原题链接 题目描述 请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。 实现 FrequencyTracker 类： FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。 void add(int number)：添加一个 number 到数据结构中。 void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。 bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。 示例 1： 输入 ["FrequencyTracker", "add", "add", "hasFrequency"] [[], [3], [3], [2]] 输出 [null, null, null, true] 解释 FrequencyTracker ...

在安装完Debian后，vi编辑器键盘不能正常使用，使用下面方法解决： 编辑文件/etc/vim/vimrc.tiny，将 compatible改成nocompatible非兼容模式； 并添加一句：set backspace=2（注：主要看最后几行） cat /etc/vim/vimrc.tiny " Vim configuration file, in effect when invoked as "vi". The aim of this " configuration file is to provide a Vim environment as compatible with the " original vi as possible. Note that ~/.vimrc configuration files as other " configuration files in the runtimepath are still sourced. " When Vim is invoked d ...

Git 分布式版本管理工具。 分布式版本控制系统没有“中央服务器”，每个人电脑都是一个完整的版本库，这样在工作的时候就不需要联网了，多人协作只需要各自的修改推广给对方，就可以看到对方的修改了。 安装 Git - Downloads (git-scm.com)，在官网下载，然后安装就可以了。 如果选择自解压，需要配置环境变量。 打开控制台窗口，输入git --version，成功输出版本号就意味着成功安装。 安装完成后，首先要做的事情是设置用户名和邮箱，每次Git提交都会使用该用户信息。 git config --global user.name "username" git config --global user.email "example@example.com" 如果已经设置过，再次输入就可以覆盖之前设置的。 查看配置信息： git config --global user.name git config --global user.email 使用 获取本地仓库 要使用Git对代码进行版本控制，首先需要获得本地仓库。在需要管理的 ...