LeetCode
leetcode Word Search
摘要: 给定一个board字符矩阵，可以从任意一个点开始经过上下左右的方式走，每个点只能走一次，如果存在一条路走过的字符等于给定的字符串，那么返回trueGiven a 2D board and a word, find if the word exists in the grid.The word can...阅读全文
leetcode[78] Subsets
摘要: Given a set of distinct integers,S, return all possible subsets.Note:Elements in a subset must be in non-descending order.The solution set must not co...阅读全文
leetcode[77] Combinations
摘要: 给定n和k，从1到n中选k个数，存到结果中。其实就是组合问题。例如Ifn= 3， k = 2, 结果是 {1,2], [1,3], [2,3] };思路：利用回溯法。class Solution {public: void dfs77(vector > &ans, vector subans,...阅读全文
leetcode[76] Minimum Window Substring
摘要: 给定两个串，S和T，在S中找到包含T的最短子串，如果不能包含，返回空字符。Given a string S and a string T, find the minimum window in S which will contain all the characters in T in compl...阅读全文
leetcode[75] sort colors
摘要: 给定一个数组，有0,1,2三个数，把数组排好序。不能直接用sort。策略一：简单的思路，扫描两次，第一次记录0,1,2的个数，第二次重写数组。class Solution {public: void sortColors(int A[], int n) { if(n ans(n...阅读全文
leetcode [64] merge tow sorted lists
摘要: 之前忘记记录这题了，现在补上。合并两个有序的list，要求是：Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes o...阅读全文
leetcode[74] Search a 2D Matri
摘要: 你能用最快的速度找到矩阵中是否有我们想要的值吗。例如：1 2 34 5 67 8 9target = 9，return true，target=10，return false。ps：矩阵升序（左到右，上到下），但不一定是连续数字。解法：两次二分。1. 一次二分找到给定的target可能在第几行2. ...阅读全文
leetcode[73] Set Matrix Zeroes 将矩阵置零
摘要: 给定一个矩阵，把零值所在的行和列都置为零。例如：1 2 31 0 31 1 1操作之后变为1 0 30 0 01 0 1方法1：赋值另存一个m*n的矩阵，在原矩阵为零的值相应置新的矩阵行和列为零。额外空间为O(m*n).方法2：两个数组，bool[m] 和 bool[n] 分别存某行有零，后者某列有...阅读全文
leetcode[72] Edit Distance
摘要: 两个字符串，判断他们之间的编辑距离，可以通过三个操作，删除，添加，替换。每种操作都算距离加一。例如“ab”和“abc”的距离为1.动态规划：用dis[i][j]记录string1的前i个和string2的前j个的距离。那么可以知道：1.如果str1的第i个，也就是str1[i-1]和str2的第j个...阅读全文
leetcode[71] Sqrt(x)
摘要: 题目，就是实现一个开方，返回是整数。int sqrt(int x)用二分法，因为一个数的开方肯定小于 x/2 + 1, 因为小于5的某些数的开方并不一定比x/2小，所以要+1，那么们定义一个left一个right分别为0和x/2 + 1，然后更新左右边界，直至左边界大于右边界，返回右边界就是答案。c...阅读全文
leetcode[70] Simplify Path
摘要: 题目的意思是简化一个unix系统的路径。例如：path="/home/", =>"/home"path="/a/./b/../../c/", =>"/c"我尝试用逐个字符判断的方法，一直提交测试，发现要修改甚多的边界。于是就参考了这位大神思路其实不会那么复杂，C#里面的话直接可以用split就可以分...阅读全文
Text Justification 实现两端对齐功能
摘要: 实现office word中的两端对齐功能。只有个单词时，右边补齐空格。最后一行每个词间一个空格，整下的空格右边补齐。给定字符串，和每行的字符数L。进行两端对齐输出。我的思路是写一个函数，给定相应的参数就返回该行的string。然后在主函数里只要负责给参数就好了。参数包括words字符串数组本身，然...阅读全文
leetcode[68] Climbing Stairs
摘要: n个台阶，每次可以走一步或者两步，总共有多少种走法。第一感觉想到的是递归，n为1的时候1种，2的时候2中。其他时候就是 fun(n) = fun(n-1) + fun(n-2);递归的代码很简单。如下class Solution {public: int climbStairs(int n) ...阅读全文
leetcode[67] Plus One
摘要: 题目：对一个用vector存的数字进行加1,然后返回加1后的值。一次就在oj上通过了。就是进位加上当前位如果大于9，那就当前位等于0；随后进位还为1的话就是在数组前面插入一个1；class Solution {public: vector plusOne(vector &digits) ...阅读全文
valid number 判断字符串是否为有效数字
摘要: RT，面试题，给定一个字符串判断是否为科学计数法的有效数字。此题各种繁琐考虑。今天终于学会了用有限状态机来处理。理解之后简洁易懂。在此分享我的理解推导思路，大有收获啊。网上有解法说先记录每个状态代表的意思，然后根据状态的可能转移写出转移矩阵。但是，你肯定是一头雾水，状态数一多，就混乱不堪，根本很难有...阅读全文
leetcode Add Binary
摘要: 题目：给定两个二进制字符串，返回相加的结果，也是二进制表示。主要就是考查进位如何操作，以及最后如果加完之后进位还是1的话那么不能漏了还要加1.跟之前有做过一题的类似。因为这题easy就是判断，所以直接贴代码了，感觉好长的样子。class Solution {public: string add...阅读全文
leetcode Minimum Path Sum
摘要: 题目：还是类似于之前两题，这里给定的m*n矩阵是每个数字都有值的。求的从头到尾的最小sum是多少。还是用动态规划求。初始化的时候是先计算第一行和第一列。假设给定的数据如下：那么初始化后为：那么再定位要处理的数字到i=1和j=1处，如表中的数字2处。这个时候更新是更加它加上它的左边或者上边的较小的值。...阅读全文
leetcode Unique Paths II
摘要: 题目：和上一题类似，就是这个时候给定了矩阵包含0和1,1代表不能从这里走。我的想法其实很明确，还是用动态规划，只是碰到壁垒的时候要进行考虑。还有初始化很重要。因为1本来是要用来代表在这里出发到终点有一种可能的，所以壁垒的1要用其他代替，我用-1代表是壁垒。如果给定的数组第一个数就是1，那永远都出发不...阅读全文
leetcode[61] Unique Paths
摘要: 题目：给定一个m*n的矩阵，从头开始，只能往右边和下边走，一次走一格，知道走到最后一个（右下角）为止。总共有多少种走法。典型的动态规划吧。其实从头走到尾部，和从尾部开始走到头是一样的次数。我们用一个矩阵记录到第一格子的次数，那么可以看到有如下的表：假设是3*4的矩阵，那么我们要返回的就是10了，每个...阅读全文
leetcode[60] Rotate List
摘要: 题目：给定链表，和一个k，把链表的后k个旋转到前头，例如链表为：1->2->3->4->5->NULLandk=2,return4->5->1->2->3->NULL.一开始我想，跟将后面第k个元素删除一样，可以遍历一次就可以解决问题。但是在测评的时候发现k有大于链表长度的时候，我以为如果大于长度了...阅读全文
leetcode Permutation Sequence
摘要: 题目：给定数字n，然后将1到n的第k个字典序排列找出来，例如3的时候有所有字典序为："123""132""213""231""312""321" 那么第2个就是“132”，返回这个字符串。记得之前有做过输出所有可能的排序，在Permutation中，有兴趣还可以看看。所以很直观的就是复制那题的代码然...阅读全文
leetcode Spiral Matrix II
摘要: 题目：是Spiral Matrix相关的的。这题的意思是给定一个n，那么在n*n的矩阵里按照循环记录将1,2,3，..., n*n。如下如果给定3，那么:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]一开始我想是不是有数学公式直接下标对应的，那直接遍历输出就可以了。...阅读全文
leetcode Length of Last Word
摘要: 题目：给定一个只包含大小写字母和空格的字符串。返回最后一个单词的长度。“abc a” 是1 “abc ”是3两种思路，一个从头往后，一个从后往前。1.从头往后的话，需要记住空格前的一个单词是多长，如果空格到尾了，就输出记录的值，如果空格之后还有单词，就重新计数。用flag记录知否遇到空格。cla...阅读全文
leetcode Insert Interval
摘要: 题目：给定一系列的区间，这些区间是不重合的，而且按每个区间的起始点排好序了。再来一个区间。怎么得到所有合并后的区间。Example 1:Given intervals[1,3],[6,9], insert and merge[2,5]in as[1,5],[6,9].Example 2:Given[...阅读全文
leetcode[55] Merge Intervals
摘要: 题目：给定一连串的区间，要求输出不重叠的区间。Given a collection of intervals, merge all overlapping intervals.For example,Given[1,3],[2,6],[8,10],[15,18],return[1,6],[8,10]...阅读全文
leetcode Jump Game
摘要: 这题和那题类似，这题更简单。我当初就做了这题。当初的代码如下：class Solution {public: bool canJump(int A[], int n) { if (n canReach) return false; ...阅读全文
leetcode Spiral Matrix
摘要: 题目：螺旋输出数组（听师兄说是今年google电话面试题）Given a matrix ofmxnelements (mrows,ncolumns), return all elements of the matrix in spiral order.For example,Given the fo...阅读全文
leetcode Maximum Subarray
摘要: 题目：Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array[−2,1,−3,4,−1,2...阅读全文
leetcode N-QueensII
摘要: 题目和上一题一样，就是要求输出有多少种结果。最直接的就是，只要在上一题的代码return ans.size();就可以了。果然也是AC了。然后我翻看了几种别人写的，暂时还没有找到复杂度可以比上一题降低多少的。可以加一个全局变量。以前都没有想到给solution类加全局变量。满足条件的时候全局变量加一...阅读全文
leetcode[50] N-Queens
摘要: 题目：给定一个n，那么在n*n的棋盘里面放国际象棋的皇后，皇后之间互不在攻击范围。（皇后的攻击范围是她所在位置的哪一行，那一列，和她的正负1的对角线）Then-queens puzzle is the problem of placingnqueens on ann×nchessboard such...阅读全文
leetcod Pow(x, n)
摘要: 题目：就是实现一个指数函数。直接用一个while一直乘以n词肯定是会超时的。自己写了用递归（而且是很挫的递归），测试了无数次，根据每个case去修改代码。终于可以AC了。不忍直视，自己写了好长，如下：class Solution {public: double pow(double x, in...阅读全文
leetcode Anagrams
摘要: 题目：给定一个vector，然后里面有若干个字符串的长度和组成的字母是相同的，找出这些字符串记录并返回。顾名思义，也就是抛弃单一的字符串，单一是指没有和它长度相同并且组成的字母也相同的另一个字符串。原题如下：Given an array of strings, return all groups o...阅读全文
leetcode Rotate Image
摘要: 题目：You are given annxn2D matrix representing an image.Rotate the image by 90 degrees (clockwise).Follow up:Could you do this in-place?在原址上进行将矩阵旋转90度。如...阅读全文
leetcode Jump Game II
摘要: 题目：Given an array of non-negative integers, you are initially positioned at the first index of the array.Each element in the array represents your max...阅读全文
leetcode Permutations II
摘要: 题目：和上一题一样，就是这时候给定的数字可能有重复。做法：只要将num排好序，然后判断如果当前的值等于前一个的话，那么就跳过，就不会有重复的人。果然是AC了。 1 class Solution { 2 public: 3 vector > permuteUnique(vector &num)...阅读全文
leetcode Permutations
摘要: 题目：Given a collection of numbers, return all possible permutations.For example,[1,2,3]have the following permutations:[1,2,3],[1,3,2],[2,1,3],[2,3,1],...阅读全文
leetcode 第43题 Wildcard Matching
摘要: 题目：（这题好难。题目意思类似于第十题，只是这里的*就是可以匹配任意长度串，也就是第十题的‘.*’）'?' Matches any single character.'*' Matches any sequence of characters (including the empty sequenc...阅读全文
leetcode 第42题 Multiply Strings
摘要: 题目：Given two numbers represented as strings, return multiplication of the numbers as a string.Note: The numbers can be arbitrarily large and are non-n...阅读全文
leetcode 第41题 Trapping Rain Water
摘要: 题目：Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining...阅读全文
leetcode第40题--First Missing Positive
摘要: 题目：Given an unsorted integer array, find the first missing positive integer.For example,Given[1,2,0]return3,and[3,4,-1,1]return2.Your algorithm should...阅读全文
leetcode第39题--Combination Sum II
摘要: 题目：Given a collection of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.Each numb...阅读全文
leetcode第38题--Combination Sum
摘要: 题目：Given a set of candidate numbers (C) and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.Thesamerepeated ...阅读全文
leetcode第37题--Count and Say
摘要: 题目：（据说是facebook的面试题哦）The count-and-say sequence is the sequence of integers beginning as follows:1, 11, 21, 1211, 111221, ...1is read off as"one 1"or1...阅读全文
leetcode第36题--Sudoku Solver
摘要: 题目：Write a program to solve a Sudoku puzzle by filling the empty cells.Empty cells are indicated by the character'.'.You may assume that there will be...阅读全文
leetcode第35题--Valid Sudoku
摘要: 题目：Determine if a Sudoku is valid, according to:Sudoku Puzzles - The Rules.The Sudoku board could be partially filled, where empty cells are filled wi...阅读全文
leetcode第34题--Search Insert Position
摘要: Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in or...阅读全文
leetcode第33题--Search for a Range
摘要: Given a sorted array of integers, find the starting and ending position of a given target value.Your algorithm's runtime complexity must be in the ord...阅读全文
leetcode第32题--Search in Rotated Sorted Array
摘要: Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).You are given a target value t...阅读全文
leetcode第31题--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...阅读全文
leetcode第30题--Next Permutation
摘要: problem：Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.If such arrangement is not...阅读全文
leetcode第29题--Substring with Concatenation of All Words
摘要: problem：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 con...阅读全文
leetcode第28题--Divide Two Integers
摘要: Divide two integers without using multiplication, division and mod operator.分析：题目意思很容易理解，就是不用乘除法和模运算求来做除法，很容易想到的一个方法是一直做减法，然后计数，超时。在网上找到一种解法，利用位运算，意思是...阅读全文
leetcode第27题--Implement strStr()
摘要: Implement strStr().Returns a pointer to the first occurrence of needle in haystack, ornullif needle is not part of haystack.就是判断haystack中是否有needle，如果包...阅读全文
leetcode第26题--Remove Duplicates from Sorted Array
摘要: problem： Given a sorted array, remove the duplicates in place such that each element appear onlyonceand return the new length.Do not allocate extra sp...阅读全文
leetcode第25题--Remove Element
摘要: problem：Given an array and a value, remove all instances of that value in place and return the new length.The order of elements can be changed. It doe...阅读全文
leetcode第24题--Reverse Nodes in k-Group
摘要: problem：Given a linked list, reverse the nodes of a linked listkat a time and return its modified list.If the number of nodes is not a multiple ofkthe...阅读全文
leetcode第23题--Swap Nodes in Pairs
摘要: Problem：Given a linked list, swap every two adjacent nodes and return its head.For example,Given1->2->3->4, you should return the list as2->1->4->3.Yo...阅读全文
leetcode第22题--Merge k Sorted Lists
摘要: problem：Mergeksorted linked lists and return it as one sorted list. Analyze and describe its complexity.先合并两个list，再根据归并排序的方法递归合并。假设总共有k个list，每个list的最大...阅读全文
leetcode第21题--Generate Parentheses
摘要: problem：Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, givenn= 3, a solution set is...阅读全文
leetcode第20题--Valid Parentheses
摘要: Problem：Given a string containing just the characters'(',')','{','}','['and']', determine if the input string is valid.The brackets must close in the ...阅读全文
leetcode第19题--Remove Nth Node From End of List
摘要: Problem：Given a linked list, remove thenthnode from the end of list and return its head.For example, Given linked list: 1->2->3->4->5, and n = 2. ...阅读全文
leetcode第18题--Letter Combinations of a Phone Number
摘要: Problem：Given a digit string, return all possible letter combinations that the number could represent.A mapping of digit to letters (just like on the ...阅读全文
leetcode第17题--4Sum
摘要: Problem:Given an arraySofnintegers, are there elementsa,b,c, anddinSsuch thata+b+c+d= target? Find all unique quadruplets in the array which gives the...阅读全文
leetcode第16题--3Sum Closest
摘要: Problem：Given an arraySofnintegers, find three integers inSsuch that the sum is closest to a given number, target. Return the sum of the three integer...阅读全文
leetcode第15题--3Sum
摘要: Problem:Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.Not...阅读全文
leetcode第14题--Longest Common Prefix
摘要: Problems:Write a function to find the longest common prefix string amongst an array of strings.就是返回一个字符串数组的所有的公共前缀。不难。我是已第一个字符串为参考，然后依次遍历其他的字符串，一旦遇到不同...阅读全文
leetcode第13题--Roman to Integer
摘要: Problem：Given a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.遍历一次输入的字符串，如果不满足类似4或者9的就直接加相应的数，否则减去...阅读全文
leetcode第12题--Integer to Roman
摘要: Problem:Given an integer, convert it to a roman numeral.Input is guaranteed to be within the range from 1 to 3999.把阿拉伯数字转换为罗马数字输出。百度一下对应的 I V X L C D ...阅读全文
leetcode第11题--Container With Most Water
摘要: Problem：Givennnon-negative integersa1,a2, ...,an, where each represents a point at coordinate (i,ai).nvertical lines are drawn such that the two endpo...阅读全文
leetcode第十题--Regular Expression Matching
摘要: Problem：Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the precedin...阅读全文
leetcode第九题--Palindrome Number
摘要: Problem:Determine whether an integer is a palindrome. Do this without extra space.click to show spoilers.Some hints:Could negative integers be palindr...阅读全文
leetcode第八题--String to Integer (atoi)
摘要: Problem:Implementatoito convert a string to an integer.Hint:Carefully consider all possible input cases. If you want a challenge, please do not see be...阅读全文
leetcode第七题--Reverse Integer
摘要: Problem：Reverse digits of an integer.Example1:x = 123, return 321Example2:x = -123, return -321终于什么都没参考就一次Accept了。可能是这题比较简单，同时自己也进步了一点点，leetcode就是这样给我...阅读全文
leetcode第六题--ZigZag Conversion
摘要: Problem：The string"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed...阅读全文
leetcode第五题--Longest Palindromic Substring
摘要: Problem：Given a stringS, find the longest palindromic substring inS. You may assume that the maximum length ofSis 1000, and there exists one unique lo...阅读全文
leetcode第四题--Add Two Numbers
摘要: Problem:You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a...阅读全文
leetcode第三题--Longest Substring Without Repeating Characters
摘要: Problem:Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating le...阅读全文
leetcode第二题--Median of Two Sorted Arrays
摘要: Problem:There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity sh...阅读全文
leetcode第一题--two sum
摘要: Problem：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 th...阅读全文