每日刷题记录 (二十八)

转x33g5p2x  于2022-07-20 转载在 其他  
字(5.5k)|赞(0)|评价(0)|浏览(197)

第一题: 117. 填充每个节点的下一个右侧节点指针 II

LeetCode: 117. 填充每个节点的下一个右侧节点指针 II

描述:
给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

解题思路:

  1. 使用层序遍历的方法.
  2. 将每层的节点进行链接.
  3. 这里注意为空的情况. 如果没有下一节点就不继续链接了

代码实现:

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size != 0) {
                Node top = queue.poll();
                if(size != 1) {
                    top.next = queue.peek();
                }
                if(top.left != null) queue.offer(top.left);
                if(top.right != null) queue.offer(top.right);
                size--;
            } 
        }
        return root;
    }
}

第二题: 147. 对链表进行插入排序

LeetCode: 147. 对链表进行插入排序

描述:
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

  1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
  2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
  3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

解题思路:

  1. 使用插入排序的思路.
  2. 首先如果下一个节点的值, 大于此节点值, 就让 head = head.next
  3. 来一个前驱节点, 指向头节点.
  4. 如果前驱节点的下一个节点的值, 小于 head的下一个节点的值, 那么就移动这个前驱节点,
  5. 直到找到 大于head下一节点值的节点.
  6. 然后此时进行交换.

代码实现:

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode pre = new ListNode(-1);
        pre.next = head;
        while(head != null && head.next != null) {
            if(head.val <= head.next.val) {
                head = head.next;
                continue;
            }
            ListNode tmp = pre;
            while(tmp.next.val < head.next.val) 
                tmp = tmp.next;
            ListNode cur = head.next;
            head.next = cur.next;
            cur.next = tmp.next;
            tmp.next = cur; 
        }
        return pre.next;
    }
}

第三题: 641. 设计循环双端队列

LeetCode: 641. 设计循环双端队列

描述:
设计实现双端队列。

实现 MyCircularDeque 类:

  • MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
  • boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
  • boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
  • boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
  • boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
  • int getFront() ：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
  • int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
  • boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
  • boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

解题思路:

  1. 这里使用一个数组实现.
  2. 这里 有 head 指向头. tail 指向尾. size 表示有效元素, 初始化数组大小为 k
  3. isEmpty()方法, 判断当前 size == 0
  4. isFull() 方法, 判断当前 size == arr.length
  5. insetFront(), 头插, 首先进行判断, 是否满了, 满了就不能插入了.没满, 首先进行判断, 如果 head==0, 让head=arr.length-1处, 如果head!=0, 直接插入head=head-1处 , 有效元素 size++
  6. insertLast(), 尾插, 直接对tail位置进行插入, 然后对tail++, 注意tail为arr.length的情况, 要让tail = 0. 有效元素size++
  7. deleteFront(), 头删, 直接移动head, 让head++, 注意head为arr.length的情况, 让head=0, 有效元素size–
  8. deleteLast(), 尾删, 直接移动tail, 让tail–, 注意tail为0的情况, 要让tail =arr.length. 有效元素size–
  9. getFront(), 直接返回 head下标处的元素
  10. getRear(), 返回 tail-1 处的元素, 注意tail为0的情况,.

代码实现:

class MyCircularDeque {

    private int[] arr;
    private int head;
    private int tail;
    private int size;
    public MyCircularDeque(int k) {
        arr = new int[k];
        size = 0;
        head = 0;
        tail = 0;
    }

    public boolean insertFront(int value) {
        if(isFull()){
            return false;
        }
        if(head == 0) {
            head = arr.length - 1;
        }else{
            head = head - 1;
        }
        arr[head] = value;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if(isFull()){
            return false;
        }
        arr[tail] = value;
        if(tail == arr.length-1){
            tail = 0;
        }else{
            tail++; 
        }
        size++;
        return true;
    }

    public boolean deleteFront() {
        if(isEmpty()){
            return false;
        }
        if(head == arr.length - 1) {
            head = 0;
        }else {
            head = head + 1;
        }
        size--;
        return true;
    }

    public boolean deleteLast() {
        if(isEmpty()) return false;
        if(tail == 0) {
            tail = arr.length - 1;
        }else{
            tail--;
        }
        size--;
        return true;
    }

    public int getFront() {
        if(isEmpty()) return -1;
        return arr[head];
    }

    public int getRear() {
        if(isEmpty()) return -1;
        if(tail == 0) return arr[arr.length - 1];
        return arr[tail-1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return  size == arr.length;
    }
}

第四题: 705. 设计哈希集合

LeetCode: 705. 设计哈希集合

描述:
不使用任何内建的哈希表库设计一个哈希集（HashSet）。

实现 MyHashSet 类：

  • void add(key) 向哈希集合中插入值 key 。
  • bool contains(key) 返回哈希集合中是否存在这个值 key 。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

解题思路:

  1. 直接定义一个长度为 10^6 + 1 的数组.
  2. add操作的时候, 让 key 下标的元素为 true
  3. contains 操作的时候, 判断 key 下标的元素是否为 true
  4. remove 操作的时候, 让 key 下标的元素为 false;

代码实现:

class MyHashSet {
    boolean[] map;
    public MyHashSet() {
        map = new boolean[1000001];
    }
    
    public void add(int key) {
        map[key] = true;
    }
    
    public void remove(int key) {
        map[key] = false;
    }
    
    public boolean contains(int key) {
        return map[key] == true;
    }
}

第五题: 706. 设计哈希映射

LeetCode: 706. 设计哈希映射

描述:
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

  • MyHashMap() 用空映射初始化对象
  • void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
  • int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
  • void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

解题思路:

  1. 定义一个长度为 10^6+1 的数组, 默认值为-1
  2. put操作的时候, 直接将key下标的元素替换成value
  3. get 操作的时候, 直接返回key下标的元素
  4. remove 操作的时候, 让key 下标的元素等于 -1

代码实现:

class MyHashMap {
    private int[] map;
    public MyHashMap() {
        map = new int[1000001];
        Arrays.fill(map,-1);
    }
    
    public void put(int key, int value) {
        map[key] = value;
    }
    
    public int get(int key) {
        return map[key];
    }
    
    public void remove(int key) {
        map[key] = -1;
    }
}

第六题: 725. 分隔链表

LeetCode: 725. 分隔链表

描述:
给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

解题思路:

  1. 首先要求得链表的长度 len
  2. 再根据这个长度, 去求得每个部分的长度.
  • 情况1: len <= k, 直接将每个节点进行划分, 不够的部分直接不管
  • 情况2: len > k, len / k 为整数. 那么直接划分成等分.
  • 情况3: len > k, len / k 有余数, 要确保每个部分相差不超过1, 所以每次取余数的1个.
  1. 例如 这里的 余数为mod,整数部分为num, 那么每部分长度就可以 让 size = num + (mod-- > 0 ? 1 : 0), 这样保证, 有余数的时候, 首先让第一部分得到1, 然后余数-1, 第二部分再看余数是否减完, 没减完继续拿1个, 保证了相差不超过1.
  2. 每次进行数组赋值之后, 要将对应的链表分割开来.

代码实现:

/**
 * 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[] splitListToParts(ListNode head, int k) {
        ListNode[] res = new ListNode[k];
        int len = 0;
        ListNode cur = head;
        while(cur != null) {
            len++;
            cur = cur.next;
        }
        int mod = len % k;
        int num = len / k;
        cur = head;
        // 这里 cur != null. 对于 len <= k 的进行了处理
        for (int i = 0; i < k && cur != null; i++) {
            res[i] = cur;
            // 对每部分进行划分
            int size = num + (mod-- > 0 ? 1 : 0);
            for(int j = 0; j < size - 1; j++) {
                cur = cur.next;
            }
            // 分割
            ListNode curNext = cur.next; 
            cur.next = null;
            cur = curNext;
        }
        return res;
    }
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://wangzhi430.blog.csdn.net/article/details/125873377

内容来源于网络，如有侵权，请联系作者删除！

数据结构leetcode算法链表

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com