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

LeetCode: 781. 森林中的兔子

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

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

解题思路:

1. 这里使用哈希表解题. value值是, 对应颜色的兔子个数
2. 遍历数组, 查看是否该值存在与哈希表中. 如果存在, 还需要判断当前value值是否大于0.
   • 例如 [1,1,1] 的情况, 这里有3个回答了1, 如果他们颜色都一样, 那么就不可能是1, 会矛盾, 所以, 只可能两个颜色一样, 剩下的1个和其他的一样.
3. 这里如果存在哈希表中, 且value值大于0, 那么就让value-1. 减去一个人.
4. 如果这里的哈希表不存在, 直接记录结果中

代码实现:

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

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

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

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

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

解题思路:

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

代码实现:

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

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

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

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

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

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

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

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

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

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

解题思路:

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

代码实现:

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

第四题: 817. 链表组件

LeetCode: 817. 链表组件

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

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

解题思路:

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

代码实现:

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int num : nums) {
            set.add(num);
        }
        int count = 0;
        ListNode cur = head;
        boolean flg = false;
        while(cur != null) {
            if(set.contains(cur.val)) {
                if(!flg) count++;
                flg = true;
                set.remove(cur.val);
            }else{
                flg = false;
            }
            cur = cur.next;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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. 反转要记录反转后的头节点,尾节点, 然后进行链接.

代码实现:

class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        int n = 1;
        while(cur != null) {
            int k = 0;
            ListNode tmp = pre;
            while(k < n && cur!= null) {
                pre = cur;
                cur = cur.next;
                k++;
            }
            
            if(k % 2 == 0) {
                ListNode tmpNext = tmp.next;
                pre = reverse(tmp.next,pre);
                tmp.next = pre;
                tmpNext.next = cur;
                pre = tmpNext;
            }
            n++;
        }
        return head;
    }
    public ListNode reverse(ListNode cur, ListNode pre) {
        ListNode ret = null;
        while(cur != pre) {
            ListNode curNext = cur.next;
            cur.next = ret;
            ret = cur;
            cur = curNext;
        }
        pre.next = ret;
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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. 然后相对的去遍历, 求得两个节点相加的值的最大值,

代码实现:

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