C语言求解买卖股票的最好时机（一）  解题思路： 使用贪心算法，不妨设对于 8 9 4 5 2 7 1 ，遍历的过程中维护两个变量：一个是最低的购入价格，另一个是当前出售的利润最大值。假设第n天出售了股票，那么一定是在1~n-1之间的最低值买入的。dp[i] = a[i] - min_buy。因此使用一个变量不断记录最低的购入价格。   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型一维数组 * @param pricesLen int prices数组长度 * @return int整型 * * C语言声明定义...

C语言解礼物的最大值  解题思路：一个经典的动态规划问题，求方格路径的最大值，例如求dp[i][j]，表示位置i,j的最大值，由于路径只能向右或者向下，也就是i,j位置只能来源于(i-1,j)或者是(i,j-1)，求其最大值即可。dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]。 初始值：初始化第一行以及第一列，路径是确定的。   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param grid int整型二维数组 * @param gridRowLen int grid数组行数 * @param gridC...

C语言求解矩形覆盖  解题思路：对于2*n的一个矩形 去考虑一下右侧的组成形状 有两种可能：一种是竖着的2*1矩形，另一种是两个横着的2*1矩形。因此dp[n]=dp[n-1]+dp[n-2]  /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param number int整型 * @return int整型 * * C语言声明定义全局变量请加上static，防止重复定义 */ int rectCover(int number ) { int dp[40]; dp[0]=0; dp[1]=1; dp[2]=2; if(number<=...

C语言 把数字翻译成字符串 1. 解题思路 动态规划问题，对于一串字符 1223424220238012，不妨设求第n个字符的可能情况。那么首先需要考虑的是这个字符nums[n]，有两种大的情况，1.能否和前一个字符组成10~26之间的数，自身能否独立成一个新的数。 case1: 自身为0，只能依附于前一个字符，此时需要判断前一个字符是否等于 1或2 ，只有这样才能组成10 或者20 ，此时dp[n]=dp[n-2] case2：自身不为0 前一个字符为0 ,此时只能自己独立成一个数字 dp[n]=dp[n-1] case2: 自身不为0 前一个字符不为0，和前一个数字组合起来位于 10~26...

C语言青蛙跳台阶扩展  思路: 考虑跳n级台阶，可以从(n-1)跳一层、(n-2)跳两层、(n-3)跳3层、、、(n-n)跳n层上来，所以dp[n]=dp[n-1]+dp[n-2]+...+dp[0] 同样的 dp[n+1]=dp[n]+dp[n-1]+dp[n-2]+...+dp[0] = 2*dp[n]，实际上是求2^(n-1)的问题，直接使用移位运算 2<<(number-1)   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param number int整型 * @return int整型 * * C语言声明定义全局变量请加...

C语言斐波那契数列  解题思路：和上一题的青蛙跳台阶一样 使用动态规划解决，但是时间复杂度是O(n)，要是想将时间复杂度降到O(logn)，emmmmm   * * @param n int整型 * @return int整型 * * C语言声明定义全局变量请加上static，防止重复定义 */ int Fibonacci(int n ) { // write code here if(n==1) return 1; if(n==2) return 1; int temp1=1,temp2=1,temp=0; for(int i=2;i<n;i++){ temp=temp1; temp1...

C语言求解青蛙跳台阶问题  解题思路：很基本的动态规划问题。假设青蛙求跳n级台阶，那么青蛙的上一级台阶只能是(n-1)级台阶，或者是(n-2)级台阶，所有dp[n]=dp[n-1]+dp[n-2] 使用两个变量保存一下两个前驱dp即可。   * * @param number int整型 * @return int整型 * * C语言声明定义全局变量请加上static，防止重复定义 */ int jumpFloor(int number ) { // write code here if(number==1) return 1; if(number==2) return 2; int temp...

C语言求解连续子数组的最大和（二）   解题思路： 由于已经使用动态规划解决了连续子数组的最大和（一）,那么思路相同，只不过这次的输出是要求输出这个连续子数组，那么可以添加一个变量，用于记录返回数组的末尾元素位置，同时还需要一个变量记录一下连续的数组长度。   遇到的坑： 2.1 由于遇到多个最优解的字符串 返回最长的那个 这里的最长子数组有两种可能，一种是dp[i-1]=0，那么之后的序列可以包含dp[i-1]也可以从dp[i]开始，比如：1 2 -3 4 -1 1 -3 2，对应的dp数组为 1 3 0 4 3 4 1 3，可以看到最大值为4，并且有两个，最大数组分别是：[1,2,-3,4...

C语言求解连续子数组的最大和   解题思路：动态规划（dp）问题，对于一个连续的数组：1 -2 3 10 -4 7 2 -5，当计算第i个dp时，此时需要根据dp[i-1]来推算出dp[i]的值，此时dp[i]相比于dp[i-1]的变数 只有a[i]这个值，接下来应该判断a[i]是否有可能添加到dp[i-1]的序列中呢？如果说添加了这个a[i]比dp[i-1]+a[i]>a[i]，那么dp[i]是应该包含a[i]的，否则dp[i-1]+a[i]<a[i] 那个dp[i]=a[i];   当遍历到第i个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置i结尾的最大连续...

C语言求解数字序列第n位数字   思路：对于一个数字序列0123456789 1011121314... 做出以下的分析:  1位数区间 [0~9] 共10位 2位数区间 [10~99] 共90位 占据字符串90*2 = 180位 3位数区间 [100~999] 共900位 占据字符串 900*3 = 2700位。 ... n位数区间 [10^n,10^(n+1)-1] 共 9*10^(n-1) 位 占据字符串 9*10^(n-1) *n位    对于数字n，第一步先确定区间范围，比如n=1000，首先1000>区间1 那么减去区间1的占位 剩余990 继续判断是否位于区间二，区间二总计...

C语言实现字符串的全排列  解题思路：还是以具体例子思考：从最简单的出发：一个字符：a，只有一种排列方式；两个字符：ab，排列方式有 ab，ba；三个字符，cab，由于 ab有两种排列方式 c这个字符可以与a b这两个字符任意调换位置。因此有 cab acb bac cba bca abc；以此类推，假设一个较长的字符串：abcdabc，那么可以考虑字符 a + bcdabc之间的组合。只需要确定了bcdabc的全排列后，那么替换a到这些位置即可，也就是a bcdabc的全排列就简化成了 bcdabc的全排列，以此类推，递归解决所有问题。 重点：如何去除全排列中的重复序列呢？比如说 aabb，...

C语言求数字在升序数组中出现的次数  思路：思路简单 时间复杂度要求log2n，使用二分查找法找到数字k的位置 然后从这个位置左右遍历计算总数即可。   * * @param data int整型一维数组 * @param dataLen int data数组长度 * @param k int整型 * @return int整型 * * C语言声明定义全局变量请加上static，防止重复定义 */ int GetNumberOfK(int* data, int dataLen, int k ) { // write code here if(k>data[dataLen-1]||k&lt...

C语言求解滑动窗口最大值  思路：单调队列：谈一下个人对单调队列的理解。比如说有10个元素，窗口宽度为4，在遍历这10个元素的时候，首先队列是空的，先将第一个元素放入队列，然后当遍历到第二个元素时，将第二个元素与队列里面的比较，如果第二个元素比第一个元素大，那么由于我是求一个滑动的连续的元素最大值，所以之后第一个元素不可能成为最大值，因为元素2存活周期（滑动窗口的宽度）长，并且比元素1大。因此我只需要维护一个单调递减得到队列即可。比如说我已经遍历到了第6个元素，队列中存放的是 2 3 5元素。而 2 > 3 > 6 > 5，这时候5元素就应该被淘汰，而6元素存进去。同时还需要...

C语言实现栈的压入弹出序列比较  思路：以压入顺序： 1 2 3 4 5，弹出顺序 4 5 3 1 2为列，外层循环遍历弹出序列 4 5 3 1 2，来判断这些元素是否在栈顶。首先对于弹出序列4这个元素，由于一开始是空栈，肯定要不断地入栈，直到栈顶元素为4。然后再将栈顶元素pop出。这时候栈里的元素：1 2 3，未入栈元素 5；弹出序列：5 3 1 2；遍历弹出序列的下一个5，和栈顶元素不相同，继续入栈栈外元素，直到全部入栈或者栈顶元素相同。 重点：入栈的判断条件：1.空栈（一定要判断空栈，此时入栈）2.栈顶元素和弹出序列不相同 3.外部有未入栈元素。出栈条件：等于弹出序列。 返回出口：全部元...