Error[8]: Undefined offset: 1507, File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 121
File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 473, decode(

文章目录


前言

编程是需要不断练习实践的,所以刷题是很有必要的。但是不能盲目的刷题,要对做过的题题目进行总结复盘。以下是我对暑假期间做过的题目的部分总结,做个简单的记录。


1、重合元素问题 1.力扣645 错误的集合

题目链接力扣645

题目的要求就是在1到n中查找重复的数字和丢失的数字,我们先这样思考一下假如集合中1到n没有发生丢失,1到n就是自然数顺序排列,这样和我们数组的下标是和契合的,数组的下标就是0到n-1的自然数顺序数列,那我们将集合的每个元素减1当作另一个数组的下标来使用,将这个数组的所有的元素的元素初始化都置为0,再用集合中元素当作此数组下标,进行遍历加1,因为有重复的数据,所以数组中某个位置处肯定是2,找到这个2的位置,也就是数组的下标,这个下标就是重复的数据,因为丢失了某个数据。也就是说数组的某个位置没有加1,还是初始值0,找到0所对应的下标就是丢失的数据。

基于上述思路写出如下代码

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    *returnSize=2;
    int* arr1;
    arr1=(int*)malloc(sizeof(int)*2);
    int* arr2;
    arr2=calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]-1]++;
    }
    for(int j=0;j<numsSize;j++)
    {
        if(arr2[j]==2)
          {
              arr1[0]=j+1;
          }
          else if(arr2[j]==0)
          {
              arr1[1]=j+1;
          }
    }
  return arr1;
}

在这里说一下,力扣是接口型oj,,函数的返回值和参数都已经写好固定了,只要完善这个函数即可。这个代码中calloc函数是动态分配空间,并且将分配的空间的元素都置为0,有类似于初始化的作用,malloc函数只是分配空间.
因为数组的下标是从0开始的,所以将集合中元素当作下标的时候减1,同时在找丢失的数据和重复的数据的时候需要再把这个1加回来,当然也可以多申请一个空间,这样就不用加1减1了,但是要注意集合的下标不要越界。
arr2[nums[i]-1]这是十分最主要的一步。
这道题其实就是处理元素重合问题,处理这种问题,将要处理的集合元素转化为另一个数组的下标是一种很有用的方法。

2.力扣349求两个数的交集

题目链接 力扣349题

这道题也是重和的问题,还可以利用上述的方法。将集合的元素转化成数组的下标,只不过不用加1,我们直接将数组元素置为一个数,因为要处理两个集合,这两个集合的元素不确定出现多少次,比如2在集合1和集合2中重复3次,3在集合1和集合2出现了1次,如果还是采用加加的 *** 作 不好通过数组的元素的值判断重复的元素,直接将给数组元素置数赋值,就可以很好的处理了
基于上述思路,写出如下代码

int* intersection(int* nums1, int nums1Size, int* nums2,
 int nums2Size, int* returnSize)
 {
*returnSize=0;
int* arr=calloc(10001,sizeof(int));
int* return_arr=malloc(10001*sizeof(int));
for(int i=0;i<nums1Size;i++)
{
    arr[nums1[i]]=1;
   
 }
   
 for(int j=0;j<nums2Size;j++)
 {
     if(arr[nums2[j]]==1)
     {
         arr[nums2[j]]=2;
     }
 }

 for(int k=0;k<1001;k++)
 {
     if(arr[k]==2)
     {
         return_arr[*returnSize]=k;
         *returnSize+=1;
     }
 }
 return return_arr;

}

我们先将集合1元素当作数组下标,并且将数组元素置为1,接着再将集合2的元素当作数组下标,再里面找1,如果找到了1,这个位置的下标就是两个集合中相同的元素,那么为了找到这个下标,直接将其置为2,就一步就相当于对数组该位置进行标记。最后在数组中找到2对应的下标,这个下标就是重复的元素,因为我没有减1,直接用的集和元素,所以在下标就是重复元素,就不用再去减1了。同时题目给了集合元素个数范围,为了避免空间不够,我就申请了10001*4字节的空间

3. 牛客HJ10 字符个数统计

题目链接字符统计个数

这道题还是元素重和问题,还是老方法,将字符串每个字符转成另一个数组的下标来处理。因为题目说了多个相同只算一次,同时字符串也没有空格。还是直接数组元素置数。

代码如下

#include
int word_count(char* str, int len)
{
    int arr[127] = { 0 };
    int count = 0;
    for (int i = 0; i < len; i++)
    {
        arr[str[i]] = 1;
    }
    for (int i = 0; i < 127; i++)
    {
        if (arr[i] == 1)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    char str[5001] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int ret = word_count(str, len);
    printf("%d", ret);
    return 0;
}

之所以将数组的个数设置成127因为字符对应的ASCII值最大为127,也就是字符串字符作为数组下标时最大只能到127.将数组元素置为1,在判断如果数组元素时1,计数器加1,这样置数赋值,就算有重复的字符也只计算一次。

4.力扣448找到数组中消失的数字

题目链接 力扣448题

这题和第一道例题特别相似,题目还是关于元素重合问题,这个找没有出现的的元素,第一道例题是找丢失的元素,很明显题目是换了个马甲,还是老方法处理转成数组下标然后置数赋值

基于以上思路,写出如下代码

int* findDisappearedNumbers(int* nums, int numsSize,int* returnSize)
{
     *returnSize=0;
    int* arr1=(int*)malloc(sizeof(int)*(numsSize+1));
    int* arr2=calloc((numsSize+1),sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]]=1;
    }
    for(int j=1;j<numsSize+1;j++)
    {
        if(arr2[j]==0)
          {
              arr1[*returnSize]=j;
              *returnSize+=1;
          }
          
    }
  return arr1;
}

利用calloc函数将开辟的空间中的元素初始化为0.将集合的元素转化为数组下标,这次我直接将集合中的元素转为下标没有减1,然后置1进行判断找到还是0的元素下标,但是要注意一点就是由于集合元素转为数组下标时没有减1,开辟空间是需要比集合的元素个数多一个的。因为数组的元素个数是和决定了数组元素下标最大值的,数组下标必须要满足大于等于集合中的最大元素的。

2.杂题汇总 1.摩尔投票法

题目链接 力扣169

题目描述,集合中一定有一个出现次数的最多的元素,找出来这个元素。这道题用摩尔投票法可以轻松解决。什么是摩尔投票法,这里先不说卖个关子,我们直接看代码分析

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

摩尔投票法,听着名字挺唬人的。按照我自己理解就是一换一厮杀法 求解数组中最多元素问题 。假如在3国时,蜀吴各有两千士兵,现在魏国有1万士兵,现在3国进行决战,魏蜀吴的士兵每个士兵都只能一换一同归于尽,那么最后打赢的一定是魏国。因为3方士兵只能一换一,魏国士兵最多。这个厮杀的过程就是在找出现次数最多的元素,为了模拟这个厮杀过程 可以用一个计数器来表示,将不同的元素想象成不同国家的士兵 ,计数器来表示生命值 ,遇到相同士兵计数器就加一, 表示结成阵营, 不同的就减一 ,表示一换一杀死了一个士兵。一旦计数器为0,就换下一个兵种,最后剩下的就是人数最多的士兵。我们最开始的时候直接将第一个元素当作出现次数最多的,这个时候相当于有了一个士兵,所以就有了一条命,计数器要赋值成1.然后进行厮杀,如果某次计数器为0,就表示某国的士兵死完了,换下一个国家的士兵继续厮杀。注意一点我在代码中写的是else if不是if,如果是if就会同时判断,类似于并行的关系。用了elsi fi是类似于递进的,上一个不满足时才会判断下一个

2.除自身以外所有元素的乘积

题目链接 力扣238题

这道题确实有难懂,我暑假琢磨了很久才弄懂
题目要求就是将元素对应位置的地方放置除了它本身外和其他元素的乘积,我们这样思考一下,假如我以每个元素的位置为分界线 将左边部分的乘积按顺序放放在一个数组中,将右边部分的乘积按顺序放在另一个数组中,如果分界线元素在两个端点处,所对应的乘积直接为1,在将这两个数组对应位置相乘即为所求

这样说比较抽象直接画图举例

基于上述思路写出如下代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* nums_return = malloc(numsSize * 4);
    int  left =1;
    int right = 1;
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums_return[i]=left;
        left=left*nums[i];
    }
   
   for(int j=numsSize-1;j>=0;j--) 
   {
    
    nums_return[j]=nums_return[j]*right;
    right=right*nums[j];
   }
    return nums_return;


}

上面为了解题思路更加清晰,特意引入了两个数组来说明这个解题过程,我们发现保存左端元素之积的位置和保存右端元素之积的位置都是一一对应的,所以只用将左端或者右端元素之积保存到一个数组中,在遍历这数组挨个乘上右端或者左端元素之积并且进行保存。左端元素之积叫做前缀之积,右端元素之积叫做后缀之积

3至少是其他数字的两倍

题目链接 力扣747

这道题有很多细节需要处理,要对问题考虑全面才能通过所有的测试用例。首先这个最大的数是要满足它至少是别的每个数的两倍,那么我们思考一下这个数最小应该是多少,最少应该是第二大的数的两倍,那么我们就把这个问题转化成了找数组中最大的数,和第二大的数。这样就比较好处理了

基于上述思路写出如下代码

int dominantIndex(int* nums, int numsSize){
    int flag=-1;
    int frist;
    int second ;
    if(nums[0]>nums[1])
    {
        frist=nums[0];
        second=nums[1];
        flag=0;
    }
    if(nums[0]<nums[1])
    {
        frist=nums[1];
        second=nums[0];
        flag=1;

    }
    if(numsSize==1)
    {
        return 0;
    }
    
   for(int i=2;i<numsSize;i++)
   {   
       if(nums[i]>frist)
       {  second=frist;
           frist=nums[i];
           flag=i;
           
       }
       else 
       {
         second=(second>nums[i]?second:nums[i]);
        
       }
   }
 if(frist>=2*second)
 {
     return flag;
 }
 else
 return -1;
}

我们在找一个数组中最大的元素一般做法就是将数组首元素赋值给变量max,然后遍历数组,这样赋初值的原因就是保证max在这个数组范围内的,不能脱离这个范围。因此我们在赋初值的时候将数组首元素和第二个元素赋值给frist second ,同时用flag记录frist的下标。直接就是进行遍历了,挨个比较交互,但是为什么要加上else 呢?我们在赋值的是直接将数组第一个元素和第二个元素给了两个变量,如果数组最大的元素就在这两个位置之中,first确实是最大元素,但是能保证second就是第二大的元素吗?如果没有elseif 语句,frist不会进入if语句中去,所有根本无法保证second就是第二大的数,所以要有一个else 同时i=2开始循环的,也不担心出现frist和second相同的情况

4.珠玑妙算

题目链接 力扣面试题16.15.

其实这个题目我当时想了好一会才读懂,期间将题目理解错了,导致一直不能过全部测试用例。我当时以为伪猜中就是在对应位置不相等的前提下,guess是solution的子集。实际上不是这样的,对应位置如果相同算猜中,同时这个字符不会再参与伪猜中的比较,同时在对应位置不相等的前提下,对于solution中出现过一次的元素,guess哪怕出现多次也只是按一次计算,但是对应位置不相同的前提下,soloution中某个字符出现多次的话,guess也出现多次实际上要算多次的,这多次的次数是以soloution中的次数为准的,其实对于同一个元素的伪猜中,最多的次数就是两次。因为只有4个位置还要保持对应位置不相等,对于同一个字符来说最多只能出现在两个位置上。

题目要求弄懂了,具体怎么解决呢?我还是采用元素重合问题处理,将guess和solution元素转为下标,很明显这里不能用置数的因为重复的元素可能也会参与计数。于是只能用加加 *** 作了。这个还有个要处理的点就是计数,计数是以solution中的元素为准的,哪怕gusee出现多次也不参与计数。同时元素当作数组下标其实充当了计数功能的出现一次加一次,又因为会有重复元素重复计数问题,直接取guess和solutions所对应数组的元素最小值。同时这样做猜中也是会被计算在内的,最后减去猜中的次数即可

代码如下

int* masterMind(char* solution, char* guess, int* returnSize){
    *returnSize=2;
    int *nums=malloc(sizeof(int)*2);
    int count1=0;
    int count2=0;
    int arr1[26]={0};
    int arr2[26]={0};
    for(int i=0;i<4;i++)
    {
      if(solution[i]==guess[i])
      {
        count1++;
      }
    arr1[solution[i]-65]++;
    arr2[guess[i]-65]++;
    }

for(int j=0;j<26;j++)
{ 
    if(arr1[j]+arr2[j]>=2)
       {
           count2=(arr2[j]>arr1[j]?arr1[j]:arr2[j])+count2;;
       }
}
    
  if(count1==4)
    {
        nums[1]=0;
        nums[0]=4;
    }
  
   if(count2!=0)
    {
        nums[0]=count1;
        nums[1]=count2-count1;
    }

 if(count2==0)
   {
       nums[1]=0;
       nums[0]=0;
   }
   return nums;
}

同时对几种特殊情况判断就是 都猜中了,还有就是连伪猜中都没有。伪猜中都没有,猜中肯定也没有。因为都是小写字母,所以减了65,相当于减了个字符a.

3.移位 *** 作符和位 *** 作符相关问题 1.整数转换

题目链接 力扣面试题05.06整数转换

题目描述 需要改变多少个位才能将a转成b,这题实际上就是要求a和b有多少位是不同的,我们知道异或运算就是相同为0,不同为1,如果我们将a和b异或后,再求出这个异或后的数中有多少位是1,就解决了这个问题了

基于上述思路写出如下代码

int convertInteger(int A, int B){
    int n=A^B;
 int  count =0;
 for(int i=0;i<32;i++)
 {
     if((n>>i)&1)
     {
         count++;
     }
 }
  return count;
}



将a和b异或之后,在右移每一位于1进行与运算,如果该位是1,与运算后也是1,计数器加1,这个移位之后n的值本身没有发生改变,因为这里没有出现赋值行为,在之前的文章中求1的时候有这样的写法 n=n&(n-1),在这道题中是行不通的,因为题目给出的数据测试范围有部分有符号整数会溢出,不能用intl类型,但是题目的形参类型已经固定了,所以只能通过移位来计算的

2.牛客 寻找奇数

题目链接 KS33 寻找奇数

根据题目描述,只有一个数字是出现了奇数次数,其他都偶数次数。找到这个数字。在之前的文章中有介绍不引入第三个变量,利用异或运算交换两个数。异或运算有这样一个特性 a^a=0, a ^ 0=a,0 ^ 0=0,那么一个数经过偶数次异或本身,那么这个数就是0,奇数次异或就还是它本身,那么直接将0和这个数组的每个元素进行异或运算,因为出现偶数次数的数异或后还是0,0与0异或还是0,最后就只有0和和出现奇数次数的数异或,异或的结果就是这个数字。

写出如下代码

#include
int main()
{ int ret=0;
    int n =0;
    scanf("%d",&n);
    int nums[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    for(int j=0;j<n;j++)
    {
        ret=nums[j]^ret;
    }
 
 printf("%d",ret);
}

这题还是比较简单的,可能有时候想不到。我当时也没有马上想到还是题做少了,只要多编程实践并且总结,慢慢就会下笔如有神的。

3.不用加减乘除做加法

题目链接 牛客JZ65 不用加减乘除做加法

这道题猛一看感觉无从下手,其实在数电中可以用异或门和与门实现一个半加器。半加器是实现两个一位二进制数加法运算的器件。实际上就是利用异或运算和与运算,来实现了加法。这些位 *** 作都以2进制为基础来运算的,也就是题目是想要求我们以用2进制加法规则来实现10进制的计算.在实现之前我们先分析一下10进制的加法运算规则.
以5+4为例
05
+
04
________
09
这是没有进位的加法,4 和5除了本身的个位以外其余高位都是0,因为没有进位直接对应位置相加即可。那要是有进位怎么办呢?以9+4为例
9+4=(9+1)+3=10+3.我们先把需要进位的分部先进位,进位以后就还是对应位置直接相加即可。

说完10进制再来说2进制
2进制数除了0就是1,同时缝2进1,
也就是说 1+0 =1;0+1=1;0+0=0;1+1=1 0;
我们先不看进位的部分,就是说
1+0 =1 ; 0+1=1 ;0+0=0;1+1=0;(先不看进位部分),这样的运算结果是不是很像异或,相同为0,不同为1.这对于2进制来说。不需要进位的加法,运算逻辑就是异或.
那进位部分怎么算呢,首先通过上面的例子可以看到只有当对应位置为1时才进位 .那么计算进位时,第一件事就是判断对应位置哪里有1, 同时对于非1的位置不做处理,只是单纯的得到进位部分 ,2进制除了0就是1现在只是处理对应位置的1,剩下的0的保持原样即可,符合这个条件的只有与运算了,因为进位对应数值需要到高位上去,所以需要左移一位。在将进位部分和非进位部分相加即可。

总的来说 如果对应位置没有1就是 a&b==0;相加的结果就是 a^ b ;如果对应位置有1就是 :a&b!=0;相加结果就是a ^ b+a&b<<1;但是进位都是低位往高位进的,对于一串二进制数来说,进位可能不仅仅至进位一次,从低位往高位挨个判断是否有1需要进位.
如果我们定义一个add函数来实现a+b,add(a,b) 实际上 就是求a^b+a&b<<1;这貌似有了一个公式 add(a,b)=add(a ^b,a&b<<1 ),这不就是递推公式吗,递推公式有了,但是递推的出口是什么呢?我们前面说了,如果没有1不就是直接a ^ b;直接对应位置异或就行了。边界条件也有了,就是a和b对应位置有没有1.

基于上述思路代码如下

nt Add(int num1, int num2 ) {
    
     if(num1&num2==0)
     {
         return num1^num2;
     }
    
     else

    return Add(num1^num2,num1&num2<<1) ;
}

在判断边界条件时返回值时num1 ^ num2,在说异或时0 ^a=a,这不相当于a+0=a,所以边界条件还可以改写一下

if(num1=0||num2=0)//加数有一个为0,直接返回另一个加数 符合加法逻辑

但是这道题如果用递归的话,时间复杂度太大了。过不了牛客测试用例。其实基本上所有的递归都可以改写成循环的形式来处理。既然递归的通不过我们直接写循环 既然是循环,那循环条件是什么呢?上面提到了有加数是0直接返回另一个加数,如果num2是0,直接返回num1,如果不是进入循环,从低位往高位判断对应位置是否都是1。这就说明b要不断更新,保证在对应位置没0的时候顺利跳出循环。异或运算实际并不会计算需要进位的位置,它只会保留本位的数值,9+4=10按照异或逻辑类似于只会保留0,1直接舍去。所以直接开始异或运算也不会影响到后续,当两数相加需要进位时,可以把位进后的结果保留,在进行对应位置的不进位的加法运算。这个把位进了的过程就是a&b<<1 类比 9+4的10进制计算,9+4=13 1直接舍去保留3, 9+1=10 把位进了 ,然后 10+(3)=13;每一次进位后进行对应位置的不进位的加法计算。什么时候停下种重复计算呢,毫无疑问就是当没有进位计算的时候,也就是说b中的1消耗完的时候,就是相与之后为0的时候,b的重新赋值既保留了进位后的结果,也保证了能顺利跳出循环


add(int a ,int b)
{
     while(b!=0)      
    { int tem=a^b;  
     b=(a&b<<1);
     a=tem;    
    }
    return a;
}

9+4=13 舍去1 保留3 就是03 ; 9+4=13,舍去3,保留1,就是10;最后就是10+03 =13
对于加法计算实际上是拆分了两部分计算 进位计算 不进位对应位置计算,每一次进位后 都要进行对 对应位置 不进位计算 实际上这也就是加法运算规则。然后重复上述的 *** 作 直到没有进位计算为止

这道题在《剑指offer》上也有出现。力扣上也有这道题但是力扣的题目要求更多一点,牛客上只能算正数,算不了负数,其实算负数就相当于不用四则运算实现了减法,加上一个数的相反数等于减去这个数

力扣题目链接不用四则运算做加法

因为上述代码只能算正整数,正整数的补码与原码相同,负整数的补码为其原码除符号位外的所有位取反后加 1。因为每一次拆分都可以让需要进位的最低位至少左移一位。符号位与数值要一起参与运算,要保证这一点。我们直接将进位的被结果保存到无符号整型中,然后异或完成不进位相加时,将保留的无符号整型赋值给b,来实现负数的相加。

int add(int a,int b)
{ w
    while(b)
    {
        unsigned int tem =(unsigned int)(a&b)<<1;
        a=a^b;
        b=tem;

    }
    return a;
}

这样实现的add函数除了算加法还可以算减法。

4.字符串相关问题 1. 牛客 单词倒排

题目链接 牛客 hj31

在字符串的相关练习的博客中,我提到了并实现reverse(反转)函数,就是将字符串的每个字符逆序,我们看到其实这道题也可以利用反转函数。我们把除了字母和空格外的所有字符都变成空格。在利用reverse函数处理字符串,和单词倒序那道题一样的做法,最后输出即可。这道题和单词倒序基本上没有太大的区别

单词倒序题目链接 牛客倒置字符串
基于上述思路代码如下

#include
#include

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}

int main()
{
	char str[10002] = { 0 };
	int len = 0;
	int i=0; 
	int flag = 0;
	gets(str);
	len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && 
		str[i] <= 'Z' || str[i] == ' ')
			continue;//这个循环停止是为了提高一点效率
		else
		{
			str[i] = ' ';
			//将字符串中除字母和空格以外的位置都替换为空格
		}
	}

	char* start =str ;

	while (*start != ')'char
	{
		*= end ; startwhile
		( *!=end ' ' && * !=end ')' ++;
		{
			end}reverse
		(
		,-start1 end ) ;if(

		* !=')'end = +1
			start ; end else =;
		}
			start reverse end(

	,
	+-str1 str)len;puts()
	;returnstr0;
   } 反转函数的实现我就不多说了,还是想提下我第一次做倒置单词的时候,我曾经将start end同时定义在while循环外部,程序出错了,因为end更新指向时空格时,需要跳出循环,之后的end需要再次进入第二个while中指向下一个单词结尾处的空格或者当end每次跳出第二个循环时必须进行判断,end是因为空格跳出来的还是因为void跳出来的,如果是空格那就end+1,start指向下一个单词的开头,如果不是空格,那就一定是string_revolve,这个时候只用start直接等于end不用加1,因为这说明最后一个单词已经是逆序完了,直接跳出循环即可。,如果在循环外部定义end,之后的end再也不会进入第二个while更新了,所以必须再将下个单词的起始位置start赋给end.因此在不想引入第三个变量的前提下,需要将end定义在while循环内。(
char

*
,

2.左旋字符串

这道题我们通常想到的做法就是 我们将字符串的符串挨个往前挪动一步,同时将字符串首字符保存,挪动完了再将字符串的首字符移动到末尾,重复上述步骤,直到将k个字符挪动完毕

基于上述思路写出如下代码

int ,int)//1将第一个字符保存str//2每个字符都往前挪动//3将第一个字符放在末尾,并且循环往返 kfor( lenint
{  =
	0
	;
	< ;++ i ) char= i * k; ifor(
	 {
		int tem = 0str;
		< -1 j ; ++) j * len(+) j=*
		{
			(+str+j1 ) ;}str * j(+-1
		)
		=;str } len } len%k voidreverse tem(

	  char

 *

这种方法就属于暴力枚举,挨个挪动,如果有7个字符的字符串挪动7次以后就复原了,所以可以用,将这个结果作为循环挪动的次数
除了上述的做法外还有一种方法还是利用到reverse翻转函数,

所以先将字符串分为2部分,先各自逆序翻转,最后整体反转
代码如下


char *)while( left< )char right=
{
	* ;left * right=
	{
		* tem ; *left=
		;left ++ ;right--
		;right } tem}
		leftintmain
		right()

	char

[

] ="ABCD"}
{
	; str//A DCB  BCDAint = { strlen ();
	int len = 2;str//旋转次数reverse
	( k , +-1
	);str//先旋转单个部分 str reverse k(+,+-
	1)str ; k//在旋转后半部分整体 str reverse len ( ,+-1
	);str//旋转整个字符串 str printf len ( "%s",);
	}intfind( strconstchar
*

3.左旋判断


既然左旋都会了,判断就很容易,求出字符串的长度,然后挨个左旋判断,如果是就返回对应的左旋次数。如果有7个字符的字符串,左旋7次都没有匹配上,直接返回0.任选上述两种左旋方式都可以解决这个问题。
那还有其他的方法吗?我们再原有的字符串上基础上再追加它本身,那么它所有的左旋结果都是这个追加后的字符串的子串
ABCDE的所有左旋结果都是 ABCDEABCDE 的子串
这样我们直接用库函数实现即可
代码如下

, char*) char [ src256 ] = find0
{
	} tmp;//用一个辅助空间将原字符串做成两倍原字符串strcpy ( { , ); //先拷贝一遍
	char*tmp= srcstrcat( ,
	);ret//再连接一遍 if(tmp!= srcNULL) return
	1;ret}return0
	{
	  ;  }[+++]
	[+++]
  esle 
  [+++] [+++][+++]
[+++]

其实还可以直接在原字符串上直接追加它本身在用strstr查找匹配,但是会改变原字符串内容。

3.总结

1.关于元素重合问题,将元素转为数组下标,然后直接置数。注意一点数组的元素个数是决定了数组的下标值的范围,数组下标最大值一定是要大于等于元素最大值的。
2.逻辑运算和位运算,需要总结并且不断练习实践。
3.字符串问题,逆序反转函数很有用,做题以前可以先观察输入和输出之间有没有联系。
4.编程需要多实践,做的题多了,思维就会更加开阔。同时要及时复盘总结。
5.以上的解法都没有用到特别高深的算法和复杂的数据结构。可能处理方式比较巧妙一点,但是我觉得不要为自己懒刷题找借口,认为自己数据结构什么都不会,就不能去做力扣题和牛客题。只要肯学,肯练。一切都会慢慢好起来的。这句话是对我自己说的。显然我现在也还不会数据结构,但是我相信再寒假之前一定会有长进的!
6.以上解法不一定是最优解,只是我个人的浅薄见解,内容如有问题欢迎指正!

)
File: /www/wwwroot/outofmemory.cn/tmp/route_read.php, Line: 126, InsideLink()
File: /www/wwwroot/outofmemory.cn/tmp/index.inc.php, Line: 165, include(/www/wwwroot/outofmemory.cn/tmp/route_read.php)
File: /www/wwwroot/outofmemory.cn/index.php, Line: 30, include(/www/wwwroot/outofmemory.cn/tmp/index.inc.php)
Error[8]: Undefined offset: 1508, File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 121
File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 473, decode(

文章目录


前言

编程是需要不断练习实践的,所以刷题是很有必要的。但是不能盲目的刷题,要对做过的题题目进行总结复盘。以下是我对暑假期间做过的题目的部分总结,做个简单的记录。


1、重合元素问题 1.力扣645 错误的集合

题目链接力扣645

题目的要求就是在1到n中查找重复的数字和丢失的数字,我们先这样思考一下假如集合中1到n没有发生丢失,1到n就是自然数顺序排列,这样和我们数组的下标是和契合的,数组的下标就是0到n-1的自然数顺序数列,那我们将集合的每个元素减1当作另一个数组的下标来使用,将这个数组的所有的元素的元素初始化都置为0,再用集合中元素当作此数组下标,进行遍历加1,因为有重复的数据,所以数组中某个位置处肯定是2,找到这个2的位置,也就是数组的下标,这个下标就是重复的数据,因为丢失了某个数据。也就是说数组的某个位置没有加1,还是初始值0,找到0所对应的下标就是丢失的数据。

基于上述思路写出如下代码

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    *returnSize=2;
    int* arr1;
    arr1=(int*)malloc(sizeof(int)*2);
    int* arr2;
    arr2=calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]-1]++;
    }
    for(int j=0;j<numsSize;j++)
    {
        if(arr2[j]==2)
          {
              arr1[0]=j+1;
          }
          else if(arr2[j]==0)
          {
              arr1[1]=j+1;
          }
    }
  return arr1;
}

在这里说一下,力扣是接口型oj,,函数的返回值和参数都已经写好固定了,只要完善这个函数即可。这个代码中calloc函数是动态分配空间,并且将分配的空间的元素都置为0,有类似于初始化的作用,malloc函数只是分配空间.
因为数组的下标是从0开始的,所以将集合中元素当作下标的时候减1,同时在找丢失的数据和重复的数据的时候需要再把这个1加回来,当然也可以多申请一个空间,这样就不用加1减1了,但是要注意集合的下标不要越界。
arr2[nums[i]-1]这是十分最主要的一步。
这道题其实就是处理元素重合问题,处理这种问题,将要处理的集合元素转化为另一个数组的下标是一种很有用的方法。

2.力扣349求两个数的交集

题目链接 力扣349题

这道题也是重和的问题,还可以利用上述的方法。将集合的元素转化成数组的下标,只不过不用加1,我们直接将数组元素置为一个数,因为要处理两个集合,这两个集合的元素不确定出现多少次,比如2在集合1和集合2中重复3次,3在集合1和集合2出现了1次,如果还是采用加加的 *** 作 不好通过数组的元素的值判断重复的元素,直接将给数组元素置数赋值,就可以很好的处理了
基于上述思路,写出如下代码

int* intersection(int* nums1, int nums1Size, int* nums2,
 int nums2Size, int* returnSize)
 {
*returnSize=0;
int* arr=calloc(10001,sizeof(int));
int* return_arr=malloc(10001*sizeof(int));
for(int i=0;i<nums1Size;i++)
{
    arr[nums1[i]]=1;
   
 }
   
 for(int j=0;j<nums2Size;j++)
 {
     if(arr[nums2[j]]==1)
     {
         arr[nums2[j]]=2;
     }
 }

 for(int k=0;k<1001;k++)
 {
     if(arr[k]==2)
     {
         return_arr[*returnSize]=k;
         *returnSize+=1;
     }
 }
 return return_arr;

}

我们先将集合1元素当作数组下标,并且将数组元素置为1,接着再将集合2的元素当作数组下标,再里面找1,如果找到了1,这个位置的下标就是两个集合中相同的元素,那么为了找到这个下标,直接将其置为2,就一步就相当于对数组该位置进行标记。最后在数组中找到2对应的下标,这个下标就是重复的元素,因为我没有减1,直接用的集和元素,所以在下标就是重复元素,就不用再去减1了。同时题目给了集合元素个数范围,为了避免空间不够,我就申请了10001*4字节的空间

3. 牛客HJ10 字符个数统计

题目链接字符统计个数

这道题还是元素重和问题,还是老方法,将字符串每个字符转成另一个数组的下标来处理。因为题目说了多个相同只算一次,同时字符串也没有空格。还是直接数组元素置数。

代码如下

#include
int word_count(char* str, int len)
{
    int arr[127] = { 0 };
    int count = 0;
    for (int i = 0; i < len; i++)
    {
        arr[str[i]] = 1;
    }
    for (int i = 0; i < 127; i++)
    {
        if (arr[i] == 1)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    char str[5001] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int ret = word_count(str, len);
    printf("%d", ret);
    return 0;
}

之所以将数组的个数设置成127因为字符对应的ASCII值最大为127,也就是字符串字符作为数组下标时最大只能到127.将数组元素置为1,在判断如果数组元素时1,计数器加1,这样置数赋值,就算有重复的字符也只计算一次。

4.力扣448找到数组中消失的数字

题目链接 力扣448题

这题和第一道例题特别相似,题目还是关于元素重合问题,这个找没有出现的的元素,第一道例题是找丢失的元素,很明显题目是换了个马甲,还是老方法处理转成数组下标然后置数赋值

基于以上思路,写出如下代码

int* findDisappearedNumbers(int* nums, int numsSize,int* returnSize)
{
     *returnSize=0;
    int* arr1=(int*)malloc(sizeof(int)*(numsSize+1));
    int* arr2=calloc((numsSize+1),sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]]=1;
    }
    for(int j=1;j<numsSize+1;j++)
    {
        if(arr2[j]==0)
          {
              arr1[*returnSize]=j;
              *returnSize+=1;
          }
          
    }
  return arr1;
}

利用calloc函数将开辟的空间中的元素初始化为0.将集合的元素转化为数组下标,这次我直接将集合中的元素转为下标没有减1,然后置1进行判断找到还是0的元素下标,但是要注意一点就是由于集合元素转为数组下标时没有减1,开辟空间是需要比集合的元素个数多一个的。因为数组的元素个数是和决定了数组元素下标最大值的,数组下标必须要满足大于等于集合中的最大元素的。

2.杂题汇总 1.摩尔投票法

题目链接 力扣169

题目描述,集合中一定有一个出现次数的最多的元素,找出来这个元素。这道题用摩尔投票法可以轻松解决。什么是摩尔投票法,这里先不说卖个关子,我们直接看代码分析

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

摩尔投票法,听着名字挺唬人的。按照我自己理解就是一换一厮杀法 求解数组中最多元素问题 。假如在3国时,蜀吴各有两千士兵,现在魏国有1万士兵,现在3国进行决战,魏蜀吴的士兵每个士兵都只能一换一同归于尽,那么最后打赢的一定是魏国。因为3方士兵只能一换一,魏国士兵最多。这个厮杀的过程就是在找出现次数最多的元素,为了模拟这个厮杀过程 可以用一个计数器来表示,将不同的元素想象成不同国家的士兵 ,计数器来表示生命值 ,遇到相同士兵计数器就加一, 表示结成阵营, 不同的就减一 ,表示一换一杀死了一个士兵。一旦计数器为0,就换下一个兵种,最后剩下的就是人数最多的士兵。我们最开始的时候直接将第一个元素当作出现次数最多的,这个时候相当于有了一个士兵,所以就有了一条命,计数器要赋值成1.然后进行厮杀,如果某次计数器为0,就表示某国的士兵死完了,换下一个国家的士兵继续厮杀。注意一点我在代码中写的是else if不是if,如果是if就会同时判断,类似于并行的关系。用了elsi fi是类似于递进的,上一个不满足时才会判断下一个

2.除自身以外所有元素的乘积

题目链接 力扣238题

这道题确实有难懂,我暑假琢磨了很久才弄懂
题目要求就是将元素对应位置的地方放置除了它本身外和其他元素的乘积,我们这样思考一下,假如我以每个元素的位置为分界线 将左边部分的乘积按顺序放放在一个数组中,将右边部分的乘积按顺序放在另一个数组中,如果分界线元素在两个端点处,所对应的乘积直接为1,在将这两个数组对应位置相乘即为所求

这样说比较抽象直接画图举例

基于上述思路写出如下代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* nums_return = malloc(numsSize * 4);
    int  left =1;
    int right = 1;
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums_return[i]=left;
        left=left*nums[i];
    }
   
   for(int j=numsSize-1;j>=0;j--) 
   {
    
    nums_return[j]=nums_return[j]*right;
    right=right*nums[j];
   }
    return nums_return;


}

上面为了解题思路更加清晰,特意引入了两个数组来说明这个解题过程,我们发现保存左端元素之积的位置和保存右端元素之积的位置都是一一对应的,所以只用将左端或者右端元素之积保存到一个数组中,在遍历这数组挨个乘上右端或者左端元素之积并且进行保存。左端元素之积叫做前缀之积,右端元素之积叫做后缀之积

3至少是其他数字的两倍

题目链接 力扣747

这道题有很多细节需要处理,要对问题考虑全面才能通过所有的测试用例。首先这个最大的数是要满足它至少是别的每个数的两倍,那么我们思考一下这个数最小应该是多少,最少应该是第二大的数的两倍,那么我们就把这个问题转化成了找数组中最大的数,和第二大的数。这样就比较好处理了

基于上述思路写出如下代码

int dominantIndex(int* nums, int numsSize){
    int flag=-1;
    int frist;
    int second ;
    if(nums[0]>nums[1])
    {
        frist=nums[0];
        second=nums[1];
        flag=0;
    }
    if(nums[0]<nums[1])
    {
        frist=nums[1];
        second=nums[0];
        flag=1;

    }
    if(numsSize==1)
    {
        return 0;
    }
    
   for(int i=2;i<numsSize;i++)
   {   
       if(nums[i]>frist)
       {  second=frist;
           frist=nums[i];
           flag=i;
           
       }
       else 
       {
         second=(second>nums[i]?second:nums[i]);
        
       }
   }
 if(frist>=2*second)
 {
     return flag;
 }
 else
 return -1;
}

我们在找一个数组中最大的元素一般做法就是将数组首元素赋值给变量max,然后遍历数组,这样赋初值的原因就是保证max在这个数组范围内的,不能脱离这个范围。因此我们在赋初值的时候将数组首元素和第二个元素赋值给frist second ,同时用flag记录frist的下标。直接就是进行遍历了,挨个比较交互,但是为什么要加上else 呢?我们在赋值的是直接将数组第一个元素和第二个元素给了两个变量,如果数组最大的元素就在这两个位置之中,first确实是最大元素,但是能保证second就是第二大的元素吗?如果没有elseif 语句,frist不会进入if语句中去,所有根本无法保证second就是第二大的数,所以要有一个else 同时i=2开始循环的,也不担心出现frist和second相同的情况

4.珠玑妙算

题目链接 力扣面试题16.15.

其实这个题目我当时想了好一会才读懂,期间将题目理解错了,导致一直不能过全部测试用例。我当时以为伪猜中就是在对应位置不相等的前提下,guess是solution的子集。实际上不是这样的,对应位置如果相同算猜中,同时这个字符不会再参与伪猜中的比较,同时在对应位置不相等的前提下,对于solution中出现过一次的元素,guess哪怕出现多次也只是按一次计算,但是对应位置不相同的前提下,soloution中某个字符出现多次的话,guess也出现多次实际上要算多次的,这多次的次数是以soloution中的次数为准的,其实对于同一个元素的伪猜中,最多的次数就是两次。因为只有4个位置还要保持对应位置不相等,对于同一个字符来说最多只能出现在两个位置上。

题目要求弄懂了,具体怎么解决呢?我还是采用元素重合问题处理,将guess和solution元素转为下标,很明显这里不能用置数的因为重复的元素可能也会参与计数。于是只能用加加 *** 作了。这个还有个要处理的点就是计数,计数是以solution中的元素为准的,哪怕gusee出现多次也不参与计数。同时元素当作数组下标其实充当了计数功能的出现一次加一次,又因为会有重复元素重复计数问题,直接取guess和solutions所对应数组的元素最小值。同时这样做猜中也是会被计算在内的,最后减去猜中的次数即可

代码如下

int* masterMind(char* solution, char* guess, int* returnSize){
    *returnSize=2;
    int *nums=malloc(sizeof(int)*2);
    int count1=0;
    int count2=0;
    int arr1[26]={0};
    int arr2[26]={0};
    for(int i=0;i<4;i++)
    {
      if(solution[i]==guess[i])
      {
        count1++;
      }
    arr1[solution[i]-65]++;
    arr2[guess[i]-65]++;
    }

for(int j=0;j<26;j++)
{ 
    if(arr1[j]+arr2[j]>=2)
       {
           count2=(arr2[j]>arr1[j]?arr1[j]:arr2[j])+count2;;
       }
}
    
  if(count1==4)
    {
        nums[1]=0;
        nums[0]=4;
    }
  
   if(count2!=0)
    {
        nums[0]=count1;
        nums[1]=count2-count1;
    }

 if(count2==0)
   {
       nums[1]=0;
       nums[0]=0;
   }
   return nums;
}

同时对几种特殊情况判断就是 都猜中了,还有就是连伪猜中都没有。伪猜中都没有,猜中肯定也没有。因为都是小写字母,所以减了65,相当于减了个字符a.

3.移位 *** 作符和位 *** 作符相关问题 1.整数转换

题目链接 力扣面试题05.06整数转换

题目描述 需要改变多少个位才能将a转成b,这题实际上就是要求a和b有多少位是不同的,我们知道异或运算就是相同为0,不同为1,如果我们将a和b异或后,再求出这个异或后的数中有多少位是1,就解决了这个问题了

基于上述思路写出如下代码

int convertInteger(int A, int B){
    int n=A^B;
 int  count =0;
 for(int i=0;i<32;i++)
 {
     if((n>>i)&1)
     {
         count++;
     }
 }
  return count;
}



将a和b异或之后,在右移每一位于1进行与运算,如果该位是1,与运算后也是1,计数器加1,这个移位之后n的值本身没有发生改变,因为这里没有出现赋值行为,在之前的文章中求1的时候有这样的写法 n=n&(n-1),在这道题中是行不通的,因为题目给出的数据测试范围有部分有符号整数会溢出,不能用intl类型,但是题目的形参类型已经固定了,所以只能通过移位来计算的

2.牛客 寻找奇数

题目链接 KS33 寻找奇数

根据题目描述,只有一个数字是出现了奇数次数,其他都偶数次数。找到这个数字。在之前的文章中有介绍不引入第三个变量,利用异或运算交换两个数。异或运算有这样一个特性 a^a=0, a ^ 0=a,0 ^ 0=0,那么一个数经过偶数次异或本身,那么这个数就是0,奇数次异或就还是它本身,那么直接将0和这个数组的每个元素进行异或运算,因为出现偶数次数的数异或后还是0,0与0异或还是0,最后就只有0和和出现奇数次数的数异或,异或的结果就是这个数字。

写出如下代码

#include
int main()
{ int ret=0;
    int n =0;
    scanf("%d",&n);
    int nums[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    for(int j=0;j<n;j++)
    {
        ret=nums[j]^ret;
    }
 
 printf("%d",ret);
}

这题还是比较简单的,可能有时候想不到。我当时也没有马上想到还是题做少了,只要多编程实践并且总结,慢慢就会下笔如有神的。

3.不用加减乘除做加法

题目链接 牛客JZ65 不用加减乘除做加法

这道题猛一看感觉无从下手,其实在数电中可以用异或门和与门实现一个半加器。半加器是实现两个一位二进制数加法运算的器件。实际上就是利用异或运算和与运算,来实现了加法。这些位 *** 作都以2进制为基础来运算的,也就是题目是想要求我们以用2进制加法规则来实现10进制的计算.在实现之前我们先分析一下10进制的加法运算规则.
以5+4为例
05
+
04
________
09
这是没有进位的加法,4 和5除了本身的个位以外其余高位都是0,因为没有进位直接对应位置相加即可。那要是有进位怎么办呢?以9+4为例
9+4=(9+1)+3=10+3.我们先把需要进位的分部先进位,进位以后就还是对应位置直接相加即可。

说完10进制再来说2进制
2进制数除了0就是1,同时缝2进1,
也就是说 1+0 =1;0+1=1;0+0=0;1+1=1 0;
我们先不看进位的部分,就是说
1+0 =1 ; 0+1=1 ;0+0=0;1+1=0;(先不看进位部分),这样的运算结果是不是很像异或,相同为0,不同为1.这对于2进制来说。不需要进位的加法,运算逻辑就是异或.
那进位部分怎么算呢,首先通过上面的例子可以看到只有当对应位置为1时才进位 .那么计算进位时,第一件事就是判断对应位置哪里有1, 同时对于非1的位置不做处理,只是单纯的得到进位部分 ,2进制除了0就是1现在只是处理对应位置的1,剩下的0的保持原样即可,符合这个条件的只有与运算了,因为进位对应数值需要到高位上去,所以需要左移一位。在将进位部分和非进位部分相加即可。

总的来说 如果对应位置没有1就是 a&b==0;相加的结果就是 a^ b ;如果对应位置有1就是 :a&b!=0;相加结果就是a ^ b+a&b<<1;但是进位都是低位往高位进的,对于一串二进制数来说,进位可能不仅仅至进位一次,从低位往高位挨个判断是否有1需要进位.
如果我们定义一个add函数来实现a+b,add(a,b) 实际上 就是求a^b+a&b<<1;这貌似有了一个公式 add(a,b)=add(a ^b,a&b<<1 ),这不就是递推公式吗,递推公式有了,但是递推的出口是什么呢?我们前面说了,如果没有1不就是直接a ^ b;直接对应位置异或就行了。边界条件也有了,就是a和b对应位置有没有1.

基于上述思路代码如下

nt Add(int num1, int num2 ) {
    
     if(num1&num2==0)
     {
         return num1^num2;
     }
    
     else

    return Add(num1^num2,num1&num2<<1) ;
}

在判断边界条件时返回值时num1 ^ num2,在说异或时0 ^a=a,这不相当于a+0=a,所以边界条件还可以改写一下

if(num1=0||num2=0)//加数有一个为0,直接返回另一个加数 符合加法逻辑

但是这道题如果用递归的话,时间复杂度太大了。过不了牛客测试用例。其实基本上所有的递归都可以改写成循环的形式来处理。既然递归的通不过我们直接写循环 既然是循环,那循环条件是什么呢?上面提到了有加数是0直接返回另一个加数,如果num2是0,直接返回num1,如果不是进入循环,从低位往高位判断对应位置是否都是1。这就说明b要不断更新,保证在对应位置没0的时候顺利跳出循环。异或运算实际并不会计算需要进位的位置,它只会保留本位的数值,9+4=10按照异或逻辑类似于只会保留0,1直接舍去。所以直接开始异或运算也不会影响到后续,当两数相加需要进位时,可以把位进后的结果保留,在进行对应位置的不进位的加法运算。这个把位进了的过程就是a&b<<1 类比 9+4的10进制计算,9+4=13 1直接舍去保留3, 9+1=10 把位进了 ,然后 10+(3)=13;每一次进位后进行对应位置的不进位的加法计算。什么时候停下种重复计算呢,毫无疑问就是当没有进位计算的时候,也就是说b中的1消耗完的时候,就是相与之后为0的时候,b的重新赋值既保留了进位后的结果,也保证了能顺利跳出循环


add(int a ,int b)
{
     while(b!=0)      
    { int tem=a^b;  
     b=(a&b<<1);
     a=tem;    
    }
    return a;
}

9+4=13 舍去1 保留3 就是03 ; 9+4=13,舍去3,保留1,就是10;最后就是10+03 =13
对于加法计算实际上是拆分了两部分计算 进位计算 不进位对应位置计算,每一次进位后 都要进行对 对应位置 不进位计算 实际上这也就是加法运算规则。然后重复上述的 *** 作 直到没有进位计算为止

这道题在《剑指offer》上也有出现。力扣上也有这道题但是力扣的题目要求更多一点,牛客上只能算正数,算不了负数,其实算负数就相当于不用四则运算实现了减法,加上一个数的相反数等于减去这个数

力扣题目链接不用四则运算做加法

因为上述代码只能算正整数,正整数的补码与原码相同,负整数的补码为其原码除符号位外的所有位取反后加 1。因为每一次拆分都可以让需要进位的最低位至少左移一位。符号位与数值要一起参与运算,要保证这一点。我们直接将进位的被结果保存到无符号整型中,然后异或完成不进位相加时,将保留的无符号整型赋值给b,来实现负数的相加。

int add(int a,int b)
{ w
    while(b)
    {
        unsigned int tem =(unsigned int)(a&b)<<1;
        a=a^b;
        b=tem;

    }
    return a;
}

这样实现的add函数除了算加法还可以算减法。

4.字符串相关问题 1. 牛客 单词倒排

题目链接 牛客 hj31

在字符串的相关练习的博客中,我提到了并实现reverse(反转)函数,就是将字符串的每个字符逆序,我们看到其实这道题也可以利用反转函数。我们把除了字母和空格外的所有字符都变成空格。在利用reverse函数处理字符串,和单词倒序那道题一样的做法,最后输出即可。这道题和单词倒序基本上没有太大的区别

单词倒序题目链接 牛客倒置字符串
基于上述思路代码如下

#include
#include

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}

int main()
{
	char str[10002] = { 0 };
	int len = 0;
	int i=0; 
	int flag = 0;
	gets(str);
	len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && 
		str[i] <= 'Z' || str[i] == ' ')
			continue;//这个循环停止是为了提高一点效率
		else
		{
			str[i] = ' ';
			//将字符串中除字母和空格以外的位置都替换为空格
		}
	}

	char* start =str ;

	while (*start != ')'char
	{
		*= end ; startwhile
		( *!=end ' ' && * !=end ')' ++;
		{
			end}reverse
		(
		,-start1 end ) ;if(

		* !=')'end = +1
			start ; end else =;
		}
			start reverse end(

	,
	+-str1 str)len;puts()
	;returnstr0;
   } 反转函数的实现我就不多说了,还是想提下我第一次做倒置单词的时候,我曾经将start end同时定义在while循环外部,程序出错了,因为end更新指向时空格时,需要跳出循环,之后的end需要再次进入第二个while中指向下一个单词结尾处的空格或者当end每次跳出第二个循环时必须进行判断,end是因为空格跳出来的还是因为void跳出来的,如果是空格那就end+1,start指向下一个单词的开头,如果不是空格,那就一定是string_revolve,这个时候只用start直接等于end不用加1,因为这说明最后一个单词已经是逆序完了,直接跳出循环即可。,如果在循环外部定义end,之后的end再也不会进入第二个while更新了,所以必须再将下个单词的起始位置start赋给end.因此在不想引入第三个变量的前提下,需要将end定义在while循环内。(
char

*
,

2.左旋字符串

这道题我们通常想到的做法就是 我们将字符串的符串挨个往前挪动一步,同时将字符串首字符保存,挪动完了再将字符串的首字符移动到末尾,重复上述步骤,直到将k个字符挪动完毕

基于上述思路写出如下代码

int ,int)//1将第一个字符保存str//2每个字符都往前挪动//3将第一个字符放在末尾,并且循环往返 kfor( lenint
{  =
	0
	;
	< ;++ i ) char= i * k; ifor(
	 {
		int tem = 0str;
		< -1 j ; ++) j * len(+) j=*
		{
			(+str+j1 ) ;}str * j(+-1
		)
		=;str } len } len%k voidreverse tem(

	  char

 *

这种方法就属于暴力枚举,挨个挪动,如果有7个字符的字符串挪动7次以后就复原了,所以可以用,将这个结果作为循环挪动的次数
除了上述的做法外还有一种方法还是利用到reverse翻转函数,

所以先将字符串分为2部分,先各自逆序翻转,最后整体反转
代码如下


char *)while( left< )char right=
{
	* ;left * right=
	{
		* tem ; *left=
		;left ++ ;right--
		;right } tem}
		leftintmain
		right()

	char

[

] ="ABCD"}
{
	; str//A DCB  BCDAint = { strlen ();
	int len = 2;str//旋转次数reverse
	( k , +-1
	);str//先旋转单个部分 str reverse k(+,+-
	1)str ; k//在旋转后半部分整体 str reverse len ( ,+-1
	);str//旋转整个字符串 str printf len ( "%s",);
	}intfind( strconstchar
*

3.左旋判断


既然左旋都会了,判断就很容易,求出字符串的长度,然后挨个左旋判断,如果是就返回对应的左旋次数。如果有7个字符的字符串,左旋7次都没有匹配上,直接返回0.任选上述两种左旋方式都可以解决这个问题。
那还有其他的方法吗?我们再原有的字符串上基础上再追加它本身,那么它所有的左旋结果都是这个追加后的字符串的子串
ABCDE的所有左旋结果都是 ABCDEABCDE 的子串
这样我们直接用库函数实现即可
代码如下

, char*) char [ src256 ] = find0
{
	} tmp;//用一个辅助空间将原字符串做成两倍原字符串strcpy ( { , ); //先拷贝一遍
	char*tmp= srcstrcat( ,
	);ret//再连接一遍 if(tmp!= srcNULL) return
	1;ret}return0
	{
	  ;  }
	[+++]
  esle 
  [+++] [+++][+++]
[+++]

其实还可以直接在原字符串上直接追加它本身在用strstr查找匹配,但是会改变原字符串内容。

3.总结

1.关于元素重合问题,将元素转为数组下标,然后直接置数。注意一点数组的元素个数是决定了数组的下标值的范围,数组下标最大值一定是要大于等于元素最大值的。
2.逻辑运算和位运算,需要总结并且不断练习实践。
3.字符串问题,逆序反转函数很有用,做题以前可以先观察输入和输出之间有没有联系。
4.编程需要多实践,做的题多了,思维就会更加开阔。同时要及时复盘总结。
5.以上的解法都没有用到特别高深的算法和复杂的数据结构。可能处理方式比较巧妙一点,但是我觉得不要为自己懒刷题找借口,认为自己数据结构什么都不会,就不能去做力扣题和牛客题。只要肯学,肯练。一切都会慢慢好起来的。这句话是对我自己说的。显然我现在也还不会数据结构,但是我相信再寒假之前一定会有长进的!
6.以上解法不一定是最优解,只是我个人的浅薄见解,内容如有问题欢迎指正!

)
File: /www/wwwroot/outofmemory.cn/tmp/route_read.php, Line: 126, InsideLink()
File: /www/wwwroot/outofmemory.cn/tmp/index.inc.php, Line: 165, include(/www/wwwroot/outofmemory.cn/tmp/route_read.php)
File: /www/wwwroot/outofmemory.cn/index.php, Line: 30, include(/www/wwwroot/outofmemory.cn/tmp/index.inc.php)
Error[8]: Undefined offset: 1509, File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 121
File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 473, decode(

文章目录


前言

编程是需要不断练习实践的,所以刷题是很有必要的。但是不能盲目的刷题,要对做过的题题目进行总结复盘。以下是我对暑假期间做过的题目的部分总结,做个简单的记录。


1、重合元素问题 1.力扣645 错误的集合

题目链接力扣645

题目的要求就是在1到n中查找重复的数字和丢失的数字,我们先这样思考一下假如集合中1到n没有发生丢失,1到n就是自然数顺序排列,这样和我们数组的下标是和契合的,数组的下标就是0到n-1的自然数顺序数列,那我们将集合的每个元素减1当作另一个数组的下标来使用,将这个数组的所有的元素的元素初始化都置为0,再用集合中元素当作此数组下标,进行遍历加1,因为有重复的数据,所以数组中某个位置处肯定是2,找到这个2的位置,也就是数组的下标,这个下标就是重复的数据,因为丢失了某个数据。也就是说数组的某个位置没有加1,还是初始值0,找到0所对应的下标就是丢失的数据。

基于上述思路写出如下代码

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    *returnSize=2;
    int* arr1;
    arr1=(int*)malloc(sizeof(int)*2);
    int* arr2;
    arr2=calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]-1]++;
    }
    for(int j=0;j<numsSize;j++)
    {
        if(arr2[j]==2)
          {
              arr1[0]=j+1;
          }
          else if(arr2[j]==0)
          {
              arr1[1]=j+1;
          }
    }
  return arr1;
}

在这里说一下,力扣是接口型oj,,函数的返回值和参数都已经写好固定了,只要完善这个函数即可。这个代码中calloc函数是动态分配空间,并且将分配的空间的元素都置为0,有类似于初始化的作用,malloc函数只是分配空间.
因为数组的下标是从0开始的,所以将集合中元素当作下标的时候减1,同时在找丢失的数据和重复的数据的时候需要再把这个1加回来,当然也可以多申请一个空间,这样就不用加1减1了,但是要注意集合的下标不要越界。
arr2[nums[i]-1]这是十分最主要的一步。
这道题其实就是处理元素重合问题,处理这种问题,将要处理的集合元素转化为另一个数组的下标是一种很有用的方法。

2.力扣349求两个数的交集

题目链接 力扣349题

这道题也是重和的问题,还可以利用上述的方法。将集合的元素转化成数组的下标,只不过不用加1,我们直接将数组元素置为一个数,因为要处理两个集合,这两个集合的元素不确定出现多少次,比如2在集合1和集合2中重复3次,3在集合1和集合2出现了1次,如果还是采用加加的 *** 作 不好通过数组的元素的值判断重复的元素,直接将给数组元素置数赋值,就可以很好的处理了
基于上述思路,写出如下代码

int* intersection(int* nums1, int nums1Size, int* nums2,
 int nums2Size, int* returnSize)
 {
*returnSize=0;
int* arr=calloc(10001,sizeof(int));
int* return_arr=malloc(10001*sizeof(int));
for(int i=0;i<nums1Size;i++)
{
    arr[nums1[i]]=1;
   
 }
   
 for(int j=0;j<nums2Size;j++)
 {
     if(arr[nums2[j]]==1)
     {
         arr[nums2[j]]=2;
     }
 }

 for(int k=0;k<1001;k++)
 {
     if(arr[k]==2)
     {
         return_arr[*returnSize]=k;
         *returnSize+=1;
     }
 }
 return return_arr;

}

我们先将集合1元素当作数组下标,并且将数组元素置为1,接着再将集合2的元素当作数组下标,再里面找1,如果找到了1,这个位置的下标就是两个集合中相同的元素,那么为了找到这个下标,直接将其置为2,就一步就相当于对数组该位置进行标记。最后在数组中找到2对应的下标,这个下标就是重复的元素,因为我没有减1,直接用的集和元素,所以在下标就是重复元素,就不用再去减1了。同时题目给了集合元素个数范围,为了避免空间不够,我就申请了10001*4字节的空间

3. 牛客HJ10 字符个数统计

题目链接字符统计个数

这道题还是元素重和问题,还是老方法,将字符串每个字符转成另一个数组的下标来处理。因为题目说了多个相同只算一次,同时字符串也没有空格。还是直接数组元素置数。

代码如下

#include
int word_count(char* str, int len)
{
    int arr[127] = { 0 };
    int count = 0;
    for (int i = 0; i < len; i++)
    {
        arr[str[i]] = 1;
    }
    for (int i = 0; i < 127; i++)
    {
        if (arr[i] == 1)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    char str[5001] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int ret = word_count(str, len);
    printf("%d", ret);
    return 0;
}

之所以将数组的个数设置成127因为字符对应的ASCII值最大为127,也就是字符串字符作为数组下标时最大只能到127.将数组元素置为1,在判断如果数组元素时1,计数器加1,这样置数赋值,就算有重复的字符也只计算一次。

4.力扣448找到数组中消失的数字

题目链接 力扣448题

这题和第一道例题特别相似,题目还是关于元素重合问题,这个找没有出现的的元素,第一道例题是找丢失的元素,很明显题目是换了个马甲,还是老方法处理转成数组下标然后置数赋值

基于以上思路,写出如下代码

int* findDisappearedNumbers(int* nums, int numsSize,int* returnSize)
{
     *returnSize=0;
    int* arr1=(int*)malloc(sizeof(int)*(numsSize+1));
    int* arr2=calloc((numsSize+1),sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]]=1;
    }
    for(int j=1;j<numsSize+1;j++)
    {
        if(arr2[j]==0)
          {
              arr1[*returnSize]=j;
              *returnSize+=1;
          }
          
    }
  return arr1;
}

利用calloc函数将开辟的空间中的元素初始化为0.将集合的元素转化为数组下标,这次我直接将集合中的元素转为下标没有减1,然后置1进行判断找到还是0的元素下标,但是要注意一点就是由于集合元素转为数组下标时没有减1,开辟空间是需要比集合的元素个数多一个的。因为数组的元素个数是和决定了数组元素下标最大值的,数组下标必须要满足大于等于集合中的最大元素的。

2.杂题汇总 1.摩尔投票法

题目链接 力扣169

题目描述,集合中一定有一个出现次数的最多的元素,找出来这个元素。这道题用摩尔投票法可以轻松解决。什么是摩尔投票法,这里先不说卖个关子,我们直接看代码分析

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

摩尔投票法,听着名字挺唬人的。按照我自己理解就是一换一厮杀法 求解数组中最多元素问题 。假如在3国时,蜀吴各有两千士兵,现在魏国有1万士兵,现在3国进行决战,魏蜀吴的士兵每个士兵都只能一换一同归于尽,那么最后打赢的一定是魏国。因为3方士兵只能一换一,魏国士兵最多。这个厮杀的过程就是在找出现次数最多的元素,为了模拟这个厮杀过程 可以用一个计数器来表示,将不同的元素想象成不同国家的士兵 ,计数器来表示生命值 ,遇到相同士兵计数器就加一, 表示结成阵营, 不同的就减一 ,表示一换一杀死了一个士兵。一旦计数器为0,就换下一个兵种,最后剩下的就是人数最多的士兵。我们最开始的时候直接将第一个元素当作出现次数最多的,这个时候相当于有了一个士兵,所以就有了一条命,计数器要赋值成1.然后进行厮杀,如果某次计数器为0,就表示某国的士兵死完了,换下一个国家的士兵继续厮杀。注意一点我在代码中写的是else if不是if,如果是if就会同时判断,类似于并行的关系。用了elsi fi是类似于递进的,上一个不满足时才会判断下一个

2.除自身以外所有元素的乘积

题目链接 力扣238题

这道题确实有难懂,我暑假琢磨了很久才弄懂
题目要求就是将元素对应位置的地方放置除了它本身外和其他元素的乘积,我们这样思考一下,假如我以每个元素的位置为分界线 将左边部分的乘积按顺序放放在一个数组中,将右边部分的乘积按顺序放在另一个数组中,如果分界线元素在两个端点处,所对应的乘积直接为1,在将这两个数组对应位置相乘即为所求

这样说比较抽象直接画图举例

基于上述思路写出如下代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* nums_return = malloc(numsSize * 4);
    int  left =1;
    int right = 1;
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums_return[i]=left;
        left=left*nums[i];
    }
   
   for(int j=numsSize-1;j>=0;j--) 
   {
    
    nums_return[j]=nums_return[j]*right;
    right=right*nums[j];
   }
    return nums_return;


}

上面为了解题思路更加清晰,特意引入了两个数组来说明这个解题过程,我们发现保存左端元素之积的位置和保存右端元素之积的位置都是一一对应的,所以只用将左端或者右端元素之积保存到一个数组中,在遍历这数组挨个乘上右端或者左端元素之积并且进行保存。左端元素之积叫做前缀之积,右端元素之积叫做后缀之积

3至少是其他数字的两倍

题目链接 力扣747

这道题有很多细节需要处理,要对问题考虑全面才能通过所有的测试用例。首先这个最大的数是要满足它至少是别的每个数的两倍,那么我们思考一下这个数最小应该是多少,最少应该是第二大的数的两倍,那么我们就把这个问题转化成了找数组中最大的数,和第二大的数。这样就比较好处理了

基于上述思路写出如下代码

int dominantIndex(int* nums, int numsSize){
    int flag=-1;
    int frist;
    int second ;
    if(nums[0]>nums[1])
    {
        frist=nums[0];
        second=nums[1];
        flag=0;
    }
    if(nums[0]<nums[1])
    {
        frist=nums[1];
        second=nums[0];
        flag=1;

    }
    if(numsSize==1)
    {
        return 0;
    }
    
   for(int i=2;i<numsSize;i++)
   {   
       if(nums[i]>frist)
       {  second=frist;
           frist=nums[i];
           flag=i;
           
       }
       else 
       {
         second=(second>nums[i]?second:nums[i]);
        
       }
   }
 if(frist>=2*second)
 {
     return flag;
 }
 else
 return -1;
}

我们在找一个数组中最大的元素一般做法就是将数组首元素赋值给变量max,然后遍历数组,这样赋初值的原因就是保证max在这个数组范围内的,不能脱离这个范围。因此我们在赋初值的时候将数组首元素和第二个元素赋值给frist second ,同时用flag记录frist的下标。直接就是进行遍历了,挨个比较交互,但是为什么要加上else 呢?我们在赋值的是直接将数组第一个元素和第二个元素给了两个变量,如果数组最大的元素就在这两个位置之中,first确实是最大元素,但是能保证second就是第二大的元素吗?如果没有elseif 语句,frist不会进入if语句中去,所有根本无法保证second就是第二大的数,所以要有一个else 同时i=2开始循环的,也不担心出现frist和second相同的情况

4.珠玑妙算

题目链接 力扣面试题16.15.

其实这个题目我当时想了好一会才读懂,期间将题目理解错了,导致一直不能过全部测试用例。我当时以为伪猜中就是在对应位置不相等的前提下,guess是solution的子集。实际上不是这样的,对应位置如果相同算猜中,同时这个字符不会再参与伪猜中的比较,同时在对应位置不相等的前提下,对于solution中出现过一次的元素,guess哪怕出现多次也只是按一次计算,但是对应位置不相同的前提下,soloution中某个字符出现多次的话,guess也出现多次实际上要算多次的,这多次的次数是以soloution中的次数为准的,其实对于同一个元素的伪猜中,最多的次数就是两次。因为只有4个位置还要保持对应位置不相等,对于同一个字符来说最多只能出现在两个位置上。

题目要求弄懂了,具体怎么解决呢?我还是采用元素重合问题处理,将guess和solution元素转为下标,很明显这里不能用置数的因为重复的元素可能也会参与计数。于是只能用加加 *** 作了。这个还有个要处理的点就是计数,计数是以solution中的元素为准的,哪怕gusee出现多次也不参与计数。同时元素当作数组下标其实充当了计数功能的出现一次加一次,又因为会有重复元素重复计数问题,直接取guess和solutions所对应数组的元素最小值。同时这样做猜中也是会被计算在内的,最后减去猜中的次数即可

代码如下

int* masterMind(char* solution, char* guess, int* returnSize){
    *returnSize=2;
    int *nums=malloc(sizeof(int)*2);
    int count1=0;
    int count2=0;
    int arr1[26]={0};
    int arr2[26]={0};
    for(int i=0;i<4;i++)
    {
      if(solution[i]==guess[i])
      {
        count1++;
      }
    arr1[solution[i]-65]++;
    arr2[guess[i]-65]++;
    }

for(int j=0;j<26;j++)
{ 
    if(arr1[j]+arr2[j]>=2)
       {
           count2=(arr2[j]>arr1[j]?arr1[j]:arr2[j])+count2;;
       }
}
    
  if(count1==4)
    {
        nums[1]=0;
        nums[0]=4;
    }
  
   if(count2!=0)
    {
        nums[0]=count1;
        nums[1]=count2-count1;
    }

 if(count2==0)
   {
       nums[1]=0;
       nums[0]=0;
   }
   return nums;
}

同时对几种特殊情况判断就是 都猜中了,还有就是连伪猜中都没有。伪猜中都没有,猜中肯定也没有。因为都是小写字母,所以减了65,相当于减了个字符a.

3.移位 *** 作符和位 *** 作符相关问题 1.整数转换

题目链接 力扣面试题05.06整数转换

题目描述 需要改变多少个位才能将a转成b,这题实际上就是要求a和b有多少位是不同的,我们知道异或运算就是相同为0,不同为1,如果我们将a和b异或后,再求出这个异或后的数中有多少位是1,就解决了这个问题了

基于上述思路写出如下代码

int convertInteger(int A, int B){
    int n=A^B;
 int  count =0;
 for(int i=0;i<32;i++)
 {
     if((n>>i)&1)
     {
         count++;
     }
 }
  return count;
}



将a和b异或之后,在右移每一位于1进行与运算,如果该位是1,与运算后也是1,计数器加1,这个移位之后n的值本身没有发生改变,因为这里没有出现赋值行为,在之前的文章中求1的时候有这样的写法 n=n&(n-1),在这道题中是行不通的,因为题目给出的数据测试范围有部分有符号整数会溢出,不能用intl类型,但是题目的形参类型已经固定了,所以只能通过移位来计算的

2.牛客 寻找奇数

题目链接 KS33 寻找奇数

根据题目描述,只有一个数字是出现了奇数次数,其他都偶数次数。找到这个数字。在之前的文章中有介绍不引入第三个变量,利用异或运算交换两个数。异或运算有这样一个特性 a^a=0, a ^ 0=a,0 ^ 0=0,那么一个数经过偶数次异或本身,那么这个数就是0,奇数次异或就还是它本身,那么直接将0和这个数组的每个元素进行异或运算,因为出现偶数次数的数异或后还是0,0与0异或还是0,最后就只有0和和出现奇数次数的数异或,异或的结果就是这个数字。

写出如下代码

#include
int main()
{ int ret=0;
    int n =0;
    scanf("%d",&n);
    int nums[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    for(int j=0;j<n;j++)
    {
        ret=nums[j]^ret;
    }
 
 printf("%d",ret);
}

这题还是比较简单的,可能有时候想不到。我当时也没有马上想到还是题做少了,只要多编程实践并且总结,慢慢就会下笔如有神的。

3.不用加减乘除做加法

题目链接 牛客JZ65 不用加减乘除做加法

这道题猛一看感觉无从下手,其实在数电中可以用异或门和与门实现一个半加器。半加器是实现两个一位二进制数加法运算的器件。实际上就是利用异或运算和与运算,来实现了加法。这些位 *** 作都以2进制为基础来运算的,也就是题目是想要求我们以用2进制加法规则来实现10进制的计算.在实现之前我们先分析一下10进制的加法运算规则.
以5+4为例
05
+
04
________
09
这是没有进位的加法,4 和5除了本身的个位以外其余高位都是0,因为没有进位直接对应位置相加即可。那要是有进位怎么办呢?以9+4为例
9+4=(9+1)+3=10+3.我们先把需要进位的分部先进位,进位以后就还是对应位置直接相加即可。

说完10进制再来说2进制
2进制数除了0就是1,同时缝2进1,
也就是说 1+0 =1;0+1=1;0+0=0;1+1=1 0;
我们先不看进位的部分,就是说
1+0 =1 ; 0+1=1 ;0+0=0;1+1=0;(先不看进位部分),这样的运算结果是不是很像异或,相同为0,不同为1.这对于2进制来说。不需要进位的加法,运算逻辑就是异或.
那进位部分怎么算呢,首先通过上面的例子可以看到只有当对应位置为1时才进位 .那么计算进位时,第一件事就是判断对应位置哪里有1, 同时对于非1的位置不做处理,只是单纯的得到进位部分 ,2进制除了0就是1现在只是处理对应位置的1,剩下的0的保持原样即可,符合这个条件的只有与运算了,因为进位对应数值需要到高位上去,所以需要左移一位。在将进位部分和非进位部分相加即可。

总的来说 如果对应位置没有1就是 a&b==0;相加的结果就是 a^ b ;如果对应位置有1就是 :a&b!=0;相加结果就是a ^ b+a&b<<1;但是进位都是低位往高位进的,对于一串二进制数来说,进位可能不仅仅至进位一次,从低位往高位挨个判断是否有1需要进位.
如果我们定义一个add函数来实现a+b,add(a,b) 实际上 就是求a^b+a&b<<1;这貌似有了一个公式 add(a,b)=add(a ^b,a&b<<1 ),这不就是递推公式吗,递推公式有了,但是递推的出口是什么呢?我们前面说了,如果没有1不就是直接a ^ b;直接对应位置异或就行了。边界条件也有了,就是a和b对应位置有没有1.

基于上述思路代码如下

nt Add(int num1, int num2 ) {
    
     if(num1&num2==0)
     {
         return num1^num2;
     }
    
     else

    return Add(num1^num2,num1&num2<<1) ;
}

在判断边界条件时返回值时num1 ^ num2,在说异或时0 ^a=a,这不相当于a+0=a,所以边界条件还可以改写一下

if(num1=0||num2=0)//加数有一个为0,直接返回另一个加数 符合加法逻辑

但是这道题如果用递归的话,时间复杂度太大了。过不了牛客测试用例。其实基本上所有的递归都可以改写成循环的形式来处理。既然递归的通不过我们直接写循环 既然是循环,那循环条件是什么呢?上面提到了有加数是0直接返回另一个加数,如果num2是0,直接返回num1,如果不是进入循环,从低位往高位判断对应位置是否都是1。这就说明b要不断更新,保证在对应位置没0的时候顺利跳出循环。异或运算实际并不会计算需要进位的位置,它只会保留本位的数值,9+4=10按照异或逻辑类似于只会保留0,1直接舍去。所以直接开始异或运算也不会影响到后续,当两数相加需要进位时,可以把位进后的结果保留,在进行对应位置的不进位的加法运算。这个把位进了的过程就是a&b<<1 类比 9+4的10进制计算,9+4=13 1直接舍去保留3, 9+1=10 把位进了 ,然后 10+(3)=13;每一次进位后进行对应位置的不进位的加法计算。什么时候停下种重复计算呢,毫无疑问就是当没有进位计算的时候,也就是说b中的1消耗完的时候,就是相与之后为0的时候,b的重新赋值既保留了进位后的结果,也保证了能顺利跳出循环


add(int a ,int b)
{
     while(b!=0)      
    { int tem=a^b;  
     b=(a&b<<1);
     a=tem;    
    }
    return a;
}

9+4=13 舍去1 保留3 就是03 ; 9+4=13,舍去3,保留1,就是10;最后就是10+03 =13
对于加法计算实际上是拆分了两部分计算 进位计算 不进位对应位置计算,每一次进位后 都要进行对 对应位置 不进位计算 实际上这也就是加法运算规则。然后重复上述的 *** 作 直到没有进位计算为止

这道题在《剑指offer》上也有出现。力扣上也有这道题但是力扣的题目要求更多一点,牛客上只能算正数,算不了负数,其实算负数就相当于不用四则运算实现了减法,加上一个数的相反数等于减去这个数

力扣题目链接不用四则运算做加法

因为上述代码只能算正整数,正整数的补码与原码相同,负整数的补码为其原码除符号位外的所有位取反后加 1。因为每一次拆分都可以让需要进位的最低位至少左移一位。符号位与数值要一起参与运算,要保证这一点。我们直接将进位的被结果保存到无符号整型中,然后异或完成不进位相加时,将保留的无符号整型赋值给b,来实现负数的相加。

int add(int a,int b)
{ w
    while(b)
    {
        unsigned int tem =(unsigned int)(a&b)<<1;
        a=a^b;
        b=tem;

    }
    return a;
}

这样实现的add函数除了算加法还可以算减法。

4.字符串相关问题 1. 牛客 单词倒排

题目链接 牛客 hj31

在字符串的相关练习的博客中,我提到了并实现reverse(反转)函数,就是将字符串的每个字符逆序,我们看到其实这道题也可以利用反转函数。我们把除了字母和空格外的所有字符都变成空格。在利用reverse函数处理字符串,和单词倒序那道题一样的做法,最后输出即可。这道题和单词倒序基本上没有太大的区别

单词倒序题目链接 牛客倒置字符串
基于上述思路代码如下

#include
#include

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}

int main()
{
	char str[10002] = { 0 };
	int len = 0;
	int i=0; 
	int flag = 0;
	gets(str);
	len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && 
		str[i] <= 'Z' || str[i] == ' ')
			continue;//这个循环停止是为了提高一点效率
		else
		{
			str[i] = ' ';
			//将字符串中除字母和空格以外的位置都替换为空格
		}
	}

	char* start =str ;

	while (*start != ')'char
	{
		*= end ; startwhile
		( *!=end ' ' && * !=end ')' ++;
		{
			end}reverse
		(
		,-start1 end ) ;if(

		* !=')'end = +1
			start ; end else =;
		}
			start reverse end(

	,
	+-str1 str)len;puts()
	;returnstr0;
   } 反转函数的实现我就不多说了,还是想提下我第一次做倒置单词的时候,我曾经将start end同时定义在while循环外部,程序出错了,因为end更新指向时空格时,需要跳出循环,之后的end需要再次进入第二个while中指向下一个单词结尾处的空格或者当end每次跳出第二个循环时必须进行判断,end是因为空格跳出来的还是因为void跳出来的,如果是空格那就end+1,start指向下一个单词的开头,如果不是空格,那就一定是string_revolve,这个时候只用start直接等于end不用加1,因为这说明最后一个单词已经是逆序完了,直接跳出循环即可。,如果在循环外部定义end,之后的end再也不会进入第二个while更新了,所以必须再将下个单词的起始位置start赋给end.因此在不想引入第三个变量的前提下,需要将end定义在while循环内。(
char

*
,

2.左旋字符串

这道题我们通常想到的做法就是 我们将字符串的符串挨个往前挪动一步,同时将字符串首字符保存,挪动完了再将字符串的首字符移动到末尾,重复上述步骤,直到将k个字符挪动完毕

基于上述思路写出如下代码

int ,int)//1将第一个字符保存str//2每个字符都往前挪动//3将第一个字符放在末尾,并且循环往返 kfor( lenint
{  =
	0
	;
	< ;++ i ) char= i * k; ifor(
	 {
		int tem = 0str;
		< -1 j ; ++) j * len(+) j=*
		{
			(+str+j1 ) ;}str * j(+-1
		)
		=;str } len } len%k voidreverse tem(

	  char

 *

这种方法就属于暴力枚举,挨个挪动,如果有7个字符的字符串挪动7次以后就复原了,所以可以用,将这个结果作为循环挪动的次数
除了上述的做法外还有一种方法还是利用到reverse翻转函数,

所以先将字符串分为2部分,先各自逆序翻转,最后整体反转
代码如下


char *)while( left< )char right=
{
	* ;left * right=
	{
		* tem ; *left=
		;left ++ ;right--
		;right } tem}
		leftintmain
		right()

	char

[

] ="ABCD"}
{
	; str//A DCB  BCDAint = { strlen ();
	int len = 2;str//旋转次数reverse
	( k , +-1
	);str//先旋转单个部分 str reverse k(+,+-
	1)str ; k//在旋转后半部分整体 str reverse len ( ,+-1
	);str//旋转整个字符串 str printf len ( "%s",);
	}intfind( strconstchar
*

3.左旋判断


既然左旋都会了,判断就很容易,求出字符串的长度,然后挨个左旋判断,如果是就返回对应的左旋次数。如果有7个字符的字符串,左旋7次都没有匹配上,直接返回0.任选上述两种左旋方式都可以解决这个问题。
那还有其他的方法吗?我们再原有的字符串上基础上再追加它本身,那么它所有的左旋结果都是这个追加后的字符串的子串
ABCDE的所有左旋结果都是 ABCDEABCDE 的子串
这样我们直接用库函数实现即可
代码如下

, char*) char [ src256 ] = find0
{
	} tmp;//用一个辅助空间将原字符串做成两倍原字符串strcpy ( { , ); //先拷贝一遍
	char*tmp= srcstrcat( ,
	);ret//再连接一遍 if(tmp!= srcNULL) return
	1;ret}return0
	{
	  ;  }
	
  esle 
  [+++] [+++][+++]
[+++]

其实还可以直接在原字符串上直接追加它本身在用strstr查找匹配,但是会改变原字符串内容。

3.总结

1.关于元素重合问题,将元素转为数组下标,然后直接置数。注意一点数组的元素个数是决定了数组的下标值的范围,数组下标最大值一定是要大于等于元素最大值的。
2.逻辑运算和位运算,需要总结并且不断练习实践。
3.字符串问题,逆序反转函数很有用,做题以前可以先观察输入和输出之间有没有联系。
4.编程需要多实践,做的题多了,思维就会更加开阔。同时要及时复盘总结。
5.以上的解法都没有用到特别高深的算法和复杂的数据结构。可能处理方式比较巧妙一点,但是我觉得不要为自己懒刷题找借口,认为自己数据结构什么都不会,就不能去做力扣题和牛客题。只要肯学,肯练。一切都会慢慢好起来的。这句话是对我自己说的。显然我现在也还不会数据结构,但是我相信再寒假之前一定会有长进的!
6.以上解法不一定是最优解,只是我个人的浅薄见解,内容如有问题欢迎指正!

)
File: /www/wwwroot/outofmemory.cn/tmp/route_read.php, Line: 126, InsideLink()
File: /www/wwwroot/outofmemory.cn/tmp/index.inc.php, Line: 165, include(/www/wwwroot/outofmemory.cn/tmp/route_read.php)
File: /www/wwwroot/outofmemory.cn/index.php, Line: 30, include(/www/wwwroot/outofmemory.cn/tmp/index.inc.php)
Error[8]: Undefined offset: 1510, File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 121
File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 473, decode(

文章目录


前言

编程是需要不断练习实践的,所以刷题是很有必要的。但是不能盲目的刷题,要对做过的题题目进行总结复盘。以下是我对暑假期间做过的题目的部分总结,做个简单的记录。


1、重合元素问题 1.力扣645 错误的集合

题目链接力扣645

题目的要求就是在1到n中查找重复的数字和丢失的数字,我们先这样思考一下假如集合中1到n没有发生丢失,1到n就是自然数顺序排列,这样和我们数组的下标是和契合的,数组的下标就是0到n-1的自然数顺序数列,那我们将集合的每个元素减1当作另一个数组的下标来使用,将这个数组的所有的元素的元素初始化都置为0,再用集合中元素当作此数组下标,进行遍历加1,因为有重复的数据,所以数组中某个位置处肯定是2,找到这个2的位置,也就是数组的下标,这个下标就是重复的数据,因为丢失了某个数据。也就是说数组的某个位置没有加1,还是初始值0,找到0所对应的下标就是丢失的数据。

基于上述思路写出如下代码

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    *returnSize=2;
    int* arr1;
    arr1=(int*)malloc(sizeof(int)*2);
    int* arr2;
    arr2=calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]-1]++;
    }
    for(int j=0;j<numsSize;j++)
    {
        if(arr2[j]==2)
          {
              arr1[0]=j+1;
          }
          else if(arr2[j]==0)
          {
              arr1[1]=j+1;
          }
    }
  return arr1;
}

在这里说一下,力扣是接口型oj,,函数的返回值和参数都已经写好固定了,只要完善这个函数即可。这个代码中calloc函数是动态分配空间,并且将分配的空间的元素都置为0,有类似于初始化的作用,malloc函数只是分配空间.
因为数组的下标是从0开始的,所以将集合中元素当作下标的时候减1,同时在找丢失的数据和重复的数据的时候需要再把这个1加回来,当然也可以多申请一个空间,这样就不用加1减1了,但是要注意集合的下标不要越界。
arr2[nums[i]-1]这是十分最主要的一步。
这道题其实就是处理元素重合问题,处理这种问题,将要处理的集合元素转化为另一个数组的下标是一种很有用的方法。

2.力扣349求两个数的交集

题目链接 力扣349题

这道题也是重和的问题,还可以利用上述的方法。将集合的元素转化成数组的下标,只不过不用加1,我们直接将数组元素置为一个数,因为要处理两个集合,这两个集合的元素不确定出现多少次,比如2在集合1和集合2中重复3次,3在集合1和集合2出现了1次,如果还是采用加加的 *** 作 不好通过数组的元素的值判断重复的元素,直接将给数组元素置数赋值,就可以很好的处理了
基于上述思路,写出如下代码

int* intersection(int* nums1, int nums1Size, int* nums2,
 int nums2Size, int* returnSize)
 {
*returnSize=0;
int* arr=calloc(10001,sizeof(int));
int* return_arr=malloc(10001*sizeof(int));
for(int i=0;i<nums1Size;i++)
{
    arr[nums1[i]]=1;
   
 }
   
 for(int j=0;j<nums2Size;j++)
 {
     if(arr[nums2[j]]==1)
     {
         arr[nums2[j]]=2;
     }
 }

 for(int k=0;k<1001;k++)
 {
     if(arr[k]==2)
     {
         return_arr[*returnSize]=k;
         *returnSize+=1;
     }
 }
 return return_arr;

}

我们先将集合1元素当作数组下标,并且将数组元素置为1,接着再将集合2的元素当作数组下标,再里面找1,如果找到了1,这个位置的下标就是两个集合中相同的元素,那么为了找到这个下标,直接将其置为2,就一步就相当于对数组该位置进行标记。最后在数组中找到2对应的下标,这个下标就是重复的元素,因为我没有减1,直接用的集和元素,所以在下标就是重复元素,就不用再去减1了。同时题目给了集合元素个数范围,为了避免空间不够,我就申请了10001*4字节的空间

3. 牛客HJ10 字符个数统计

题目链接字符统计个数

这道题还是元素重和问题,还是老方法,将字符串每个字符转成另一个数组的下标来处理。因为题目说了多个相同只算一次,同时字符串也没有空格。还是直接数组元素置数。

代码如下

#include
int word_count(char* str, int len)
{
    int arr[127] = { 0 };
    int count = 0;
    for (int i = 0; i < len; i++)
    {
        arr[str[i]] = 1;
    }
    for (int i = 0; i < 127; i++)
    {
        if (arr[i] == 1)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    char str[5001] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int ret = word_count(str, len);
    printf("%d", ret);
    return 0;
}

之所以将数组的个数设置成127因为字符对应的ASCII值最大为127,也就是字符串字符作为数组下标时最大只能到127.将数组元素置为1,在判断如果数组元素时1,计数器加1,这样置数赋值,就算有重复的字符也只计算一次。

4.力扣448找到数组中消失的数字

题目链接 力扣448题

这题和第一道例题特别相似,题目还是关于元素重合问题,这个找没有出现的的元素,第一道例题是找丢失的元素,很明显题目是换了个马甲,还是老方法处理转成数组下标然后置数赋值

基于以上思路,写出如下代码

int* findDisappearedNumbers(int* nums, int numsSize,int* returnSize)
{
     *returnSize=0;
    int* arr1=(int*)malloc(sizeof(int)*(numsSize+1));
    int* arr2=calloc((numsSize+1),sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]]=1;
    }
    for(int j=1;j<numsSize+1;j++)
    {
        if(arr2[j]==0)
          {
              arr1[*returnSize]=j;
              *returnSize+=1;
          }
          
    }
  return arr1;
}

利用calloc函数将开辟的空间中的元素初始化为0.将集合的元素转化为数组下标,这次我直接将集合中的元素转为下标没有减1,然后置1进行判断找到还是0的元素下标,但是要注意一点就是由于集合元素转为数组下标时没有减1,开辟空间是需要比集合的元素个数多一个的。因为数组的元素个数是和决定了数组元素下标最大值的,数组下标必须要满足大于等于集合中的最大元素的。

2.杂题汇总 1.摩尔投票法

题目链接 力扣169

题目描述,集合中一定有一个出现次数的最多的元素,找出来这个元素。这道题用摩尔投票法可以轻松解决。什么是摩尔投票法,这里先不说卖个关子,我们直接看代码分析

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

摩尔投票法,听着名字挺唬人的。按照我自己理解就是一换一厮杀法 求解数组中最多元素问题 。假如在3国时,蜀吴各有两千士兵,现在魏国有1万士兵,现在3国进行决战,魏蜀吴的士兵每个士兵都只能一换一同归于尽,那么最后打赢的一定是魏国。因为3方士兵只能一换一,魏国士兵最多。这个厮杀的过程就是在找出现次数最多的元素,为了模拟这个厮杀过程 可以用一个计数器来表示,将不同的元素想象成不同国家的士兵 ,计数器来表示生命值 ,遇到相同士兵计数器就加一, 表示结成阵营, 不同的就减一 ,表示一换一杀死了一个士兵。一旦计数器为0,就换下一个兵种,最后剩下的就是人数最多的士兵。我们最开始的时候直接将第一个元素当作出现次数最多的,这个时候相当于有了一个士兵,所以就有了一条命,计数器要赋值成1.然后进行厮杀,如果某次计数器为0,就表示某国的士兵死完了,换下一个国家的士兵继续厮杀。注意一点我在代码中写的是else if不是if,如果是if就会同时判断,类似于并行的关系。用了elsi fi是类似于递进的,上一个不满足时才会判断下一个

2.除自身以外所有元素的乘积

题目链接 力扣238题

这道题确实有难懂,我暑假琢磨了很久才弄懂
题目要求就是将元素对应位置的地方放置除了它本身外和其他元素的乘积,我们这样思考一下,假如我以每个元素的位置为分界线 将左边部分的乘积按顺序放放在一个数组中,将右边部分的乘积按顺序放在另一个数组中,如果分界线元素在两个端点处,所对应的乘积直接为1,在将这两个数组对应位置相乘即为所求

这样说比较抽象直接画图举例

基于上述思路写出如下代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* nums_return = malloc(numsSize * 4);
    int  left =1;
    int right = 1;
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums_return[i]=left;
        left=left*nums[i];
    }
   
   for(int j=numsSize-1;j>=0;j--) 
   {
    
    nums_return[j]=nums_return[j]*right;
    right=right*nums[j];
   }
    return nums_return;


}

上面为了解题思路更加清晰,特意引入了两个数组来说明这个解题过程,我们发现保存左端元素之积的位置和保存右端元素之积的位置都是一一对应的,所以只用将左端或者右端元素之积保存到一个数组中,在遍历这数组挨个乘上右端或者左端元素之积并且进行保存。左端元素之积叫做前缀之积,右端元素之积叫做后缀之积

3至少是其他数字的两倍

题目链接 力扣747

这道题有很多细节需要处理,要对问题考虑全面才能通过所有的测试用例。首先这个最大的数是要满足它至少是别的每个数的两倍,那么我们思考一下这个数最小应该是多少,最少应该是第二大的数的两倍,那么我们就把这个问题转化成了找数组中最大的数,和第二大的数。这样就比较好处理了

基于上述思路写出如下代码

int dominantIndex(int* nums, int numsSize){
    int flag=-1;
    int frist;
    int second ;
    if(nums[0]>nums[1])
    {
        frist=nums[0];
        second=nums[1];
        flag=0;
    }
    if(nums[0]<nums[1])
    {
        frist=nums[1];
        second=nums[0];
        flag=1;

    }
    if(numsSize==1)
    {
        return 0;
    }
    
   for(int i=2;i<numsSize;i++)
   {   
       if(nums[i]>frist)
       {  second=frist;
           frist=nums[i];
           flag=i;
           
       }
       else 
       {
         second=(second>nums[i]?second:nums[i]);
        
       }
   }
 if(frist>=2*second)
 {
     return flag;
 }
 else
 return -1;
}

我们在找一个数组中最大的元素一般做法就是将数组首元素赋值给变量max,然后遍历数组,这样赋初值的原因就是保证max在这个数组范围内的,不能脱离这个范围。因此我们在赋初值的时候将数组首元素和第二个元素赋值给frist second ,同时用flag记录frist的下标。直接就是进行遍历了,挨个比较交互,但是为什么要加上else 呢?我们在赋值的是直接将数组第一个元素和第二个元素给了两个变量,如果数组最大的元素就在这两个位置之中,first确实是最大元素,但是能保证second就是第二大的元素吗?如果没有elseif 语句,frist不会进入if语句中去,所有根本无法保证second就是第二大的数,所以要有一个else 同时i=2开始循环的,也不担心出现frist和second相同的情况

4.珠玑妙算

题目链接 力扣面试题16.15.

其实这个题目我当时想了好一会才读懂,期间将题目理解错了,导致一直不能过全部测试用例。我当时以为伪猜中就是在对应位置不相等的前提下,guess是solution的子集。实际上不是这样的,对应位置如果相同算猜中,同时这个字符不会再参与伪猜中的比较,同时在对应位置不相等的前提下,对于solution中出现过一次的元素,guess哪怕出现多次也只是按一次计算,但是对应位置不相同的前提下,soloution中某个字符出现多次的话,guess也出现多次实际上要算多次的,这多次的次数是以soloution中的次数为准的,其实对于同一个元素的伪猜中,最多的次数就是两次。因为只有4个位置还要保持对应位置不相等,对于同一个字符来说最多只能出现在两个位置上。

题目要求弄懂了,具体怎么解决呢?我还是采用元素重合问题处理,将guess和solution元素转为下标,很明显这里不能用置数的因为重复的元素可能也会参与计数。于是只能用加加 *** 作了。这个还有个要处理的点就是计数,计数是以solution中的元素为准的,哪怕gusee出现多次也不参与计数。同时元素当作数组下标其实充当了计数功能的出现一次加一次,又因为会有重复元素重复计数问题,直接取guess和solutions所对应数组的元素最小值。同时这样做猜中也是会被计算在内的,最后减去猜中的次数即可

代码如下

int* masterMind(char* solution, char* guess, int* returnSize){
    *returnSize=2;
    int *nums=malloc(sizeof(int)*2);
    int count1=0;
    int count2=0;
    int arr1[26]={0};
    int arr2[26]={0};
    for(int i=0;i<4;i++)
    {
      if(solution[i]==guess[i])
      {
        count1++;
      }
    arr1[solution[i]-65]++;
    arr2[guess[i]-65]++;
    }

for(int j=0;j<26;j++)
{ 
    if(arr1[j]+arr2[j]>=2)
       {
           count2=(arr2[j]>arr1[j]?arr1[j]:arr2[j])+count2;;
       }
}
    
  if(count1==4)
    {
        nums[1]=0;
        nums[0]=4;
    }
  
   if(count2!=0)
    {
        nums[0]=count1;
        nums[1]=count2-count1;
    }

 if(count2==0)
   {
       nums[1]=0;
       nums[0]=0;
   }
   return nums;
}

同时对几种特殊情况判断就是 都猜中了,还有就是连伪猜中都没有。伪猜中都没有,猜中肯定也没有。因为都是小写字母,所以减了65,相当于减了个字符a.

3.移位 *** 作符和位 *** 作符相关问题 1.整数转换

题目链接 力扣面试题05.06整数转换

题目描述 需要改变多少个位才能将a转成b,这题实际上就是要求a和b有多少位是不同的,我们知道异或运算就是相同为0,不同为1,如果我们将a和b异或后,再求出这个异或后的数中有多少位是1,就解决了这个问题了

基于上述思路写出如下代码

int convertInteger(int A, int B){
    int n=A^B;
 int  count =0;
 for(int i=0;i<32;i++)
 {
     if((n>>i)&1)
     {
         count++;
     }
 }
  return count;
}



将a和b异或之后,在右移每一位于1进行与运算,如果该位是1,与运算后也是1,计数器加1,这个移位之后n的值本身没有发生改变,因为这里没有出现赋值行为,在之前的文章中求1的时候有这样的写法 n=n&(n-1),在这道题中是行不通的,因为题目给出的数据测试范围有部分有符号整数会溢出,不能用intl类型,但是题目的形参类型已经固定了,所以只能通过移位来计算的

2.牛客 寻找奇数

题目链接 KS33 寻找奇数

根据题目描述,只有一个数字是出现了奇数次数,其他都偶数次数。找到这个数字。在之前的文章中有介绍不引入第三个变量,利用异或运算交换两个数。异或运算有这样一个特性 a^a=0, a ^ 0=a,0 ^ 0=0,那么一个数经过偶数次异或本身,那么这个数就是0,奇数次异或就还是它本身,那么直接将0和这个数组的每个元素进行异或运算,因为出现偶数次数的数异或后还是0,0与0异或还是0,最后就只有0和和出现奇数次数的数异或,异或的结果就是这个数字。

写出如下代码

#include
int main()
{ int ret=0;
    int n =0;
    scanf("%d",&n);
    int nums[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    for(int j=0;j<n;j++)
    {
        ret=nums[j]^ret;
    }
 
 printf("%d",ret);
}

这题还是比较简单的,可能有时候想不到。我当时也没有马上想到还是题做少了,只要多编程实践并且总结,慢慢就会下笔如有神的。

3.不用加减乘除做加法

题目链接 牛客JZ65 不用加减乘除做加法

这道题猛一看感觉无从下手,其实在数电中可以用异或门和与门实现一个半加器。半加器是实现两个一位二进制数加法运算的器件。实际上就是利用异或运算和与运算,来实现了加法。这些位 *** 作都以2进制为基础来运算的,也就是题目是想要求我们以用2进制加法规则来实现10进制的计算.在实现之前我们先分析一下10进制的加法运算规则.
以5+4为例
05
+
04
________
09
这是没有进位的加法,4 和5除了本身的个位以外其余高位都是0,因为没有进位直接对应位置相加即可。那要是有进位怎么办呢?以9+4为例
9+4=(9+1)+3=10+3.我们先把需要进位的分部先进位,进位以后就还是对应位置直接相加即可。

说完10进制再来说2进制
2进制数除了0就是1,同时缝2进1,
也就是说 1+0 =1;0+1=1;0+0=0;1+1=1 0;
我们先不看进位的部分,就是说
1+0 =1 ; 0+1=1 ;0+0=0;1+1=0;(先不看进位部分),这样的运算结果是不是很像异或,相同为0,不同为1.这对于2进制来说。不需要进位的加法,运算逻辑就是异或.
那进位部分怎么算呢,首先通过上面的例子可以看到只有当对应位置为1时才进位 .那么计算进位时,第一件事就是判断对应位置哪里有1, 同时对于非1的位置不做处理,只是单纯的得到进位部分 ,2进制除了0就是1现在只是处理对应位置的1,剩下的0的保持原样即可,符合这个条件的只有与运算了,因为进位对应数值需要到高位上去,所以需要左移一位。在将进位部分和非进位部分相加即可。

总的来说 如果对应位置没有1就是 a&b==0;相加的结果就是 a^ b ;如果对应位置有1就是 :a&b!=0;相加结果就是a ^ b+a&b<<1;但是进位都是低位往高位进的,对于一串二进制数来说,进位可能不仅仅至进位一次,从低位往高位挨个判断是否有1需要进位.
如果我们定义一个add函数来实现a+b,add(a,b) 实际上 就是求a^b+a&b<<1;这貌似有了一个公式 add(a,b)=add(a ^b,a&b<<1 ),这不就是递推公式吗,递推公式有了,但是递推的出口是什么呢?我们前面说了,如果没有1不就是直接a ^ b;直接对应位置异或就行了。边界条件也有了,就是a和b对应位置有没有1.

基于上述思路代码如下

nt Add(int num1, int num2 ) {
    
     if(num1&num2==0)
     {
         return num1^num2;
     }
    
     else

    return Add(num1^num2,num1&num2<<1) ;
}

在判断边界条件时返回值时num1 ^ num2,在说异或时0 ^a=a,这不相当于a+0=a,所以边界条件还可以改写一下

if(num1=0||num2=0)//加数有一个为0,直接返回另一个加数 符合加法逻辑

但是这道题如果用递归的话,时间复杂度太大了。过不了牛客测试用例。其实基本上所有的递归都可以改写成循环的形式来处理。既然递归的通不过我们直接写循环 既然是循环,那循环条件是什么呢?上面提到了有加数是0直接返回另一个加数,如果num2是0,直接返回num1,如果不是进入循环,从低位往高位判断对应位置是否都是1。这就说明b要不断更新,保证在对应位置没0的时候顺利跳出循环。异或运算实际并不会计算需要进位的位置,它只会保留本位的数值,9+4=10按照异或逻辑类似于只会保留0,1直接舍去。所以直接开始异或运算也不会影响到后续,当两数相加需要进位时,可以把位进后的结果保留,在进行对应位置的不进位的加法运算。这个把位进了的过程就是a&b<<1 类比 9+4的10进制计算,9+4=13 1直接舍去保留3, 9+1=10 把位进了 ,然后 10+(3)=13;每一次进位后进行对应位置的不进位的加法计算。什么时候停下种重复计算呢,毫无疑问就是当没有进位计算的时候,也就是说b中的1消耗完的时候,就是相与之后为0的时候,b的重新赋值既保留了进位后的结果,也保证了能顺利跳出循环


add(int a ,int b)
{
     while(b!=0)      
    { int tem=a^b;  
     b=(a&b<<1);
     a=tem;    
    }
    return a;
}

9+4=13 舍去1 保留3 就是03 ; 9+4=13,舍去3,保留1,就是10;最后就是10+03 =13
对于加法计算实际上是拆分了两部分计算 进位计算 不进位对应位置计算,每一次进位后 都要进行对 对应位置 不进位计算 实际上这也就是加法运算规则。然后重复上述的 *** 作 直到没有进位计算为止

这道题在《剑指offer》上也有出现。力扣上也有这道题但是力扣的题目要求更多一点,牛客上只能算正数,算不了负数,其实算负数就相当于不用四则运算实现了减法,加上一个数的相反数等于减去这个数

力扣题目链接不用四则运算做加法

因为上述代码只能算正整数,正整数的补码与原码相同,负整数的补码为其原码除符号位外的所有位取反后加 1。因为每一次拆分都可以让需要进位的最低位至少左移一位。符号位与数值要一起参与运算,要保证这一点。我们直接将进位的被结果保存到无符号整型中,然后异或完成不进位相加时,将保留的无符号整型赋值给b,来实现负数的相加。

int add(int a,int b)
{ w
    while(b)
    {
        unsigned int tem =(unsigned int)(a&b)<<1;
        a=a^b;
        b=tem;

    }
    return a;
}

这样实现的add函数除了算加法还可以算减法。

4.字符串相关问题 1. 牛客 单词倒排

题目链接 牛客 hj31

在字符串的相关练习的博客中,我提到了并实现reverse(反转)函数,就是将字符串的每个字符逆序,我们看到其实这道题也可以利用反转函数。我们把除了字母和空格外的所有字符都变成空格。在利用reverse函数处理字符串,和单词倒序那道题一样的做法,最后输出即可。这道题和单词倒序基本上没有太大的区别

单词倒序题目链接 牛客倒置字符串
基于上述思路代码如下

#include
#include

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}

int main()
{
	char str[10002] = { 0 };
	int len = 0;
	int i=0; 
	int flag = 0;
	gets(str);
	len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && 
		str[i] <= 'Z' || str[i] == ' ')
			continue;//这个循环停止是为了提高一点效率
		else
		{
			str[i] = ' ';
			//将字符串中除字母和空格以外的位置都替换为空格
		}
	}

	char* start =str ;

	while (*start != ')'char
	{
		*= end ; startwhile
		( *!=end ' ' && * !=end ')' ++;
		{
			end}reverse
		(
		,-start1 end ) ;if(

		* !=')'end = +1
			start ; end else =;
		}
			start reverse end(

	,
	+-str1 str)len;puts()
	;returnstr0;
   } 反转函数的实现我就不多说了,还是想提下我第一次做倒置单词的时候,我曾经将start end同时定义在while循环外部,程序出错了,因为end更新指向时空格时,需要跳出循环,之后的end需要再次进入第二个while中指向下一个单词结尾处的空格或者当end每次跳出第二个循环时必须进行判断,end是因为空格跳出来的还是因为void跳出来的,如果是空格那就end+1,start指向下一个单词的开头,如果不是空格,那就一定是string_revolve,这个时候只用start直接等于end不用加1,因为这说明最后一个单词已经是逆序完了,直接跳出循环即可。,如果在循环外部定义end,之后的end再也不会进入第二个while更新了,所以必须再将下个单词的起始位置start赋给end.因此在不想引入第三个变量的前提下,需要将end定义在while循环内。(
char

*
,

2.左旋字符串

这道题我们通常想到的做法就是 我们将字符串的符串挨个往前挪动一步,同时将字符串首字符保存,挪动完了再将字符串的首字符移动到末尾,重复上述步骤,直到将k个字符挪动完毕

基于上述思路写出如下代码

int ,int)//1将第一个字符保存str//2每个字符都往前挪动//3将第一个字符放在末尾,并且循环往返 kfor( lenint
{  =
	0
	;
	< ;++ i ) char= i * k; ifor(
	 {
		int tem = 0str;
		< -1 j ; ++) j * len(+) j=*
		{
			(+str+j1 ) ;}str * j(+-1
		)
		=;str } len } len%k voidreverse tem(

	  char

 *

这种方法就属于暴力枚举,挨个挪动,如果有7个字符的字符串挪动7次以后就复原了,所以可以用,将这个结果作为循环挪动的次数
除了上述的做法外还有一种方法还是利用到reverse翻转函数,

所以先将字符串分为2部分,先各自逆序翻转,最后整体反转
代码如下


char *)while( left< )char right=
{
	* ;left * right=
	{
		* tem ; *left=
		;left ++ ;right--
		;right } tem}
		leftintmain
		right()

	char

[

] ="ABCD"}
{
	; str//A DCB  BCDAint = { strlen ();
	int len = 2;str//旋转次数reverse
	( k , +-1
	);str//先旋转单个部分 str reverse k(+,+-
	1)str ; k//在旋转后半部分整体 str reverse len ( ,+-1
	);str//旋转整个字符串 str printf len ( "%s",);
	}intfind( strconstchar
*

3.左旋判断


既然左旋都会了,判断就很容易,求出字符串的长度,然后挨个左旋判断,如果是就返回对应的左旋次数。如果有7个字符的字符串,左旋7次都没有匹配上,直接返回0.任选上述两种左旋方式都可以解决这个问题。
那还有其他的方法吗?我们再原有的字符串上基础上再追加它本身,那么它所有的左旋结果都是这个追加后的字符串的子串
ABCDE的所有左旋结果都是 ABCDEABCDE 的子串
这样我们直接用库函数实现即可
代码如下

, char*) char [ src256 ] = find0
{
	} tmp;//用一个辅助空间将原字符串做成两倍原字符串strcpy ( { , ); //先拷贝一遍
	char*tmp= srcstrcat( ,
	);ret//再连接一遍 if(tmp!= srcNULL) return
	1;ret}return0
	{
	  ;  }
	
  esle 
   [+++][+++]
[+++]

其实还可以直接在原字符串上直接追加它本身在用strstr查找匹配,但是会改变原字符串内容。

3.总结

1.关于元素重合问题,将元素转为数组下标,然后直接置数。注意一点数组的元素个数是决定了数组的下标值的范围,数组下标最大值一定是要大于等于元素最大值的。
2.逻辑运算和位运算,需要总结并且不断练习实践。
3.字符串问题,逆序反转函数很有用,做题以前可以先观察输入和输出之间有没有联系。
4.编程需要多实践,做的题多了,思维就会更加开阔。同时要及时复盘总结。
5.以上的解法都没有用到特别高深的算法和复杂的数据结构。可能处理方式比较巧妙一点,但是我觉得不要为自己懒刷题找借口,认为自己数据结构什么都不会,就不能去做力扣题和牛客题。只要肯学,肯练。一切都会慢慢好起来的。这句话是对我自己说的。显然我现在也还不会数据结构,但是我相信再寒假之前一定会有长进的!
6.以上解法不一定是最优解,只是我个人的浅薄见解,内容如有问题欢迎指正!

)
File: /www/wwwroot/outofmemory.cn/tmp/route_read.php, Line: 126, InsideLink()
File: /www/wwwroot/outofmemory.cn/tmp/index.inc.php, Line: 165, include(/www/wwwroot/outofmemory.cn/tmp/route_read.php)
File: /www/wwwroot/outofmemory.cn/index.php, Line: 30, include(/www/wwwroot/outofmemory.cn/tmp/index.inc.php)
Error[8]: Undefined offset: 1511, File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 121
File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 473, decode(

文章目录


前言

编程是需要不断练习实践的,所以刷题是很有必要的。但是不能盲目的刷题,要对做过的题题目进行总结复盘。以下是我对暑假期间做过的题目的部分总结,做个简单的记录。


1、重合元素问题 1.力扣645 错误的集合

题目链接力扣645

题目的要求就是在1到n中查找重复的数字和丢失的数字,我们先这样思考一下假如集合中1到n没有发生丢失,1到n就是自然数顺序排列,这样和我们数组的下标是和契合的,数组的下标就是0到n-1的自然数顺序数列,那我们将集合的每个元素减1当作另一个数组的下标来使用,将这个数组的所有的元素的元素初始化都置为0,再用集合中元素当作此数组下标,进行遍历加1,因为有重复的数据,所以数组中某个位置处肯定是2,找到这个2的位置,也就是数组的下标,这个下标就是重复的数据,因为丢失了某个数据。也就是说数组的某个位置没有加1,还是初始值0,找到0所对应的下标就是丢失的数据。

基于上述思路写出如下代码

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    *returnSize=2;
    int* arr1;
    arr1=(int*)malloc(sizeof(int)*2);
    int* arr2;
    arr2=calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]-1]++;
    }
    for(int j=0;j<numsSize;j++)
    {
        if(arr2[j]==2)
          {
              arr1[0]=j+1;
          }
          else if(arr2[j]==0)
          {
              arr1[1]=j+1;
          }
    }
  return arr1;
}

在这里说一下,力扣是接口型oj,,函数的返回值和参数都已经写好固定了,只要完善这个函数即可。这个代码中calloc函数是动态分配空间,并且将分配的空间的元素都置为0,有类似于初始化的作用,malloc函数只是分配空间.
因为数组的下标是从0开始的,所以将集合中元素当作下标的时候减1,同时在找丢失的数据和重复的数据的时候需要再把这个1加回来,当然也可以多申请一个空间,这样就不用加1减1了,但是要注意集合的下标不要越界。
arr2[nums[i]-1]这是十分最主要的一步。
这道题其实就是处理元素重合问题,处理这种问题,将要处理的集合元素转化为另一个数组的下标是一种很有用的方法。

2.力扣349求两个数的交集

题目链接 力扣349题

这道题也是重和的问题,还可以利用上述的方法。将集合的元素转化成数组的下标,只不过不用加1,我们直接将数组元素置为一个数,因为要处理两个集合,这两个集合的元素不确定出现多少次,比如2在集合1和集合2中重复3次,3在集合1和集合2出现了1次,如果还是采用加加的 *** 作 不好通过数组的元素的值判断重复的元素,直接将给数组元素置数赋值,就可以很好的处理了
基于上述思路,写出如下代码

int* intersection(int* nums1, int nums1Size, int* nums2,
 int nums2Size, int* returnSize)
 {
*returnSize=0;
int* arr=calloc(10001,sizeof(int));
int* return_arr=malloc(10001*sizeof(int));
for(int i=0;i<nums1Size;i++)
{
    arr[nums1[i]]=1;
   
 }
   
 for(int j=0;j<nums2Size;j++)
 {
     if(arr[nums2[j]]==1)
     {
         arr[nums2[j]]=2;
     }
 }

 for(int k=0;k<1001;k++)
 {
     if(arr[k]==2)
     {
         return_arr[*returnSize]=k;
         *returnSize+=1;
     }
 }
 return return_arr;

}

我们先将集合1元素当作数组下标,并且将数组元素置为1,接着再将集合2的元素当作数组下标,再里面找1,如果找到了1,这个位置的下标就是两个集合中相同的元素,那么为了找到这个下标,直接将其置为2,就一步就相当于对数组该位置进行标记。最后在数组中找到2对应的下标,这个下标就是重复的元素,因为我没有减1,直接用的集和元素,所以在下标就是重复元素,就不用再去减1了。同时题目给了集合元素个数范围,为了避免空间不够,我就申请了10001*4字节的空间

3. 牛客HJ10 字符个数统计

题目链接字符统计个数

这道题还是元素重和问题,还是老方法,将字符串每个字符转成另一个数组的下标来处理。因为题目说了多个相同只算一次,同时字符串也没有空格。还是直接数组元素置数。

代码如下

#include
int word_count(char* str, int len)
{
    int arr[127] = { 0 };
    int count = 0;
    for (int i = 0; i < len; i++)
    {
        arr[str[i]] = 1;
    }
    for (int i = 0; i < 127; i++)
    {
        if (arr[i] == 1)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    char str[5001] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int ret = word_count(str, len);
    printf("%d", ret);
    return 0;
}

之所以将数组的个数设置成127因为字符对应的ASCII值最大为127,也就是字符串字符作为数组下标时最大只能到127.将数组元素置为1,在判断如果数组元素时1,计数器加1,这样置数赋值,就算有重复的字符也只计算一次。

4.力扣448找到数组中消失的数字

题目链接 力扣448题

这题和第一道例题特别相似,题目还是关于元素重合问题,这个找没有出现的的元素,第一道例题是找丢失的元素,很明显题目是换了个马甲,还是老方法处理转成数组下标然后置数赋值

基于以上思路,写出如下代码

int* findDisappearedNumbers(int* nums, int numsSize,int* returnSize)
{
     *returnSize=0;
    int* arr1=(int*)malloc(sizeof(int)*(numsSize+1));
    int* arr2=calloc((numsSize+1),sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]]=1;
    }
    for(int j=1;j<numsSize+1;j++)
    {
        if(arr2[j]==0)
          {
              arr1[*returnSize]=j;
              *returnSize+=1;
          }
          
    }
  return arr1;
}

利用calloc函数将开辟的空间中的元素初始化为0.将集合的元素转化为数组下标,这次我直接将集合中的元素转为下标没有减1,然后置1进行判断找到还是0的元素下标,但是要注意一点就是由于集合元素转为数组下标时没有减1,开辟空间是需要比集合的元素个数多一个的。因为数组的元素个数是和决定了数组元素下标最大值的,数组下标必须要满足大于等于集合中的最大元素的。

2.杂题汇总 1.摩尔投票法

题目链接 力扣169

题目描述,集合中一定有一个出现次数的最多的元素,找出来这个元素。这道题用摩尔投票法可以轻松解决。什么是摩尔投票法,这里先不说卖个关子,我们直接看代码分析

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

摩尔投票法,听着名字挺唬人的。按照我自己理解就是一换一厮杀法 求解数组中最多元素问题 。假如在3国时,蜀吴各有两千士兵,现在魏国有1万士兵,现在3国进行决战,魏蜀吴的士兵每个士兵都只能一换一同归于尽,那么最后打赢的一定是魏国。因为3方士兵只能一换一,魏国士兵最多。这个厮杀的过程就是在找出现次数最多的元素,为了模拟这个厮杀过程 可以用一个计数器来表示,将不同的元素想象成不同国家的士兵 ,计数器来表示生命值 ,遇到相同士兵计数器就加一, 表示结成阵营, 不同的就减一 ,表示一换一杀死了一个士兵。一旦计数器为0,就换下一个兵种,最后剩下的就是人数最多的士兵。我们最开始的时候直接将第一个元素当作出现次数最多的,这个时候相当于有了一个士兵,所以就有了一条命,计数器要赋值成1.然后进行厮杀,如果某次计数器为0,就表示某国的士兵死完了,换下一个国家的士兵继续厮杀。注意一点我在代码中写的是else if不是if,如果是if就会同时判断,类似于并行的关系。用了elsi fi是类似于递进的,上一个不满足时才会判断下一个

2.除自身以外所有元素的乘积

题目链接 力扣238题

这道题确实有难懂,我暑假琢磨了很久才弄懂
题目要求就是将元素对应位置的地方放置除了它本身外和其他元素的乘积,我们这样思考一下,假如我以每个元素的位置为分界线 将左边部分的乘积按顺序放放在一个数组中,将右边部分的乘积按顺序放在另一个数组中,如果分界线元素在两个端点处,所对应的乘积直接为1,在将这两个数组对应位置相乘即为所求

这样说比较抽象直接画图举例

基于上述思路写出如下代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* nums_return = malloc(numsSize * 4);
    int  left =1;
    int right = 1;
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums_return[i]=left;
        left=left*nums[i];
    }
   
   for(int j=numsSize-1;j>=0;j--) 
   {
    
    nums_return[j]=nums_return[j]*right;
    right=right*nums[j];
   }
    return nums_return;


}

上面为了解题思路更加清晰,特意引入了两个数组来说明这个解题过程,我们发现保存左端元素之积的位置和保存右端元素之积的位置都是一一对应的,所以只用将左端或者右端元素之积保存到一个数组中,在遍历这数组挨个乘上右端或者左端元素之积并且进行保存。左端元素之积叫做前缀之积,右端元素之积叫做后缀之积

3至少是其他数字的两倍

题目链接 力扣747

这道题有很多细节需要处理,要对问题考虑全面才能通过所有的测试用例。首先这个最大的数是要满足它至少是别的每个数的两倍,那么我们思考一下这个数最小应该是多少,最少应该是第二大的数的两倍,那么我们就把这个问题转化成了找数组中最大的数,和第二大的数。这样就比较好处理了

基于上述思路写出如下代码

int dominantIndex(int* nums, int numsSize){
    int flag=-1;
    int frist;
    int second ;
    if(nums[0]>nums[1])
    {
        frist=nums[0];
        second=nums[1];
        flag=0;
    }
    if(nums[0]<nums[1])
    {
        frist=nums[1];
        second=nums[0];
        flag=1;

    }
    if(numsSize==1)
    {
        return 0;
    }
    
   for(int i=2;i<numsSize;i++)
   {   
       if(nums[i]>frist)
       {  second=frist;
           frist=nums[i];
           flag=i;
           
       }
       else 
       {
         second=(second>nums[i]?second:nums[i]);
        
       }
   }
 if(frist>=2*second)
 {
     return flag;
 }
 else
 return -1;
}

我们在找一个数组中最大的元素一般做法就是将数组首元素赋值给变量max,然后遍历数组,这样赋初值的原因就是保证max在这个数组范围内的,不能脱离这个范围。因此我们在赋初值的时候将数组首元素和第二个元素赋值给frist second ,同时用flag记录frist的下标。直接就是进行遍历了,挨个比较交互,但是为什么要加上else 呢?我们在赋值的是直接将数组第一个元素和第二个元素给了两个变量,如果数组最大的元素就在这两个位置之中,first确实是最大元素,但是能保证second就是第二大的元素吗?如果没有elseif 语句,frist不会进入if语句中去,所有根本无法保证second就是第二大的数,所以要有一个else 同时i=2开始循环的,也不担心出现frist和second相同的情况

4.珠玑妙算

题目链接 力扣面试题16.15.

其实这个题目我当时想了好一会才读懂,期间将题目理解错了,导致一直不能过全部测试用例。我当时以为伪猜中就是在对应位置不相等的前提下,guess是solution的子集。实际上不是这样的,对应位置如果相同算猜中,同时这个字符不会再参与伪猜中的比较,同时在对应位置不相等的前提下,对于solution中出现过一次的元素,guess哪怕出现多次也只是按一次计算,但是对应位置不相同的前提下,soloution中某个字符出现多次的话,guess也出现多次实际上要算多次的,这多次的次数是以soloution中的次数为准的,其实对于同一个元素的伪猜中,最多的次数就是两次。因为只有4个位置还要保持对应位置不相等,对于同一个字符来说最多只能出现在两个位置上。

题目要求弄懂了,具体怎么解决呢?我还是采用元素重合问题处理,将guess和solution元素转为下标,很明显这里不能用置数的因为重复的元素可能也会参与计数。于是只能用加加 *** 作了。这个还有个要处理的点就是计数,计数是以solution中的元素为准的,哪怕gusee出现多次也不参与计数。同时元素当作数组下标其实充当了计数功能的出现一次加一次,又因为会有重复元素重复计数问题,直接取guess和solutions所对应数组的元素最小值。同时这样做猜中也是会被计算在内的,最后减去猜中的次数即可

代码如下

int* masterMind(char* solution, char* guess, int* returnSize){
    *returnSize=2;
    int *nums=malloc(sizeof(int)*2);
    int count1=0;
    int count2=0;
    int arr1[26]={0};
    int arr2[26]={0};
    for(int i=0;i<4;i++)
    {
      if(solution[i]==guess[i])
      {
        count1++;
      }
    arr1[solution[i]-65]++;
    arr2[guess[i]-65]++;
    }

for(int j=0;j<26;j++)
{ 
    if(arr1[j]+arr2[j]>=2)
       {
           count2=(arr2[j]>arr1[j]?arr1[j]:arr2[j])+count2;;
       }
}
    
  if(count1==4)
    {
        nums[1]=0;
        nums[0]=4;
    }
  
   if(count2!=0)
    {
        nums[0]=count1;
        nums[1]=count2-count1;
    }

 if(count2==0)
   {
       nums[1]=0;
       nums[0]=0;
   }
   return nums;
}

同时对几种特殊情况判断就是 都猜中了,还有就是连伪猜中都没有。伪猜中都没有,猜中肯定也没有。因为都是小写字母,所以减了65,相当于减了个字符a.

3.移位 *** 作符和位 *** 作符相关问题 1.整数转换

题目链接 力扣面试题05.06整数转换

题目描述 需要改变多少个位才能将a转成b,这题实际上就是要求a和b有多少位是不同的,我们知道异或运算就是相同为0,不同为1,如果我们将a和b异或后,再求出这个异或后的数中有多少位是1,就解决了这个问题了

基于上述思路写出如下代码

int convertInteger(int A, int B){
    int n=A^B;
 int  count =0;
 for(int i=0;i<32;i++)
 {
     if((n>>i)&1)
     {
         count++;
     }
 }
  return count;
}



将a和b异或之后,在右移每一位于1进行与运算,如果该位是1,与运算后也是1,计数器加1,这个移位之后n的值本身没有发生改变,因为这里没有出现赋值行为,在之前的文章中求1的时候有这样的写法 n=n&(n-1),在这道题中是行不通的,因为题目给出的数据测试范围有部分有符号整数会溢出,不能用intl类型,但是题目的形参类型已经固定了,所以只能通过移位来计算的

2.牛客 寻找奇数

题目链接 KS33 寻找奇数

根据题目描述,只有一个数字是出现了奇数次数,其他都偶数次数。找到这个数字。在之前的文章中有介绍不引入第三个变量,利用异或运算交换两个数。异或运算有这样一个特性 a^a=0, a ^ 0=a,0 ^ 0=0,那么一个数经过偶数次异或本身,那么这个数就是0,奇数次异或就还是它本身,那么直接将0和这个数组的每个元素进行异或运算,因为出现偶数次数的数异或后还是0,0与0异或还是0,最后就只有0和和出现奇数次数的数异或,异或的结果就是这个数字。

写出如下代码

#include
int main()
{ int ret=0;
    int n =0;
    scanf("%d",&n);
    int nums[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    for(int j=0;j<n;j++)
    {
        ret=nums[j]^ret;
    }
 
 printf("%d",ret);
}

这题还是比较简单的,可能有时候想不到。我当时也没有马上想到还是题做少了,只要多编程实践并且总结,慢慢就会下笔如有神的。

3.不用加减乘除做加法

题目链接 牛客JZ65 不用加减乘除做加法

这道题猛一看感觉无从下手,其实在数电中可以用异或门和与门实现一个半加器。半加器是实现两个一位二进制数加法运算的器件。实际上就是利用异或运算和与运算,来实现了加法。这些位 *** 作都以2进制为基础来运算的,也就是题目是想要求我们以用2进制加法规则来实现10进制的计算.在实现之前我们先分析一下10进制的加法运算规则.
以5+4为例
05
+
04
________
09
这是没有进位的加法,4 和5除了本身的个位以外其余高位都是0,因为没有进位直接对应位置相加即可。那要是有进位怎么办呢?以9+4为例
9+4=(9+1)+3=10+3.我们先把需要进位的分部先进位,进位以后就还是对应位置直接相加即可。

说完10进制再来说2进制
2进制数除了0就是1,同时缝2进1,
也就是说 1+0 =1;0+1=1;0+0=0;1+1=1 0;
我们先不看进位的部分,就是说
1+0 =1 ; 0+1=1 ;0+0=0;1+1=0;(先不看进位部分),这样的运算结果是不是很像异或,相同为0,不同为1.这对于2进制来说。不需要进位的加法,运算逻辑就是异或.
那进位部分怎么算呢,首先通过上面的例子可以看到只有当对应位置为1时才进位 .那么计算进位时,第一件事就是判断对应位置哪里有1, 同时对于非1的位置不做处理,只是单纯的得到进位部分 ,2进制除了0就是1现在只是处理对应位置的1,剩下的0的保持原样即可,符合这个条件的只有与运算了,因为进位对应数值需要到高位上去,所以需要左移一位。在将进位部分和非进位部分相加即可。

总的来说 如果对应位置没有1就是 a&b==0;相加的结果就是 a^ b ;如果对应位置有1就是 :a&b!=0;相加结果就是a ^ b+a&b<<1;但是进位都是低位往高位进的,对于一串二进制数来说,进位可能不仅仅至进位一次,从低位往高位挨个判断是否有1需要进位.
如果我们定义一个add函数来实现a+b,add(a,b) 实际上 就是求a^b+a&b<<1;这貌似有了一个公式 add(a,b)=add(a ^b,a&b<<1 ),这不就是递推公式吗,递推公式有了,但是递推的出口是什么呢?我们前面说了,如果没有1不就是直接a ^ b;直接对应位置异或就行了。边界条件也有了,就是a和b对应位置有没有1.

基于上述思路代码如下

nt Add(int num1, int num2 ) {
    
     if(num1&num2==0)
     {
         return num1^num2;
     }
    
     else

    return Add(num1^num2,num1&num2<<1) ;
}

在判断边界条件时返回值时num1 ^ num2,在说异或时0 ^a=a,这不相当于a+0=a,所以边界条件还可以改写一下

if(num1=0||num2=0)//加数有一个为0,直接返回另一个加数 符合加法逻辑

但是这道题如果用递归的话,时间复杂度太大了。过不了牛客测试用例。其实基本上所有的递归都可以改写成循环的形式来处理。既然递归的通不过我们直接写循环 既然是循环,那循环条件是什么呢?上面提到了有加数是0直接返回另一个加数,如果num2是0,直接返回num1,如果不是进入循环,从低位往高位判断对应位置是否都是1。这就说明b要不断更新,保证在对应位置没0的时候顺利跳出循环。异或运算实际并不会计算需要进位的位置,它只会保留本位的数值,9+4=10按照异或逻辑类似于只会保留0,1直接舍去。所以直接开始异或运算也不会影响到后续,当两数相加需要进位时,可以把位进后的结果保留,在进行对应位置的不进位的加法运算。这个把位进了的过程就是a&b<<1 类比 9+4的10进制计算,9+4=13 1直接舍去保留3, 9+1=10 把位进了 ,然后 10+(3)=13;每一次进位后进行对应位置的不进位的加法计算。什么时候停下种重复计算呢,毫无疑问就是当没有进位计算的时候,也就是说b中的1消耗完的时候,就是相与之后为0的时候,b的重新赋值既保留了进位后的结果,也保证了能顺利跳出循环


add(int a ,int b)
{
     while(b!=0)      
    { int tem=a^b;  
     b=(a&b<<1);
     a=tem;    
    }
    return a;
}

9+4=13 舍去1 保留3 就是03 ; 9+4=13,舍去3,保留1,就是10;最后就是10+03 =13
对于加法计算实际上是拆分了两部分计算 进位计算 不进位对应位置计算,每一次进位后 都要进行对 对应位置 不进位计算 实际上这也就是加法运算规则。然后重复上述的 *** 作 直到没有进位计算为止

这道题在《剑指offer》上也有出现。力扣上也有这道题但是力扣的题目要求更多一点,牛客上只能算正数,算不了负数,其实算负数就相当于不用四则运算实现了减法,加上一个数的相反数等于减去这个数

力扣题目链接不用四则运算做加法

因为上述代码只能算正整数,正整数的补码与原码相同,负整数的补码为其原码除符号位外的所有位取反后加 1。因为每一次拆分都可以让需要进位的最低位至少左移一位。符号位与数值要一起参与运算,要保证这一点。我们直接将进位的被结果保存到无符号整型中,然后异或完成不进位相加时,将保留的无符号整型赋值给b,来实现负数的相加。

int add(int a,int b)
{ w
    while(b)
    {
        unsigned int tem =(unsigned int)(a&b)<<1;
        a=a^b;
        b=tem;

    }
    return a;
}

这样实现的add函数除了算加法还可以算减法。

4.字符串相关问题 1. 牛客 单词倒排

题目链接 牛客 hj31

在字符串的相关练习的博客中,我提到了并实现reverse(反转)函数,就是将字符串的每个字符逆序,我们看到其实这道题也可以利用反转函数。我们把除了字母和空格外的所有字符都变成空格。在利用reverse函数处理字符串,和单词倒序那道题一样的做法,最后输出即可。这道题和单词倒序基本上没有太大的区别

单词倒序题目链接 牛客倒置字符串
基于上述思路代码如下

#include
#include

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}

int main()
{
	char str[10002] = { 0 };
	int len = 0;
	int i=0; 
	int flag = 0;
	gets(str);
	len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && 
		str[i] <= 'Z' || str[i] == ' ')
			continue;//这个循环停止是为了提高一点效率
		else
		{
			str[i] = ' ';
			//将字符串中除字母和空格以外的位置都替换为空格
		}
	}

	char* start =str ;

	while (*start != ')'char
	{
		*= end ; startwhile
		( *!=end ' ' && * !=end ')' ++;
		{
			end}reverse
		(
		,-start1 end ) ;if(

		* !=')'end = +1
			start ; end else =;
		}
			start reverse end(

	,
	+-str1 str)len;puts()
	;returnstr0;
   } 反转函数的实现我就不多说了,还是想提下我第一次做倒置单词的时候,我曾经将start end同时定义在while循环外部,程序出错了,因为end更新指向时空格时,需要跳出循环,之后的end需要再次进入第二个while中指向下一个单词结尾处的空格或者当end每次跳出第二个循环时必须进行判断,end是因为空格跳出来的还是因为void跳出来的,如果是空格那就end+1,start指向下一个单词的开头,如果不是空格,那就一定是string_revolve,这个时候只用start直接等于end不用加1,因为这说明最后一个单词已经是逆序完了,直接跳出循环即可。,如果在循环外部定义end,之后的end再也不会进入第二个while更新了,所以必须再将下个单词的起始位置start赋给end.因此在不想引入第三个变量的前提下,需要将end定义在while循环内。(
char

*
,

2.左旋字符串

这道题我们通常想到的做法就是 我们将字符串的符串挨个往前挪动一步,同时将字符串首字符保存,挪动完了再将字符串的首字符移动到末尾,重复上述步骤,直到将k个字符挪动完毕

基于上述思路写出如下代码

int ,int)//1将第一个字符保存str//2每个字符都往前挪动//3将第一个字符放在末尾,并且循环往返 kfor( lenint
{  =
	0
	;
	< ;++ i ) char= i * k; ifor(
	 {
		int tem = 0str;
		< -1 j ; ++) j * len(+) j=*
		{
			(+str+j1 ) ;}str * j(+-1
		)
		=;str } len } len%k voidreverse tem(

	  char

 *

这种方法就属于暴力枚举,挨个挪动,如果有7个字符的字符串挪动7次以后就复原了,所以可以用,将这个结果作为循环挪动的次数
除了上述的做法外还有一种方法还是利用到reverse翻转函数,

所以先将字符串分为2部分,先各自逆序翻转,最后整体反转
代码如下


char *)while( left< )char right=
{
	* ;left * right=
	{
		* tem ; *left=
		;left ++ ;right--
		;right } tem}
		leftintmain
		right()

	char

[

] ="ABCD"}
{
	; str//A DCB  BCDAint = { strlen ();
	int len = 2;str//旋转次数reverse
	( k , +-1
	);str//先旋转单个部分 str reverse k(+,+-
	1)str ; k//在旋转后半部分整体 str reverse len ( ,+-1
	);str//旋转整个字符串 str printf len ( "%s",);
	}intfind( strconstchar
*

3.左旋判断


既然左旋都会了,判断就很容易,求出字符串的长度,然后挨个左旋判断,如果是就返回对应的左旋次数。如果有7个字符的字符串,左旋7次都没有匹配上,直接返回0.任选上述两种左旋方式都可以解决这个问题。
那还有其他的方法吗?我们再原有的字符串上基础上再追加它本身,那么它所有的左旋结果都是这个追加后的字符串的子串
ABCDE的所有左旋结果都是 ABCDEABCDE 的子串
这样我们直接用库函数实现即可
代码如下

, char*) char [ src256 ] = find0
{
	} tmp;//用一个辅助空间将原字符串做成两倍原字符串strcpy ( { , ); //先拷贝一遍
	char*tmp= srcstrcat( ,
	);ret//再连接一遍 if(tmp!= srcNULL) return
	1;ret}return0
	{
	  ;  }
	
  esle 
   [+++]
[+++]

其实还可以直接在原字符串上直接追加它本身在用strstr查找匹配,但是会改变原字符串内容。

3.总结

1.关于元素重合问题,将元素转为数组下标,然后直接置数。注意一点数组的元素个数是决定了数组的下标值的范围,数组下标最大值一定是要大于等于元素最大值的。
2.逻辑运算和位运算,需要总结并且不断练习实践。
3.字符串问题,逆序反转函数很有用,做题以前可以先观察输入和输出之间有没有联系。
4.编程需要多实践,做的题多了,思维就会更加开阔。同时要及时复盘总结。
5.以上的解法都没有用到特别高深的算法和复杂的数据结构。可能处理方式比较巧妙一点,但是我觉得不要为自己懒刷题找借口,认为自己数据结构什么都不会,就不能去做力扣题和牛客题。只要肯学,肯练。一切都会慢慢好起来的。这句话是对我自己说的。显然我现在也还不会数据结构,但是我相信再寒假之前一定会有长进的!
6.以上解法不一定是最优解,只是我个人的浅薄见解,内容如有问题欢迎指正!

)
File: /www/wwwroot/outofmemory.cn/tmp/route_read.php, Line: 126, InsideLink()
File: /www/wwwroot/outofmemory.cn/tmp/index.inc.php, Line: 165, include(/www/wwwroot/outofmemory.cn/tmp/route_read.php)
File: /www/wwwroot/outofmemory.cn/index.php, Line: 30, include(/www/wwwroot/outofmemory.cn/tmp/index.inc.php)
Error[8]: Undefined offset: 1512, File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 121
File: /www/wwwroot/outofmemory.cn/tmp/plugin_ss_superseo_model_superseo.php, Line: 473, decode(

文章目录


前言

编程是需要不断练习实践的,所以刷题是很有必要的。但是不能盲目的刷题,要对做过的题题目进行总结复盘。以下是我对暑假期间做过的题目的部分总结,做个简单的记录。


1、重合元素问题 1.力扣645 错误的集合

题目链接力扣645

题目的要求就是在1到n中查找重复的数字和丢失的数字,我们先这样思考一下假如集合中1到n没有发生丢失,1到n就是自然数顺序排列,这样和我们数组的下标是和契合的,数组的下标就是0到n-1的自然数顺序数列,那我们将集合的每个元素减1当作另一个数组的下标来使用,将这个数组的所有的元素的元素初始化都置为0,再用集合中元素当作此数组下标,进行遍历加1,因为有重复的数据,所以数组中某个位置处肯定是2,找到这个2的位置,也就是数组的下标,这个下标就是重复的数据,因为丢失了某个数据。也就是说数组的某个位置没有加1,还是初始值0,找到0所对应的下标就是丢失的数据。

基于上述思路写出如下代码

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    *returnSize=2;
    int* arr1;
    arr1=(int*)malloc(sizeof(int)*2);
    int* arr2;
    arr2=calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]-1]++;
    }
    for(int j=0;j<numsSize;j++)
    {
        if(arr2[j]==2)
          {
              arr1[0]=j+1;
          }
          else if(arr2[j]==0)
          {
              arr1[1]=j+1;
          }
    }
  return arr1;
}

在这里说一下,力扣是接口型oj,,函数的返回值和参数都已经写好固定了,只要完善这个函数即可。这个代码中calloc函数是动态分配空间,并且将分配的空间的元素都置为0,有类似于初始化的作用,malloc函数只是分配空间.
因为数组的下标是从0开始的,所以将集合中元素当作下标的时候减1,同时在找丢失的数据和重复的数据的时候需要再把这个1加回来,当然也可以多申请一个空间,这样就不用加1减1了,但是要注意集合的下标不要越界。
arr2[nums[i]-1]这是十分最主要的一步。
这道题其实就是处理元素重合问题,处理这种问题,将要处理的集合元素转化为另一个数组的下标是一种很有用的方法。

2.力扣349求两个数的交集

题目链接 力扣349题

这道题也是重和的问题,还可以利用上述的方法。将集合的元素转化成数组的下标,只不过不用加1,我们直接将数组元素置为一个数,因为要处理两个集合,这两个集合的元素不确定出现多少次,比如2在集合1和集合2中重复3次,3在集合1和集合2出现了1次,如果还是采用加加的 *** 作 不好通过数组的元素的值判断重复的元素,直接将给数组元素置数赋值,就可以很好的处理了
基于上述思路,写出如下代码

int* intersection(int* nums1, int nums1Size, int* nums2,
 int nums2Size, int* returnSize)
 {
*returnSize=0;
int* arr=calloc(10001,sizeof(int));
int* return_arr=malloc(10001*sizeof(int));
for(int i=0;i<nums1Size;i++)
{
    arr[nums1[i]]=1;
   
 }
   
 for(int j=0;j<nums2Size;j++)
 {
     if(arr[nums2[j]]==1)
     {
         arr[nums2[j]]=2;
     }
 }

 for(int k=0;k<1001;k++)
 {
     if(arr[k]==2)
     {
         return_arr[*returnSize]=k;
         *returnSize+=1;
     }
 }
 return return_arr;

}

我们先将集合1元素当作数组下标,并且将数组元素置为1,接着再将集合2的元素当作数组下标,再里面找1,如果找到了1,这个位置的下标就是两个集合中相同的元素,那么为了找到这个下标,直接将其置为2,就一步就相当于对数组该位置进行标记。最后在数组中找到2对应的下标,这个下标就是重复的元素,因为我没有减1,直接用的集和元素,所以在下标就是重复元素,就不用再去减1了。同时题目给了集合元素个数范围,为了避免空间不够,我就申请了10001*4字节的空间

3. 牛客HJ10 字符个数统计

题目链接字符统计个数

这道题还是元素重和问题,还是老方法,将字符串每个字符转成另一个数组的下标来处理。因为题目说了多个相同只算一次,同时字符串也没有空格。还是直接数组元素置数。

代码如下

#include
int word_count(char* str, int len)
{
    int arr[127] = { 0 };
    int count = 0;
    for (int i = 0; i < len; i++)
    {
        arr[str[i]] = 1;
    }
    for (int i = 0; i < 127; i++)
    {
        if (arr[i] == 1)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    char str[5001] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int ret = word_count(str, len);
    printf("%d", ret);
    return 0;
}

之所以将数组的个数设置成127因为字符对应的ASCII值最大为127,也就是字符串字符作为数组下标时最大只能到127.将数组元素置为1,在判断如果数组元素时1,计数器加1,这样置数赋值,就算有重复的字符也只计算一次。

4.力扣448找到数组中消失的数字

题目链接 力扣448题

这题和第一道例题特别相似,题目还是关于元素重合问题,这个找没有出现的的元素,第一道例题是找丢失的元素,很明显题目是换了个马甲,还是老方法处理转成数组下标然后置数赋值

基于以上思路,写出如下代码

int* findDisappearedNumbers(int* nums, int numsSize,int* returnSize)
{
     *returnSize=0;
    int* arr1=(int*)malloc(sizeof(int)*(numsSize+1));
    int* arr2=calloc((numsSize+1),sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]]=1;
    }
    for(int j=1;j<numsSize+1;j++)
    {
        if(arr2[j]==0)
          {
              arr1[*returnSize]=j;
              *returnSize+=1;
          }
          
    }
  return arr1;
}

利用calloc函数将开辟的空间中的元素初始化为0.将集合的元素转化为数组下标,这次我直接将集合中的元素转为下标没有减1,然后置1进行判断找到还是0的元素下标,但是要注意一点就是由于集合元素转为数组下标时没有减1,开辟空间是需要比集合的元素个数多一个的。因为数组的元素个数是和决定了数组元素下标最大值的,数组下标必须要满足大于等于集合中的最大元素的。

2.杂题汇总 1.摩尔投票法

题目链接 力扣169

题目描述,集合中一定有一个出现次数的最多的元素,找出来这个元素。这道题用摩尔投票法可以轻松解决。什么是摩尔投票法,这里先不说卖个关子,我们直接看代码分析

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

摩尔投票法,听着名字挺唬人的。按照我自己理解就是一换一厮杀法 求解数组中最多元素问题 。假如在3国时,蜀吴各有两千士兵,现在魏国有1万士兵,现在3国进行决战,魏蜀吴的士兵每个士兵都只能一换一同归于尽,那么最后打赢的一定是魏国。因为3方士兵只能一换一,魏国士兵最多。这个厮杀的过程就是在找出现次数最多的元素,为了模拟这个厮杀过程 可以用一个计数器来表示,将不同的元素想象成不同国家的士兵 ,计数器来表示生命值 ,遇到相同士兵计数器就加一, 表示结成阵营, 不同的就减一 ,表示一换一杀死了一个士兵。一旦计数器为0,就换下一个兵种,最后剩下的就是人数最多的士兵。我们最开始的时候直接将第一个元素当作出现次数最多的,这个时候相当于有了一个士兵,所以就有了一条命,计数器要赋值成1.然后进行厮杀,如果某次计数器为0,就表示某国的士兵死完了,换下一个国家的士兵继续厮杀。注意一点我在代码中写的是else if不是if,如果是if就会同时判断,类似于并行的关系。用了elsi fi是类似于递进的,上一个不满足时才会判断下一个

2.除自身以外所有元素的乘积

题目链接 力扣238题

这道题确实有难懂,我暑假琢磨了很久才弄懂
题目要求就是将元素对应位置的地方放置除了它本身外和其他元素的乘积,我们这样思考一下,假如我以每个元素的位置为分界线 将左边部分的乘积按顺序放放在一个数组中,将右边部分的乘积按顺序放在另一个数组中,如果分界线元素在两个端点处,所对应的乘积直接为1,在将这两个数组对应位置相乘即为所求

这样说比较抽象直接画图举例

基于上述思路写出如下代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* nums_return = malloc(numsSize * 4);
    int  left =1;
    int right = 1;
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums_return[i]=left;
        left=left*nums[i];
    }
   
   for(int j=numsSize-1;j>=0;j--) 
   {
    
    nums_return[j]=nums_return[j]*right;
    right=right*nums[j];
   }
    return nums_return;


}

上面为了解题思路更加清晰,特意引入了两个数组来说明这个解题过程,我们发现保存左端元素之积的位置和保存右端元素之积的位置都是一一对应的,所以只用将左端或者右端元素之积保存到一个数组中,在遍历这数组挨个乘上右端或者左端元素之积并且进行保存。左端元素之积叫做前缀之积,右端元素之积叫做后缀之积

3至少是其他数字的两倍

题目链接 力扣747

这道题有很多细节需要处理,要对问题考虑全面才能通过所有的测试用例。首先这个最大的数是要满足它至少是别的每个数的两倍,那么我们思考一下这个数最小应该是多少,最少应该是第二大的数的两倍,那么我们就把这个问题转化成了找数组中最大的数,和第二大的数。这样就比较好处理了

基于上述思路写出如下代码

int dominantIndex(int* nums, int numsSize){
    int flag=-1;
    int frist;
    int second ;
    if(nums[0]>nums[1])
    {
        frist=nums[0];
        second=nums[1];
        flag=0;
    }
    if(nums[0]<nums[1])
    {
        frist=nums[1];
        second=nums[0];
        flag=1;

    }
    if(numsSize==1)
    {
        return 0;
    }
    
   for(int i=2;i<numsSize;i++)
   {   
       if(nums[i]>frist)
       {  second=frist;
           frist=nums[i];
           flag=i;
           
       }
       else 
       {
         second=(second>nums[i]?second:nums[i]);
        
       }
   }
 if(frist>=2*second)
 {
     return flag;
 }
 else
 return -1;
}

我们在找一个数组中最大的元素一般做法就是将数组首元素赋值给变量max,然后遍历数组,这样赋初值的原因就是保证max在这个数组范围内的,不能脱离这个范围。因此我们在赋初值的时候将数组首元素和第二个元素赋值给frist second ,同时用flag记录frist的下标。直接就是进行遍历了,挨个比较交互,但是为什么要加上else 呢?我们在赋值的是直接将数组第一个元素和第二个元素给了两个变量,如果数组最大的元素就在这两个位置之中,first确实是最大元素,但是能保证second就是第二大的元素吗?如果没有elseif 语句,frist不会进入if语句中去,所有根本无法保证second就是第二大的数,所以要有一个else 同时i=2开始循环的,也不担心出现frist和second相同的情况

4.珠玑妙算

题目链接 力扣面试题16.15.

其实这个题目我当时想了好一会才读懂,期间将题目理解错了,导致一直不能过全部测试用例。我当时以为伪猜中就是在对应位置不相等的前提下,guess是solution的子集。实际上不是这样的,对应位置如果相同算猜中,同时这个字符不会再参与伪猜中的比较,同时在对应位置不相等的前提下,对于solution中出现过一次的元素,guess哪怕出现多次也只是按一次计算,但是对应位置不相同的前提下,soloution中某个字符出现多次的话,guess也出现多次实际上要算多次的,这多次的次数是以soloution中的次数为准的,其实对于同一个元素的伪猜中,最多的次数就是两次。因为只有4个位置还要保持对应位置不相等,对于同一个字符来说最多只能出现在两个位置上。

题目要求弄懂了,具体怎么解决呢?我还是采用元素重合问题处理,将guess和solution元素转为下标,很明显这里不能用置数的因为重复的元素可能也会参与计数。于是只能用加加 *** 作了。这个还有个要处理的点就是计数,计数是以solution中的元素为准的,哪怕gusee出现多次也不参与计数。同时元素当作数组下标其实充当了计数功能的出现一次加一次,又因为会有重复元素重复计数问题,直接取guess和solutions所对应数组的元素最小值。同时这样做猜中也是会被计算在内的,最后减去猜中的次数即可

代码如下

int* masterMind(char* solution, char* guess, int* returnSize){
    *returnSize=2;
    int *nums=malloc(sizeof(int)*2);
    int count1=0;
    int count2=0;
    int arr1[26]={0};
    int arr2[26]={0};
    for(int i=0;i<4;i++)
    {
      if(solution[i]==guess[i])
      {
        count1++;
      }
    arr1[solution[i]-65]++;
    arr2[guess[i]-65]++;
    }

for(int j=0;j<26;j++)
{ 
    if(arr1[j]+arr2[j]>=2)
       {
           count2=(arr2[j]>arr1[j]?arr1[j]:arr2[j])+count2;;
       }
}
    
  if(count1==4)
    {
        nums[1]=0;
        nums[0]=4;
    }
  
   if(count2!=0)
    {
        nums[0]=count1;
        nums[1]=count2-count1;
    }

 if(count2==0)
   {
       nums[1]=0;
       nums[0]=0;
   }
   return nums;
}

同时对几种特殊情况判断就是 都猜中了,还有就是连伪猜中都没有。伪猜中都没有,猜中肯定也没有。因为都是小写字母,所以减了65,相当于减了个字符a.

3.移位 *** 作符和位 *** 作符相关问题 1.整数转换

题目链接 力扣面试题05.06整数转换

题目描述 需要改变多少个位才能将a转成b,这题实际上就是要求a和b有多少位是不同的,我们知道异或运算就是相同为0,不同为1,如果我们将a和b异或后,再求出这个异或后的数中有多少位是1,就解决了这个问题了

基于上述思路写出如下代码

int convertInteger(int A, int B){
    int n=A^B;
 int  count =0;
 for(int i=0;i<32;i++)
 {
     if((n>>i)&1)
     {
         count++;
     }
 }
  return count;
}



将a和b异或之后,在右移每一位于1进行与运算,如果该位是1,与运算后也是1,计数器加1,这个移位之后n的值本身没有发生改变,因为这里没有出现赋值行为,在之前的文章中求1的时候有这样的写法 n=n&(n-1),在这道题中是行不通的,因为题目给出的数据测试范围有部分有符号整数会溢出,不能用intl类型,但是题目的形参类型已经固定了,所以只能通过移位来计算的

2.牛客 寻找奇数

题目链接 KS33 寻找奇数

根据题目描述,只有一个数字是出现了奇数次数,其他都偶数次数。找到这个数字。在之前的文章中有介绍不引入第三个变量,利用异或运算交换两个数。异或运算有这样一个特性 a^a=0, a ^ 0=a,0 ^ 0=0,那么一个数经过偶数次异或本身,那么这个数就是0,奇数次异或就还是它本身,那么直接将0和这个数组的每个元素进行异或运算,因为出现偶数次数的数异或后还是0,0与0异或还是0,最后就只有0和和出现奇数次数的数异或,异或的结果就是这个数字。

写出如下代码

#include
int main()
{ int ret=0;
    int n =0;
    scanf("%d",&n);
    int nums[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    for(int j=0;j<n;j++)
    {
        ret=nums[j]^ret;
    }
 
 printf("%d",ret);
}

这题还是比较简单的,可能有时候想不到。我当时也没有马上想到还是题做少了,只要多编程实践并且总结,慢慢就会下笔如有神的。

3.不用加减乘除做加法

题目链接 牛客JZ65 不用加减乘除做加法

这道题猛一看感觉无从下手,其实在数电中可以用异或门和与门实现一个半加器。半加器是实现两个一位二进制数加法运算的器件。实际上就是利用异或运算和与运算,来实现了加法。这些位 *** 作都以2进制为基础来运算的,也就是题目是想要求我们以用2进制加法规则来实现10进制的计算.在实现之前我们先分析一下10进制的加法运算规则.
以5+4为例
05
+
04
________
09
这是没有进位的加法,4 和5除了本身的个位以外其余高位都是0,因为没有进位直接对应位置相加即可。那要是有进位怎么办呢?以9+4为例
9+4=(9+1)+3=10+3.我们先把需要进位的分部先进位,进位以后就还是对应位置直接相加即可。

说完10进制再来说2进制
2进制数除了0就是1,同时缝2进1,
也就是说 1+0 =1;0+1=1;0+0=0;1+1=1 0;
我们先不看进位的部分,就是说
1+0 =1 ; 0+1=1 ;0+0=0;1+1=0;(先不看进位部分),这样的运算结果是不是很像异或,相同为0,不同为1.这对于2进制来说。不需要进位的加法,运算逻辑就是异或.
那进位部分怎么算呢,首先通过上面的例子可以看到只有当对应位置为1时才进位 .那么计算进位时,第一件事就是判断对应位置哪里有1, 同时对于非1的位置不做处理,只是单纯的得到进位部分 ,2进制除了0就是1现在只是处理对应位置的1,剩下的0的保持原样即可,符合这个条件的只有与运算了,因为进位对应数值需要到高位上去,所以需要左移一位。在将进位部分和非进位部分相加即可。

总的来说 如果对应位置没有1就是 a&b==0;相加的结果就是 a^ b ;如果对应位置有1就是 :a&b!=0;相加结果就是a ^ b+a&b<<1;但是进位都是低位往高位进的,对于一串二进制数来说,进位可能不仅仅至进位一次,从低位往高位挨个判断是否有1需要进位.
如果我们定义一个add函数来实现a+b,add(a,b) 实际上 就是求a^b+a&b<<1;这貌似有了一个公式 add(a,b)=add(a ^b,a&b<<1 ),这不就是递推公式吗,递推公式有了,但是递推的出口是什么呢?我们前面说了,如果没有1不就是直接a ^ b;直接对应位置异或就行了。边界条件也有了,就是a和b对应位置有没有1.

基于上述思路代码如下

nt Add(int num1, int num2 ) {
    
     if(num1&num2==0)
     {
         return num1^num2;
     }
    
     else

    return Add(num1^num2,num1&num2<<1) ;
}

在判断边界条件时返回值时num1 ^ num2,在说异或时0 ^a=a,这不相当于a+0=a,所以边界条件还可以改写一下

if(num1=0||num2=0)//加数有一个为0,直接返回另一个加数 符合加法逻辑

但是这道题如果用递归的话,时间复杂度太大了。过不了牛客测试用例。其实基本上所有的递归都可以改写成循环的形式来处理。既然递归的通不过我们直接写循环 既然是循环,那循环条件是什么呢?上面提到了有加数是0直接返回另一个加数,如果num2是0,直接返回num1,如果不是进入循环,从低位往高位判断对应位置是否都是1。这就说明b要不断更新,保证在对应位置没0的时候顺利跳出循环。异或运算实际并不会计算需要进位的位置,它只会保留本位的数值,9+4=10按照异或逻辑类似于只会保留0,1直接舍去。所以直接开始异或运算也不会影响到后续,当两数相加需要进位时,可以把位进后的结果保留,在进行对应位置的不进位的加法运算。这个把位进了的过程就是a&b<<1 类比 9+4的10进制计算,9+4=13 1直接舍去保留3, 9+1=10 把位进了 ,然后 10+(3)=13;每一次进位后进行对应位置的不进位的加法计算。什么时候停下种重复计算呢,毫无疑问就是当没有进位计算的时候,也就是说b中的1消耗完的时候,就是相与之后为0的时候,b的重新赋值既保留了进位后的结果,也保证了能顺利跳出循环


add(int a ,int b)
{
     while(b!=0)      
    { int tem=a^b;  
     b=(a&b<<1);
     a=tem;    
    }
    return a;
}

9+4=13 舍去1 保留3 就是03 ; 9+4=13,舍去3,保留1,就是10;最后就是10+03 =13
对于加法计算实际上是拆分了两部分计算 进位计算 不进位对应位置计算,每一次进位后 都要进行对 对应位置 不进位计算 实际上这也就是加法运算规则。然后重复上述的 *** 作 直到没有进位计算为止

这道题在《剑指offer》上也有出现。力扣上也有这道题但是力扣的题目要求更多一点,牛客上只能算正数,算不了负数,其实算负数就相当于不用四则运算实现了减法,加上一个数的相反数等于减去这个数

力扣题目链接不用四则运算做加法

因为上述代码只能算正整数,正整数的补码与原码相同,负整数的补码为其原码除符号位外的所有位取反后加 1。因为每一次拆分都可以让需要进位的最低位至少左移一位。符号位与数值要一起参与运算,要保证这一点。我们直接将进位的被结果保存到无符号整型中,然后异或完成不进位相加时,将保留的无符号整型赋值给b,来实现负数的相加。

int add(int a,int b)
{ w
    while(b)
    {
        unsigned int tem =(unsigned int)(a&b)<<1;
        a=a^b;
        b=tem;

    }
    return a;
}

这样实现的add函数除了算加法还可以算减法。

4.字符串相关问题 1. 牛客 单词倒排

题目链接 牛客 hj31

在字符串的相关练习的博客中,我提到了并实现reverse(反转)函数,就是将字符串的每个字符逆序,我们看到其实这道题也可以利用反转函数。我们把除了字母和空格外的所有字符都变成空格。在利用reverse函数处理字符串,和单词倒序那道题一样的做法,最后输出即可。这道题和单词倒序基本上没有太大的区别

单词倒序题目链接 牛客倒置字符串
基于上述思路代码如下

#include
#include

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}

int main()
{
	char str[10002] = { 0 };
	int len = 0;
	int i=0; 
	int flag = 0;
	gets(str);
	len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && 
		str[i] <= 'Z' || str[i] == ' ')
			continue;//这个循环停止是为了提高一点效率
		else
		{
			str[i] = ' ';
			//将字符串中除字母和空格以外的位置都替换为空格
		}
	}

	char* start =str ;

	while (*start != ')'char
	{
		*= end ; startwhile
		( *!=end ' ' && * !=end ')' ++;
		{
			end}reverse
		(
		,-start1 end ) ;if(

		* !=')'end = +1
			start ; end else =;
		}
			start reverse end(

	,
	+-str1 str)len;puts()
	;returnstr0;
   } 反转函数的实现我就不多说了,还是想提下我第一次做倒置单词的时候,我曾经将start end同时定义在while循环外部,程序出错了,因为end更新指向时空格时,需要跳出循环,之后的end需要再次进入第二个while中指向下一个单词结尾处的空格或者当end每次跳出第二个循环时必须进行判断,end是因为空格跳出来的还是因为void跳出来的,如果是空格那就end+1,start指向下一个单词的开头,如果不是空格,那就一定是string_revolve,这个时候只用start直接等于end不用加1,因为这说明最后一个单词已经是逆序完了,直接跳出循环即可。,如果在循环外部定义end,之后的end再也不会进入第二个while更新了,所以必须再将下个单词的起始位置start赋给end.因此在不想引入第三个变量的前提下,需要将end定义在while循环内。(
char

*
,

2.左旋字符串

这道题我们通常想到的做法就是 我们将字符串的符串挨个往前挪动一步,同时将字符串首字符保存,挪动完了再将字符串的首字符移动到末尾,重复上述步骤,直到将k个字符挪动完毕

基于上述思路写出如下代码

int ,int)//1将第一个字符保存str//2每个字符都往前挪动//3将第一个字符放在末尾,并且循环往返 kfor( lenint
{  =
	0
	;
	< ;++ i ) char= i * k; ifor(
	 {
		int tem = 0str;
		< -1 j ; ++) j * len(+) j=*
		{
			(+str+j1 ) ;}str * j(+-1
		)
		=;str } len } len%k voidreverse tem(

	  char

 *

这种方法就属于暴力枚举,挨个挪动,如果有7个字符的字符串挪动7次以后就复原了,所以可以用,将这个结果作为循环挪动的次数
除了上述的做法外还有一种方法还是利用到reverse翻转函数,

所以先将字符串分为2部分,先各自逆序翻转,最后整体反转
代码如下


char *)while( left< )char right=
{
	* ;left * right=
	{
		* tem ; *left=
		;left ++ ;right--
		;right } tem}
		leftintmain
		right()

	char

[

] ="ABCD"}
{
	; str//A DCB  BCDAint = { strlen ();
	int len = 2;str//旋转次数reverse
	( k , +-1
	);str//先旋转单个部分 str reverse k(+,+-
	1)str ; k//在旋转后半部分整体 str reverse len ( ,+-1
	);str//旋转整个字符串 str printf len ( "%s",);
	}intfind( strconstchar
*

3.左旋判断


既然左旋都会了,判断就很容易,求出字符串的长度,然后挨个左旋判断,如果是就返回对应的左旋次数。如果有7个字符的字符串,左旋7次都没有匹配上,直接返回0.任选上述两种左旋方式都可以解决这个问题。
那还有其他的方法吗?我们再原有的字符串上基础上再追加它本身,那么它所有的左旋结果都是这个追加后的字符串的子串
ABCDE的所有左旋结果都是 ABCDEABCDE 的子串
这样我们直接用库函数实现即可
代码如下

, char*) char [ src256 ] = find0
{
	} tmp;//用一个辅助空间将原字符串做成两倍原字符串strcpy ( { , ); //先拷贝一遍
	char*tmp= srcstrcat( ,
	);ret//再连接一遍 if(tmp!= srcNULL) return
	1;ret}return0
	{
	  ;  }
	
  esle 
   
[+++]

其实还可以直接在原字符串上直接追加它本身在用strstr查找匹配,但是会改变原字符串内容。

3.总结

1.关于元素重合问题,将元素转为数组下标,然后直接置数。注意一点数组的元素个数是决定了数组的下标值的范围,数组下标最大值一定是要大于等于元素最大值的。
2.逻辑运算和位运算,需要总结并且不断练习实践。
3.字符串问题,逆序反转函数很有用,做题以前可以先观察输入和输出之间有没有联系。
4.编程需要多实践,做的题多了,思维就会更加开阔。同时要及时复盘总结。
5.以上的解法都没有用到特别高深的算法和复杂的数据结构。可能处理方式比较巧妙一点,但是我觉得不要为自己懒刷题找借口,认为自己数据结构什么都不会,就不能去做力扣题和牛客题。只要肯学,肯练。一切都会慢慢好起来的。这句话是对我自己说的。显然我现在也还不会数据结构,但是我相信再寒假之前一定会有长进的!
6.以上解法不一定是最优解,只是我个人的浅薄见解,内容如有问题欢迎指正!

)
File: /www/wwwroot/outofmemory.cn/tmp/route_read.php, Line: 126, InsideLink()
File: /www/wwwroot/outofmemory.cn/tmp/index.inc.php, Line: 165, include(/www/wwwroot/outofmemory.cn/tmp/route_read.php)
File: /www/wwwroot/outofmemory.cn/index.php, Line: 30, include(/www/wwwroot/outofmemory.cn/tmp/index.inc.php)
C语言解题报告_C_内存溢出

C语言解题报告

C语言解题报告,第1张

文章目录
  • 前言
  • 1、重合元素问题
    • 1.力扣645 错误的集合
    • 2.力扣349求两个数的交集
    • 3. 牛客HJ10 字符个数统计
    • 4.力扣448找到数组中消失的数字
  • 2.杂题汇总
    • 1.摩尔投票法
    • 2.除自身以外所有元素的乘积
    • 3至少是其他数字的两倍
    • 4.珠玑妙算
  • 3.移位 *** 作符和位 *** 作符相关问题
    • 1.整数转换
    • 2.牛客 寻找奇数
    • 3.不用加减乘除做加法
  • 4.字符串相关问题
    • 1. 牛客 单词倒排
    • 2.左旋字符串
    • 3.左旋判断
  • 3.总结


前言

编程是需要不断练习实践的,所以刷题是很有必要的。但是不能盲目的刷题,要对做过的题题目进行总结复盘。以下是我对暑假期间做过的题目的部分总结,做个简单的记录。


1、重合元素问题 1.力扣645 错误的集合

题目链接力扣645

题目的要求就是在1到n中查找重复的数字和丢失的数字,我们先这样思考一下假如集合中1到n没有发生丢失,1到n就是自然数顺序排列,这样和我们数组的下标是和契合的,数组的下标就是0到n-1的自然数顺序数列,那我们将集合的每个元素减1当作另一个数组的下标来使用,将这个数组的所有的元素的元素初始化都置为0,再用集合中元素当作此数组下标,进行遍历加1,因为有重复的数据,所以数组中某个位置处肯定是2,找到这个2的位置,也就是数组的下标,这个下标就是重复的数据,因为丢失了某个数据。也就是说数组的某个位置没有加1,还是初始值0,找到0所对应的下标就是丢失的数据。

基于上述思路写出如下代码

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    *returnSize=2;
    int* arr1;
    arr1=(int*)malloc(sizeof(int)*2);
    int* arr2;
    arr2=calloc(numsSize,sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]-1]++;
    }
    for(int j=0;j<numsSize;j++)
    {
        if(arr2[j]==2)
          {
              arr1[0]=j+1;
          }
          else if(arr2[j]==0)
          {
              arr1[1]=j+1;
          }
    }
  return arr1;
}

在这里说一下,力扣是接口型oj,,函数的返回值和参数都已经写好固定了,只要完善这个函数即可。这个代码中calloc函数是动态分配空间,并且将分配的空间的元素都置为0,有类似于初始化的作用,malloc函数只是分配空间.
因为数组的下标是从0开始的,所以将集合中元素当作下标的时候减1,同时在找丢失的数据和重复的数据的时候需要再把这个1加回来,当然也可以多申请一个空间,这样就不用加1减1了,但是要注意集合的下标不要越界。
arr2[nums[i]-1]这是十分最主要的一步。
这道题其实就是处理元素重合问题,处理这种问题,将要处理的集合元素转化为另一个数组的下标是一种很有用的方法。

2.力扣349求两个数的交集

题目链接 力扣349题

这道题也是重和的问题,还可以利用上述的方法。将集合的元素转化成数组的下标,只不过不用加1,我们直接将数组元素置为一个数,因为要处理两个集合,这两个集合的元素不确定出现多少次,比如2在集合1和集合2中重复3次,3在集合1和集合2出现了1次,如果还是采用加加的 *** 作 不好通过数组的元素的值判断重复的元素,直接将给数组元素置数赋值,就可以很好的处理了
基于上述思路,写出如下代码

int* intersection(int* nums1, int nums1Size, int* nums2,
 int nums2Size, int* returnSize)
 {
*returnSize=0;
int* arr=calloc(10001,sizeof(int));
int* return_arr=malloc(10001*sizeof(int));
for(int i=0;i<nums1Size;i++)
{
    arr[nums1[i]]=1;
   
 }
   
 for(int j=0;j<nums2Size;j++)
 {
     if(arr[nums2[j]]==1)
     {
         arr[nums2[j]]=2;
     }
 }

 for(int k=0;k<1001;k++)
 {
     if(arr[k]==2)
     {
         return_arr[*returnSize]=k;
         *returnSize+=1;
     }
 }
 return return_arr;

}

我们先将集合1元素当作数组下标,并且将数组元素置为1,接着再将集合2的元素当作数组下标,再里面找1,如果找到了1,这个位置的下标就是两个集合中相同的元素,那么为了找到这个下标,直接将其置为2,就一步就相当于对数组该位置进行标记。最后在数组中找到2对应的下标,这个下标就是重复的元素,因为我没有减1,直接用的集和元素,所以在下标就是重复元素,就不用再去减1了。同时题目给了集合元素个数范围,为了避免空间不够,我就申请了10001*4字节的空间

3. 牛客HJ10 字符个数统计

题目链接字符统计个数

这道题还是元素重和问题,还是老方法,将字符串每个字符转成另一个数组的下标来处理。因为题目说了多个相同只算一次,同时字符串也没有空格。还是直接数组元素置数。

代码如下

#include
int word_count(char* str, int len)
{
    int arr[127] = { 0 };
    int count = 0;
    for (int i = 0; i < len; i++)
    {
        arr[str[i]] = 1;
    }
    for (int i = 0; i < 127; i++)
    {
        if (arr[i] == 1)
        {
            count++;
        }
    }
    return count;
}
int main()
{
    char str[5001] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int ret = word_count(str, len);
    printf("%d", ret);
    return 0;
}

之所以将数组的个数设置成127因为字符对应的ASCII值最大为127,也就是字符串字符作为数组下标时最大只能到127.将数组元素置为1,在判断如果数组元素时1,计数器加1,这样置数赋值,就算有重复的字符也只计算一次。

4.力扣448找到数组中消失的数字

题目链接 力扣448题

这题和第一道例题特别相似,题目还是关于元素重合问题,这个找没有出现的的元素,第一道例题是找丢失的元素,很明显题目是换了个马甲,还是老方法处理转成数组下标然后置数赋值

基于以上思路,写出如下代码

int* findDisappearedNumbers(int* nums, int numsSize,int* returnSize)
{
     *returnSize=0;
    int* arr1=(int*)malloc(sizeof(int)*(numsSize+1));
    int* arr2=calloc((numsSize+1),sizeof(int));
    for(int i=0;i<numsSize;i++)
    {
        arr2[nums[i]]=1;
    }
    for(int j=1;j<numsSize+1;j++)
    {
        if(arr2[j]==0)
          {
              arr1[*returnSize]=j;
              *returnSize+=1;
          }
          
    }
  return arr1;
}

利用calloc函数将开辟的空间中的元素初始化为0.将集合的元素转化为数组下标,这次我直接将集合中的元素转为下标没有减1,然后置1进行判断找到还是0的元素下标,但是要注意一点就是由于集合元素转为数组下标时没有减1,开辟空间是需要比集合的元素个数多一个的。因为数组的元素个数是和决定了数组元素下标最大值的,数组下标必须要满足大于等于集合中的最大元素的。

2.杂题汇总 1.摩尔投票法

题目链接 力扣169

题目描述,集合中一定有一个出现次数的最多的元素,找出来这个元素。这道题用摩尔投票法可以轻松解决。什么是摩尔投票法,这里先不说卖个关子,我们直接看代码分析

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

摩尔投票法,听着名字挺唬人的。按照我自己理解就是一换一厮杀法 求解数组中最多元素问题 。假如在3国时,蜀吴各有两千士兵,现在魏国有1万士兵,现在3国进行决战,魏蜀吴的士兵每个士兵都只能一换一同归于尽,那么最后打赢的一定是魏国。因为3方士兵只能一换一,魏国士兵最多。这个厮杀的过程就是在找出现次数最多的元素,为了模拟这个厮杀过程 可以用一个计数器来表示,将不同的元素想象成不同国家的士兵 ,计数器来表示生命值 ,遇到相同士兵计数器就加一, 表示结成阵营, 不同的就减一 ,表示一换一杀死了一个士兵。一旦计数器为0,就换下一个兵种,最后剩下的就是人数最多的士兵。我们最开始的时候直接将第一个元素当作出现次数最多的,这个时候相当于有了一个士兵,所以就有了一条命,计数器要赋值成1.然后进行厮杀,如果某次计数器为0,就表示某国的士兵死完了,换下一个国家的士兵继续厮杀。注意一点我在代码中写的是else if不是if,如果是if就会同时判断,类似于并行的关系。用了elsi fi是类似于递进的,上一个不满足时才会判断下一个

2.除自身以外所有元素的乘积

题目链接 力扣238题

这道题确实有难懂,我暑假琢磨了很久才弄懂
题目要求就是将元素对应位置的地方放置除了它本身外和其他元素的乘积,我们这样思考一下,假如我以每个元素的位置为分界线 将左边部分的乘积按顺序放放在一个数组中,将右边部分的乘积按顺序放在另一个数组中,如果分界线元素在两个端点处,所对应的乘积直接为1,在将这两个数组对应位置相乘即为所求

这样说比较抽象直接画图举例

基于上述思路写出如下代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    int* nums_return = malloc(numsSize * 4);
    int  left =1;
    int right = 1;
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++)
    {
        nums_return[i]=left;
        left=left*nums[i];
    }
   
   for(int j=numsSize-1;j>=0;j--) 
   {
    
    nums_return[j]=nums_return[j]*right;
    right=right*nums[j];
   }
    return nums_return;


}

上面为了解题思路更加清晰,特意引入了两个数组来说明这个解题过程,我们发现保存左端元素之积的位置和保存右端元素之积的位置都是一一对应的,所以只用将左端或者右端元素之积保存到一个数组中,在遍历这数组挨个乘上右端或者左端元素之积并且进行保存。左端元素之积叫做前缀之积,右端元素之积叫做后缀之积

3至少是其他数字的两倍

题目链接 力扣747

这道题有很多细节需要处理,要对问题考虑全面才能通过所有的测试用例。首先这个最大的数是要满足它至少是别的每个数的两倍,那么我们思考一下这个数最小应该是多少,最少应该是第二大的数的两倍,那么我们就把这个问题转化成了找数组中最大的数,和第二大的数。这样就比较好处理了

基于上述思路写出如下代码

int dominantIndex(int* nums, int numsSize){
    int flag=-1;
    int frist;
    int second ;
    if(nums[0]>nums[1])
    {
        frist=nums[0];
        second=nums[1];
        flag=0;
    }
    if(nums[0]<nums[1])
    {
        frist=nums[1];
        second=nums[0];
        flag=1;

    }
    if(numsSize==1)
    {
        return 0;
    }
    
   for(int i=2;i<numsSize;i++)
   {   
       if(nums[i]>frist)
       {  second=frist;
           frist=nums[i];
           flag=i;
           
       }
       else 
       {
         second=(second>nums[i]?second:nums[i]);
        
       }
   }
 if(frist>=2*second)
 {
     return flag;
 }
 else
 return -1;
}

我们在找一个数组中最大的元素一般做法就是将数组首元素赋值给变量max,然后遍历数组,这样赋初值的原因就是保证max在这个数组范围内的,不能脱离这个范围。因此我们在赋初值的时候将数组首元素和第二个元素赋值给frist second ,同时用flag记录frist的下标。直接就是进行遍历了,挨个比较交互,但是为什么要加上else 呢?我们在赋值的是直接将数组第一个元素和第二个元素给了两个变量,如果数组最大的元素就在这两个位置之中,first确实是最大元素,但是能保证second就是第二大的元素吗?如果没有elseif 语句,frist不会进入if语句中去,所有根本无法保证second就是第二大的数,所以要有一个else 同时i=2开始循环的,也不担心出现frist和second相同的情况

4.珠玑妙算

题目链接 力扣面试题16.15.

其实这个题目我当时想了好一会才读懂,期间将题目理解错了,导致一直不能过全部测试用例。我当时以为伪猜中就是在对应位置不相等的前提下,guess是solution的子集。实际上不是这样的,对应位置如果相同算猜中,同时这个字符不会再参与伪猜中的比较,同时在对应位置不相等的前提下,对于solution中出现过一次的元素,guess哪怕出现多次也只是按一次计算,但是对应位置不相同的前提下,soloution中某个字符出现多次的话,guess也出现多次实际上要算多次的,这多次的次数是以soloution中的次数为准的,其实对于同一个元素的伪猜中,最多的次数就是两次。因为只有4个位置还要保持对应位置不相等,对于同一个字符来说最多只能出现在两个位置上。

题目要求弄懂了,具体怎么解决呢?我还是采用元素重合问题处理,将guess和solution元素转为下标,很明显这里不能用置数的因为重复的元素可能也会参与计数。于是只能用加加 *** 作了。这个还有个要处理的点就是计数,计数是以solution中的元素为准的,哪怕gusee出现多次也不参与计数。同时元素当作数组下标其实充当了计数功能的出现一次加一次,又因为会有重复元素重复计数问题,直接取guess和solutions所对应数组的元素最小值。同时这样做猜中也是会被计算在内的,最后减去猜中的次数即可

代码如下

int* masterMind(char* solution, char* guess, int* returnSize){
    *returnSize=2;
    int *nums=malloc(sizeof(int)*2);
    int count1=0;
    int count2=0;
    int arr1[26]={0};
    int arr2[26]={0};
    for(int i=0;i<4;i++)
    {
      if(solution[i]==guess[i])
      {
        count1++;
      }
    arr1[solution[i]-65]++;
    arr2[guess[i]-65]++;
    }

for(int j=0;j<26;j++)
{ 
    if(arr1[j]+arr2[j]>=2)
       {
           count2=(arr2[j]>arr1[j]?arr1[j]:arr2[j])+count2;;
       }
}
    
  if(count1==4)
    {
        nums[1]=0;
        nums[0]=4;
    }
  
   if(count2!=0)
    {
        nums[0]=count1;
        nums[1]=count2-count1;
    }

 if(count2==0)
   {
       nums[1]=0;
       nums[0]=0;
   }
   return nums;
}

同时对几种特殊情况判断就是 都猜中了,还有就是连伪猜中都没有。伪猜中都没有,猜中肯定也没有。因为都是小写字母,所以减了65,相当于减了个字符a.

3.移位 *** 作符和位 *** 作符相关问题 1.整数转换

题目链接 力扣面试题05.06整数转换

题目描述 需要改变多少个位才能将a转成b,这题实际上就是要求a和b有多少位是不同的,我们知道异或运算就是相同为0,不同为1,如果我们将a和b异或后,再求出这个异或后的数中有多少位是1,就解决了这个问题了

基于上述思路写出如下代码

int convertInteger(int A, int B){
    int n=A^B;
 int  count =0;
 for(int i=0;i<32;i++)
 {
     if((n>>i)&1)
     {
         count++;
     }
 }
  return count;
}



将a和b异或之后,在右移每一位于1进行与运算,如果该位是1,与运算后也是1,计数器加1,这个移位之后n的值本身没有发生改变,因为这里没有出现赋值行为,在之前的文章中求1的时候有这样的写法 n=n&(n-1),在这道题中是行不通的,因为题目给出的数据测试范围有部分有符号整数会溢出,不能用intl类型,但是题目的形参类型已经固定了,所以只能通过移位来计算的

2.牛客 寻找奇数

题目链接 KS33 寻找奇数

根据题目描述,只有一个数字是出现了奇数次数,其他都偶数次数。找到这个数字。在之前的文章中有介绍不引入第三个变量,利用异或运算交换两个数。异或运算有这样一个特性 a^a=0, a ^ 0=a,0 ^ 0=0,那么一个数经过偶数次异或本身,那么这个数就是0,奇数次异或就还是它本身,那么直接将0和这个数组的每个元素进行异或运算,因为出现偶数次数的数异或后还是0,0与0异或还是0,最后就只有0和和出现奇数次数的数异或,异或的结果就是这个数字。

写出如下代码

#include
int main()
{ int ret=0;
    int n =0;
    scanf("%d",&n);
    int nums[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&nums[i]);
    }
    for(int j=0;j<n;j++)
    {
        ret=nums[j]^ret;
    }
 
 printf("%d",ret);
}

这题还是比较简单的,可能有时候想不到。我当时也没有马上想到还是题做少了,只要多编程实践并且总结,慢慢就会下笔如有神的。

3.不用加减乘除做加法

题目链接 牛客JZ65 不用加减乘除做加法

这道题猛一看感觉无从下手,其实在数电中可以用异或门和与门实现一个半加器。半加器是实现两个一位二进制数加法运算的器件。实际上就是利用异或运算和与运算,来实现了加法。这些位 *** 作都以2进制为基础来运算的,也就是题目是想要求我们以用2进制加法规则来实现10进制的计算.在实现之前我们先分析一下10进制的加法运算规则.
以5+4为例
05
+
04
________
09
这是没有进位的加法,4 和5除了本身的个位以外其余高位都是0,因为没有进位直接对应位置相加即可。那要是有进位怎么办呢?以9+4为例
9+4=(9+1)+3=10+3.我们先把需要进位的分部先进位,进位以后就还是对应位置直接相加即可。

说完10进制再来说2进制
2进制数除了0就是1,同时缝2进1,
也就是说 1+0 =1;0+1=1;0+0=0;1+1=1 0;
我们先不看进位的部分,就是说
1+0 =1 ; 0+1=1 ;0+0=0;1+1=0;(先不看进位部分),这样的运算结果是不是很像异或,相同为0,不同为1.这对于2进制来说。不需要进位的加法,运算逻辑就是异或.
那进位部分怎么算呢,首先通过上面的例子可以看到只有当对应位置为1时才进位 .那么计算进位时,第一件事就是判断对应位置哪里有1, 同时对于非1的位置不做处理,只是单纯的得到进位部分 ,2进制除了0就是1现在只是处理对应位置的1,剩下的0的保持原样即可,符合这个条件的只有与运算了,因为进位对应数值需要到高位上去,所以需要左移一位。在将进位部分和非进位部分相加即可。

总的来说 如果对应位置没有1就是 a&b==0;相加的结果就是 a^ b ;如果对应位置有1就是 :a&b!=0;相加结果就是a ^ b+a&b<<1;但是进位都是低位往高位进的,对于一串二进制数来说,进位可能不仅仅至进位一次,从低位往高位挨个判断是否有1需要进位.
如果我们定义一个add函数来实现a+b,add(a,b) 实际上 就是求a^b+a&b<<1;这貌似有了一个公式 add(a,b)=add(a ^b,a&b<<1 ),这不就是递推公式吗,递推公式有了,但是递推的出口是什么呢?我们前面说了,如果没有1不就是直接a ^ b;直接对应位置异或就行了。边界条件也有了,就是a和b对应位置有没有1.

基于上述思路代码如下

nt Add(int num1, int num2 ) {
    
     if(num1&num2==0)
     {
         return num1^num2;
     }
    
     else

    return Add(num1^num2,num1&num2<<1) ;
}

在判断边界条件时返回值时num1 ^ num2,在说异或时0 ^a=a,这不相当于a+0=a,所以边界条件还可以改写一下

if(num1=0||num2=0)//加数有一个为0,直接返回另一个加数 符合加法逻辑

但是这道题如果用递归的话,时间复杂度太大了。过不了牛客测试用例。其实基本上所有的递归都可以改写成循环的形式来处理。既然递归的通不过我们直接写循环 既然是循环,那循环条件是什么呢?上面提到了有加数是0直接返回另一个加数,如果num2是0,直接返回num1,如果不是进入循环,从低位往高位判断对应位置是否都是1。这就说明b要不断更新,保证在对应位置没0的时候顺利跳出循环。异或运算实际并不会计算需要进位的位置,它只会保留本位的数值,9+4=10按照异或逻辑类似于只会保留0,1直接舍去。所以直接开始异或运算也不会影响到后续,当两数相加需要进位时,可以把位进后的结果保留,在进行对应位置的不进位的加法运算。这个把位进了的过程就是a&b<<1 类比 9+4的10进制计算,9+4=13 1直接舍去保留3, 9+1=10 把位进了 ,然后 10+(3)=13;每一次进位后进行对应位置的不进位的加法计算。什么时候停下种重复计算呢,毫无疑问就是当没有进位计算的时候,也就是说b中的1消耗完的时候,就是相与之后为0的时候,b的重新赋值既保留了进位后的结果,也保证了能顺利跳出循环


add(int a ,int b)
{
     while(b!=0)      
    { int tem=a^b;  
     b=(a&b<<1);
     a=tem;    
    }
    return a;
}

9+4=13 舍去1 保留3 就是03 ; 9+4=13,舍去3,保留1,就是10;最后就是10+03 =13
对于加法计算实际上是拆分了两部分计算 进位计算 不进位对应位置计算,每一次进位后 都要进行对 对应位置 不进位计算 实际上这也就是加法运算规则。然后重复上述的 *** 作 直到没有进位计算为止

这道题在《剑指offer》上也有出现。力扣上也有这道题但是力扣的题目要求更多一点,牛客上只能算正数,算不了负数,其实算负数就相当于不用四则运算实现了减法,加上一个数的相反数等于减去这个数

力扣题目链接不用四则运算做加法

因为上述代码只能算正整数,正整数的补码与原码相同,负整数的补码为其原码除符号位外的所有位取反后加 1。因为每一次拆分都可以让需要进位的最低位至少左移一位。符号位与数值要一起参与运算,要保证这一点。我们直接将进位的被结果保存到无符号整型中,然后异或完成不进位相加时,将保留的无符号整型赋值给b,来实现负数的相加。

int add(int a,int b)
{ w
    while(b)
    {
        unsigned int tem =(unsigned int)(a&b)<<1;
        a=a^b;
        b=tem;

    }
    return a;
}

这样实现的add函数除了算加法还可以算减法。

4.字符串相关问题 1. 牛客 单词倒排

题目链接 牛客 hj31

在字符串的相关练习的博客中,我提到了并实现reverse(反转)函数,就是将字符串的每个字符逆序,我们看到其实这道题也可以利用反转函数。我们把除了字母和空格外的所有字符都变成空格。在利用reverse函数处理字符串,和单词倒序那道题一样的做法,最后输出即可。这道题和单词倒序基本上没有太大的区别

单词倒序题目链接 牛客倒置字符串
基于上述思路代码如下

#include
#include

void reverse(char* left, char* right)
{
	while (left < right)
	{
		char temp = *left;
		*left = *right;
		*right = temp;
		left++;
		right--;
	}
}

int main()
{
	char str[10002] = { 0 };
	int len = 0;
	int i=0; 
	int flag = 0;
	gets(str);
	len = strlen(str);

	for (i = 0; i < len; i++)
	{
		if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && 
		str[i] <= 'Z' || str[i] == ' ')
			continue;//这个循环停止是为了提高一点效率
		else
		{
			str[i] = ' ';
			//将字符串中除字母和空格以外的位置都替换为空格
		}
	}

	char* start =str ;

	while (*start != ')'char
	{
		*= end ; startwhile
		( *!=end ' ' && * !=end ')' ++;
		{
			end}reverse
		(
		,-start1 end ) ;if(

		* !=')'end = +1
			start ; end else =;
		}
			start reverse end(

	,
	+-str1 str)len;puts()
	;returnstr0;
   } 反转函数的实现我就不多说了,还是想提下我第一次做倒置单词的时候,我曾经将start end同时定义在while循环外部,程序出错了,因为end更新指向时空格时,需要跳出循环,之后的end需要再次进入第二个while中指向下一个单词结尾处的空格或者当end每次跳出第二个循环时必须进行判断,end是因为空格跳出来的还是因为void跳出来的,如果是空格那就end+1,start指向下一个单词的开头,如果不是空格,那就一定是string_revolve,这个时候只用start直接等于end不用加1,因为这说明最后一个单词已经是逆序完了,直接跳出循环即可。,如果在循环外部定义end,之后的end再也不会进入第二个while更新了,所以必须再将下个单词的起始位置start赋给end.因此在不想引入第三个变量的前提下,需要将end定义在while循环内。(
char

*
,

2.左旋字符串

这道题我们通常想到的做法就是 我们将字符串的符串挨个往前挪动一步,同时将字符串首字符保存,挪动完了再将字符串的首字符移动到末尾,重复上述步骤,直到将k个字符挪动完毕

基于上述思路写出如下代码

int ,int)//1将第一个字符保存str//2每个字符都往前挪动//3将第一个字符放在末尾,并且循环往返 kfor( lenint
{  =
	0
	;
	< ;++ i ) char= i * k; ifor(
	 {
		int tem = 0str;
		< -1 j ; ++) j * len(+) j=*
		{
			(+str+j1 ) ;}str * j(+-1
		)
		=;str } len } len%k voidreverse tem(

	  char

 *

这种方法就属于暴力枚举,挨个挪动,如果有7个字符的字符串挪动7次以后就复原了,所以可以用,将这个结果作为循环挪动的次数
除了上述的做法外还有一种方法还是利用到reverse翻转函数,

所以先将字符串分为2部分,先各自逆序翻转,最后整体反转
代码如下


char *)while( left< )char right=
{
	* ;left * right=
	{
		* tem ; *left=
		;left ++ ;right--
		;right } tem}
		leftintmain
		right()

	char

[

] ="ABCD"}
{
	; str//A DCB  BCDAint = { strlen ();
	int len = 2;str//旋转次数reverse
	( k , +-1
	);str//先旋转单个部分 str reverse k(+,+-
	1)str ; k//在旋转后半部分整体 str reverse len ( ,+-1
	);str//旋转整个字符串 str printf len ( "%s",);
	}intfind( strconstchar
*

3.左旋判断


既然左旋都会了,判断就很容易,求出字符串的长度,然后挨个左旋判断,如果是就返回对应的左旋次数。如果有7个字符的字符串,左旋7次都没有匹配上,直接返回0.任选上述两种左旋方式都可以解决这个问题。
那还有其他的方法吗?我们再原有的字符串上基础上再追加它本身,那么它所有的左旋结果都是这个追加后的字符串的子串
ABCDE的所有左旋结果都是 ABCDEABCDE 的子串
这样我们直接用库函数实现即可
代码如下

, char*) char [ src256 ] = find0
{
	} tmp;//用一个辅助空间将原字符串做成两倍原字符串strcpy ( { , ); //先拷贝一遍
	char*tmp= srcstrcat( ,
	);ret//再连接一遍 if(tmp!= srcNULL) return
	1;ret}return0
	{
	  ;  }
	
  esle 
   

其实还可以直接在原字符串上直接追加它本身在用strstr查找匹配,但是会改变原字符串内容。

3.总结

1.关于元素重合问题,将元素转为数组下标,然后直接置数。注意一点数组的元素个数是决定了数组的下标值的范围,数组下标最大值一定是要大于等于元素最大值的。
2.逻辑运算和位运算,需要总结并且不断练习实践。
3.字符串问题,逆序反转函数很有用,做题以前可以先观察输入和输出之间有没有联系。
4.编程需要多实践,做的题多了,思维就会更加开阔。同时要及时复盘总结。
5.以上的解法都没有用到特别高深的算法和复杂的数据结构。可能处理方式比较巧妙一点,但是我觉得不要为自己懒刷题找借口,认为自己数据结构什么都不会,就不能去做力扣题和牛客题。只要肯学,肯练。一切都会慢慢好起来的。这句话是对我自己说的。显然我现在也还不会数据结构,但是我相信再寒假之前一定会有长进的!
6.以上解法不一定是最优解,只是我个人的浅薄见解,内容如有问题欢迎指正!

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/2991602.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表(0条)

保存