ARTS 第48周

发表于

ARTS （第48周）

如同认知世界，要先接近技术，才能学习到技术。

Algorithm 算法

字符串的排列

1
2
3
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1

每次将首位和其它位置更改，然后从下一位开始递归的解法。

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
public ArrayList<String> Permutation_(String str) {
		ArrayList<String> res = new ArrayList<String>();
		if (str == null || str.length() == 0) {
			return res;
		}
		res = PermutationHelp(str.toCharArray(), 0);
		// 未排序的 提交是错误的
		Collections.sort(res);
		return res;
	}

	private ArrayList<String> PermutationHelp(char[] chars, int idx) {
		ArrayList<String> res = new ArrayList<String>();
		int len = chars.length;
		if (len - idx == 1) {
			res.add(String.valueOf(chars[idx]));
		} else {
			for (int i = idx; i < len; i++) {
				// 避免重复
				if (i == idx || chars[idx] != chars[i]) {
					// 每次交换首位进行判断
					swap_(chars, idx, i);
					ArrayList<String> sub = PermutationHelp(chars, idx + 1);
					for (String s : sub) {
						res.add(String.valueOf(chars[idx]) + s);
					}
					swap_(chars, idx, i);
				}
			}
		}
		return res;
	}

	private void swap_(char[] c, int i, int j) {
		char t = c[i];
		c[i] = c[j];
		c[j] = t;
	}

解法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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// https://blog.csdn.net/qq_40688707/article/details/80430661
	// 参照里面的那个字典的字典序树 可以更好理解
	// 找到公共前缀 然后对后面字符做 swap 然后reverse
	// 这种解法 其实给我的感觉就是从数学公式的推导而来的算法
	// 如果按那个字典序树就类似于树的前序遍历（最初的时候，会只改变后2位，然后逐渐变成后第3位(第三位改变后，再改变后2位)，以次类推）
	// 每次都是向前查找第一个变小的元素（即方法里的l变量） 即获取最长的公共前缀 便于改变公共前缀后面的东西
	// 然后从后找最后一个比l大的元素 即r 这个数字是用来替换最高位的数字的
	// 然后r和l的位置交换，然后reverse(l到末尾)
	//
	// 如012543 会找到l=2 r=5 然后交换2和5 得出013542 然后reverse 变量l后面的字符 即013245
	public ArrayList<String> Permutation(String str) {
		ArrayList<String> res = new ArrayList<String>();
		if (str == null || str.length() == 0) {
			return res;
		}
		char[] cs = str.toCharArray();
		// Arrays.sort(cs);
		// res.add(String.valueOf(cs));
		while (true) {
			int l = cs.length - 1;
			// 向前查找第一个变小的元素 即最长的公共前缀 然后改变公共前缀后面的东西
			while (l >= 1 && cs[l - 1] >= cs[l]) {
				l--;
			}
			if (l == 0)// 这种情况 就是有序度为0 例如12345已经变成了54321 即字典序树最后一种情况的时候
				break;

			int r = l;
			// 从l向后查找最后一个变大的元素
			while (r < cs.length && cs[r] > cs[l - 1]) {
				r++;
			}
			// 交换 r和l 然后反转l之后的东西
			// 例如12345 可以变成12354
			swap(cs, l - 1, r - 1);
			reverse(cs, l);

			res.add(String.valueOf(cs));
		}
		return res;
	}

	private void reverse(char[] chars, int k) {
		if (chars == null || chars.length <= k)
			return;
		int len = chars.length;
		for (int i = 0; i < (len - k) / 2; i++) {
			int m = k + i;
			int n = len - 1 - i;
			if (m <= n) {
				swap(chars, m, n);
			}
		}

	}

	private void swap(char[] c, int i, int j) {
		char t = c[i];
		c[i] = c[j];
		c[j] = t;
	}

数组中出现次数超过一半的数字

1
2
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 排序法

因为多了个不满足条件的判断，所以需要一轮额外的循环

还可以用map记录每种数字出现次数的暴力法等，这种写法比较简单，这里我就不写了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int MoreThanHalfNum_Solution_(int[] array) {
		if (array == null || array.length == 0)
			return 0;
		Arrays.sort(array);
		// 找出排序后的中位数
		int res = array[array.length / 2];
		int count = 0;
		for (int i : array) {
			if (i == res)
				count++;
		}
		// 判断出现次数是否大于一半
		return count > (array.length / 2) ? res : 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
// 摩尔投票法
	
	public int MoreThanHalfNum_Solution(int[] array) {
		if (array == null || array.length == 0)
			return 0;
		int res = 0;
		int n = 0;
		for (int val : array) {
			if (n == 0) {
				n++;
				res = val;
			} else if (res == val) {
				n++;
			} else {
				n--;
			}

		}
		// 一样的验证
		int count = 0;
		for (int i : array) {
			if (i == res)
				count++;
		}
		// 判断出现次数是否大于一半
		return count > (array.length / 2) ? res : 0;
	}

最小的K个数

1
2
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 排序法

构建堆的思路 其实和这里是一样的，也是排序后获取前n个

1
2
3
4
5
6
7
8
9
10
11
12

// 还可以用堆的结构 其实思路是类似的，这里我就不写了
public ArrayList<Integer> GetLeastNumbers_Solution_(int[] input, int k) {
	ArrayList<Integer> res = new ArrayList<Integer>();
	if (input == null || input.length == 0 || k > input.length)
		return res;
	Arrays.sort(input);
	for (int i = 0; i < k; i++) {
		res.add(input[i]);
	}
	return res;
}

解法2 使用快排的部分算法 通过找出基准点 当基准点是k的时候，就代表前k个数字已经选出来了。

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 ArrayList<Integer> GetLeastNumbers_Solution__(int[] input, int k) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if (input == null || input.length == 0 || k > input.length)
			return res;
		int s = 0;
		int e = input.length - 1;
		int p = qucik(input, s, e);
		while (p != k - 1) {
			if (p > k - 1) {
				e = p - 1;
				p = qucik(input, s, e);
			} else {
				s = p + 1;
				p = qucik(input, s, e);
			}
		}
		for (int i = 0; i < k; i++) {
			res.add(input[i]);
		}
		Collections.sort(res);
		return res;
	}

	public int qucik(int[] arr, int s, int e) {
		int pivot = arr[s];// 基准点
		while (e > s) {
			// 从最右边开始 查找第一个小于基准点的数值
			while (e > s && arr[e] >= pivot) {
				e--;
			}
			// 找到后，首次覆盖基准点，后续则覆盖下个循环里找到的点
			// 如果未找到 则s==e
			arr[s] = arr[e];
			// 从右边查找第一个大于基准点的数值
			while (e > s && arr[s] <= pivot) {
				s++;
			}
			// 找到后，覆盖前一个循环里找到的点
			// 如果未找到 则s==e
			arr[e] = arr[s];
		}
		arr[s] = pivot;
		return e;
	}

解法3 部分选择排序

非完整选择排序，仅循环k次，即时间复杂度为k*n

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 ArrayList<Integer> GetLeastNumbers_Solution___(int[] input, int k) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if (input == null || input.length == 0 || k > input.length || k <= 0)
			return res;
		// 找出前K个最小 选择排序
		for (int i = 0; i < k; i++) {
			int min = i;// 最小坐标
			for (int j = i + 1; j < input.length; j++) {
				// 遍历找出最小
				if (input[min] > input[j]) {
					min = j;
				}
			}
			// 将最小的和i进行对换
			int temp = input[i];
			input[i] = input[min];
			input[min] = temp;
		}
		for (int i = 0; i < k; i++) {
			res.add(input[i]);
		}
		return res;

	}

解法4 选择排序混合解法

在n和k差距较大的时候，有一定程度的优化，最差情况等于n^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
45
// 看了题解 一个从选择排序改进来的混合的解法 复杂度从变成(n^2)变成了((n-k)^2+k^2)
	// 在n和k差距较大的时候，有一定程度的优化，最差情况等于n^2
	public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if (input == null || input.length == 0 || k > input.length || k <= 0)
			return res;
		// 给前k个数字排序 这里用上一个解法里的选择排序
		for (int i = 0; i < k; i++) {
			int min = i;// 最小坐标
			for (int j = i + 1; j < k; j++) {
				// 遍历找出最小
				if (input[min] > input[j]) {
					min = j;
				}
			}
			// 将最小的和i进行对换
			int temp = input[i];
			input[i] = input[min];
			input[min] = temp;
		}

		for (int i = k; i < input.length; i++) {
			// 这里其实是插入排序
			int temp = input[i];// 缓存
			int j = i - 1;// 和之前的数比较
			for (; j >= 0; j--) {
				// 若当前j坐标的数字更小,则往后挪一位
				if (input[j] > temp) {
					input[j + 1] = input[j];
				} else {
					break;
				}

			}
			// 将缓存的数值插入到合适的位置
			input[j + 1] = temp;

		}

		for (int i = 0; i < k; i++) {
			res.add(input[i]);
		}
		return res;

	}

连续子数组的和

1
2
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=11183&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int FindGreatestSumOfSubArray_1(int[] array) {
		if (array == null || array.length == 0)
			return 0;
		int res = array[0];
		int[] dp = new int[array.length];
		dp[0] = array[0];
		for (int i = 1; i < dp.length; i++) {
			if (dp[i - 1] >= 0) {
				dp[i] = dp[i - 1] + array[i];
			} else {
				dp[i] = array[i];
			}
			if (dp[i] > res)
				res = dp[i];
		}

		return res;
	}

解法2 动态规划优化

其实这题做过，最先想到的是这种写法，本质也是动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int FindGreatestSumOfSubArray_(int[] array) {
		if (array == null || array.length == 0)
			return 0;
		int res = array[0];
		int sum = 0;
		for (int num : array) {
			if (sum > 0) {
				sum += num;
			} else {
				sum = num;
			}
			if (sum > res)
				res = sum;
		}
		return res;
	}

解法3 递归分治

偶然想起这题在哪里看到过，有一个分治写法，就去找了找思路写了出来，

将每个序列都分成不包含中点的左序列或右序列，以及包含中点的序列，然后递归从查找。

这种思路是好的，将大问题拆成小问题进行查找，但是这题有更好的解法。如动态规划。

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
// 分治辅助
	public int FindGreatestSumOfSubArray_Help(int[] nums, int left, int right) {
		if (left == right)
			return nums[left];

		int mid = (left + right) / 2;
		// 从中点拆分成左、右 以及从中点延伸
		int leftSum = FindGreatestSumOfSubArray_Help(nums, left, mid);
		int rightSum = FindGreatestSumOfSubArray_Help(nums, mid + 1, right);
		int midSum = FindGreatestSumOfSubArray_Help_GedMiddle(nums, left, right, mid);

		return Math.max(Math.max(leftSum, rightSum), midSum);
	}

	// 分治
	public int FindGreatestSumOfSubArray(int[] array) {
		if (array == null || array.length == 0)
			return 0;
		return FindGreatestSumOfSubArray_Help(array, 0, array.length - 1);
	}

	public int FindGreatestSumOfSubArray_1(int[] array) {
		if (array == null || array.length == 0)
			return 0;
		int res = array[0];
		int[] dp = new int[array.length];
		dp[0] = array[0];
		for (int i = 1; i < dp.length; i++) {
			if (dp[i - 1] >= 0) {
				dp[i] = dp[i - 1] + array[i];
			} else {
				dp[i] = array[i];
			}
			if (dp[i] > res)
				res = dp[i];
		}

		return res;
	}

整数中1出现的个数

1
2
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1暴力法

优点是思路简单，缺点是时间复杂度n，而且会创建n个string类型的变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 暴力法
	public int NumberOf1Between1AndN_Solution_(int n) {
		if (n <= 0)
			return 0;
		int count = 0;
		for (int i = 1; i <= n; i++) {
			String num = i + "";
			for (int j = 0; j < num.length(); j++) {
				if (num.charAt(j) == '1')
					count++;
			}
		}
		return count;
	}

解法2 题解里看到的解法

归纳特征，然后整合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int NumberOf1Between1AndN_Solution(int n) {
		    int cnt = 0;
		    for (int m = 1; m <= n; m *= 10) {
		        int a = n / m;//除数
		        int b = n % m;//余数
		        // 这里先忽略+8,a/10就是把当前位数当成个位数,判断一共出现多少个1（每10个数字出现一个1）,
		        // +8是考虑到如112这种情况，如果直接除以10，就丢失了111这个数字的个位。
		        // 因此+8,但不能+9,因为如111这种情况,+1就会导致多计算一个数字，所以末尾是1 的情况额外判断考虑，即后面的变量d
		        // 然后乘以m，就是乘以当前位数 ，
		        // 当考虑到非个位，如100，把100的个位舍去（除以10），然后用10除以10，得出结果1，因为这个结果是除以了10的，所以这里要再乘以10（如100里十位出现的次数是10次）
		        // 
		        int c = (a + 8) / 10 * m;
		        //这里考虑的是末尾数是1 的情况，如111 这个数字,因为上面的计算,只有加了8,就需要额外判断,即如果尾数是1，就进行加1.
		        //然后如果有余数,有多少个余数就会额外出现多少个1  如1515这样的数字 再计算到最后千位的时候，c就会是0，因为数字只剩下1，不整除了
		        //然后要计算千位上出现的次数 1001~1515即515，然后再计算1000这个数字的1次（末尾等于1的情况） 所以要+1 = 516次
		        int d = (a % 10 == 1 ? b + 1 : 0);
		        //然后与之相对应的如2515这种情况，千位的时候，因为（2+8）/1000= 1 ，然后乘以1000，即出现1000次（1000~1999）
		        cnt += c + d;
		    }
		    return cnt;
		}

解法3数学公式归纳

参考自 https://www.jianshu.com/p/109fce1289e6

数学公式归纳

1
2
3
4
5
6
7
8
9
10
11
12
13
// 数学归纳
	public int NumberOf1Between1AndN_Solution1(int n) {
		if (n <= 0)
			return 0;
		int count = 0;
		for (long i = 1; i <= n; i *= 10) {
			
			long diviver = i * 10;
			long val = n % diviver - i + 1;
			count += (n / diviver) * i + Math.min(Math.max(val, 0), i);
		}
		return count;
	}

Review 英文文章

http://kafka.apache.org/quickstart

kafka 的helloword

Tip 技巧

一、第一阶段“不知道自己不知道”，也就是无知，人所处的盲区。比如，我们以前在管理孩子时，认为要给孩子指出问题，让他改正才是对孩子的负责，因此我们不断看到孩子的问题并指出来。结果问题永远改不完，还导致孩子和家长对着干。我们以为家长已经尽力了，孩子就是不懂事不理解大人的良苦用心，其实这就是家长处在了管教孩子的无知盲区之中，不知道自己因为方法不当错误的管教孩子，还以为己做的很对。再比如你吃完饭脸上粘上一颗米粒，你没照镜子也没有和说的，你不知道，可能还觉得自己很美、到处炫耀你的靓丽呢。我上高一时不知道什么是“相对论”，但还和同学辩论的津津有味，现在想来真可笑。当自己不知道自己的无知时，看到的是别人做的不对，自己不会改正错误，也无从下手改正。

无知的原因受个人成长、家庭、文化的影响。例如，从孩子的问题入手管教孩子，是从家族的管理模式中学来的。有人说：“只有人家夸你的孩子好，哪有自己夸自家孩子好的，把他夸骄傲了怎么办。”这就是她的谦虚的传统认知，实际上她不知道现在很多父母以夸孩子为主。再比如一家人吃饭，是谁有空谁吃还是人凑齐了一起吃，不同的家庭有不同的习惯。我们在公共场合的大声喧哗，不出国门你不知道有些文明与我们很不同。

二、当别人帮你指出来，通过观察学习发现自己无知时，你就进入了“知道自己不知道”的阶段，开始有了自知。人贵有自知之明，当我们知道自己无知时，也就能谦虚向他人学习了。比如，当孩子出现不努力学习的问题时，我知道我的管理方法有问题了，我止住我原来的错误做法，开始走向新的学习之路。

三、当我们不断的学习，向他人请教，我们逐渐知道了很多知识，就进入了“知道自己知道”的觉察状态，能时刻反思自己的做法是否正确有效。比如我在管教孩子时，我对孩子的行为不满，一旦采取了打骂指责的办法，我当即觉察到这个办法无效且有害，立即止住、调整思维方向，发现孩子积极正向的动机，满足孩子的心理价值需要，向孩子表达我的感觉，孩子的行为就自动转化了。再比如，当我遇到困难时，一旦出现心烦气躁、抱怨他人的现象，立即觉察到这个方向无效，迅速止住、改变模式，改为我做些什么就能有所变化，只要做就有改变的可能，然后全力以赴去行动。

四、随着我们不断的觉察，不断的应用知道的知识做出行动，最后形成了习惯。不需要思考，大脑便自动自发的按新形成的模式去做，这就便进入了“不知道自己知道的”状态，形成了习惯成。比如，当我们已经习惯对他人欣赏认可时，“对”、“很好”会随时从嘴里冒出。我们学会开车后，在路上开车不会仔细考虑怎么加油门、刹车、打方向等，开车操作已经成了一种无意识运作。

我们认识新事物，学习新知识，就是不断的从无知到自知，再到觉察，最后形成习惯的过程。一个人首先让他觉察到自己的无知，才能走向自知，改变就有了可能。但从“知道”到“做到”也是一个相当难的过程，长期形成的模式很容易反复，需要不断的觉察、改变，持之以恒的坚持去做，才能逐渐形成习惯。

摘自 https://www.jianshu.com/p/ca8d65bf4094

Share 分享

https://blog.csdn.net/zhujianlin1990/article/details/60756448 zookeeper 因为hostname不匹配 导致的缓慢问题

https://www.zhihu.com/question/291554395 爬虫究竟是合法还是违法的？

https://www.jianshu.com/p/109fce1289e6 剑指offer最优解Java版-整数中1出现的次数（从1到n整数中1出现的次数）

https://www.jianshu.com/p/ca8d65bf4094 自我认识的四个阶段

https://blog.csdn.net/happyrocking/article/details/83619392 字典序算法详解