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 / Validate Binary Search Tree.cpp
Created February 24, 2013 00:16
Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.
/**
* 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 / Search a 2D Matrix.cpp
Created February 26, 2013 06:17
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//search row first
int low = 0;
int high = matrix.size();
@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];
@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 / 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 / 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 / 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 / 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 / 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 / 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: