• 每周算法:拨号键盘上的字符组合

    Description

    Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

    A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

    1 2abc 3def
    4ghi 5jkl 6mno
    7pqrs 8tuv 9wxyz

    Example:

    Input: "23"
    Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    

    Note:
    Although the above answer is in lexicographical order, your answer could be in any order you want.

    来源:leetcode 17 letter combinations of a phone number

    Solution

    Approach 1

    借助加法计算进位的思想,下面是我的解法。我首次提交时并没有注意输入字符串为空的情况,对于输入参数的检查还是太容易忽略了。

    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        if (digits.empty()) {
    	return ans;
        }
    
        vector<string> letters {"",  "", "abc", "def", "ghi",
    	    "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<int> carry(nums.size(), 0);
        vector<int> nums;
        for (char ch : digits) {
    	int n = ch - '0';
    	nums.push_back(n);
        }
    
        do{
    	string str;
    	for (size_t i=0; i<carry.size(); ++i) {
    	    str += letters[nums[i]] [carry[i]];
    	}
    	ans.push_back(str);
    
    	int c = 1;
    	for (int i=carry.size()-1; i >= 0; --i) {
    	    int d = carry[i] + c;
    	    if (d >= letters[nums[i]].size()) {
    		carry[i] = 0;
    		c = 1;
    	    }
    	    else {
    		carry[i] = d;
    		c = 0;
    		break;
    	    }
    	}
    
    	if ( 1 == c) {
    	    break;
    	}
    
        } while (1);
    
        return ans;
    }
    

    我在想的是这个算法的时间复杂度是多少,感觉它的时间复杂度应该是O(n2)。

    Approach 2 recursive

    使用递归完成字符串的拼接,在每次递归,都会增加一个字符。终止递归的条件是字符串长度达到输入参数的长度。递归方法符合生活中的使用场景,还是比较容易理解的。

    class Solution {
        char mMap[8][4] = {
    	{'a', 'b', 'c', '#'},
    	{'d', 'e', 'f', '#'},
    	{'g', 'h', 'i', '#'},
    	{'j', 'k', 'l', '#'},
    	{'m', 'n', 'o', '#'},
    	{'p', 'q', 'r', 's'},
    	{'t', 'u', 'v', '#'},
    	{'w', 'x', 'y', 'z'},
        };
    
    public:
        vector<string> letterCombinations(string digits) {
    	vector<string> result;
    	backTrack(digits, result, "", 0);
    	return result;
        }
    
        void backTrack(string &digits, vector<string> &result, string combination, int index) {
    	if (index >= digits.length()) {
    	    if (combination.empty()) {
    		return;
    	    }
    	    result.push_back(combination);
    	    return;
    	}
    	for (char c : mMap[digits[index] - '2']) {
    	    if (c == '#')
    		continue;
    
    	    combination += c;
    	    backTrack(digits, result, combination, index+1);
    
    	    // 这里为什么要删去最后一个呢?
    	    // 因为之前在尾部追加了一个c
    	    combination.erase(combination.end() - 1);
    	}
        }
    };
    

    如何评估递归算法的时间复杂度和空间复杂度呢?

    Approach 3 BFS

    宽度优先搜索,breadth-first search(BFS),是一种对树(tree)或图(graph)的遍历算法,下面就是这种算法的解法,代码使用java编写。

    public List<String> letterCombinations(String digits) {
        LinkedList<String> ans = new LinkedList<String>();
        if(digits.isEmpty()) {
    	return ans;
        }
    
        String[] mapping = new String[] {"0", "1", "abc", "def",
    				     "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
        ans.add("");
        for(int i=0; i<digits.length(); i++) {
    	int x = Character.getNumericValue(digits.charAt(i));
    
    	while(ans.peek().length() == i) {
    	    String t = ans.remove(); // remove是从头部删去一个元素
    	    for(char s : mapping[x].toCharArray()) {
    		ans.add(t+s); // add是向尾部添加一个元素
    	    }
    	}
        }
        return ans;
    }
    

    下面是另外一种使用BFS算法实现的解法

    public List<String> letterCombinations(String digits) {
        LinkedList<String> ans = new LinkedList<String>();
        if(digits.isEmpty()) {
    	return ans;
        }
        String[] mapping = new String[] {"0", "1", "abc", "def",
    				     "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ans.add("");
        while(ans.peek().length() != digits.length()){
    	String remove = ans.remove();
    	String map = mapping[digits.charAt(remove.length())-'0'];
    	for(char c: map.toCharArray()){
    	    ans.addLast(remove+c);
    	}
        }
        return ans;
    }
    
  • 每周算法:最接近的三数之和

    Description

    Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    Example:

    Given array nums = [-1, 2, 1, -4], and target = 1.
    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
    

    来源:leetcode 16 3um closest

    Solution

    Approach 1

    这道题与之前的“3Sum”十分类似,做起来思路是非常相似的,最容易想到的就是暴力解法,穷举出所有的组合,进而找出最接近的。

    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3) {
    	return 0;
        }
    
        int ans = nums[0] + nums[1] + nums[2];
        int diff = abs(target - ans);
    
        // 穷举出所有的组合,与target比较,找到最接近的
        for (int i=0; i < nums.size(); ++i) {
    	for (int j=i+1; j < nums.size(); ++j) {
    	    for (int k=j+1; k < nums.size(); ++k) {
    		int sum_t = nums[i] + nums[j] + nums[k];
    		int diff_t = abs(target - sum_t);
    
    		ans = diff_t < diff ? (diff = diff_t, sum_t) : ans;
    
    		if (ans == target) {
    		    return ans;
    		}
    	    }
    	}
        }
    
        return ans;
    }
    

    Approach 2

    套用之前“3Sum”的O(n2)解法,下面的解法也是很容易想到的。

    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3) {
    	return 0;
        }
    
        sort(nums.begin(), nums.end());
    
        int ans = nums[0] + nums[1] + nums[2];
        int diff = abs(target - ans);
    
        for (int i=0; i < nums.size(); ++i) {
    	int n1 = nums[i];
    	int front = i + 1;
    	int end = nums.size() - 1;
    
    	while (front < end) {
    	    int n2 = nums[front];
    	    int n3 = nums[end];
    	    int sum = n1 + n2 + n3;
    	    int diff_t = abs(target - sum);
    
    	    if (diff > diff_t) {
    		ans = sum;
    		diff = diff_t;
    	    }
    
    	    if (sum == target) {
    		return sum;
    	    }
    	    else if (sum > target) {
    		--end;
    	    }
    	    else {
    		++front;
    	    }
    	}
        }
    
        return ans;
    }
    
  • 在shell中使用正则表达式

    引言

    本篇文章主要是针对shell中的 grepegrep 的讲解,对于正则表达式的规则本身并没有太多的内容。在阅读本篇文章之前,读者应该对正则表达式有个大致的了解。

    grep 命令

    grep 命令是linux终端中最常用的命令之一,它的全称是“global regular expression print”,从字面上理解, grep 可以用来进行正则表达式匹配。

    常用选项
    使用一些选项命令能够更加方便地进行匹配
    -i 忽略大小写
    -v 进行逆向匹配
    -n 打印行号
    --color=auto 彩色输出结果

    支持的表达式
    正则表达式有很多规则, grep 支持的有如下:
    在每一行的开始

    grep "^GUN" GPL-3
    

    在每一行的结尾

    grep "and$" GPL-3
    

    匹配任意字符

    grep "..cept" GPL-3
    

    在指定的字符中进行匹配

    grep "t[wo]o" GPL-3
    

    在指定的字符中进行逆向匹配

    grep "[^c]ode" GPL-3
    

    使用范围来指定字符

    grep "^[A-Z]" GPL-3
    

    限定出现的次数为0次或0次以上

    grep "([A-Za-z ]*)" GPL-3
    

    egrep 命令

    egrep 的含义为“extended grep”,相对于 grep 有更多的正则表达式特性。同样,可以在使用 grep 时增加 -E 参数获得相同的效果。

    表达式分组
    使用括号能够将表达式进行分组,下面的任何一个都能够实现这个效果

    grep "\(grouping\)" file.txt
    grep -E "(grouping)" file.txt
    egrep "(grouping)" file.txt
    

    表达式进行中多选一

    egrep "(GPL|General Public License)" GPL-3
    

    匹配的重复次数为0次或0次以上,与 * 限定符类似,但是 ? 可以作用于一组字符

    egrep "(copy)?right" GPL-3
    

    指定匹配的重复次数

    egrep "[AEIOUaeiou]{3}" GPL-3
    
  • 线程与进程的比较

    进程与线程之间有什么区别

    进程(process)是指在系统中正在运行的一个应用程序,是系统资源分配的基本单位,在内存中有其完备的数据空间和代码空间,拥有完整的虚拟空间地址。一个进程所拥有的数据和变量只属于它自己。

    线程(thread)是进程内相对独立的可执行单元,所以也被称为轻量进程(lightweight processes)。线程是操作系统进行任务调度的基本单元,它与父进程的其它线程共享该进程所拥有的全部代码空间和全局变量,但拥有独立的堆栈(即局部变量对于线程来说是私有的)。

    进程和线程都具有就绪、阻塞和运行三种基本状态。

    联系

    • 一个进程至少拥有一个线程(主线程),也可以拥有多个线程
    • 一个线程必须有一个父进程,多个进程可以并发执行
    • 一个线程可以创建和撤销另一个线程
    • 同一个进程中的多个线程之间可以并发执行

    区别

    系统开销:在创建或撤消进程时,由于系统都要为之分配和回收资源,导致系统的开销明显大于创建或撤消线程时的开销
    资源管理:进程有独立的地址空间,一个进程崩溃后,在保护模式下不会对其它进程产生影响,而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量,但线程之间没有单独的地址空间,一个线程死掉就等于整个进程死掉,所以多进程的程序要比多线程的程序健壮,但在进程切换时,耗费资源较大,效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作,只能用线程,不能用进程。

    通信方式

    进程间通信主要包括管道、系统IPC(包括消息队列,信号量,共享存储)、SOCKET,具体说明参考linux进程间通信方式。进程间通信其实是指分属于不同进程的线程之间的通讯,所以进程间的通信方法同样适用于线程间的通信。但对于同一进程的不同线程来说,使用全局变量进行通信效率会更高。

    什么情况下适合使用线程

    线程相对于进程的优势:

    • 线程间通信(数据交互)比进程间通信更加简便快捷。
    • 线程之间的上下文切换速度要比进程间的快,也就是说,对于操作系统而言,停止一个线程并启动另一个线程的速度比进程之间相似操作更快。
    • 创建一个线程的速度比创建一个进程的速度快。

    下面的一些情景更适合使用线程来完成:

    • 进行耗时较长的处理:当一个windows界面程序正在计算时,它就不能处理其他消息(message)了,界面就不能及时更新。
    • 进行后台处理:有些任务并不是时间紧迫的,但是需要定期执行。
    • 进行 I/O 处理: I/O 操作或网络操作一般都会有一定的延迟,线程能保证程序中的其他部分不会受到延迟的影响。

    什么情况下适合使用进程

    进程相对于线程的优势:

    • 多线程系单进程的软件只能运行在一台机器上,而多进程的软件可以运行在多台机器上。这在一定程度上限制软件的可拓展性,单台机器的性能总是有限的。
    • 多进程模型的鲁棒性更好,有更好的容错性。运行在同一进程下的多个线程会相互影响,如果其中的一个线程出了问题,可能会波及整个进程。
    • 有些功能模块并不是线程安全的,这时就只能使用多进程模型了。

    以chrome浏览器为例,它使用了多进程模型。每一个标签页都是一个进程,这样能够将渲染引擎中的bug隔离在该进程内,从而使整个程序免受影响。多进程模型将JavaScript隔离在每个进程中,这样就能防止其因占用过多的CPU或内存,使整个软件失去响应。另一方面,多进程模型的系统开销也是比较大的,这点能够从chrome的高额内存使用中看出来。不过chrome的优化策略可以让较低内存的情况下有更好内存使用效率。当一个标签页处于非激活状态,其对应的内存可以在需要时被交换进硬盘中,这样用户当前操作的页面就能够保持响应状态。如果使用的是多线程模型,区分活跃内存和非活跃内存就变得十分困难,导致内存使用效率的下降。

  • 每周算法:三数之和

    Description

    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]
    ]
    

    来源:leetcode.com 15 3Sum

    Solution

    Approach 1

    这道题有点难度,第一时间没有什么思路。我想到的主要问题是如何保证返回结果中不包含重复的一组数。如果使用暴力解法,将所有满足条件的组合取到后进行重复性清洗,应该是一种可行的解法,只是这样做时间复杂度有点高。

    下面的代码就是暴力解法的实现。不出意外,在leetcode中结果为超时。这种算法的时间复杂度为 O(n^3 * nlogn) + O(n^2)

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        for (size_t i=0; i<nums.size(); ++i) {
    	int n1 = nums[i];
    	for (size_t j=i+1; j<nums.size(); ++j) {
    	    int n2 = nums[j];
    	    for (size_t k=j+1; k<nums.size(); ++k) {
    		int n3 = nums[k];
    		if (n1 + n2 + n3 == 0) {
    		    vector<int> triplet{n1, n2, n3};
    		    sort(triplet.begin(), triplet.end());
    		    ans.push_back(triplet);
    		}
    	    }
    	}
        }
    
        // 将结果中的重复组合删掉
        for (vector<vector<int>>::iterator it1 = ans.begin();
    	 it1 != ans.end(); ++it1) {
    	for (vector<vector<int>>::iterator it2=it1+1; it2!=ans.end();) {
    	    if (*it1 == *it2) {
    		it2 = ans.erase(it2);
    	    }
    	    else {
    		++it2;
    	    }
    	}
        }
    
        return ans;
    }
    

    从上面这个解法中,我能够得到的 教训 经验是对 vector 进行具有删除操作的循环时,使用迭代器完成更不容易出错。我之前的去重逻辑是这样的。

    for (int i=0; i<ans.size(); ++i) {
        for (int j=i+1; j<ans.size(); ++j) {
    	if (ans[i] == ans[j]) {
    	    ans.erase(ans.begin() + j);
    	}
        }
    }
    

    很显然,上面的代码在一些情况下并不能彻底删去所有重复的元素,下面的代码才是真正正确的实现。

    for (int i=0; i<ans.size(); ++i) {
        for (int j=i+1; j<ans.size();) {
    	if (ans[i] == ans[j]) {
    	    ans.erase(ans.begin() + j);
    	}
    	else {
    	    ++j;
    	}
        }
    }
    

    Approach 2

    我认为这到题的主要难点啊主要是在去除重复的问题上。下面的解法来自 leetcode ,在处理重复性问题时,在匹配答案时将重复的数字跳过,这样就不用在后续的结果中进行剔除重复元素的步骤了。

    vector<vector<int> > threeSum(vector<int> &num) {
    
        std::sort(num.begin(), num.end());
    
        vector<vector<int> > res;
        for (int i = 0; i < num.size(); i++) {
    
    	int target = -num[i];
    	int front = i + 1;
    	int back = num.size() - 1;
    
    	while (front < back) {
    
    	    int sum = num[front] + num[back];
    
    	    // Finding answer which start from number num[i]
    	    if (sum < target)
    		front++;
    
    	    else if (sum > target)
    		back--;
    
    	    else {
    		vector<int> triplet = {num[i], num[front], num[back]};
    		res.push_back(triplet);
    
    		// Processing duplicates of Number 2
    		// Rolling the front pointer to the next different number forwards
    		while (front < back && num[front] == triplet[1])
    		    ++front;
    	    }
    	}
    
    	// Processing duplicates of Number 1
    	while (i + 1 < num.size() && num[i + 1] == num[i])
    	    ++i;
        }
    
        return res;
    }
    

    上面的代码中,只需要跳过 front 所对应的数字就好,因为 back 对应的数字会自然地随 front 变化而变化。

  • 每周算法:罗马数字转阿拉伯数字

    Description

    Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

    Symbol       Value
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000
    

    For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII , which is simply X + II . The number twenty seven is written as XXVII , which is XX + V + II .

    Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII . Instead, the number four is written as IV . Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX . There are six instances where subtraction is used:

    I can be placed before V (5) and X (10) to make 4 and 9.
    X can be placed before L (50) and C (100) to make 40 and 90.
    C can be placed before D (500) and M (1000) to make 400 and 900.
    Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

    Example 1:

    Input: "III"
    Output: 3
    

    Example 2:

    Input: "IV"
    Output: 4
    

    Example 3:

    Input: "IX"
    Output: 9
    

    Example 4:

    Input: "LVIII"
    Output: 58
    Explanation: C = 100, L = 50, XXX = 30 and III = 3.
    

    Example 5:

    Input: "MCMXCIV"
    Output: 1994
    Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
    

    来源:leetcode 13 roman to integer

    Solution

    Approach 1

    这道题不是很难,很容易就能想到解法,需要注意好边界条件问题,下面就是我的解法。

    pint romanToInt(string str) {
        int ans = 0;
        int pos = 0;
        const int len = str.length();
    
        // 千位
        while (pos < len && str[pos] == 'M') {
    	++pos;
        }
        ans += 1000 * pos;
        if (pos == len) {
    	return ans;
        }
    
        // 百位
        switch (str[pos]) {
        case 'C':
    	ans += 100;
    	++pos;
    
    	if (str[pos] == 'D') {
    	    ans += 300;
    	    ++pos;
    	}
    	else if (str[pos] == 'M') {
    	    ans += 800;
    	    ++pos;
    	}
    	else {
    	    while (pos < len && str[pos] == 'C') {
    		ans += 100;
    		++pos;
    	    }
    	}
    	break;
    
        case 'D':
    	ans += 500;
    	++pos;
    	while (pos < len && str[pos] == 'C') {
    	    ans += 100;
    	    ++pos;
    	}
    	break;
    
        default:
    	break;
        }
        if (pos == len) {
    	return ans;
        }
    
        // 十位
        switch (str[pos]) {
        case 'X':
    	ans += 10;
    	++pos;
    
    	if (str[pos] == 'C') {
    	    ans += 80;
    	    ++pos;
    	}
    	else if (str[pos] == 'L'){
    	    ans += 30;
    	    ++pos;
    	}
    	else {
    	    while (pos < len && str[pos] == 'X') {
    		ans += 10;
    		++pos;
    	    }
    	}
    	break;
    
        case 'L':
    	ans += 50;
    	++pos;
    	while (pos < len && str[pos] == 'X') {
    	    ans += 10;
    	    ++pos;
    	}
    	break;
    
        default:
    	break;
        }
        if (pos == len) {
    	return ans;
        }
    
        // 个位
        switch (str[pos]) {
        case 'I':
    	ans += 1;
    	++pos;
    	if (str[pos] == 'X') {
    	    ans += 8;
    	    ++pos;
    	}
    	else if (str[pos] == 'V') {
    	    ans += 3;
    	    ++pos;
    	}
    	else {
    	    while (pos < len && str[pos] == 'I') {
    		++ans;
    		++pos;
    	    }
    	}
    
    	break;
        case 'V':
    	ans += 5;
    	++pos;
    	while (pos < len && str[pos] == 'I') {
    	    ++ans;
    	    ++pos;
    	}
    	break;
        default:
    	break;
        }
    
        return ans;
    }
    

    不得不说,这样的代码比较丑,这是真的,就算解出来了成就感也不强。

    Approach 2

    这个解法是leetcode上最快的解法之一,只使用一个循环就完成了计算,代码整体上很简洁,也比较好理解。只需要针对6种特殊情况做特殊处理就好。

    int romanToInt(string s) {
        int result = 0;
        int size = s.size();
        for(int i = 0; i < size; ++i) {
    	switch(s[i]) {
    	case 'M':
    	    if(i - 1 >= 0 && s[i - 1] == 'C')
    		result += 800;
    	    else
    		result += 1000;
    	    break;
    
    	case 'D':
    	    if(i - 1 >= 0 && s[i - 1] == 'C')
    		result += 300;
    	    else
    		result += 500;
    	    break;
    
    	case 'C':
    	    if(i - 1 >= 0 && s[i - 1] == 'X')
    		result += 80;
    	    else
    		result += 100;
    	    break;
    
    	case 'L':
    	    if(i - 1 >= 0 && s[i - 1] == 'X')
    		result += 30;
    	    else
    		result += 50;
    	    break;
    
    	case 'X':
    	    if(i - 1 >= 0 && s[i - 1] == 'I')
    		result += 8;
    	    else
    		result += 10;
    	    break;
    
    	case 'V':
    	    if(i - 1 >= 0 && s[i - 1] == 'I')
    		result += 3;
    	    else
    		result += 5;
    	    break;
    
    	case 'I':
    	    result += 1;
    	    break;
    
    	default:;
    	}
        }
        return result;
    }
    

    Approach 3

    下面这个是我在看该问题的discuss板块的时候发现的。不得不说,结题思路实在新奇,这点是值得学习的。不过我比较担心它的时间复杂度。该方法使用Java编写。

    public int romanToInt(String s) {
        int sum=0;
        if(s.indexOf("IV")!=-1){sum-=2;}
        if(s.indexOf("IX")!=-1){sum-=2;}
        if(s.indexOf("XL")!=-1){sum-=20;}
        if(s.indexOf("XC")!=-1){sum-=20;}
        if(s.indexOf("CD")!=-1){sum-=200;}
        if(s.indexOf("CM")!=-1){sum-=200;}
    
        char c[]=s.toCharArray();
        int count=0;
    
        for(;count<=s.length()-1;count++){
    	if(c[count]=='M') sum+=1000;
    	if(c[count]=='D') sum+=500;
    	if(c[count]=='C') sum+=100;
    	if(c[count]=='L') sum+=50;
    	if(c[count]=='X') sum+=10;
    	if(c[count]=='V') sum+=5;
    	if(c[count]=='I') sum+=1;
        }
    
        return sum;
    }