jingsuwen1的博客

题目描述在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。给定一个整数n，请返回n位的格雷码，顺序为从0开始。测试样例：1返回：["0","1"题目分析：//方法一：递归//递归的思路就是n位gray码是由n-1位gray码生成，举个例

本题为在两个排序数组中找第K大的数的一个特殊情况——第（A.length+B.length）/2大的数。使用并归的思想逐个比较找出满足要求的数的时间复杂度为O（N）。使用二分法比较A[K/2-1]和B[K/2-1]，并思考这两个元素和第k大元素的关系。1.A[K/2-1] 2.若k/2-1超出了A的长度，则必取B[0]～B[k/2-1]。接下来考虑特殊情

题目：给定一个字符串，将字符串分成多个部分，满足每一部分都是回文串，请输出所有可能的情况。       该问题的难度比较大，很可能第一次遇到没有思路，这很正常。下面我们一点点分析，逐步理清思路。先不考虑所有的情况，针对一个符合条件的划分，每一部分都是一个回文子串，而且各部分的长度不固定。也即每一部分都是原始字符串的一个子串，且满足回文条件。所有的划分都满足上述条件，所以这就启发我们

题目：给定一个字符串str，返回把str全部切成回文子串的最小分割数。举例：str="ABA" ，不需要切割，返回0；str="ACDCDCDAD"，最少需要切两次，比如"A","CDCDC","DAD"，所以返回2.解题思路：动态规划问题。  dp[i] - 表示子串（0，i）的最小回文切割，则最优解在dp[s.length-1]中。（0,i）的子串中

题目：给定一个整形矩阵map,其中的值只有0和1两种，求其中全是1的所有矩阵区域中，最大的矩形的面积。例如：图中是一个４　×　６的矩形，画出红色的是我们要找到的区域，结果返回为 4.      仔细观察发现：因为我们要找的是矩形，所以它一定是以某个行元素开始的，这样的话，其实我们要找到的某个矩形就转换成以某一个行开始的 histogram的最大矩形问题了

转载自：LeetCode Question Difficulty Distribution       1Two Sum25arraysort    setTwo Pointers

题目描述      N个加油站呈环形分布，第i个加油站的油量为gas[i]，你有一辆可以装无限油量的卡车，并且从加油站i到加油站i+1的途中需要消耗掉cost[i]的油量。油箱为空的条件下选择一个加油站起步并能够转一圈重新回到起点。若不存在这样的加油站返回-1，否则返回该加油站的下标。该题求线性的解法方法一：最直观的解法为O(N^2)时间

jump-game题目描述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 maximum jump length a

题目描述Given two integers n and k, return all possible combinations of knumbers out of 1 ... n.For example,If n = 4 and k = 2, a solution is:[ [2,4], [3,4], [2,3], [1,2], [1

题目描述Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).You may assume that the intervals were initially sorted according to their s

题目描述Given a 2D board containing'X'and'O', capture all regions surrounded by'X'.A region is captured by flipping all'O's into'X's in that surrounded region .For example,X X X X

题目描述给定一个矩阵，如果有零元素那么就将零元素所在的行和列都置为零。Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.题目的难点就在于，如果遇到零元素之后马上在矩阵上操作，将所在的行和列都置为零。在接下来的遍历中，如果你再遇到零，你讲不清

题目描述Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.Above is a histogram where wid

题目描述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"()", w

题目描述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

题目描述：给定一个非负整数n，生成n对括号的所有合法排列。Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.For example, given n = 3, a solution set is:"((()))",

题目描述题意：判断一个9*9的矩阵的每一行，每一列，每一个小九宫格是否没有重复的数字，数字范围为“1-9”.A partially filled sudoku which is valid.import java.util.*;public class Solution { public boolean isValidSudoku(char[][] board) {

题一  Combination Sum I，题目大意是这样的：有一个正整数集合C，和一个目标数T（T也为正整数）。现从C中选出一些数，使其累加和恰好等于T（C中的每个数都可以取若干次），求所有不同的取数方案。要求：所得集合元素不能降序排列，结果不能有重复的集合。       例如：C={2,3,6,7}  T=7                  res={  [7],

题目描述The set[1,2,3,…,n]contains a total of n! unique permutations.By listing and labeling all of the permutations in order,We get the following sequence (ie, for n = 3):"123""132"

题目描述：找到排序数组的下一个排序例如：1,2,3→1,3,23,2,1→1,2,31,1,5→1,5,1字典序排列把升序的排列（当然，也可以实现为降序）作为当前排列开始，然后依次计算当前排列的下一个字典序排列。对当前排列从后向前扫描，找到一对为升序的相邻元素，记为i和j（i 到第一个大于i的元素k，交换i和k，然后对从j开始到结束的子序

题目描述：permutationGiven 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],[3,1,2], and[3,2,1].

题目描述Given a digit string, return all possible letter combinations that the number could represent.A mapping of digit to letters (just like on the telephone buttons) is given below.

题目描述请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符

题目描述:subsetsGiven 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 contain duplicate s

题目描述Implementint sqrt(int x).Compute and return the square root ofx.public class Solution { public int sqrt(int x) { if(x <= 0) return 0; int start=1;

题目描述 ：pascals-triangleGiven numRows, generate the firstnumRows of Pascal's triangle.For example, given numRows = 5,Return[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1

2个字符串的最长公共前缀，其长度肯定不会超过最短的字符串的长度，设最短的字符串长度为n，那么只要比较这2个字符串的前n个字符即可。如此得出这2个字符串的最长公共前缀prefix后，再拿prefix作为新的字符串和数组中的下一个字符串比较，方法同上。需要注意的是，如果数组中的某个字符串长度为0，或者求得的当前最长公共前缀的长度为0，就直接返回空字串。public class Solution

题目描述：single-number1一个数组中除了一个数字外，其余数字均出现两次，找出只出现一次的数字。要求线性复杂度方法：两个相同的数字异或得0，一个数字和0异或结果是它本身。public class Solution { public int singleNumber(int[] nums) { int num=0; fo...

验证一个字符串是否是回文字符串。Famous examples include "Amore, Roma", "A man, a plan, a canal: Panama" and "No 'x' in 'Nixon'"。 判读一个字符串是否是回文，一种方法可以将字符串倒置然后和原字符串进行比较。这里采用一种类似字符串翻转的方法，通过从前后两个方向来比较判断是否是回文。本题中的有效字

题目描述Given a string s and a dictionary of wordsdict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.For example, givens ="leetcode",dict =["le

题目描述A message containing letters fromA-Zis being encoded to numbers using the following mapping:'A' -> 1'B' -> 2...'Z' -> 26Given an encoded message containing digits, determine the total nu

题目来源：http://www.cnblogs.com/easonliu/p/3696135.html分析：这个问题是google的面试题。由于一个字符串有很多种二叉表示法，貌似很难判断两个字符串是否可以做这样的变换。对付复杂问题的方法是从简单的特例来思考，从而找出规律。先考察简单情况：字符串长度为1：很明显，两个字符串必须完全相同才可以。字符串长度为2：当s1="ab

题目描述求两个字符串的编辑距离：具体操作方法为：a) Insert a characterb) Delete a characterc) Replace a character比如，对于“abcd”和"abcde"可以认为最少需要通过增加/减少一个'g'得到，则编辑距离为1。思路：若第一个字符是相同的，则考虑两个字符串从第二个

题目描述：Follow up for "Unique Paths":Now consider if some obstacles are added to the grids. How many unique paths would there be?An obstacle and empty space is marked as1and0respectively in

题目描述一个m x n的矩阵，机器人从左上角走到右下角总共有多少种走法。注：每次只能向下或向右走一格。public int uniquePaths(int m, int n) { //状态转移方程为：f(i,i)=f(i,j-1)+f(i-1,j) if(m == 0||n == 0) return 0;

题目描述一个 m x n 的矩阵填充着非负整数，找到从左上角到右下角和最小的路径。注：每一步只能向下一格走或向右一格走。import java.util.*;public class Solution { public int minPathSum(int[][] grid) { if(grid == null) return

题目描述：要求是判断一个字符串能不能由两个字符串按照它们自己的顺序，每次挑取两个串中的一个字符来构造出来。For example,Given:s1 ="aabcc",s2 ="dbbca",When s3 ="aadbbcbcac", return true.When s3 ="aadbbbaccc", return false.递推公式如递归过程，竟然没有超时

题目描述n个小朋友站成一排，根据他们的得分分发糖果，得分高的小朋友要比旁边得分低的小朋友得到的糖果多，每个小朋友至少得到一枚糖果，问最少要准备多少糖果？方法：先从左到右扫描一遍，使得右边比左边得分高的小朋友糖果数比左边多1(尽可能的少)；再从右到左扫描一遍，使得左边比右边得分高的小朋友糖果数比右边多（这里要注意，从右向左比较时，只有当左边小朋友比右边的分高且得到的糖果少于等于右边时

题目描述：给定2个字符串s, t，求t在s中出现的次数。要求可以是不连续的，但是t在s中的顺序必须和t以前的一致。例如：S ="rabbbit", T ="rabbit"Return3.解法：递推公式化为递归的代码为：   其中存在大量的重复计算.public class Solution { public int numDistinct(Strin

仍是数字三角形问题，求从三角形顶端到最底层最小路径和。题目要求空间复杂度O(n),那么就要将二维数组压缩为一维。因DP中历史状态只能通过当前状态影响下一个状态，所以压缩数组是可行的。数字三角形如下：[ [2], [3,4], [6,5,7], [4,1,8,3]]import java.util.*;public class Solut