Fork me on GitHub

ARTS(4)

Posted on | Edited on | In | Views:

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
63

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
40
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-------------