刷题笔记

二分法 二分法代码1234567891011121314151617181920212223242526272829303132333435363738// 二分查找（折半查找）：对于已排序，若无序，需要先排序// 非递归int BinarySearch(vector<int> v, int value , int low, int high) { if (v.size() <= 0) { return -1; } while (low <= high) { int mid = low + (high - low) / 2; if (v[mid] == value) { return mid; } else if (v[mid] > value) { high = mid - 1; } else { low = mid + 1; } } return -1;}// 递归int BinarySearch2(ve ...

分治算法自刷 分治算法的核心思想分治算法的核心思想就是四个字,分而治之,也就是将原来的问题划分成n个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解.  看起来有点像递归,不过要知道分治算法是一种处理问题的思想,递归是一种编程技巧.看起来像是因为分治算法一般都比较适合用递归去实现 分治算法递归实现步骤1. 分解：​ 将原问题分解为一系列的子问题 2. 解决：递归地求解各个子问题，若子问题足够小，则直接求解。 3. 合并：将子问题的结果合并为原问题 53.最大子序和 53.最大子序和给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 123输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。`进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 解题思路1. Post not found: 力扣自刷/动态规划2. Post not found: 力扣自刷/贪心算法3. 分治 ...

副本文件回溯17. 电话号码的字母组合 22. 括号生成 电话号码的字母组合17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例:12输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].说明:尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 12345678910111213141516171819202122232425262728293031public: map<char, string> M = { {'2',"abc"},{'3 ...

题目列表最大上升子序和 最大子序和 最长回文子串 不同路径 最长回文子序列 正则表达式匹配 最大上升子序列和题目描述一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …,aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。 输入描述:12输入包含多组测试数据。每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到100 ...