11.8打卡-526互联

1. 插入区间（57）

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
    boolean flag = false;
        List<int[]> res = new ArrayList<>();
        int left = newInterval[0],right = newInterval[1];
        for (int[] interval : intervals) {
            if(interval[0]>right){
                if(!flag){
                    res.add(new int[]{left,right});
                    flag=true;
                }
                res.add(interval);
            }
            else if(interval[1]<left){
                res.add(interval);
            }
            else {
                left = Math.min(left,interval[0]);
                right = Math.max(right,interval[1]);
            }
        }
        if(!flag){
            res.add(new int[]{left,right});
        }
        return  res.toArray(new int[res.size()][2]);
    }
}

2. 最后一个单词的长度（58）

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

class Solution {
    public int lengthOfLastWord(String s) {
     char[] chars = s.toCharArray();
        int i = chars.length - 1;
        while (i>=0&&chars[i] == ' ') {
            i--;
        }
        int count = 0;
        while (i>=0&&chars[i]!=' '){
            count++;
            i--;
        }
        return count;
    }
}

3. 螺旋矩阵II（59）

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

class Solution {
    public int[][] generateMatrix(int n) {
      int[][] res = new int[n][n];
        int left = 0,right = n-1, up=0,down = n-1;
        int k = 1;
        while (true){
            for (int i = left; i <=right; i++) {
                res[up][i]=k++;
            }
            if(++up>down)break;
            for (int i = up; i <=down ; i++) {
                res[i][right]=k++;
            }
            if(--right<left)break;
            for (int i = right; i >=left ; i--) {
                res[down][i]=k++;
            }
            if(--down<up)break;
            for (int i = down; i >=up ; i--) {
                res[i][left]=k++;
            }
              if(++left>right)
                break;
        }
        return res;
    }
}

4. 排列序列（60）

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况

思想：数学归纳+回溯+剪枝

class Solution {
    public String getPermutation(int n, int k) {
  int[] nums = new int[n];//生成nums数组
        for (int i = 0; i < n; i++) nums[i] = i + 1;
        boolean[] used = new boolean[n];//记录当前的索引的数是否被使用过
        return dfs(nums, new ArrayList<String>(), used, 0, n, k);
    }

    private String dfs(int[] nums, List<String> levelList, boolean[] used, int depth, int n, int k) {
        if (depth == n) {//触发出口条件，开始收集结果集
            StringBuilder res = new StringBuilder();
            for (String s : levelList) res.append(s);
            return res.toString();
        }
        int cur = factorial(n - depth - 1);//当前的depth也就是索引，有多少排列数
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;//当前元素被使用过，做剪枝
            if (cur < k) {//当前的排列组合数小于k，说明就算这一层排完了，也到不了第k个，剪枝
                k -= cur;
                continue;
            }
            levelList.add(nums[i] + "");//list收的是string类型
            used[i] = true;//当前元素被使用过标记
            return dfs(nums, levelList, used, depth + 1, n, k);
        }
        return null;
    }


    //返回n的阶乘，如3!=3*2*1=6
    private int factorial(int n) {
        int res = 1;
        while (n > 0) {
            res *= n--;
        }
        return res;
}
}

5. 旋转链表（61）

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
  if(k==0||head==null||head.next==null)
            return head;
        int n =1;
        ListNode iter = head;
        while (iter.next !=null){
            iter=iter.next;
            n++;
        }
        
        int add =n-k%n;
        if(add==n)
            return head;
        iter.next=head;
        while (add-->0){
            iter=iter.next;
        }
        ListNode res = iter.next;
        iter.next=null;
        return res;
    }
}

runtimeexception 11.8 11