LeetCode Record (Easy)
Begin to pratice coding in leetcode, record here for convenient review.
Date: 2015.10.8
Add Digit
——————————————————————–
Maximum Depth of Binary Tree
——————————————————————–
Delete Node in a Linked List
——————————————————————–
Same Tree
——————————————————————–
Move Zeros
——————————————————————–
Invert Binary Tree
——————————————————————–
Number of 1 Bits
——————————————————————–
Contains Duplicate
——————————————————————–
Excel Sheet Column Number
——————————————————————–
Majority Element
——————————————————————–
Valid Anagram
——————————————————————–
Remove Duplicates
——————————————————————–
Climb Stairs
Knowledge
1. Review of Binary Tree
2. Review of Linked List
3. Recursive Algorithm and Thinking Pattern
——————————————————————–
Date: 2015.10.15
Nim Game
Date: 2015.10.8
Add Digit
class Solution {
public:
int addDigits(int num) {
return calc(num);
}
int calc(int num) {
int sum = 0;
while(true){
int tem = num%10;
sum+=tem;
num = num/10;
if(num==0)
break;
}
if(sum/10==0) return sum;
else return calc(sum);
}
};
——————————————————————–
Maximum Depth of Binary Tree
/**
* 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:
int maxDepth(TreeNode* root) {
if(!root)
return 0;
return calcDepth(root);
}
int calcDepth(TreeNode* node){
int leftDepth = 0, rightDepth = 0;
if(node->left!=NULL)
leftDepth = calcDepth(node->left);
if(node->right!=NULL)
rightDepth = calcDepth(node->right);
int depth = leftDepth>rightDepth? leftDepth:rightDepth;
depth++;//Important: once enter calcDepth() method, depth + 1
return depth;
}
};
——————————————————————–
Delete Node in a Linked List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
if(node->next)
node->val = node->next->val;
node->next = node->next->next;
}
};
——————————————————————–
Same Tree
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==NULL && q==NULL)
return true;
else if(p==NULL && q!=NULL)
return false;
else if(p!=NULL && q==NULL)
return false;
return isSameFromNode(p,q);
}
bool isSameFromNode(TreeNode* p, TreeNode* q){
TreeNode* pleft = p->left;
TreeNode* pright = p->right;
TreeNode* qleft = q->left;
TreeNode* qright = q->right;
int pVal = p->val;
int qVal = q->val;
bool leftBool=false, rightBool=false;
if(pleft!=NULL && qleft!=NULL && pVal==qVal){
leftBool = isSameFromNode(pleft, qleft);
} else if(pleft==NULL && qleft==NULL && pVal==qVal){
leftBool = true;
}
if(pright!=NULL && qright!=NULL && pVal==qVal){
rightBool = isSameFromNode(pright, qright);
} else if(pright==NULL && qright==NULL && pVal==qVal){
rightBool = true;
}
return (leftBool&&rightBool);
}
};
——————————————————————–
Move Zeros
class Solution {
public:
void moveZeroes(vector<int>& nums) {
vector<int>::iterator iter = nums.begin();
int count = 0;
while(iter!=nums.end()){
if(*iter!=0){
iter++;
continue;
}
nums.erase(iter);
count++;
}
for(int i = 0; i < count; i++){
nums.push_back(0);
}
}
};
——————————————————————–
Invert Binary Tree
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root){
invert(root);
}
return root;
}
void invert(TreeNode* node){
TreeNode* tem = node->left;
node->left = node->right;
node->right = tem;
if(node->left)
invert(node->left);
if(node->right)
invert(node->right);
}
};
——————————————————————–
Number of 1 Bits
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(true){
if(n==0) break;
if(n%2==0) {//even
n=n/2;//move right
} else {//odd
n=n-1;
count++;
n=n/2;//move right
}
}
return count;
}
};
——————————————————————–
Contains Duplicate
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if(nums.size()==0)
return false;
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size()-1; i++){
if(nums[i]==nums[i+1])
return true;
}
return false;
}
};
——————————————————————–
Excel Sheet Column Number
class Solution {
public:
int titleToNumber(string s) {
// don't need to transform to uppercase
// transform(s.begin(), s.end(), s.begin(), ::toupper);
int sum = 0;
int len = s.length();
for(int i = 0; iint num = (int)s[i]-64;
int order = len-1-i;
sum+=num*pow(26,order);
}
return sum;
}
};
——————————————————————–
Majority Element
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
// int total=nums.size();
// //init with first element
// int count=1;
// int res = nums[0];
// //loop
// for(int i=1; i
// //equal and go on counting
// if(nums[i]==nums[i-1]){
// count++;
// continue;
// }
// // not equal and not gt half
// if(nums[i]!=nums[i-1] && count<=total/2){
// res=nums[i];
// count=1;
// continue;
// }
// }
// return res;
}
};
——————————————————————–
Valid Anagram
class Solution {
public:
bool isAnagram(string s, string t) {
//this is slow, but extremely readable
sort(s.begin(),s.end());
sort(t.begin(),t.end());
if(s==t) return true;
else return false;
}
};
——————————————————————–
Remove Duplicates
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head)
checkEqualAndDelete(head, head->next);
return head;
}
void checkEqualAndDelete(ListNode* node, ListNode* next){
if(!node || !next) return;
if(node->val!=next->val)
checkEqualAndDelete(next, next->next);
else {
if(next->next)
node->next->val = next->next->val;
node->next = next->next;
checkEqualAndDelete(node, node->next);
}
}
};
——————————————————————–
Climb Stairs
class Solution {
public:
int climbStairs(int n) {
// return climb(n);
return climbFaster(n);
}
//recursive is slow
int climb(int remain){
if(remain==1 || remain==2)
return remain;
return climb(remain-2)+climb(remain-1);
}
//none recursive is fast
int climbFaster(int n){
int step[n+1];
step[1]=1; step[2]=2;
for(int i = 3; i < n+1; i++){
step[i] = step[i-1]+step[i-2];
}
return step[n];
}
};
Knowledge
1. Review of Binary Tree
2. Review of Linked List
3. Recursive Algorithm and Thinking Pattern
——————————————————————–
Date: 2015.10.15
Nim Game
class Solution {
public:
bool canWinNim(int n) {
// recursive method is slow, time limited
// return recursive(n);
// iterative method is faster, but will cause runtime limit
// return iterative(n);
// mathematical method
return math(n);
}
bool recursive(int n){
if(n<=3)
return true;
bool takeOne = !canWinNim(n-1);
bool takeTwo = !canWinNim(n-2);
bool takeThree = !canWinNim(n-3);
return takeOne||takeTwo||takeThree;
}
bool iterative(int n){
bool flag[n+1];//ignore index 0 for readability....
flag[1]=true; flag[2]=true; flag[3]=true;
for(int i = 4; i < n+1; i++){
flag[i] = (!flag[i-1]) || (!flag[i-2]) || (!flag[i-3]);
}
return flag[n];
}
bool math(int n){
int remain = n%4;
if(remain==0) return false;
else return true;
}
};