[Hè 2016] Buổi 3 - STL

Góc học tập Thuật toán - OLP / ICPC
1

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/

2

Đăng kí tham gia

3

Đăng kí tham gia

4

Đăng kí tham gia

5

Đăng kí tham gia

6

Đăng kí tham gia

7

Đăng kí tham dự

8

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);
    }
};
9

Đăng ký tham gia

10

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*)==c.end()){
c[nums*]=1;
}
else {
return true;
}
}
return false;
}
};
11

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*)==c.end()){
c[nums*]=i;
}
else{
//tim thay
if (i-c[nums*]<=k){
return true;
}
else {
c[nums*]=i;
}
}
}
return false;
}
};
12

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-count[nums*]<k) return true;
count[nums*]=i+1;
}
return false;
}
};
13

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();
        }
    }
};
14

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*;
}
}
};
15

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*]!=0){
if(abs(i+1-c[nums*]) <= k)
return true;
else c[nums*]=i+1;
}
else c[nums*]=i+1;
}
return false;
}
};
16

Contains Duplicate: https://leetcode.com/problems/contains-duplicate/
104ms

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

Move Zeroes: https://leetcode.com/problems/move-zeroes/
22ms

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

Find the Duplicate: https://leetcode.com/problems/find-the-duplicate-number/
Time: 56ms

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

Remove Element : https://leetcode.com/problems/remove-element/
Time: 4ms

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
for(i=0;i<nums.size();i++){
if(nums*==val){
nums.erase(nums.begin()+i);
i--;
}
}
return nums.size();
}
};
20

Majority Element: https://leetcode.com/problems/majority-element/
Time: 48 ms

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