在做LeetCode题目的过程中, 我发现我对于STL容器的了解还是过于浅薄, 因此决定专门学习总结一下. 主要资料来源是http://www.cplusplus.com/reference/stl/.

标准容器

一个容器是一个保存一组其他对象(元素 element)的对象, 他们都是用类模板来实现的. 容器管理着保存元素的存储空间并且提供直接或通过迭代器(iterators)访问它们的成员函数.

stack, queue和priority_queue被实现为容器适配器(container adaptors), 容器适配器不是完整的容器类, 而是提供依赖于容器类(如deque或list)对象的特定接口的类.

顺序容器 Sequence Containers

• array
• vector
• deque
• forward_list
• list

容器适配器 Container Adaptors

• stack
• queue
• priority_queue

关联容器 Associative Containers

• set
• multiset
• map
• multimap

无序关联容器 Unordered Associative Containers

• unordered_set
• unordered_multiset
• unordered_map
• unordered_multimap

更多参考资料: http://www.cplusplus.com/reference/stl/

Array [C++11]

Array是固定大小的顺序容器, 它以固定的线性顺序存储特定数量的元素(注意不是特定的大小顺序). 在内部, Array不保存除了它包含的元素以外的任何数据(包括容器大小, 它是在编译期确定的值). 不同于vector, array不能动态改变大小. 大小为0的array是合法的, 但是它不应该被解引用(front, back和data成员函数). 不同于其他STL容器, swap两个array是一个线性操作, 会对每一个元素单独进行swap, 这一般被认为是一种低效操作.

部分成员函数

绝大部分array容器的成员函数时间复杂度都是常数时间复杂度.

array::data

1
2

value_type* data() noexcept;
const value_type* data() const noexcept;`</pre>

返回指向array对象首个元素的指针. 因为元素是连续存储的, 因此可以用偏移量(offset)来访问array中的元素. ​

array::fill

1

void fill (const value_type& val);

把array中的所有元素都设置为val. 时间复杂度: 线性.

array::swap

1

void swap (array& x) noexcept(noexcept(swap(declval<value_type&>(),declval<value_type&>())));

与array x交换内容. 时间复杂度: 线性. 迭代器合法性: 所有迭代器, 引用和指针的合法性都不会改变. 它们仍然与调用前相同的容器的相同位置相关联, 但是他们指向的值会是交换后的值.

题目描述:

Given a digit string, 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.

Input:Digit string "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.

这道题要求输入一串手机九宫格按键, 输出所有可能的字母组合. 方法是每读入一个按键, 就将原字符串数组复制数次(数量取决于这个按键上有几个字母), 然后加上当前读入的按键.

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        int letterNumOnButton[] = {1, 1, 3, 3 ,3, 3, 3, 4, 3, 4};
        vector<string> m = {
            " ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };
        
        if(digits.empty())
            return vector<string>();
        
        vector<string> re = {""};
        for(int i = 0; i < digits.length(); i++){
            int button = digits[i] - '0';
            
            int size = re.size();
            for(int j = 0; j < letterNumOnButton[button] - 1; j++){
                for(int k = 0; k < size; k++){
                    re.push_back(re[k]);
                }
            }
            
            for(int j = 0; j < m[button].length(); j++){
                for(int k = 0; k < size; k++){
                    re[j * size + k].push_back(m[button][j]);
                }
            }
        }
        
        return re;
    }
};

题目描述:

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

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

首先这是一个3Sum问题, 因此仍然先使用上一道题目的思路, 用双指针实现2Sum, 用target - nums[i]作为2Sum的target. 接下来的问题就是closest的问题了, 我的办法是遍历所有的2Sum组合(只需要遍历下标在i之后的元素), 找到最接近target - nums[i]的组合. 当三个数的和与target差距为0时也可以退出循环, 否则直到i等于nums.size() - 1为止.

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int minLen = INT_MAX, ret;
        for(int i = 0; i < nums.size(); i++){
            int oldMinLen = minLen;
            int sum = twoSum(nums, target - nums[i], i + 1, nums.size(), minLen);
            if(minLen < oldMinLen){
                ret = sum + nums[i];
            }
            if(minLen == 0) break;
        }
        return ret;
    }
    
    int twoSum(vector<int>& nums, int target, int left, int right, int &minLen) {
        int l = left, r = right - 1;
        int ret;
        while(l < r){
            int sum = nums[l] + nums[r];
            if(sum == target){
                ret = sum;
                minLen = 0;
                break;
            }
            else if(sum > target){
                r--;
            }
            else{
                l++;
            }
            int len = lenBetweenInt(sum, target);
            if(len < minLen){
                minLen = len;
                ret = sum;
            }
        }
        return ret;
    }
    
    int lenBetweenInt(int a, int b){
        return abs(a - b);
    }
};

对我来说, 相比于Windows, Linux更加能胜任开发的工作, 开发工具丰富, 有Terminal. 但是因为我只有一台笔记本电脑, 以前安装双系统总是被驱动问题所困扰, 显卡驱动, 网卡驱动是重灾区, 而且双系统切换需要重启, 非常繁琐. 在我增加了一块SSD后就一直没有再安装双系统.

最近微软为Windows 10提供了Ubuntu子系统, 但是到目前位置还是有Insider预览版可以安装. 我并不想去给微软当小白鼠, 况且我对于Windows系统本身也没什么兴趣, 也早就不再追逐软件的最新版. 从另一个方面来说, 我觉得这混淆了Windows和Linux, 写代码我喜欢Linux的那一套东西, 但是我觉得这拼凑出来的东西并不会好用.

虚拟机是一个不错的解决办法, 以前我都是使用VmWare运行桌面版的Linux, 但是性能是一个问题, 而且我发现我似乎用不到虚拟机Linux的桌面环境.

所以我今天用Hyper-V安装了Ubuntu Server版, 用SSH的办法登录上去, 就可以使用较低的硬件资源.

题目描述:

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

参考http://xiadong.info/2016/07/1-two-sum/Two Sum这道题, 我们可以先取得一个数n, 将-n作为target就变为了Two Sum问题, 代码如下:

class Solution {
    vector<vector<int>> ret;
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); i++){
            if(i >= 1 && nums[i] == nums[i - 1]) continue;
            if(nums[i] > 0) break;
            twoSum(nums, -nums[i], i + 1, nums.size());
        }
        return ret;
    }
    
    void twoSum(vector<int>& nums, int target, int left, int right) {
        int l = left, r = right - 1;
        while(l < r){
            int sum = nums[l] + nums[r];
            if(sum == target){
                vector<int> t = {-target, nums[l], nums[r]};
                ret.push_back(t);
                do{r--;}while(nums[r] == nums[r + 1]);
                do{l++;}while(nums[l] == nums[l - 1]);
            }
            else if(sum > target){
                r--;
            }
            else{
                l++;
            }
        }
    }
};

题目描述:

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

寻找一组字符串的最长公共前缀. 首先, 如果只有一个字符串, 那么它就是最长公共前缀, 如果有两个, 那么再跟第二个字符串逐个字符对比, 找出最长公共前缀. 再增加字符串则依次类推.

在这个方法的基础上, 可以想到最长公共前缀一定不会比字符串数组中最短的字符串长, 因此可以先找到最短字符串, 以它为一开始的基准.

代码:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty())
            return "";
        
        int shortestIndex = findShortest(strs);
        int prefixLen = strs[shortestIndex].length();
        int len = strs.size();
        
        for(int i = 0; i < len; i++){
            if(prefixLen == 0) return "";
            string s = strs[i];
            int l1 = prefixLen, l2 = s.length(), j;
            for(j = 0; j < l1 && j < l2; j++){
                if(strs[0][j] != s[j])
                    break;
            }
            
            if(j != l1 && j != l2){
                prefixLen = j;
            }
            else if(j == l2){
                prefixLen = l2;
            }
        }
        
        return strs[shortestIndex].substr(0, prefixLen);
    }
    
    int findShortest(vector<string> &strs){
        int minLen = INT_MAX, index;
        for(int i = 0; i < strs.size(); i++){
            if(strs[i].length() < minLen){
                minLen = strs[i].length();
                index = i;
            }
        }
        return index;
    }
};

问题描述:

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example:

n = 10, I pick 6.

Return 6.

二分搜索问题.

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int mid = n / 2, left = 1, right = n, tmpResult;
        while((tmpResult = guess(mid)) != 0){
            if(tmpResult == -1){
                right = mid;
            }
            else if(tmpResult == 1){
                left = mid + 1;
            }
            mid = (right - left) / 2 + left;
        }
        return mid;
    }
};

题目描述:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

与第12题相反, 同样是简单模拟:

class Solution {
public:
    int romanToInt(string s) {
        int ret = 0;

        int last_weight = -1;
        for(int i = s.length() - 1; i >= 0; i--){
            int w = symbolToVal(s[i]);
            if(w < last_weight)
                ret -= w;
            else{
                last_weight = w;
                ret += w;
            }
        }

        return ret;
    }
    
    int symbolToVal(char s){
        switch(s){
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return -1;
        }
    }
};

题目要求:

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

关于罗马数字的表示方法参考这里https://www.wikiwand.com/en/Roman_numerals

同时有以下三条规则:

• I placed before V or X indicates one less, so four is IV (one less than five) and nine is IX (one less than ten)
• X placed before L or C indicates ten less, so forty is XL (ten less than fifty) and ninety is XC (ten less than a hundred)
• C placed before D or M indicates a hundred less, so four hundred is CD (a hundred less than five hundred) and nine hundred is CM (a hundred less than a thousand)

整数转化为罗马数字，简单模拟。

class Solution {
public:
    string intToRoman(int num) {
        int numArr[4] = {0};
        int numArrIndex = 3;
        while(num > 0){
            numArr[numArrIndex--] = num % 10;
            num /= 10;
        }
        string ret;

        for(int i = 3, offset = 1; i >= 0; i--, offset *= 10){
            if(numArr[i] == 0) continue;
            else if(numArr[i] < 4){
                for(int j = 0; j < numArr[i]; j++) ret.push_back(valToSymbol(1 * offset));
            }
            else if(numArr[i] == 4){
                ret.push_back(valToSymbol(5 * offset));
                ret.push_back(valToSymbol(1 * offset));
            }
            else if(numArr[i] < 9){
                for(int j = 5; j < numArr[i]; j++) ret.push_back(valToSymbol(1 * offset));
                ret.push_back(valToSymbol(5 * offset));
            }
            else{
                ret.push_back(valToSymbol(10 * offset));
                ret.push_back(valToSymbol(1 * offset));
            }
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    
    char valToSymbol(int val){
        switch(val){
            case 1:
                return 'I';
            case 5:
                return 'V';
            case 10:
                return 'X';
            case 50:
                return 'L';
            case 100:
                return 'C';
            case 500:
                return 'D';
            case 1000:
                return 'M';
            default:
                return 0;
        }
    }
};

Runtime: 28ms

题目描述:

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.

稍微优化的暴力搜索，时间复杂度比O(n^2)稍低。

C:

int maxArea(int height[], int n) {
    int max = 0, len = n;
    for(int i = 0; i < len; i++){
        if(height[i] * (len - i - 1) <= max)continue;
        for(int j = i + (max / height[i] > 1 ? max / height[i] : 1); j < len; j++){
            int area = (j - i) * (height[i] < height[j] ? height[i] : height[j]);
            if(area > max)max = area;
        }
    }
    
    return max;
}

使用双指针的方法，从数组两端向中间遍历，时间复杂度约为O(n)。

C++:

class Solution {
public:
    int maxArea(vector<int> &height) {
        int start = 0, end = height.size() - 1, max = 0, area;
        
        while(start < end){
            if(height[start] < height[end]){
                area = height[start] * (end - start);
                max = max > area ? max : area;
                start++;
            }
            else{
                area = height[end] * (end - start);
                max = max > area ? max : area;
                end--;
            }
        }
        
        return max;
    }
};