Posts tagged as “bit”

花花酱 LeetCode 190. Reverse Bits

By zxi on September 30, 2019

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Solution: Bit operation

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

uint32_t reverseBits(uint32_t n) {

uint32_t ans = 0;

for (int i = 0; i < 32; ++i) {

ans <<= 1;

ans |= n & 1;

n >>= 1;

}

return ans;

}

};

花花酱 LeetCode 1125. Smallest Sufficient Team

By zxi on July 15, 2019

In a project, you have a list of required skills req_skills, and a list of people. The i-th person people[i] contains a list of skills that person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person: for example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].

Return any sufficient team of the smallest possible size, represented by the index of each person.

You may return the answer in any order. It is guaranteed an answer exists.

Example 1:

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

Example 2:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

Constraints:

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
It is guaranteed a sufficient team exists.

Solution: DP

C++/Array

// Author: Huahua, 24 ms / 11 MB

class Solution {

public:

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {

const int n = req_skills.size();

const int target = (1 << n) - 1;

vector<int> skills;

for (const auto& p : people) {

int mask = 0;

for (const string& s: p)

mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills));

skills.push_back(mask);

}

vector<int> dp((1 << n), INT_MAX / 2);

vector<pair<int, int>> pt((1 << n));

dp[0] = 0;

for (int i = 0; i < people.size(); ++i) {

const int k = skills[i];

if (k == 0) continue;

for (int j = target; j >= 0; --j)

if (dp[j] + 1 < dp[j | k]) {

dp[j | k] = dp[j] + 1;

pt[j | k] = {j, i};

}

int t = target;

vector<int> ans;

while (t) {

ans.push_back(pt[t].second);

t = pt[t].first;

}

return ans;

}

};

C++/HashTable

// Author: Huahua, 272 ms / 94.8 MB

class Solution {

public:

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {

const int n = req_skills.size();

vector<int> skills;

for (const auto& p : people) {

int mask = 0;

for (const string& s: p)

mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills));

skills.push_back(mask);

}

unordered_map<int, vector<int>> dp;

dp[0] = {};

for (int i = 0; i < people.size(); ++i) {

unordered_map<int, vector<int>> tmp(dp);

for (const auto& kv : dp) {

int k = kv.first | skills[i];

if (!tmp.count(k) || kv.second.size() + 1 < tmp[k].size()) {

tmp[k] = kv.second;

tmp[k].push_back(i);

}

tmp.swap(dp);

}

return dp[(1 << n) - 1];

}

};

花花酱 LeetCode 1073. Adding Two Negabinary Numbers

By zxi on June 6, 2019

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Note:

1 <= arr1.length <= 1000
1 <= arr2.length <= 1000
arr1 and arr2 have no leading zeros
arr1[i] is 0 or 1
arr2[i] is 0 or 1

Solution: Simulation

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 8 ms, 9.2 MB

class Solution {

public:

vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {

int i = arr1.size();

int j = arr2.size();

int carry = 0;

vector<int> ans;

while (i || j || carry) {

int sum = (i ? arr1[--i] : 0) + (j ? arr2[--j] : 0) + carry;

ans.push_back(sum & 1);

carry = -(sum >> 1);

}

while (ans.back() == 0 && ans.size() > 1) ans.pop_back();

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 67. Add Binary

By zxi on April 10, 2019

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Solution: Big integer

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string addBinary(string a, string b) {

int carry = 0;

int i = a.length() - 1;

int j = b.length() - 1;

string ans;

while (i >= 0 || j >= 0) {

int s = (i >= 0 ? a[i--] - '0' : 0) +

(j >= 0 ? b[j--] - '0' : 0) +

carry;

carry = s >> 1;

ans += '0' + (s & 1);

}

if (carry) ans += '1';

return {rbegin(ans), rend(ans)};

}

};

花花酱 LeetCode 1012. Complement of Base 10 Integer

By zxi on March 16, 2019

Every non-negative integer N has a binary representation. For example, 5 can be represented as "101" in binary, 11 as "1011" in binary, and so on. Note that except for N = 0, there are no leading zeroes in any binary representation.

The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1. For example, the complement of "101" in binary is "010" in binary.

For a given number N in base-10, return the complement of it’s binary representation as a base-10 integer.

Example 1:

Input: 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Note:

0 <= N < 10^9

Solution: Bit

Find the smallest binary number c that is all 1s, (e.g. “111”, “11111”) that is greater or equal to N.
ans = C ^ N or C – N

Time complexity: O(log(n))
Space complexity: O(1)

C++

// Author: Huahua, running time: 4 ms, 8 MB

class Solution {

public:

int bitwiseComplement(int N) {

int c = 1;

while (c < N)

c = (c << 1) | 1;

return N ^ c;

}

};