ARTS-第45周

发表于

ARTS （第45周）

将情况细分，尽量考虑每种情况。

Algorithm 算法

AVL树

数值的整数次方

1
2
3
4
5
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0

https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&tqId=11165&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

暴力法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 暴力法
	public double Power2(double base, int exponent) {
		if (exponent == 0)
			return 1;
		double tmp = base;
		boolean flag = exponent < 0;
		if (flag)// 取绝对值
			exponent = -exponent;
		for (int i = 1; i < exponent; i++)
			base = base * tmp;
		if (flag)
			return 1.0 / base;
		return base;
	}

迭代法

拆解答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 本来想着 如 2^8 可以等同于4^4，来减少次数的写法 ，后面发现可能不行，如果2^7之类的情况，就不行了
//然后看到了这样一个解法，理解思路之后写了出来
	public double Power(double base, int exponent) {
		int flag = Math.abs(exponent);
		double result = 1.0;
		while (flag != 0) {
			if ((flag & 1) != 0) {
				// 这个时候的base 就是之前的乘积
				// 如 7 就是可以拆分成4 2 1 这里可以拿之前的乘积来用 减少循环次数
				result = result * base;
			}
			base = base * base;
			flag >>= 1;
			// System.out.println("result:" + result);
			// System.out.println("base:" + base);
			// System.out.println("flag:" + flag);
			// System.out.println("==========");
		}
		return (exponent > 0) ? result : 1.0 / result;
	}

链表翻转

1
2
输入一个链表，反转链表后，输出新链表的表头。
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 翻转链表
	public ListNode ReverseList(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode cur = head;// 当前
		ListNode prev = null;// 前一个
		while (cur != null) {
			// 暂存下一个 （即下次循环的cur）
			ListNode temp = cur.next;
			// 新的链
			cur.next = prev;
			// 重设指针
			prev = cur;
			cur = temp;
		}
		return prev;
	}

Review 英文文章

vue的路由

https://vuejs.org/v2/guide/routing.html

Tip 技巧

（一）访问文件的方式

​ 读取和写入文件I/O操作都调用操作系统提供的接口，因为磁盘设备是由操作系统管理的，应用程序要访问物理设备只能通过系统调用的方式来工作，但是系统将内存空间分成了内核空间地址和用户空间地址，所有在读取文件或写入文件时也必然存在数据可能需要从内核空间向用户空间复制的问题。

1.标准访问文件的方式：

​ （1）读取：应用程序调用read()接口，操作下同检查在内核的高速缓存中有没有存在需要的数据，有的话直接拿，没有的话从磁盘中读取，然后缓存在操作系统的缓存中。

​ （2）写出：应用程序调用write()接口，将数据从用户地址空间复制到内核地址空间的缓存中。这时对用户来说写操作已经完成，至于什么时候再写到磁盘中由操作系统决定，或者调用sync（此方法在java.io.FileDescriptor中）同步命令。

​

2.直接I/O方式：

​ 所谓的直接I/O就是应用程序直接访问磁盘数据，不经过操作系统的内核缓存区，这样就避免了内核空间到用户空间的复制操作。这种访问文件的方式通常是在对数据的缓存管理由应用程序实现的数据库管理系统中。如在数据库管理系统中，系统知道哪些数据需要缓存，应该失效哪些数据，哪些数据是热点数据，可以提前加载，这样可以提高访问效率。因为操作系统是缓存最近一次从磁盘读取的数据，而且操作系统并不知道哪些数据是热点数据，需要提前加载，所以在这种情况下是不管用的。

​ 但是直接I/O也有缺点，如果在缓存中找不到想要的数据，那就得直接从磁盘中读取，而这种直接读取的速度非常慢。通常直接I/O跟异步I/O结合使用的话性能会更好。

​

3.同步访问文件的方式：

​ 同步访问文件的方式跟标准访问文件方式相同，但是同步访问文件只有当文件成功 写到磁盘时才会返回成功标记，这种访问方式效率低，只有当一些数据安全性要求比较高的场所中才会使用，而且通常这种操作方式的硬件都是定制的。

​

4.异步访问文件的方式：

​ 异步访问文件的方式就是访问数据的线程发出请求之后，线程会去先处理其他的事情，而不是阻塞等待，当请求的数据返回后继续处理下面的操作。这种访问文件的方式可以明显提高应用程序的效率，但不会改变访问程序的效率。

​

5.内存映射的方式：

​ 内存映射的方式是指操作系统将内存中的某一区域与磁盘中的文件关联起来，当要访问内存中的一段数据时，转换为访问文件的某一段数据。这种方式的目的同样是减少数据从内核空间缓存到用户空间缓存的数据复制操作，因为这两个空间的数据是共享的。

转载自 https://my.oschina.net/dingzebin/blog/884017 用户：追梦人_(https://my.oschina.net/dingzebin)

Share 分享

https://www.oracle.com/technetwork/java/javase/archive-139210.html 旧版JDK下载

https://www.cnblogs.com/lanhaicode/p/11321243.html AVL树

https://www.cnblogs.com/aspirant/p/7190513.html AVL树