Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

被这道题坑了超级长的时间。题目很长时间内都没有看明白。我把中间的诸如[2,4]以为是从2到4.我就觉得很奇怪，明明是挑出k个数，为什么挑出这么多数字来。就因为这个卡了好久的时间。
这道题目又是一道深度优先搜索的问题，也就是回溯法的应用。说起来这种题目已经做了好几道了。慢慢的有点儿感觉，但还是需要多练习练习。

Implement int sqrt(int x).

Compute and return the square root of x.

计算x的平方根。题目难度还好，有两个问题。第一个是普通的遍历的话时间是不够用的，二分法来做。

第二是注意题目给的是int型，做的时候要注意溢出的问题。所以用了long型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Solution {
    public int mySqrt(int x) {
        long start=1,end=x;
        while (start+1<end){
            long mid=start+(end-start)/2;
            if(mid*mid<=x){
                start=mid;
            }else {
                end=mid;
            }
        }
        if(end*end<=x){
            return (int)end;
        }
        return (int)start;
    }
}

这么长时间，上传的都是leetcode题目，稍微写点生活上的杂记吧。
其实有一段时间没有更新了，主要是前段时间的考试比较多。另外还有一些lab的东西，似乎总是无法抽出身来去做一些别的事情，令人遗憾。
考试结束了，生活还是规律一点吧。学生时代的最后一个暑假了，加油。

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

这道题目是求在一个矩阵中的最短路径问题。和前面两道题目是非常像的，也是一个动态规划的问题。

这道题目的精髓是抽象出来sum[i][j]=grid[i][j]+min(sum[i-1][j],sum[i][j-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 as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
这道题目和前面的62是同一样的题目，所以就放在一起来写了。题目的意思是要找出机器人在一个m*n的矩阵中到达对角的所有可能。
而63和62所不同的是，题目中设置了障碍，当遇到障碍的时候，这条路就是走不通的情况。
题目的解决方法是用动态规划来解决的。如果能注意到，其中每个点的总路数其实是它的上面那个点的路数与左边路数之和。
问题是好解决的。而在本道题目中，在遇到障碍的时候，将那一个具体格置为0即可。

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”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

这道题和46,47题都很有关系的，但是那两道题目都是一个个的插入进去来做的。这道题目如果先排好序再来做的话，时间复杂度是o(n3)，明显是不可以的。

如果换用别的思路的话，可以发现的是如果给的是n个数，那么会有的是n！个组合。而第一个数是有(n-1)!个可能的。依次往下类推下去，
可以得出这道题的解决办法。另外一点是用arraylist来保存数字，当这些数字被用过以后，就从arraylist中除掉。

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

螺旋矩阵第二道。不过并没有太大的新意。和第一道的思路基本是差不多的。就像剥洋葱，一层层的剥下去就可以了。

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

题目的意思是给出一个字符串，求出这个字符串的最后一个没有空格的完整的字符串。
题目的难度还好，我想到的是从字符串的最后开始出发，先找到end在哪里。
然后再找出start在哪里。最后返回两个的之差就可以了。我在做的时候，遇到的一个坑就是
在判断end的时候，是判断的s.length!=’ ‘，给搞反了。

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 start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

因为这道题目和56题大部分相同，就放在这一块写了。57题相较于56只是多了一个在list中插入Interval的操作。
主要还是用到了merge函数的部分。主要的思路是先通过将list进行一次排序，然后再通过start和end的位置，来进行合并。这道题主要学习了comparator接口的使用。

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 at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

这道题的要求是判断最后在给定的数组中能否走到最后的一个问题，解决思路是每走一步的时候判断是否越过界。
时间复杂度为o(n).

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Solution {
    public boolean canJump(int[] nums) {
        int max=nums[0];
        for(int i=1;i<nums.length;i++){
            if (max==0) return false;
            max--;
            if(nums[i]>max){
                max=nums[i];
            }
        }
        return true;
    }
}