Fork me on GitHub

ARTS(3)

Posted on | Edited on | In | Views:

ARTS 第三周分享

每周完成一个ARTS（也就是 Algorithm、Review、Tip、Share 简称ARTS）：

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

Algorithm

LeetCode 593. Valid Square

Given the coordinates of four points in 2D space, return whether the four points could construct a square.

The coordinate (x,y) of a point is represented by an integer array with two integers.

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

思路：以某点（如 p1）为顶点，确定与其他三点的距离是否满足等边及勾股定理。
如果满足，轮换顶点（一般三个点即可，轮换四个点更稳妥）

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
import org.junit.Assert;
import org.junit.Test;
import java.util.Arrays;

public class ValidSquare {

	@Test
	public void getResult() {
		int[] p1 = {0, 1};
		int[] p2 = {1, 1};
		int[] p3 = {1, 0};
		int[] p4 = {0, 0};

		boolean actual = validSquare(p1, p2, p3, p4);
		Assert.assertTrue(actual);
	}

	public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
		return validOnce(p1, p2, p3, p4)
				&& validOnce(p2, p3, p4, p1)
				&& validOnce(p3, p1, p2, p4)
				&& validOnce(p4, p1, p2, p3);

	}

	public boolean validOnce(int[] p1, int[] p2, int[] p3, int[] p4) {
		int len1 = getLen(p1, p2);
		int len2 = getLen(p1, p3);
		int len3 = getLen(p1, p4);

		int[] a = {len1, len2, len3};
		Arrays.sort(a);
		if (a[2] == 0) {
			return false; // 避免四点重合的情况
		}
		if (a[0] != a[1] || a[0] * 2 != a[2]) {
			return false;
		}
		return true;
	}

	private int getLen(int[] a, int[] b) {
		return ((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
	}
}

LeetCode 647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.

Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

思路：求回文子串的个数，使用动归时边找边统计。

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

public class PalindromicSubstrings {

	@Test
	public void testResult() {
		String s = "aaa";
		System.out.println(countSubstrings(s));
	}

	public int countSubstrings(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		int n = s.length();
		int result = 0;
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; ++i) {
			dp[i][i] = 1;
			++result;
			if (i < n - 1) {
				if (s.charAt(i) == s.charAt(i + 1)) {
					dp[i][i + 1] = 1;
					++result;
				} else {
					dp[i][i + 1] = 0;
				}
			}
		}

		for (int step = 3; step <= n; ++step) {
			for (int i = 0; i + step <= n; ++i) {
				int j = i + step - 1;
				if (dp[i + 1][j - 1] == 0) {
					dp[i][j] = 0;
				} else {
					if (s.charAt(i) == s.charAt(j)) {
						dp[i][j] = 1;
						++result;
					} else {
						dp[i][j] = 0;
					}
				}
			}
		}
		return result;
	}
}

LeetCode 491. Increasing Subsequences

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

思路：使用 DFS 以及 visited 数组去重。

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

import org.junit.Test;

import java.util.*;

public class IncreasingSubsequences {

	@Test
	public void testResult() {
		int[] nums = {4, 6, 7, 7};
		List<List<Integer>> list = findSubsequences(nums);
		for (List<Integer> subList : list) {
			subList.forEach(i -> System.out.print(i + " "));
			System.out.println();
		}
	}

	public List<List<Integer>> findSubsequences(int[] nums) {
		if (nums == null) {
			return null;
		}
		List<List<Integer>> list = new ArrayList<>();
		if (nums.length == 0) {
			return list;
		}
		List<Integer> subList = new ArrayList<>();
		getSubList(nums, 0, nums.length - 1, subList, list);
		return list;
	}

	private void getSubList(int[] nums, int head, int tail, List<Integer> subList, List<List<Integer>> list) {
		if (subList.size() >= 2) {
			list.add(new ArrayList<>(subList));
		}
		Set<Integer> visited = new HashSet<>();
		for (int i = head; i <= tail; ++i) {
			if (visited.contains(nums[i])) {
				continue;
			}
			visited.add(nums[i]);
			if (subList.size() == 0 || nums[i] >= subList.get(subList.size() - 1)) {
				subList.add(nums[i]);
				getSubList(nums, i + 1, tail, subList, list);
				subList.remove(subList.size() - 1);
			}
		}
	}
}

Review

Database Caching With Redis and Java

我们对缓存的要求主要有两点：

  • 缓存部分数据，等待命中；
  • 保持缓存跟 DB 的数据一致性。
  1. 主要解释了数据库的几种缓存策略：
    1. Read-Through Caching Strategy（直读缓存机制）。优先从缓存中读取，若没取到，则查 DB，同时将查到的数据在缓存中存一份。特点：适合读任务多的场景。比如新闻网站等的数据，会被大量阅读而不是修改。第一次从缓存中取数据时常常会失败，开发者可以考虑提前缓存一部分可能的热点数据。
    2. Write-Through Caching Strategy（直写缓存机制）。优先写入缓存，然后立即再写入 DB。
    3. Write-Behind Caching Strategy（写回缓存机制）。优先写入缓存，延后写回 DB 中。适合于写任务多的场景。特点：通常是由数据被替换出缓存时，才会被写到 DB 中；缺点：一旦断点，数据无法找回。
  2. 使用 Redisson 作为客户端的缓存操作（其将数据放入 Map 中）。
    1. 直读缓存机制中，若缓存未命中，则会通过MapLoader对象进行载入；
    2. 直写缓存机制中，只有当缓存跟 DB 的数据都被MapWriter对象更新完成之后，才会退出 update 方法。
    3. 写回缓存机制中，同样使用MapWriter接口来完成异步更新，可以设置writeBehindThreads 参数来表示执行写操作的线程数量。
  3. 总结：Redisson 中的RMap,RMapCache, RLocalCachedMap,RLocalCachedMapCache四个对象都支持上述策略，后两者的读操作更快一些。

Tip

今天分享一个在 Mac 电脑上使用 workflow （也叫自动操作）功能的实践。

自动化你的工作很重要！！

效果：自动改变图片分辨率，主要用来应对图片尺寸过大的问题。
步骤：

  1. 设置 workflow，如下图：

说明：将图片拖入 pics 文件夹中，此 workflow 会将图片缩放到1440像素，然后处理后的图片会在桌面上出现。上面的文件夹名称跟像素都可以按个人喜好设置。

  1. 如果需要修改此 workflow，如下图，在你的 pics 文件夹处右键，进入“文件夹操作设置”，就可以继续修改自定义的 workflow 了。

Share

本周分享的是最近写的一份代码实现，主要是关于类加载过程解读的，请点击下方链接查看：

自定义一个类加载器代码实现

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