题目已知有两个字符串s1,s2，求其最长公共子串。思路定义dp[i][j]表示s1[0,i],s2[0,j]最长公共子串的长度，则dp[i][j]=dp[i-1][j-1]+1,s1[i]==s2[j],dp[i][j]=0,s1[i]!=s2[j]。dps1.length-1就是答案的最长长度代码#include <vector> using namespace std; class CommonString { public: string longestCommonString(string s1, string s2) { int n = s1.length(); int m = s2.length(); vector<vector<int>> dp(n,vector<int>(m)); int location = 0; int longest = 0; for(int i = 0;i < n;i++) {

题目：有一个金字塔，想从金字塔底走到塔顶。每一条路所花的时间都不一样长。请找出登上金字塔最快的路(所费时间为路径上数字的总和)。每个向上的路径只有左上和右上的两条路。输入:[[45],[20,33],[34,18,30],[14,45,09,11]]，输出:92思路：arr表示输入的二维数组，定义dp[i][j]表示从塔底走到位置(i,j)花费的最少时间。则dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+arr[i][j],边界条件dp[arr.size()-1][k] = arr[arr.size()-1][k],0<=k<=arr.size()-1 计算顺序为从二维数组的底部向上。代码：#include <vector> using namespace std; class MinPath { public: int minPathPyramid(vector<vector<int>>& pyramid) { for(int i = pyramid.size()-2;i &g

题目一个正整数数组 arr ，表示不同面额的硬币；一个整数 n ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。每种硬币的数量是无限的。思路使用动态规划，动态规划的精髓是用小问题的解合并为大问题的解。这道题的大问题是什么？小问题是什么？原问题是给定的金额换成零钱。小问题肯定是比给定金额小的金额。那是多少呢?假如零钱种类为{1,2,5}，给定的金额为10，答案为f(10)。现在换了一个5元的。还剩5元需要换。有这个等式：f(10)=f(5)+1。很显然，使用所有的面额换一次，剩下还没换的金额就是小问题，取所有小问题答案中的最小值+1,就是最终答案即 f(10) = min{f(10-5),f(10-1),f(10-2)} + 1给定金额为n,零钱面额数组为arr定义 f(n) 为最少的金币数量。则状态转移方程为：f(n) = min(f(n-arr[i]))+1, 0<=i<=arr.size()-1。边界条件：f(0)=0，f(arr[i]) = 1,0<=i<=arr.size()-1代码#i

题目：平面上有一些点，每个点的坐标可用(x,y)表示。请找出所有的极点。对于平面上的两个点:A(x1,y1) 和 B(x2,y2)，如果x1>x2,且y1>y2,则点A支配点B。极点是不被其他点支配的点。思路：暴力法的时间复杂度是O(n2)。本题利用分治法可以使时间复杂度降到NlogN。具体步骤：首先对数组排序，使所有点在x轴上从小到大排列把数组分为左右两部分，分别求极点对2步骤的两个结果合并，不过要先过滤左边部分有可能被右边极点支配的点。代码：#include <vector> using namespace std; class MaximumPoint { static bool compareTwoPoint(vector<int> point1, vector<int> point2) { return point1[0] < point2[0]; } public: vector<vector<int>> findMaximumPoint(vector<

题目：给定一个长度为n的数组arr，请输出第k小值,1<=k<=n,当k = 1或n时，就是找最小值或最大值。思路：把数组划分为n/5组。每组5个元素。分别找到每组的中间值，然后在n/5个中间值中找中间值mm。用这个中间值mm划分数组，如果mm所在位置等于k,则找到答案。如果，mm所在位置小于k,继续在右半部分找。如果mm所在位置大于k,继续在左半部分找。重复这个过程。直到找到答案。中间给5个元素排序，用的是快速排序代码，给5个元素排序的时间复杂度为O(1)代码：class kSmallNumber { public: int kSmallNumb(vector<int>& arr,int k,int left, int right) { int n = right - left + 1; if (n <= 5) { quickSort(arr,left,right); return arr[left + k-1]; } vect