Skip to content

Instantly share code, notes, and snippets.

@xiren-wang
xiren-wang / combination_sum_II.cpp
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<vector<int> > combinationSum2(vector<int> &candidates, int target) {
vector<vector<int> > vvInt;
set<vector<int> >svInt;
vector<int> oneCombination;
vector<bool> visited((int)candidates.size(), false);
sort(candidates.begin(), candidates.end());
View combination_sum.cpp
class Solution {
public:
//recursive; push one candidate C to a vector, then find new target = target - C
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
vector<vector<int> > vvInt;
set<vector<int> >svInt;
vector<int> oneCombination;
sort(candidates.begin(), candidates.end());
getCombinationSum(candidates, target, oneCombination, svInt);
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:
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;
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:
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:
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.
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 {
@xiren-wang
xiren-wang / candy.cpp
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?
*/
@xiren-wang
xiren-wang / combination.cpp
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<vector<int> > combine(int n, int k) {
vector<vector<int> > vvInt;
set<vector<int> > 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.