ARTS-第8周

发表于

ARTS （第8周）

开篇词

重视细节。重视实践。
在工作生活和血虚中，如果都没有实践。或者是单纯的只有实践而不注意细节都不行的。

本周：

二叉树

Algorithm 算法

搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

1
2
输入: [1,3,5,6], 5
输出: 2

示例 2:

1
2
输入: [1,3,5,6], 2
输出: 1

示例 3:

1
2
输入: [1,3,5,6], 7
输出: 4

示例 4:

1
2
输入: [1,3,5,6], 0
输出: 0

这个题目一看的时候，我就发现了是一个很经典的二分法的题目，就是在数组里找到第一个小于等于目标数的坐标。也和之前在极客时间专栏讲到的知识点十分类似。

这个是我的解法，对比最简单的二分法多了2种判断。

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
public static int searchInsert(int[] nums, int target) {
		if (nums.length == 1) {
			return nums[0] >= target ? 0 : 1;
		}
		int start = 0;
		int end = nums.length - 1;
		while (start <= end) {
			int middle = (start + end) / 2;
			if (target < nums[middle]) {
				end = middle - 1;
				// 前一个数字比当前的大
				if (middle==0 || target > nums[middle - 1]) {
					return middle;
				}

			} else if (target > nums[middle]) {
				start = middle + 1;
				//最后一个的时候
				if (middle==nums.length-1 ) {
					return nums.length;
				}
			} else {
				return middle;
			}
		}
		
		return 0;
	}

做完的时候看到的最优解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int searchInsert2(int[] nums, int target) {
	        int left = 0;
	        int right = nums.length - 1;
	        while (left <= right) {
	            int mid = left + ((right - left) >> 1);
	            if (target == nums[mid]) {
	                return mid;
	            } else if (target > nums[mid]) {
	                left = mid + 1;
	                continue;
	            } else {
	                right = mid - 1;
	                continue;
	            }
	        }
	        return left;
	    }

这个最优解法，代码较少，每次二分都会利用left 保存小于目标数的坐标，直到结束。

如果结束的时候，未找到，因为mid的最后一次的值会是数组的length-1，那么答案就会是数组长度。

PS：对于这两种解法来说，第二种更简约，第一种更容易理解。

另外我还看到一个利用循环遍历的做法，代码我就不贴出来了，这个做法排在第二梯队。根据我的判断，在这题里遍历之所以能排第二，是因为数据量不大。那么假设数据量是100，遍历的执行次数就是100，而二分法的是指数阶的，所以二分法的执行次数是7次。而随着数据量的加大，差距会越来越明显，至于如果是小数据量的场景，这段函数执行的时间都极短，二者之间的差别可以忽略不计。因此在这里我不推荐那种循环遍历的做法。

Review 英文文章

https://spark.apache.org/

简单介绍了spark。

Tip 技巧

尚硅谷spring注解篇

来源自http://www.gulixueyuan.com/

简单总结了一下常用的注解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

@Configuration  //告诉Spring这是一个配置类
@ComponentScan  value:指定要扫描的包
@excludeFilters = Filter[] ：指定扫描的时候按照什么规则排除那些组件
@includeFilters = Filter[] ：指定扫描的时候只需要包含哪些组件
@FilterType.ANNOTATION：按照注解
@FilterType.ASSIGNABLE_TYPE：按照给定的类型；
@FilterType.ASPECTJ：使用ASPECTJ表达式
@FilterType.REGEX：使用正则指定
@FilterType.CUSTOM：使用自定义规则
@@Import导入组件，id默认是组件的全类名
@Conditional({Xxx.class}):满足当前条件，这个类中配置的所有bean注册才能生效；
@Scope("prototype")作用域
@Lazy懒加载
@Bean 注册bean
@Autowired：自动注入：
  		1）、默认优先按照类型去容器中找对应的组件:applicationContext.getBean(BookDao.class);找到就赋值
  		2）、如果找到多个相同类型的组件，再将属性的名称作为组件的id去容器中查找applicationContext.getBean("bookDao")
  		3）、@Qualifier("bookDao")：使用@Qualifier指定需要装配的组件的id，而不是使用属性名
  		4）、自动装配默认一定要将属性赋值好，没有就会报错；可以使用@Autowired(required=false);
  		5）、@Primary：让Spring进行自动装配的时候，默认使用首选的bean；也可以继续使用@Qualifier指定需要装配的bean的名字
//Spring还支持使用@Resource(JSR250)和@Inject(JSR330)[java规范的注解]
@Resource:可以和@Autowired一样实现自动装配功能；默认是按照组件名称进行装配的；没有能支持@Primary功能没有支持@Autowired（reqiured=false）;
@Inject:需要导入javax.inject的包，和Autowired的功能一样。没有required=false的功能；

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的21-23篇

学习了HASH算法和树的结构。

HASH算法也就是散列、哈希。只是叫法不一样

二叉树
二叉树即是每个节点最多只有2个子节点的树

除了叶子节点外，每个节点都有左右两个子节点，这种二叉树叫做满二叉树。

叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

一般可以用两种方式实现

1、链式存储，即链表。

2、顺序存储，即数组。

有一种常用的储存方式如：

根节点存储在下标为1的位置。

假设某节点存储在数组中的下标为i，那么它的左子节点的存储下标为2i，右子节点的下标为2i+1，

反过来，下标i/2位置存储的就是该节点的父节点。

出处：《数据结构与算法之美》（作者：王争）

[https://time.geekbang.org/column/intro/126]

Share 分享

https://blog.csdn.net/csdnnews/article/details/89956408

互联网人在硅谷：听 Google 资深产品经理 bigjoe 聊聊职业与热爱