public class Solution{
public static void main(String[] args){
System.out.println(numSquares(8));
}
public static int numSquares(int n){
//dp[n]=dp[i + j*j] = min(dp[i]+1,dp[i + j*j]);
int dp[] = new int[n+1];
for (int i = 1; i * i <= n; i++) {
dp[i * i] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; i + j*j <= n; j++){
if(dp[i + j * j] == 0){
dp[i + j * j] = dp[i] + 1;
}
dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
}
}
return dp[n];
}
}
public class Solution {
public void connect(TreeLinkNode root) {
if(null == root) return;
TreeLinkNode cur;
TreeLinkNode pre = root;
while(pre.left != null){
cur = pre;
while(cur != null){
cur.left.next = cur.right;
if(cur.next != null){
cur.right.next = cur.next.left;
}
cur = cur.next;
}
pre=pre.left;
}
}
}
public class Solution {
public int minPathSum(int[][] grid) {
int[][] res = new int[grid.length][grid[0].length];
for(int i = 0; i < grid.length;i++){
for(int j = 0; j < grid[0].length; j++){
if(i == 0 && j == 0){
res[0][0] = grid[0][0];
}else if(i == 0){
res[i][j] = res[i][j-1] + grid[i][j];
}else if(j == 0){
res[i][j] = res[i-1][j]+grid[i][j];
}else{
res[i][j] = grid[i][j] +Math.min(res[i-1][j],res[i][j-1]);
}
}
}
return res[grid.length-1][grid[0].length-1];
}
}
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map; public class Solution{ public static void main(String[] args){
System.out.println(generateParenthesis(3));
} public static List<String> generateParenthesis(int n){
List<String> res = new LinkedList();
Map<StringBuffer,Integer> map = new HashMap();
if(n <= 0) return res;
StringBuffer tmp = new StringBuffer();
tmp.append("(");
int num = 1;
map.put(tmp, 1);
StringBuffer sb = new StringBuffer();
while(num < 2*n ){
Map<StringBuffer,Integer> map2 = new HashMap();
Iterator it = map.entrySet().iterator();
while(it.hasNext()){
int k = 0;
Map.Entry<StringBuffer,Integer> entry =(Map.Entry) it.next();
sb = entry.getKey();
k = entry.getValue();
if(k > 0) {
StringBuffer s1 = new StringBuffer(sb.toString());
s1.append(")");
map2.put(s1, k-1); }
if(k < n && k < 2*n - num){
StringBuffer s2 = new StringBuffer(sb.toString());
s2.append("(");
System.out.println(s2);
map2.put(s2, k+1); } }
num++;
map = map2;
map2 = null; }
Iterator it2 = map.entrySet().iterator();
while(it2.hasNext()){
int k = 0;
Map.Entry<StringBuffer,Integer> entry =(Map.Entry) it2.next();
sb = entry.getKey();
res.add(sb.toString());
} return res;
}
}
public class Solution {
//对于一正方形有四边，所以一次旋转，一个数的改变涉及到了四个数的改变。
//因为是对称的，所以，i只需要到一半就可以。此外因为i到了第二行，第一列对应于第一行已经做了改变，所以，j从i开始。此外j改变到的地方是他替换的地方，即n-1-i
public void rotate(int[][] matrix) {
int n = matrix.length;
int limit = (n-1)/2;
for(int i=0;i<=limit; i++){
for(int j=i;j<n-i-1;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[n-1-j][i];
matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
matrix[j][n-1-i] = temp;
}
}
}
}
import java.util.Arrays;
public class Solution {
//开辟了额外空间
public static void main(String[] args){
int[][] a = {{1,2},{3,4}};
rotate(a);
}
public static void rotate(int[][] matrix) {
int n = matrix.length;
if(n == 1) return;
int[][] res = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
res[j][n - 1 - i] = matrix[i][j];
}
}
for(int i = 0; i < n; i++ ){
for(int j =0 ; j < n;j++){
matrix[i][j] = res[i][j];
}
}
}
}
public class Solution {
public int uniquePaths(int m, int n) {
int[][] res = new int[m][n];
for(int i = 0;i < m; i++){
for(int j = 0; j < n; j++){
if(i == 0 || j == 0) res[i][j] = 1;
else res[i][j] = res[i-1][j] + res[i][j-1];
}
}
return res[m-1][n-1];
}
}
public class Solution {
public int maxSubArray(int[] nums) {
int max = 0;
int Max = 0;
for(int i = 0; i < nums.length; i++){
if(i == 0) {
Max = nums[0];
max = nums[0];
}
else{
if(max > 0) max = max + nums[i];
else{
max = nums[i];
}
}
Max = Math.max(max, Max);
}
return Max;
}
}
import java.util.Arrays;
public class Solution{
public static void main(String[] args){
}
public static int[] productExceptSelf(int[] nums){
int[] res = new int[nums.length];
int[] right = new int[nums.length];
int flag = 1;
for(int i = 0;i < nums.length; i++){
flag *= nums[i];
res[i] = flag;
}
int flag2 = 1;
for(int i = nums.length-1;i >=1; i--){
res[i] = flag2 * res[i-1];
flag2 *= nums[i];
}
res[0] = flag2;
return res;
}
}
之前的left，right如下:
import java.util.Arrays;
public class Solution{
public static void main(String[] args){
}
public static int[] productExceptSelf(int[] nums){
int[] res = new int[nums.length];
int[] left = new int[nums.length];
int[] right = new int[nums.length];
int flag = 1;
for(int i = 0;i < nums.length; i++){
flag *= nums[i];
left[i] = flag;
}
System.out.println(Arrays.toString(left));
int flag2 = 1;
for(int i = nums.length-1;i >=0; i--){
flag2 *= nums[i];
right[i] = flag2;
}
System.out.println(Arrays.toString(right));
for(int i = 1; i < nums.length-1; i++){
res[i] = left[i - 1] * right[i+1];
}
res[0] = right[1];
res[nums.length-1] = left[nums.length -2];
return res;
}
}
/* The isBadVersion API is defined in the parent class VersionControl.
boolean isBadVersion(int version); */ public class Solution extends VersionControl {
public int firstBadVersion(int n) {
int left = 1;
int right = n;
int res = 0;
while(left <= right){
int mid = left + (right-left)/2;
if(isBadVersion(mid)){
res = mid;
right = mid - 1;
}else{
left = mid + 1;
}
}
return res;
}
}
public class Solution {
public int searchInsert(int[] nums, int target) {
int res = 0;
int i=0;
for( ; i < nums.length; i++){
if(target <= nums[i]){
return i;
}
}
res = i;
return res;
}
}
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet; public class Solution{ public static void main(String[] args){ int[] a = {2,1,4};
System.out.println(firstMissingPositive(a));
}
public static int firstMissingPositive(int[] nums){
int res = 0; for(int i = 0; i < nums.length; i++){
int tmp;
while(nums[i] != i + 1 && nums[i] > 0 && nums[i] < nums.length + 1 && nums[i] != nums[nums[i] - 1]){
tmp = nums[i];
nums[i] = nums[tmp - 1];
nums[tmp - 1] = tmp;
}
}
System.out.println(Arrays.toString(nums));
int i = 0;
for(; i < nums.length; i++){
if(nums[i] != i + 1){
return i+ 1;
}
} return i+ 1 ;
}
}
public class Solution{
public static void main(String[] args){
int[] a = {0};
System.out.println(missingNumber(a));
}
public static int missingNumber(int[] nums){
int res = 0;
int max = 0;
int sum = 0;
for(int i = 0; i < nums.length; i++){
max = Math.max(max, nums[i]);
sum += nums[i];
}
if(max<nums.length) max = max + 1;
res = max*(max+1)/2 -sum;
return res;
}
}
74--------------Single Number III（数组里面有两个数字只出现一次）
------------------答案和思路：（位运算，第一次异或得到了两个只出一次的结果，A XOR B。那么结果出现1的位置，这两个值必然有一个为1，一个为0.由此划分为两组数字。在进行一次异或就可得到结果。回归到Single Number II）
import java.util.Arrays;
public class Solution{
public static void main(String[] args){
int[] a= {1,2,3,3};
System.out.println(Arrays.toString(singleNumber(a)));
System.out.println();
}
public static int[] singleNumber(int[] nums){
int[] res = new int[2];
int tmp = 0;
for(int i = 0; i < nums.length; i++){
tmp ^= nums[i];
}
int flag = 0;
int k = -1;
while(flag != 1){
k++;
flag = (tmp >> k) & 1;
}
for(int i = 0; i < nums.length; i++){
if(((nums[i] >> k) & 1) == 1 ){
res[0] ^= nums[i];
}else{
res[1] ^= nums[i];
}
}
return res;
}
}
73--------------Single Number II（数组里面只有一个数字没有出现三次）
-------------------答案和思路：
import java.util.LinkedList;
import java.util.List; public class Solution{ public static void main(String[] args){
int[] a = {1,2,2,2,1,3,1};
System.out.println(singleNumber(a));
} public static int singleNumber(int[] nums){
int res = 0;
int[] bitInt = new int[32]; for(int i = 0; i < 32; i++){
for(int j = 0; j < nums.length; j++){
bitInt[i] += (nums[j] >> i) & 1;
}
res |= (bitInt[i] %3)<<i;
}
return res;
}
}
72--------------Binary Tree Inorder Traversal（二叉树中序遍历）
--------------------答案和思路
import java.util.LinkedList;
import java.util.List; class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
} public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList();
inOrder(root,list);
return list; }
public static void inOrder(TreeNode root,List<Integer> list){
if(root == null) return ; inOrder(root.left,list);
list.add(root.val);
inOrder(root.right,list);
}
}
71-------------Binary Tree Preorder Traversal（二叉树前序遍历）
-----------答案和思路：用list代替print
import java.util.LinkedList;
import java.util.List; class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
} public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList();
preOrder(root,list);
return list; }
public static void preOrder(TreeNode root,List<Integer> list){
if(root == null) return ;
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
}
}
70----------------Compare Version Numbers(比较版本大小)
------------答案和思路：注意split里面.要用\\.
public class Solution {
public static void main(String[] args){
System.out.println(compareVersion("1","1.0.1"));
}
public static int compareVersion(String version1, String version2) {
int res = 0;
String[] str1 = version1.split("\\.");
String[] str2 = version2.split("\\.");
int i = 0;
while(i < str1.length && i < str2.length){
int digit1 = Integer.parseInt(str1[i]);
int digit2 = Integer.parseInt(str2[i]);
if(digit1 > digit2) return 1;
else if(digit1 < digit2) return -1;
i++;
}
int k = i;
while(i < str1.length){
if(Integer.parseInt(str1[i]) > 0)
return 1;
i++;
}
while(k < str2.length){
if(Integer.parseInt(str2[k]) > 0) return -1;
k++;
}
return res;
}
}
69-----------String to Integer (atoi)（字符串装换成整数）
-----------答案和思路：
public class Solution{
public static void main(String[] args){
System.out.println(myAtoi("9223372036854775809"));
}
//照着要求写代码，可以总结如下：
//1. 字串为空或者全是空格，返回0；
//2. 字串的前缀空格需要忽略掉；
//3. 忽略掉前缀空格后，遇到的第一个字符，如果是‘+’或‘－’号，继续往后读；如果是数字，则开始处理数字；如果不是前面的2种，返回0；
//4. 处理数字的过程中，如果之后的字符非数字，就停止转换，返回当前值；
//5. 在上述处理过程中，如果转换出的值超出了int型的范围，就返回int的最大值或最小值。
//清楚了要求，就可以写出AC的代码了。
public static int myAtoi(String str){
int len = str.length();
if(len == 0) return 0;
long res = 0;
int i = 0;
while(str.charAt(i) == ' '){
i++;
}
int flag = 1;
if(i < len && str.charAt(i) == '-'){
flag = -1;
i++;
}else if(i < len && str.charAt(i) == '+'){
i++;
}
//
while(i < len){
if(str.charAt(i)>=48 && str.charAt(i) <= 57){
res = res * 10 + (int)(str.charAt(i) - 48);
if(res > Integer.MAX_VALUE ){
if(flag == -1) return Integer.MIN_VALUE;
else
return Integer.MAX_VALUE;
}
}else
{
if(res > Integer.MAX_VALUE ){
if(flag == -1) return Integer.MIN_VALUE;
else
return Integer.MAX_VALUE;
}
return (int)res * flag;
}
i++;
}
if(res > Integer.MAX_VALUE ){
if(flag == -1) return Integer.MIN_VALUE;
else
return Integer.MAX_VALUE;
}
return (int)res*flag;
}
}
68-------------Summary Ranges(给一个数据，用连续范围来表他
----答案和思路：
import java.util.LinkedList;
import java.util.List; public class Solution{ public static void main(String[] args){ int[] a = {0,1,9};
System.out.println(summaryRanges(a));
} public static List<String> summaryRanges(int[] nums){
StringBuffer sb = new StringBuffer();
List<String> res = new LinkedList();
int start = 0;
int end = 0;
int flag = 0;
for(int i = 0; i < nums.length ; i++){
start = nums[i];
while(i != nums.length - 1 && nums[i] + 1 == nums[i+1]){
end = nums[++i];
flag = 1;
}
if(flag == 1){
sb.append(start);
sb.append("->");
sb.append(end);
}else{
sb.append(start);
}
String tmp = sb.toString();
res.add(tmp);
sb = new StringBuffer();
end = 0;
start = 0;
flag = 0;
} return res;
}
}
67------------ZigZag Conversion(Z字形转变字符串)
----------------答案和思路（注意可以用StringBuffer就不用再用list了。以后的String的list就用StringBuffer）
public class Solution{
public static void main(String[] args){
System.out.println(convert("ABCD",2));
}
public static String convert(String s, int nRows){
StringBuffer res = new StringBuffer();
StringBuffer[] sb = new StringBuffer[nRows];
for(int i = 0; i < nRows; i++){
sb[i] = new StringBuffer();
}
int digit = 0;
for(int i = 0; i < s.length();){
for(int j = 0; j < nRows && i < s.length(); j++){
sb[j].append(s.charAt(i++));
}
for(int k = nRows - 2; k >0 && i <s.length(); k--){
sb[k].append(s.charAt(i++));
}
}
for(int i = 0; i < nRows; i++){
res.append(sb[i]);
}
return res.toString();
}
}
66--------------Single Number（数组里面有一个只出现一次）
------------答案和思路
public class Solution{
public static void main(String[] args){
System.out.println(3^1^2^2^3);
}
public int singleNumber(int[] nums){
int res = 0;
res = nums[0];
for(int i = 1; i < nums.length; i++){
res = res ^ nums[i];
}
return res;
}
}
65--------------Implement strStr()(字符串的包含出现的第一个位置)
-------------------答案和思路：
public class Solution {
public static void main(String[] args){
String a = "a";
String b = "a";
System.out.println(strStr(a,b));
}
public static int strStr(String haystack, String needle) {
int res = -1;
int len1 = haystack.length();
int len2 = needle.length();
if(len2 == 0 || len1 == 0 && len2 == 0) return 0;
for(int i = 0; i <= len1 -len2; i++){
if(haystack.substring(i, i+len2).equals(needle)){
return i;
}
}
return res;
}
}
64--------------Binary Tree Paths(输出二叉树到叶节点的所有路径)
----------------答案和思路：
import java.util.LinkedList;
import java.util.List; class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x;
this.left = null;
this.right = null;
}
} public class Solution { public static void main(String[] args){
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
System.out.println(binaryTreePaths(root));
}
public static List<String> binaryTreePaths(TreeNode root) {
List<String> res = new LinkedList();
List<List<TreeNode>> list = new LinkedList();
if(root == null) return res;
List<TreeNode> tree = new LinkedList();
preOrder(root,res,tree);
return res;
}
public static void preOrder(TreeNode root,List<String> list,List<TreeNode> tree){
if(root == null) return; tree.add(root);
if(root.left == null && root.right == null){
StringBuffer sb = new StringBuffer();
sb.append(tree.get(0).val);
for(int i = 1; i < tree.size(); i++){
sb.append("->");
sb.append(tree.get(i).val);
}
list.add(sb.toString()); }else{
preOrder(root.left,list, tree);
preOrder(root.right, list, tree);
}
tree.remove(tree.size() - 1);
}
}
63-----------Range Sum Query - Immutable（数组的坐标范围内的和）
------------答案和思路：
public class NumArray {
static int[] sum;
public NumArray(int[] nums) {
sum = new int[nums.length];
if(nums.length > 0) sum[0] = nums[0];
for(int i = 1; i < nums.length; i++){
sum[i] = sum[i-1] + nums[i];
}
}
public static int sumRange(int i, int j) {
if(i == 0 ) return sum[j];
return sum[j] - sum[i - 1];
}
}
62--------------Bulls and Cows（公牛和母牛。猜数字游戏）
-----------------答案和思路：
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List; public class Solution{ public static void main(String[] args){ System.out.println(getHint("1807","7810"));
}
public static String getHint(String secret, String guess){
StringBuffer res = new StringBuffer();
int bull = 0;
int cow = 0;
List<Character> list1 = new LinkedList();
List<Character> list2 = new LinkedList();
HashSet hash1 = new HashSet();
HashSet hash2 = new HashSet();
for(int i = 0; i < secret.length(); i++){
list1.add(secret.charAt(i));
list2.add(guess.charAt(i));
}
for(int i = 0; i < guess.length(); i++){
if(secret.charAt(i) == guess.charAt(i)){
bull++;
list1.remove(list1.indexOf(guess.charAt(i)));
list2.remove(list2.indexOf(guess.charAt(i)));
}
}
System.out.println(list1);
System.out.println(list2);
while(!list2.isEmpty()){
System.out.println("list2 = " + list2.get(0));
if(list1.contains(list2.get(0))){
cow++;
list1.remove(list1.indexOf(list2.get(0))); }
list2.remove(list2.indexOf(list2.get(0)));
}
res.append(bull).append("A").append(cow).append("B"); return res.toString();
} }
61--------------Count Primes（数素数）
-------------答案和思路，注意这里是小于n
public class Solution {
public int countPrimes(int n) {
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (notPrime[i] == false) {
count++;
for (int j = 2; i*j < n; j++) {
notPrime[i*j] = true;
}
}
}
return count;
}
}
60-----------------Add Binary（字符串按二进制相加）
import java.util.ArrayList;
import java.util.List; public class Solution{ public static void main(String[] args){ System.out.println(addBinary("1","111")); }
public static String addBinary(String a, String b){
StringBuffer res = new StringBuffer();
int n1 = a.length() - 1;
int n2 = b.length() - 1; int flag = 0;
while(n1 != -1 || n2 != -1){
int tmp1 = 0;
int tmp2 = 0;
int ans = 0;
if(n1 != -1){
tmp1 = a.charAt(n1--) - 48; }
if(n2 != -1){
tmp2 = b.charAt(n2--) - 48; }
int tmp3 = tmp1 + tmp2 + flag;
if(tmp3 >= 2){
flag = 1;
ans = tmp3 % 2;
}else{
flag = 0;
ans = tmp3;
} res.append(ans);
}
if(flag == 1) res.append("1");
return res.reverse().toString();
}
}
59------------Count and Say（数数字。）
---------------答案和思路：
public class Solution{
public static void main(String[] args){
System.out.println(countAndSay(5));
}
public static String countAndSay(int n){
StringBuffer res = new StringBuffer("1");
if(n == 1) return res.toString();
for(int i = 2; i <= n; i++){
StringBuffer res2 = new StringBuffer();
char c = res.charAt(0);
int tmp = 0;
for(int j = 0; j < res.length(); j++){
if(res.charAt(j) == c){
tmp++;
}else
{
res2.append(tmp);
res2.append(c);
tmp = 1;
c = res.charAt(j);
}
}
res2.append(tmp);
res2.append(c);
res = res2;
System.out.println("res = " + res);
}
return res.toString();
}
}
58----------Reverse Integer（把整数翻转）
-----------答案和思路：
public class Solution {
public static void main(String[] args){
System.out.println(reverse(1534236469));
System.out.println(Integer.MAX_VALUE);
}
public static int reverse(int x) {
int res = 0;
while(x != 0){
int digit = x % 10;
if(res > Integer.MAX_VALUE/10 || res < Integer.MIN_VALUE/10) return 0;
res = res * 10 + digit;
x = x / 10;
}
return res;
}
}
57-------------------------Longest Common Prefix（最长的公共前缀）
--------------------答案和思路：
import java.util.ArrayList;
import java.util.List; public class Solution { public static void main(String[] args){
String[] strs = {""};
System.out.println(longestCommonPrefix(strs));
} public static String longestCommonPrefix(String[] strs) {
if(strs.length == 0) return ""; List<Character> list = new ArrayList();
int i = 0;
String res = "";
String str1 = strs[0];
if(str1.length() == 0) return "";
char c = str1.charAt(0);
while(true){
for(String tmp : strs){
if(i == tmp.length() || tmp.charAt(i) != c){
return res;
}
}
res = res + String.valueOf(c);
++i;
if(i == str1.length()) return res;
c = str1.charAt(i); }
}
}
56--------------------------Word Pattern（单词匹配模式）
--------------------------答案和思路：ERROR：记住，双映射
public class Solution {
public static boolean wordPattern(String pattern, String str){
boolean res = true;
String[] tmp = str.split(" ");
if(tmp.length != pattern.length()) return false;
Map<Character, String> hash = new HashMap();
Map<String,Character> hash2 = new HashMap();
for(int i = 0; i < pattern.length(); ++i){
if(hash.containsKey(pattern.charAt(i))){
if(!hash.get(pattern.charAt(i)).equals(tmp[i])) return false;
}else{
hash.put(pattern.charAt(i), tmp[i]);
}
if(hash2.containsKey(tmp[i])){
if(!hash2.get(tmp[i]).equals(pattern.charAt(i))) return false;
}else{
hash2.put(tmp[i],pattern.charAt(i));
}
}
return res;
}
}
55-------------------Isomorphic Strings（同构的字符串）
-------------------答案和思路：注意映射是相互的。
public class Solution {
public static boolean isIsomorphic(String s, String t) {
Map<Character, Character> map = new HashMap();
Map<Character, Character> map1 = new HashMap();
boolean res = true;
if(s.length() == 0 && t.length() == 0 )return true;
if(s.length() != t.length()) return false;
for(int i = 0; i < s.length(); i++){
if(!map.containsKey(s.charAt(i))){
map.put(s.charAt(i), t.charAt(i));
}else{
if(map.get(s.charAt(i)) != t.charAt(i)){
return false;
}
}
if(!map1.containsKey(t.charAt(i))){
map1.put(t.charAt(i), s.charAt(i));
}else{
if(map1.get(t.charAt(i)) != s.charAt(i)){
return false;
}
}
}
return res;
}
}
54---------------------Rectangle Area（总的矩阵面积）
---------------答案和思路：注意可能会没有交集的情况。
public class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int area1 = (C - A ) * (D - B);
int area2 = (G - E) * (H - F);
if(C <= E || G<=A ||D <= F || H <= B){
return area1 + area2;
}
int len = 0;
int wide = 0;
len = Math.abs(Math.max(A, E) - Math.min(C, G));
wide = Math.abs(Math.max(B, F) - Math.min(D, H));
int common =(int)len * wide;
System.out.println(common);
System.out.println(area2);
return (area1 + area2 - common);
}
}
53---------------------Minimum Depth of Binary Tree（找树的根结点到叶子节点的最短的路径）
--------------答案思路：利用层次遍历
public class Solution {
public static int minDepth(TreeNode root){
Queue<TreeNode> a = new LinkedList<TreeNode>();
int res = 0;
if(root == null) return res;
a.add(root);
while(!a.isEmpty()){
int levelNum = a.size();
res++;
for(int i = 0; i < levelNum; i++){
TreeNode top = a.poll();
if(top.left == null && top.right == null){
//leaf
return res;
}
if(top.left != null) a.add(top.left);
if(top.right != null) a.add(top.right);
}
}
return res;
}
}
52---------------------Path Sum(树的路径，到叶子节点的和是否等于给出的值)
-------------------答案和思路：每一个结点加上他父亲结点
public class Solution{
public static boolean hasPathSum(TreeNode root, int sum){
if(root == null) return false;
if(root.left == null && root.right == null){
System.out.println("sum = " + sum +", val = " + root.val);
if(root.val == sum) return true;
}else{
System.out.println("here");
if(root.left != null) root.left.val += root.val;
if(root.right != null) root.right.val += root.val;
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
return false;
}
}
51---------------------Valid Sudoku（数独，只需要判断填入数字是否已经违反了不能重复的原则）
----------答案和思路：
import java.util.ArrayList;
import java.util.List;
public class Solution{
public static void main(String[] args){
}
public static boolean isValidSudoku(char[][] board){
boolean res = true;
for(int i = 0 ; i < 9; i ++){
List<Character> listRow = new ArrayList();
List<Character> listColumn = new ArrayList();
for(int j = 0 ; j < 9; j++){
if(board[i][j] != '.' && listRow.contains(board[i][j])){
System.out.println(i+"here1"+j);
return false;
}
else{
listRow.add(board[i][j]);
}
if(board[j][i] != '.' &&listColumn.contains(board[j][i])){
System.out.println(i+"here2"+j + "," + board[j][i]);
return false;
}
else{
listColumn.add(board[j][i]);
}
}
}
for(int h = 0; h < 9;){
for(int k = 0; k < 9; ){
List<Character> list = new ArrayList();
for(int i = 0 + h; i < 3 + h; i ++){
for(int j = 0 + k; j < 3+ k; j++){
if(board[i][j] != '.' &&list.contains(board[i][j])){
System.out.println(i+"here3"+j);
return false;
}
else{
list.add(board[i][j]);
}
}
}
k = k + 3;
}
h = h+3;
}
return res;
}
}
50---------------------Pascal's Triangle II（帕斯卡三角，杨辉三角。返回第k行。注意0行开始）
---------------答案和思路：
import java.util.ArrayList;
import java.util.List;
public class Solution{
public static void main(String[] args){
getRow(3);
}
public static List<Integer> getRow(int rowIndex){
List<Integer> res = new ArrayList();
int tmp = 1;
for(int i = 0; i <= rowIndex; ++i ){
List<Integer> list = new ArrayList();
if(tmp == 1) list.add(1);
else if (tmp == 2){
list.add(0, 1);
list.add(1, 1);
}else{
list.add(0, 1);
for(int k = 0; k < res.size() - 1;k++){
int sum = res.get(k) + res.get(k+1);
list.add(sum);
}
list.add(tmp-1,1);
}
tmp++;
res = list;
}
System.out.println(res);
return res;
}
}
49--------------------Pascal's Triangle（帕斯卡三角，杨辉三角）
-----------答案和思路：
public class Solution{
public static void main(String[] args){
generate(5);
}
public static List<List<Integer>> generate(int numRows){
List<List<Integer>> res = new ArrayList();
List<Integer> level = new ArrayList();
int tmp = 1;
for(int i = 0; i < numRows; ++i ){
List<Integer> list = new ArrayList();
if(tmp == 1) list.add(1);
else if (tmp == 2){
list.add(0, 1);
list.add(1, 1);
}else{
list.add(0, 1);
for(int k = 0; k < level.size() - 1;k++){
int sum = level.get(k) + level.get(k+1);
list.add(sum);
}
list.add(tmp-1,1);
}
res.add(list);
tmp++;
level = list;
System.out.println(list);
}
return res;
}
}
48--------------------Plus One（数字变成数组，然后+1）
------------答案与思路：
import java.util.Arrays;
public class Solution{
public static void main(String[] args){
int[] a = {};
System.out.println(Arrays.toString(plusOne(a)));
}
public static int[] plusOne(int[] digits){
int len = digits.length;
if(len == 0) return digits;
int i;
for( i = len - 1; i >= 0; i--){
if(digits[i] != 9){
digits[i] += 1;
break;
}
else{
digits[i] = 0;
}
}
if(i == -1){
int[] res = new int[len + 1];
res[0] = 1;
return res;
}
return digits;
}
}
47--------------------House Robber(入室抢劫，不能抢相邻的两个。给一个数组，不能相邻的相加。求max)
---------------思路和答案：
public class Solution {
public static int rob(int[] nums){
//dp[i] = nums[i] + max(dp[i-2],dp[i-3])
int res = 0;
int len = nums.length;
int[] max = new int[len];
for(int i = 0; i < len; i++ ){
if(i == 0) max[0] = nums[0];
else if(i == 1) max[1] = nums[1];
else if(i == 2) max[2] = nums[0] + nums[2];
else{
max[i] = nums[i] + Math.max(max[i - 2],max[i-3]);
}
res = Math.max(res, max[i]);
}
return res;
}
}
46-------------------Length of Last Word（字符串的最后一个单词的长度）
--------------------答案和思路：
public class Solution {
public static int lengthOfLastWord(String s){
int res = 0;
for( int i = s.length() - 1; i >= 0; i--)
{
if(s.charAt(i) == ' ' && res != 0){
break;
}
if(s.charAt(i) == ' '){
res = 0;
}
else{
res++;
}
}
return res;
}
}
45------------Symmetric Tree（判断一棵树是否对称）
----------答案和思路：
public class Solution {
public static boolean isSymmetric(TreeNode root){
boolean res = true;
if(root == null) return true;
return isSymmetric(root.left, root.right);
}
public static boolean isSymmetric(TreeNode A, TreeNode B){
if(A == null && B == null) return true;
if(null == A && B != null || A != null && B == null) return false;
if(A.val != B.val) return false;
return isSymmetric(A.left,B.right) && isSymmetric(A.right,B.left);
}
}
44----------------Reverse Bits(反转二进制移位)
---------------------答案思路：
public class Solution {
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result += n & 1;
n >>>= 1; // CATCH: must do unsigned shift
if (i < 31) // CATCH: for last digit, don't shift!
result <<= 1;
}
return result;
}
}
43------------------Valid Palindrome（给一个字符串，看是否是回文。只考虑字母和数字）
---------------答案和思路：
public class Solution {
public static boolean isPalindrome(String s){
boolean res = true;
int head = 0;
int tail = s.length() - 1;
while( head < tail){
while(!Character.isLetterOrDigit(s.charAt(head)) && head < tail){
head++;
}
while(!Character.isLetterOrDigit(s.charAt(tail))&& head < tail){
tail--;
}
if(Character.toLowerCase(s.charAt(head)) != Character.toLowerCase(s.charAt(tail))){
return false;
}
head++;
tail--;
}
return res;
}
}
42--------------Binary Tree Level Order Traversal II（二叉树从低到上层次遍历）
--------------答案思路：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> a = new LinkedList<TreeNode>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
a.add(root);
while(!a.isEmpty()){
int levelNum = a.size();
List<Integer> level = new ArrayList();
for(int i = 0; i < levelNum; i++){
TreeNode top = a.poll();
if(top.left != null) a.add(top.left);
if(top.right != null) a.add(top.right);
level.add(top.val);
}
res.add(level);
}
List<List<Integer>> tmp = new ArrayList<List<Integer>>();
for(int i = res.size() - 1; i >= 0; i--){
tmp.add(res.get(i));
}
res =tmp;
return res;
}
}
41---------Binary Tree Level Order Traversal(二叉树的层次遍历)
---------------答案思路：
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> a = new LinkedList<TreeNode>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
a.add(root);
while(!a.isEmpty()){
int levelNum = a.size();
List<Integer> level = new ArrayList();
for(int i = 0; i < levelNum; i++){
TreeNode top = a.poll();
if(top.left != null) a.add(top.left);
if(top.right != null) a.add(top.right);
level.add(top.val);
}
res.add(level);
}
return res;
}
}
40-------Merge Sorted Array
------------答案思路：
public class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int left1 = 0;
int left2 = 0;
int[] num = new int[m + n];
for( int i = 0; i < m + n; i++){
if(left2 >= n || left1 < m && nums1[left1] < nums2[left2]){
num[i] = nums1[left1++];
}else {
num[i] = nums2[left2++];
}
}
for(int i = 0; i < m + n; i++){
nums1[i] = num[i];
}
}
}
39--------Palindrome Number(判断数字是否是回文)
-------------思路答案，负数不是
public class Solution {
public static boolean isPalindrome(int x){
if(x < 0 ) return false;
boolean res = true;
int n = 0;
int tmp = x;
while(tmp != 0){
n++;
tmp = tmp/10;
}
for(int i = 1; i < n; i++){
int a1 = (int) ((x / Math.pow(10, i - 1)) % 10);
int a2 = (int) (x / Math.pow(10, n - i)) % 10;
System.out.println(a1+ "," +a2);
if(a1 != a2){
return false;
}
}
return res;
}
}
38(2)--------------Remove Duplicates from Sorted Array II
---------------答案和思路：
import java.util.Arrays;
public class Solution{
public static void main(String[] args){
int[] a = {1,1,1};
System.out.println(removeDuplicates(a));
System.out.println(Arrays.toString(a));
}
public static int removeDuplicates(int[] nums){
int res = nums.length;
int flag = 0;
if(nums.length <= 1) return nums.length;
int tmp = nums[0];
flag = 1;
int pre = 1 ;
for(int i = 1; i < nums.length; i++){
if(nums[i] == tmp){
flag++;
if(flag > 2){
while(i < nums.length && nums[i] == tmp ){
i++;
res--;
}
if(i == nums.length) return res;
nums[pre] = nums[i];
tmp = nums[i];
flag = 1;
}
else{
nums[pre] = nums[i];
}
}else{
tmp = nums[i];
nums[pre] = nums[i];
flag = 1;
}
pre++;
}
return res;
}
}
38--------------Remove Duplicates from Sorted Array
-------------答案思路：用一个k标记每一个位置该写什么值。num[k] 当然=num[0].从1开始，在遍历的过程中，不=num[k]的就赋值到他的后面。
public class Solution {
public static int removeDuplicates(int[] nums){
int len = nums.length;
if(len <= 1) return len;
int k = 0;
for( int i = 1; i < len; ++i){
if(nums[k] != nums[i]){
nums[++k] = nums[i];
}
}
return k+1;
}
}
37-------------Remove Element
------------答案思路：把后面不==val的替换前面的。如果替换值也==，就再提换，用while来看是否需要一直替换
public class Solution {
public static void main(String[] args){
int[] a = {2,3,3};
removeElement(a,3);
System.out.println(Arrays.toString(a));
}
public static int removeElement(int[] nums, int val) {
int len = nums.length;
for( int i = 0; i < len; ++i){
while(nums[i] == val && i < len){
nums[i] = nums[--len];
}
}
return len;
}
}
36---------------Power of Two（2的幂）
-------------------思路答案（）利用移位
public class Solution {
public boolean isPowerOfTwo(int n) {
if(n <= 0 ) return false;//ERROR: if(n == 0 ) return false;注意负数，0
//都不是
int count = 0;
while(n != 0)
{
if((n & 1) != 0) count++;//&操作比=等级低，要加括号
if(count > 1) return false;
n = n >>>1;
}
return true;
}
}
35----------------Balanced Binary Tree(平衡二叉树)
---------------------答案思路：
public class Solution {
public boolean isBalanced(TreeNode root) {
int[] dep = new int[1];
return checkBalance(root, dep);
}
public static boolean checkBalance(TreeNode root, int[] dep){//java 里没有传地址
if(null == root){
dep[0] = 0;
return true;
}
int[] leftDep = new int[1];
int[] rightDep = new int[1];
boolean leftBalance = checkBalance(root.left, leftDep);
boolean rightBalance = checkBalance(root.right, rightDep);
dep[0] = Math.max(leftDep[0], rightDep[0]) + 1;
return leftBalance && rightBalance && (Math.abs(rightDep[0] - leftDep[0]) <=1);
}
}
34----------------------Happy Number(快乐数字。把数字位的平方加起来，知道结果为1)、
-----------------答案思路：
public class Solution {
public static boolean isHappy(int n){
boolean res = false;
List<Integer> l = new ArrayList();
int tmp = 0;
while(!l.contains(tmp)){
l.add(tmp);
tmp = 0;
while(n != 0){
int digit = n % 10;
tmp += digit * digit;
n = n / 10;
}
if(tmp == 1) return true;
n = tmp;
}
return false;
}
}
34-------------------Integer to Roman(整数变成罗马数字)
--------------------答案和思路：
public class Solution{
public String intToRoman(int num){
StringBuffer res = new StringBuffer();
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
int i = 0;
while(num > 0){
while(num >= values[i]){
num = num - values[i];
res.append(numerals[i]);
}
i++;
}
return res.toString();
}
}
33--------------------Roman to Integer(把罗马数字转换成整数)
----------------答案思路：注意，要减去的那些数字
public class Solution {
public static int romanToInt(String s){
//I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)
int res = 0;
Map<Character,Integer> m = new HashMap();
m.put('I', 1);
m.put('V', 5);
m.put('X', 10);
m.put('L', 50);
m.put('C', 100);
m.put('D', 500);
m.put('M', 1000);
for( int i = 0; i < s.length(); i++){
res = res + m.get(s.charAt(i));
}
if(s.indexOf("IV") != -1) res -= 2;
if(s.indexOf("IX") != -1) res -= 2;
if(s.indexOf("XL") != -1) res -= 20;
if(s.indexOf("XC") != -1) res -= 20;
if(s.indexOf("CD") != -1) res -= 200;
if(s.indexOf("CM") != -1) res -= 200;
return res;
}
}
32----------------Number of 1 Bits
-------------------答案思路： 给一个数，看他变成二进制，包含了几个1.用移位预算。切记<<<，<<。前者是高位补0；
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int res = 0;
while(n != 0){
if((n & 1) == 1) res++;
n = n >>> 1;
}
return res;
}
}
31---------Lowest Common Ancestor of a Binary Search Tree（二叉排序树，二叉查找树的最近公共祖先）
--------------答案：
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
else if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
else return root;
}
}
30---------Valid Anagram(有效的回文构词法。判断两个字符串的字母是否相同，只是顺序不一样)
---------------答案：（记得先判断长度）
public class Solution {
public static boolean isAnagram(String s, String t){
boolean res = true;
if(s.length() != t.length()) return false;
int[] a1 = new int[26];
int[] a2 = new int[26];
for(int i = 0; i < s.length(); i++){
int n1 = s.charAt(i) - 'a';
int n2 = t.charAt(i) - 'a';
a1[n1]++;
a2[n2]++;
}
for(int i = 0; i < 26; i++){
if(a1[i] != a2[i])
return false;
}
return res;
}
}
29---------Excel Sheet Column Title（给一个数字，转换成对应的字母）
---------答案：
public class Solution {
public static String convertToTitle(int n){
//错误在于，与10进制不同的是，他不是从0开始，而是从1开始，所以要进行减1操作。
String res = "";
//base = 26
while(n != 0){
int digit = (n-1) % 26;
char tmp = (char) ('A' + digit);
res = String.valueOf(tmp) + res;
n = (n-1) / 26;
}
return res;
}
}
28-----Excel Sheet Column Number(字母转成数字)
-------------答案：
public class Solution {
public static int titleToNumber(String s){
int res = 0;
char[] tmp = s.toCharArray();
for(int i = 0; i < tmp.length; i++){
int n = tmp[i] - 'A' + 1;
res = res*26 + n;
}
return res;
}
}
27-----------Maximum Depth of Binary Tree(求二叉树高度，找二叉树最大深度)
---------答案：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return 1 + Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
26---------------Invert Binary Tree（翻转二叉树）
-----------------答案：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if(null == root) return root;
TreeNode tmp = new TreeNode(0);
tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
25---------------Same Tree(相同的树)
---------------答案：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if((p == null && q != null) || (p != null && null == q) ||p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
24--------Nim Game 移除石头的游戏
------------答案思路：通过手写来找出规律
public class Solution {
public boolean canWinNim(int n) {
return (n % 4 == 0 ) ? false : true;
}
}
22--------------------Add Digits(位数相加)
--------------答案2：
public class Solution {
public int addDigits(int num) {
return num == 0 ? 0 : (num - 1) % 9 + 1;
}
}
-----------答案1：
public class Solution {
public static void main(String[] args){
int a = 10;
System.out.println(addDigits(a));
System.out.println("end");
}
public static int addDigits(int num){
int res =num;
while(res >= 10){
int res1 = 0;
while(num != 0){
int tmp = num % 10;
res1 += tmp;
num = num/10;
}
res = res1;
num = res;
}
return res;
}
}
21----------------Median of Two Sorted Arrays(找到两个有序数组的中位数)
------------思路，如果一共奇数个，返回中间那个，偶数个，中间两个的平均值，利用递归的思想。
------------答案：
import java.util.Arrays;
public class Solution {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
double res = 0;
int n1 = nums1.length, n2 = nums2.length;
if(n1 + n2 <= 0) return res;
int count = 0;
if((n1 + n2 ) % 2 == 1){
count = (n1 + n2 ) / 2 + 1;
if(n1 <= 0) return nums2[count - 1];
if(n2 <= 0) return nums1[count - 1];
int left1 = 0, left2 = 0;
while(left1 < n1 || left2 < n2){
if(left1 < n1 &&( left2 >= n2 || nums1[left1] < nums2[left2] )){
count--;
if(count == 0){
res = nums1[left1];
break;
}
left1++;
}
else{
count--;
if(count == 0){
res = nums2[left2];
break;
}
left2++;
}
}
}
else{
count = (n1 + n2 ) / 2 + 1;
if(n1 <= 0) return (nums2[count-2] + nums2[count - 1]) / 2.0;
if(n2 <= 0) return (nums1[count-2] + nums1[count - 1]) / 2.0;
int left1 = 0, left2 = 0;
int res1 = 0, res2 = 0;
while(left1 < n1 || left2 < n2){
if(left1 < n1 && ( left2 >= n2 || nums1[left1] < nums2[left2] )){
count--;
if(count == 0){
res2 = nums1[left1];
break;
}else{
res1 = nums1[left1];
}
left1++;
}
else{
count--;
if(count == 0){
res2 = nums2[left2];
break;
}else{
res1 = nums2[left2];
}
left2++;
}
}
res = (res1 + res2) / 2.0;
}
return res;
}
}
20----------------Find Minimum in Rotated Sorted Array(循环数组里面找最小的元素，包含重复元素）
--------------思路：与上一题是一样的。区别就是多了重复元素，那么只有第一个大于第二个的时候第二个才是min。所以，答案是一样的。
public class Solution {
public static int findMin(int[] nums){
if(nums.length <= 1) return nums[0];
int min = nums[0];
if(nums[0] <= nums[1]){
for(int i = 1; i < nums.length; ++i){
if(nums[i] < nums[i - 1]){
min = nums[i ];
break;
}
}
}
else{
min = nums[1];
}
return min;
}
}
19----------------Find Minimum in Rotated Sorted Array(循环数组里面找最小的元素）
-------------思路：一种情况，第一个值大于第二个值，那么第一个是最大，第二个是最小，直接返回。第二种情况，第一个值小于第二个值，这又有两种情况，第一个是min，还有就是到了后面某一处突然变小，那么这个小的就是min
------------------答案：
public class Solution {
public static int findMin(int[] nums){
if(nums.length <= 1) return nums[0];
int min = nums[0];
if(nums[0] < nums[1]){
for(int i = 1; i < nums.length; ++i){
if(nums[i] < nums[i - 1]){
min = nums[i ];
break;
}
}
}
else{
min = nums[1];
}
return min;
}
}
18-----------Majority Element II(找出现次数超过三分之一 n/3的数字)
-------------思路：先统计出出现最多次数的，再看看是否超过了n/3。
--------------答案：
public class Solution {
public List<Integer> majorityElement(int[] nums) {
int max1 = 0,max2 = 0;
int count1=0, count2=0;
for(int i = 0; i < nums.length; ++i){
if(nums[i] == max1){
count1++;
}else if (count1 == 0){
max1 = nums[i];
count1++;
}else if(nums[i] == max2){
count2++;
}else if(count2 == 0){
max2 = nums[i];
count2++;
}
else{
count1--;
count2--;
}
}
//calculate length of two max
count1=0;
count2=0;
for(int i = 0; i < nums.length; i++){
if(nums[i] == max1) count1++;
if(nums[i] == max2) count2++;
}
List<Integer> res = new ArrayList();
if(count1 > nums.length / 3) res.add(max1);
if((count2 > nums.length / 3 )&& max2 != max1) res.add(max2);
return res;
}
}
17-----------Majority Element(找出现次数超过一半n/2的数字)
--------思路，利用一个count一直做统计。只要不同的就相互抵消。他超过一半，一定能干掉所有人的。
-------答案：
public class Solution {
public int majorityElement(int[] nums) {
int res = 0;
int count = 0;
for(int i = 0; i < nums.length; i++){
if(count == 0){
res = nums[i];
count = 1; //error:count ==1;
}else if(res == nums[i]){
count++;
}else{
count--;
}
}
return res;
}
}
16------------Permutations II（数字排列组合，要求unique。要求要不同，独一无二）
------思路，利用hash。把得到的结果丢入hash，那么就会排除掉相同的。再从hash拿出来就正确了。
-----------答案：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
//思路：不断往里放东西。第一个list，只有list（0），然后放1的时候，可以放（1,0），（0,1），然后放2的时候可以在（1，0）里放2处
public static List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList();
List<Integer> tmp = new ArrayList();
if(nums.length <= 0) return res;
tmp.add(nums[0]);
res.add(tmp);
for(int i = 1; i < nums.length; i++){
List<List<Integer>> newRes = new ArrayList<List<Integer>>();
for(int j = 0; j <= i; j++){
for(List<Integer> tmpList : res){
List<Integer> newList = new ArrayList(tmpList);
newList.add(j, nums[i]);
newRes.add(newList);
}
}
res = newRes;
}
Set<List<Integer>> hash = new HashSet();
for(List<Integer> tmpList:res){
hash.add(tmpList);
}
List<List<Integer>> res2 = new ArrayList();
for(List<Integer> tmpList:hash){
res2.add(tmpList);
}
return res2;
}
}
15------------Permutations（数字排列组合）
---思路：首先，例如三个数，1,2,3.先把1放入一个List。再把这个List放入一个list。然后开始放2，把里面的list拿出来，插入2，得到两个list。放入新的结果里，然
后再拿出来，然后放3.
------------答案：
import java.util.ArrayList;
import java.util.List;
public class Solution {
//思路：不断往里放东西。第一个list，只有list（0），然后放1的时候，可以放（1,0），（0,1），然后放2的时候可以在（1，0）里放2处
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList();
List<Integer> tmp = new ArrayList();
if(nums.length <= 0) return res;
tmp.add(nums[0]);
res.add(tmp);
for(int i = 1; i < nums.length; i++){
List<List<Integer>> newRes = new ArrayList<List<Integer>>();
for(int j = 0; j <= i; j++){
for(List<Integer> tmpList : res){
List<Integer> newList = new ArrayList(tmpList);
newList.add(j, nums[i]);
newRes.add(newList);
}
}
res = newRes;
}
return res;
}
}
14------------Jump Game II（是否能跳到最后位置）
public class Solution{
public static void main(String[] args){
int[] a = { 2,3,0,1,4};
System.out.println(jump(a));
}
public static int jump(int[] nums){
//思路，就是在走的过程中，记录如果再跳一次，最远能够跳到那里，那么当当前走到的位置已经超过了商议跳所能够达到的位置时候开始跳
//所以，用maxReach记录当前这一跳能够跳到哪里。如果>=last index，就break。并且如果不能够跳到最后，那么需要下一跳，所以下一跳要找跳到最远的位置，
//所以要一直记录nextReach的max。
if(nums.length <= 1) return 0;
int res = 1;
int maxReach = nums[0];
int nextReach = nums[0];
for(int i = 0; i < nums.length ; i++){
if(i > maxReach) {
res++;
maxReach = nextReach;
}
if(maxReach >= nums.length - 1) break;
nextReach = Math.max(nextReach, nums[i] + i);
}
return res;
}
}
13------------Jump Game（是否能跳到最后位置）
------------思路与答案：
public class Solution{
public boolean canJump(int[] nums){
//思路：因为考虑的是是否能够跳过去，所以，这里，我们就需要看，在这个点的时候，最多能够往后多少步
int maxStep = -1;
if(nums.length <= 1) return true;
for(int i = 0; i < nums.length - 1 ; ++i){
maxStep = Math.max(maxStep, nums[i]);
if(maxStep == 0) return false;
maxStep--;
}
return true;
}
//error:input [0] excepted true.并且，题目要求是跳到last index，所以，最后一个值无论是是什么都没关系。
}
12-2------------Best Time to Buy and Sell Stock with Cooldown(买卖股票。含有cooldown，冷冻期)
--------答案和思路：根据这一天是buy还是sell还是rest来写递推式，然后再简化。http://www.cnblogs.com/grandyang/p/4997417.html
public class Solution{
public int maxProfit(int[] prices){
int buy = Integer.MIN_VALUE;
int pre_buy = 0;
int sell =0;
int pre_sell = 0;
for(int price : prices){
pre_buy = buy;
buy = Math.max(pre_sell - price, pre_buy);
pre_sell = sell;
sell = Math.max(pre_buy + price, pre_sell);
}
return sell;
}
}
12------------Best Time to Buy and Sell Stock IV(买股票，可以买k次)
-----------思路与答案一起给出：
public class Solution{
//思路：
//localProfit[i][j]：到了第i天，并且第i天进行了第j次交易的maxProfit
//globalProfit[i][j]:到了第i天，进行了j次交易的maxProfit
//note：为什么要分两个？答：首先一定要有的是globalProfit[i][j]。因为这个就是要求的答案
//但是这个答案分为两种方案：1，是i天不做交易，那么他就==global[i-1][j];
//一种是，i天做交易。那么就要用一个i天做交易得到的maxProfit。
//然后最后max两种情况。
//【错误】注意，n天最多交易n/2次，当k很大，大于n/2要单独判断（相当于第一题，随便几次都可以），并且不要忘记那时候就要return
public int maxProfit(int k, int[] prices){
int n = prices.length;
if(k <= 0 || n == 0) return 0;
if(k >= n / 2){
int max = 0;
for(int i = 1; i < n; i++){
max += Math.max(0, prices[i] - prices[i - 1]);
}
return max;
}
int[][] localProfit = new int[n][k+1];
int[][] globalProfit = new int[n][k + 1];
//最重要的部分，从这里开始：
for(int j = 1; j <= k; ++j){
for(int i = 1; i < n; ++i){//天数是从0开始的。localProfit[0][0] = 0;
localProfit[i][j] = Math.max(localProfit[i - 1][j] + prices[i] - prices[i - 1],globalProfit[i - 1][j - 1] +Math.max(0, prices[i] - prices[i - 1]));
globalProfit[i][j] = Math.max(localProfit[i][j], globalProfit[i - 1][j]);
}
}
return globalProfit[n - 1][k];
}
}
11------------Best Time to Buy and Sell Stock III（买股票，只可以进行两次）
-----------------------思路，就是卖出那一刻，前面是第一题模式，往后走又是第一题模式，错误在于，一定要保证在O（N ），所以先存下来到某一个点前的利益，以及到某一个点往后的利益。
-------------答案：
public class Solution {
public static int maxProfit(int[] prices) {
//思路：其实进行了两次，到了第一次卖出那里是第一次，之后的又会进行第二次，这样
//就变成了题目I进行两遍动态变化的题。
//但是错在了LTE。因为一开始开了外层for来看到那一个点。这个时候利用cache原理，先把到某一个点maxprofit存下来。空间换时间。
int maxProfit = 0;
int length = prices.length;
int min = Integer.MAX_VALUE;
int res= 0;
int[] maxBefore = new int[length];
int[] maxAfter = new int[length];
for(int i = 0; i < prices.length; i++){
if(prices[i] - min > res){
res = prices[i] - min;
}
if(prices[i] < min){
min = prices[i];
}
maxBefore[i] = res;
}
int max = 0;
res = 0;
for(int i = length - 1; i >= 0; i--){
if(max - prices[i] > res){
res = max - prices[i];
}
if(prices[i] > max){
max = prices[i];
}
maxAfter[i] = res;
}
for(int i = 0 ; i < length; i++){
maxProfit = Math.max(maxProfit, maxBefore[i] + maxAfter[i]);
}
return maxProfit;
}
}
10------------Best Time to Buy and Sell Stock II（股票最大利益。可以买卖多次。同一天可以买卖）
---------------思路，不要想太复杂了，只要出现今天买进明天能赚钱的现象就进行买卖。
----答案：
public int maxProfit(int[] prices) {
//思路：只要是能够卖了赚钱的都买进买出。
int maxProfit = 0;
for(int i = 1; i < prices.length; i++)
{
if(prices[i - 1] < prices[i])
{
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
9------------Best Time to Buy and Sell Stock(最好的时间去买彩票，买彩票。股票最大利益)
---------------思路：因为只买一次卖一次。那么就是找最大差值就可以了。但是因为小的一定在大的前面。而且最大差值卖出去的那个一定是减去了他前面的所有值中最小的。所以，先把买入值设为第一个，那么到了第二个就出现了一个差值，那么走到第三个的时候，要减去的应该是1,2位置中较小的那一个，所以，需要min来记录谁小，而且一只计算差值并且更新最大的差值。
----------------错误：一定要判断输入的是空数组的情况。今后每次都要先判定。
---------------答案：
public class Solution {
public static int maxProfit(int[] prices){
int res = 0;
if(prices.length == 0 ) return 0;
int min = prices[0];
for(int i = 1; i < prices.length; ++i){
if(prices[i] - min > res){
res = prices[i] - min;
}
if(prices[i] < min){
min = prices[i];
}
}
return res;
}
}
（找峰值元素）
开始：
8------------Sqrt(x)（求平方根）
----------思路，注意是否越界，这里mid = left + （right - left） / 2；
-----------答案：
public static int mySqrt(int x){
int res = 0;
if(x <= 1) return x;
int left = 1;
int right = x;
while(left <= right){
int mid = left + (right -left ) / 2;
if(x / mid == mid) return mid;
else if (x / mid > mid) left = mid + 1;
else right = mid - 1;
}
return left - 1 ;
}
7----------Contains Duplicate III（看数组是否有重复元素，值差距t，下标差距k）
-----思路，也是和之前的一样，另外开一个存储来辅助。因为右值范围，所以n划分为小于他的部分，大于他的部分，那么只需要找距离他最近的两个值。所以，有排序，用treeset。
其中：set.floor(n):<=n,里面的max。
set.ceiling(n) >=n 里面的min
------------答案：
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t){
TreeSet<Integer> set = new TreeSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(set.floor(nums[i]) != null && set.floor(nums[i]) + t >=nums[i] || set.ceiling(nums[i]) != null && set.ceiling(nums[i]) - t <= nums[i]){
return true;
}
set.add(nums[i]);
if(i >= k){
set.remove(nums[i - k]);
}
}
return false;
}
}
5------------Contains Duplicat（判断数组是否有重复元素）
------------思路，利用hash是否能add来判断，这样就不用扫描两遍。
--------------答案：
public class Solution {
public static boolean containsDuplicate(int[] nums) {
Set hash = new HashSet();
for(int n : nums){
if(!hash.add(n)) return true;
}
return false;
}
}
5-----------Contains Duplicate II（给一个数组，给一个k，小于k的距离内有两个值相等）
--------------思路：注意，如果用for，for，会LTE。那么善于利用HashSet。根据是否能add知道是否有重复，但是因为要控制距离，所以，到了i这里，i-k-1的值要从hash里面移除；
--------------答案：
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set hash = new HashSet();
for(int i = 0; i < nums.length; i++){
if(i > k) hash.remove(nums[i - k - 1]);
if(!hash.add(nums[i])){
return true;
}
}
return false;
}
}
格式：1---------------英文名称（中文名称）题号
1------Reverse Words in a String（字符串中翻转单词） 151
---答案：（注意，前后有空格要去掉。而且要注意最后出的结果是只有一个空格）
public class Solution {
public String reverseWords(String s) {
String[] str = s.trim().split("\\s+");
s="";
for(int i = str.length - 1; i > 0; --i){
s += str[i] + " ";
}
s += str[0];
return s;
}
}
2-----------------rotate array（循环移动数组，右移数组）189
---答案：
public class Solution {
public void rotate(int[] nums, int k) {
if(nums.length <= 1){
return;
}
//step each time to move
int step = k % nums.length;
reverse(nums,0,nums.length - 1);//这句话放到最后就是左移
reverse(nums,0,step - 1);
reverse(nums,step,nums.length - 1);
}
//reverse int array from n to m
public void reverse(int[] nums, int n, int m){
while(n < m){
nums[n] ^= nums[m];
nums[m] ^= nums[n];
nums[n] ^= nums[m];
n++;
m--;
}
}
}
3------------Move Zeroes(前置0，后置0）283
答案----------思路：后置。循环的时候，如果a[i] ！= 0 ，continue。直到找到第一个0
，，然后往后找到第一个1。然后交换。重复。（重点：if(flag == length) break;）
public class Solution {
public void moveZeroes(int[] nums) {
int flag = 0;
int length = nums.length;
for(int i = 0; i < length; i++){
if(nums[i] != 0){
continue;
}
if(flag <= i ) flag = i + 1;
while(flag < length && nums[flag] == 0)
{
flag++;
}
if(flag == length) break;
//swap
int tmp = nums[i];
nums[i] = nums[flag];
nums[flag] = tmp;
}
}
}
4------------Climbing Stairs(爬楼，台阶问题)
答案---------------思路：这个台阶来源于前一个，和前两个。所以把他们加起来。
代码：
public class Solution {
public static int climbStairs(int n){
int res = 0;
int[] f = new int[n + 1];
f[0] = 1;
f[1] = 1;
for(int i = 2; i < n + 1; i++){
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
}
5------------Find Peak Element（找峰值元素）
答案------------思路：用二分。注意判断mid！=right。
public class Solution {
public static int findPeakElement(int[] nums) {
int res = 0;
if(nums.length == 1 ) return 0;
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (right + left) / 2 ;
if(mid != right && nums[mid] < nums[mid + 1]) left = mid + 1;
else if(mid != left && nums[mid] < nums[mid -1]) right = mid - 1;
else {
res = mid;
break;
}
}
return res;
}
}
6------------sort colors(只有0,1,2元素，进行排序)
答案--------------------------------思路：是0的时候一次对2,1，往后移，覆盖是的赋值
public class Solution {
public void sortColors(int[] nums) {
int n0 = 0, n1 = 0, n2 = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] == 0){
nums[n2++] = 2;
nums[n1++] = 1;
nums[n0++] = 0;
}else if (nums[i] == 1){
nums[n2++] = 2;
nums[n1++] = 1;
}else{
nums[n2++] = 2;
}
}
}
}
7-----------Repeated DNA Sequences（求字符串子串长度出现不止一次的子串）
-------思路：切记，不要重复重复的算一段子串的hash。子串数量就是从第一个开始，数10个，然后第二开始数。总的有length - 9 个子串。
-------答案：
public class Solution {
public static List<String> findRepeatedDnaSequences(String s){
List<String> res = new ArrayList<String>();
int index1 = 0;
int index2 = 0;
String s1 = new String();
String s2 = new String();
long hash1,hash2;
Set hashset = new HashSet();
for(index1 = 0; index1 < s.length() - 9; index1++){
s1 = s.substring(index1,index1 + 10);
hash1 = getHash(s1);
if(!hashset.add(hash1)){
if(!res.contains(s1)){
res.add(s1);
}
}
}
for(String t : res){
System.out.println(t);
}
return res;
}
public static long getHash(String s){
char[] c = s.toCharArray();
long res = 0;
int key;
int base = 5;
for(int i = 0; i < c.length; i++){
if(c[i] == 'A') key = 1;
else if(c[i] == 'C') key = 2;
else if(c[i] == 'G') key = 3;
else key =4;
res = res * base + key;
}
return res;
}
}
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）
5------------Find Peak Element（找峰值元素）