leetcode-简单

448. 找到所有数组中消失的数字

硬解 时间O(n)，空间O(n)

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> result;
        vector<int> tem(nums.size()+1, 0);
        for(int i: nums)
        {
            tem[i] = 1;
        }
        for(int i = 1; i < nums.size()+1; i++)
        {
            if(tem[i] == 0)
            {
                result.push_back(i);
            }
        }
        return result;
    }
};

由于num属于[1,n]，遍历nums，每遇到一个数num，令nums[num - 1]的值加n,表示有集合中有num这个数。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        for(int i = 0; i < nums.size(); i++)
        {
            int x = (nums[i] - 1) % nums.size();
            nums[x] = nums[x] + nums.size();
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] <= nums.size())
            {
                res.push_back(i + 1);
            }
        }
        return res;
    }
};

374. 猜数字大小

暴力解法，超出时间限制

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */
class Solution {
public:
    int guessNumber(int n) {
        for(int i = 1; i <=n; i++)
        {
            if(0 == guess(i))
            {
                return i;
            }
        }
        return -1;
    }
};

 二分查找，注意n可能会大于int，代码可以通过，但是如果要找的数大于int是不是会出问题，关键他自己的guess参数只有int。

更正：应该时计算mid时left+right时溢出，应使用

int mid = left + (right - left) / 2; // 防止计算时溢出

class Solution {
public:
    int guessNumber(int n) {
        uint left = 1;
        uint right = n;
        uint mid;
        while(1)
        {
            mid = (left + right) / 2;
            uint res = guess(mid);
            if(-1 == res)
            {
                right = mid - 1;
            }
            else if(1 == res)
            {
                left = mid + 1;
            }
            else if(0 == res)
            {
                return mid;
            }
        }
    }
};

303. 区域和检索 - 数组不可变

class NumArray {
private:
    vector<int> nums;
public:
    NumArray(vector<int>& nums) {
        this->nums = nums;
    }
    
    int sumRange(int left, int right) {
        int sum = 0;
        for(int i = left; i <= right;i++)
        {
            sum += nums[i];
        }
        return sum;
    }
};

用一个数组保存累加和，需要的时候直接返回区间差

class NumArray {
private:
    vector<int> nums;
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        this->nums.resize(n + 1);
        for(int i = 0; i < n; i++)
        {
            this->nums[i + 1] = this->nums[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return this->nums[right + 1] - this->nums[left];
    }
};

387. 字符串中的第一个唯一字符

使用map

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> map;
        for(char i : s)
        {
            map[i] +=1;
        }
        for(int i = 0; i<s.size(); i++)
        {
            if(map[s[i]] == 1)
            {
                return i;
            }
        }
        return -1;
    }
};

 389. 找不同

 使用数组计数

class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> vec(26, 0);
        for(char ch : s)
        {
            vec[ch - 'a'] += 1;
        }
        for(char ch : t)
        {
            vec[ch - 'a'] -= 1;
        }
        for(int i = 0; i < vec.size(); i++)
        {
            if(vec[i] == -1)
            {
                return char(i + 'a');
            }
        }
        return ' ';
    }
};

392. 判断子序列

使用队列 

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if(s.size()==0) return true;
        queue<char> qu;
        for(char ch : s)
        {
            qu.push(ch);
        }
        for(char ch : t)
        {
            if(ch == qu.front())
            {
                qu.pop();
            }
            if(qu.empty())
            {
                return true;
            }
        }
        return false;
    }
};