刷题日记 - 1

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0; // nums1 的索引
        int j = 0; // nums2 的索引
        int[] copy = new int[m]; // 创建一个数组来存储 nums1 的前 m 个元素的副本
        System.arraycopy(nums1, 0, copy, 0, m); // 复制 nums1 的前 m 个元素到 copy 中

        int num1; // 存储 copy[i] 的值
        int num2; // 存储 nums2[j] 的值
        int idx = 0; // 合并后的数组索引
        
        // 合并两个数组
        while (i < m && j < n) {
            num1 = copy[i];
            num2 = nums2[j];
            if (num1 <= num2) {
                nums1[idx] = num1; // 如果 num1 小于等于 num2，将 num1 放入 nums1
                i++;
            } else {
                nums1[idx] = num2; // 否则，将 num2 放入 nums1
                j++;
            }
            idx++;
        }
        
        // 如果 copy 还有剩余的元素，添加到 nums1 中
        while (i < m) {
            nums1[idx++] = copy[i++];
        }
        
        // 如果 nums2 还有剩余的元素，添加到 nums1 中
        while (j < n) {
            nums1[idx++] = nums2[j++];
        }
    }
}

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建一个虚拟头节点 dummy，用于简化边界条件的处理
        ListNode dummy = new ListNode(-1);
        // 指针 p 和 q 分别指向 list1 和 list2 的头节点
        ListNode p = list1;
        ListNode q = list2;
        // 指针 t 指向当前合并后的链表的尾部
        ListNode t = dummy;

        // 遍历 list1 和 list2，直到其中一个链表为空
        while (p != null && q != null) {
            // 比较当前节点的值，将较小的节点连接到合并后的链表
            if (p.val <= q.val) {
                t.next = p; // 将 p 连接到 t 的后面
                t = t.next; // t 前移到下一个位置
                p = p.next; // p 前移到下一个位置
            } else {
                t.next = q; // 将 q 连接到 t 的后面
                t = t.next; // t 前移到下一个位置
                q = q.next; // q 前移到下一个位置
            }
        }

        // 如果 list1 或 list2 还有剩余节点，将剩余部分连接到合并后的链表
        t.next = (p == null) ? q : p;

        // 返回合并后的链表头节点（跳过虚拟头节点 dummy）
        return dummy.next;
    }
}

/**
 * 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 mergeKLists(ListNode[] lists) {
        // 如果链表数组为空，直接返回 null
        if (lists.length == 0) return null;
        // 遍历链表数组，将前两个链表合并，然后将结果存储在第二个位置
        for (int i = 0; i < lists.length - 1; i++) {
            // 将第 i 个链表和第 i+1 个链表合并
            ListNode tmp = mergeList(lists[i], lists[i + 1]);
            // 将合并后的链表存储在第 i+1 个位置
            lists[i + 1] = tmp;
        }
        // 返回最终合并后的链表（存储在数组的最后一个位置）
        return lists[lists.length - 1];
    }

    // 辅助函数
    private ListNode mergeList(ListNode node1,ListNode node2){
        ListNode dummy = new ListNode(-1);
        ListNode p = node1,q = node2,t = dummy;
        while(p!=null&&q!=null){
            if(p.val<q.val){
                t.next = p;
                t = t.next;
                p = p.next;
            }else {
                t.next = q;
                t = t.next;
                q = q.next;
            }
        }
        t.next = (q==null) ? p : q;
        return dummy.next;
    }
}

/**
 * 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 mergeKLists(ListNode[] lists) {
        // 使用优先队列（最小堆）来存储节点，以便始终可以快速获取最小节点
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        // 将所有链表的头节点加入优先队列
        for (ListNode p : lists) {
            if (p != null)
                pq.offer(p);
        }

        // 创建一个虚拟头节点，用于简化链表操作
        ListNode dummy = new ListNode(-1);
        ListNode t = dummy;

        // 当优先队列不为空时，重复以下操作
        while (!pq.isEmpty()) {
            // 取出队列中最小的节点
            ListNode p = pq.poll();
            // 将该节点添加到结果链表中
            t.next = p;
            t = t.next;
            // 如果该节点有下一个节点，则将下一个节点加入优先队列
            if (p.next != null)
                pq.offer(p.next);
        }

        // 返回合并后的链表
        return dummy.next;
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int head = 0;
        int tail = n - 1;    
        
        while (head <= tail) {
            if (nums[head] == val) {
                // 找到从后向前第一个不等于 val 的元素
                while (head < tail && nums[tail] == val) {
                    tail--;
                }
                // 将其与当前 head 位置的元素交换
                nums[head] = nums[tail];
                tail--;
            }
            if (nums[head] != val) {  
                head++;
            }
        }
        // 返回新数组的长度
        return head;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;  // 获取数组长度
        int idx = 0;  // idx 指针用于记录数组中非重复元素的最后一个位置
        int p = 0;  // p 指针用于遍历数组
        
        // 遍历数组
        while(p < len) {
            // 如果当前元素和 idx 位置的元素不同
            if(nums[p] != nums[idx]) {
                nums[++idx] = nums[p];  // 将当前元素放到 idx 的下一个位置
            }
            p++;  // 移动 p 指针
        }
        
        // 返回数组中非重复元素的个数
        return idx + 1;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;  // 获取数组长度
        int idx = 0;  // idx 指针用于记录数组中元素的位置
        int p = 1;  // p 指针用于遍历数组，初始值为1，因为第一个元素总是保留的
        int count = 1;  // 计数器，用于记录当前数字出现的次数
        
        // 遍历数组
        while(p < len) {
            if(nums[p] == nums[idx]) {  // 如果当前元素与 nums[idx] 相同
                count++;  // 计数器增加
                if(count <= 2) {  // 只允许最多两个相同的元素
                    nums[++idx] = nums[p];  // 将当前元素放到 idx 的下一个位置
                }
            } else {  // 如果当前元素与 nums[idx] 不同
                nums[++idx] = nums[p];  // 将当前元素放到 idx 的下一个位置
                count = 1;  // 重置计数器
            }
            p++;  // 移动 p 指针
        }
        
        // 返回数组中保留的元素个数
        return idx + 1;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        int idx = 0;
        for(int i=0;i<len;i++){
            if(idx<2||nums[idx-2]!=nums[i]){
                nums[idx++] = nums[i];
            }
        }
        return idx;
    }
}