Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
-------------------------------------------------------
Similar to level order traversal
can be done iteratively with a queue
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void side(vector<int> &rt, int level, TreeNode *root) {
if (root == NULL) {
return;
}
if (rt.size() < level) {
rt.push_back(root->val);
}else {
rt[level - 1] = root->val;
}
side(rt,level + 1, root->left);
side(rt,level + 1, root->right);
}
vector<int> rightSideView(TreeNode* root) {
vector<int> rt;
side(rt,1,root);
return rt;
}
};
Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
------------------------------------------------------
Solution #1 dfs
class Solution {
public:
void dfs(vector<vector<char>>& grid, vector<vector<bool> > &visit, int row, int col) {
if (row < 0 || row >= visit.size() || col < 0 || col >= visit[0].size() || visit[row][col] || grid[row][col] == '0') return;
visit[row][col] = true;
dfs(grid,visit,row + 1, col);
dfs(grid,visit,row - 1, col);
dfs(grid,visit,row, col + 1);
dfs(grid,visit,row, col - 1);
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
vector<vector<bool> > visit(m,vector<bool>(n,false));
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visit[i][j] && grid[i][j] == '1') {
count++;
dfs(grid,visit,i,j);
}
}
}
return count;
}
};
Solution #2 bfs
class Solution {
public:
void bfs(vector<vector<char>>& grid, vector<vector<bool> > &visit, int row, int col) {
queue<pair<int,int> > que;
que.push(make_pair(row,col));
visit[row][col] = true;
while (!que.empty()) {
pair<int,int> point = que.front();
que.pop();
row = point.first;
col = point.second;
if (row + 1 < visit.size() && !visit[row + 1][col] && grid[row + 1][col] == '1') {
que.push(make_pair(row + 1,col));
visit[row + 1][col] = true;
}
if (row - 1 >= 0 && !visit[row - 1][col] && grid[row - 1][col] == '1') {
que.push(make_pair(row - 1,col));
visit[row - 1][col] = true;
}
if (col - 1 >= 0 && !visit[row][col - 1] && grid[row][col - 1] == '1') {
que.push(make_pair(row,col - 1));
visit[row][col - 1] = true;
}
if (col + 1 < visit[0].size() && !visit[row][col + 1] && grid[row][col + 1] == '1') {
que.push(make_pair(row,col + 1));
visit[row][col + 1] = true;
}
}
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if (m == 0) return 0;
int n = grid[0].size();
vector<vector<bool> > visit(m,vector<bool>(n,false));
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visit[i][j] && grid[i][j] == '1') {
bfs(grid,visit,i,j);
count++;
}
}
}
return count;
}
};
Bitwise AND of Numbers Range
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
---------------------------------------
The idea is very simple:
- last bit of (odd number & even number) is 0.
- when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
- Move m and n rigth a position.
Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int count = 0;
while (m != n) {
m >>= 1;
n >>= 1;
count++;
}
return m << count;
}
};
Happy Number
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 1
----------------------------------------------
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> s;
while (s.find(n) == s.end()) {
if (n == 1) return true;
s.insert(n);
int sum = 0;
while (n != 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
n = sum;
}
return false;
}
};
Remove Linked List Elements
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
--------------------------------------------------------
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *itr = dummy;
while (itr->next != NULL) {
if (itr->next->val == val) {
itr->next = itr->next->next;
}else {a
itr = itr->next;
}
}
return dummy->next;
}
};
Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.
Note:
You may assume both s and t have the same length.
--------------------------------------------
class Solution {
public:
bool isIsomorphic(string s, string t) {
vector<char> dicS(256,'\0');
vector<char> dicT(256,'\0');
for (int i = 0; i < s.length(); i++) {
if (dicS[s[i]] == '\0' && dicT[t[i]] == '\0') {
dicS[s[i]] = t[i];
dicT[t[i]] = s[i];
}else if (dicS[s[i]] != t[i] || dicT[t[i]] != s[i]) {
return false;
}
}
return true;
}
};
Reverse Linked List
Reverse a singly linked list.
----------------------------------------------------------------
Iterative
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *newHead = NULL;
while (head != NULL) {
ListNode *temp = head->next;
head->next = newHead;
newHead = head;
head = temp;
}
return newHead;
}
};
Recursive
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *rev(ListNode* head, ListNode * newHead) {
if (head == NULL) return newHead;
ListNode *temp = head->next;
head->next = newHead;
return rev(temp,head);
}
ListNode* reverseList(ListNode* head) {
return rev(head,NULL);
}
};
