Begin to pratice coding in leetcode, record here for convenient review.
Date: 2015.10.8
Add Digit
class Solution {
public:
int addDigits(int num) {
return calc(num);
}
int calc(int num) {
int sum = ;
while(true){
int tem = num%;
sum+=tem;
num = num/;
if(num==)
break;
}
if(sum/==) 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 ;
return calcDepth(root);
}
int calcDepth(TreeNode* node){
int leftDepth = , rightDepth = ;
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 = ;
while(iter!=nums.end()){
if(*iter!=){
iter++;
continue;
}
nums.erase(iter);
count++;
}
for(int i = ; i < count; i++){
nums.push_back();
}
}
};
——————————————————————–
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 = ;
while(true){
if(n==) break;
if(n%==) {//even
n=n/;//move right
} else {//odd
n=n-;
count++;
n=n/;//move right
}
}
return count;
}
};
——————————————————————–
Contains Duplicate
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
if(nums.size()==)
return false;
sort(nums.begin(),nums.end());
for(int i = ; i < nums.size()-; i++){
if(nums[i]==nums[i+])
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 = ;
int len = s.length();
for(int i = ; i<len; i++){
int num = (int)s[i]-;
int order = len--i;
sum+=num*pow(,order);
}
return sum;
}
};
——————————————————————–
Majority Element
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/];
// int total=nums.size();
// //init with first element
// int count=1;
// int res = nums[0];
// //loop
// for(int i=1; i<total; 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== || remain==)
return remain;
return climb(remain-)+climb(remain-);
}
//none recursive is fast
int climbFaster(int n){
int step[n+];
step[]=; step[]=;
for(int i = ; i < n+; i++){
step[i] = step[i-]+step[i-];
}
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<=)
return true;
bool takeOne = !canWinNim(n-);
bool takeTwo = !canWinNim(n-);
bool takeThree = !canWinNim(n-);
return takeOne||takeTwo||takeThree;
}
bool iterative(int n){
bool flag[n+];//ignore index 0 for readability....
flag[]=true; flag[]=true; flag[]=true;
for(int i = ; i < n+; i++){
flag[i] = (!flag[i-]) || (!flag[i-]) || (!flag[i-]);
}
return flag[n];
}
bool math(int n){
int remain = n%;
if(remain==) return false;
else return true;
}
};