练手题目

写在开头

写这篇博客旨在把平日练手的一些有趣的小题分享，很多的题应该都不会涉及复杂的算法只是一些想法比较有意思的小题

1.一串数字，长度未知，求其中只出现一次的数。要求时间复杂度O(1),空间复杂度O(0)

一开始看到这道题想了用标记数组来做，后在看视频的时候无意间看到了”^”这个符号想起来了用位运算来处理每一个数，如果两个数相同异或就会变成0，任何数和0异或又是
其本身，代码如下**

#include<stdio.h>
int main()
{
    int n,ans=0;
    while(EOF!=scanf("%d",&n))
    {
        ans^=n;
    }
    printf("%d\n",ans);
    return 0;
}

2.给出三个队列 s1，s2，s3 ，判断 s3 是否是由 s1 和 s2 交叉得来。 如：s1 为 aabcc ， s2 为 dbbca。 当 s3 aadbbcbcac 时，返回 true（即将 s1 拆成三部分： aa，bc，c 分别插入 s2 对应位置） 否则返回 false。**

一开始想到就是字符串匹配问题，代码如下,但没有考虑，前一串以最优情况匹配，后一串在匹配时会因前一串把优先把靠前位置都占据，而出现匹配不
上的情况，因此加以优化，将第一串从后往前匹配，将更优的位置给下一串留下，中途甚至想过用每个字符的ASCII码建一个数组，然后只用匹配数量即可，但后来发现这样匹配没有考虑到字符串本来的顺序问题，放弃。

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
char a[100];
char b[100];
char c[200];
int ans[200];
char d[400];
int main()
{
    memset(ans,0,sizeof(ans));
    int i = 0 ,flag = 1 ,mark = 1 , m = 0 , n = 0 ,pos;
   scanf("%s",d);
   getchar();
   while(d[i]!=',')
   {
       a[i] = d[i];
       i++;
   }
   a[i] = '\0';
   i++;
   while(d[i]!=',')
   {
       b[m++] = d[i++];
   }
   b[m] = '\0';
   i++;
   int len = strlen(d);
   while(i<len)
   {
       c[n++] = d[i++];
   }
   c[n] = '\0';
   int lena = strlen(a);
   pos = lena-1;
   for(int j = n-1 ; j >=0 ; j--)
   {
       if(c[j]==a[pos])
       {
           ans[j] = 1;
           pos--;
       }
   }
   if(pos!=-1)
   {
       flag = 0;
   }
   pos = 0;
   for(int j = 0 ; j < n ; j++)
   {
       if(c[j]==b[pos]&&ans[j]!=1)
       {
           pos++;
       }
   }

   if(pos != m)
   {
       mark = 0;
   }
   if(mark&&flag)
   {
       printf("true\n");
   }
   else{
    printf("false\n");
   }
   return 0;
}