LeetCode 题解随笔：补充题目

目录

1365. 有多少小于当前数字的数字

941. 有效的山脉数组

1207. 独一无二的出现次数

---

一、数组 1365. 有多少小于当前数字的数字

vector smallerNumbersThanCurrent(vector& nums) {
        vector numsSort = nums;
        sort(numsSort.begin(), numsSort.end());
        unordered_map record;
        // 从后向前赋值，保证下标为第一个出现的元素
        for(int i = numsSort.size() - 1; i >= 0; i--) {
            record[numsSort[i]] = i;    
        }
        vector res(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            res[i] = record[nums[i]];
        }
        return res;
    }

941. 有效的山脉数组

bool validMountainArray(vector& arr) {
        // 双指针法
        if (arr.size() <= 2)   return false;
        int left = 0;
        int right = arr.size() - 1;
        while (left < arr.size() - 1 && arr[left + 1] > arr[left]) {
            left++;
        }
        while (right > 0 && arr[right - 1] > arr[right]) {
            right--;
        }
        if (left == right && left != 0 && right != arr.size() - 1) return true;
        else    return false;
    }

1207. 独一无二的出现次数

bool uniqueOccurrences(vector& arr) {
        unordered_map arrCount;
        for (int i : arr) {
            arrCount[i]++;
        }
        set count;
        for (auto it = arrCount.begin(); it != arrCount.end(); it++) {
            count.insert(it->second);
        }
        if (arrCount.size() == count.size())   return true;
        else    return false;
    }

189. 轮转数组

void rotate(vector& nums, int k) {
        // 参考翻转字符串问题
        k = k % nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }

724. 寻找数组的中心下标

int pivotIndex(vector& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int tempSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (sum - nums[i] == 2 * tempSum)   return i;
            tempSum += nums[i];
        }
        return -1;
    }

922. 按奇偶排序数组 II

vector sortArrayByParityII(vector& nums) {
        // 双指针法
        int odd = 1;
        for (int even = 0; even < nums.size(); even += 2) {
            // 偶数位不符合，在奇数位寻找不符合的元素进行替换
            if (nums[even] % 2 != 0) {
                while (nums[odd] % 2 != 0)   odd += 2;
                swap(nums[odd], nums[even]);
            }
        }
        return nums;
    }

---

二、哈希表 205. 同构字符串

bool isIsomorphic(string s, string t) {
        // 利用unordered_map直接记录字符与字符之间的映射
        unordered_map map1;
        unordered_map map2;
        for (int i = 0, j = 0; i < s.size(); i++, j++) {
            if (map1.find(s[i]) == map1.end()) { // map1保存s[i] 到 t[j]的映射
                map1[s[i]] = t[j];
            }
            if (map2.find(t[j]) == map2.end()) { // map2保存t[j] 到 s[i]的映射
                map2[t[j]] = s[i];
            }
            // 发现映射 对应不上，立刻返回false
            if (map1[s[i]] != t[j] || map2[t[j]] != s[i]) {
                return false;
            }
        }
        return true;
    }

925. 长按键入

bool isLongPressedName(string name, string typed) {
        int index = 0;
        // 记录重复元素数
        int count = 0;
        for (int i = 0; i < name.size(); i++) {
            // 名字中有连续重复字符
            if (i > 0 && name[i] == name[i - 1]) {
                count--;
                if (count < 0)     return false;
            }
            // 名字中没有连续重复字符
            else {
                count = 0;
                if (name[i] != typed[index])     return false;
                if (index >= typed.size())     return false;
                while (index + 1 < typed.size() && typed[index + 1] == typed[index]) {
                    index++;
                    count++;
                }
                index++;
            }    
        }
        // 是否有多余字符
        if (index != typed.size())   return false;
        return true;
    }