5. Contain Duplicated

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.empty())
            return false;
        unordered_map<int,int> mp;

        for(int i : nums)
        {
            if(++mp[i]>1)
                return true;
        }
        return false;
    }

};

• unordered_map 은 Hash Table을 쉽게 이용할 수 있게 한다.

4. Rotate Array

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(k==0)
        {
            return;
        }
        int n = nums.size();
        int* A = new int[k+1];
        int* B = new int[n-k];
        for(int i=0; i<k+1;i++)
        {
            A[i]=nums[i]; // A = {1,2,3,4}
        }
        for(int i=1; i<n-k;i++)
        {
            B[i-1]=nums[i+k]; // B = {5,6,7}
        }
        for(int i =0; i<n-k-1;i++) // 7-3-1 = 3
        {
            nums[i] = B[i];
            // std::cout<<nums[i]<<" ,";
        }
        for(int i = 0; i<k+1;i++) // 0,1,2,3<3
        {
            nums[k+i] = A[i];
        }


    }
};

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

        //rotate
        for(int i = 0; i<n; i++)
        {
            nums[(i+k)%n] = copynums[i];
        }
    }
};

3. Best Time to buy and sell stock 2

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum=0;
        for(int i = 1; i<prices.size(); i++)
        {
            int diff = prices[i] - prices[i-1];
            if(diff>0)
                sum+=diff;
        }
        return sum;

    }
};

2. remove duplicated from sorted array

11. Valid sudoku

Three flags are used to check whether a number appear.

used1: check each row

used2: check each column

used3: check each sub-boxes

class Solution
{
public:
    bool isValidSudoku(vector<vector<char> > &board)
    {
        int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};

        for(int i = 0; i < board.size(); ++ i)
            for(int j = 0; j < board[i].size(); ++ j)
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0' - 1, k = (i/3) * 3 + j / 3; // It is (i/3)3 not i/(33)
                    if(used1[i][num] || used2[j][num] || used3[k][num])
                        return false;
                    used1[i][num] = used2[j][num] = used3[k][num] = 1;
                }

        return true;
    }
};

This is what k looks like:

0 1 2

3 4 5

6 7 8

Each number represents a 3 * 3 sub-matrix

• visualization of used3 of k

0  0  0 | 1  1  1 | 2  2  2
0  0  0 | 1  1  1 | 2  2  2
0  0  0 | 1  1  1 | 2  2  2
--------+---------+---------
3  3  3 | 4  4  4 | 5  5  5
3  3  3 | 4  4  4 | 5  5  5
3  3  3 | 4  4  4 | 5  5  5
--------+----------+--------
6  6  6 | 7  7  7 | 8  8  8
6  6  6 | 7  7  7 | 8  8  8
6  6  6 | 7  7  7 | 8  8  8