合并区间
题目：给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路：这道题现在有一个不太成熟的想法，就是建一个大数组。当出现这个区间的数则加1，这样哪怕重复区间也不多是往上加而已。最后遍历这个大数组，遇到0则闭合。现在的问题就是给定区间数组会多大。我先去试试
大体思路是对的，但是很多细节不行，一点点调出来的正确答案。说一下遇到的情况：可能会0，0 . 1，1这种区间。所以开区间闭区间在一起，就很难处理。 还有0，0. 1，4这种，如果按照递加则会2，1，1，1，1这样结果也是错的。所以在做的过程中调整了下。开区间和区间中的所有都是1，但是在闭区间时，如果这个闭区间是0(说明不在别的区间之中)则赋值为-1。
然后这个数组可以很明显的看到闭区间的值是哪个（-1的就是闭区间的值）。剩下分两种情况：
- 闭区间本身也是开区间， 例如1，1 . 2，2这种的，所以要判断这个闭区间之前的是不是1.如果不是1则说明该区间本身也是闭区间。
- 正常的区间值， 1，4这种就会是1，1，1，-1。此时要记录这个第一的开区间的值，也就是第一个1.我用first来记录的。
直接贴一下代码:
class Solution {
public int[][] merge(int[][] intervals) {
int[] d = new int[10000];
int max = 0;
for(int [] arr : intervals){
if(max<arr[1]) max = arr[1];
for(int i = arr[0];i<arr[1];i++){
d[i] = 1;
}
if(d[arr[1]]==0) d[arr[1]] = -1;
}
List<List<Integer>> list = new ArrayList<List<Integer>>();
int first = 0;
for(int i = 0;i<=max;i++){
if(i>0 && d[i]==1 && d[i-1]!=1){//区间起始
first = i;
}
if(d[i]==-1){//区间结束
if(i>0 && d[i-1]!=1) {
list.add(Arrays.asList(i,i));
}else{
list.add(Arrays.asList(first,i));
}
}
}
int[][] res = new int[list.size()][];
int idx = 0;
for(List<Integer> l : list){
res[idx] = new int[]{l.get(0),l.get(1)};
idx++;
}
return res;
}
}
螺旋矩阵2
题目：给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
思路:这道题感觉也还好，反正我目前的思路就是一个个往上顺序摆元素，分为上下左右四个方向。就是比螺旋矩阵1还简单，我去简单实现下。
好了，实现了，简单粗暴，性能超过百分百，我直接贴代码了：
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int d = 0; //0是从左到右， 1是从上到下，2是从右到左，3是从下到上
int i = 1;
int left = 0;
int right = n-1;
int up = 0;
int down = n-1;
while(i<=n*n){
if(d==0){
for(int j = left;j<=right;j++){
res[up][j] = i++;
}
d = 1;
up++;
if(up>down) return res;
}
if(d==1){
for(int j = up;j<=down;j++){
res[j][right] = i++;
}
d = 2;
right--;
if(right<left) return res;
}
if(d==2){
for(int j = right;j>=left;j--){
res[down][j] = i++;
}
d = 3;
down--;
if(down<up) return res;
}
if(d==3){
for(int j = down;j>=up;j--){
res[j][left] = i++;
}
d = 0;
left++;
if(left>right) return res;
}
}
return res;
}
}
这个题就这样了，因为比较简单而且逻辑清楚。直接下一题了。
第K个排列
题目：给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
思路：这道题怎么说呢，其实乍一看比较没思路，但是我仔细看了下，是有规律的。比如n是1，则一种可能，n是2则两种可能，第一个数是1，第一个数是2。n是3则6种可能，分别是第一个数+后两个数的两种可能。第二个数+其余两个数的两种可能，第三个数+其实两个数的两种可能。同理n等于4是24种可能，第一个数+后三个数的六种可能，第二个数+其实三个数的六种可能，第三个数+其余三个数的六种可能，第四个数+其余三个数的六种可能。假如是5 应该是5乘24.是6则是6乘5乘24。然后顺序其实也是可以找到规律的。首先看第一个数是哪个，然后顺序往下判断。反正规律我是找到了，接下来去代码实现了。
我先把第一版本的代码贴上来，也是随着做随着该一点点完善的：
class Solution {
public String getPermutation(int n, int k) {
int[] d = new int[]{1,1,2,6,24,120,720,5040,40320,362880};
//这个一开始用数组的，后来发现数组不能删除元素，所以换成list
List<Integer> list = new ArrayList<Integer>();
for(int i = 0;i<=9;i++){
list.add(i);
}
StringBuffer sb = new StringBuffer();
//因为这个算法最后k=0 是可以的，所以k--
k--;
while(n>0){
int val = k/d[n-1];
sb.append(list.get(val+1));
list.remove(val+1);
k = k% d[n-1];
n--;
}
return sb.toString();
}
}
然后因为这个性能2ms，只超过百分之八十多的人，所以我觉得这个题可能是有什么我没发现的窍门，我直接看看排行第一的代码吧。
刚刚看了排行第一的代码，就是细节处理上的区别，剩下主要逻辑大同小异。比如我这里用的list。但是人家用的数组，下标代替值，数组是Boolean值，true代表用过了。我直接贴代码:
class Solution {
public String getPermutation(int n, int k) {
if (n == 1){
return "1";
}
int sum = 0;
StringBuffer res = new StringBuffer();
boolean [] b = new boolean [n + 1];
int i = n;
while (res.length() < n){
int j = 1;
while (b[j]){
j ++;
}
while (i > 1 && k > step(i - 1)){
k -= step(i - 1);
j ++;
while (b[j]){
j ++;
}
}
b[j] = true;
res.append(j);
i --;
}
return res.toString();
}
public int step(int n){
int sum = 1;
for (int i = 1; i <= n; i ++){
sum *= i;
}
return sum;
}
}
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家新年快乐，现在疫情这么严重也希望大家尽量少出门。中国加油！
