{{ message }}

Instantly share code, notes, and snippets.

# xiren-wang

Created Sep 4, 2014
combination sum II. every candidate can only be used once.
View combination_sum_II.cpp
 class Solution { public: //recursive; push one candidate C to a vector, then find new target = target - C // remember which is visited; if visited, just neglect in next finding vector > combinationSum2(vector &candidates, int target) { vector > vvInt; set >svInt; vector oneCombination; vector visited((int)candidates.size(), false); sort(candidates.begin(), candidates.end());
Created Sep 4, 2014
combination sum.
View combination_sum.cpp
 class Solution { public: //recursive; push one candidate C to a vector, then find new target = target - C vector > combinationSum(vector &candidates, int target) { vector > vvInt; set >svInt; vector oneCombination; sort(candidates.begin(), candidates.end()); getCombinationSum(candidates, target, oneCombination, svInt);
Created Sep 4, 2014
simplify path.
View simplify_path.cpp
 /* Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" */ class Solution { public:
Created Sep 3, 2014
maximum subarray
View maximum_subarray.cpp
 class Solution { public: // two ways: // 1. iterative, O(n): sum from left; if <0, reset to 0; get max() at every step // 2. divide and conquer: // max = max(left), or max(right), or max(cross_left_right) // cross_left_right is also to get max_from_middle_to_left, and max_from_middle+1_to_right /*int maxSubArray(int A[], int n) { if (n <= 0) return 0;
Created Sep 3, 2014
search a 2D matrix
View search_a_2D_matrix.cpp
 /* 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. For example, Consider the following matrix:
Last active Aug 29, 2015
path sum II.
View path_sum_II.cpp
 /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example:
Created Sep 3, 2014
surrounded regions.
View surrounded_regions.cpp
 class Solution { public: /* Surrounded Regions Total Accepted: 12671 Total Submissions: 89715 Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.
Created Sep 2, 2014
longest consecutive sequence
View longest_consecutive_sequence.cpp
 /* 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 {
Created Sep 2, 2014
candy. minimum num of candy
View candy.cpp
 /* There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give? */
Created Sep 2, 2014
combination. Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
View combination.cpp
 class Solution { public: vector > combine(int n, int k) { vector > vvInt; set > svInt; //to avoid duplications like [4,1] and [1 4] if ( n <= 0 || k < 0) return vvInt; //select all combinations, but only select those with k elemetns int cnt = 0;
You can’t perform that action at this time.