目录
数组中出现次数超过一半的数字.
方法一：摩尔投票法
/*
解题思路：
摩尔投票法的解题思路比较简单，假设如果当前没有候选人(cnt = 0，val = 0)，那么第一个出现的数字就投
票给他，遍历的过程只要值与val的值相等那么cnt就计数++，否则就计数--，两种情况，第一次出现的人已经
获胜那么返回该值即可，如果中途被选下去需要换人重新投票
*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
int val = 0, count = 0;
for(auto &ref : nums)
{
if(!cnt) val = ref , count = 1; //换人重新投票
else val == ref ? count ++ : count --; //得到一票计数++，否则计数--
}
return val;
}
};
方法二：map
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int, int> m;
int cnt = 0, val = 0;
for(auto &ref : nums)
{
m[ref]++; //统计计数
if(m[ref] > cnt){ //比较cnt，记录出现次数最多的val值
cnt = m[ref];
val = ref;
}
}
return val;
}
};
构建乘积数组.
解题步骤：
1、先从前往后遍历一遍原数组将计算的结果依次存放到这个临时数组v中
vector<int> v(n);
for(int i = 0, p = 1; i < n; i++)
{
v[i] = p; //遍历原数组a计算的乘积暂存到v中
p *= a[i]; //利用临时变量累计乘积
}
2、将原来存放在v中的值取出来，从后往前遍历原数组计算他们的乘积再保存回v中
for(int i = n - 1, p = 1; i >= 0; i--)
{
v[i] *= p; // 遍历原数组a计算的乘积暂存到v中
p *= a[i]; //利用临时变量累计乘积
}
相当是先算左边的乘积，再算右边的乘积，最终将他们的乘积相乘再存放至v中
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
if(a.empty()) return a;
int n = a.size();
vector<int> v(n);
for(int i = 0, p = 1; i < n; i++)
{
v[i] = p; //遍历原数组a计算的乘积暂存到v中
p *= a[i]; //利用临时变量累计乘积
}
for(int i = n - 1, p = 1; i >= 0; i--)
{
v[i] *= p; // 遍历原数组a计算的乘积暂存到v中
p *= a[i]; //利用临时变量累计乘积
}
return v;
}
};
和为s的连续正数序列.
/*
解题思路：
使用双指针做法，选i，j位置作为起始位置，j往后遍历的过程中求和
直到j到达某一位置计算的和值等于原先的目标值(s == sum),再将该区间
【i，j】的值保存至vector中，接着i再从下一处位置开始继续后续循环
*/
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> res;
for(int i = 1, j = 1,s = 1; i <= sum; i++)//i,j指针从起始地出发
{
while(s < sum) s += ++j; // 记录
if(s == sum && j - i > 0)//判断是否合法
{
vector<int> v;
for(int k = i; k <= j; k++) v.push_back(k);//记录合法值
res.push_back(v);
}
s -= i; //既然i指针在往后移动后s需要减小
}
return res;
}
};
圆圈中最后剩下的数字.
计算公式：（总长度 + m）% 总长度
class Solution {
public:
int lastRemaining(int n, int m) {
return n == 1 ? 0 : (lastRemaining(n - 1, m) + m) % n;
}
};