ARTS-第29周

发表于

ARTS （第29周）

表象和实际不一样。

最近看的书从基础讲解起了java。

发现了很多和以前理解不一样的东西。

如类的信息的编译和加载，加载的流程。也借此解开了很多以前的困惑。

但也带了更多的困惑。

Algorithm 算法

数组循环队列

循环队列的本质就是将数组当成一个环，头尾相连，

其他地方的实现不难，难的就是只有一个，就是获取头或者尾的指针的下一个位置，主要考虑的情况是指针是数组最后一个位置的情况。

如max是8 ，tail是7那么下一个指针获取的就应该是0，主要为的也是这样的特殊情况。

这里的算法为 -> (tail + 1) % max ;

加一取模 即在0~max-1的环里，获取tail里的下一个数
加一就等于当前数字的下一个数字 ,模max就等于最大数字是max-1
使得算出来的数字是在环里的下一个数字

普通情况就等同于 tail+1 == 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
64
65
66
67
68
69
70
71

/**
 * 循环队列
 * @author Tencent
 *
 */
public class CircularArray {
	//核心算法:获取指针在环里的下一个数字-> (tail + 1) % max ;
	String[] e;
	int size;
	int max;
	int head = 0;// 头
	int tail = 0;// 尾

	public CircularArray() {
		this(16);
	}

	public CircularArray(int s) {
		e = new String[s];
		max = s;
	}

	public boolean enqueue(String v) {
		if (!isFull()) {
			e[tail] = v;
			size++;
			// 刷新tail指针 得出的数字是在环里的下一个数字
			tail = (tail + 1) % max;
			return true;
		}
		return false;
	}

	private String dequeue() {
		if (isEmpty())
			return null;
		String val = e[head];
		// 刷新head指针 得出的数字是在环里的下一个数字
		head = (head + 1) % max;
		size--;
		return val;
	}

	private boolean isFull() {
		// 加一取模 即在0~max-1的环里，获取tail里的下一个数
		// 加一就等于当前数字的下一个数字 ,模max就等于最大数字是max-1
		// 使得算出来的数字是在环里的下一个数字
		// 如max是8 ，tail是7那么获取的就是0，主要为的也是这样的特殊情况
		// 普通情况就等同于 tail+1 == head
		return (tail + 1) % max == head;
	}

	// PS 个人感觉如果想要更容易理解的写法
	private boolean isFull_() {
		if (tail == max - 1) {
			// 末尾的时候 判断head是否为0
			return head == 0;
		}
		// 其它时候 直接判断下一个数字是不是head
		return tail + 1 == head;
	}

	private boolean isEmpty() {
		return head == tail;
	}

	private int getSize() {
		return size;
	}
}

###69. x 的平方根

LeetCode 69

https://leetcode-cn.com/problems/sqrtx/submissions/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

第一个解法

将有可能的数都罗列出来，但发现int做计算有进度的问题。然后发现效率不高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 执行用时:15 ms,在所有java提交中击败了10.65%的用户
	// 内存消耗:33.4 MB,在所有java提交中击败了75.82%的用户
	public int mySqrt_1(int x) {
		// 用遍历数字做平方
		// 找到第一个小于X的数字
		// 因为是非负整数 所以设置这两个边界
		if (x == 1)
			return x;
		// 精度问题 进行到这样的数字在进行计算会变成负数
		if (x >= 2147395600) {
			// PS:这一行有点取巧 但如果在int范围里计算是没问题的
			// 是提交错误之后发现的
			return 46340;
		}
		int l = 0;
		int r = x / 2 + 1;
		for (; l <= r; l++) {
			if (l * l > x) {
				return l - 1;
			}
		}
		return l;
	}

第二个解法

在原有的基础上考虑精度的问题后。然后发现效率不高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 执行用时:29 ms,在所有java提交中击败了8.23%的用户
	// 内存消耗:33.7 MB,在所有java提交中击败了75.07%的用户
	public int mySqrt_2(int x) {
		if (x == 1)
			return x;
		// 用遍历数字做平方
		// 找到第一个小于X的数字
		// 因为是非负整数 所以设置这两个边界

		// 精度问题 用long类型
		long m = x;
		long l = 0;
		long r = x / 2 + 1;
		for (; l <= r; l++) {
			if (l * l > m) {
				return (int) l - 1;
			}
		}
		return (int) l;
	}

第三个解法（二分）

但不是找等值的二分 而是找第一个小于等于数的二分 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//执行用时:2 ms,在所有java提交中击败了93.59%的用户
	//内存消耗:33.4 MB,在所有java提交中击败了76.15%的用户
	public int mySqrt(int x) {
		if (x == 1)
			return x;
		// 前面发现了进度问题 这里都用long类型
		long l = 0;
		long r = x;
		long max = x;// max其实可以不用
		// 二分
		// 但不是找等值的二分 而是找第一个小于等于数的二分 
		while (l < r - 1) {
			long m = (l + r) / 2;
			long s = m * m;
			if (max == s)
				return (int) m;
			else if (max > s) {
				l = m;
			} else {
				r = m;
			}
		}
		return (int) l;
	}

另外看到的几个比较经典的答案

leetcode里all_is_wel用户的答案

这里利用的是魔数0x5f3759df

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int mySqrt(int x) {
        long t = x;
        t = 0x5f3759df - (t >> 1);
        while (!(t*t <= x && (t+1)*(t+1) > x))
            t = (x/t + t)/2;
		return (int)t;
    }
}
 	作者：all_is_wel
	 链接：https://leetcode-cn.com/problems/sqrtx/comments/
	 来源：力扣（LeetCode）
	 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

经典的解法-牛顿迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 牛顿迭代法
	class Solution {
		int s;

		public int mySqrt(int x) {
			s = x;
			if (x == 0)
				return 0;
			return ((int) (sqrts(x)));
		}

		public double sqrts(double x) {
			double res = (x + s / x) / 2;
			if (res == x) {
				return x;
			} else {
				return sqrts(res);
			}
		}
	}
	 作者：LOAFER
	 链接：https://leetcode-cn.com/problems/sqrtx/solution/niu-dun-die-dai-fa-by-loafer/
	 来源：力扣（LeetCode）
	 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Review 英文文章

https://spring.io/guides/gs/rest-service/

spring官网的介绍 如何构建一个 RESTful Web Service

Tip 技巧

1、基础数据类型的二进制表示

​ 如整数类型，数字类型，负数用补码来表示的，这么取是因为好计算。

2、类的基础、继承、扩展。

类信息、方法信息等是经过编译的。会在加载的时候将这些信息加载进内存。

3、Random类随机（线性同余法），

jdk里的Random类是一种伪随机算法，但基本能够达到使用的要求。当然特殊场景可以根据需求使用其他的随机方法或者自己定制。

Share 分享

https://blog.csdn.net/weixin_33901641/article/details/91452010 java句柄