Skip to content

Instantly share code, notes, and snippets.

View zhoutuo's full-sized avatar

Z.T. Yang zhoutuo

7 followers · 0 following
View GitHub Profile
@zhoutuo
zhoutuo / Pow(x, n).cpp
Created March 21, 2013 17:23
Implement pow(x, n).
class Solution {
public:
double pow(double x, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n == 0) {
return 1;
}
@zhoutuo
zhoutuo / Longest Consecutive Sequence.cpp
Created March 19, 2013 00:44
Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity.
class Solution {
public:
int longestConsecutive(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
unordered_map<int, int> map;
int res = 1;
for(int i = 0; i < num.size(); ++i) {
int cur = num[i];
if(map.find(cur) != map.end()) {
@zhoutuo
zhoutuo / Remove Duplicates from Sorted List II.cpp
Created March 17, 2013 18:00
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
@zhoutuo
zhoutuo / Partition List.cpp
Created March 17, 2013 17:04
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
@zhoutuo
zhoutuo / Decode Ways.cpp
Created March 17, 2013 05:54
A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). The number of ways decoding "12" is 2.
class Solution {
public:
int numDecodings(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s.length() == 0) {
return 0;
}
@zhoutuo
zhoutuo / Recover Binary Search Tree.cpp
Created March 8, 2013 04:44
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
@zhoutuo
zhoutuo / Binary Tree Level Order Traversal.cpp
Created March 1, 2013 20:49
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ]
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
@zhoutuo
zhoutuo / Balanced Binary Tree.cpp
Created February 26, 2013 23:00
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
@zhoutuo
zhoutuo / Flatten Binary Tree to Linked List.cpp
Created February 26, 2013 22:41
Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
@zhoutuo
zhoutuo / Triangle.cpp
Created February 26, 2013 21:53
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> second = triangle[triangle.size() - 1];
for(int i = triangle.size() - 2; i >= 0; --i) {
vector<int> first = triangle[i];