给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof 方法1：自己想的笨方法：空间换时间 /* 思路：建立两个数组：vec1用于存储已成功翻译的字符串的最后一个字符,vec2用于临时做各种处理。 扫描输入数字,进入vec2中，从vec1选出每个数字与输入数字组合，若在1...

题目见书上暴力法可解，但超时，所以用动态规划。 /* 思路：动态规划。 f(i)表示以第i位元素结尾的不包含重复字符的子字符串的最大长度。 1.若第i个字符之前没有出现过，则f(i)=f(i-1)+1; 2.若第i个字符之前出现过，分情况讨论。令第i个字符与之前出现过的同样的字符的距离为d. 2.1 若d<=f(i-1)，表示重复字符的前一个出现在了f(i-1)所代表的的字串中，所以f(i)=d。这也意味着第i个字符出现两次所夹的子字符串中再没有其他重复的字符。 2.2 若d>f(i-1)，表示重复字符的前一个出现在了f(i-1)所代表的的字串以外，不影响现有不重复...

题目如书上动态规划问题。 /* 思路：跟迷宫类似，按照给定方向遍历，给出最后的最大值。 1.建立方向数组 2.建立礼物最大值矩阵，与原始输入矩阵维度一样，每个点存储着从起点到该点得到的礼物的最大值。 */ int presentValue(vector<vector<int> >&present, int m, int n) { if (present.size() <= 0 || m <= 0 || n <= 0) return 0; vector<vector<int> >mostVa...

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。 这个题的难点与创新点在于构造出了我们需要的比较大小的方法，具体看代码中。要注意的几点： cmp函数要定义成static成员函数，不然会报错。 比较大小的方法和string类型拼接的方法 程序开始之前判断输入是否为空，若为空返回空的string代码： class Solution { public: /* 定义大小规则：若两个数m和n,组合出来的mn和nm。若mn小于nm，则应输出mn，此时定义m<...

剑指offer p225 思路：分析规律。 当数字位数为1时，表示的范围从0-9，总数为10，共10个数字； 当数字位数为2时，表示的范围从10-99，总数为90，共2x90=180个数字； 当数字位数为3时，表示的范围从100-999，总数为900，共3x900=2700个数字； ...... 举例，若Index=1001， 1001>10，跳过一位数字的10个数，1001-10=991； 991>180,跳过两位数字的180个数，991-180=811； 811<2700,所以第811位是某个三位数中的一位。由于811=270*3+1，这意味着第811位是从100开始的第...

求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。 参考思路：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/javadi-gui-by-xujunyi/ 解题思路 f(n))函数的意思是1～n这n个整数的十进制表示中1出现的次数，将n拆分为两部分，最高一位的数字high和其他位的数字last，分别判断情况后将结果相加，看例子更加简单。 1.例子如n=1234，high=1, pow=1000, last=234可以将数字范围分成两部分1-999和10...

{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1) 动态规划。时间复杂度：O(n)，空间复杂度：O(n) 若数组长度为1，直接返回； 若数组长度大于1，则根据公式算出数组每个位置的最大连续子序列的和。i=0,maxSum[0]=array[0]=6;i=1,maxSum[1]=max(array[1],array[1]+maxSum[0])=max(-3,-3+6)=3;i=2,maxSum[2]=max(array[2],array[2]+maxSum[1])...

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 利用大顶堆小顶堆的思想（具体参考书） class Solution { public: vector<int> maxHeap;//最大堆，存储的是左边部分值，总体小于右边部分，最大值位于堆顶 vector<int> minHeap;//最小堆，存储的是右边部分值，总体大于右...

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。 方法1：时间复杂度O(N),会改变原数组 思路：将原数组排序，直接返回前k个最小值即可 class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> output; if (input.empty()||k>input.size()||k<=0) ...

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。 方法1：利用hash表特性，时间复杂度O(n),空间复杂度O(n) 思路：由于n个数字的范围已知，都在[0,n-1]之间，所以建立一个长度为n的数组hash，遍历输入数组，将hash数组中下标对应原数组数值的+1，所以hash数组的下标即为输入数组的值，hash数组的值即为对应下标表示的数的个数 #include<iostr...

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 常规方法1： 若数组为空，返回0； 若数组中只有一个数字，直接返回那个数字； 对数组进行排序，vector<int>可直接用sort函数排序，然后设置两个前后位置i,j遍历找出出现次数大于数组一半的数字。找到后返回值即可。class Solution { public: int MoreThanHalfNum_Solution(vector<int> num...

1.求数字的全排列，允许有重复数字 http://www.cnblogs.com/cxjchen/p/3932949.html #include<iostream> #include <vector> #include <stdio.h> using namespace std; /* 开始选定第一个元素，将后面的元素进行全排列； 接下来用后面的每个元素与第一个元素交换，并排列后面的元素 */ static int Count = 0; //交换begin与其后的behind的字符 void swap(vector<int>& n...

小易觉得高数课太无聊了，决定睡觉。不过他对课上的一些内容挺感兴趣，所以希望你在老师讲到有趣的部分的时候叫醒他一下。你知道了小易对一堂课每分钟知识点的感兴趣程度，并以分数量化，以及他在这堂课上每分钟是否会睡着，你可以叫醒他一次，这会使得他在接下来的k分钟内保持清醒。你需要选择一种方案最大化小易这堂课听到的知识点分值。 主要是优化算法 #include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { int n, k; while ...

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。例如：N = 4，M = 24：4->6->8->12->18->24于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板 #include<iostream> #include<algorithm>...