2023-05-17：一个正整数如果能被 a 或 b 整除，那么它是神奇的。给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。输入：n = 4, a = 2, b = 3。输出：6。

工程概论 - 电梯调度模拟软件设计思路问题建模及基本假设查阅18层大楼的层高和电梯速度，再结合便于软件开发的目的，不妨设电梯的速度为0.5层/秒，且为匀速运动，没有加减速过程。考虑到实际电梯容量和便于图形化的原因，不妨设电梯容量为12人。考虑到进出电梯的人越多，电梯停留时间越长，不妨设为每秒钟电梯可以出一人或者进一人。考虑到出现人群的分布不是均匀的，尤其在 1楼有非常大的吞吐量，所以设置人群生成规则如下:    25%的人群 : 1楼出发,到达 random(0,20)    25%的人群 : random(0,20)出发,到达1楼    50%的人群 : random(0,20)出发 到达 random(0,20)设人群的人数为 random(1,5)技术选型首先，在所有同学都已经有 C 和 Java学习经验的基础上，最关键的技术瓶颈在于GUI层。经过交流，团队中只有一名同学掌握有GUI 开发的经验，技术栈是 .NET 的 C# + WPF。但是会 C#的只有一人，如果承担了所有的开发工作就会导致效率低下，所以要将程序解耦为算法层和GUI层。后来算法同学决定使用Python。因为程序的数据规模非常低，使用 Python不会造成性能瓶颈，而且可以降低语言层面的复杂度。算法层和GUI层之间的通信，一开始使用了命令行调用、标准输入输出的方式。算法层和GUI层定义了一致的数据结构，并且使用JSON 进行数据传递。但这种方式需要使用者也拥有 Python环境，且该方式在非GUI开发者的电脑上出现异常，难以调试。所以决定转用 HTTP协议，使用 Flask 对算法进行服务端的封装，再使用 Docker部署在服务器上，对外提供API。这样使用者的电脑只需要 .NET Framework环境就可以运行程序。此外，以后还可以使用 Web 端 / QT / Android / IOS等不同前端技术及平台开发运行在不同操作系统上的前端程序。核心算法简介该电梯调度算法主要基于 LOOK调度算法。该算法按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求，当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向，从而实现对电梯的有效调度。此外由于电梯1只停在单数层,电梯2只停在双数层,只有电梯3可以停在任意层。这个约束条件看似引入了新的复杂度，其实恰恰让三个电梯失去了联系，大大降低了复杂度。显然，只存在唯一一种调度分配情况，就是单数层到单数层的人由电梯1负责，双数层到双数层的人由电梯2负责，剩下由电梯3负责。3个电梯之间互不干扰，实现非常简便。在后续实践中，也验证了此调度分配情况可以基本完成负载均衡分配，效率高。基本数据类型定义person：搭乘电梯的乘客。其属性包括：come_time（出现的时间）、from_floor（起始楼层）to_floor（目标楼层）、current_floor（当前楼层）、in_which_elevator（所在电梯,可取0，1，2，3，分别指不在电梯中、在第一个电梯中、在第二个电梯中、在第三个电梯中）、is_out（是否完成电梯乘坐）elevator：电梯。其属性包括：current_floor（当前楼层）、move_direction（运行方向）floor：楼层。其属性包括：floor_up_people =[]（上行人群）、self.floor_down_people =[]（下行人群）、up_button（上升按钮）、down_button（下降按钮）算法伪代码//已知第t秒时的状态,进行调度,给出t+1时的状态时间循环（每循环一轮为一秒）//处理person到达事件遍历person数组，如果p.come_time==t（该乘客首次出现）将该乘客分配给对应的楼层 更新对应楼层电梯按钮更新楼层people数组（分为上行人群和下行人群）//处理电梯//对每个电梯，根据电梯的move_direction分类处理（move_direction取0，1，2，分别代表电梯静止、上行、下行）//（这一秒结束）代表continue，不再执行循环体剩下的部分 如果电梯静止遍历所有楼层，检测楼层电梯按钮 如果楼上有人按电梯电梯设置为上行（这一秒结束） 如果楼下有人按电梯电梯设置为下行（这一秒结束） 如果本层楼有人 如果此人上行电梯设置为上行（这一秒结束） 如果此人下行 电梯设置为下行（这一秒结束）如果电梯上行 如果电梯没有对齐某一楼层（如在3.5层） 电梯向上运行半层更新乘客状态（这一秒结束） 如果电梯对齐了某一楼层如果电梯中有乘客抵达目标楼层 更新该乘客的状态（这一秒结束）如果电梯人数已满 电梯向上运行半层 更新乘客状态（这一秒结束）如果楼层有人要进电梯 更新人的状态 更新楼层的状态如果楼层上行person数组为空 楼层上行按钮置False （这一秒结束）如果电梯内人数不为零 向上半层，并且更新乘客状态（这一秒结束）如果电梯内人数为零 如果电梯以上的楼层还有人向上半层，并且更新乘客状态（这一秒结束） 如果电梯以上的楼层没有人电梯状态改为静止（这一秒结束） //下行同理 //其余两个电梯同理软件功能不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。每天早上，那些差5分钟就迟到的人，在等电梯时，一般会做两件事：    第一，在心里骂电梯慢    第二，在心里暗算着电梯调度如何优化前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。为了上班不扣工资不迟到，我们决定通过调整电梯调度算法来实现对电梯运行载客的优化，以达到节约时间的目的。本程序基于我们的电梯调度算法，计划使用三个电梯同时模拟各层楼随机出现人前往不同楼层来验证本算法的可靠性。并且为了使运行结果明显，本程序还增添了可视化界面，使测试人能够清晰明了的观察本程序的运行情况。运行结果通过分析最终采用3个电梯，1号电梯只停奇数楼层和1楼，2号电梯只停偶数电梯和1楼，三号电梯所有楼层都停。经过多次测试，每次测试时长均超过10分钟，程序运行稳定，能够满足预想的最优化调度电梯，尽可能的缩短人员的等待时间，来实现效率最大化。in.json 运行顺利，没有故障，对实际的电梯调度具有参考意义。结构框图在这里插入图片描述软件流程图在这里插入图片描述在这里插入图片描述运行界面截图在这里插入图片描述在这里插入图片描述在这里插入图片描述软件测试及截图测试文件为algorithm_test.py文件。该文件为测试算法的一个测试文件，读取test_json文件夹中的测试文件，调用算法运行，与正确结果进行对比，相同returntestsuccess。交互选择初始人为设定乘楼梯人的属性（come_time,from_floor,to_floor,current_floor,in_which-elevator,is_out）,把设定的属性写在test_json文件夹中的in1.json和in2.json文件中，把正确的结果写在该文件夹下的out1.json和out2.json文件中。在这里插入图片描述在这里插入图片描述♻️ 资源在这里插入图片描述大小： 1.33MB➡️ 资源下载：https://download.csdn.net/download/s1t16/87390787————————————————版权声明：本文为CSDN博主「神仙别闹」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/s1t16/article/details/129314916

安排电影院座位如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，它表示第 3 行第 8 个座位被预约了。请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。示例 1：输入：n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]输出：4解释：上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。    1    2    3解法：位运算判断解题思路： 其实思路很简单，每行最多能容纳两个四人家庭，而第一个位置跟最后一个位置并不会对结果造成影响所以我们用一个8位的数字来进行判断，当第i个位置被预定之后，我们就将i-2位的数字变成1，没被预定即为0，然后将该数字跟当前行用一个哈希表联系起来当预定数字全部遍历完之后，我们只要取出哈希表中的值进行以下操作即可判断是否能容纳四人家庭    跟11110000按位或计算，如果结果仍是11110000,说明四个0的位置可以容纳一个四人家庭    跟11000011按位或计算，同理    跟00001111按位或计算，同理完整代码：class Solution {    public int maxNumberOfFamilies(int n, int[][] reservedSeats) {        int left = 0b11110000;        int middle = 0b11000011;        int right = 0b00001111;        Map <Integer, Integer> occupied = new HashMap <Integer, Integer> ();        for (int[] seat: reservedSeats) {            if (seat[1] >= 2 && seat[1] <= 9) {                int origin = occupied.containsKey(seat[0]) ? occupied.get(seat[0]) : 0;                int value = origin | (1 << (seat[1] - 2));                occupied.put(seat[0], value);            }        }        int ans = (n - occupied.size()) * 2;        //seat[1] = 1 || seat[1] = 10的就是坐两组家庭的，他们不会出现在哈希表中        for (Map.Entry <Integer, Integer> entry : occupied.entrySet()) {            int row = entry.getKey(), bitmask = entry.getValue();            if (((bitmask | left) == left) || ((bitmask | middle) == middle) || ((bitmask | right) == right)) {                ++ans;  // 每一排座位只能坐一组家庭，因为出现在哈希表表示在[2,9]至少有一个座位被预约了            }        }        return ans;    }}    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25    26心得体会其实看到这道题我就觉得挺简单的，但是没想到用哈希表和按位或计算来简化代码，用了一大堆if语句，后面受不了了就看了题解————————————————版权声明：本文为CSDN博主「jump_into_zehe」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/jump_into_zehe/article/details/107544321

写在前面GitHubTensorFlow原文档TensorFlow版本：2.3引言Keras的Tokenizer是一个分词器，用于文本预处理，序列化，向量化等。在我们的日常开发中，我们经常会遇到相关的概念，即token-标记、tokenize–标记化以及tokenizer–标记解析器。Tokenizer类允许通过将每个文本转换为整数序列（每个整数是字典中标记的索引）或转换成矢量（其中每个标记的系数可以是二进制的）的矢量化语料库，基于单词数 ，基于TF-IDF等等。形如如下使用创建方式：tf.keras.preprocessing.text.Tokenizer(    num_words=None,    filters='!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~\t\n',    lower=True,    split=' ',    char_level=False,    oov_token=None,    document_count=0,    **kwargs)    1    2    3    4    5    6    7    8    9    10参数    num_words：根据单词频率排序，保留前num_words个单词，即仅保留最常见的num_words-1个单词    filters: 一个用于过滤的正则表达式的字符串，这个过滤器作用在每个元素上，默认过滤除‘`’字符外的所有标点符号，制表符和换行符    lower：boolean值， 标记是否将文本转换为小写    split：字符串值， 分词分隔符    char_level：如果为True，则进行字符级别的分词    oov_token：如果给出的话，它将被添加到word_index中，并用于在text_to_sequence调用期间替换词汇外的单词，即用来补充原文本中没有的词。默认情况下，将删除所有标点符号，从而将文本转换为以空格分隔的单词序列（单词可能包含’字符，如I’am）， 然后将这些序列分为标记列表，并将它们编入索引或向量化。注意力， 0是保留索引，不会分配给任何单词。所以科学使用Tokenizer的方法是，首先用Tokenizer的 fit_on_texts 方法学习出文本的字典，然后word_index 就是对应的单词和数字的映射关系dict，通过这个dict可以将每个string的每个词转成数字，可以用texts_to_sequences，这是我们需要的，然后通过padding的方法补成同样长度，在用keras中自带的embedding层进行一个向量化，并输入到LSTM中。方法    fit_on_texts(texts) ：        参数 texts：要用以训练的文本列表。        返回值：无。    texts_to_sequences(texts) ：        参数 texts：待转为序列的文本列表。        返回值：序列的列表，列表中每个序列对应于一段输入文本。    texts_to_sequences_generator(texts) ：        本函数是texts_to_sequences的生成器函数版。        参数 texts：待转为序列的文本列表。        返回值：每次调用返回对应于一段输入文本的序列。    texts_to_matrix(texts, mode) ：        参数 texts：待向量化的文本列表。        参数 mode：‘binary’，‘count’，‘tfidf’，‘freq’ 之一，默认为 ‘binary’。        返回值：形如(len(texts), num_words) 的numpy array。    fit_on_sequences(sequences) ：        参数 sequences：要用以训练的序列列表。        返回值：无    sequences_to_matrix(sequences) ：        参数 sequences：待向量化的序列列表。        参数 mode：‘binary’，‘count’，‘tfidf’，‘freq’ 之一，默认为 ‘binary’。        返回值：形如(len(sequences), num_words) 的 numpy array。    get_config:        将标记器的配置返回为Python字典，标记器使用的字数字典被序列化为纯JSON，以便其他项目可以读取配置        返回值：带有tokenizer配置的Python字典    to_json：        返回包含标记器配置的JSON字符串，要从JSON字符串加载标记器，请使用keras.preprocessing.text.tokenizer_from_json(json_string)。        返回值：包含标记器配置的JSON字符串属性    word_counts: 字典，将单词（字符串）映射为它们在训练期间出现的次数。仅在调用fit_on_texts之后设置。    word_docs: 字典，将单词（字符串）映射为它们在训练期间所出现的文档或文本的数量。仅在调用fit_on_texts之后设置。    word_index: 字典，将单词（字符串）映射为它们的排名或者索引。仅在调用fit_on_texts之后设置。    document_count: 整数。分词器被训练的文档（文本或者序列）数量。仅在调用fit_on_texts或fit_on_sequences之后设置示例from tf.keras.preprocessing.text import Tokenizer# Using TensorFlow backend.#  创建分词器 Tokenizer 对象tokenizer = Tokenizer()#  texttext = ["今天 北京 下 雨 了", "我 今天 加班"]#  fit_on_texts 方法tokenizer.fit_on_texts(text)#  word_counts属性tokenizer.word_counts# OrderedDict([('今天', 2),#              ('北京', 1),#              ('下', 1),#              ('雨', 1),#              ('了', 2),#              ('我', 1),#              ('加班', 1)])#  word_docs属性tokenizer.word_docs# defaultdict(int, {'下': 1, '北京': 1, '今天': 2, '雨': 1, '了': 2, '我': 1, '加班': 1})#  word_index属性tokenizer.word_index# {'今天': 1, '了': 2, '北京': 3, '下': 4, '雨': 5, '我': 6, '加班': 7}#  document_count属性tokenizer.document_count# 2    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16    17    18    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33需要注意的点是，由于书写习惯，英文文本的单词之间是用空格隔开的，split=' ' 这个参数可以直接对英文文本进行空格分词。但是对中文不行，因此使用 tokenizer.fit_on_texts(text) 时，text如果是英文文本，可以直接 text = ["Today is raining.", "I feel tired today."] ，但是text是中文文本的话，需要先将中文文本分词再作为输入text： text = ["今天 北京 下 雨 了", "我 今天 加班"]，因此，keras的Tokenizer对于英文文档可以做分词+嵌入 两步，对于中文的话，其实只有嵌入这步。如下：from tf.keras.preprocessing.text import Tokenizerfrom tf.keras.preprocessing.sequence import pad_sequences# 1. 创建分词器 Tokenizer 对象tokenizer = Tokenizer() # 里面的参数可以自己根据实际情况更改# 2. 整理整体语料，中文需空格分词text = ["今天 北京 下 雨 了", "我 今天 加班"]# 3. 将Tokenizer拟合语料，生成字典，形成新的tokenizertokenizer.fit_on_texts(text)# 4. 保存tokenizer，避免重复对同一语料进行拟合import joblibjoblib.dump(tokenizer, save_path)# 5. 整合需要做嵌入的文本，中文需要空格分词new_text = ["今天 回家 吃饭", "我 今天 生病 了"]# 6. 将文本向量化list_tokenized = tokenizer.text_to_sequence(new_text)# 7. 生成训练数据的序列X_train = pad_sequences(list_tokenized, maxlen=200)————————————————版权声明：本文为CSDN博主「BoCong-Deng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/DBC_121/article/details/108038858

写在前面如果觉得写得好，或者有所帮助，记得点个关注和点个赞，不胜感激！我发现最近经常会遇到一些需要通过数学分析去解决的问题，做的时候想着各种方法，然后看到题解，发现可以用数学分析的方式，找到非常快的解决办法，整个人就emmmmm了，所以这里开这篇博文，用来记录自己碰到的可以用数学分析的方式解决的算法问题，不断更新。“树根”相关问题“树根”在维基百科的定义如下：在数学中，数根(又称位数根或数字根Digital root)是自然数的一种性质，换句话说，每个自然数都有一个数根。数根是将一正整数的各个位数相加（即横向相加），若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于十为止，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于10，则7为54817的数根。那么“树根”又有什么用途呢？数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。另外，数根也可以用来判断数字的整除性，如果数根能被3或9整除，则原来的数也能被3或9整除。接下来讨论我们怎么求出树根。我们把 1 到 30 的树根列出来。原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3    1    2可以发现数根 9 个为一组， 1 - 9 循环出现。我们需要做就是把原数映射到树根就可以，循环出现的话，想到的就是取余了。结合这个规律，对于给定的 n 有三种情况。    n 是 0 ，数根就是 0。    n 不是 9 的倍数，数根就是 n 对 9 取余，即 n mod 9。    n 是 9 的倍数，数根就是 9。我们可以把两种情况统一起来，我们将给定的数字减 1，相当于原数整体向左偏移了 1，然后再将得到的数字对 9 取余，最后将得到的结果加 1 即可。原数是 n，树根就可以表示成 (n-1) mod 9 + 1，可以结合下边的过程理解。原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30偏移: 0 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29取余: 0 1 2 3 4 5 6 7 8  0  1  2  3  4  5  6  7  8  0  1  2  3  4  5  6  7  8  0  1  2  数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3    1    2    3    4所以，求一个数的树根，一句代码就可以实现，即(num - 1) % 9 + 1;，这里给出一个题目，一句代码即可。在这里插入图片描述public int addDigits(int num) {    return (num - 1) % 9 + 1;}    1    2    3计算阶乘0的个数这个我之前单独写过一篇文章，这里就不赘述了，地址。四平方和定理四平方和定理，意思是任何正整数都能表示成四个平方数的和。少于四个平方数的，像 12 12 12 这种，可以补一个 0 0 0 也可以看成四个平方数， 12 = 4 + 4 + 4 + 0 12 = 4 + 4 + 4 + 0 12=4+4+4+0。知道了这个定理，对于题目要找的解，其实只可能是 1 , 2 , 3 , 4 1, 2, 3, 4 1,2,3,4 其中某个数。Legendre’s three-square theorem ，这个定理表明，如果正整数 n 被表示为三个平方数的和，那么 n n n 不等于 4 a ∗ ( 8 b + 7 ) 4^a*(8b+7) 4a∗(8b+7)， a a a 和 b b b 都是非负整数。换言之，如果 n = = 4 a ∗ ( 8 b + 7 ) n == 4^a*(8b+7) n==4a∗(8b+7) ，那么他一定不能表示为三个平方数的和，同时也说明不能表示为一个、两个平方数的和，因为如果能表示为两个平方数的和，那么补个 0 0 0，就能凑成三个平方数的和了。一个、两个、三个都排除了，所以如果 n = = 4 a ∗ ( 8 b + 7 ) n == 4^a*(8b+7) n==4a∗(8b+7)，那么 n n n 只能表示成四个平方数的和了。所以代码的话，我们采取排除的方法。    首先考虑答案是不是 1 1 1，也就是判断当前数是不是一个平方数。    然后考虑答案是不是 4 4 4，也就是判断 n 是不是等于 4 a ∗ ( 8 b + 7 ) 4^a*(8b+7) 4a∗(8b+7)。    然后考虑答案是不是 2 2 2，当前数依次减去一个平方数，判断得到的差是不是平方数。    以上情况都排除的话，答案就是 3 3 3。在这里插入图片描述public int numSquares(int n) {    if (isSquare(n)) {        return 1;    }    int temp = n;    while (temp % 4 == 0) {        temp /= 4;    }    if (temp % 8 == 7) {        return 4;    }    for (int i = 1; i * i < n; i++) {        if (isSquare(n - i * i)) {            return 2;        }    }    return 3;}private boolean isSquare(int n) {    int sqrt = (int) Math.sqrt(n);    return sqrt * sqrt == n;}————————————————版权声明：本文为CSDN博主「BoCong-Deng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/DBC_121/article/details/106218081

目录•写在前面•什么是编辑距离？•思路•思路可视化•代码实现•写在前面编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。最简单的方法是检查所有可能的编辑序列，从中找出最短的一条。但这个序列总数可能达到指数级，但完全不需要这么多，因为我们只要找到距离最短的那条而不是所有可能的序列。这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出来的，所以也叫 Levenshtein 距离。总是比较相似的，或多或少我们可以考虑编辑距离。我们在解决这个问题中，使用动态规划的思想进行求解。•什么是编辑距离？这里给一个题目的描述：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作。    插入一个字符    删除一个字符    替换一个字符为了更好的理解，我这里给出两个示例，帮助理解这个概念示例一：    输入: word1 = "horse", word2 = "ros"    输出: 3    解释:    horse -> rorse (将 'h' 替换为 'r')    rorse -> rose (删除 'r')    rose -> ros (删除 'e')示例二：    输入: word1 = "intention", word2 = "execution"    输出: 5    解释:    intention -> inention (删除 't')    inention -> enention (将 'i' 替换为 'e')    enention -> exention (将 'n' 替换为 'x')    exention -> exection (将 'n' 替换为 'c')    exection -> execution (插入 'u')•思路我们的目的是让问题简单化，比如说两个单词 horse 和 ros 计算他们之间的编辑距离 D，容易发现，如果把单词变短会让这个问题变得简单，很自然的想到用 D[n][m] 表示输入单词长度为 n 和 m 的编辑距离。具体来说，D[ i ][ j ] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。更通俗的理解，假设我们可以使用d[ i , j ]个步骤（可以使用一个二维数组保存这个值，使用动态规划的思想），表示将串s[ 1…i ] 转换为串t [ 1…j ]所需要的最少步骤个数，那么，在最基本的情况下，即在 i 等于 0 时，也就是说串 s 为空，那么对应的d[ 0 , j ] 就是 增加 j 个字符，使得 s 转化为 t，在 j 等于 0 时，也就是说串 t 为空，那么对应的 d[ i, 0] 就是 减少 i 个字符，使得 s 转化为 t。更一般的情况，加一点动态规划的想法，我们要想得到将 s[1..i] 经过最少次数的增加，删除，或者替换操作就转变为 t[1..j]，那么我们就必须在之前可以以最少次数的增加，删除，或者替换操作，使得现在串 s 和串 t 只需要再做一次操作或者不做就可以完成 s[1..i] == t[1..j] 的转换。所谓的“之前”分为下面三种情况：    要得到 s[1…i] == t[1…j-1]，需要 k 个操作    要得到 s[1..i-1] == t[1..j]，需要 k 个操作    要得到 s[1…i-1] == t [1…j-1]，需要 k 个操作在上面的这三种情况的基础下，我们需要得到 s[1..i] == t[1..j] ，我们分别给出解决思路，如下    第1种情况，只需要在最后将 t[1…j-1] 加上 s[i] 就完成了匹配，这样总共就需要 k+1 个操作。    第2种情况，只需要在最后将 s[1..i-1] 加上 t[j] 就完成了匹配，所以总共需要 k+1 个操作。    第3种情况，只需要在最后将 s[ i ] 替换为 t[ j ]，使得满足 s[1..i] == t[1..j]，这样总共也需要 k+1 个操作。特别注意：而如果在第3种情况下，s[i]刚好等于t[j]，那我们就可以仅仅使用k个操作就完成这个过程。最后，为了保证得到的操作次数总是最少的，我们可以从上面三种情况中选择消耗最少的一种最为将s[1..i]转换为t[1..j]所需要的最小操作次数。我们把储存k的二维数组命名为 D[ ][ ] ，显而易见，当我们获得 D[i-1][j]，D[i][j-1] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。如果两个子串的最后一个字母相同，即word1[i] = word2[i] 的情况下：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1]-1)如果两个子串的最后一个字母不相同，即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1])•思路可视化在上面的思路描述下，我们大致能够理解了，当然，如果还是有点迷糊的，这里我将思路用表格一步一步的表示出来，帮助理解。首先我们先初始化一个二维数组，如下。“.” 代表空串。第一行和第一列按照个数进行初始化，这一步要想明白，想明白了之后就好理解了。如果两个子串的最后一个字母相同，即word1[i] = word2[i] 的情况下：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1]-1)，图形如下。如果两个子串的最后一个字母不相同，即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1])，图形如下。最后我们会得到如下的结果，二维数组最后的 3 就是我们的答案。•代码实现    public int minDistance(String word1, String word2){        int n = word1.length();        int m = word2.length();             if(n * m == 0)            return n + m;             int[][] d = new int[n + 1][m + 1];        for (int i = 0; i < n + 1; i++){            d[i][0] = i;        }             for (int j = 0; j < m + 1; j++){                d[0][j] = j;        }             for (int i = 1; i < n + 1; i++){            for (int j = 1; j < m + 1; j++){                int left = d[i - 1][j] + 1;                int down = d[i][j - 1] + 1;                int left_down = d[i - 1][j - 1];                if (word1.charAt(i - 1) != word2.charAt(j - 1))                    left_down += 1;                d[i][j] = Math.min(left, Math.min(down, left_down));            }        }        return d[n][m];}————————————————版权声明：本文为CSDN博主「BoCong-Deng」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/DBC_121/article/details/104198838

写在前面的话偶尔出来发个大招谨以此篇献给我最爱的grandpa, 你知道的没有你就没有我。我觉得我对你说我爱你说的太少了。只有你会在我发烧时候每隔5分钟来摸摸我的脑袋。为我跑遍整个昆明城买我最喜欢的食物，为我跑遍整个昆明城帮我办公交卡，在我人生低谷，不吃不喝的时候濒临奔溃的时候一直安安静静的陪我哭，帮我想办法，让我活过来。只有你，会为我剪报纸，帮我搜集高考每一所学校的录取学校，做成美美的小册子。我上班太辛苦了，你总是说宝宝，我们家不缺钱，不用这么拼，外公养你一辈子，你在家给我做做饭就够了，钱够花就行。我初中赖床，不起床复习，你总是把我吼起来，你说你看看你上次年纪第三，这次考第五，都下降了，咱们能严格要求下自己么。我上班起不来，我叫你叫我起床，你说几点，我说8点，你总是说让你没有成就感，哪有人8点还要人叫起床的。我出国交流，回家躺倒床上就睡，你总是提着拖把闯进来，把我拎起来，问我为什么还不复习雅思。为什么不好好准备考试。我每次躺倒床上没几分钟，你就过来闹觉，我每次都是装作听不见。谢谢你在初中的时候一直教我电路图，我们一起做插座，一起动手安装家具，我们一起卖废品，一起收集瓶子，一起卖废报纸，一起去购物，你总是喜欢坐在超市的沙发上享受一会。你喜欢偷怕我和外婆。所以我叫你冠希哥。我总是用脚戳你，你一趟在沙发上。你总是倔强，不许我乱花钱，自己动手做床。我们一起种了树，很多树，家里很美，我们种了很多花。你帮我做镜子，还把我小学二年级的照片黏在后面，我说干嘛要粘这么马肯头的一张，你说，我孙女是全世界最美的。我用你手机照了一张相，你见人就炫耀，你看，我孙女是不是全世界最美的小姑娘，这么标志，简直是遗传外婆的所有优点。哪有小孩子5岁都不断奶，因为都是你惯的，你每天晚上都要给我起来煮奶。我们一起吹泡泡，一起喂鸡，我帮你洗你的臭袜子，你背着我每周二去集市买大白兔，搞的我一口虫牙。你每天吃饭都会出脑筋急转弯给我。你说我们这臭脾气很像，对呀，我不像你像谁，我是你骄傲，这么会这么轻易让人超越。我们一直就是这么霸气侧漏，我们不用逼自己变优秀。你跟我开家长会总是在拉自己的胡子。哈哈，你还从床上睡到掉下来，你真的好笨！我知道的血液就是你血脉的延续，所以我做每一件事都是你的标识。我会把我做的每一件事情都做到极致，跟自己约定，等明年的时候，我会在全球最好的会议上亲自告诉最顶尖的科研人员，我会做最好的研究，用最踏实的态度活好每一天，那是因为你。你说如果你接受和我一样的教育，你会成为比我厉害一百倍的科学家，我说，你会。我跟你开玩笑说，外公，你这么厉害，你一定能比屠呦呦厉害。以后我们家都靠你养了，你也去发明个什么青蒿素，完全不是问题。外公，我要让全世界看见，你的血液里面最闪光的所有宝藏。I promise。在我心跳停止的之前，我会努力做到让全世界为你致敬，把你所有美好的品质发挥到极致。你说的，我是你的骄傲，我会一直是你最好的骄傲。always and forever, we are family, I love you, always and forever.我说你是全世界最聪明的老爷爷，你这么努力，你这么能干，你是我的骄傲，我会加油。你要好好照顾自己，I miss you.感觉自己真的很任性，一次一次说我是为自己的梦想，每次都不顾一切不考虑你的年纪，让我比同龄人慢了很多，你总是这么倔，你就为给我省钱不好好照顾自己。我自己也不好，没有固执的带你去看医生，没有固执给你买我所有想买给你的东西。你总是嫌我品味差，给你买的鞋子难看。给你买的皮鞋你一次都没有穿过。对不起，对不起，对不起。我这么不好，我这么不好，固执，倔强，蛮横，执拗，你还是这么一直一直很好很好的给我全世界最好的爱。感觉自己欠了外公10年的时光。我会努力，明年我就在家里最好的地方买一幢别墅给外婆，不用让你再去爬楼梯，我会给你买最好的地方，让你可以每天可以看到八百里滇池的日出日落，每天都可以吹吹海风。我们一直是家人对不对，I love you.好像图论和树在计算机的数据结构中，都有种魔咒，好难，代码也不好写。我觉得难的是心态，要是预先给我们自己定了一个这个东西很难的调调，然后我们永远做不好这事。只要用心，没有什么是我们不可以实现的，我们做的每一件事就是为了创造奇迹而存在的。这是我外公教我的，他每天都是这么实践的。图的定义图（graph）G=（V，E）由顶点（vertex）的集V和边（Edge）的集E组成。顶点代表了对象，在示意图中我们使用点或圆来表示它；边代表了两个对象的连接关系，在示意图中我们使用连接两顶点的线段来表示。有时也把边称作弧（arc），如果点对（v，w）是有序的，那么图就叫做有向的图（有向图）。如果点对(v,w)是无序的，那么图就叫做无向的图（无向图）。简单的讲，边没有指向性的图叫做无向图，边具有指向性的图叫做有向图。顶点v和w邻接（adjacent）当且仅当（v，w）属于E。我们可以给边赋予各式的属性，比如权值（cost）。权值可以表示从一个顶点到另一个顶点的距离，也可以表示一个顶点到另一个顶点说话费的代价（比如时间、金钱等）。一个边上带权值的图称为网络（network）。如果无向图中从每一个顶点到其他每个顶点都存在一条路径，则称该无向图是连通的（connected）。具有这样性质的有向图称为是强连通的的（strongly connected）。如果有向图不是强连通的，但它的基础图（underlying graph）（也就是其弧上去掉方向说形成的图）是连通的，那么称该有向图是弱连通的（weakly connected）。完全图（complete graph）是其每一对顶点间都存在一条边的图。这里写图片描述度（degree）指的是顶点v的边的条数。这里写图片描述如果具有n个顶点，e条边的图G的顶点i的度为di，则G的边数为：$ e =\frac { \sum_{0}^{n-1} d_i} {2} $这个是针对无向图来说的。我们以上面这个图来详细的说明一下整个问题：这里写图片描述我们给每个节点编号根据每个节点对应的度来求这个图的边：这里写图片描述刚好是7。这个高中的时候学欧拉公式应该很熟练了（新教材被删减了，我又暴露年龄了），因为针对每一条边，它的每天边被每个顶点重复利用了一次。对于边1-2和变2-1其实是相同的事情。所以在这里我们是需要除以二的。但是对于有向图，我们只需要计算每个顶点的出度或者是入度就可以知道这个图总共是有多少条边。这里写图片描述这《数据结构与算法C语言版》的这本书中这个比较经典的图形，我们计算这个图形的边，同样可以先把它看成是无向图。按照上面的公式来计算：这里写图片描述又或者你可以根据这个图的出度或者是入度中的任意一个来计算，下面我们选择的是出度来计算这个有向图的边。这里写图片描述图的存储表示方式图主要有3种常用的存储表示方式：邻接矩阵（adjacency matrices），邻接表（adjacency lists），邻接多重表（adjacency multilists）##邻接矩阵邻接矩阵使用|V|∗|V|的二维数组来表示图。g[i][j]表示的是顶点i和顶点j的关系。1）因为在无向图中，我们只需要知道顶点i和顶点j是否是相连的，因此我们只需要将g[i][j]和g[j][j]设置为1或是0表示相连或不相连即可。如下图所示。这里写图片描述2）而在有向图中，我们只需要知道是否有从顶点i到顶点j的边，因此如果顶点i有一条指向顶点j的边，那么g[i][j]就设为1，否则设为0。有向图与无向图不同，并不需要满足g[i][j]=g[j][i]。这里写图片描述3）在带权值的图中，g[i][j]表示的是顶点i到顶点j的边的权值。由于在边不存在的情况下，如果将g[i][j]设为0，就无法和权值为0的情况区分开来，因此选取适当的较大的常数INF（只要能和普通的权值区别开来就可以了），然后令g[i][j]=INF就好了。当然，在无向图中还是要保持g[i][j]=g[j][i]。在一条边上有多种不带权值的情况下，定义多个同样的|V|∗|V|数组，或者是使用结构体或类作为数组的元素，就可以和原来一样对图进行处理了。这里写图片描述使用这种存储方式，可以很方便地判断任意两个顶点之间是否有边以及确定顶点的度，这也是这种表示法最大的优势。任意一个顶点i的度等于其邻接矩阵中顶点i所对应的行中的数字之和：$ \sum_{j=0}^{n-1} g[i][j] $在这种表示法中扫描所有边至少需要O(n2)时间，因为必须检查矩阵中的n2−n个元素才能确定图中边的条数（邻接矩阵对角线上的n个元素都是0，因此不用检查。又因为无向图的邻接矩阵是对称的，实际只需检查邻接矩阵的一半元素）。通常把边很少的图成为稀疏图（sparse graphs）图的同构我们先看一个简单的例子：图一对于上面这个简单图，我们用邻接矩阵来表示这个图，得到的形式如下所示：这里写图片描述        首先，我们需要明确一点，图的邻接矩阵是不唯一，取决于顶点的排列顺序.        无向图的邻接矩阵是对称的定义同构的图：本质上相同的图，表示了类似的集合和关系这里写图片描述下面两个图是同构的：这里写图片描述函数f满足f(u1)=v1,f(u2)=v4 ,f(u3)=v3 ,f(u4)=v2 ,它是V和W之间的一一对应。为了看出这个对应保持相邻关系，注意G里相邻的顶点是u1和u2， u1和u3，u2和u4，以及u3和u4，由f(u1)=v1和f(u2)= v4 ，f(u1)=v1 和f(u3)= v3 ，f(u2)= v4和f(u4)= v2 ，以及f(u3)= v3和f(u4)= v2所组成的每一对顶点都是在H里相邻的。图的同构是一个一一对应关系，但是子图同构在严格的意义上讲不能叫做映射。why?我们先说明完图的同构问题.    同构的充分条件，可用于判定同构    给出一个顶点的一一对应，按相应的顺序求出邻接矩阵    邻接矩阵相同 ==》那么图是同构    同构的必要条件，可用于判定不同构    （1）顶点数相同    （2）边数相同    （3）顶点度相同    （4）同度顶点构成的子图都同构这里写图片描述G和H都具有5个顶点和6条边。不过，H有1度顶点e而G没有1度顶点。我们可以看出在H这个图中节点e只有一个度，在图G中我们根本找不到节点的度是1的。所以G与H是不同构的。重要的事情多说几遍，我们判断两个图是不是同构的，可以根据节点的度来判断 .这里写图片描述图G和H都具有8个顶点和10条边。它们都具有4个2度顶点和4个3度顶点。因为这些不变量都相同，所以可能想到它们是同构的.然而G和H不是同构的。为了看明白这一点，注意到因为在G里deg(a)=2，所以a必然对应于H里的t，u，x或y，这是因为这些顶点是H里的2度顶点。不过， H里的这4个顶点中每一个都与H里另一个2度顶点相邻，但是在H里a却不是这样的。图同构的，那么度相同的节点构成的子图也是同构的。我们看一下这两个图中度为三的节点构成的子图是什么样子的：如下图所示：这里写图片描述根据上图所示，这两个图明显是不同构。————————————————版权声明：本文为CSDN博主「君的名字」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/chichoxian/article/details/52674252

写在前面的话k-means 算法是一个聚类的算法 也就是clustering 算法。是属于无监督学习算法，也是就样本没有label(标签)的算分，然后根据某种规则进行“分割”， 把相同的或者相近的objects 物体放在一起。在这里K就是我们想要分割的的聚类的个数。当然了，很多资料都会说这个算法吧，毕竟简单粗暴可依赖算法描述首先我们有以下的几个点    A1    (2,10)A2    (2,5)A3    (8,4)A4    (5,8)A5    (7,5)A6    (6,4)A7    (1,2)A8    (4,9)这个算法不能帮助我们自动分类，所以我们需要指定我们需要的个数。其实在很多实际应用当中，我们很难知道我们的数据是什么分布的，应该分成几类比较好。这也是k-means自身的一个缺陷，所以不能帮助我们自动的聚类。注：如果我在本文中说了分类，其实是分割的意思，我想表达的意思是聚类。中文和英文切换，在意思上表达真的有点差距。现在假设我们需要把上面的数据点分成三类。我们需要遵循下面的几个步骤    选取三个类的初始中心    计算剩余点到这三个中心的距离    将距离中心点距离最短的点归为一类    依次划分好所有的数据点    重新计算中心    重复2-5 个步骤，直到中心点不会在变化为止现在看完步骤，其实可能会有一些疑问：1. 怎么选择我们的初始中心点？2. 怎么计算点之间的距离呢。选择中心点中心点怎么选择，一般情况下我们是随机的从我们的数据集中选择的。当然还会有其他的方法，我们在之后的文章中可能会讨论。如果我还有时间去写的话，一般我会有时间写的。甚至这个中心点的选择可以是完全随机的，甚至都不需要从我们的数据集中选取，在这里，我们的数据集是一个二维的，所以我们可以选择在XY坐标上的任意三个点，随你高兴都是可以的注意：中心点的选取不同，最后的聚类结果可能大不相同在这里我们假设我们的三个初始点是A，在这里我们选取的初始点是A1，A4，A7在这里我们定义两个点之间的距离用曼哈顿聚类距离，也可以叫做城市街区距离。在这里插入图片描述在这里我们是二维坐标，所以我们可以按照下面这个公式：在这里插入图片描述下面是一个例子：在这里插入图片描述计算的一般过程：我们先看第一轮：在这里插入图片描述选取距离最近的归为一类这个时候我们得到的聚类的结果：在这里插入图片描述得到了第一轮的结果我们需要重新的计算每个聚类的中心cluster1对于第一个聚类只有一个点所以它的聚类的中心就是它自己。Cluster2X:(8+5+7+6+4)/5 = 6Y:(4+8+5+4+9)/5 = 6这个时候它的中心就变成了（6,6）Cluster3：X：（2+1）/2 = 1.5Y：（5+2）/2 = 3.5这个时候在进行第二轮迭代：在这里插入图片描述这个时候再次计算中心：在这里插入图片描述这个时候用我们的新的中心再来计算一遍：在这里插入图片描述这个时候我们在重新根据新的聚类重新计算我们的中心：在这里插入图片描述得到新的点之后我们在重新计算新的聚类在这里插入图片描述这个时候发现和上一次的结果是一致的，这个时候我们就可以停止我们的算法了。下面我们来看一下这个迭代过程的图谱。这个是我们的的初始过程在这里插入图片描述之后是我们选取中心点：在这里插入图片描述依次迭代的过程：在这里插入图片描述在这里插入图片描述————————————————版权声明：本文为CSDN博主「君的名字」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/chichoxian/article/details/84075128