只出现一次的数字
思路:简单的位运算，对位运算想深入了解的可以看我这篇文章位运算。
class Solution { public: int singleNumber(vector<int>& nums) { int n=0; for(int i=0;i<nums.size();i++) { n^=nums[i]; } return n; } };
杨辉三角
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> a(numRows); for(int i=0;i<numRows;i++) { a[i].resize(i+1);//每行开辟i+个空间都默认为0 a[i][0]=a[i][i]=1;//保证每行的第一个和最后一个都是1 for(int j=1;j<i;j++) { a[i][j]=a[i-1][j-1]+a[i-1][j];//根据规律得出的式子 } } return a; } };
删除有序数组的重复项
思路:我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就告诉 slow 并让 slow 前进一步。这样当 fast 指针遍历完整个数组 nums 后，**nums[0..slow] 就是不重复元素**。
class Solution { public: int removeDuplicates(vector<int>& nums) { int n=nums.size(); if(n==0) { return 0; } int fast=1,low=1; while(fast<n) { if(nums[fast]!=nums[fast-1]) { nums[low]=nums[fast]; low++; } fast++; } return low; } };
只出现一次的数字II
思路：我在力扣上看到了电路门，异或等解决方案,不过我还是觉得哈希表最实用,用的也比较多,我这里只提供哈希表做题思路:
我们可以使用哈希映射统计数组中每个元素的出现次数。对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数。
在统计完成后，我们遍历哈希映射即可找出只出现一次的元素。
class Solution { public: int singleNumber(vector<int>& nums) { map<int,int> a; int n=nums.size(); int ans=0; for(int i=0;i<n;i++) { a[nums[i]]++; } for(int i=0;i<n;i++) { if(a[nums[i]]==1) { ans=nums[i]; break; } } return ans; } };
只出现一次的数字III
思路:运用哈希表直接可以做出来,不过这题推荐用异或来做提升自己的思维。我这里就光给出哈希表的答案,异或大家可以去试一下,力扣也给出了官方题解
class Solution { public: vector<int> singleNumber(vector<int>& nums) { map<int,int> a; vector<int> c; for(auto m:nums) { ++a[m]; } for(auto m:nums) { if(a[m]==1) { c.push_back(m); } } return c; } };
数组中出现超过一半的数字
思路:可以先将数组排序，然后可能的众数肯定在数组中间，然后判断一下，这里其实也不需要判断,因为数组中超过一半的数字就是说中间数肯定是众数
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { sort(numbers.begin(), numbers.end()); int cond = numbers[numbers.size() / 2]; int cnt = 0; for (const int k :numbers) { if (cond == k) ++cnt; } if (cnt > numbers.size() / 2) return cond; return 0; } };
电话号码的字母组合
思路:这题我只能想到用深搜,可以说是模板题,大家可以看看我写的算法博客里有DFS和回溯算法的模板
class Solution { string arr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; public: void _letterCombinations(const string& digits,size_t i,string combinStr,vector<string>& strV) { if(i==digits.size()) { strV.push_back(combinStr); return ; } string str=arr[digits[i]-'0']; for(size_t j=0;j<str.size();j++) { _letterCombinations(digits,i+1,combinStr+str[j],strV); } } vector<string> letterCombinations(string digits) { string combinStr; vector<string> strV; if(digits.empty()) { return strV; } _letterCombinations(digits,0,combinStr,strV); return strV; } };
练习子数组的最大和
思路:动态规划，设动态规划列表 dp，dp[i] 代表以元素 array[i] 为结尾的连续子数组最大和。
状态转移方程： dp[i] = Math.max(dp[i-1]+array[i], array[i]);
具体思路如下：
1.遍历数组，比较 dp[i-1] + array[i] 和 array[i]的大小;
2.为了保证子数组的和最大，每次比较 sum 都取两者的最大值;
3.用max变量记录计算过程中产生的最大的连续和dp[i]；
public int FindGreatestSumOfSubArray(int[] array) { int sum = 0; int max = array[0]; for(int i=0;i<array.length;i++){ // 优化动态规划，确定sum的最大值 sum = Math.max(sum + array[i], array[i]); // 每次比较，保存出现的最大值 max = Math.max(max,sum); } return max; }
