ARTS-第7周

发表于

ARTS （第7周）

最近发现经常阅读CSDN和其它一些渠道的关于程序员的新闻或者文章，
都能对自己有很大的帮助。
比如学习方向，思考方式等。

本周：

几种小算法

Algorithm 算法

有效括号

https://leetcode-cn.com/problems/valid-parentheses/comments/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  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 boolean isValid(String s) {
		try {
			Stack<Character> stack = new Stack<>();
			for (int i = 0; i < s.length(); i++) {
				char c = s.charAt(i);
				if (c == ')') {
					if (!stack.pop().equals('(')) {
						return false;
					}
				} else if (c == '}') {
					if (!stack.pop().equals('{')) {
						return false;
					}
				} else if (c == ']') {
					if (!stack.pop().equals('[')) {
						return false;
					}
				} else {
					stack.add(c);
				}

			}
			if (stack.empty())
				return true;
		} catch (Exception e) {
		}
		return false;
	}

这里我在这个算法的答案里看到的最佳答案，也是用的栈结构，不过他在这里是用数组写了一个简易的栈，所以这个栈，对比jdk的原生栈类功能要少的多，开销要小得多，但在这个题目的场景里，已经完全足够了。

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
public boolean isValid(String s) {
       int len=s.length();
       char[] stack=new char[len];
       int k=-1;
       char[] list=s.toCharArray();
       for(int i=0;i<list.length;i++){
           if(list[i]=='('||list[i]=='['||list[i]=='{'){
               stack[++k]=list[i];
           }else{
               if(k<0){
                   return false;
               }
                if (stack[k] == '[' && list[i] != ']') {
         return false;
       } else if (stack[k] == '(' && list[i] != ')') {
         return false;
       } else if (stack[k] == '{' && list[i] != '}') {
         return false;
       }
               k--;
           }
       }
       if(k>=0){
           return false;
       }
       return true;
   }

合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

链表结构

1
2
3
4
5
6
7
8
9
10
11
12
13
public static class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
		//这个方法是我后面加进去的，方便测试用的
		public ListNode setNext(int x) {
			this.next = new ListNode(x);
			return next;
		}
	}

解法

因为这里是2个有序的集合的合并，就完全符合两路归并排序中的排序部分思想，

因此我在这里就是用归并排序的排序方式进行排序的。每次都是用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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) {
			return l2;
		}
		if (l2 == null) {
			return l1;
		}
		ListNode r = null;
		ListNode c = null;
		// 匹配哪个ListNode的数据放在最前面
		// 相等则无所谓哪个放前面
		if (l1.val > l2.val) {
			r = l2;
			l2 = l2.next;
			c = r;
		} else {
			r = l1;
			l1 = l1.next;
			c = r;
		}
		// 类似归并排序的归并部分的算法
		while (l1 != null && l2 != null) {
			if (l1.val > l2.val) {
				c.next = l2;
				l2 = l2.next;

			} else {
				ListNode n = new ListNode(l1.val);
				c.next = l1;
				l1 = l1.next;
			}
			c = c.next;
		}
		// 其它的本身就有链接了
		if (l1 != null) {
			c.next = l1;
		}
		// 其它的本身就有链接了
		if (l2 != null) {
			c.next = l2;
		}

		return r;
	}

这个答案是我看到的一个更加合适的答案，加了一个哨兵节点，思路和上面的一致，因为多了哨兵节点，所以代码可以少写一些。

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
// 加了个哨兵头
	public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
		// 类似归并排序中的合并过程
		ListNode dummyHead = new ListNode(0);
		ListNode cur = dummyHead;
		while (l1 != null && l2 != null) {
			if (l1.val < l2.val) {
				cur.next = l1;
				cur = cur.next;
				l1 = l1.next;
			} else {
				cur.next = l2;
				cur = cur.next;
				l2 = l2.next;
			}
		}
		// 任一为空，直接连接另一条链表
		if (l1 == null) {
			cur.next = l2;
		} else {
			cur.next = l1;
		}

		return dummyHead.next;
	}

移除元素

https://leetcode-cn.com/problems/remove-element/

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

1
2
3
4
5
给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

这里我的思路有点类似快慢指针法，快指针负责遍历全部节点，慢指针负责符合的节点。每遇到一个符合的节点，慢指针就给当前节点赋值，然后快慢指针向前，这题的其实类似之前做的一道题【删除排序数组中的重复项】，做法也比较类似。

1
2
3
4
5
6
7
8
9
10
// 类似快慢指针
	public static int removeElement(int[] nums, int val) {
		int r = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != val) {
				nums[r++] = nums[i];
			}
		}
		return r;
	}

实现strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

1
2
输入: haystack = "hello", needle = "ll"
输出: 2

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf()) 定义相符。

最初的写法与下面的写法思路类似，也是先进行首位的判断，然后相同的情况再继续匹配剩下的，不过当时的匹配比较冗余，有很多不必要的东西，也不如现在的简洁。当提交之后的效率不尽人意，后来我就去看了jdk的源码进行了改进。

这边的2种写法里的2个内层的循环的写法，都是看了jdk的indexof源码后写出来的。后来在调试的时候，发现这个循环的执行时间和普通的循环不一样。

我这里的2种做法，一种是将字符串转成char数组进行比较，一种是从字符串里charat（）方法，截取char字符进行匹配。

但写出来最好的结果，仅仅是超过80%多的用户。

后面我去看了更多的答案。第一名是直接使用了jdk的indexof方法直接返回。

我再次去查看了indexof的源码，发现我的代码应该对比jdk源码的部分，算法的内容只应该有少没有多。唯一多的部分就是，indexof的源码进行匹配用的char数组就是string类里的数组，而我这里进行匹配用的数组，则是进行转存后的数组，所以效率不如原生indexof，并且string类的数组是私有的，我无法直接获取来判断，因此效率不如原生jdk的indexof方法。（虽然用反射可以，但如果用反射就失去了做算法的意义，而且效率未必会更高）。

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
/*
	 执行用时 : 4 ms, 在Implement strStr()的Java提交中击败了79.40% 的用户
	 内存消耗 : 35 MB, 在Implement strStr()的Java提交中击败了94.10% 的用户
	  */
	public static int strStr2(String haystack, String needle) {
		if (needle == null || needle.length() == 0) {
			return 0;
		}
		if (haystack == null) {
			return -1;
		}
		int r = -1;
		// 最大需要的长度
		int len = haystack.length() - needle.length();
		for (int i = 0; i <=len; i++) {
			
			if (haystack.charAt(i) != needle.charAt(0)) {
				while(++i <len && haystack.charAt(i) != needle.charAt(0)){}
			}
			int j = 0;
			for (; j < needle.length() && haystack.charAt(j + i) == needle.charAt(j); j++) {

			}
			if (j == needle.length()) {
				return i;
			}
		}
		return r;
	}
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
/* 
    * 执行用时 : 2 ms, 在Implement strStr()的Java提交中击败了88.79% 的用户 
    * 内存消耗 : 35 MB, 在Implement strStr()的Java提交中击败了93.61% 的用户
 * 
 */
public static int strStr(String haystack, String needle) {
	 if (needle == null || needle.length() == 0) {
			return 0;
		}
		if (haystack == null) {
			return -1;
		}

		int r = -1;
		// 最大需要的长度
		int len = haystack.length() - needle.length() + 1;
		char[] c = needle.toCharArray();
		char[] s = haystack.toCharArray();
		char top = c[0];

		for (int i = 0; i < len; i++) {
			while (top != s[i]) {
				if (i < len-1) {
					i++;
				} else {
					return -1;
				}
			}
			int j = 0;
			for (; j < c.length && s[j + i] == c[j]; j++) {

			}
			if (j == c.length) {
				return i;
			}
			// 匹配
		}
		return r;
}

Review 英文文章

https://spark.apache.org/

简单介绍了spark的使用

Tip 技巧

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

本周学习了该专栏中的17-20篇

学习了跳表以及散列的思想。

了解了散列可能出现的问题，如何提高效率等。

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

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

Share 分享

阿里 P9 级面试官是如何 360° 无死角考察候选人的？

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