第一题: 1108. IP 地址无效化

LeetCode: 1108. IP 地址无效化

描述:
给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。

所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。

解题思路:

1. 这里利用的是字符串.
2. 只要遇到了 . 就拼接 [.]

代码实现:

class Solution {
    public String defangIPaddr(String address) {
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < address.length(); i++) {
            if(address.charAt(i)=='.') {
                res.append("[.]");
            }else{
                res.append(address.charAt(i));
            }
        }
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

第二题: 1431. 拥有最多糖果的孩子

LeetCode: 1431. 拥有最多糖果的孩子

描述:
给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

解题思路:

1. 第一次遍历, 拿到数组中 最大的元素.
2. 第二次遍历, 看数组中元素加上 extraCandies 是否大于这个最大值.
   • 如果大于, 就是true
   • 如果小于, 就是false

代码实现:

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        List<Boolean> res = new ArrayList<>();
        int max = 0;
        for(int candie : candies) {
            max = Math.max(candie,max);
        }
        for(int i = 0; i < candies.length ; i++) {
            if(candies[i] + extraCandies >= max) {
                res.add(true);
            }else{
                res.add(false);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第三题: 1720. 解码异或后的数组

LeetCode: 1720. 解码异或后的数组

描述:
未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

解题思路:

1. 解题思路 由 a ^ b = c, 限制知道b, c,求a, a = b ^ c
2. 按题意, 结果数组的大小是 encoded 数组长度+1.
3. 首元素是 first. 后面的元素依次是 res[i] = res[i-1] ^ encoded[i-1]

代码实现:

class Solution {
    public int[] decode(int[] encoded, int first) {
        int[] res = new int[encoded.length + 1];
        res[0] = first;
        for(int i = 0; i < encoded.length; i++) {
            res[i+1] = encoded[i] ^ res[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10

第四题: 1863. 找出所有子集的异或总和再求和

LeetCode: 1863. 找出所有子集的异或总和再求和

描述:
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

• 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

注意：在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

解题思路:

1. 使用回溯解题.
2. 注意剪枝的情况, 不能重复使用元素.
3. 将所有异或的结果进行相加.

代码实现:

class Solution {
    private int res = 0;
    public int subsetXORSum(int[] nums) {
        bfs(nums,0,0);
        return res;
    }
    public void bfs(int[] nums, int start , int tmp) {
        res += tmp;
        for(int i = start; i < nums.length; i++) {
            bfs(nums, i+1, tmp^nums[i]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

第五题: 2160. 拆分数位后四位数字的最小和

LeetCode: 2160. 拆分数位后四位数字的最小和

描述:
给你一个四位 正 整数 num 。请你使用 num 中的 数位 ，将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ，且 num 中 所有 数位都必须使用。

• 比方说，给你 num = 2932 ，你拥有的数位包括：两个 2 ，一个 9 和一个 3 。一些可能的 [new1, new2] 数对为 [22, 93]，[23, 92]，[223, 9] 和 [2, 329] 。

请你返回可以得到的 new1 和 new2 的 最小 和。

解题思路:

1. 这里首先将所有位数都进行一个数组化.
2. 然后对这个数组 进行排序.
3. 例如 a < b < c < d, 让 a*10 + d, b*10 + c, 这就是两个最小和数对.
4. 返回这两个数的和

代码实现:

class Solution {
    public int minimumSum(int num) {
        int[] arr = new int[4];
        for(int i = 0; i < 4; i++) {
            arr[i] = num%10;
            num /= 10;
        }
        Arrays.sort(arr);
        return arr[0]*10+arr[3] + arr[1]*10+arr[2];
    }
}
1
2
3
4
5
6
7
8
9
10
11

第六题: 2181. 合并零之间的节点

LeetCode: 2181. 合并零之间的节点

描述:
给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。

对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。

返回修改后链表的头节点 head 。

解题思路:

1. 使用一个 cur 指向头节点, 这个cur用来进行移动
2. 使用一个 pre 指向头节点, 这个pre用来对数求和之后的修改. 始终让pre指向为0的节点.
3. 使用一个node, 指向pre的前一个节点, 这样可以去除最后一个为0的情况
4. 首先进行遍历, 如果 cur.val != 0, 就进行计算, 求得不为0 这一连续节点的值 tmp.
5. 让pre 节点的值进行替换, 然后让pre指向下一个为0的节点. 让node指向pre的前一个节点.
6. 遍历结束, 让node.next 置空. 多了一个为0的节点, 要去掉
   

代码实现:

/**
 * 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 mergeNodes(ListNode head) {
        ListNode cur = head;
        ListNode pre = head;
        ListNode node = null;
        while(cur != null) {
            int tmp = 0;
            while(cur != null && cur.val != 0) {
                tmp += cur.val;
                cur = cur.next;
            }
            if(tmp != 0) {
                node = pre;
                pre.val = tmp;
                pre.next = cur;
                pre = cur;
            }
            cur = cur.next;
        }
        node.next = null;
        return head;
    }
}
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