只出现一次的数字

杨辉三角

删除有序数组的重复项

只出现一次的数字II

只出现一次的数字III 

数组中出现超过一半的数字

电话号码的字母组合

 练习子数组的最大和

只出现一次的数字

 思路:简单的位运算，对位运算想深入了解的可以看我这篇文章位运算。

class Solution {public:    int singleNumber(vector& nums) { int n=0; for(int i=0;i<nums.size();i++) {     n^=nums[i]; } return n;    }};

杨辉三角

class Solution {public:    vector<vector> generate(int numRows) {     vector<vector> a(numRows);     for(int i=0;i<numRows;i++)     { a[i].resize(i+1);//每行开辟i+个空间都默认为0  a[i][0]=a[i][i]=1;//保证每行的第一个和最后一个都是1for(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& 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& nums) {    map 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 singleNumber(vector& nums) {    map a;    vector 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 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& 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 letterCombinations(string digits) {      string combinStr;      vector 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;}

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖