luoxiaoxun’s gists

luoxiaoxun / LeetCode-Word Search

Last active December 18, 2015 17:39

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board = [ ["ABCE"], ["SFCS"], ["ADEE"] ] word = "ABCCED", -> ret…

	C++:
	class Solution {
	public:
	bool exist(vector<vector<char>> &board, string word) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(word.length()==0) return false;
	int m=board.size();
	if(m==0) return false;
	int n=board[0].size();

luoxiaoxun / LeetCode-Sort Colors

Created June 20, 2013 03:18

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for this problem. F…

	C++:
	class Solution {
	public:
	void sortColors(int A[], int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int head=0;
	int tail=n-1;
	int cur=0;
	while(cur<=tail){

luoxiaoxun / LeetCode-Minimum Window Substring

Created June 21, 2013 01:24

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC". Note: If there is no such window in S that covers all characters in T, return the emtpy string "". If there are multiple such windows, you are guaranteed…

	C++:
	class Solution {
	public:
	string minWindow(string S, string T) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(T.length()==0\|\|S.length()<T.length()) return "";
	int sLen=S.length();
	int tLen=T.length();
	int ct1[256];

luoxiaoxun / LeetCode-Search a 2D Matrix

Created June 21, 2013 01:50

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: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]

	C++:
	class Solution {
	public:
	bool searchMatrix(vector<vector<int> > &matrix, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(matrix.size()==0) return false;
	int rowLow=0;
	int rowHigh=matrix.size()-1;
	int rowMiddle=0;

luoxiaoxun / LeetCode-Set Matrix Zeroes

Created June 21, 2013 02:53

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?

	C++:
	class Solution {
	public:
	void setZeroes(vector<vector<int> > &matrix) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	bool row=false;
	bool col=false;
	for(int i=0;i<matrix.size();i++)
	if(matrix[i][0]==0){

luoxiaoxun / LeetCode-Edit Distance

Created June 23, 2013 01:51

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character

	C++:
	class Solution {
	public:
	int minDistance(string word1, string word2) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int d[word1.length()+1][word2.length()+1];
	d[0][0]=0;
	for(int i=1;i<=word1.length();i++) d[i][0]=i;
	for(int j=1;j<=word2.length();j++) d[0][j]=j;

luoxiaoxun / LeetCode-Simplify Path

Created June 23, 2013 03:59

Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" Corner Cases: Did you consider the case where path = "/../"? In this case, you should return "/". Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/". In this case,…

	C++:
	class Solution {
	public:
	string simplifyPath(string path) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	stack<string> result;
	string cur;
	for(int i=0;i<path.length();i++){
	if(path[i]=='/'){

luoxiaoxun / LeetCode-Climbing Stairs

Created June 23, 2013 04:21

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

	C++:
	class Solution {
	public:
	int climbStairs(int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(n==0) return 0;
	if(n==1) return 1;
	int one=1;
	int two=0;

luoxiaoxun / LeetCode-Sqrt(x)

Created June 23, 2013 07:40

Implement int sqrt(int x). Compute and return the square root of x.

	(1)二分法
	C++:
	class Solution {
	public:
	int sqrt(int x) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(x<0) return -1;
	long long x1=(long long)x;
	long long left=0;

luoxiaoxun / LeetCode-Plus One

Created June 23, 2013 08:19

Given a number represented as an array of digits, plus one to the number.

	C++:
	class Solution {
	public:
	vector<int> plusOne(vector<int> &digits) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> result;
	stack<int> sum;
	int plusNumber=1;
	for(int i=digits.size()-1;i>=0;i--){