每日刷题记录 (二十九)

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

第一题: 781. 森林中的兔子

LeetCode: 781. 森林中的兔子

描述:
森林中有未知数量的兔子。提问其中若干只兔子 “还有多少只兔子与你（指被提问的兔子）颜色相同?” ，将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

解题思路:

  1. 这里使用哈希表解题. value值是, 对应颜色的兔子个数

  • 遍历数组, 查看是否该值存在与哈希表中. 如果存在, 还需要判断当前value值是否大于0.

  • 例如 [1,1,1] 的情况, 这里有3个回答了1, 如果他们颜色都一样, 那么就不可能是1, 会矛盾, 所以, 只可能两个颜色一样, 剩下的1个和其他的一样.

  • 这里如果存在哈希表中, 且value值大于0, 那么就让value-1. 减去一个人.

  • 如果这里的哈希表不存在, 直接记录结果中

代码实现:

  1. class Solution {
  2.     public int numRabbits(int[] answers) {
  3.         Map<Integer,Integer> map = new HashMap<>();
  4.         int res = 0;
  5.         for(int answer : answers) {
  6.             if(map.containsKey(answer) && map.get(answer) > 0) {
  7.                 map.put(answer,map.get(answer) - 1);
  8.             }else {
  9.                 res += answer + 1;
  10.                 map.put(answer,answer);
  11.             }
  12.         }
  13.         return res;
  14.     }
  15. }

第二题: 783. 二叉搜索树节点最小距离

LeetCode: 783. 二叉搜索树节点最小距离

描述:
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

解题思路:

  1. 由于是二叉搜索树. 中序遍历就是有序的.
  2. 然后对于有序的去求差值, 就可以得到最小的差值.
  3. 用根节点去比较.

代码实现:

  1. class Solution {
  2.     private TreeNode pre = null;
  3.     private int res = Integer.MAX_VALUE;
  4.     public int minDiffInBST(TreeNode root) {
  5.         if(root == null) return 0;
  6.         minDiffInBST(root.left);
  7.         if(pre != null) {
  8.             res = Math.min(res,root.val - pre.val);
  9.         }
  10.         pre = root;
  11.         minDiffInBST(root.right);
  12.         return res;
  13.     }
  14. }

第三题: 804. 唯一摩尔斯密码词

LeetCode: 804. 唯一摩尔斯密码词

描述:
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如:

  • 'a' 对应 ".-" ，
  • 'b' 对应 "-..." ，
  • 'c' 对应 "-.-." ，以此类推。

为了方便，所有 26 个英文字母的摩尔斯密码表如下：

  1. [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

给你一个字符串数组 words ，每个单词可以写成每个字母对应摩尔斯密码的组合。

  • 例如，“cab” 可以写成 “-.-…–…” ，(即 “-.-.” + “.-” + “-…” 字符串的结合)。我们将这样一个连接过程称作 单词翻译 。

对 words 中所有单词进行单词翻译，返回不同 单词翻译 的数量。

解题思路:

  1. 这里直接定义一个数组, 用来放入每个字母对应的摩尔斯密码
  2. 然后遍历 words, 得到每个字符串对应的摩尔斯密码的字符串形式.
  3. 放入set中, 查看set的大小

代码实现:

  1. class Solution {
  2.     public int uniqueMorseRepresentations(String[] words) {
  3.         String[] str = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
  4.         Set<String> set = new HashSet<>();
  5.         for(String word : words) {
  6.             StringBuilder sb = new StringBuilder();
  7.             for(char ch : word.toCharArray()) {
  8.                 sb.append(str[ch-'a']);
  9.             }
  10.             set.add(sb.toString());
  11.         }
  12.         return set.size();
  13.     }
  14. }

第四题: 817. 链表组件

LeetCode: 817. 链表组件

描述:
给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。

返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。

解题思路:

  1. 首先将 数组 nums 中所有元素 添加到哈希表中
  2. 再去遍历链表, 如果链表中存在元素, 就表示这是一个组件, 记录依次.
  3. 如果此时遍历元素不存在哈希表中, 那么就分隔开, 下次在遍历存在的时候, 就需要再次记录.
  4. 可以使用一个 布尔类型去标记

代码实现:

  1. class Solution {
  2.     public int numComponents(ListNode head, int[] nums) {
  3.         Set<Integer> set = new HashSet<>();
  4.         for(int num : nums) {
  5.             set.add(num);
  6.         }
  7.         int count = 0;
  8.         ListNode cur = head;
  9.         boolean flg = false;
  10.         while(cur != null) {
  11.             if(set.contains(cur.val)) {
  12.                 if(!flg) count++;
  13.                 flg = true;
  14.                 set.remove(cur.val);
  15.             }else{
  16.                 flg = false;
  17.             }
  18.             cur = cur.next;
  19.         }
  20.         return count;
  21.     }
  22. }

第五题: 2074. 反转偶数长度组的节点

LeetCode: 2074. 反转偶数长度组的节点

描述:
给你一个链表的头节点 head 。

链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, …）。一个组的 长度 就是组中分配到的节点数目。换句话说：

  • 节点 1 分配给第一组
  • 节点 2 和 3 分配给第二组
  • 节点 4、5 和 6 分配给第三组，以此类推

注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。

反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。

解题思路:

  1. 这里遍历链表的时候, 可以使用一个n=1来记录, 每次n++, 这也分组就是1 , 2 ,3 ,4 …
  2. 这里要注意, 可能你分组了2个 但链表长度不够的情况, 所以遍历的时候也要注意真实的分组长度.
  3. 如果真实长度为偶数 就要进行反转.
  4. 反转要记录反转后的头节点,尾节点, 然后进行链接.

代码实现:

  1. class Solution {
  2.     public ListNode reverseEvenLengthGroups(ListNode head) {
  3.         ListNode cur = head;
  4.         ListNode pre = null;
  5.         int n = 1;
  6.         while(cur != null) {
  7.             int k = 0;
  8.             ListNode tmp = pre;
  9.             while(k < n && cur!= null) {
  10.                 pre = cur;
  11.                 cur = cur.next;
  12.                 k++;
  13.             }
  14.             
  15.             if(k % 2 == 0) {
  16.                 ListNode tmpNext = tmp.next;
  17.                 pre = reverse(tmp.next,pre);
  18.                 tmp.next = pre;
  19.                 tmpNext.next = cur;
  20.                 pre = tmpNext;
  21.             }
  22.             n++;
  23.         }
  24.         return head;
  25.     }
  26.     public ListNode reverse(ListNode cur, ListNode pre) {
  27.         ListNode ret = null;
  28.         while(cur != pre) {
  29.             ListNode curNext = cur.next;
  30.             cur.next = ret;
  31.             ret = cur;
  32.             cur = curNext;
  33.         }
  34.         pre.next = ret;
  35.         return pre;
  36.     }
  37. }

第六题: 2130. 链表最大孪生和

LeetCode: 2130. 链表最大孪生和

描述:
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。

  • 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

解题思路:

  1. 这里依次遍历就可以实现.
  2. 首先获取到中间节点. 这里使用快慢指针的方法.
  3. 然后将后半部分进行反转.
  4. 让一个节点指向左半部分的头节点, 一个节点指向右半部分的头节点.
  5. 然后相对的去遍历, 求得两个节点相加的值的最大值,

代码实现:

  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 int pairSum(ListNode head) {
  13.         ListNode fast = head;
  14.         ListNode slow = head;
  15.         while(fast != null && fast.next != null) {
  16.             fast = fast.next.next;
  17.             slow = slow.next;
  18.         }
  19.         ListNode cur = slow;
  20.         ListNode ret = null;
  21.         while(cur != null) {
  22.             ListNode curNext = cur.next;
  23.             cur.next = ret;
  24.             ret = cur;
  25.             cur = curNext;
  26.         }
  27.         int max = 0;
  28.         while(head != null && ret != null) {
  29.             max = Math.max(max,head.val + ret.val);
  30.             head = head.next;
  31.             ret = ret.next;
  32.         }
  33.         return max;
  34.     }
  35. }

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

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

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

leetcode算法动态规划

相关文章

    查看更多

    热门标签

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

    最新文章

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