Estom的博客

1 该类问题的第一个子问题问题分析1.1 该类问题的第一个子问题——第一种方法问题分析策略选择算法设计算法分析算法实现1.2 该类问题的第一个子问题——第二中方法策略选择算法设计算法分析算法实现该类问题的第三个子问题——第一种方法问题分析算法设计算法分析算法实现

1 重复数字问题问题描述 找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 问题链接 问题分析 重复问题的解决大部分都可以使用哈希表。然后根据元素提供的额外属性采用哈希表的变种。 如本题中提供了额外的限制——0-n-1范围内的数字。那么除了用提供的unordered_set。也可以使用数组作为哈希表，数组的下标作为键，数组的值为值。于是很容易想到第二种方法的改进，即第三种方法。 问题分类 线性数据结构 查找问题 枚举法。 1.1 重复数字问题——排序策略选择算法设计 使用快速排序 寻找第一组相邻的重复数字。 正确性证明算法分析 时间复杂度O(nlogn) 空间复杂度O(logn) 算法实现12345678910// 排序方法。排序后出现连续重复数字。int findRepeatNumber1(vector<int>& nums) { sort(nums.begin(),nums...

1 二维数组的查找问题描述 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 链接 问题分析 与一维查找类似。找到中间数字，每次移动可以舍弃掉一半的数字。由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。 从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。 从二维数组的左下角开始查找。具有完全一致的效果。 问题分类 线性数据结构 枚举法 查找问题 策略选择算法设计 若数组为空，返回 false 初始化行下标为 0，列下标为二维数组的列数减 1 重复下列步骤，直到行下标或列下标超出边界 获得当前下标位置的元素 num 如果 num 和 target 相等，返回 true 如果 num 大于 target，列下标减 1 如果 num 小于 target，行下标加 1 循环体执行...

1 把数组排成最小数问题描述 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 链接 问题分析问题分类 排序 算法设计 算法原理：此题求拼接起来的最小数字，本质上是一个排序问题。设数组nums 中任意两数字的字符串为 x 和 y ，则规定 排序判断规则 为： 若拼接字符串 x+y>y+x ，则 x “大于” y ； 反之，若 x+y<y+x ，则 x “小于” y ； 算法流程 初始化： 字符串列表 strsstrs ，保存各数字的字符串格式； 列表排序： 应用以上 “排序判断规则” ，对 strsstrs 执行排序； 返回值： 拼接 strsstrs 中的所有字符串，并返回。 算法分析 时间复杂度O(NlogN) ： N 为最终返回值的字符数量（ strs列表的长度 N≤N ）；使用快排或内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N^2) 空间...

正则表达式匹配问题1 正则表达式匹配问题描述 请实现一个函数用来匹配包含’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。 问题分析 可以使用动态规划。将字符串的规模增长的方向，作为动态变化的方向。状态变量表示当前的正则表达式，能够与之匹配。当规模发生变化时，保证字符串-1和正则表达式-1能够匹配。其实在这里感觉规模增长的方向，确实是有两个。但是状态变量的设置比较精巧。 问题分类 字符串匹配问题 动态规划 递归 1.1 正则表达式匹配——动态规划选择策略 动态规划 算法设计 设s的长度为n ，pp 的长度为 m ；将 s 的第 i 个字符记为 s_i，p 的第 j个字符记为 p_j ，将 s 的前 i 个字符组成的子字符串记为s[:i] , 同理将 p 的前 j 个字符组成的子字符串记为 p[:j]p[:j] 。 因此，本题可转化为求s[:n] 是否能和p[:m...

表示数值的字符串1 表示数值的字符串问题描述 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。 链接 问题分析 这题一看，明显就是有限状态自动机。词法分析过程中用来判断关键字、数值的。属于暴力破解。使用优先状态自动机。确定分类讨论的情况。找到符合规则的所有的路。 另外提供了另外一种暴力破解的思路。通过讨论违反规则的情况。找到违反规则的所有的路。 提供了两种截然不同的分类讨论的思路。在某些情况下，第二种思路反而会简单很多。 在 C++ 文档 中，描述了一个合法的数值字符串应当具有的格式。具体而言，它包含以下部分： 符号位，即 +、− 两种符号 整数部分，即由若干字符 0-9组成的字符串 小数点 小数部分，其构成与整数部分相同 指数部分，其中包含开头的字符 e（大写小写均可）、可选的符号位，和整数部分 问题分类 枚举法 正向分类讨论和反向分类讨论 1.1 表示...