一周刷题总结 - 2

又到了一周题目总结时间。到现在为止总共完成了三十道题，每天大概做1-3题。感觉这个步骤还是比较适合自己的进度的。

• leetcode 9

给出一个Int值，判断是否是回文数字。

我们可以想到，如果是字符串的话，我们可以通过字符串的处理方式来处理，但这里是一个数字。我们可以从回文的定义知道，如果我们将整个数字反转过来，如果仍然等于原来的数字，那么这个数字就是回文数。

代码如下

bool isPalindrome(int x) {
    if(x<0) return false;
    if(x<10) return true;
    
    int y=0,temp = x;
    
    while(temp)
    {
        y = y*10 + (temp%10);
        temp/=10;
    }
    
    return x==y;
}

• leetcode 26

移除一个数组中重复的数字。

根据题意，我们只需要将重复的数字不停地移动到数组末尾，然后缩短数组大小就可以了。

int removeDuplicates(int* nums, int numsSize) {
    
    if(numsSize<2) return numsSize;
    
    int cur = 0;int temp = nums[0];
    
    for(int i = 1;i<numsSize;i++)
    {
        if(nums[i] == temp) continue;
        else
        {
            nums[cur+1] = nums[i];
            cur++;
            temp = nums[i];
        }
    }    
    return cur+1;
}

• leetcode 136

给出一个数组，找出数组中唯一一个只出现了一次的数，其他的数都出现了两次，要求线性时间内完成且不能用额外的空间。

这道题给的难度分类是中等，但是我看了下题目的通过率很高，说明又很巧妙地方法。我自己在开始做得时候想到的都都要用额外的存储空间。在看了别人的方法后才知道原来可以用异或方法，因为异或方法相当于交换了两个数。所以我们要做得就是遍历一次数组，用一个数与每个数组的数异或，最后保留的数就是唯一一个出现了一次的数。

int removeDuplicates(int* nums, int numsSize) {
    
    if(numsSize<2) return numsSize;
    
    int cur = 0;int temp = nums[0];
    
    for(int i = 1;i<numsSize;i++)
    {
        if(nums[i] == temp) continue;
        else
        {
            nums[cur+1] = nums[i];
            cur++;
            temp = nums[i];
        }
    }
    
    return cur+1;
}

同样地,leetcode还给出了一道相似的题目，就是

• leetcode 260

这道题目和上面的题目基本一样，唯独不同的是给出的数组中有两个数只出现了一次。

题目中提到了，要在线性时间内完成，我们还是要考虑从上面的题目中怎么改进就可以完成这道题目。

int* singleNumber(int* nums, int numsSize, int* returnSize) {
    int i, *result = calloc(*returnSize = 2, sizeof(int));
    for(i = 0; i < numsSize; result[0] ^= nums[i++]);
    for(i = 0; i < numsSize; i++)
        if(nums[i] & result[0] & -result[0])
            result[1] ^= nums[i];
    result[0] ^= result[1];
    return result;
}

这个方法，首先找出了一个result[0]，这个是保存了两个出现了一次的的数字的异或结果a xor b;
我们知道 如果a != b的话，那么a xor b就会保准他们每个数字的一部分的二进制。
那么第二部我们通过异或就可以刷选出一个结果。
通过 a xor b的结果再异或，就可以得出另一个结果。

通过上面两道题目可以得出，简简单单的异或有时候可是非常强大的。

##小结

虽然每周做得题目不止这么多，但是受限时间，只能慢慢整理，优先整理我觉得值得思考的题目。

赏

谢谢你请我吃糖果