题目描述:

Implement pow(x, n).

题目要求实现pow函数. 首先n若小于0, 则可以先把x取倒数, 然后n取相反数, 从而变为n大于0的情况(但是由于int表示范围的问题, 所以新的n应该使用long long来存储), 所以只要考虑n大于0的情况. xⁿ = (x²)^n/2(n为偶数); xⁿ = x*(x²)^{(n - 1)/2}(n为奇数), 所以循环次数可以降低至logn次.

class Solution {
public:
    double myPow(double x, int n) {
        long long nn = n;
        double re = 1;
        if(nn == 0) return 1;
        if(nn < 0){
            x = 1 / x;
            nn = -nn;
        }
        while(nn > 1){
            if(nn % 2 == 0){
                x *= x;
                nn = nn >> 1;
            }
            else{
                re *= x;
                nn -= 1;
            }
        }
        return re * x;
    }
};

题目描述:

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

anagram的意思是"颠倒字母而成的词句", 也就是要把由相同字母组成的但顺序不同的字符串放到一起. 使用hash表, 对每个字符串中的字符排序后得到的新字符串作为hash表的key, value则是对应的原字符串集合.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        vector<vector<string>> ret;
        for(int i = 0; i < strs.size(); i++){
            string s = strs[i];
            sort(s.begin(), s.end());
            if(m.count(s)){
                m[s].push_back(strs[i]);
            }
            else{
                m[s] = vector<string>(1, strs[i]);
            }
        }
        ret.resize(m.size()); //预先扩展ret的大小, 避免在循环中push_back频繁分配新的内存空间
        int cnt = 0;
        for(auto i = m.begin(); i != m.end(); i++){
            ret[cnt++] = (i->second);
        }
        return ret;
    }
};

题目描述:

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

题目要求将一个n*n数组顺时针旋转90度, 并且最好不使用额外空间. 所以用对角线将矩阵分为四个区域, 对于每个区域内的每个元素依次放入上一个区域的值.

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n / 2; i++){
            for(int j = i; j < n - 1 - i; j++){
                int swap_t = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = swap_t;
            }
        }
    }
};

[TOC]

List 双向链表

list是允许在容器内任意位置以常数时间进行插入删除操作的顺序容器, 它的迭代器也是双向的.

list被实现为双向链表, 它与forward_list的主要区别在于forward_list是单向链表, 迭代器只能向前.

与其他顺序容器相比主要优点在于在容器任意位置插入, 提取和移动的表现更好. 不足在于不能根据元素在容器中的位置来访问元素.

部分函数

list没有随机访问方法, 没有at成员函数或者[]运算符.

构造函数

与其他顺序容器类似

类型	原型
default (1)	explicit list (const allocator_type& alloc = allocator_type());
fill (2)	explicit list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());
range (3)	template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
copy (4)	list (const list& x);

list::merge

void merge (list& x);
  void merge (list&& x);
template <class Compare>
  void merge (list& x, Compare comp);
template <class Compare>
  void merge (list&& x, Compare comp);

将x中的元素按照相应的顺序放入容器中, 两个容器都应有序. 该操作移除x中的所有元素, 但不会析构或构造任何对象.

该函数的模板版本使用comp作为比较元素大小的方法. 结果得到的list是稳定的. 当&x == this时不会做任何事.

list::splice

将元素从x中转移到当前容器中, 插入到position指定的位置.

晕啊素会从x中移除, 两个容器的大小都会改变. 该操作不会析构或构造任何对象.

void splice (const_iterator position, list& x);
void splice (const_iterator position, list&& x);

x中的所有元素都转移到list中.

void splice (const_iterator position, list& x, const_iterator i);
void splice (const_iterator position, list&& x, const_iterator i);

只有迭代器i指定的元素被移动.

void splice (const_iterator position, list& x,
            const_iterator first, const_iterator last);
void splice (const_iterator position, list&& x,
            const_iterator first, const_iterator last);

[first, last)范围内的元素被移动.

list::unique

void unique();

删除除了第一个元素以外的重复元素. **注意:**只有与前一个元素相等的元素才会被移除, 所以该函数只能用于有序list.

template <class BinaryPredicate>
    void unique (BinaryPredicate binary_pred);

使用一个比较函数来决定两个元素是否相等. unique会对每个相邻元素调用binary_pred(*i, *(i - 1)), 如果返回true则删除i.

题目描述:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

与上一题46. Permutations类似, 只不过输入集合中可能有重复数字, 而输出要求没有重复. 所以先对输入序列进行排序, 然后每次递归时跳过多次出现的数字中除了第一个数字以外的数.

class Solution {
    vector<vector<int>> ret;
    int numsLen;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> flag(nums.size(), false);
        vector<int> p;
        numsLen = nums.size();
        for(int i = 0; i < numsLen; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            flag[i] = true;
            p.push_back(nums[i]);
            permute(nums, flag, p, nums.size() - 1);
            p.pop_back();
            flag[i] = false;
        }
        return ret;
    }
    
    void permute(vector<int>& nums, vector<bool> &flag, vector<int> &p, int lastLen){
        if(lastLen == 0){
            ret.push_back(p);
            return;
        }
        for(int i = 0; i < numsLen; i++){
            if(flag[i]) continue;
            if(i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]) continue;
            flag[i] = true;
            p.push_back(nums[i]);
            permute(nums, flag, p, lastLen - 1);
            p.pop_back();
            flag[i] = false;
        }
    }
};

题目描述:

Given a collection of distinct numbers, return all possible permutations.

For example,

[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

使用递归来创建所有排列.

class Solution {
    vector<vector<int>> ret;
    int numsLen;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> flag(nums.size(), false);
        vector<int> p;
        numsLen = nums.size();
        for(int i = 0; i < numsLen; i++){
            flag[i] = true;
            p.push_back(nums[i]);
            permute(nums, flag, p, nums.size() - 1);
            p.pop_back();
            flag[i] = false;
        }
        return ret;
    }
    
    void permute(vector<int>& nums, vector<bool> &flag, vector<int> &p, int lastLen){
        if(lastLen == 0){
            ret.push_back(p);
            return;
        }
        for(int i = 0; i < numsLen; i++){
            if(flag[i]) continue;
            flag[i] = true;
            p.push_back(nums[i]);
            permute(nums, flag, p, lastLen - 1);
            p.pop_back();
            flag[i] = false;
        }
    }
};

问题描述:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:

You can assume that you can always reach the last index.

当走到nums[i]时, 遍历[i + 1, i + nums[i]]范围内的元素, 找到其中最大的值, 作为下一次循环的i. 对于只有一个元素的nums单独处理.

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        int p = 0,step = 0;
        while(p + nums[p] < nums.size() - 1){
            step++;
            int nextP = -1, nextPPos = 0;
            for(int j = 1; j <= nums[p] && p + j < nums.size(); j++){
                if(nums[p + j] + p + j > nextP){
                    nextP = nums[p + j] + p + j;
                    nextPPos = p + j;
                }
            }
            p = nextPPos;
        }
        return step + 1;
    }
};

题目描述:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:

• What if negative numbers are allowed in the given array?
• How does it change the problem?
• What limitation we need to add to the question to allow negative numbers?

这是一道比较明显的动态规划题, 但是我一开始还是直接用了递归, 无悬念的超时.

和等于target的组合数量等于target减去nums中每一个元素后的所有新target的组合数量之和. 如果target与nums中某个值相等则再加1.

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        for(int i = 0; i <= target; i++){
            for(int j = 0; j < nums.size(); j++){
                if(i == nums[j]) dp[i]++;
                else if(i > nums[j]){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

关于Follow up: 如果nums中出现了负数, 那么问题在于新的target值是通过target - nums[i]来得到的, 如果nums[i]为负, 那么新的target将会大于旧的target, 这会有两个问题

1. 动态规划只保存了小于旧target的值
2. 如果动态规划不以target为终点而继续到新的target值, 那么又会产生更大的target, target会无穷增长下去.

在题目中要求每个数只能选择一次就可以避免target的无限增长, 从而使求解成为可能.

题目描述:

Implement wildcard pattern matching with support for ‘?’ and ‘*’.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

与LeetCode 10. Regular Expression Matching这道题看起来十分相似, 但是使用相同的方法的话会超时. 然后我参考了这篇文章: http://yucoding.blogspot.jp/2013/02/leetcode-question-123-wildcard-matching.html. 主要思路如下:

• 用两个指针i,j或下标分别指向字符串s和p的开头
• s[i] == p[j]或p[j] == '?', 字符匹配, i和j都加1
• p[j] == '*', 也匹配, 记录下该*出现的位置lastStar和此时匹配的s中的位置lastPosAfterStarMatch, 这种情况下先认为*符号匹配空串, 所以只有j++
• 剩下的情况就是不匹配, 先看p串之前有没有位置lastStar, 如果有, 就将该位置的*所匹配的串长度加1(初始为0), 也就是把i变为++lastPosAfterStarMatch, j变为lastStar + 1
• 如果之前没有*, 那么就返回不匹配
• 整个循环要处理完s, 然后查看p中剩下的字符是不是都是*, 如果是就返回true

这个方法实际是回溯法, 只不过只回溯到上一个*而不再往前回溯.

代码:

class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0, lastStar = -1, lastPosAfterStarMatch = -1;
        while(i < s.size()){
            if(j < p.size() && (s[i] == p[j] || p[j] == '?')){
                i++;j++;
            }
            else if(j < p.size() && p[j] == '*'){
                lastStar = j++;
                lastPosAfterStarMatch = i;
            }
            else if(lastStar != -1){
                i = ++lastPosAfterStarMatch;
                j = lastStar + 1;
            }
            else return false;
        }
        for(; j < p.size(); j++){
            if(p[j] != '*') return false;
        }
        return true;
    }
};

题目描述:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

• The numbers can be arbitrarily large and are non-negative.
• Converting the input string to integer is NOT allowed.
• You should NOT use internal library such as BigInteger.

输入两个用数组表示的非负数, 输出它们相乘的结果. 使用模拟手算的方法:

class Solution {
public:
    void multiplyWithOneDigit(string& num1, char num2, vector<string>& v){
        int jw = 0;
        string re;
        for(int i = num1.size() - 1; i >= 0; i--){
            int t = (num2) * (num1[i]) + jw;
            re.push_back((t % 10));
            jw = t / 10;
        }
        if(jw)
            re.push_back(jw);
        v.push_back(re);
    }
    void plusString(string& a, string& b){
        if(a.size() < b.size()){
            swap(a, b);
        }
        string re;
        int jw = 0;
        for(int i = 0; i < b.size(); i++){
            int t = a[i] + b[i] + jw;
            re.push_back((t % 10));
            jw = t / 10;
        }
        for(int i = b.size(); i < a.size(); i++){
            int t = a[i] + jw;
            re.push_back((t % 10));
            jw = t / 10;
        }
        if(jw)
            re.push_back(jw);
        a = re;
    }
    string plusAll(vector<string>& v){
        string re = {0};
        for(int i = 0; i < v.size(); i++){
            plusString(re, v[i]);
        }
        while(!re.empty() && re.back() == 0) re.pop_back();
        if(re.empty())
            re = {0};
        return re;
    }
    string multiply(string num1, string num2) {
        for(auto &i : num1) i -= '0';
        for(auto &i : num2) i -= '0';
        vector<string> v;
        if(num2.size() > num1.size()) swap(num1, num2);
        for(int i = num2.size() - 1; i >= 0; i--){
            multiplyWithOneDigit(num1, num2[i], v);
            v.back().insert(v.back().begin(), num2.size() - i - 1, 0);
        }
        string ret = plusAll(v);
        reverse(ret.begin(), ret.end());
        for(auto &i : ret) i += '0';
        return ret;
    }
};