safeng’s gists

safeng / rect_intersect.cc

Created October 8, 2014 03:12

Check whether xy-aligned rectangle r1 and r2 intersects. If it is, return the intersected range.

	#include <iostream>
	using namespace std;

	struct Rectangle {
	int x, y, width, height;
	};

	bool is_intersect(const Rectangle &r1, const Rectangle &r2);

	Rectangle rect_intersect(const Rectangle &r1, const Rectangle &r2)

safeng / gen_rand.cc

Created October 8, 2014 01:14

Generate uniform random numbers in [a, b] from 0/1 random number generator

	#include <iostream>
	#include <cstdlib>
	#include <ctime>
	using namespace std;
	// Generate random numbers in large ranges with random number
	// generator in small ranges

	// For random number generator with 0/1, we can use it to generate bits
	unsigned char zero_one()
	{

safeng / max_prod.cc

Last active August 29, 2015 14:06

Maximum Product Subarray

	class Solution {
	public:
	int maxProduct(int A[], int n) {
	if (n == 0)
	return 0;
	// record both min values and max values. Use dp
	int max_pre = A[0];
	int min_pre = A[0];
	int max_value = A[0];
	int min_cur, max_cur;

safeng / generateTrees.cc

Created May 16, 2014 02:39

Unique Binary Search Trees II

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

safeng / reverseWords.cc

Created March 16, 2014 06:39

Reverse Words in a String. Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the".

	class Solution {
	public:
	void reverseWords(string &s) {
	if(s.size() == 0)
	return;
	reverse(s.begin(), s.end());
	// reverse word by word
	istringstream iss(s);
	string word;
	ostringstream oss;

safeng / anagramsStr.cc

Created January 24, 2014 04:07

Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case.

	class Solution {
	public:
	vector<string> anagrams(vector<string> &strs) {
	// find distribution or sort
	vector<string> res;
	int n = strs.size();
	// sort each string in string array
	// use hash to find equal elements of two arrays or duplicate elements in one array
	unordered_map<string, int> dict;
	for(int i = 0; i<n; ++i)

safeng / longestValidParentheses.cc

Created January 20, 2014 06:13

Longest Valid Parentheses Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

	class Solution {
	public:
	int longestValidParentheses(string s) {
	vector<int> dp(s.size(),0);
	int max=0;
	for(int i=s.size()-2; i>=0; i--)
	{
	if(s[i]=='(')
	{
	int j=i+1+dp[i+1];

safeng / findSubstring.cc

Created January 20, 2014 04:54

Substring with Concatenation of All Words You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. For example, given: S: "barfoothefoobarman" L: ["foo", "bar"] You should return…

	class Solution {
	public:
	vector<int> findSubstring(string S, vector<string> &L) {
	vector<int> ret;
	if(S.empty() \|\| L.empty() \|\| S.size()<L.size()*L[0].size())
	return ret;
	int wordLength = L[0].size(), sumLength=L.size()*wordLength;
	//Initilize hashtable: needFound[L[i]] is no. of occurences of L[i] in L
	unordered_map<string, int> needFound; // may contain duplicates
	for(int i=0; i<L.size(); ++i) needFound[L[i]]++;

safeng / reverseKGroup.cc

Created January 18, 2014 03:47

Reverse Nodes in k-Group Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed. For example, …

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

safeng / threeSum.cc

Created January 15, 2014 02:23

3Sum Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4}, …

	class Solution {
	public:
	// based on two sum
	void twoSum(vector<int> & num, vector<vector<int> > & res, int target)
	{
	int n = num.size();
	int i = 0, j = n-1;
	int prei = INT_MAX;// note ensure uniqueness
	int prej = INT_MAX;
	while(i<j)

Shuang Feng safeng