class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = nums[0];
        for(int i = 1; i < nums.size() ;i++){
            result = result ^ nums[i];
        }
        return result;
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //出现次数超过一半的数字一定是出现最多的数字
        map<int , int>mp;
        int max = 0;//出现次数
        int result = 0;//出现次数最多的数字
        for(int i = 0; i < nums.size() ; i++){
            if(mp.find(nums[i]) != mp.end()){//map中找得到该数字
                mp[nums[i]] = ++mp[nums[i]];
                if(mp[nums[i]] > max){
                    max = mp[nums[i]];
                    result = nums[i];
                }
            }
            else{//map中找不到该数字
                mp[nums[i]] = 1;
                if(1 > max){
                    max = 1;
                    result = nums[i];
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    bool findTarget(vector<vector<int>>& matrix , int i , int j , int target){
        if(matrix[i][j] == INT_MIN){//递归可能会超时，需要将递归经过的地方设置为INT_MIN，之后递归再次遇到该值直接跳过;
            return false;
        }
        else if(matrix[i][j] == target){
            return true;
        }
        else if(matrix[i][j] > target){
            return false;
        }
        else{
            matrix[i][j] = INT_MIN;
        }

        if(i == matrix.size()-1 && j == matrix[i].size()-1){//最后一行最后一列
            return false;
        }
        else if(i == matrix.size()-1){//最后一行
            return findTarget(matrix , i , j+1 , target);
        }
        else if(j == matrix[i].size()-1){//最后一列
            return findTarget(matrix , i+1 , j , target);
        }
        if(matrix[i][j] < target && matrix[i+1][j] > target && matrix[i][j+1] > target){
            return false;
        }
        return findTarget(matrix , i+1 , j , target) || findTarget(matrix , i , j+1 , target);
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        return findTarget(matrix , 0 , 0 , target);    
    }
};

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums3;
        int p1 = 0;
        int p2 = 0;
        while(p1 < m && p2 < n){
            if(nums1[p1] <= nums2[p2]){
                nums3.push_back(nums1[p1]);
                p1++;
            }
            else{
                nums3.push_back(nums2[p2]);
                p2++;
            }
        }
        if(p1 == m){
            for(int i = p2 ; i < n ; i++){
                nums3.push_back(nums2[i]);
            }
        }
        else if(p2 == n){
            for(int i = p1 ; i < m ; i++){
                nums3.push_back(nums1[i]);
            }
        }
        nums1.resize(0);
        for(int i = 0; i < m+n ;i++){
            nums1.push_back(nums3[i]);
        }
    }
};

class Solution {
public:
    bool isPalindrome(string s) {
        //大写转换为小写
        for(int i = 0; i < s.length() ;i++){
            if(s[i] >= 'A' && s[i] <= 'Z'){
                s[i] = s[i] + 32;
            }
        }
        int i = 0;
        int j = s.length() - 1;
        while(i < j){
            //筛选掉非数字和字母的部分
            while(!((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= '0' && s[i] <= '9'))){
                i++;
                if(i >= j){
                    return true;
                }
            }
            while(!((s[j] >= 'a' && s[j] <= 'z') || (s[j] >= '0' && s[j] <= '9'))){
                j--;
                if(i >= j){
                    return true;
                }
            }
            if(s[i] != s[j]){
                return false;
            }
            else{
                i++;
                j--;
            }
        }
        return true;
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        int flag[26];
        memset(flag , 0 , 26*sizeof(int));
        for(int i = 0; i < s.length() ; i++){
            flag[s[i]-'a']++;
        }
        for(int i = 0; i < t.length(); i++){
            flag[t[i]-'a']--;
        }
        for(int i = 0; i < 26 ;i++){
            if(flag[i] != 0){
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    int firstUniqChar(string s) {
        int flag[26];
        memset(flag , 0 , 26*sizeof(int));
        for(int i = 0; i < s.length() ; i++){
            flag[s[i]-'a']++;
        }
        for(int i = 0; i < s.length() ; i++){
            if(flag[s[i]-'a'] == 1){
                return i;
            }
        }
        return -1;
    }
};

class Solution {
public:
    void swap(char &s1 , char &s2){
        char tmp = s1;
        s1 = s2;
        s2 = tmp;
    }

    void reverseString(vector<char>& s) {
        int i = 0;
        int j = s.size() - 1;
        while(i < j){
            swap(s[i] , s[j]);
            i++;
            j--;
        }
    }
};