zhoutuo’s gists

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 / 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 / Binary Tree Inorder Traversal.cpp

Created February 23, 2013 23:48

Given a binary tree, return the inorder traversal of its nodes' values.

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {

zhoutuo / Combination sum.cpp

Created February 19, 2013 06:22

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, â€¦ , ak) must be in non-descending orde…

	class Solution {
	public:
	vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	sort(candidates.begin(), candidates.end());
	vector<int> curResult;
	vector<vector<int> > results;
	solve(candidates, target, results, 0, curResult);
	return results;

zhoutuo / Search for a Range.cpp

Created February 19, 2013 01:40

Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

	class Solution {
	public:
	vector<int> searchRange(int A[], int n, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function

	int low = low_bound(A, n, target);
	int high = high_bound(A, n, target);

zhoutuo / Search insert position.cpp

Created February 19, 2013 00:00

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0

+class Solution {
+public:
+    int searchInsert(int A[], int n, int target) {
+        // Start typing your C/C++ solution below
+        // DO NOT write int main() function
+        int low = 0;
+        int high = n;
+        while(low < high) {
+            int middle = low + (high - low) / 2;
+            if(A[middle] == target) {

zhoutuo / Next Permutation.cpp

Last active December 13, 2015 22:08

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left…

	class Solution {
	public:
	void nextPermutation(vector<int> &num) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	bool found = false;
	int left = -1;
	int right = num.size();
	for(int i = num.size() - 1; i >= 0; --i) {
	int cur = num[i];

zhoutuo / Merge Two Sorted Lists.cpp

Created February 16, 2013 22:26

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:

zhoutuo / Plus One.cpp

Created February 16, 2013 22:13

Given a number represented as an array of digits, plus one to the number.

	class Solution {
	public:
	vector<int> plusOne(vector<int> &digits) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function

	for(int i = 0; i < digits.size() / 2; ++i) {
	swap(digits[i], digits[digits.size() - i - 1]);
	}

zhoutuo / Divide two integers.cpp

Created February 16, 2013 00:19

Divide two integers without using multiplication, division and mod operator.

	//
	// main.cpp
	// Divide_Two_Integers
	//
	// Created by Zhoutuo Yang on 2/15/13.
	// Copyright (c) 2013 Zhoutuo Yang. All rights reserved.
	//

	#include <iostream>
	using namespace std;

Z.T. Yang zhoutuo