两个链表的第一个公共结点：最直观的想法是，首先计算链表1和链表2的长度以及链表1与链表2的差值长度diff，然后将长度较大的那个链表走diff步，接着两个链表一起走并判断是否相等，如果是则返回该相等的公共结点，注意，由于此处没有头结点，故不需要判断当前链表的下一个是否想等，而是直接判断当前链表是否想等即可。 // 求链表长度 int GetLength(ListNode *pLink) { int len=0; while(pLink) { len++; pLink=pLink->next; } return len; } ListNode* FindFirstCommonNode( L...

数组中的逆序对：最直观的想法是，二层循环，使用变量i遍历数组表示当前元素，使用变量j遍历数组表示当前元素在当前轮次中对应的后续元素，然后判断data[i]是否大于data[j]，如果是则将res加一，并对应模以1000000007，最后返回res即可。(超时) int InversePairs(vector<int> data) { int res=0; for(int i=0;i<data.size();i++) { for(int j=i+1;j<data.size();j++) { if(data[i]>data[j]) res=(res+1)%100000...

第一个只出现一次的字符：最直观的想法是，使用一个unordered_map来存储字符串中的字符、字符出现的次数、字符第一次出现的位置下标，使用res来记录结果，其初始化为-1，然后从头到尾遍历字符串，如果该字符第一次出现，则将其次数设为1，并记录对应的位置下标，反之如果第n次出现，则将其次数加一即可，最后遍历umap，如果对应出现次数为1，则记录结果并返回即可。但是这样有一个问题，即umap其存储是无序的，内部实现是hash，那么就会导致遍历umap时，其出现的顺序与字符元素出现的顺序不一致。(umap元素顺序与字符串str元素出现顺序不一致) int FirstNotRepeatingCha...

丑数：最直观的想法是，暴力质因数分解，由于此处质因子只有2、3、5，故与原始质因数分解写法有些许不同。首先编写isUgly函数用于判断数n是否为丑数，由于1、2、3、4、5、6均是丑数，故若index小于等于6，则直接返回index即可，反之记录当前丑数数量num为6，再从7开始遍历，如果当前数是丑数，则对应丑数数量num加一，再判断丑数数量num是否等于给定个数index，如果是则记录结果并返回。(超时) //判断是否为丑数 与原始的质因数分解不同 bool isUgly(int n) { while(n%2==0) n/=2; while(n%3==0) n/=3; while(n%5==...

最长不含重复字符的子字符串：最直观的想法是，使用变量i表示字符串起始位置，使用变量j表示字符串结束位置，i的范围是0~s.size()，j的范围是i~s.size()，每个起始位置轮次，创建一个无序集合unordered_set来存储从该起始位置开始不重复的字符，如果当前字符s[j]在uset中未出现过，那么就加入uset，反之则退出内层循环，同时计算字符串长度更新最长子字符串长度。其中有两点需要注意的地方：一个是当字符串只含有一个空格时，即s=" "，那么应该返回1，这是测试样例中的一个例子；另一个是j的作用域不应该只设置在内层for循环，因为有可能字符串遍历完，即j=s.size()，此时...

礼物的最大价值：最直观的想法是，使用二维数组dp[i][j]表示第i行第j列所能拿的礼物的最大价值，首先初始化第一行和第一列，其是当前行(列)前一个最大价值与当前元素之和，接着从左向右从上向下遍历，其中dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j]，最后返回dp[m-1][n-1]即可。 int maxValue(vector<vector<int> >& grid) { //m表示长 n表示宽 int m=grid.size(),n=grid[0].size(); //dp[i][j]表示第i行第j列的所能拿的礼物的最大价...

把数字翻译成字符串：最直观的想法是，一开始想，首先使用dp[i]表示前i个字符串的翻译结果数，初始化均为1，因为字符串一个字符一个字符翻译则结果数为1，然后从第二个元素开始遍历，如果当前字符和前一个字符组成的数在10~26之间，则会出现两种翻译结果，一种是一个字符一个字符，另一种是当前字符和前一个字符，dp[i]=2*dp[i-1]，反之则直接翻译，dp[i]=dp[i-1]，最后返回dp[nums.size()-1]即可。(出错)分析：但是上述这样想出错了，那么肯定是递推公式有些许问题，不过动态规划本身就有点复杂，错了也没关系，肯定是某些方面没有考虑全面，找找原因再接再厉好啦。根据上述描述，...

把数组排成最小的数：最直观的想法是，重载sort函数的cmp函数，注意，其中的cmp函数是静态的，因为static函数与具体的对象无关，其可以被全局调用。排序即按照一定顺序排列元素，该顺序可以是递增的，也可以是递减的，甚至可以是自定义的。由于返回的结果要求是字符串，故先将数字数组转换为字符串数组，然后对字符串数组按照自定义顺序cmp进行排序，接着将排序后的字符串数组元素拼接成字符串，其中cmp是字符串拼接比较函数，即字符串s1和s2，其要求s1+s2小于s2+s1的，其中字符串比较是按照字典顺序比较的。 static bool cmp(string &s1,string &s2) { retu...

数字序列中某一位的数字：最直观的想法是，将数字序列转换为字符串，然后利用字符串长度函数来获取对应位数的相应数字即可。但是该题中函数的参数值只有第n位而没有数字序列，所以我们需要对数字序列找规律。数字序列为“01234567891011...”，即按照0、1、2、3...自然数依次排列，并且序列位数从0开始，即第0位是0、第1位是1、第2位是2...第10位是1等依次类推。idea：第一步确定输入的数位n对应的位数digit，比如求第n=15位对应的数字，那么n=15这个数的位数digit=2，如此便可以定位到其对应的区间，为了规律性我们忽略掉0，比如区间1~9，起始位置start为1，位数di...

整数中1出现的次数(从1到n整数中1出现的次数)：最直观的想法是，遍历1到n，然后将每一个数转换为字符串，再遍历字符串求字符1出现的次数，依次累加即可得到结果。其中，之所以将数字转换为字符串，是为了利用字符串的长度函数来求长度，避免整数位数不确定的情况。 int NumberOf1Between1AndN_Solution(int n) { string str; int res=0; for(int i=1;i<=n;i++) { str=to_string(i); for(int j=0;j<str.size();j++) { if(str[j]=='1') res++; } ...

连续子数组的最大和：最直观的想法是，使用一个变量i枚举区间起始位置，使用一个变量j枚举区间结束位置，使用一个变量k枚举区间变量值用于求和，使用一个变量sum用于求区间和，使用一个变量ans用于求区间和最大值，三层for循环。（但是很明显该方法超时故我们需要优化时间复杂度） int FindGreatestSumOfSubArray(vector<int> array) { //数组长度 int n=array.size(); //最大和 int ans=INT_MIN; //起始位置 for(int i=0;i<n;i++) { //结束位置 for(int j=i;j&lt...

数据流中的中位数：最直观的想法是，使用sort函数对数组进行排序，如果数组长度为奇数，则返回数组最中间的一个数，反之如果数组长度为偶数，则返回数组最中间的两个数之和的平均值。 vector<int> res; //结果数组 void Insert(int num) { //存储数据 res.push_back(num); } double GetMedian() { //排序 sort(res.begin(),res.end()); //求长度 int n=res.size(); //中位数结果 double result; //数组长度为奇数 if(n%2!=0) result=...

最小的k个数：最直观的想法是，使用sort排序，然后遍历数组返回前k个数或者直接使用迭代器返回前k个数。 vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> res; if(input.size()==0) return res; sort(input.begin(),input.end()); //不能越界且为k个数 for(int i=0;i<k&&i<input.size();i++) res.push_back(input[i]); re...

数组中出现次数超过一半的数字：最直观的想法是，使用unordered_map来存储<int,int>类型的键值对，其中第一个int表示key即元素值，第二个int表示value即该元素出现的次数，然后遍历numbers数组，将该元素值对应的次数加一，并判断其次数是否大于数组长度的一半，如果是则记录结果并返回。 unordered_map<int,int> umap; int MoreThanHalfNum_Solution(vector<int> numbers) { int result; for(int i=0;i<numbers.size();i...