算法集

字符串

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

代码

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 1) {
        return strdup(*strs);
    }
    int pos = 0;
    char tmp = 0, ttmp = 0;
    char *first = *strs;
    while ((tmp = *(first+pos))) {
        for (int i = 1; i < strsSize; ++i) {
            char *str = *(strs + i);
            if ((ttmp = *(str+pos)) == 0 || tmp != ttmp) {
                goto _s;
            }
        }
        pos++;
    }
_s:
    if (pos != 0) {
        char *res = (char *)malloc(pos+1);
        if (res == NULL) {
            return "";
        }
        strncpy(res, first, pos);
        res[pos] = 0;
        return res;
    }
    return "";
}

字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").


示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False


注意：

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

代码

bool match(int list1[], int list2[]) {
    for (int i = 0; i < 26; ++i) {
        if (list1[i] != list2[i]) return false;
    }

    return true;
}

bool checkInclusion(string s1, string s2) {
    if (s1.size() > s2.size()) {
        return false;
    }
    int list1[26] = {0};
    int list2[26] = {0};
    for (int i = 0; i < s1.size(); ++i) {
        list1[s1[i]-'a'] += 1;
        list2[s2[i]-'a'] += 1;
    }
    // 窗口思想
    int len = (int)(s2.size() - s1.size());
    for (int i = 0; i < len; ++i) {
        if (match(list1, list2)) return true;
        list2[s2[i+s1.size()] - 'a'] += 1;
        list2[s2[i] - 'a'] -= 1;
    }
    return match(list1, list2);
}

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"
说明：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

代码

string multiply(string num1, string num2) {
    int size = (int)(num1.size() + num2.size());
    vector<int> value(size + 1, 0);
    for (int i = (int)(num1.size() - 1); i >= 0; i--) {
        for (int j = (int)(num2.size() - 1); j >= 0; j--) {
            value[i+j+1] += (num1[i] - '0') * (num2[j] - '0');
        }
    }
    int r = 0;
    for (int i = size - 1; i >= 0; i--) {
        int &num = value[i];
        num += r;
        r = num / 10;
        num = num % 10;
    }
    int i = 0;
    // 清除最高位的0
    while (i < size && value[i] == 0) i++;
    if (i == size) return "0";
    string s;
    for (; i < size; i++) {
        s.push_back(value[i] + '0');
    }
    return s;
}

翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

示例:  

输入: "the sky is blue",
输出: "blue is sky the".
说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

代码

void reverseWords(char *s) {
    int i = 0, j = 0, pos = 0, offset = 0;
    while (*(s+i) == ' ') i++;
    int size = (int)strlen(s);
    if (size == 0) {
        return;
    }
    if (i == size) {
        s[0] = 0;
        return;
    }
    j = size-1;
    char *buffer = (char *)malloc(size+1);
    if (buffer == NULL) {
        return;
    }
    while (*(s+j) == ' ') j--;
    while (i <= j) {
        pos = 0;
        while (*(s+j-pos) != ' ' && i <= (j-pos)) pos++;
        
        strncpy(buffer+offset, s+j-(pos-1), pos);
        offset += pos;
        buffer[offset] = ' ';
        offset++;
        
        j -= pos + 1;
        
        while (*(s+j) == ' ') j--;
    }
    buffer[offset-1] = 0;
    strncpy(s, buffer, offset);
    s[offset-1] = 0;
    free(buffer);
}

简化路径

给定一个文档 (Unix-style) 的完全路径，请进行路径简化。

例如，
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

边界情况:

你是否考虑了 路径 = "/../" 的情况？
在这种情况下，你需返回 "/" 。
此外，路径中也可能包含多个斜杠 '/' ，如 "/home//foo/" 。
在这种情况下，你可忽略多余的斜杠，返回 "/home/foo" 。

代码

char* simplifyPath(char* path) {
    int length = (int)strlen(path);
    char *res = malloc(length+1);
    if (res == NULL) {
        return "";
    }
    memset(res, 0, length+1);
    int pos = 0, offset = 0;
    char ch = 0;
    while ((ch = *(path + pos))) {
        if (ch == '.') {
            if (*(path + pos + 1) == '/') {
                pos += 1;
            } else if (*(path + pos + 1) == '.') {
                if (*(path + pos + 2) == '/') {
                    int count = 0;
                    int i = offset-1;
                    for (; i >= 0; --i) {
                        if (*(res + i) == '/') {
                            if (++count >= 2) {
                                break;
                            }
                        }
                    }
                    offset = ++i <= 0 ? 1 : i;
                    pos += 2;
                } else if (*(path + pos + 2)) {
                    res[offset++] = '.';
                    res[offset++] = '.';
                    int tpos = 0;
                    while (*(path + pos + 2 + tpos)) {
                        if (*(path + pos + 2 + tpos) == '/') {
                            break;
                        }
                        res[offset++] = *(path + pos + 2 + tpos++);
                    }
                    pos += 2 + --tpos;
                } else {
                    int count = 0;
                    int i = offset-1;
                    for (; i >= 0; --i) {
                        if (*(res + i) == '/') {
                            if (++count >= 2) {
                                break;
                            }
                        }
                    }
                    offset = ++i <= 0 ? 1 : i;
                }
            } else if (*(path + pos + 1)) {
                res[offset++] = '.';
                int tpos = 0;
                while (*(path + pos + 1 + tpos)) {
                    if (*(path + pos + 1 + tpos) == '/') {
                        break;
                    }
                    res[offset++] = *(path + pos + 1 + tpos++);
                }
                pos += 1 + --tpos;
            }
        } else if (ch == '/' && *(path + pos + 1) == '/') {
            if (res[offset-1] != '/') {
                res[offset++] = '/';
            }
            int tpos = 0;
            while (*(path + pos + 1 + tpos++) == '/');
            pos += --tpos;
        } else if (ch == '/' && (offset == 1 || res[offset-1] == '/')) {
            
        } else {
            res[offset++] = ch;
        }
        ++pos;
    }
    
    if (offset != 0) {
        if (offset > 1 && res[offset-1] == '/') {
            --offset;
        }
    } else {
        res[offset++] = '/';
    }
    
    res[offset] = 0;
    return res;
}

复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

代码

char** restoreIpAddresses(char* s, int* returnSize) {
    char *str = s;
    int size = (int)strlen(str);
    if (size < 4 || size > 12) {
        *returnSize = 0;
        return NULL;
    }
    
    char **res = (char **)malloc(sizeof(char *));
    if (res == NULL) {
        return NULL;
    }
    int base1 = 1;

    for (int i1 = base1; i1 <= 3; ++i1) {
        char buffer1[i1+1];
        strncpy(buffer1, str, i1);
        buffer1[i1] = 0;
        int a1 = atoi(buffer1);
        if (buffer1[0] == '0' && strlen(buffer1) > 1) {
            break;
        }
        if (a1 >= 0 && a1 <= 255) {
            int base2 = 1;
            for (int i2 = base2; i2 <= 3; ++i2) {
                char buffer2[i2+1];
                strncpy(buffer2, str+i1, i2);
                buffer2[i2] = 0;
                int a2 = atoi(buffer2);
                if (buffer2[0] == '0' && strlen(buffer2) > 1) {
                    break;
                }
                if (a2 >= 0 && a2 <= 255) {
                    int base3 = 1;
                    for (int i3 = base3; i3 <= 3; ++i3) {
                        char buffer3[i3+1];
                        strncpy(buffer3, str+i1+i2, i3);
                        buffer3[i3] = 0;
                        if (buffer3[0] == '0' && strlen(buffer3) > 1) {
                            break;
                        }
                        int a3 = atoi(buffer3);
                        if (a3 >= 0 && a3 <= 255) {
                            int base4 = size - i1 - i2 - i3;
                            if (base4 > 3 || base4 < 1) {
                                continue;
                            }
                            int i4 = base4;
                            char buffer4[i4+1];
                            strncpy(buffer4, str+i1+i2+i3, i4);
                            buffer4[i4] = 0;
                            int a4 = atoi(buffer4);
                            if (buffer4[0] == '0' && strlen(buffer4) > 1) {
                                continue;
                            }
                            if (a4 >= 0 && a4 <= 255) {
                                char **tmpRes = (char **)realloc(res, sizeof(char *) * (*returnSize+1));
                                if (tmpRes == NULL) {
                                    return res;
                                }
                                res = tmpRes;
                                char *tres = (char *)malloc(sizeof(char) * (size+3+1));
                                if (tres == NULL) {
                                    continue;
                                }
                                sprintf(tres, "%d.%d.%d.%d", a1, a2, a3, a4);
                                tres[sizeof(char) * (size+3)] = 0;
                                res[(*returnSize)++] = tres;
                            }
                        } else {
                            break;
                        }
                    }
                } else {
                    break;
                }
            }
        } else {
            break;
        }
    }
    
    return res;
}

最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

代码

char* longestPalindrome(char* s) {
    char *org = s, *child = s;
    int maxLen = 1;
    while (*s) {
        char *l = s-1;
        char *r = s+1;
        while (*r && *r == *s) ++r; // *s与*(s+1) ...一致，r后移1位
        while (l >= org && *r && *l == *r) { // *l与*r一致，l前移1位，r后移1位
            --l;
            ++r;
        }
        
        int len = (int)((r-1)-(l+1)+1);
        if (len > maxLen) {
            maxLen = len;
            child = l+1; //child指向l的最后的相等位
        }
        ++s;
        
        if (!*r) { // 遍历结束标志
            break;
        }
    }
    child[maxLen] = 0;
    return child;
}

字符串转换整数 (atoi)

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，qing返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42
示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
    我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
    因此无法执行有效的转换。
示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
    因此返回 INT_MIN (−231) 。

代码

int myAtoi(char* str) {
    if (!*str) return 0;
    // 清除空字符
    while (*str == ' ') ++str;
    long res = 0;
    int factor = 1;
    // 判断正负数
    if (*str == '-') {
        factor = -1;
        ++str;
    } else if (*str == '+') ++str;
    while (*str >= '0' && *str <= '9') {
        res = res * 10 + (*str++ - '0');
        if (res > INT_MAX) return factor == 1 ? INT_MAX : INT_MIN;
    }
    return (int)(res * factor);
}

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

代码

bool isValid(string s) {
    stack<char> paren;
    for (char& c : s) {
        switch (c) {
            case '(':
            case '{':
            case '[': paren.push(c); break;
            case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
            case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
            case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
            default: ; // pass
        }
    }
    return paren.empty();
}

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。

示例 1:

输入: "hello"
输出: "olleh"
示例 2:

输入: "A man, a plan, a canal: Panama"
输出: "amanaP :lanac a ,nalp a ,nam A"

代码

string reverseString(string s) {
    for (int i = 0, j = (int)s.size() - 1; i < j; ++i, --j) {
        swap(s[i], s[j]);
    }
    return s;
}

反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1:

输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc" 
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

代码

string reverseWords(string s) {
    int b = 0, n = (int)s.size()-1;
    if (s[n] != ' ') {
        s.append(" ");
        n++;
    }
    while (s[b] == ' ') b++;
    for (int i = b; i <= n; ++i) {
        if (s[i] == ' ') {
            reverse(s.begin()+b, s.begin()+i);
            b = i + 1;
        }
    }
    while (s[n] == ' ') {
        s.pop_back();
        n--;
    }
    return s;
}

数学与数字

整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321
示例 2:

输入: -123
输出: -321
示例 3:

输入: 120
输出: 21
注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

代码

int reverse(int x) {
    long res = 0;
    while (x) {
        res = res * 10 + x % 10;
        x /= 10;
    }
    if (res > INT_MAX || res < INT_MIN) {
        return 0;
    }
    return (int)res;
}

回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

代码

bool isPalindrome(int x) {
    if (x < 0) return false;
    
    int t = x, ans = 0;
    while (t) {
        ans = ans * 10 + t % 10;
        t /= 10;
    }
    return x == ans;
}

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

代码

int singleNumber(vector<int>& nums) {
    int num = 0;
    for (int i = 0; i < nums.size(); i++) {
        num = num ^ nums[i];
    }
    return num;
}

求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

代码

int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size()/2];
}

2的幂

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

示例 1:

输入: 1
输出: true
解释: 20 = 1
示例 2:

输入: 16
输出: true
解释: 24 = 16
示例 3:

输入: 218
输出: false

代码

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    else if (n == 1) return true;
    while (n > 1) {
        if (n & 1) return false;
        n >>= 1;
    }
    return true;
}

数组与排序

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

代码

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hm1;

    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (hm1.find(complement) != hm1.end()) return {hm1.find(complement)->second, i};
        hm1[nums[i]] = i;
    }
    return {-1, -1};
}

寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

代码

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int sum = nums1Size + nums2Size, mid = 0, i = 0, j = 0, t1 = 0, t2 = 0;
    if (sum % 2) { // 奇数 mid
        mid = ceil(sum / 2.0);
        for (int k = 0;k < mid; k++) {
            if (i < nums1Size && j < nums2Size) {
                if (nums1[i] < nums2[j]) t1 = nums1[i++];
                else t1 = nums2[j++];
            } else {
                if (i < nums1Size) t1 = nums1[i++];
                else if (j < nums2Size) t1 = nums2[j++];
            }
        }
        return t1;
    } else { //偶数 mid mid+1 的一半
        mid = sum / 2;
        for (int k = 0;k < mid; k++) {
            if (i < nums1Size && j < nums2Size) {
                if (nums1[i] < nums2[j]) t1 = nums1[i++];
                else t1 = nums2[j++];
            } else {
                if (i < nums1Size) t1 = nums1[i++];
                else if (j < nums2Size) t1 = nums2[j++];
            }
        }
        if (i < nums1Size && j < nums2Size) {
            if (nums1[i] < nums2[j]) t2 = nums1[i++];
            else t2 = nums2[j++];
        } else {
            if (i < nums1Size) t2 = nums1[i++];
            else if (j < nums2Size) t2 = nums2[j++];
        }
        return (t1 + t2) / 2.0;
    }
    return 0;
}

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
    [-1, 0, 1],
    [-1, -1, 2]
]

代码

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    if (nums.size() < 3) return ans;
    sort(nums.begin(), nums.end());

    int i, j, k;
    for (i = 0; i < nums.size() - 2; i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int val = -nums[i];
        for (j = i + 1, k = (int)(nums.size() - 1); j < k; ) {
            if (nums[j] + nums[k] > val) {
                k--;
            } else if (nums[j] + nums[k] < val) {
                j++;
            } else {
                ans.push_back(vector<int>{nums[i], nums[j], nums[k]});
                while (++j && nums[j] == nums[j - 1]) {}
                while (--k && nums[k] == nums[k + 1]) {}
            }
        }
    }

    return ans;
}

最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

代码

int threeSumClosest(vector<int>& nums, int target) {
    int min = 0x7f7f;
    sort(nums.begin(), nums.end());
    int size = (int)nums.size();
    for (int i = 0; i < size; i++) {
        int j = i + 1, k = size - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (abs(min - target) > abs(sum - target)){
                min = sum;
            }
            if (sum <= target) j++;
            else k--;
        }
    }
    return min;
}

删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。
说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

代码

int removeDuplicates(vector<int>& nums) {
    int len = (int)nums.size();
    if (len <= 1) return len;
    int n = 0;
    for (int i = 0; i < len; ++i) {
        if (nums[i] != nums[n]) swap(nums[i], nums[++n]);
    }
    return n+1;
}

除自身以外数组的乘积

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

代码

vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> res (nums.size(), 1);
    int left = 1, right = 1, n = (int)nums.size();
    for (int i = 0; i < n; ++i) {
        res[i] *= left;
        res[n-1-i] *= right;
        left *= nums[i];
        right *= nums[n-1-i];
    }
    return res;
}

存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true
示例 2:

输入: [1,2,3,4]
输出: false
示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

代码

bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] == nums[i-1]) {
            return true;
        }
    }
    return false;
}

螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:

输入:
[
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

代码

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> res;
    int h = (int)matrix.size();
    if (h == 0) {
        return res;
    }
    int w = (int)matrix[0].size();
    if (w == 0) {
        return res;
    }
    
    int i = -1, j = -1, n = w * h, d = 0;
    while (true) {
        for (++i, ++j; i < w-d; ++i) {
            res.push_back(matrix[j][i]);
        }
        if (res.size() == n) break;
        for (--i, ++j; j < h-d; ++j) {
            res.push_back(matrix[j][i]);
        }
        if (res.size() == n) break;
        for (--j, --i; i >= d; --i) {
            res.push_back(matrix[j][i]);
        }
        if (res.size() == n) break;
        for (i = d, --j; j >= d + 1; --j) {
            res.push_back(matrix[j][i]);
        }
        if (res.size() == n) break;
        ++d;
    }
    return res;
}

螺旋矩阵 II

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
    [ 1, 2, 3 ],
    [ 8, 9, 4 ],
    [ 7, 6, 5 ]
]

代码

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n, vector<int>(n, 0));
    int s = 0, e = 1, end = n * n;
    while (e <= end) {
        for (int i = s; i < n - s; ++i)
            res[s][i] = e++;
        for (int i = s + 1; i < n - s; ++i)
            res[i][n - s - 1] = e++;
        for (int i = n - s - 2; i >= s; --i)
            res[n - s - 1][i] = e++;
        for (int i = n - s - 2; i > s; --i)
            res[i][s] = e++;
        ++s;
    }
    return res;
}

合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

代码

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    auto b1 = nums1.rbegin() + n, b2 = nums2.rbegin();
    for (auto cur = nums1.rbegin(); b1 != nums1.rend(); ++cur) {
        if (b2 == nums2.rend()) return;
        if (*b2 < *b1) *cur = *b1++;
        else *cur = *b2++;
    }
    copy(b2, nums2.rend(), nums1.rend() - (nums2.rend() - b2));
}

搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

代码

int search(vector<int>& nums, int target) {
    int n = (int)nums.size();
    if (n == 0) return -1;
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < nums[right]) {
            if (nums[mid] < target && nums[right] >= target) left = mid + 1;
            else right = mid - 1;
        } else {
            if (nums[left] <= target && nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
    }
    return -1;
}

最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续的的递增序列。

示例 1:

输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。 
示例 2:

输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
注意：数组长度不会超过10000。

代码

int findLengthOfLCIS(vector<int>& nums) {
    int len = (int)nums.size();
    if (len == 0) {
        return 0;
    }
    int maxCount = 1, count = 1;
    for (int i = 0; i < len-1;++i) {
        if (nums[i] < nums[i+1]) maxCount = max(maxCount, ++count);
        else count = 1;
    }
    return maxCount;
}

数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

代码

int findKthLargest(vector<int>& nums, int k) {
    if (nums.size() == 1) {
        return nums.front();
    }
    vector<int> maxs;
    for (int i = 0; i < k; ++i) {
        maxs.push_back(nums[i]);
    }

    sort(maxs.begin(), maxs.end(), [](int a, int b) { return a > b; });
    for (int i = k, len = (int)nums.size(); i < len; ++i) {
        int num = nums[i];
        for (auto begin = maxs.begin(), end = maxs.end(); begin != end; ++begin) {
            if (*begin >= num) {
                continue;
            }
            maxs.insert(begin, num);
            maxs.pop_back();
            break;
        }
    }
    return maxs.back();
}

最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

代码

int longestConsecutive(vector<int>& nums) {
    int res = 0;
    unordered_set<int> s(nums.begin(), nums.end());
    for (int val : nums) {
        if (!s.count(val)) continue;
        s.erase(val);
        int pre = val - 1, next = val + 1;
        while (s.count(pre)) s.erase(pre--);
        while (s.count(next)) s.erase(next++);
        res = max(res, next - pre - 1);
    }
    return res;
}

第k个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。
示例 1:

输入: n = 3, k = 3
输出: "213"
示例 2:

输入: n = 4, k = 9
输出: "2314"

代码

string getPermutation(int n, int k) {
    string res;
    string num = "123456789";
    vector<int> nums;
    nums.push_back(1);
    for (int i = 1; i < n; ++i) {
        nums.push_back(nums[i-1] * i);
    }
    k--;
    for (int i = n; i > 0; --i) {
        int f = nums[i - 1];
        int j = k / f;
        k %= f;
        res.push_back(num[j]);
        num.erase(j, 1);
    }
    return res;
}

朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意：
    N 在[1,200]的范围内。
    对于所有学生，有M[i][i] = 1。
    如果有M[i][j] = 1，则有M[j][i] = 1。

代码

int findCircleMember(vector<vector<int>>& M, int i, bool visited[]) {
        for (int j = 0; j < M.size(); ++j) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = true;
                findCircleMember(M, j, visited);
            }
        }
        return 0;
    }

    int findCircleNum(vector<vector<int>>& M) {
        int count = 0, size = (int)M.size();
        bool visited[size];
        memset(visited, false, size);
        for (int i = 0; i < size; ++i) {
            if (!visited[i]) {
                findCircleMember(M, i, visited);
                ++count;
            }
        }
        return count;
    }

岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

代码

int grd(vector<vector<int>>& grid, int i, int j, int xSize, int ySize) {
    int sum = 1;
    grid[i][j] = 0;
    int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    for (int k = 0; k < 4; ++k) {
        int x = i + dir[k][0];
        int y = j + dir[k][1];
        if (x >= 0 && x < xSize && y >= 0 && y < ySize && grid[x][y] == 1) {
            sum += grd(grid, x, y, xSize, ySize);
        }
    }
    return sum;
}

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int ySize = (int)grid[0].size();
    int xSize = (int)grid.size();
    int max = 0;
    for (int i = 0; i < xSize; ++i) {
        for (int j = 0; j < ySize; ++j) {
            if (grid[i][j] == 1) {
                max = std::max(grd(grid, i, j, xSize, ySize), max);
            }
        }
    }
    return max;
}

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

代码

vector<Interval> merge(vector<Interval>& intervals) {
    int len = (int)intervals.size();
    
    vector<Interval> res;

    sort(intervals.begin(), intervals.end(), [](Interval& i1, Interval& i2) { return i1.start < i2.start; });

    for (int i = 0; i < len;) {
        int start = intervals[i].start;
        int end = intervals[i].end;
        
        for (i++; i < len && intervals[i].start <= end; i++) end = max(end, intervals[i].end);
        
        res.push_back({start, end});
    }

    return res;
}

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

代码

int trap(vector<int>& height) {
    if (height.size() <= 2) return 0;
    
    vector<int> lastMax(height.size(), 0);
    int result = 0;
    lastMax.back() = height.back();
    
    for (int i = (int)height.size()-2; i >= 0; --i)
        lastMax.at(i) = max(lastMax.at(i+1), height.at(i));
    
    for (int i = 1; i < height.size(); ++i) {
        if (height.at(i) >= height.at(i-1)) continue;
        int leftmax  = height.at(i-1);
        while (i+1 < height.size() && lastMax.at(i+1) <= height.at(i)) {
            ++i;
            leftmax = max(leftmax, height.at(i));
        }
        int sum = 0, end = i;
        leftmax = min(leftmax, lastMax.at(i));
        while (end < height.size() && height.at(end) >= leftmax) ++end;
        i = end;
        if (end == height.size()) return result;
        while (end < height.size() && height.at(end) < leftmax) sum += height.at(end++);
        result += (end - i) * leftmax - sum;
        i = end;
    }
    return result;
}

盛最多水的容器

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。


示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

代码

int maxArea(vector<int>& height) {
    int val = 0, max = 0;
    for (int i = 0, j = (int)height.size() - 1; i < j; ) {
        if (height[i] > height[j]) {
            val = height[j] * (j - i);
            j--;
        }
        else {
            val = height[i] * (j - i);
            i++;
        }
        max = std::max(max, val);
    }
    return max;
}

链表

反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

代码

ListNode* reverseList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    ListNode *ans = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return ans;
}

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

代码

void createNode(int val, struct ListNode **thead) {
    struct ListNode *tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
    if (tmp == NULL) {
        return;
    }
    tmp->val = val;
    tmp->next = NULL;
    if (*thead != NULL) {
        (*thead)->next = tmp;
    }
    *thead = tmp;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *head = NULL;
    struct ListNode *thead = NULL;
    int remain = 0;
    if (l1 && l2) {
        int num = l1->val + l2->val;
        if (num > 9) {
            remain = 1;
            num = num % 10;
        }
        createNode(num, &thead);
        head = thead;
        
        l1 = l1->next;
        l2 = l2->next;
        while (l1 && l2) {
            int num = l1->val + l2->val + remain;
            if (num > 9) {
                remain = 1;
                num = num % 10;
            } else {
                remain = 0;
            }
            createNode(num, &thead);
            
            l1 = l1->next;
            l2 = l2->next;
        }
    }
    while (l1) {
        int num = l1->val + remain;
        if (num > 9) {
            remain = 1;
            num = num % 10;
        } else {
            remain = 0;
        }
        createNode(num, &thead);

        l1 = l1->next;
    }
    while (l2) {
        int num = l2->val + remain;
        if (num > 9) {
            remain = 1;
            num = num % 10;
        } else {
            remain = 0;
        }
        createNode(num, &thead);

        l2 = l2->next;
    }
    
    if (remain == 1) {
        createNode(1, &thead);
    }
    
    return head;
}

旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

代码

ListNode* rotateRight(ListNode* head, int k) {
    if (head == nullptr) return head;
    ListNode *temp = head;
    int len = 1;
    while (temp->next != nullptr) {
        temp = temp->next;
        len++;
    }
    temp->next = head;
    k %= len;
    ListNode *cur = head;
    int cnt = 1;
    while (cnt < len-k) {
        cur = cur->next;
        cnt++;
    }
    ListNode *ret = cur->next;
    cur->next = nullptr;
    return ret;
}

删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

    4 -> 5 -> 1 -> 9
示例 1:

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

代码

void deleteNode(ListNode* node) {
    node->val = node->next->val;
    ListNode *tmp = node->next;
    node->next = tmp->next;
    delete tmp;
}

环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。


示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

代码

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow) return true;
    }
    return false;
}

环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。


示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

代码

ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (slow == nullptr || fast == nullptr || fast->next == nullptr) return nullptr;

    ListNode *thead = head;
    while (thead != slow) {
        thead = thead->next;
        slow = slow->next;
    }
    return thead;
}

相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。


示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。


示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。


注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *tailA = headA;
    ListNode *tailB = headB;
    ListNode *preA = nullptr, *preB = nullptr;
    while (tailA && tailB) {
        preA = tailA;
        preB = tailB;
        tailA = tailA->next;
        tailB = tailB->next;
    }
    if (tailA == nullptr) {
        while (tailB) {
            preB = tailB;
            headB = headB->next;
            tailB = tailB->next;
        }
    } else {
        while (tailA) {
            preA = tailA;
            headA = headA->next;
            tailA = tailA->next;
        }
    }
    if (preA != preB) {
        return nullptr;
    }
    while (headA && headB) {
        if (headA == headB) {
            return headA;
        }
        headA = headA->next;
        headB = headB->next;
    }
    return nullptr;
}

合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

代码

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) {
        return l2;
    } else if (l2 == nullptr) {
        return l1;
    }

    ListNode *merged = nullptr;
    if (l1->val < l2->val) {
        merged = l1;
        merged->next = mergeTwoLists(l1->next, l2);
    } else {
        merged = l2;
        merged->next = mergeTwoLists(l1, l2->next);
    }

    return merged;
}

排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

代码

ListNode *getMid(ListNode *head) {
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) {
        return l2;
    } else if (l2 == nullptr) {
        return l1;
    }

    ListNode *merged = nullptr;
    if (l1->val < l2->val) {
        merged = l1;
        merged->next = mergeTwoLists(l1->next, l2);
    } else {
        merged = l2;
        merged->next = mergeTwoLists(l1, l2->next);
    }

    return merged;
}

ListNode* sortList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;

    ListNode *first = head, *mid = getMid(head), *second = mid->next;
    mid->next = nullptr;

    first = sortList(first);
    second = sortList(second);

    return mergeTwoLists(first, second);
}

合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
    1->4->5,
    1->3->4,
    2->6
]
输出: 1->1->2->3->4->4->5->6

代码

class compare {
public:
	bool operator() (ListNode* n1,ListNode* n2) const {
		if ( !n1 || !n2)
			return !n1;
		return n1->val>n2->val;
	}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty())
        return NULL;
    ListNode *guard = new ListNode (0);
    ListNode *tail= guard;
    priority_queue<ListNode *, vector<ListNode *>, compare> Q;
    for (int i=0; i < lists.size(); i++)
        Q.push(lists[i]);
    while (!Q.empty() && Q.top() != NULL) {
        ListNode* t = Q.top();
        Q.pop();
        tail->next = t;
        tail = tail->next;
        Q.push(t->next);
    }
    ListNode *res = guard->next;
    delete guard;
    return res;
}

树

二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
     3
    / \
   1   4
        \
         2
输出: 1
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
     5
    / \
   3   6
      / \
     2   4
    /
   1
输出: 3

代码

void kth(TreeNode* root, int k, int &res, int &index) {
    if (root == nullptr) return;
    int left = 0, right = 0;;
    kth(root->left, k, res, left);
    if (left + 1 == k)
        res = root->val;
    else if(left < k)
        kth(root->right, k - left - 1, res, right);
    
    index = left + right + 1;
}

int kthSmallest(TreeNode* root, int k) {
    int res = 0;
    int index = 0;
    kth(root, k, res, index);
    return res;
}

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

     3
    / \
   9  20
     /  \
    15   7
返回它的最大深度 3 。

代码

int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return 1 + max(left, right);
}

二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

     1
    / \
   2   3

输出: 6
示例 2:

输入: [-10,9,20,null,null,15,7]

    -10
    / \
   9  20
     /  \
    15   7

输出: 42

代码

int maxPathSum(TreeNode *root) {
    int ret = INT_MIN;
    onePath(root, ret);
    return ret;
}

int onePath(TreeNode* root, int &ret) {
    if (root == nullptr) return 0;
    int l = onePath(root->left, ret);
    int r = onePath(root->right, ret);
    ret = max(ret, max(0, l) + max(0, r) + root->val);
    return max(0, max(l, r)) + root->val;
}

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

     3
    / \
   9  20
     /  \
    15   7
返回锯齿形层次遍历如下：

[
    [3],
    [20,9],
    [15,7]
]

代码

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> vec;
    if (!root) return vec;

    bool open = false;
    queue<TreeNode *> que;
    que.push(root);

    while (!que.empty()) {
        int count = (int)que.size();
        vector<int> base;
        while (count--) {
            TreeNode *tmp = que.front();
            que.pop();
            base.push_back(tmp->val);
            if (tmp->left)
                que.push(tmp->left);
            if (tmp->right)
                que.push(tmp->right);
        }
        if (open) reverse(base.begin(), base.end());
        open = !open;
        vec.push_back(base);
    }
    return vec;
}

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

代码

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode *cur = root;
    while(1){
        if (cur == nullptr) return nullptr;
        if (p == cur || q == cur) return cur;
        else if (cur->val < p->val && cur->val < q->val)
            cur = cur->right;
        else if (cur->val > p->val && cur->val > q->val)
            cur = cur->left;
        else return cur;
    }
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。


说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

代码

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || root == p || root == q) return root;

    TreeNode *left = lowestCommonAncestor(root->left, p, q);
    TreeNode *right = lowestCommonAncestor(root->right, p, q);
    if (left != nullptr && right != nullptr) return root;
    return left == nullptr ? right : left;
}

回溯

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

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

代码

void dfsgen_parenthesis(int left, int right, vector<string>& res, string test) {
    if (left > right) return;
    if (left == 0 && right == 0) {
        res.push_back(test);
        return;
    }
    if (left > 0) dfsgen_parenthesis(left - 1, right, res, test + '(');
    if (right > 0) dfsgen_parenthesis(left, right - 1, res, test + ')');
}

vector<string> generateParenthesis(int n) {
    int left = n, right = n;
    vector<string> result;
    dfsgen_parenthesis(left, right, result, "");
    return result;
}

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
]

代码

vector<vector<int>> subsets(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ret;
    int all_set = (1 << nums.size());
    for (int i = 0; i < all_set; ++i) {
        vector<int> item;
        for (int j = 0 ; j < nums.size(); ++j) {
            if (i & (1 << j))
                item.push_back(nums[j]);
        }
        ret.push_back(item);
    }
    return ret;
}

全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
]

代码

void permuteRecur(vector<int> &num, int index, vector<vector<int>> &res, vector<int> &tempres) {
    if (index == num.size()) {
        res.push_back(tempres);
        return;
    }
    for(int i = index; i < num.size(); i++) {
        swap(num[index], num[i]);
        tempres.push_back(num[index]);
        permuteRecur(num, index+1, res, tempres);
        tempres.pop_back();
        swap(num[index], num[i]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    if (nums.size() == 0) return res;
    vector<int> tempres;
    sort(nums.begin(), nums.end());
    permuteRecur(nums, 0, res, tempres);
    return res;
}

格雷编码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。

00 - 0
10 - 2
11 - 3
01 - 1
示例 2:

输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
    给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
    因此，当 n = 0 时，其格雷编码序列为 [0]。

代码

vector<int> grayCode(int n) {
    int len = 1;
    for (int i = 0; i < n; ++i) {
        len *= 2;
    }
    vector<int> res;
    for (int i = 0; i < len; ++i) {
        res.push_back((i >> 1) ^ i);
    }
    return res;
}

动态规划与贪心

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:

输入: m = 7, n = 3
输出: 28

代码

int uniquePaths(int m, int n) {
    int a[m][n];
    for (int i = 0; i < m; i++) a[i][0]=1;
    for (int j = 0; j < n; j++) a[0][j]=1;
    for (int i = 1; i < m; i++)
        for(int j = 1; j < n; j++)
            a[i][j] = a[i-1][j] + a[i][j-1];
    
    return a[m-1][n-1];
}

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

代码

int maxProfit(vector<int>& prices) {
    if (prices.size() <= 1) return 0;

    int max = 0, sum = 0;
    for (int i = 1; i < prices.size(); ++i) {
        sum = std::max(0, sum + prices[i] - prices[i - 1]);
        max = std::max(max, sum);
    }
    return max;
}

买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
    因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

代码

int maxProfit(vector<int>& prices) {
    int maxPro = 0, tmp = 0;
    for (int i = 1; i < prices.size(); ++i) {
        tmp = prices[i] - prices[i-1];
        if (tmp > 0) maxPro += tmp;
    }
    return maxPro;
}

最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

代码

int maximalSquare(vector<vector<char>>& matrix) {
    int height = (int)matrix.size();
    if (height == 0) return 0;
    int width = matrix[0].size();
    int res = 0;
    vector<vector<int>> vec(height, vector<int>(width, 0));
    for (int i = 0; i < height; i++) {
        for(int j = 0; j < width; j++) {
            if (matrix[i][j] == '1') {
                vec[i][j] = 1;
                if(i > 0 && j > 0) vec[i][j] += min(min(vec[i-1][j], vec[i][j-1]), vec[i-1][j-1]);
            }
            res = max(res, vec[i][j]);
        }
    }
    return res * res;
}

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

代码

int maxSubArray(vector<int>& nums) {
    int res = INT_MIN, sum = 0;
    for (int num : nums) {
        sum = std::max(sum + num, num);
        res = std::max(res, sum);
    }
    return res;
}

三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
    [2],
   [3,4],
  [6,5,7],
 [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

代码

int minimumTotal(vector<vector<int>>& triangle) {
    int n = (int)triangle.size();
    vector<int> dp (triangle.back());
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
        }
        dp.pop_back();
    }
    return dp.front();
}

俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:
不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

代码

int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        int size = (int)envelopes.size();
        if (size == 0) return 0;
        else if (size == 1) return 1;

        vector<int> enp;
        sort(envelopes.begin(),envelopes.end(), [](const pair<int,int> &a, const pair<int,int>&b) {
            if (a.first == b.first) return a.second > b.second;
            return a.first < b.first;
        });
        for (int i = 0; i < size; ++i) {
            auto it = lower_bound(enp.begin(), enp.end(), envelopes[i].second);
            if (it == enp.end()) enp.push_back(envelopes[i].second);
            else *it = envelopes[i].second;
        }
        return (int)enp.size();
    }

数据结构

最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

代码

class MinStack {
private:
    struct StackNode {
        int val;
        StackNode *pre;
    };
    StackNode *topNode;
    StackNode *minNode;
    int min;
    
public:
    /** initialize your data structure here. */
    MinStack() {
        topNode = nullptr;
        minNode = nullptr;
    }
    ~MinStack() {
        while (topNode) {
            StackNode *pre = topNode->pre;
            delete topNode;
            topNode = pre;
        }
        
        while (minNode) {
            StackNode *pre = minNode->pre;
            delete minNode;
            minNode = pre;
        }
    }
    
    void push(int x) {
        StackNode *node = new StackNode;
        if (node == nullptr) {
            return;
        }
        node->val = x;
        node->pre = nullptr;
        if (topNode == nullptr) {
            topNode = node;
            min = x;
        } else {
            node->pre = topNode;
            topNode = node;
            if (min > x) {
                min = x;
            }
        }
        
        StackNode *node1 = new StackNode;
        if (node1 == nullptr) {
            return;
        }
        node1->val = min;
        node1->pre = nullptr;
        if (minNode == nullptr) {
            minNode = node1;
        } else {
            node1->pre = minNode;
            minNode = node1;
        }
    }
    
    void pop() {
        if (topNode == nullptr) {
            return;
        }
        StackNode *pre = topNode->pre;
        delete topNode;
        topNode = pre;
        
        if (minNode == nullptr) {
            return;
        }
        StackNode *preMin = minNode->pre;
        delete minNode;
        minNode = preMin;
        if (minNode) {
            min = minNode->val;
        }
    }
    
    int top() {
        return topNode == nullptr ? 0 : topNode->val;
    }
    
    int getMin() {
        return min;
    }
};

LRU缓存机制

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

代码

class LRUCache {
private:
    int capacity;
    unordered_map<int, list<pair<int, int>>::iterator> map;
    list<pair<int, int>> caches;
    
public:
    LRUCache(int capacity) : capacity(capacity), map(unordered_map<int, list<pair<int, int>>::iterator> (capacity)) {
        
    }
    
    int get(int key) {
        auto iterator = map.find(key);
        if (iterator == map.end()) {
            return -1;
        }
        
        caches.splice(caches.begin(), caches, iterator->second);
        return iterator->second->second;
    }
    
    void put(int key, int value) {
        auto iterator = map.find(key);
        if (iterator == map.end()) {
            caches.push_front({key, value});
            map[key] = caches.begin();
            if (caches.size() > capacity) {
                map.erase(caches.back().first);
                caches.pop_back();
            }
        } else {
            iterator->second->second = value;
            caches.splice(caches.begin(), caches, iterator->second);
        }
    }
};

全 O(1) 的数据结构

实现一个数据结构支持以下操作：

Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。

代码

class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {
        
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        auto h = hashStr(key);
        auto iterator = data.find(h);
        if (iterator != data.end()) iterator->second += 1;
        else data[h] = 1;
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        auto h = hashStr(key);
        auto iterator = data.find(h);
        if (iterator != data.end()) {
            if (iterator->second == 1) data.erase(iterator);
            else iterator->second -= 1;
        }
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if (data.size() == 0) {
            return "";
        }
        unordered_map<unsigned long long, int>::iterator maxKeyIterator;
        auto begin = data.begin();
        int max = (*begin).second;
        maxKeyIterator = begin;
        for (; begin != data.end(); ++begin) {
            int value = (*begin).second;
            if (max < value) {
                max = value;
                maxKeyIterator = begin;
            }
        }
        
        return unhashStr(maxKeyIterator->first);
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if (data.size() == 0) {
            return "";
        }
        unordered_map<unsigned long long, int>::iterator minKeyIterator;
        auto begin = data.begin();
        int min = (*begin).second;
        minKeyIterator = begin;
        for (; begin != data.end(); ++begin) {
            int value = (*begin).second;
            if (value < min) {
                min = value;
                minKeyIterator = begin;
            }
        }
        
        return unhashStr(minKeyIterator->first);
    }
    
private:
    const int base = 131;
    unsigned long long hashStr(string &key) {
        int n = (int)key.size();
        unsigned long long ans = 0;
        for (int i = 0; i < n; i++) ans = ans * base + key[i];
        return ans;
    }
    
    string unhashStr(unsigned long long h) {
        string ans = "";
        while (h) {
            ans += char(h % base);
            h /= base;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
    
private:
    unordered_map<unsigned long long, int> data;
};

拓展

Nim游戏

你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4
输出: false 
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
    因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

代码

bool canWinNim(int n) {
    return (n % 4) == 0 ? false : true;
}

x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
    由于返回类型是整数，小数部分将被舍去。

代码

int mySqrt(int x) {
    // x1 = (x0 + (x/x0))/2
    if(x <= 0) return 0;

    double res = x * 0.5, lastRes = x;

    while(fabs(lastRes-res) > 1e-15) {
        lastRes = res;
        res = (res + x/res) * 0.5;
    }

    return res;
}

UTF-8 编码验证

UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：

    1.对于 1 字节的字符，字节的第一位设为0，后面7位为这个符号的unicode码。
    2.对于 n 字节的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为0，后面字节的前两位一律设为10。剩下的没有提及的二进制位，全部为这个符号的unicode码。
这是 UTF-8 编码的工作方式：

Char. number range  |        UTF-8 octet sequence
    (hexadecimal)   |              (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

给定一个表示数据的整数数组，返回它是否为有效的 utf-8 编码。

注意:
输入是整数数组。只有每个整数的最低 8 个有效位用来存储数据。这意味着每个整数只表示 1 字节的数据。

示例 1:

data = [197, 130, 1], 表示 8 位的序列: 11000101 10000010 00000001.

返回 true 。
这是有效的 utf-8 编码，为一个2字节字符，跟着一个1字节字符。
示例 2:

data = [235, 140, 4], 表示 8 位的序列: 11101011 10001100 00000100.

返回 false 。
前 3 位都是 1 ，第 4 位为 0 表示它是一个3字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不以 10 开头，所以是不符合规则的。

代码

bool validUtf8(vector<int>& data) {
    int cnt = 0;
    for(int d : data) {
        if (!cnt) {
            if (d >> 5 == 0b110) cnt = 1;
            else if (d >> 4 == 0b1110) cnt = 2;
            else if (d >> 3 == 0b11110) cnt = 3;
            else if (d >> 7) return false;
        } else {
            if (d >> 6 != 0b10) return false;
            --cnt;
        }
    }
    return !cnt;
}

第二高的薪水

编写一个 SQL 查询，获取 Employee 表中第二高的薪水（Salary） 。

+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+
例如上述 Employee 表，SQL查询应该返回 200 作为第二高的薪水。如果不存在第二高的薪水，那么查询应返回 null。

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

代码

SELECT MAX(e.Salary) AS SecondHighestSalary FROM Employee AS e,
(SELECT MAX(e0.Salary) AS MaxSalary FROM Employee AS e0) AS e1
WHERE e.Salary <> e1.MaxSalary