每日刷题记录 (二十八)

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

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

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

描述:
给定一个二叉树

  1. struct Node {
  2. int val;
  3. Node *left;
  4. Node *right;
  5. Node *next;
  6. }

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

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

解题思路:

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

代码实现:

  1. class Solution {
  2. public Node connect(Node root) {
  3. if(root == null) return null;
  4. Queue<Node> queue = new LinkedList<>();
  5. queue.offer(root);
  6. while(!queue.isEmpty()) {
  7. int size = queue.size();
  8. while(size != 0) {
  9. Node top = queue.poll();
  10. if(size != 1) {
  11. top.next = queue.peek();
  12. }
  13. if(top.left != null) queue.offer(top.left);
  14. if(top.right != null) queue.offer(top.right);
  15. size--;
  16. }
  17. }
  18. return root;
  19. }
  20. }

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

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

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

插入排序 算法的步骤:

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

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

对链表进行插入排序。

解题思路:

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

代码实现:

  1. class Solution {
  2. public ListNode insertionSortList(ListNode head) {
  3. ListNode pre = new ListNode(-1);
  4. pre.next = head;
  5. while(head != null && head.next != null) {
  6. if(head.val <= head.next.val) {
  7. head = head.next;
  8. continue;
  9. }
  10. ListNode tmp = pre;
  11. while(tmp.next.val < head.next.val)
  12. tmp = tmp.next;
  13. ListNode cur = head.next;
  14. head.next = cur.next;
  15. cur.next = tmp.next;
  16. tmp.next = cur;
  17. }
  18. return pre.next;
  19. }
  20. }

第三题: 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的情况,.

代码实现:

  1. class MyCircularDeque {
  2. private int[] arr;
  3. private int head;
  4. private int tail;
  5. private int size;
  6. public MyCircularDeque(int k) {
  7. arr = new int[k];
  8. size = 0;
  9. head = 0;
  10. tail = 0;
  11. }
  12. public boolean insertFront(int value) {
  13. if(isFull()){
  14. return false;
  15. }
  16. if(head == 0) {
  17. head = arr.length - 1;
  18. }else{
  19. head = head - 1;
  20. }
  21. arr[head] = value;
  22. size++;
  23. return true;
  24. }
  25. public boolean insertLast(int value) {
  26. if(isFull()){
  27. return false;
  28. }
  29. arr[tail] = value;
  30. if(tail == arr.length-1){
  31. tail = 0;
  32. }else{
  33. tail++;
  34. }
  35. size++;
  36. return true;
  37. }
  38. public boolean deleteFront() {
  39. if(isEmpty()){
  40. return false;
  41. }
  42. if(head == arr.length - 1) {
  43. head = 0;
  44. }else {
  45. head = head + 1;
  46. }
  47. size--;
  48. return true;
  49. }
  50. public boolean deleteLast() {
  51. if(isEmpty()) return false;
  52. if(tail == 0) {
  53. tail = arr.length - 1;
  54. }else{
  55. tail--;
  56. }
  57. size--;
  58. return true;
  59. }
  60. public int getFront() {
  61. if(isEmpty()) return -1;
  62. return arr[head];
  63. }
  64. public int getRear() {
  65. if(isEmpty()) return -1;
  66. if(tail == 0) return arr[arr.length - 1];
  67. return arr[tail-1];
  68. }
  69. public boolean isEmpty() {
  70. return size == 0;
  71. }
  72. public boolean isFull() {
  73. return size == arr.length;
  74. }
  75. }

第四题: 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;

代码实现:

  1. class MyHashSet {
  2. boolean[] map;
  3. public MyHashSet() {
  4. map = new boolean[1000001];
  5. }
  6. public void add(int key) {
  7. map[key] = true;
  8. }
  9. public void remove(int key) {
  10. map[key] = false;
  11. }
  12. public boolean contains(int key) {
  13. return map[key] == true;
  14. }
  15. }

第五题: 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

代码实现:

  1. class MyHashMap {
  2. private int[] map;
  3. public MyHashMap() {
  4. map = new int[1000001];
  5. Arrays.fill(map,-1);
  6. }
  7. public void put(int key, int value) {
  8. map[key] = value;
  9. }
  10. public int get(int key) {
  11. return map[key];
  12. }
  13. public void remove(int key) {
  14. map[key] = -1;
  15. }
  16. }

第六题: 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. 每次进行数组赋值之后, 要将对应的链表分割开来.

代码实现:

  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. * int val;
  5. * ListNode next;
  6. * ListNode() {}
  7. * ListNode(int val) { this.val = val; }
  8. * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9. * }
  10. */
  11. class Solution {
  12. public ListNode[] splitListToParts(ListNode head, int k) {
  13. ListNode[] res = new ListNode[k];
  14. int len = 0;
  15. ListNode cur = head;
  16. while(cur != null) {
  17. len++;
  18. cur = cur.next;
  19. }
  20. int mod = len % k;
  21. int num = len / k;
  22. cur = head;
  23. // 这里 cur != null. 对于 len <= k 的进行了处理
  24. for (int i = 0; i < k && cur != null; i++) {
  25. res[i] = cur;
  26. // 对每部分进行划分
  27. int size = num + (mod-- > 0 ? 1 : 0);
  28. for(int j = 0; j < size - 1; j++) {
  29. cur = cur.next;
  30. }
  31. // 分割
  32. ListNode curNext = cur.next;
  33. cur.next = null;
  34. cur = curNext;
  35. }
  36. return res;
  37. }
  38. }

相关文章