Week 3 | Grind 169 | Blind 75
1. Same Tree
Given the roots of two binary trees p
and q
, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Iterative
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<TreeNode*> que;
if(p==NULL || q==NULL) return p==q;
que.push(p); que.push(q);
while(!que.empty()) {
TreeNode* left = que.front(); que.pop();
TreeNode *right = que.front(); que.pop();
if(left==NULL && right==NULL) continue;
if(left==NULL || right==NULL) return false;
if(left->val != right->val) return false;
que.push(left->left);
que.push(right->left);
que.push(left->right);
que.push(right->right);
}
return true;
}
Recursive
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q== NULL) return true;
if(p == NULL || q== NULL) return false;
if(p->val != q->val) return false;
return isSameTree(p->right, q->right) && isSameTree(p->left, q->left) ;
}
2. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight
).
Note:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation 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 3, the input represents the signed integer.
Naive
int setBits(int N) {
int count = 0;
while(N){
count += (N & 1);
N = N >> 1;
}
return count;
}
Brian Kernighan’s Algorithm
int setBits(int N) {
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count;
}
STL
int hammingWeight(uint32_t n) {
return __builtin_popcount(n);
}
Converting to string
int hammingWeight(uint32_t n){
string bin = bitset<32>(n).to_string();
int counter = count(bin.begin(), bin.end(), '1');
return counter;
}
3. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string ""
.
Horizontal scanning
string longestCommonPrefix(vector<string>& str) {
int n = str.size();
if(n == 1) return str[0];
string ans = "";
int longest = INT_MAX, curr, j, k;
for(int i=0; i<n-1; i++){
curr = j = k = 0;
int a = str[i].size(), b = str[i+1].size();
while(j < a and k < b and str[i][j++] == str[i+1][k++])
curr++;
if(curr == 0) return "";
if(curr < longest){
ans = str[i].substr(0 , curr);
longest = curr;
}
}
return ans;
}
Vertical scanning
string longestCommonPrefix(vector<string>& str) {
int n = str.size();
if (n == 0) return "";
for (int i = 0; i < str[0].size(); i++){
char c = str[0][i];
for (int j = 1; j < n; j ++)
if (i == str[j].size() || str[j][i] != c)
return str[0].substr(0, i);
}
return str[0];
}
4. Single Number
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
int singleNumber(vector<int>& nums) {
int ans = 0;
for(auto e: nums)
ans ^= e;
return ans;
}