1 查找问题
1 该类问题的第一个子问题问题分析1.1 该类问题的第一个子问题——第一种方法问题分析策略选择算法设计算法分析算法实现1.2 该类问题的第一个子问题——第二中方法策略选择算法设计算法分析算法实现该类问题的第三个子问题——第一种方法问题分析算法设计算法分析算法实现
1.1 重复问题
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...
5.3 最长公共子序列问题
最长公共子序列问题描述求数组A和B的最长公共子序列 问题分析 子序列(subsequence)： 一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。例如序列<A,B,C,B,D,A,B>的子序列有：<A,B>、<B,C,A>、<A,B,C,D,A>等。 公共子序列(common subsequence)： 给定序列X和Y，序列Z是X的子序列，也是Y的子序列，则Z是X和Y的公共子序列。例如X=[A,B,C,B,D,A,B]，Y=[B,D,C,A,B,A[，那么序列Z=[B,C,A]为X和Y的公共子序列，其长度为3。但Z不是X和Y的最长公共子序列，而序列[B,C,B,A]和[B,D,A,B]也均为X和Y的最长公共子序列，长度为4，而X和Y不存在长度大于等于5的公共子序列。对于序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[]。 最长公共子序列：给定序列X和Y，从它们的所有公共子序列中选出长度最长的那一个或几个。 子串： 将一个序列从最前或最后或同时删掉...
