for Robot Artificial Inteligence

44. Number of 1 Bits

15 Jul 2020 | Daily Algorithms

Explain

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int result = 0;
        while(n)
        {
            n &= (n-1);
            result++;
        }
        return result;
    }
};

n & (n - 1) drops the lowest set bit. It’s a neat little bit trick.

Let’s use n = 00101100 as an example. This binary representation has three 1s.

If n = 00101100, then n - 1 = 00101011, so n & (n - 1) = 00101100 & 00101011 = 00101000. Count = 1.

If n = 00101000, then n - 1 = 00100111, so n & (n - 1) = 00101000 & 00100111 = 00100000. Count = 2.

If n = 00100000, then n - 1 = 00011111, so n & (n - 1) = 00100000 & 00011111 = 00000000. Count = 3.

n is now zero, so the while loop ends, and the final count (the numbers of set bits) is returned.

using STL

class Solution {
public:
    int hammingWeight(uint32_t n) {
        return bitset<32>(n).count();
    }
};

Comment  Read more

관심있는 한국 로봇 회사들

14 Jul 2020 | daily

Top Tier

  • 네이버 랩스
  • 로보틱스
  • 배달의 민족
  • LG전자
  • 현대자동차
  • SK텔레콤
  • 삼성전자
  • KT

Second Tier

  • 유진 로봇
  • 현대 로보틱스
  • 한화 로봇
  • 두산 로보틱스
  • 닐손 로봇

Third Tier

  • 벨류체인씨엔티
  • 워드로봇
  • 서울로보틱스

Comment  Read more

43. Roman to Integer

13 Jul 2020 | Daily Algorithms 

class Solution {
public:
    int romanToInt(string s) {

        int res =0;
        int temp  = 0;
        for(int i = 0; i<s.size(); i++)
        {
            char sym = s[i];
            int pos = 0;
            switch(sym)
            {
                case 'I': pos = 1; break;
                case 'V': pos = 5; break;
                case 'X': pos = 10; break;
                case 'L': pos = 50; break;
                case 'C': pos = 100; break;
                case 'D': pos = 500; break;
                case 'M': pos = 1000; break;
                default : return 0;
            }
            res += pos;
            if(temp<pos)
            {
                res -= 2*temp;
            }
            temp = pos;
        }

        return res;

    }
};

Comment  Read more

42. Power of Three

13 Jul 2020 | Daily Algorithms 

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n == 0)
            return false;
        while(n!=1)
        {
            if(n%3 != 0)
                return false;
            n = n/3;
            cout<< n<< " ";
        }
        return true;
    }
};

Comment  Read more

41. Count Primes

13 Jul 2020 | Daily Algorithms

My Version

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> pass(n,true);
        pass[0] = false, pass[1] = false;
        for(int i = 0; i<sqrt(n);++i)
        {
            if(pass[i])
            {
                for(int j = i*i; j<n; j+=i)
                {
                    pass[j] = false;
                }
            }
        }
        return count(pass.begin(),pass.end(),true);
    }
};

Other

class Solution {
public:
int countPrimes(int n) {
    if (n<=2) return 0;
	vector<bool> passed(n, false);
	int sum = 1;
	int upper = sqrt(n);
	for (int i=3; i<n; i+=2) {
		if (!passed[i]) {
			sum++;
			//avoid overflow
			if (i>upper) continue;
			for (int j=i*i; j<n; j+=i) {
				passed[j] = true;
			}
		}
	}
	return sum;
}
};

Comment  Read more