for Robot Artificial Inteligence

74. Find All Duplicates in an Array(easy)

09 Sep 2020 | Daily Algorithms 

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        unordered_map<int,int> op;
        vector<int> result;
        for(auto c : nums)
        {
            if(op[c]<1)
            {
                op[c]++;
            }
            else if(op[c]>0)
            {
                result.push_back(c);
            }

        }
        return result;


    }
};

Comment  Read more

73. Valid Palindrome

08 Sep 2020 | Daily Algorithms 

class Solution {
public:
    bool isPalindrome(string s) {
        vector<char> f;
        for(char c : s)
        {
            if(64<c and c<91 || 96<c and c<123 || 47<c and c<58)
            {
                if(64<c and c<91)
                {
                    c=c+32; // lower alphabet
                }
                f.push_back(c);
            }
        }
        int n = f.size()-1; // total size of
        for(int i = 0, j =n; i<=n; i++,j--)
        {
            if(f[i]!=f[j])
                return false;
        }

        return true;
    }
};

Comment  Read more

72. Design Hashset

08 Sep 2020 | Daily Algorithms

  • Since we do not need same elements multiple times, I used boolean array that can easily return the presence of the element in the array.

  • As per the constraints the size of the array is 1000000 and all elements are initialised to false.

  • Lets take following test case :-


class MyHashSet {
public:
    /** Initialize your data structure here. */
    bool arr[1000000]
    {
        false
    };

    MyHashSet() {

    }

    void add(int key) {
        arr[key] = true;
    }

    void remove(int key) {
        arr[key] = false;

    }

    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return arr[key];

    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

Comment  Read more

71. Power of Four(bitwise 사용)

07 Sep 2020 | Daily Algorithms

Explanation

  1. Solution Bit Manipulation the idea is : as we need to find the Num is power of 4 or not We Can Solve it by doing Bit Manipulation
  • [if Any num is valid power of 4 then it should be valid power of 2 as well] <- use this property

Let’s Suppose it they are asking for finding is the num is power of 2 or not then what should we do We just trying to find is that Num Have only one set bit or Not if there is only One set bit exist then we can blindly say that it’s A valid power of 2

so, the same idea we need here also but need to check one more condition.

what is the 2nd Condition would be. Let’s Find out by analysing Few Example

1 2 4 8 16 32 64 128 256 592 1084 …… -> This All Are Power Of Two [ Mean Having Only One Set Bit ]

1 4 16 64 256 1084……-> This All Are Power Of Four , Now We can Greedly Observe That Between two power_of_4 there Was One Invaild Power_Of_4 Exist

So Conditions Are :

  1. No of Set Bit Always Be Only ONE
  2. That SetBit Possition Should Be always In odd Place [ starting from Left ]

Let’s See Example :

No Bit_re SetBitPos No_of_setBit Valid_power_of_four 64 1 0 0 0 0 0 0 7 1 True <= :) 128 1 0 0 0 0 0 0 0 8 1 False <=2nd Condition fail :( 18 1 0 0 1 0 5,2 2 False <=1st Condition Fail :( 32 1 0 0 0 0 0 6 1 False <=2nd Condition fail :(

Time Complexcity O ( 1 ) =>as we Only Traverse max 32 Bit Space Complexcity O ( 1) => No Extra Space

Solution 1

class Solution {
public:
    bool isPowerOfFour(int num) {
        if(num<0)
            return false;
        for(int i=0;i<32;i+=2)
        {
            if(num==1<<i) // 두개씩 왼쪽 쉬프트해서 1이 되는 값이 나오면 true
                return true;
        }
        return false;


    }
};

Solution 2

return num>0&&!(num&(num-1))&&!((num-1)%3);

Comment  Read more

70. Detect Capital(쉬움)

07 Sep 2020 | Daily Algorithms 

class Solution {
public:
    bool detectCapitalUse(string word) {
        int n = word.size();
        if(n==1)
            return true;
        int cap = 0;
        for(auto c : word)
        {
            if(c<97) // if c is less than 'a' means Capital, cap++
                cap++;
        }
        if(cap == 1)
            return word[0]<97; // check if the first character is captial;
        else
            return cap == 0 || cap == n; // All capital or all lowercase

    }
};

Comment  Read more