编程之美总结

缺乏、安全感 2022-08-11 12:59 249阅读 0赞

2.1.求二进制中1的个数

除数取余 v & (v - 1)

2.2.不要被阶乘吓倒：求N!中末尾有多少个0

N! = 2^a\*3^b\*5^c\*7^d\*11^e\*....

然后N!中能被x整除的数为\[N/x\]

由此可知：能被5整数的个数就是\[N / 5\] + \[N / (5^2)\] + \[N / (5^3)\]+...

2.3.寻找发帖“水王”：“水王”发帖数超过总帖数的一半，找出这个”水王“的ID

思想：先排序，然后找出超过一般的ID；先排序，然后在\[N/2\]项就是这个ID；每次删除两个不同的ID，最后一个肯定是这个水王的ID

int main()
    {
    	int a[10] = {0,1,2,3,0,0,0,7,0,0};
    	int nTimers = 0;
    	int candi;
    	for(int i = 0; i < 10; ++i)
    	{
    		if(nTimers == 0)
    		{
    			candi = a[i];
    			nTimers = 1;
    		}
    		else
    		{
    			if(candi == a[i])
    				++nTimers;
    			else
    				--nTimers;
    		}
    	}
    	cout<<candi<<endl;
    	return 0;
    }

2.4. 1的个数，给定一个N，求出1~N个数中有多少个1.

思想：从1开始遍历求出每个数的1的个数，然后计算总和；找规律，逐个求每位数中1出现的个数，然后求和

int Sumls(int n)
    {
    	int icount = 0;
    	int ifactor = 1;
    	int ilow = 0;//存放地位的数
    	int iCurr = 0;//存放当前位的数
    	int ihigh = 0;//存放高位的数
    	while(n / ifactor != 0)
    	{
    		ilow = n - (n / ifactor) * ifactor;//此处不为0，因为n/ifactor不一定整除
    		iCurr = (n / ifactor) % 10;
    		ihigh = n / (ifactor * 10);
    		switch(iCurr)
    		{
    			case 0:
    				icount +=ihigh * ifactor;
    				break;
    			case 1:
    				icount += ihigh * ifactor + ilow + 1;
    				break;
    			default:
    				icount += (ihigh + 1) * ifactor;
    				break;
    		}
    		ifactor *= 10;
    	}
    	return icount;
    }

根据上面的式子求出Sumls(N) = N的最大的N,由

Sumls(9) = 1;

Sumls(99) = 20;

Sumls(999) = 300;

Sumls(9999) = 4000;

存在一个公式Sumls(10^n - 1) = n\* 10^(n -1);

当N = 11时候

2.5寻找最大的K个数

利用堆排序，先建立小根堆，然后再逐个与对顶比较；如果数都为整数还是有限的，则利用数组存放所有的数的次数。

2.6.给定一个有限小数或无限循环小数，将其转换成分数，精确表达出来。

思想：如果为不循环小数，可以直接将其乘以10^n扩大成整数，然后将其数与10^n去掉公约数即可

如果为无限循环小数，则将循环部分变成小数，不循环部分变成整数。如果循环的位数为n，则与10^n - 1一起去掉公约数即可。最大公约数的求法见下一题

2.7.求两个数的最大公约数

辗转相除法：f(x，y) = f(y,x%y)（x>=y>0）直到y = 0时候，则另外一个数就是他们的最大公约数

但是要知道，除法比移位开销大，而取模用到了除法

可将其转换成f(x,y) = f(y,x - y)（x>=y>0）直到y= 0时，另一个为最大公约数（减少了开销，但是迭代次数比较多）

最佳方法：

将两个数变成二进制数，然判断两个是否为偶数，有的话提取公共因子，没有的话，如果一个奇数

f(42,30) = f(101010,1110) = 2\*f(10101,1111) = 2\*f(1111,110) = 2\*f(1111,11) = 2\*f(1100,11) = 2f(11,11) = 2\*f(00,11)=2\*11 = 6

2.8找符合条件的整数：给定一个最小的正整数N，求一个最小的正整数M，是的N\*M的十进制表示形式里只含有1和0

思路：首先给出N，然后从0,1,10,11这样逐个与N相处，能整数的则为最小的正整数

最佳思路：还未看懂。。。

2.9.斐波拉切数列

老题目不谈了~

2.10.寻找一个数组的最大值和最小值

为了减少比较次数，则使用数组中0和1比较，然后将最大的与max比较，最小的与min比较，则两个数比较3次，n个数比较1.5n次

2.11.在一个平面上N个点的坐标，找出距离最近的两个点

这个没看懂，以后解决。

2.12.给定一个数组，快速找出两个数使得它们的和为N

思路：hash表，先将数组中的值hash入数组，然后逐个看N-A\[i\]的值在hash表中是否存在；

首先排序，然后i = 0,j = n - 1,如果A\[i\] + A\[j\] =N则退出，如果小于N，则i递增，如果大于N，j递减，如此循环

2.13.给定一个个数为N的整数数组，找出任意N-1个数使得乘积最大。

见本人有个帖子转换说明

2.14.求数组的子数组的最大值，给定一个数组，求出连续n个数他们之和为最大值

思路：设定一个数存放历史最大值，一个数存放当前的最大值

逐个访问，如果当前最大值为负数，则重置为0，如果非负数，则与历史最大值比较，如果大，则改变历史最大值

<span style="font-size:18px;">int maxValue(int *A,int size)
    {
    	int start = A[0];//存放当前连续最大值
    	int MAX = A[0];
    	for(int i = 1;i < size;++i)
    	{
    		if(start < 0)
    			start = 0;
    		start += A[i];
    		if(start > MAX)
    			MAX = start;
    	}
    	return MAX;
    }</span>

2.15.