《剑指Offer》–算法
#include<iostream>
#include<vector>
using namespace std;
int MoreThanHalfNum_Solution(vector<int> nums)
{
int majority = nums[0];
for (int i = 1, cnt = 1; i < nums.size(); i++) {
cnt = nums[i] == majority ? cnt + 1 : cnt - 1;
cout << "cnt" <<cnt<< endl;
if (cnt == 0) {
majority = nums[i];
cnt = 1;
}
}
int cnt = 0;
for (auto val : nums) {
if (val == majority)
cnt++;
}
return cnt > (nums.size() / 2) ? majority : 0;
}
int LastRemaining_Solution(int n, int m) {
cout << "************LastRemaining_Solution************" << endl;
int count = 0;
int i = 0;
int k = -1;
int* a = new int[n];
for ( i = 0; i <n; i++)
a[i]=0;
while (count <n-1)
{
i = 0;
while (i < m)
{
k = (k + 1) % n;
if (a[k] == 0)
{
i++;
if (i % m == 0)
{
a[k] = -1;
count++;
}
}
}
}
for (i = 0; i < n; i++)
cout << a[i];
for (i = 0; i < n; i++) {
if (a[i] == 0) {
k= i + 1;
break;
}
}
delete a;
return k;
}
void test_MoreThanHalfNum_Solution()
{
vector<int> nums = { 1,1,1,4,4,4,5,5,5,5,5,5,5,5,5,5};
int majority = MoreThanHalfNum_Solution(nums);
cout << "数组出现最多的个数是:" << majority << endl;
}
int NumberOf1Between1AndN_Solution(int n) {
int cnt = 0;
for (int m = 1; m <= n; m *= 10) {
int a = n / m, b = n % m;
cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
}
return cnt;
}
int main()
{
cout << "test" << endl;
int i= NumberOf1Between1AndN_Solution(13);
cout <<i<< endl;
getchar();
return 0;
}