Fork me on GitHub

ARTS(4)

ARTS 第四周分享

每周完成一个ARTS(也就是 Algorithm、Review、Tip、Share 简称ARTS):

  1. 每周至少做一个 leetcode 的算法题
  2. 阅读并点评至少一篇英文技术文章
  3. 学习至少一个技术技巧
  4. 分享一篇有观点和思考的技术文章。

Algorithm

力扣 24. 两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

核心思路:为整个链表增加一个头结点,这样一来可以避免 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

import org.junit.Test;

public class 两两交换链表中的节点 {

@Test
public void testResult() {
ListNode node4 = new ListNode(4);
ListNode node3 = new ListNode(3);
ListNode node2 = new ListNode(2);
ListNode node1 = new ListNode(1);
node4.next = null;
node3.next = node4;
node2.next = node3;
node1.next = node2;
ListNode Head = swapPairs(node1);
while (Head != null) {
System.out.print(Head.val + " ");
Head = Head.next;
}
System.out.println();
}

public ListNode swapPairs(ListNode head) {
ListNode root = new ListNode(0);
ListNode pre = root;
pre.next = head;
ListNode current = pre.next;
if (current == null || current.next == null) {
return current;
}
ListNode next = current.next;
while (next != null) {
ListNode newCurr = next.next;
next.next = current;
current.next = newCurr;
pre.next = next;

// 移位
pre = current;
current = newCurr;
if (current == null) {
break;
}
next = current.next;
}
return root.next;

}


// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
}
}

}

力扣 594 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在,给定一个整数数组,你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是:[3,2,2,2,3].

说明: 输入的数组长度最大不超过20,000.

思路:很简单,统计所有元素及出现次数,因为限制最大最小元素差是1,那么将所有相邻和拿出来就 ok 了。

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
38
39
import org.junit.Test;
import java.util.Map;
import java.util.TreeMap;

public class 最长和谐子序列 {

@Test
public void testResult(){
int[] nums = {1,3,2,2,5,2,3,7};
int result = findLHS(nums);
System.out.println(result);
}

public int findLHS(int[] nums) {
int max = Integer.MIN_VALUE;
Map<Integer,Integer> map = new TreeMap<>();
for(int i = 0;i<nums.length;++i){
int num = nums[i];
if(map.containsKey(num)){
map.put(num,map.get(num)+1);
}else{
map.put(num,1);
}
}
for(int i:map.keySet()){
if(map.containsKey(i+1)){
int temp = map.get(i)+map.get(i+1);
if(temp>max){
max = temp;
}
}
}
if(max >Integer.MIN_VALUE){
return max;
}else{
return 0;
}
}
}

力扣781. 森林中的兔子

森林中,每个兔子都有颜色。其中一些兔子(可能是全部)告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。

返回森林中兔子的最少数量。

示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 “1” 的兔子可能有相同的颜色,设为红色。
之后回答了 “2” 的兔子不会是红色,否则他们的回答会相互矛盾。
设回答了 “2” 的兔子为蓝色。
此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。

输入: answers = [10, 10, 10]
输出: 11

输入: answers = []
输出: 0

思路:统计每个数字出现的次数,然后比较次数跟 key+1的大小,执行不同的逻辑

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
38
39
import org.junit.Test;

import java.util.Map;
import java.util.TreeMap;

@SuppressWarnings("all")
public class 森林中的兔子 {
@Test
public void getResult() {
// int[] answers = {1, 1, 2};
int[] answers = {10, 10, 10};
int result = numRabbits(answers);
System.out.println(result);
}

public int numRabbits(int[] nums) {
int result = 0;
Map<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < nums.length; ++i) {
int num = nums[i];
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
for (int key : map.keySet()) {
int value = map.get(key);
while (value > key + 1) {
result += key + 1;
value -= key + 1;
}
if (value <= key + 1) {
result += key + 1;
}
}
return result;
}
}

Review

本周分享 ZGC 的一篇文章
原文地址:A FIRST LOOK INTO ZGC
解读地址:本站另一处,点击查看:ZGC 特性解读

Tip

  1. mac 上压缩时默认使用 UTF-8,拿到的 zip 文件放到 windows 平台下,文件名都是乱码,这时候要么使用另外的压缩软件进行重新压缩,要么直接将 zip 后缀改成 rar 后缀,这样就可以避免编码问题。
  2. 进入JVM命令查询网站,可以在线查询 JVM 调参各项命令,简单易用。

Share

本周分享的是我用 Wireshark 进行网络抓包测试,学习 Http、Tcp 等网络协议的实战。

地址在本站另一处,点击查看:网络协议之抓包大作战

-------------The End-------------