看不见的bom

背景

旁边的童鞋被QA的bug报告快搞疯了。
原因是,很简单的一个逻辑,parse一个csv,然后对比各个项目,其中,第一个项目是serviceId的flag,如果这个flag不是1,我们把db中对应的flag设置成true。
但是明明这么很简单的一个逻辑,csv中的flag也是1,但是跑了之后db中的flag却不是true。这是为啥?

看不见的BOM

排除其他可能性之后再次观察这个csv,发现出现问题的记录就只有第一条。而这个servideId的flag出现在第一个位置,也就是说?会不会有可能有看不见的字符导致我们parse到的flag并不是1?

经验告诉我们,windows的一些编辑器默认会在文本文件前面插入看不见的BOM字符。

那会不会真的是存在BOM字符呢?

vim下查看并排除BOM

1
2
3
4
:set bomb?

> bomb
> nobomb

因为bom总是出现在文本第一个字符,所以简单的只是显示了是否存在。

当我们想要去除BOM的时候。

1
:set nobomb

即可。

后话

折腾浪费的时间最终就是转换成了经验。
希望以后遇到类似问题反应更快一点吧。

vim

Swap Nodes in Pairs

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[24] Swap Nodes in Pairs  

https://leetcode.com/problems/swap-nodes-in-pairs/description/

* algorithms
* Medium (45.98%)
* Total Accepted: 352.7K
* Total Submissions: 762.9K
* Testcase Example: '[1,2,3,4]'

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

 

Example:


Given 1->2->3->4, you should return the list as 2->1->4->3.

思路

这道题如果试图去用一大堆指针指向需要交换的节点以及之后的节点,然后迭代就会被弄晕。
最后还是试图使用递归的方法解决。

我们把这个问题分割称两个部分,其实就是首先交换先头两个节点,然后,去交换剩下来的链表。

我们让lists中,第一个节点为head,第二个节点为tail。

最终得到的结果无非就是tail->head->swap_pairs(tail.next)

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val)
# @val = val
# @next = nil
# end
# end

# @param {ListNode} head
# @return {ListNode}
def swap_pairs(head)
return head if head == nil || head.next == nil
tail = head.next
left = tail.next
tail.next = head
head.next = swap_pairs(left)
return tail
end

反思

变量太多把自己搞晕的时候,想想是否有简介的递归可以利用。

Merge K Sorted List

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
[23] Merge k Sorted Lists  

https://leetcode.com/problems/merge-k-sorted-lists/description/

* algorithms
* Hard (35.68%)
* Total Accepted: 444.4K
* Total Submissions: 1.2M
* Testcase Example: '[[1,4,5],[1,3,4],[2,6]]'

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:


Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

思路

我们已经有了merge-2-sorted-lists的解法,这道题只需迭代调用。

但是有个问题很关键,就是我们到底要合并多少次呢? 如果是每次把新的list合并到结果中,据说会超时。

这个时候的时间复杂度是2n + 3n + ... + kn = [(k+1)*k/2-1]*n = O(nk^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
def merge_k_lists(lists)
if lists.count == 0
return nil
end
if lists.count == 1
return lists[0]
end
if lists.count == 2
return merge_two_lists(lists[0], lists[1])
else
list = merge_k_lists(lists[1..-1])
return merge_two_lists(lists[0], list)
end
end

def merge_two_lists(l1, l2)
i = l1
j = l2
if l1 == nil
return l2 ? l2 : nil
elsif l2 == nil
return l1 ? l1 : nil
end
if l1.val > l2.val
head = l2
j = j.next
else
head = l1
i = i.next
end
current = head
while i && j
if i.val < j.val
current.next = i
i = i.next
else
current.next = j
j = j.next
end
current = current.next
end
while i
current.next = i
i = i.next
current = current.next
end
while j
current.next = j
j = j.next
current = current.next
end
return head
end

分治法解法

同样利用已经写好的merge-2-sorted-lists, 只不过这次通过两两合并来减少合并次数。
时间复杂度为时间复杂度为O(nk log(k))

最小堆排序解法

首先复习一下堆的概念。堆可以分为最小堆和最大堆。就最小堆来说,就是对于一棵二叉树,root节点总是保持最小。
任何父节点总是小于叶子节点。

最小堆主要有push和pop操作。

push: 将新元素插入到最后的叶子节点,并于父节点比较,如果小于父节点,则交换。如此循环直到遇到比自己小的父节点或者最后到root节点。

pop: 获取最小元素,由上往下比较左右两子节点,将子节点中较大的节点作为新的父节点,不断重复,直到叶子节点。

对于解决 merge-k-sorted-lists问题,我们可以先将k个list中的第一个元素组成一个堆。
每次取堆顶元素root,放入result中,然后把root.next插入到堆中。这样可以保证我们每次从堆顶获取的元素都是最小的。

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
class Solution {
public:
struct compNode {
bool operator()(ListNode *p, ListNode *q) const {
return p->val>q->val;
}
};

ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
ListNode *dummy = new ListNode(0), *tail = dummy;

for(int i=0; i<lists.size(); i++)
if(lists[i]) pq.push(lists[i]);

while(!pq.empty()) {
tail->next = pq.top();
tail = tail->next;
pq.pop();
if(tail->next) pq.push(tail->next);
}

return dummy->next;
}
};

反思

堆是一个陌生的数据结构。需要特别留意。

Generate Parentheses

题目

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
[22] Generate Parentheses  

https://leetcode.com/problems/generate-parentheses/description/

* algorithms
* Medium (56.57%)
* Total Accepted: 386.8K
* Total Submissions: 680.5K
* Testcase Example: '3'


Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.



For example, given n = 3, a solution set is:


[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

错误的漩涡

乍看这个题目,决定用递归解决。自己思考了一下,大概就是假设已经有生成的generateParenthesis(n-1)的结果,然后我们对所有的结果进行组合,大概有

1
2
3
"("+generateParenthesis(n-1)+")"
"()"+generateParenthesis(n-1)
generateParenthesis(n-1)+"()"

的形式。然后组成一个递归,当n=1的时候返回["()"]

提交结果,大错特错。比如,当n=3的时候,我们怎么样都无法获得类似(()())的形式。

正确的思考方法

其实正确的思考方法,想得到就是想得到,想不到就是背下来。

  1. 当”(“数小于n的时候,可以继续添加”(“

  2. 当”)”的个数小于”(“的个数的时候,可以添加”)”

于是我们可以新建一个方法来记录当前的结果,以及左右括号的计数,然后进行递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# @param {Integer} n
# @return {String[]}
def generate_parenthesis(n)
stack = []
generate(n,0,0,"",stack)
return stack
end

def generate(n, left, right, current, stack)
if left == n && right == n
stack << current
end
if left < n
generate(n, left+1, right, current+"(", stack)
end
if right < left
generate(n, left, right+1, current+")", stack)
end
end

插曲

在翻看答案的时候,第一眼看到了下面的解答。

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
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> allComb;
string comb;
findParenthesis(n, 0, 0, comb, allComb);
return allComb;
}

void findParenthesis(int n, int nleft, int nright, string &comb, vector<string> &allComb) {
if(nleft==n && nright==n) {
allComb.push_back(comb);
return;
}

if(nleft<n) {
comb.push_back('(');
findParenthesis(n, nleft+1, nright, comb, allComb);
comb.pop_back();
}

if(nright<nleft) {
comb.push_back(')');
findParenthesis(n, nleft, nright+1, comb, allComb);
comb.pop_back();
}
}
};

然后我陷入了沉思,最后的comb.pop_back()是为什么?
对比正解,我们发现我们在递归的时候改变了重复带入的变量的值,所以在下一次迭代之前,应该把它恢复。
至于为什么要恢复。。。撒。

你也许不需要图床

背景

使用hexo写博客已经有三四年了。
最困扰的问题依然是上传需要插入的contents的问题。

上传图片方式演化

由于hexo只是个静态博客生成器,
并不像wordpress那样有强大的contents管理功能,所有的contents我们只能通过上传到某个地方然后引用。
很显然,第一个被pass的解决方案是把图传到公共的图床上去。比如新浪微博或者七牛云存储。
前者类似盗链行为,后者复杂的流量收费计算方式实在是让人头疼。

我们的目标是,把所有的图片都放置在自己拥有管理权的地方。

自己host的图床工具

这是最早使用的解决方案。首先在github上找了个docker封装好的图床web app。然后挂到服务器上。
总体来说没什么大问题。每30分钟我都会备份一下docker container里面的图片。

1
30 * * * * /usr/bin/docker cp b7ceed2898de003e02b0addee90d0d50c63d046cd422d17dc5ba9085d44ea237:/usr/share/nginx/html/upload /data/pictshareuploads/upload/

但是后来服务器运营商MAINT停机的时候,我的docker就挂了。之前的图片虽然有作备份,现存的图姑且是全部救了回来,就是container重启之后不知道为啥UI什么的全部发生了变化,我也再也没有权限上传图片了。

当然花时间理清楚思路固然重要,不过对于我只想要简简单单解决上传图片的目的来说,显然有些多余了。

于是我把眼光转向了吱呀呀转动着的挂在自己家的NAS。

自宅NAS的复杂繁琐

QNAP这个NAS服务器真的是非常良心。不但免费提供了DDNS绑定,各种定制的contents管理工具也是十分便捷。
唯一让人头疼的是,当我们要上传图片并获取公链的时候,步骤太过于复杂。

  1. 打开FileStation, 然后选择上传。

  1. 选择上传的文件之后,点击共享,然后勾选永久共享。

  1. 获取共享链接之后,在共享链接的界面点开图片,获取真正的链接。然后复制到剪贴板。

更要命的是由于手动步骤太多导致很多时候直接就是贴错了图。

痛定思痛,我决定花点时间来解决传图的问题。目标是使用最短的时间上传任意大小的图片,并且减少操作的失误。

NGINX + SCP

这个方法的思路是。

  1. 获取本地图片/视频的md5。

  2. 用scp将本地图片上传到自己服务器的公开目录上,并重命名成”md5+extension”的名称。

  3. 拼接出图片的url,自动复制到剪贴板。

事先准备nginx的公开目录。

我们建立一个alias,把新建的目录挂到wwww.bocchi.tokyo/upload的path下面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
server {
listen 443 http2;

ssl on;
server_name www.bocchi.tokyo;
ssl_certificate /etc/letsencrypt/live/www.bocchi.tokyo/fullchain.pem;
ssl_certificate_key /etc/letsencrypt/live/www.bocchi.tokyo/privkey.pem;
root /var/www/myblog;
index index.html;

location / {
add_header Cache-Control max-age=0;
add_header Cache-Control no-store;
add_header Pragma no-cache;
#rewrite ^ https://$http_host$request_uri? redirect;
try_files $uri $uri/ =404;
}
location /upload/ {
alias /var/www/html/upload/;
}
}

本地写一个bash脚本,当执行hl my_image.jpg的时候,会把图片自动上传到公开目录并将合成的url复制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/bin/bash


md5=`md5 -q "$1"`
filename=$(basename -- "$1")
extension="${filename##*.}"

hashedName="$md5.$extension"

echo "file name is : $hashedName"

# cp $1 /tmp/$hashedName

scp "$1" gyorou@bocchi.tokyo:/var/www/html/upload/$hashedName

if [ $? -eq 0 ]; then
echo "https://www.bocchi.tokyo/upload/$hashedName" | pbcopy
echo "copied https://www.bocchi.tokyo/upload/$hashedName to clipboard"
else
echo FAIL
fi

当然为了在上传过程中不提示输入密码,ssh的无密码登陆也需要设置好。不过这个就略去不谈了。

试一下效果。

后记

看了一下现在服务器的容量,大概暂时是没有什么问题。
接下来可能会考虑把博客和邮箱完全扔到NAS上,彻底省去服务器的这笔开销吧。

3-sum-closest

问题

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
[15] 3Sum  

https://leetcode.com/problems/3sum/description/

* algorithms
* Medium (24.60%)
* Total Accepted: 631K
* Total Submissions: 2.6M
* Testcase Example: '[-1,0,1,2,-1,-4]'

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:


Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解析

和3-sum问题不一样的是,这次要寻找的不是三个数只和为0,而是最接近target的三个元素之和。

但是思路还是共通的。我们首先对nums进行排序,然后遍历排序好的数组sorted。

对于每个数组的元素sorted[i], 我们初始化左边界left为i+1,右边界为right-1。然后根据 sorted[i] + sorted[left] + sorted[right]和target的比较结果去移动边界。

我们初始化最小差距 min= sorted[0] + sorted[1] + sorted[2] - target

每当sorted[i] + sorted[left] + sorted[right] - target的绝对值小于min的绝对值,我们更新min。

每当sorted[i] + sorted[left] + sorted[right] - target > 0 说明三个数只和太大了,我们移动右边界减少三个数之和。

每当sorted[i] + sorted[left] + sorted[right] - target < 0 说明三个数只和太小了,我们移动左边界增加三个数之和。

sorted[i] + sorted[left] + sorted[right] - target == 0 那最好,我们直接返回target

当遍历完最后一个元素,我们返回min + target

解法

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
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def three_sum_closest(nums, target)
sorted = nums.sort
i = 0
min = sorted[0] + sorted[1] + sorted[2] - target
while i < sorted.length - 2
if i > 0 && sorted[i] == sorted[i-1]
i+=1
next
end
left = i+1
right = sorted.length - 1
while (left < right)
if (sorted[left] + sorted[right] + sorted[i] - target).abs < min.abs
min = sorted[left] + sorted[right] + sorted[i] - target
end
if sorted[left] + sorted[right] + sorted[i] - target > 0
right -=1
elsif sorted[left] + sorted[right] + sorted[i] - target < 0
left +=1
else
return sorted[left] + sorted[right] + sorted[i]
end
if left + 1 < right && sorted[left] == sorted[left+1]
left+=1
next
end
if right - 1 > left && sorted[right] == sorted[right-1]
right-=1
next
end
end
i += 1
end
return min + target
end

puts three_sum_closest([-1,0,1,1,55], 3)

反思

还好这题在每看结果的情况下通过了。为了二刷还是mark一下吧。

3-sum

题目

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
[15] 3Sum  

https://leetcode.com/problems/3sum/description/

* algorithms
* Medium (24.60%)
* Total Accepted: 631K
* Total Submissions: 2.6M
* Testcase Example: '[-1,0,1,2,-1,-4]'

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:


Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

思考

乍看题目的时候第一反应是先sort,说明已经步入正轨了。

然而自己最初的尝试是去固定两个数,寻找第三个数。然后根据第三个数去移动两边,结果没能很好处理边界问题。

正确解法的答案是固定一个数,然后去寻找另外两个数,遇到相同数字时候的处理方法,相对就比较直观简单了。

解法

首先进行sort。sort的时间复杂度是O(nlogn). 远远在暴力解法至少两层循环的log(n^3)之下。

sort之后,我们进行循环。对于每个元素sorted[i], 我们使用两边夹逼去寻找符合条件的sorted[left], sorted[right]

注意跳过重复的元素。

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
def three_sum(nums)
sorted = nums.sort
i = 0
j = sorted.length - 1
result = []
for i in 0..sorted.length - 3
next if (i > 0 && sorted[i] == sorted[i-1])
target = 0 - sorted[i]
left = i+1
right = sorted.length - 1
while (left < right)
a = sorted[left]
b = sorted[right]
if (a + b == target)
result << [a,b, sorted[i]].sort
while(sorted[left+1] == a && left < right)
left+=1
end
while(sorted[right-1] == b && left < right)
right -=1
end
left+=1
right-=1
elsif a+b < target
left +=1
else
right -=1
end
end
end
return result
end

Longest Common Prefix

这道题目其实非常简单。之所以要标记起来是因为发现自己很不擅长处理类似的边界。

问题

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

[14] Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/description/

* algorithms
* Easy (34.02%)
* Total Accepted: 530.8K
* Total Submissions: 1.6M
* Testcase Example: '["flower","flow","flight"]'

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:


Input: ["flower","flow","flight"]
Output: "fl"


Example 2:


Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.


Note:

All given inputs are in lowercase letters a-z.

思路

首先对字符串数组进行排序,找到最短的字符串,那么我们知道最长前缀子字符串的长度是不可能超过这个最短字符串长度的。
然后我们就开始遍历,对于最短字符串中的每个元素,我们遍历整个字符串数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longest_common_prefix(strs)
return "" if strs.empty?
sorted = strs.sort{|a| a.length}
i = 0
while i < sorted[0].length
a = sorted[0][i]
j = 0
while j < strs.length - 1
j+=1
return sorted[0][0...i] if sorted[j][i] != a
end
i += 1
end
return sorted[0]
end

后记

联想到生活中的一些目标,其实关键还是去分析自己缺乏什么解决问题的关键要素。
对症下药而不是盲目叠加自我满足感。

Minimum Window Substring 最小窗口子串

问题

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

https://leetcode.com/problems/minimum-window-substring/description/

* algorithms
* Hard (31.68%)
* Total Accepted: 267.2K
* Total Submissions: 841.8K
* Testcase Example: '"ADOBECODEBANC"\n"ABC"'

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:


Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"


Note:


If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

解析

据说窗口移动问题是疏通Array各种问题中的关键的关键。

这道Leetcode上难度为hard的题目显然就是传说中的不会做就是100年不会的题目。

看完别人的分析,我们来自己分析一下。

这个题目的核心就是,首先移动右边界,去寻找一个符合条件的字符串,记录下这个字符串的长度,然后移动左边界,直到去掉一个关键的字符,然后再试着移动右边界,去寻找一个比刚刚更短的符合条件的字符串。

详细来说,

首先,我们用一个hash来记录T中各个字符出现的次数。记做hash_t

那么例子中,我们获得的hash_t就是{a=>1, b=>1, c=>1}

接下来我们逐个遍历s中的每个字符,假设当前位置为i。每当我们遇到t中出现的字符,就将hash_t[s[i]]对应地减去1。

hash_t[s[i]]为0的时候,我们知道我们已经找到了符合要求的一个字符,所以我们可以另外用一个cnt,初始值为0,每当hash_t[s[i]]为0,我们就将cnt加上1。
同时,我们将hash_t[s[i]]减去1。

想想一下我们可能遇到hash_t[s[i]] 为负数的情况,但是这个也不要紧,这说明当前字符串s中已经有了多个在t中出现的相同字符。

当cnt等于t的长度,说明我们已经找齐了所有的t中的字符,这个时候可以将当前从左边界到右边界的字符串和目前已经知道的最短符合条件的字符串进行比较。

接下来,移动左边界left。当左边界的字符不在我们hash_t中的时候,我们不断移动左边界。当左边字符在hash_t中,我们将hash_t[s[left]]加上1。并将cnt减去1.
hash_t[s[left]]变为0以上,说明我们又缺乏了s[left],所以需要移动右边界去继续寻找。。。

Ruby 解法

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
def min_window(s, t)
hash_t = {}
t.split("").each do |c|
hash_t[c] ||=0
hash_t[c]+=1
end
cnt = 0
left = 0
min = 2**31 - 1
result = ""
for i in 0..s.length - 1
right = s[i]
if hash_t[right]
hash_t[right] -=1
cnt +=1 if hash_t[right] >= 0
end
while cnt == t.length
if min > i - left + 1
min = i - left + 1
result = s[left...left+min]
end
if hash_t[s[left]]
hash_t[s[left]] +=1
cnt -=1 if hash_t[s[left]] > 0
end
left +=1
end
end
return result
end

反思

刷题的话并不是要发明什么,所以百思不得其解的时候,去看一下答案还是有必要的。

如何把微信上传的M4a语音转换成iphone的闹铃音

背景

想让慧玲教我一下韩语的发音,于是我说你把这两个单词读一遍吧。

然后就有了以下。

哈哈太好听了,决定设置成闹铃~

可是应该怎么办呢?

方法

思路很简单,想方设法把音乐文件倒入itunes就行。

微信会自动把上传的语音文件转换为m4a格式,我们需要把m4a转换成itunes可以识别的格式,比如mp3。

各种意义,ffmpeg是我最喜欢的工具之一。

1
ffmpeg -i Delicious\ House.m4a -ab 256k huiling_alarm.mp3

转换好之后在itunes里面打开,连接上手机sync到手机上的itunes即可。

最后,在闹钟的设置里面,把默认的铃声换成目标铃声。

后话

生活的乐趣在于发现有意义的问题然后用所获取的知识去设计解决。