每日5题Day18 - LeetCode 86 - 90

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：86. 分隔链表 - 力扣（LeetCode）

/**
 * 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 partition(ListNode head, int x) {
        ListNode beforehead = new ListNode(-1);
        ListNode afterhead = new ListNode(-1);
        ListNode before = beforehead;
        ListNode after = afterhead;
        ListNode current = head;
        while(current != null){
            if(current.val < x){
                before.next = new ListNode(current.val);
                before = before.next;
            }else{
                after.next = new ListNode(current.val);
                after = after.next;
            }
            current = current.next;
        }
        before.next = afterhead.next;
        after.next = null;
        return beforehead.next;
    }
}

第二题：87. 扰乱字符串 - 力扣（LeetCode）

感觉没读懂，一开始我觉得是下面这个做法

class Solution {
    public boolean isScramble(String s1, String s2) {
        //相当于同频异位的判断
        if(s1.length() != s2.length()){
            return false;
        }
        int[] arr = new int[26];
        for(int i = 0; i < s1.length(); i++){
            arr[s1.charAt(i) - 'a']++;
            arr[s2.charAt(i) - 'a']--;
        }
        for(int i = 0; i < 26; i++){
            if(arr[i] != 0){
                return false;
            }
        }
        return true;
    }
}

第三题：88. 合并两个有序数组 - 力扣（LeetCode）

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int current = m + n - 1;
        int l = m - 1, r = n - 1;
        while(current > -1)
        {
            if(l > -1 && r > -1){
                nums1[current] = nums1[l] >= nums2[r] ? nums1[l--] : nums2[r--];
            }else if(l > -1){
                nums1[current] = nums1[l--];
            }else{
                nums1[current] = nums2[r--];
            }
            current--;
        }
        return;
    }
}

第四题：89. 格雷编码 - 力扣（LeetCode）

class Solution {
    public List<Integer> grayCode(int n) {
        // 创建一个列表来存储格雷编码序列
        List<Integer> res = new ArrayList<Integer>() {{ add(0); }};
        
        // 初始化 head 为 1，用于生成格雷编码序列
        int head = 1;
        
        // 循环遍历每一位的格雷编码
        for (int i = 0; i < n; i++) {
            // 从列表末尾向前遍历
            // 每次，将 head 加上当前值的逆序添加到列表中
            for (int j = res.size() - 1; j >= 0; j--)
                res.add(head + res.get(j));
            
            // 将 head 左移一位
            head <<= 1;
        }
        
        // 返回生成的格雷编码序列
        return res;
    }
}
AA

 第五题：90. 子集 II - 力扣（LeetCode）

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
        traversal(0, res, path, nums);
        return res;
    }

    private static void traversal(int start, List<List<Integer>> res, List<Integer> path, int[] nums){
        res.add(new ArrayList<>(path));
        for(int i = start; i < nums.length; i++){
            //组合，不是排列
            //注意去重
            if(i > start && nums[i] == nums[i - 1]){
                continue;
            }
            path.add(nums[i]);
            traversal(i + 1, res, path, nums);
            path.removeLast();
        }
        return;
    }
}