当前位置：首页 > news >正文

【C语言】数据结构基础（每日小细节025），有三数之和哦

news 来源：原创 2024/11/16 7:53:04

算法好题初阶（一共14回已经更新完毕），从今天开始就是基础的数据结构题目

1.只出现一次的数字

如果不额外开辟任何空间的话一定要想到位运算符

异或^ :两个整数异或，遵循相同为0，相异为1的二进制位运算规则

（1）任何两个相同的数字异或之后都是0

（2）任何数字和0异或之后都是本身

（3）异或遵循结合律和交换律

知道这些之后这个题就变得尤为简单，因为根据（1）所有数字里面成对出现的异或之后都是0,0和单身狗异或之后还是单身狗，并且因为（3）所以我们上面分析的过程是正确的，即使成对出现的数字不挨着，交换之后还是对的

int singleNumber(int* nums, int numsSize){
int ans=0;
for(int i=0;i<numsSize;i++)
{
    ans^=nums[i];
}
return ans;
}

2.多数元素

看到一个很有意思的解法，每个数字都代表了一个门派，开始打擂台，假设每个角色的攻击力一样，那么1v1就是两个人都死，擂台上无人（count==0）时，那么直接站上去（ans=nums【i】），如果上来一个同门派（nums【i】==ans）那么人数++（count++），如果上来别的门派直接各死一个（count--）

int majorityElement(int* nums, int numsSize){
int ans=-1,count=0;
for(int i=0;i<numsSize;i++)
{
    if(count==0)
    {
        ans=nums[i];
        count+=1;
    }
    else if(nums[i]==ans)
    {
          count+=1;
    }
    else
    {
        count-=1;
    }
}
return ans;
}

3..三数之和

三数之和是两数之和的进阶版

两数之和

两数之和是很简单的，甚至暴力遍历也可以

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
*returnSize=2;
int* tmp=(int*)malloc(sizeof(int)*2);
for(int i=0;i<numsSize;i++)
{
    for(int j=i+1;j<numsSize;j++)
    {
        if(nums[i]+nums[j]==target)
        {
            tmp[0]=i;
            tmp[1]=j;
            return tmp;
        }
    }
}
return NULL;
}

三数之和就是一个进阶版，首先暴力不能解决问题，太显然了，时间肯定超

那么还记得昨天更新的最后一天二叉搜索树里面的找两个节点的最近共同祖先，其实一个思路，昨天的思路不重复了，今天的是首先把数组排序，然后规定三个下标变量，left，right，mid，顾名思义，left从0开始，right从最后一个下标开始，mid就是left的下一个，然后开始计算三个数字的和，如果sum<0,那么说明mid的值应该更大一点，因为在我们的方法里left是最外层的循环，right除了nums[right]==nums[--right]还有sum>0,否则也是不会变的，所以只能mid向后走，因为已经有序所以向后就是增大sum

同理，如果sum>0，就应该让right--,平衡sum

最后如果有和nums[left]重复的元素，直接不遍历，left返回for循环就可以

如果有和nums[mid]相同的元素，mid++

如果有和nums[right]相等的元素，right--

 int cmp(const void* a1,const void*b1)
 {
     return *(int*)a1-*(int*)b1;
 }
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
*returnSize=0;
if(numsSize<3) return NULL;
qsort(nums,numsSize,sizeof(int),cmp); //排序
int** ans=(int**)malloc(sizeof(int*)*numsSize*numsSize);
*returnColumnSizes=(int*)malloc(sizeof(int)*numsSize*numsSize);
int i,j,k,sum,left,right=0,mid=0;
for(left=0;left<numsSize-2;left++)
{
    if(nums[left]>0) return ans;
    if(left>0 && nums[left-1]==nums[left]) continue;
    mid=left+1;right=numsSize-1;
    while(mid<right)
    {
        sum=nums[left]+nums[right]+nums[mid];
        if(sum==0)
        {
            ans[*returnSize]=(int*)malloc(sizeof(int)*3);
            (*returnColumnSizes)[*returnSize]=3;
            ans[*returnSize][0]=nums[left];
            ans[*returnSize][1]=nums[mid];
            ans[*returnSize][2]=nums[right];
            *returnSize+=1;
            while(mid<right && nums[mid]==nums[++mid]);
            while(mid<right && nums[right]==nums[--right]);
        }
        else if(sum<0)
        {
            mid++;
        }
        else{
            right--;
        }
    }

}
return ans;
}

一定要注意二维数组的初始化,一定是数组大小的平方！！！否则会栈溢出，或者写一个可以扩容的也行，但是这个题目的难点显然就不在这里，所以比数组长度平方还大肯定没问题