2021-09-24每日刷题打卡

力扣

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

对于查找来说应该用哈希，但是这里要求不使用额外空间，那我们可以直接把数组进行排序，然后从第一个元素到倒数第二个元素开始遍历，每次判断当前数是否等于它的下一个数，如果等于就让i+1来跳过那个数继续遍历，如果不等于那就可以直接输出nums[i+1]，因为我要判断这个数和它的下一个数，所以我们遍历到倒数第二个数就该停止遍历，不然会越界。有可能最后那个数是我们要找的数，为了不错过他我们在遍历外面return一个nums[nums.size()-1];如果for循环没找到那个数，就说明那个数是最后一个数，直接return。如果找到了那就在for里就会return那个数从而终止程序，也不用担心这个nums[nums.size()-1];会被返回。

class Solution {
public:
   int singleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size()-1; i++) {
        if(nums[i]==nums[i+1])
        {
            i++;
        }else{
            return nums[i];
        }
    }
    return nums[nums.size()-1];
}
};
           

贴一个哈希查找的

class Solution {
public:
   int singleNumber(vector<int>& nums) {
    unordered_map<int,int>mymap;
    for(auto i:nums)
    {
        mymap[i]++;
    }
    for(auto i:mymap)
    {
        if(i.second==1)
        {
            return i.first;
        }
    }
    return {};
}
};
           

125. 验证回文串 

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"

输出: true

解释："amanaplanacanalpanama" 是回文串

遍历一遍把其中的字母保存下来，“ ”和“，”去掉，保存的同时检测一下把所有的大写字母全部变成小写，把字符串反转，判断反转前和反转后是否相同，如果相同就是回文串。（也可以用对撞指针的方法来比较）

class Solution {
public:
    bool isPalindrome(string s) {
        string str;
        string str2;
        for(int i=0;i<s.size();i++){
            if(s[i]>=65&&s[i]<=90){
                s[i]+=32;
                str+=s[i];
            }else if(s[i]>=97&&s[i]<=122){
                str+=s[i];
            }else if(s[i]>=48&&s[i]<=57){
                str+=s[i];
            }
        }
        str2=str;
        reverse(str.begin(),str.end());
        if(str==str2){
            return true;
        }else{
            return false;
        }
        return {};
    }
};