没有加号的相加

题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
牛客题目来源
分析:
不用加减法，咋做加减？
这是个好问题
这里要补充一个知识点
两个数相 & 能够得到要进位的位 A
两个数相 ^ 能够达到各位相加后的没有进位的数 B
通过异或，我们是可以达到加法的目的的，前提是没有进位
那是不是一步步消除进位就好了呀
怎么消除进位呢，我们看一个例子

例子:
如果是 5+7 二进制分别为 0101 和 1001
0101 & 1001 = 0001 = 1
此时需要进位 1<<=1 == 2
0101 ^ 1001 = 1100 = 10
10+2 = 5+7
但是此时不能直接用 ^ 得到最终结果
只要在 & 最终为0 时，才能用 ^直接得到最终结果
还得继续
2 = 0010
10 = 1100
2&10 = 0
2^10 = 1110 = 12 = 5+7

题解和分析

int Add(int num1, int num2 ) {
    // write code here
    int a = 0;
    int b = 0;
    while(b = num1^num2,a = num1&num2)
    {
        a <<= 1;
        num1 = a;
        num2 = b;
    }
    return b;
}

总结

我总觉得这是计算机加法的本质 -
通过 & 可以得到要进位的值然后进行进位即可, 异或可以得到无需进位的相加值

统计 int 补码中的1

一个数在计算机是以补码的形式存在，如何统计补码中一的个数
这里用了一个比较巧妙的方式
n&(n-1) 会清除最右边的 1

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
	int n = -1;
	int count = 0;
	while (n)
	{
		count++;
		n &= (n - 1);
	}
	printf("%d", count);
	return 0;
}

小总结

n&(n-1) 会清除最右边的 1

除自身之外的积

除自身之外的积题目力扣来源
后面的题解是提供思路，直接拿去提交是过不了的

题解和分析

要求-给定一个数组，然后求除了某个数之外的数的乘积

方法一: 遍历，每次得到某个数，再遍历，得到其余数的乘积
好处: 简单暴力，但是不能满足时间要求

方法2 ：从那个数处分成两个数组，前缀积数组和后缀积数组，第一遍遍历得到前缀积，再遍历，得到后缀积，两者相乘就是合积
在这里插入图片描述

版本1

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int main()
{
	int arr[4] = { 1,2,3,4 };
	int pre[4] = { 0 };
	int aft[4] = { 0 };

	int i = 0,product = 1;
	for (i = 0, product = 1; i < 4; i++)
	{
		pre[i] = product;
		product *= arr[i];
	}
	for (i = 3, product = 1; i >=0; i--)
	{
		aft[i] = product;
		product *= arr[i];
	}
	for (i = 0; i < 4; i++)
	{
		printf("%d ", pre[i] * aft[i]);
	}
	return 0;
}

分析

我们有没有必要用三个数组，用三个循环？
其实是不用的，我们借用一个前缀数组，得到前缀积，此时的数就已经能够运算了,可以少用一个 aft

版本2

只是直接利用了原数组的空间直接接受后缀 * 前缀的值，减少空间利用罢了

for (i = 0, product = 1; i < 4; i++)
	{
		pre[i] = product;
		product *= arr[i];
	}
	for (i = 3, product = 1; i >= 0; i--)
	{
		pre[i] *= product;
		product *= arr[i];
	}
	for (i = 0; i < 4; i++)
	{
		printf("%d ", pre[i]);
	}

摩尔投票法

要求:
给定一个数组，一定会有一个数出现大于 n/2 次, 找到这个数
分析:
找到多数元素
长度多，数据大，本来我是想着全部统计，但是显然会直接超时
这里给到一个信息，是出现次数大于 n/2 的元素，利用这个特性，思考一下
如果是n个数据，只有两个数一个数大于 n/2个，一个数小于 n/2 个
无论哪个在前，当我一个个用大于 n/2的数来抵消其他数,剩下的一定是大于 n/2的数
如何实现这个过程?
取到第一个数，一路抵消到没有，就换数，这样每个数都被逐个抵消，剩下的只能是多数
大鱼吃小鱼，剩下的只有大鱼
寻找多数元素的题目

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
	int nums[] = { 2,2,1,1,1,2,2 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	int i = 0;
	int temp = nums[0];
	int count = 1;
	for (i = 1; i < Size; i++)
	{
		if (nums[i] == temp)
		{
			count++;
		}
		else
		{
			count--;
			if (count == 0)
			{
				temp = nums[i];
				count = 1;
			}
		}
	}
	printf("%d", temp);
	return 0;
}

珠玑妙算

珠玑妙算题目描述
题目描述:
计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。
例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。
作为用户，你试图猜出颜色组合。
打个比方，你可能会猜YRGB。
要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。

题目分析:
一开始看，我是一脸懵逼
首先，比较简单理解的就是，猜中，位置颜色都对就是猜中吧
那我就先把位置颜色一样的搞定，然后伪猜中的时候不管他，去掉
伪猜中怎么理解？
我们可以尝试把不是猜中的颜色按顺序编号
比如你猜的是 YRGB 实际是 RGGB
去掉猜中的 G 剩下 YR-B 和 RG-B
然后编号颜色 Y1 R1 B1 ; R1 G1 B1

然后按顺序找
猜测有R1, 实际也有 R1
猜测有B1, 实际也有 B1
就是两次伪猜测

int* masterMind(char* solution, char* guess, int* returnSize)
{
   int i = 0;
   int lens = 4;
   int *times = malloc(2*sizeof(int));
   
   for(i = 0;i<2;i++)
   {
       times[i] = 0;
   }
   //处理猜中的
   for(i = 0;i<lens;i++)
   {
       if(solution[i]==guess[i])
       {
           times[0]++;
           solution[i] = 0;
           guess[i] = 1;
       }
   }
   //处理伪猜中
   for(i = 0;i<lens;i++)
   {
       int j = 0;
       for(j = 0;j<lens;j++)
       {
           if( guess[i] == solution[j])
           {
               solution[j] = 0;// solution的消除方式
               guess[i]=1; //guess 的消除方式
               times[1]++;
           }
       }
   }
   *returnSize = 2;
   return times;
}