前言 今天终于刷完了 Leetcode 上的链表专题，虽然只有 31 道题（总共是 35 道，但有 4 道题加了锁）而已，但也陆陆续续做了两三个星期，严重跟不上原先计划啊。先写一篇博客总结一下这阵子刷链表题的收获吧，有输入也要有输出。这里就不花篇幅介绍链表的一些基本概念了，不清楚的看官就自行百度一下吧，本文主要介绍一些常见的链表题和解题思路。 正文 缓存 不得不说使用数组 / map 来缓存链表中结点的信息是解决链表题的一大杀器，覆盖问题的范围包括但不限于：在链表中插入 / 删除结点、反向输出链表、链表排序、翻转链表、合并链表等，Leetcode 上 31 道链表绝大部分都可以...

写在前面的话 进程（process）和线程（thread）是操作系统的基本概念，但是它们比较抽象，不容易掌握。 1 计算机的核心是CPU，它承担了所有的计算任务。它就像一座工厂，时刻在运行。 2. 假定工厂的电力有限，一次只能供给一个车间使用。也就是说，一个车间开工的时候，其他车间都必须停工。背后的含义就是，单个CPU一次只能运行一个任务。 3. 进程就好比工厂的车间，它代表CPU所能处理的单个任务。任一时刻，CPU总是运行一个进程，其他进程处于非运行状态。 4. 一个车间里，可以有很多工人。他们协同完成一个任务。 5. 线程就好比车间里的工人。一个进程可以包括多个线程。 6. ...

约瑟夫环 问题描述：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），数到 m 的 士兵会被杀死出列，之后的士兵再从 1 开始报数。直到最后剩下一士兵，求这个士兵的编号。 1、方法一：数组 在第一次遇到这个题的时候，我是用数组做的，我猜绝大多数人也都知道怎么做。方法是这样的： 用一个数组来存放 1，2，3 … n 这 n 个编号，如图（这里我们假设n = 6, m = 3） 然后不停着遍历数组，对于被选中的编号，我们就做一个标记，例如编号 arr[2] = 3 被选中了，那么我们可以做一个标记，例如让 arr[...

链接：https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。 为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。 输入描述: 输入有多组数据。 每组数据一行，包含一个整数n (1≤n≤100000)。 输出描述: 对应每一组输入，输出第n个斐波那契数的最后6位。 #include<stdio....

链接：https://www.nowcoder.com/questionTerminal/d95d98a2f96e49078cd7df84ba0c9d79 和中国的节日不同，美国的节假日通常是选择某个月的第几个星期几这种形式，因此每一年的放假日期都不相同。具体规则如下： 1月1日：元旦 1月的第三个星期一：马丁·路德·金纪念日 2月的第三个星期一：总统节 5月的最后一个星期一：阵亡将士纪念日 7月4日：美国国庆 9月的第一个星期一：劳动节 11月的第四个星期四：感恩节 12月25日：圣诞节 现在给出一个年份，请你帮忙生成当年节日的日期。 输入描述: ...

描述 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超...

写在前面的话 今天我介绍的主题是贪心算法。这是相对比较容易的一种算法。我这里不给出定义，因为大家可以自行网络搜索。咱们直接看例子。 贪心算法，如果不用手动证明一个问题的数学性质的话，其实是比较简单的。看这样一个例子：假设有一个背包，其最大容量是50KG，现在有各种不同价值的液体，比方说，有水，其价值是10 每千克，共100KG；酒精，其价值是20 每千克，共30KG；有油，价值25每千克，共30KG。问什么样的方案才能使得背包里装的液体的总价值最大？显然，这是一道小学生都会的题目，拣贵的装呗。这谁不会。那就是把30KG油先装了，因为油最贵嘛，剩下20KG的容量装酒精，因为酒精比水贵。...

1、二叉查找树的缺点 二叉查找树，相信大家都接触过，二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大，如图 基于二叉查找树的这种特点，我们在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。 之所以说是正常情况下，是因为二叉查找树有可能出现一种极端的情况，例如 这种情况也是满足二叉查找树的条件，然而，此时的二叉查找树已经近似退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，可想而知，我们必须不能让这种情况发生，为了解决这个问题，于是我们引申出了平衡...

写在前面的的话 关于字符串匹配算法有很多，之前我有写过一篇 KMP 匹配算法： https://blog.csdn.net/dreamispossible/article/details/91359237 不懂 kmp 的建议看下，写的还不错，这个算法虽然很牛逼，但在实际中用的并不是特别多。至于选择哪一种字符串匹配算法，在不同的场景有不同的选择。 在我们平时文档里的字符查找里 采用的就是 Boyer-Moore 匹配算法了，简称BM算法。这个算法也是有一定的难度，不过今天，我选用一个例子，带大家读懂这个字符串匹配 BM 算法，看完这篇博客，保证你能够掌握这个算法的思想。 首先我先给出一个字...

题目描述 在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。 给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。 测试样例： 4,[0,7,1,6],[1,5,0,6] ...

题目描述 小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3… 这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。 例如： N = 4，M = 24： 4->6->8->12->18->24 于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板 输入描述: 输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 10...

题目描述 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。 输入描述: 输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000) 第二行为n个正整数A [i] (32位整数)，以空格隔开。 输出描述: 输出所求的方案数 #include<stdio.h> long long dp[1005]; int ori[1005]; int main() { int N, M; int i,j; ...

字符串匹配算法 字符串匹配是计算机的进行的非常频繁的算法。简单的说，有一个字符串 I have a dream. 。我想知道的事情是，里面是否包含另一个字符串 dream ？ 因为执行的非常频繁，所以算法的效率也就十分重要。而本文所说的KMP算法，无疑是速度上面的佼佼者，它可以在 O(n+m) 的时间完成匹配。 KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法） 朴素的匹配方法 谈到KMP算法，就理所应当先说一说朴素的匹配方法。设待匹配串长度为 n，模版串长度为 m。 最朴素的方法就是...

案例一        给定一个整数 N，那么 N 的阶乘 N! 末尾有多少个 0？例如： N = 10，则 N！= 3628800，那么 N! 的末尾有两个0。       有些人心想，这还不简单，直接算出 N！的值，然后用除以 10 来判断多少个 0 就可以了。       有些人则这样想，直接算 N！的值再来除以 10 判断多少个 0 的话肯定会出现溢出问题，于是开始思索：一个数乘以 10 就一定会在末尾产生一个零，于是，我们可以从“哪些数相乘能够得到 10 ”入手。       没错，只有 2 * 5 才会产生 10。 注意，4 * 5 = 20 也能产生 0 啊，不...