safeng’s gists

safeng / lengthOfLongestSubstring.cc

Last active December 28, 2015 09:28

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

	class Solution {
	public:
	int lengthOfLongestSubstring(string s) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	int bitmap[256];
	std::memset(bitmap,0,sizeof(bitmap));
	int maxLen = 0;
	int curLen = 0;
	for(int i = 0; i<(int)s.length();)

safeng / maxArea.cc

Created November 15, 2013 03:46

Container With Most Water Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

	class Solution {
	public:
	int maxArea(vector<int> &height) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	size_t i = 0, j = height.size()-1;
	size_t maxSize = 0;
	while(i<j)
	{
	size_t curSize = 0;

safeng / intToRoman.cc

Last active December 28, 2015 09:29

Given an integer, convert it to a roman numeral.

	class Solution {
	public:
	string intToRoman(int num) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	/*Symbol Value
	I 1
	V 5
	X 10
	L 50

safeng / longestCommonPrefix.cc

Created November 15, 2013 06:15

Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings.

	class Solution {
	public:
	string longestCommonPrefix(vector<string> &strs) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.

	if(strs.size() == 0)
	return string();
	if(strs.size() == 1)
	return strs[0];

safeng / reverseBetween.cc

Created November 15, 2013 07:00

Reverse Linked List II Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

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

safeng / ThreeSum.cc

Last active December 28, 2015 11:49

Two Sum. Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that e…

	class Solution {
	public:

	void twoSum(int first, int last, const vector<int> sVec, int target, vector<vector<int> > & res)
	{
	int prei = INT_MAX;
	int prej = INT_MAX;
	while(first < last)
	{
	int i = sVec[first];

safeng / ValidParen.cc

Created November 16, 2013 07:36

Valid Parentheses Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

	class Solution {
	public:
	bool isValid(string s) {
	// IMPORTANT: Please reset any member data you declared, as
	// the same Solution instance will be reused for each test case.
	static unordered_map<char,char> bMap({ {'(',0}, {')',0}, {'[',1}, {']',1}, {'{',2}, {'}',2} });
	stack<char> ss;
	for(int i = 0; i<s.length(); ++i)
	{
	char c = s[i];

safeng / removeNthFromEnd.cc

Last active December 28, 2015 11:59

Remove Nth Node From End of List. Given a linked list, remove the nth node from the end of list and return its head.

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

safeng / letterCombinations.cc

Created November 17, 2013 18:35

Letter Combinations of a Phone Number Given a digit string, return all possible letter combinations that the number could represent.

	class Solution {
	public:

	void _lComb(int idx, int idxStr, const string & digits, string & str, vector<string> & res)
	{
	static string dMap[10] = {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	if(idx == digits.length())
	{
	res.push_back(str);
	}else

safeng / genParen.cc

Last active December 28, 2015 14:39

Generate Parentheses. Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

	class Solution {
	public:
	void _genParen(int numL, int numR, string & sol, vector<string> & res)
	{
	if(numL == 0 && numR == 0)
	res.push_back(sol);
	else
	{
	// numR should be > numL
	if(numL == numR)

Shuang Feng safeng