暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / [LEECODE]算法进阶自练习1-2 数组&链表&Map&Set

[LEECODE]算法进阶自练习1-2 数组&链表&Map&Set

小马爸爸的笔记 2020-09-15
167

[LEECODE]算法进阶自练习1-2 数组&链表&Map&Set

1.数组、链表

简单
  1. 删除排序数组中的重复项 leetcode 26

 因为数组中有重复的，所以最终的数据都得往前移动，因此，可以用双指针来解决。

    int removeDuplicates(vector<int>& nums) {
        int nsize = nums.size();
        if(nsize == 0) return 0;


        int fast=0, slow=0;


        for(; fast<nsize; fast++) if(nums[fast] != nums[slow]) nums[++slow] = nums[fast]; // 先++ 后填数字


        return ++slow; // 这里注意是下标+1的概念
    }
  1. 旋转数组 leetcode 189

 最简单的方式是一个一个循环来移动，但是实际上可以将数组看成无限长或者环状的数组，index往后移动k就是(index+k)%nsize (nsize为数组长度);

    void rotate(vector<int>& nums, int k) {
        int nsize = nums.size();
        vector<int> ret(nsize, 0);


        for(int i=0; i<nsize; i++) ret[(i+k)%nsize] = nums[i];
        
        ret.swap(nums);
    }
  1. 合并两个有序链表 leetcode 21

 两个比较大小然后串起来即可，记得处理下最后没有遍历完的链表就行了，这里注意用一个哑元节点可能写代码更好处理一点。

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
       ListNode* head = new ListNode(-1);
       ListNode* dummyHead = head;
       while(l1 && l2){
           if(l1->val < l2->val){
               dummyHead->next = l1;
               l1 = l1->next;
           }
           else{
               dummyHead->next = l2;
               l2 = l2->next;
           }
           dummyHead = dummyHead->next;
       }
       dummyHead->next = l1 ? l1: l2;
       return head->next;
    }
  1. 合并两个有序数组 leetcode 88

 合并两个有序数组和上面合并链表差不多，但是注意合并数组后面处理剩余的尾巴元素的时候是用循环的，和链表不一样的就在这里了。

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> ret(m+n,0);
        int i=0, j=0, k=0;
        while(i<m && j<n) ret[k++] = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];
        while(i<m) ret[k++] = nums1[i++];
        while(j<n) ret[k++] = nums2[j++];
        nums1.swap(ret);
    }
中等
  1. 两两交换链表中的节点 leetcode 24
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;
        // 1->2->3->4->5 nil
        // ret: 2->1  3->4
        ListNode* prev = nullptr;
        ListNode* ret = nullptr;
        
        while(head && head->next){
            ListNode* node = head;
            ListNode* next = head->next;
            ListNode* tmp = head->next->next;
            
            if(prev != nullptr) prev->next = next; // 这里是处理每次两个节点翻转之间的连接
            
            next->next = node;
            if(prev == nullptr) ret = next; // 这里要设置头指针
            prev = node;
            head = tmp;
        }
        prev->next = head != nullptr ? head : nullptr; // 这里一定要注意 如果双数节点要设置下最终链表以nullptr结尾。
        return ret;
    }

 递归解法：

  ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* node = head, *next = node->next;
        node->next  = swapPairs(next->next);
        next->next = node;
        return next;
        // 1 , 2 , 3
    }
  1. 三数之和 leetcode 15

 整体思路是排序后以O(n)的时间复杂度来遍历，但是要注意去重，去重要靠下面两点来保证。

vector<vector<int>> twoSumTarget(vector<int>& nums, int target, int start){
        vector<vector<int>> ret;
        int nsize=nums.size(), i=start, j=nsize-1;
        while(i < j){
            int left = nums[i], right = nums[j], sum = left + right;
            if(sum < target) while(i<j && nums[i] == left) i++; // 去重第一点
            if(sum > target) while(i<j && nums[j] == right) j--; // 去重第一点
            if(sum == target){
                ret.push_back({nums[i],nums[j]});
                while(i<j && nums[i] == left) i++; // 去重第一点
                while(i<j && nums[j] == right) j--; // 去重第一点
            }
        }
        return ret;
    }
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        int nsize = nums.size();
        for(int i=0; i<nsize; i++){
            vector<vector<int>> tmp = twoSumTarget(nums, 0-nums[i], i+1); // 去重第二点，注意这里有个start。
            for(auto& x:tmp){
                x.push_back(nums[i]);
                ret.push_back(x);
                while(i<nsize-1 && nums[i] == nums[i+1]) i++;
            }
        }
        return ret;
        
    }

2. Map & Set

简单
  1. 有效的字母异位词 leetcode 242

 这个题目两种做法：1.排序后判断是否相等 2.map字母奇数

  bool isAnagram(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        return s == t;
    }


    bool isAnagram(string s, string t) {
        int ssize = s.size(), tsize = t.size();
        if(s.size() != t.size()) return false;
        map<char,int> mp;
        for(int i=0; i<ssize; i++){
            if(mp.count(s[i]) > 0){
                mp[s[i]]++;
            }else{
                mp[s[i]] = 1;
            }
        }
        for(int i=0; i<tsize; i++){
            if(mp.count(t[i]) > 0){
                mp[t[i]]--;
                if(mp[t[i]] == 0){
                    mp.erase(t[i]);
                }
            }
            else{
                return false;
            }
        }
        return mp.empty();
    }
中等
  1. 字母异位词分组 leetcode 49

 利用map<string, vector>分组就可以了。

  vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        map<string, vector<string>> mp;
        for(auto& str: strs){
            string tmp = str;
            sort(tmp.begin(), tmp.end());
            mp[tmp].push_back(str);
        }
        for(map<string, vector<string>>::iterator it = mp.begin(); it != mp.end(); it++){
            ret.push_back(it->second);
        }
        return ret;
    }


数据库
文章转载自小马爸爸的笔记，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论