for Robot Artificial Inteligence

49. Missing Number

16 Jul 2020 | Daily Algorithms

My Solution

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if(nums.size()==1 && nums[0]==1)
        {
            return 0;
        }
        if(nums.size() == 1 && nums[0] == 0)
        {
            return 1;
        }
        int current_sum = 0;
        int max = INT_MIN;
        int min = INT_MAX;
        for(int i : nums)
        {
            current_sum = current_sum + i;
            if(max<i)
            {
                max = i;
            }
            if(min>i)
            {
                min = i;
            }
        }
        int expected_sum = 0;
        for(int i = 0; i<=max; i++)
        {
            expected_sum = expected_sum + i;
        }
        if(expected_sum - current_sum == 0)
        {
            if(min!=0)
            {
                return 0;
            }
            else
            {
                return max+1;
            }
        }
        return expected_sum - current_sum;

    }
};

Comment  Read more

48. Valid Parentheses

16 Jul 2020 | Daily Algorithms 

class Solution {
public:
    bool isValid(string s) {
        if (s.empty())
            return true;
        stack<char> database;

        for(char n : s)
        {
            if(n =='(' || n=='[' || n=='{')
            {
                database.push(n);
            }
            else
            {
                if(database.empty()) return false;
                if(n == ')' && database.top()!='(') return false;
                if(n == ']' && database.top()!='[') return false;
                if(n == '}' && database.top()!='{') return false;

                database.pop();
            }
        }
        return database.empty();


    }
};

Comment  Read more

47. Pascal's Triangle

16 Jul 2020 | Daily Algorithms 

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        for(auto i = 0; i<numRows; ++i)
        {
            res.push_back(vector<int>(i+1,1)); // i+1는 어레이 갯수를 말하고, 1은 set value 이다.
            for(auto j=1; j<i; ++j)
            {
                res[i][j] = res[i-1][j-1] + res[i-1][j];
            }
        }
        return res;

    }
};

Comment  Read more

46. Reverse Bits(어려움)

16 Jul 2020 | Daily Algorithms 

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t m = 0; // 0000000000000000000000000000
        for(int i =0; i<32; i++, n >>=1)
        {
            m<<=1; // 1값이 있을경우 왼쪽으로 쉬프트
            m |= n & 1; // //  
        }
        return m;

    }
};
  • By m«=1, you are left-shifting the value of m by 1 bit in every iteration.
    • If you do m«=1 afterwards, you will get an extra bit 0 on the LSB. since we do it before m =n&1, the extra 0 will show on the left. you can try some tests, the first time of this loop will clearly show it.
  • By m =n&1, i.e., m=m n&1you are checking if the LSB of m or the LSB of n is set, in which case you are setting the LSB of m. Then you move on to the next bit and so on…

Explain

with that in mind lets simplify the loop to 4 bits:

at the beginning m = 0000; n = 1010;

the first iteration m = 0000; n = 0101; n »=1 = n register is shifted to the right by one bit and nothing happens to m;

m«=1 // 현재 m에 1값이 없므로 nothing happen m |= n & 1 // n & 1 =(0101 & 0001)은 0001 // 0000 |= 0001 은 m= 0001이 된다.

second iteration n =0010; // n »=1을 통하여 0101 값을 오른쪽 쉬프트 m= 0010; // 첫번째 iteration에서 m 은 0001이 되었고, m«=1 operation을 통해 1값은 왼쪽으로 옮긴다. m |= n & 1 // n & 1 =(0010 & 0001)은 0000 // 0010 |= 0000 은 m= 0010이 된다.

third iteration m = 0100; n = 0001;

m |= n & 1 // n & 1 =(0001 & 0001)은 0001 // 0100 |= 0001 은 m= 0101이 된다

we return m;

we are essentially pushing bits from 1 register to another.

Comment  Read more

45. Hamming Distance(약간 헷갈림)

15 Jul 2020 | Daily Algorithms 

class Solution {
public:
    int hammingDistance(int x, int y) {
        int result = 0;
        int n = x^y; // binary number로 만들어 준다.
        while(n)
        {
            n &= (n-1);
            result ++;
        }
        return result;


    }
};

Hi, I spent 4 hours thinking how it works. It’s Brian Kernighan’s algorithm.

  1. After we got XOR (n = x ^ y) which gives us a binary where count of 1’s (set bits) is exactly the number of different bits in the given pair of numbers, we only need to count those 1’s (set bits). [0]1[1]00 ^ [1]1[0]00 = [1]0[1]00

  2. LOOP STARTS: with (n-1) we will have all the bits flipped after the rightmost set bit(1) of n (including the rightmost set bit) and leave bits to the left untouched. Consider: 10[100] - 00[001] = 10[011] or 111010[1]- 000000[1]= 111010[0]

  3. now that we have ‘inverted’ the rightmost set bit, we can easily convert it and all the bits after it to 0 by doing n &= n -1; 10[100]& 10[011]= 10[000]

count this loop (++dist)

while loop breaks when we do operation 2 and 3 for the leftmost set bit (leftmost 1) because then n turns into 0. LOOP ENDS.

return dist.

that’s it :)

link explaining the algo: https://www.techiedelight.com/brian-kernighans-algorithm-count-set-bits-integer/

Comment  Read more