• 每周算法:三数之和

    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;
    }
    
  • 每周算法:阿拉伯数字转换罗马数字

    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 an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

    Example 1:

    Input: 3
    Output: "III"
    

    Example 2:

    Input: 4
    Output: "IV"
    

    Example 3:

    Input: 9
    Output: "IX"
    

    Example 4:

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

    Example 5:

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

    来源:leetcode 12 integer to roman

    Solution

    Approach 1

    这道题并不难,方法也很容易想到,这道题被归为 medium 难度反而让我感到有些奇怪,下面的代码就是我的解法。

    string intToRoman(int num) {
    
        // digit1 ~ 4 分别代表个十百千
        int digit1 = num%10;
        int digit2 = num/10%10;
        int digit3 = num/100%10;
        int digit4 = num/1000%10;
    
        string ans;
    
        // 千
        for (int i=0; i<digit4; ++i) {
    	ans += 'M';
        }
    
        // 百
        switch (digit3) {
        case 1:
        case 2:
        case 3:
    	for (int i=0; i<digit3; ++i) {
    	    ans += 'C';
    	}
    	break;
    
        case 4:
    	ans += "CD";
    	break;
    
        case 5:
        case 6:
        case 7:
        case 8:
    	ans += 'D';
    	for (int i=5; i<digit3; ++i) {
    	    ans += 'C';
    	}
    	break;
    
        case 9:
    	ans += "CM";
    	break;
        default:
    	break;
        }
    
        // 十
        switch (digit2) {
        case 1:
        case 2:
        case 3:
    	for (int i=0; i<digit2; ++i){
    	    ans += 'X';
    	}
    	break;
    
        case 4:
    	ans += "XL";
    	break;
    
        case 5:
        case 6:
        case 7:
        case 8:
    	ans += 'L';
    	for (int i=5; i<digit2; ++i) {
    	    ans += "X";
    	}
    	break;
    
        case 9:
    	ans += "XC";
    	break;
    
        default:
    	break;
        }
    
        // 个
        switch (digit1) {
        case 1:
        case 2:
        case 3:
    	for (int i=0; i<digit1; ++i) {
    	    ans += 'I';
    	}
    	break;
    
        case 4:
    	ans += "IV";
    	break;
    
        case 5:
        case 6:
        case 7:
        case 8:
    	ans += 'V';
    	for (int i=5; i<digit1; ++i) {
    	    ans += 'I';
    	}
    	break;
    
        case 9:
    	ans += "IX";
    	break;
    
        default:
    	break;
        }
    
        return ans;
    }
    

    这样做感觉有点简单粗暴,而且代码看起来不够优雅。

    Approach 2

    下面代码是从leetcode上找的,这样的打表法,看起来至少从形式上会更加美观,而且也非常好理解。

    class Solution {
    public:
        const static string THOUS[];
        const static string HUNDS[];
        const static string TENS[];
        const static string ONES[];
        string intToRoman(int num) {
    	string result;
    	result += THOUS[(int)(num/1000)%10];
    	result += HUNDS[(int)(num/100)%10];
    	result += TENS[(int)(num/10)%10];
    	result += ONES[num%10];
    	return result;
        }
    };
    
    const string Solution::THOUS[]  = {"","M","MM","MMM"};
    const string Solution::HUNDS[]  = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
    const string Solution::TENS[]   = {"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
    const string Solution::ONES[]   = {"","I","II","III","IV","V","VI","VII","VIII","IX"};
    

    Approach 3

    下面这段代码也是leetcode上的答案,这个答案的通用性要好一些,最起码找到了规律,这有助于算法的后续拓展。

    class Solution {
    public:
        string intToRoman(int num) {
    	vector<int> base{1000, 100, 10, 1};
    	string roman = "MDCLXVI";
    	int index = 0, r;
    	string ret = "";
    	while(num) {
    	    r = num/base[index];
    	    num = num - r*base[index];
    	    if(r == 4) {
    		ret += roman[2*index];
    		ret += roman[2*index-1];
    	    }
    	    else if(r == 9) {
    		ret += roman[2*index];
    		ret += roman[2*index -2];
    	    }
    	    else if(r >= 5) {
    		ret += roman[2*index - 1];
    		// 下面这个string的用法值得学习
    		string tmp(r-5, roman[2*index]);
    		ret += tmp;
    	    }
    	    else if(r < 5) {
    		string tmp(r, roman[2*index]);
    		ret += tmp;
    	    }
    	    index++;
    	}
    	return ret;
        }
    };
    

    此外,我还学到了 string tmp(num, ch) 这样的创建具有重复字符的字符串的方法。

  • 静态成员变量初始化相关问题

    引言

    这篇文章的起因是出于对于 C++ 饿汉单例模式代码的一些疑问,查阅了一些资料。在仔细研究后,我发现在一些基础概念的理解还是存在偏差。
    下面请看这样的一段代码,能看出其中有那些不太“正常”的语句么。

    class Singleton
    {
    public:
        static Singleton* getInstance();
    private:
        Singleton() {}
        static Singleton* instance;
    };
    
    Singleton* Singleton::instance = new Singleton();
    Singleton* Singleton::getInstance() {
        return instance;
    }
    

    私有静态成员的初始化

    上面的代码是饿汉单例模式的 C++ 的实现,在没有查阅资料之前,我对其中私有静态成员变量的初始化存疑。主要有以下两点:

    • 为什么私有变量能够在类外被修改
    • 为什么私有构造函数能够在类外被调用

    在我之前的知识积累中, 私有的成员变量或成员函数是不能够在类外被访问的 。那么为什么以上代码没有问题呢?

    在C++标准中找到了下面的一段话(可以在 C++11 standard 的 9.4.2节 或 C++ standard working draft 的 10.3.9.2节 中找到)

    The initializer expression in the definition of a static data member is in the scope of its class.

    这句话的意思是:静态成员变量的初始化是被看做为它自身的类域中的( 翻译的可能不是很准 )。这样就不难理解为什么私有的静态成员变量能够在其类外被初始化了,由其私有构造函数进行构造也能说的通了。

    同样 ,在C++标准中给出了下面这样的示例代码:

    class process {
      static process* run_chain;
      static process* running;
    };
    
    process* process::running = get_main();
    process* process::run_chain = running;
    

    给出的说明如下:

    The static data member run_chain of class process is defined in global scope; the notation process​::​run_chain specifies that the member run_chain is a member of class process and in the scope of class process. In the static data member definition, the initializer expression refers to the static data member running of class process.

    静态成员 run_chain 定义在全局域;而 process::run_chain 则表示 run_chainprocess 类的成员变量,从而处在 process 类的作用域中。

    私有构造函数

    在查阅资料时,我发现 Peter 的 描述 纠正了我对私有构造函数的一些看法。

    The point of a private constructor is not preventing object construction. It is about controlling which code can access the constructor, and therefore limiting which code to create an object that is an instance of that class. A private constructor is accessible to all member functions ( static or otherwise) of the class, and to all declared friend s of the class (which may be individual functions, or other classes) - so any of those can create an instance of the class using a private constructor (assuming the constructor is defined).

    私有构造函数的目的并不是禁止对象构造,其目的在于控制哪些代码能够调用这个构造函数,进而限制类对象的创建。私有的构造函数可以被该类的所有成员函数(静态或非静态的)调用,该类的友元类或友元方法也能访问该类的私有函数,所以在上述情况中都可以通过私有的构造函数实例化出类对象。

  • 客户端使用非阻塞socket进行connect的流程

    问题

    使用非阻塞( non-blocking ) socket尝试与服务端建立连接( connect )时,由于是io非阻塞的,所以 connect 函数会立即返回,那么如何判断client与server连接成功了呢?

    解答

    客户端建立连接的示例代码如下:

    int res = connect(fd, ...);
    if (res < 0 && errno != EINPROGRESS) {
        // case1. error, fail somehow, close socket
        return;
    }
    
    if (res == 0) {
        // case2. connection has succeeded immediately
    } else {
        // case3. connection attempt is in progress
    }
    

    由于是非阻塞模式,所以 connect 之后会直接返回,根据返回值 reserrno 能够判断建立连接的结果。

    • case1,表示连接失败;
    • case2,表示连接建立成功;
    • case3,表示正在建立连接的过程中,在这个情况下,需要等待socket变成可写(writable)状态,可以使用 selectepoll 完成;

    在 case3 情况下,socket可写后,执行下面的代码检查socket是否出现错误。

    • case4和case5,表示socket出现了错误,将会关闭连接;
    • case6,表示连接建立成功,可以开始 readwrite 了。
    int result;
    socklen_t result_len = sizeof(result);
    if (getsockopt(fd, SOL_SOCKET, SO_ERROR, &result, &result_len) < 0) {
        // case4. error, fail somehow, close socket
        return;
    }
    
    if (result != 0) {
        // case5. connection failed; error code is in 'result'
        return;
    }
    
    // case6. socket is ready for read()/write()
    

    参考资料

  • 每周算法:最大容器

    Description

    Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

    Note: You may not slant the container and n is at least 2.

    Example:
    Input: [1,8,6,2,5,4,8,3,7]
    Output: 49

    来源: leetcode 11 Container with most water

    Solution

    Approach 1 暴力解法

    暴力解法是最容易想到的解法了,然而暴力解法肯定不是本题的意图。

    int maxArea(vector<int>& height) {
        int ans = 0;
    
        int len = height.size();
    
        for (int i=0; i < len-1; ++i) {
    	for (int j=i+1; j < len; ++j) {
    	    int size = (j-i) * min(height[i], height[j]);
    	    ans = ans > size ? ans : size;
    	}
        }
    
        return ans;
    }
    

    使用这种解法只要把变量变化的范围想清楚就行了,没有什么特别的难点。
    暴力解法的时间复杂度为 O(n2),空间复杂度为 O(1)。

    Approach 2

    我在leetcode上看到这样一种解法,这种解法从逻辑和形式上看上不复杂,但是我的疑问在是否有严密的数学推导和论证。

    int maxArea(vector<int>& height) {
    
        int ans = 0;
        int left = 0;
        int right = height.size()-1;
    
        while (left < right) {
    	int w = right - left;
    	int h = min(height[left], height[right]);
    
    	ans = max(w*h, ans);
    
    	if (height[left] < height[right]) {
    	    ++left;
    	}
    	else {
    	    --right;
    	}
        }
    
        return ans;
    }
    

    这个算法的主要思想是最大面积由两端边界较短的板决定;所以在移动边界时要将长板保留,移动短板。该算法的时间复杂度为 O(n),空间复杂度为O(1)。

    在寻求该算法的数学推导时,我看到了 @nan15 给出的另外一种解释:

    We starts with the widest container, l = 0 and r = n - 1 . Let's say the left one is shorter: h[l] < h[r] . Then, this is already the largest container the left one can possibly form. There's no need to consider it again. Therefore, we just throw it away and start again with l = 1 and r = n - 1 .

    这个论证我认为是更加直观的:从最宽的容器开始,这时左边坐标 l = 0 ,右边坐标 r = n - 1 。假设左边更短,也就是 h[l] < h[r] 。那么,对于左边的板子,这是已经是它能够形成的最大的面积了,也就不需要再考虑它了。因此,将左边的板子丢掉,使用 l = 1r = n - 1 重新开始。