额外题目第1天｜1365 941 1207 283 189 724 34 922 35 24

1365 暴力解法也能过

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

优化看了代码随想录的思路其实本来自己想到了要sort就可以但是没想到用一个hash来对应数值和数组中比他小的个数 填充hash时从后往前 这样相等的数值就会被覆盖成最前面的

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());

        int hash[105] = {};
        for (int i=sorted.size()-1; i>=0; i--) {
            hash[sorted[i]]=i;
        }

        vector<int> result(nums.size(), 0);
        for (int i=0; i<nums.size(); i++) {
            result[i]=hash[nums[i]];
        }
        return result;
    }
};

941 我是按照顺序来遍历找山峰的但这个逻辑确实是比较容易有所疏漏所以第一次提交的时候忽略了单调递减这个情况错误判断成了true

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if (arr.size()<3) {
            return false;
        }
        int i=1;
        while (i<arr.size() && arr[i]>arr[i-1]) {
            i++;
        }
        if (i>=arr.size() || arr[i]==arr[i-1] || i==1) {
            return false;
        }
        while (i<arr.size() && arr[i]<arr[i-1]) {
            i++;
        }
        if (i>=arr.size()) {
            return true;
        }
        return false;
    }
};

用双指针来写更加清晰且不易错 让i和j从两边单调递增到山峰最后的i和j应该是会合且不在数组头尾 其他情况都return false

lass Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if (arr.size()<3) return false;
        int i=1;
        int j= arr.size()-2;
        while (i<arr.size() && arr[i]>arr[i-1]) i++;
        while (j>=0 && arr[j]>arr[j+1]) j--;
        i--; j++;
        if (i!=j || i==0 || j==arr.size()-1) return false;
        return true;
    }
};

1207 典型哈希表题目出现的元素范围是-1000到1000 所以定义数组hash数出元素出现的个数之后遍历整个hash数组再映射到existed数组如果hash数组的值>0则记为出现过如果遍历到出现过的个数就return false

下面comment的是我自己想的用umap来写的就是把每个次数map到第一个元素出现这么多次数的数上面去遍历arr数组通过hash值在map里找这个次数如果找到就说明前面有过相同次数 return false

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        int hash[2001]={0};
        for (int i=0; i<arr.size(); i++) {
            hash[arr[i]+1000]++;
        }

        bool existed[2001]={false};
        for (int i=0; i<2000; i++) {
            if (existed[hash[i]]==true) return false;
            if (hash[i]>0) existed[hash[i]]=true;
        }
        return true;
        
        /* unordered_map<int, int> umap;
        for (int i=0; i<arr.size(); i++) {
            if (umap.find(hash[arr[i]+1000])==umap.end()) {
                umap[hash[arr[i]+1000]] = arr[i]+1000;
            }
            else {
                if (umap[hash[arr[i]+1000]] == arr[i]+1000) continue;
                else return false;
            }
        }
        return true; */
    }
};

283 这个是我自己想的！每次从头找第一个零与他后面第一个非0交换位置直到两个while loop任意一个到数组末尾为止

class Solution {
private:
    void swap(vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
public:
    void moveZeroes(vector<int>& nums) {
        while (true) {
            int i=0; 
            while (i<nums.size() && nums[i]!=0) i++;
            if (i==nums.size()) return;
            int j=i+1;
            while (j<nums.size() && nums[j]==0) j++;
            if (j==nums.size()) return;
            swap(nums,i,j);
        }
        return;
    }
};

这个思路是参考代码随想录之后写的双指针法效率感觉更高！如果忘记思路了可以再去看一下那个动图总结来说就是slow指针是一个一个走的 fast碰到有0的就跳过每次让nums[slow]=nums[fast] 当fast走到末尾的时候从slow现在的位置到末尾都赋值0

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow=0;
        int fast=0;
        while(fast<nums.size()) {
            while (fast<nums.size() && nums[fast]==0) fast++;    
            if (fast==nums.size()) break;
            nums[slow]=nums[fast];
            slow++;
            fast++;
        }
        while (slow<nums.size()) {
            nums[slow++]=0;
        }
    }
};

189 double数组之后再赋值就可以！注意旋转方向

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k=k%nums.size();
        vector<int> double_nums(2*nums.size(),0);
        for (int i=0; i<double_nums.size(); i++) {
            double_nums[i] = nums[i%nums.size()];
        }
        for (int i=0; i<nums.size(); i++) {
            nums[i]=double_nums[i+nums.size()-k];
        }
    }
};

method 2 先反转整个数组再反转前k个和后面的（这是向右轮转）

--diff 向右转就是前k个向左转是后k个

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        //method 2
        k=k%nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin()+k);
        reverse(nums.begin()+k, nums.end());
    }
};

724 本来想用双指针做但因为数组里会有负数所以还是用动态规划来做比较好（其实这里的left和right不需要是数组是variable就可以了每次覆盖就ok

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        vector<int> left(nums.size(), 0);
        vector<int> right(nums.size(),0);
        left[0]=0;
        for (int i=1; i<nums.size(); i++) {
            right[0]+=nums[i];
        }

        if (left[0]==right[0]) return 0;
        for (int i=1;i<nums.size(); i++) {
            left[i]=left[i-1]+nums[i-1];
            right[i]=right[i-1]-nums[i];
            if (left[i]==right[i]) return i;
        }
        
        return -1;
    }
};

34 二分查找题 一定一定要记得是什么区间这里是左闭右闭 所以更新mid的时候是left=mid+1 or right = mid-1 才能终止while loop

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0; 
        int right = nums.size()-1; 
        int mid=0;
        while (left<=right) {
            mid = (left+right)/2;
            if (nums[mid]==target) break;
            if (nums[mid]>target) right=mid-1;
            else if (nums[mid]<target) left=mid+1;
        }

        vector<int> result = {-1,-1};
        if (nums.size() == 0 || nums[mid]!=target) return result;

        int first=mid; int last=mid;
        while (first>=0 && nums[first]==target) first--;
        first++;
        while (last<nums.size() && nums[last]==target) last++;
        last--;

        result[0]=first; result[1]=last;
        return result;
    }
};

922 双指针法 i指向偶数位 j指向奇数位遇到合格的就跳过两个都是不合格的就互换位置 一直到任意一个遍历完整个数组位置

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int i=0;
        int j=1;
        while (i<nums.size() && j<nums.size()) {
            while (i<nums.size() && nums[i]%2==0) i=i+2;
            while (j<nums.size() && nums[j]%2==1) j=j+2;
            if (i>=nums.size() || j>=nums.size()) break;
            int temp = nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        return nums;
    }
};

35 二分查找经典模版但return的时候要判断一下是放在mid前面还是后面

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0; int right = nums.size()-1;
        int mid=0;
        while (left<=right) {
            mid = (left+right)/2;
            cout<<"mid = "<<mid<<endl;
            if (target==nums[mid]) return mid;
            if (target>nums[mid]) left = mid+1;
            else if (target<nums[mid]) right=mid-1;
        }
        if (nums[mid]>target) return mid;
        return mid+1;
    }
};

24 记得加dummy_head会好写一点要单独考虑特殊情况用curr来遍历整个链表

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy_head = new ListNode(0, head);
        ListNode* curr = dummy_head;
        while (curr!=nullptr) {
            ListNode* temp = curr->next;
            if (temp==nullptr || temp->next == nullptr) break;
            ListNode* temp1 = temp->next->next;
            curr->next = temp->next;
            curr->next->next = temp;
            temp->next = temp1;
            curr = curr->next->next;
        }
        return dummy_head->next;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/48174.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！