[Hè 2016] Buổi 3 - STL

[UIT.ACM]

Chào các bạn,

Lớp thuật toán hè buổi 3 tiếp tục diễn ra với nội dung như sau:

- Thời gian: 9h00 - 12h00 thứ 3, ngày 19/7/2016
- Địa điểm: Phòng A205
- Nội dung: Bài tập STL
- Đăng kí bằng cách reply tại đây với nội dung: Đăng kí tham gia

Các bạn xem trước bài tập: https://leetcode.com/tag/array/

[15520720]

Đăng kí tham gia

[14520178]

Đăng kí tham gia

[15520878]

Đăng kí tham gia

[15520197]

Đăng kí tham gia

[14521199]

Đăng kí tham gia

[15520596]

Đăng kí tham dự

[14520178]

Move Zeroes:

 class Solution {
public:
    void moveZeroes(vector<int>& nums) {
      auto new_end = remove(nums.begin(), nums.end(), 0);
        fill(new_end, nums.end(), 0);
    }
};

[12520657]

Đăng ký tham gia

[14520178]

Contains Duplicate
Link leetcode: https://leetcode.com/problems/contains-duplicate/
Code:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
       int i;
       map<int,int> c;
       for(i=0;i<nums.size();i++){
           if (c.find(nums[i])==c.end()){
               c[nums[i]]=1;
           }
           else {
               return true;
           }
       }
       return false;
    }
}; 

[14520178]

Contains Duplicate II: https://leetcode.com/problems/contains-duplicate-ii/

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
      map<int, int> c;
      int i;
      for (i=0;i<nums.size();i++){
          if (c.find(nums[i])==c.end()){
              c[nums[i]]=i;
          }
          else{
              //tim thay
              if (i-c[nums[i]]<=k){
                  return true;
              }
              else {
                  c[nums[i]]=i;
              }
          }
      }
      return false;
    }
}; 

[UIT.ACM]

Contains Duplicate II: https://leetcode.com/problems/contains-duplicate-ii/

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n=nums.size();
        map <int,int> count;
        for(int i=0;i<n;i++)
        {
            if(count[nums[i]] && i-count[nums[i]]<k) return true;
            count[nums[i]]=i+1;
        }
        return false;
    }
}; 

[14520178]

Rotate Array:https://leetcode.com/problems/rotate-array/

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        for(int i=0;i<k;i++){
            int c=nums.back();
            nums.insert(nums.begin(),c);
            nums.pop_back();
        }
    }
}; 

[UIT.ACM]

Rotate Array 24ms:https://leetcode.com/problems/rotate-array/

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k=k%n;
        if(k==0) return;
        vector <int> copy=nums;
        int t=n-k;
        for (int i=0; i<n; i++)
        {
            nums[(i+k)%n]=copy[i];
        }
    }
}; 

[15520596]

Contains Duplicate II: https://leetcode.com/problems/contains-duplicate-ii/
72ms

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int i;
        int n=nums.size();
        map<int, int> c;
        
        if(n<2) return false;
        
        for(i=0; i<n; i++){
            if(c[nums[i]]!=0){
                if(abs(i+1-c[nums[i]]) <= k)
                    return true;
                else c[nums[i]]=i+1;
            }
            else c[nums[i]]=i+1;
        }
        
        return false;
    }
};