39（169） 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2限制：
1 <= 数组长度 <= 50000题解
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0, votes = 0, count=0;
for(int num : nums){
if(votes==0)x=num;
votes+=num==x?1:-1;
}
// 验证 x 是否为众数
for(int num : nums)
if(num == x) count++;
return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0
}
};62 圆圈中最后剩下的数
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3示例 2：
输入: n = 10, m = 17
输出: 2限制：
1 <= n <= 10^51 <= m <= 10^6
题解
class Solution {
public:
int lastRemaining(int n, int m) {
int x = 0;
for(int i=2;i<=n;i++){
x=(x+m)%i;
}
return x;
}
};43（233） 从 1 到 n 整数中 1 出现的次数
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5示例 2：
输入：n = 13
输出：6限制：
1 <= n < 2^31
题解
class Solution
{
public:
int countDigitOne(int n)
{
long long digit = 1, res = 0;
int high = n / 10, cur = n % 10, low = 0;
while (high != 0 || cur != 0)
{
if (cur == 0)
res += high * digit; // 0
else if (cur == 1)
res += high * digit + low + 1; // 1
else
res += (high + 1) * digit; // 2-9
low += cur * digit;
cur = high % 10;
high /= 10;
digit *= 10;
}
return res;
}
};
