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; ...

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(nu...

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>dat...

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.外部有未入栈元素。出栈条件：等于弹出序列。 返回出口：全部元...

C语言实现包含min函数的栈操作 思路：简单的栈很容易实现，重点是如何维护min最小值，最简单的想法，每次计算栈元素最小值存放到一个地方，显然时间复杂度成本过高。使用额外的栈来实现，比如说我依次入栈 5 7 8 6 3 2 4，那么设置记录最小值的栈存放 5 3 2。每次入栈时和最小值栈顶比较，判断是否需要记录。出栈同样比较是否需要弹出。 重点：双栈实现 辅助栈只记录降序元素 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param value int整型 * @return 无 * * C语言声明定义全局变量请加上stati...

C语言两个栈实现队列 思路：先考虑栈结构，类似一个水桶，先进的元素再最下面；如果说像队列一样，先进的元素最先出去，也就是相当于将栈翻一翻，将水桶的水倒进另一个水桶。因此考虑使用栈，以及倒置栈 入栈操作：正常入栈1，同时将栈1倒置，重置栈2； 出栈操作：从栈2中弹出一个元素，同时使用栈2倒置，重置栈1 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param node int整型 * @return 无 * * C语言声明定义全局变量请加上static，防止重复定义 */ static int stack1[1000]; st...

C语言实现序列化二叉树 二叉树---->字符串 ·思路：采用层序遍历的方案，使用队列，遍历每一个节点的左右孩子，左右孩子为空则字符为‘#’,否则保存节点值，并且使用队列保存节点。 ·重点：字符串末尾添加结束符 字符串--->二叉树 ·思路：使用两个指针进行遍历字符串，前一个指针指向节点，后一个指针分别指向左右孩子，每个循环，前一个指针一步，后一个指针两步。依次对前一个指针的所有孩子操作。这里我使用了一个节点数组，先初始化节点数组，然后对这个节点数组进行操作 ·循环出口：后一个指针走完，说明创建结束 重点：迷惑的点在于节点数组，使用struct TreeNode *nod...