luoxiaoxun’s gists

luoxiaoxun / LeetCode-Regular Expression Matching

Created July 8, 2013 08:53

Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") ? false isMatch("aa…

	C++:
	class Solution {
	public:
	bool isMatch(const char s, const char p) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(p=='\0') return s=='\0';
	if((p+1)!='')
	return ((s==p)\|\|(s!='\0'&&p=='.'))&&isMatch(s+1,p+1);
	while((s==p)\|\|(s!='\0'&&p=='.')){

luoxiaoxun / LeetCode-Container With Most Water

Created July 8, 2013 08:10

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. Note: You may not slant the container.

	C++:
	class Solution {
	public:
	int maxArea(vector<int> &height) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int low=0;
	int high=height.size()-1;
	int ret=0;
	while(low<high){

luoxiaoxun / LeetCode-Integer to Roman

Created July 8, 2013 07:52

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

	C++:
	class Solution {
	public:
	string intToRoman(int num) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	const static char *Roman="IVXLCDM";
	string ret;
	for(int base=0;num;num /=10,base=base+2){
	int cur=num%10;

luoxiaoxun / LeetCode-Roman to Integer

Created July 8, 2013 07:11

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

	C++:
	class Solution {
	public:
	int romanToInt(string s) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int ret=0;
	for(int i=0;i<s.size();i++){
	if(i<s.size()-1){
	if(getVal(s[i])<getVal(s[i+1])) ret -=getVal(s[i]);

luoxiaoxun / 剑指offer-二维数组中的查找

Created July 7, 2013 14:29

题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。输入：输入可能包含多个测试样例，对于每个测试案例，输入的第一行为两个整数m和n(1<=m,n<=1000)：代表将要输入的矩阵的行数和列数。输入的第二行包括一个整数t(1<=t<=1000000)：代表要查找的数字。接下来的m行，每行有n个数，代表题目所给出的m行n列的矩阵(矩阵如题目描述所示，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。输出：对应每个测试案例，输出”Yes”代表在二维数组中找到了数字t。输出”No”代表在二维数组中没有找到数字t。样例输入：3 3…

	(1)C++:
	#include<cstdio>
	using namespace std;

	bool find(int matrix[1000][1000],int rows,int columns,int number){
	if(matrix!=NULL&&rows>0&&columns>0){
	int rowIndex=0;
	int colIndex=columns-1;
	while(rowIndex<rows&&colIndex>=0){
	if(matrix[rowIndex][colIndex]==number) return true;

luoxiaoxun / LeetCode-4Sum

Created July 7, 2013 08:26

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d) The solution set must not contain duplicate quadruplets. For example, given …

	C++:
	class Solution {
	private:
	vector<vector<int>> ret;
	public:
	vector<vector<int> > fourSum(vector<int> &num, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	ret.clear();
	if(num.size()<4) return ret;

luoxiaoxun / LeetCode-3Sum Closest

Created July 7, 2013 08:09

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

	C++:
	class Solution {
	public:
	int threeSumClosest(vector<int> &num, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int ret;
	int temp=INT_MAX;
	sort(num.begin(),num.end());
	for(int i=0;i<num.size()-2;i++){

luoxiaoxun / LeetCode-3Sum

Created July 7, 2013 07:46

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}, A sol…

	C++:
	class Solution {
	private:
	vector<vector<int>> ret;
	public:
	vector<vector<int> > threeSum(vector<int> &num) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	ret.clear();
	if(num.size()<3) return ret;

luoxiaoxun / LeetCode-Two Sum

Last active March 25, 2020 04:17

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 each input…

	(1)O(n*m)
	C++:
	class Solution {
	public:
	vector<int> twoSum(vector<int> &numbers, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> ret(2);
	for(int i=0;i<numbers.size();i++){
	int temp=target-numbers[i];

luoxiaoxun / LeetCode-Longest Common Prefix

Created July 5, 2013 07:28

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

	C++:
	class Solution {
	public:
	string longestCommonPrefix(vector<string> &strs) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(strs.size()==0) return "";
	if(strs.size()==1) return strs[0];
	string ret="";
	int maxLen=INT_MAX;