LeetCode 算法题(Easy)

001. Two Sum

Description: 求出能组合出目标数的两个元素

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解法一: 穷举

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$

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

解法二 : 哈希表, 两次遍历

注意, 题目中说数组的解恰好只有一个, 这是一种很强的假设, 解法二在面对有多个解时, 也只会输出一个
这里要特别注意: 同一个元素不能使用两次, 但是数组中的元素是可以重复的, 重复的元素看作是两个元素. hash表中最终存储的将会是重复元素的最后一个下标, 因此, 在进行比较时, 使用 i!= nums_map[target-nums[i]] 来判断它们是否为同一个元素, 而不能使用nums_map[nums[i]] != nums_map[target-nums[i]]

时间复杂度: $O(n)$ 遍历两次
空间复杂度: $O(n)$

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> nums_map;
        for(int i = 0 ;i<nums.size(); i++){
            nums_map.insert({nums[i], i});
        }
        for(int i  = 0 ; i<nums.size(); i++){
            if(nums_map.count(target-nums[i]) == 1 && i!= nums_map[target-nums[i]]){
                vector<int> res = {i, nums_map[target-nums[i]]}; //这里一定要用i,而不能用nums_map[nums[i]] , 上面也同理
                return res;
            }
        }      
    }
};

解法三: 哈希表 一次遍历

事实上, 可以将hash表的插入和查找对应元素的操作放在 一个循环里, 这样就只需要进行一次遍历

时间复杂度: $O(n)$ 遍历一次
空间复杂度: $O(n)$

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> nums_map;
        for(int i = 0 ;i<nums.size(); i++){
            if(nums_map.count(target-nums[i]) == 1 && i!= nums_map[target-nums[i]]){
                vector<int> res = {i, nums_map[target-nums[i]]};
                return res;
            }
            nums_map.insert({nums[i], i});
        }    
    }
};

扩展问题

How would you approach the problem if the input array is very large (but limited range) and cannot fit in the memory ? This is a follow-up question for this problem.

007. Reverse Integer

Description: 将数字逆置

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

解法一: 取余数

这道题本身不难, 只要不断对x的绝对值取余数, 就可以得到反转的整数, 但是, 该题的核心考察点在于边界条件的判断, 稍不注意, 很容易漏解(如果不进行边界判断, 即使写出了解决方法, 面试官也很不满意)

• x为0
• x反转后的值,超过了int型数据的表示范围, 检查方法是先用long存储, 然后看情况决定返回值正负.

class Solution {
public:
    int reverse(int x) {
        if(x==0) return x;
        int abs_x = abs(x);
        int sign_x = x>0? 1:-1;
        long res = 0; // 为了看int是否越界,特意将res声明为long型
        while( abs_x!=0 ){
            res = res*10 + abs_x%10;
            if(res > INT_MAX || res < INT_MIN) return 0; //这一句就是最主要的考察点,看int是否越界
            abs_x = abs_x/10 ;
        }

        if(sign_x ==-1) return 0-res;
        return res;
    }
};

013. Roman to Integer

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: L = 50, V= 5, III = 3.
Example 5:

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

解法一: 顺序扫描

时间复杂度: $O(n)$

顺序扫描, 如果当前字符比下一个字符小, 说明是 ‘4’ 或 ‘9’ 的情况, 用下一个字符的值减去当前字符的值

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> roman_char;
        roman_char['I'] = 1;
        roman_char['V'] = 5;
        roman_char['X'] = 10;
        roman_char['L'] = 50;
        roman_char['C'] = 100;
        roman_char['D'] = 500;
        roman_char['M'] = 1000;
        int res = 0;
        for(int i =0; i<s.size() ; i++){

            if( i<s.size()-1 && roman_char[s[i]] < roman_char[s[i+1]]){
                res += roman_char[s[i+1]]-roman_char[s[i]];
                i++;
            }
            else
                res += roman_char[s[i]];       
        }
        return res;
    }
};

扩展问题: 异常检测

上面的解法虽然可以通过OJ, 但是此题还需要进行特别的异常诊断, 即要能够判断出当前输入的罗马输出是否合法! 如 “IVIV” 就是典型的不合法输入, 对于此输入, 上面的程序会输出 , 这显然不正确

014. Longest Common Prefix

Description: 最长公共前缀

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:
All given inputs are in lowercase letters a-z.

解法一: 顺序比较

时间复杂度: $O(S)$, $S$ 为所有字符串中的字符总数
空间复杂度: $O(1)$, 没有使用额外的空间

暴力求解, 先求第一个字符串与第二个字符串最长公共前缀, 然后利用该前缀与第三个字符串比较, 知道公共前缀为空或者比较完所有字符串.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0 || strs[0].size()==0) return "";
        string prefix = strs[0];
        for(int i=0; i<strs.size() && !prefix.empty(); i++){
            int j=0;
            while(j<prefix.size()&&j<strs[i].size()
                 &&prefix[j] == strs[i][j]){
                j++;
            }
            prefix = prefix.substr(0, j);
        }
        return prefix;
    }
};

解法二: 垂直比较

时间复杂度: $O(S)$, $S$ 为所有字符串中的字符总数, 最好情况下复杂度为 $O(n\min(s)$, $\min(s)$ 为字符串数组中的最短字符串长度.
空间复杂度: $O(1)$, 没有使用额外的空间

顺序比较所有字符串的值, 直到遇到第一次不相等的位置, 然后输出前面的公共前缀, 需要额外注意处理以下几种特殊情况:
输入

• 输入为: [] 或 [“”] 应该直接返回””
• 输入为: [“abc”] 应该直接返回”abc”

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() ==0 || strs[0]=="") return "";
        if(strs.size() ==1 ) return strs[0];
        for(int i =0 ;; i++){
            for(int k = 1; k<strs.size(); k++){
                if(strs[0][i] != strs[k][i]){
                    if(i>0) return strs[0].substr(0,i);
                    else return "";
                }
            }
        }

        return "";

    }
};

020. Valid Parentheses

Description

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

解法一: 栈

时间复杂度: $O(n)$
空间复杂度: $O(n)$

写法一:

class Solution {
public:
    bool isValid(string s) {
        stack<char> s_brack;

        for(int i = 0; i<s.size(); i++){
            char c='\0';
            if(s[i] == ')') c='(';
            else if(s[i] == ']') c='[';
            else if(s[i] == '}') c='{';
            if(!s_brack.empty() && c ==  s_brack.top()) s_brack.pop();
            else s_brack.push(s[i]);
        }
        if(!s_brack.empty()) return false;
        return true;

    }
};

写法二:

class Solution {
public:
    bool isValid(string s) {
        stack<char> parent;
        for(auto c : s){
            if(c=='(' || c=='{' || c=='[')
                parent.push(c);
            else if(parent.empty()) return false;
            else if((c==')' && parent.top()=='(') ||
                    (c=='}' && parent.top()=='{') ||
                    (c==']' && parent.top()=='[')){
                parent.pop();
            }else
                return false;
        }
        return parent.empty() ? true : false;
    }
};

021. Merge Two Sorted Lists

Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解法一: 遍历融合

时间复杂度: $O(min(m,n))$

空间复杂度: $O(1)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;
        ListNode* head=nullptr;
        if(l1->val < l2->val) {
            head = l1;
            l1 = l1->next;
        }
        else{
            head = l2;
            l2 = l2->next;
        }
        ListNode* cur = head;
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val < l2->val){
                cur->next = l1;
                cur= cur->next;
                l1 = l1->next;
            }else{
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }            
        }
        if(l2==nullptr) cur->next = l1;
        else if(l1 == nullptr) cur->next = l2;
        return head;

    }
};

上面开关头结点的过程过于复杂, 可以用dummy指针简化这个过程

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;
        ListNode* dummy=new ListNode(0);
        ListNode* cur = dummy;
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val < l2->val){
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }else{
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }            
        }
        if(l2==nullptr) cur->next = l1;
        else if(l1 == nullptr) cur->next = l2;
        return dummy->next;

    }
};

026. Remove Duplicates from Sorted Array

Description

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

解法一:

遍历, 两种写法, 后者相当精简

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int same = nums[0];
        int length = 1;
        for(int i=1; i<nums.size(); i++){
            if(nums[i] == same){
                nums.erase(nums.begin()+i);
                i--;
                continue;
            }
            else{
                same = nums[i];
                length++;
            }

        }
        return length;
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;
        int length=1;
        for(auto n:nums){
            if(n>nums[length-1])
                nums[length++]=n;
        }
        return length;
    }
};

028. Implement strStr()

字符串匹配算法, 更详细的解析请看字符串匹配算法解析

description: KMP, 判断是否为子串

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “hello”, needle = “ll”
Output: 2
Example 2:

Input: haystack = “aaaaa”, needle = “bba”
Output: -1
Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

解法一: 暴力

解法二: KMP

求解next数组: 求解某个位置 $k$ 的next数组值是一个循环的过程, 需要不断检查以 位置 $k-1$ 的next值 为下标的元素的 下一位元素 与 当前位置 $k$ 元素 是否相等, 如果相等, 则 next[k] = next[k-1]+1, 如果不相等, 则

038. Count and Say

Description

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
2. 11
3. 21
4. 1211
5. 111221
   1 is read off as “one 1” or 11.
   11 is read off as “two 1s” or 21.
   21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

解法一: 依次查看上一次的数字

时间复杂度: $O(nm)$ m为数字字符串的长度
空间复杂度: $O(m)$

每次根据上一次的数字更新当前的数字字符串, 如此迭代直到达到指定次数

class Solution {
public:
    string countAndSay(int n) {
        string res="1";
        int i=1;
        while(i<n){
            string tmp;
            for(int u=0; u<res.size(); u++){
                char c=res[u];
                int count = 1;
                while(u+1<res.size() && res[u+1]==c){
                    count++;
                    u++;
                }
                tmp += to_string(count)+c;   
            }
            res.swap(tmp);
            i++;
        }
        return res;
    }
};

053. Maximum Subarray

连续子数组的最大和

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解法: 记录当前最大值

时间复杂度: $O(n)$
根据数组性质，设置两个变量，一个记录当前的最大值，一个记录当前的子序列之和。首先，如果当前子序列之和为负，那么就是说，从当前位置开始的子序列，比从之前位置开始的子序列大，那么就可以不考虑从之前位置开始的子序列，之前累计的和也被抛弃

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int max_sum = INT_MIN;  //数组有可能全负, 所以不能赋值为0
        for(auto num : nums){
            if(num > max_sum) max_sum = num; //主要是为了预防数组中全是负数的情况
            sum += num;
            if(sum!=0 && sum>max_sum) max_sum = sum; // sum!=0 , 为了预防数组全负时, 0一定大于sum, 造成的错解
            if(sum <0) sum =0;
        }
        return max_sum;
    }
};

更简洁的写法:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) return 0;
        int tmpRes = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (tmpRes < 0) {
                tmpRes = nums[i];
            } else {
                tmpRes += nums[i];
            }
            res = std::max(res, tmpRes);
        }
        return res;
    }
};

066. Plus One

数组代表一个整数, 模拟整数的加法

Description

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

解法一: 直接模拟

时间复杂度: $O(n)$
空间复杂度: $O(1)$

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 0, last_i = digits.size()-1;
        digits[last_i] += 1;
        if(digits[last_i] > 9) {
            digits[last_i] = 0;
            carry=1;
        }
        for(int i = last_i-1; i>=0 && carry ; i--){
            digits[i] += carry;
            if(digits[i] > 9)
                digits[i] = 0;
            else
                carry = 0;
        }
        if(carry == 1) digits.insert(digits.begin(), 1);
        return digits;
    }
};

另一种写法:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int carry = 0;
        int one = 1;
        int cur = digits.size()-1;
        for(int cur=digits.size()-1; cur>=0; cur--){
            digits[cur] += one + carry;
            one = 0;
            carry = digits[cur] / 10;
            digits[cur] = digits[cur] % 10;
        }
        if(carry) digits.insert(digits.begin(), 1);
        return digits;
    }
};

解法二: 不使用加法(更快更简单, 击败100%)

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {   //未考虑前缀0的情况
        for(int i = digits.size() - 1; i >= 0; i--)   
        {
            if(digits[i] != 9)
            {
                digits[i] ++;
                break;
            }
            digits[i] = 0;
        }
        if(digits[0] == 0)
            digits.insert(digits.begin(), 1);
        return digits;

    }
};

069. Sqrt(x)

实现开方算法

Description

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

解法一: 二分法

时间复杂度: $O(logn)$
空间复杂度: $O(1)$

class Solution {
public:
    int mySqrt(int x) {
        double low=0, high=x;
        double res = high;
        while( std::abs(res*res - x) > 0.00001 ){
            if(res*res > x){
                high = res;
                res = (low+high)/2;
            }else{
                low = res;
                res = (low+high)/2;
            }
        }
        if(ceil(res)*ceil(res)==x) return ceil(res); // 为了能够正确截断, 必须加上此句
        return int(res);
    }
};

解法二: 牛顿迭代法

时间复杂度: $O(logn)$
空间复杂度: $O(1)$

相当于求解 $f(res)=res^2 - x = 0$ 中 $res$ 的解. 则对于任意一点 $(res, f(res))$, 都有切线方程:

$$f(res) - 0 = f'(res)(res-res')$$

其中, $res’$ 是该直线与 $x$ 轴的交点. 令新的 $res$ 为该值, 就可以不断逼近 $f(res)$ 的零点, $res’$ 的值为:

$$res' = res- \frac{f(res)}{f'(res)} = res- \frac{res^2-x}{2\times res} = \frac{res^2 + x}{2\times res}$$

class Solution {
public:
    int mySqrt(int x) {
        double res = x;
        while( std::abs(res*res - x) > 0.00001 ){
            res = (res*res+x) / (2*res);
        }
        if(ceil(res)*ceil(res)==x) return ceil(res); // 为了能够正确截断, 必须加上此句
        return int(res);
    }
};

解法三: 按位检索

时间复杂度: $O(logn)$
空间复杂度: $O(1)$

由于本题要返回的是整数, 而上面的两种方法都是针对double类型的精确开根方法, 时间复杂度为 $O(logn)$, 实际上, 当只需要返回整数时, 我们可以按整数的位进行检索, 而整数总共只有32位(传入的x位int型, 所以开根后不可能超过int), 因此时间复杂度只有 $O(32)$ , 也就是 $O(1)$.

注意: 由于该方法是首先找到比 x 大的那一位, 因此有可能超过int上限, 所以要换成long整型

找到后依然需要进行二分查找来找到最终的返回值

class Solution {
public:
    int mySqrt(int x) {
        long res=0;
        int h=0;
        while( long(1<<h) * long(1<<h) <= x) h++;
        long b = 1<<(h-1);
        while( b > 0){
            if( (res+b) * (res+b) <= x)
                res += b;
            b = b/2;
        }
        return res;

    }
};

070. Climbing Stairs

实际上就是斐波那契数列, 更具体分析可看牛客的跳台阶

Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps
   Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解法一: 递归

解法二: 迭代

class Solution {
public:
    int climbStairs(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        int n1 = 1;
        int n2 = 2;
        for(int i=3; i<=n; i++){
            int temp = n2;
            n2 = n1+n2;
            n1 = temp;
        }
        return n2;
    }
};

088. Merge Sorted Array

融合两个有序数组, 其中第一个数组的元素长度为n, 第二个为m, 题目假设第一个数组的空间为n+m.

Description

解法一: 后移+插入融合

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i =n+m-1; i>=n; i--)
            nums1[i]=nums1[i-n];
        //for(int i =n; i<n+m; i++) 注意, 这样写是有问题的, 例如对于 [1,2,3,4,0], 这种情况, 从前往后的复制方法会造成元素覆盖
          //  nums1[i]=nums1[i-n];
        int i =n, j=0, k=0;
        while(i<n+m && j<n){
            if(nums1[i] < nums2[j]){
                nums1[k] = nums1[i];
                k++; i++;
            }else{
                nums1[k] = nums2[j];
                k++; j++;
            }
        }
        while(i<n+m)
            nums1[k++] = nums1[i++];
        while(j<n)
            nums1[k++] = nums2[j++];
    }
};

101. Symmetric Tree

判断一个二叉树是否为对称的.(与自身镜像相等)

Description

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

  1
 / \
2   2
 \   \
 3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

解法一: 递归

时间复杂度: $O(n)$ , 遍历了整个树中的每个节点一次
空间复杂度: $O(n)$ , 调用递归的次数与树的高度有关, 在最差的情况下, 树的高度为n.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        return isSymHelper(root->left, root->right);
    }

    bool isSymHelper(TreeNode* subRoot1, TreeNode* subRoot2){
        if(subRoot1 == nullptr && subRoot2 == nullptr) return true;
        if(subRoot1 == nullptr || subRoot2 == nullptr) return false;
        if(subRoot1->val != subRoot2->val) return false;

        bool b1 = isSymHelper(subRoot1->left, subRoot2->right);
        bool b2 = isSymHelper(subRoot1->right, subRoot2->left);
        return b1&&b2;
    }
};

更整洁的写法:

class Solution {
    bool is_sym(TreeNode* t1, TreeNode* t2){
        if(t1==nullptr && t2==nullptr) return true;
        if(t1==nullptr || t2==nullptr) return false;
        if(t1->val == t2->val)
            return is_sym(t1->left, t2->right) && is_sym(t2->left, t1->right);
        else return false;
    }
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        return is_sym(root->left, root->right);
    }
};

解法二: 迭代

时间复杂度: $O(n)$ , 遍历了整个树中的每个节点一次
空间复杂度: $O(n)$ , 层次遍历创建了两个队列, 其大小总和刚好为n. (有一种说法是: 层次遍历我们最多只会同时保存两层的节点数, 而最后一层的节点数最多为 $logn$, 所以空间复杂度实际上是 $O(logn)$ (常数项被约掉), 这种说法对吗??)

层次遍历, 注意不应该左子树和右子树做非空检查, 因此判断是否对称时, 需要包含节点为空的情况.(因为不需要知道当前的深度, 所以也不用维护深度信息)

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(root->left);
        q2.push(root->right);
        TreeNode * cur1, * cur2;
        while(!q1.empty() && !q2.empty()){
            cur1 = q1.front(); q1.pop();
            cur2 = q2.front(); q2.pop();
            if(cur1==nullptr && cur2 ==nullptr) continue;
            if(cur1==nullptr || cur2 == nullptr) return false;
            if(cur1->val != cur2->val) return false;
            q1.push(cur1->left); q1.push(cur1->right);
            q2.push(cur2->right); q2.push(cur2->left);
        }
        return true;
    }
};

解法三: 迭代

时间复杂度: $O(n)$
空间复杂度: $O(n)$

只是用一个队列, 对每一层都进行回文检查

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        std::queue<TreeNode*> queueTree;
        queueTree.push(root);
        while (!queueTree.empty()) {
            int len = queueTree.size();
            std::vector<double> vec;
            for (int i = 0; i < len; i++) {
                auto node = queueTree.front();
                queueTree.pop();
                if (node == nullptr) {
                    vec.push_back(0.5);
                } else {
                    vec.push_back(node->val);
                    queueTree.push(node->left);
                    queueTree.push(node->right);
                }
            }
            int n = vec.size();
            for (int i = 0; i < n/2; i++) {
                if (vec[i] != vec[n - i - 1]) {
                    return false;
                }
            }
        }
        return true;
    }
};

104. Maximum Depth of Binary Tree

求二叉树的最大深度(树的深度)

Description

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

解法一: 层次遍历

时间复杂度: $O(n)$
空间复杂度: $O(1)$

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        std::queue<TreeNode*> q;
        q.push(root);
        int depth = 0;
        TreeNode* cur_node;
        while(!q.empty()){
            int layer_len = q.size();
            depth++;
            for(int i=0; i<layer_len; i++){
                cur_node = q.front(); q.pop();
                if(cur_node->left!=nullptr) q.push(cur_node->left);
                if(cur_node->right!=nullptr) q.push(cur_node->right);
            }
        }
        return depth;
    }
};

解法二: 递归

class Solution {
private:
    int height(TreeNode *root){
        if(root == nullptr) return 0;
        int left_height = height(root->left);
        int right_height = height(root->right);
        return 1+max(left_height, right_height);
    }
public:
    int maxDepth(TreeNode* root) {
        return height(root);
    }
};

108. Convert Sorted Array to Binary Search Tree

根据 有序数组 构造平衡二叉搜索树(不唯一, 只要符合规则即可)

Description

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

解法一: 递归构造

时间复杂度: $O(n)$
空间复杂度: $O(n)$, 递归了n次(每个节点都被访问了一次)

由于题目给的条件是 有序数组 , 因此大大降低了了构造难度, 可以每次将数组的中间位置作为根节点, 然后分别将两边的数组作为一个新的子数组进行构造, 无需考虑插入新节点引起的二叉搜索树不平衡的问题.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {

        return construct_BST(nums, 0, nums.size()-1);
    }

    TreeNode* construct_BST(vector<int>& nums, int low, int high){
        if(low>high) return nullptr;
        int mid = (low+high)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = construct_BST(nums, low, mid-1);
        root->right = construct_BST(nums, mid+1, high);
        return root;
    }
};

解法二: 迭代

时间复杂度: $O(n)$, 只不过需要遍历两次树的size
空间复杂度: $O(n)$, 层次遍历的队列和中根遍历的栈

先用层次遍历构造一个完全二叉树(以却确保树是平衡的), 然后在利用中根遍历对树中的每个元素进行赋值.

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int tree_len = nums.size();
        if(tree_len == 0) return nullptr;
        std::queue<TreeNode*> q;
        TreeNode* root = new TreeNode(0);
        q.push(root); tree_len--;
        TreeNode* cur_node;
        int layer_len = 1;
        while(tree_len>0){
            layer_len *= 2;
            for(int i=0; i<layer_len && tree_len>0; i++){
                cur_node = q.front(); q.pop();
                TreeNode* left = new TreeNode(0);
                cur_node->left = left;
                q.push(cur_node->left); tree_len--;
                if(tree_len>0){
                    TreeNode *right = new TreeNode(0);
                    cur_node->right = right;
                    q.push(cur_node->right); tree_len--;
                }
            }
        }

        std::stack<TreeNode*> s;
        cur_node = root;
        int i = 0;
        while(!s.empty() || cur_node!=nullptr){
            while(cur_node!=nullptr){
                s.push(cur_node);
                cur_node = cur_node->left;
            }
            if(!s.empty()){
                cur_node = s.top(); s.pop();
                cur_node->val =nums[i++];
                cur_node = cur_node->right;
            }
        }
        return root;
    }
};

解法三: 迭代(只中根遍历一次)

【链接】Loading…
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35218/Java-Iterative-Solution

111. minimum depth of binary tree

题目描述

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

解法一:

层次优先遍历,遇到的首个叶子结点(左右子树为空)即为最短的深度

注意:

利用while内嵌for循环的方式, 可以省去对每个结点depth的维护, 只需要每次进入for循环之前, depth++即可(因为一个for循环会将当前层所有的结点都入队列, for循环结束后, 意味着进入了下一层, 所以depth++即可)

class Solution {
public:
    int run(TreeNode *root) {
        queue<TreeNode*> q_node;
        if(root==nullptr) return 0;
        q_node.push(root);
        int depth = 0;
        while(!q_node.empty()){
            const int size = q_node.size();
            depth++;
            for(int i = 0; i< size; i++){
                TreeNode* node = q_node.front(); q_node.pop();
                if(node->left!=nullptr) q_node.push(node->left);
                if(node->right!=nullptr) q_node.push(node->right);
                if(node->left==nullptr && node->right == nullptr) return depth;
            }
        }

        return -1;
    }
};

解法二(递归):

让当前结点为空, 则当前结点深度为0, 若当前结点左子树为空, 则当前结点深度等于左子树深度, 反之 ,等于右子树深度. 若当前结点左右子树均不为空, 则当前结点的 最小深度 等于左右子树深度 较小者 加1

class Solution {
public:
    int run(TreeNode* root) {
        if(root== nullptr) return 0;
        if(root->left==nullptr)
            return run(root->right) + 1;
        else if(root->right ==nullptr)
            return run(root->left) + 1;
        else{
            int depth1=run(root->left);
            int depth2=run(root->right);
            return depth1<depth2 ? depth1+1 : depth2+1;
        }
    }
};

118. Pascal’s Triangle

Pascal 三角形

Description

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解法一: 按照三角形的性质进行赋值

赋值时, 每一行的两端都是1, 无需重复赋值, 注意控制好边界条件

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        for(int i =0; i<numRows; i++){
            vector<int> temp(i+1, 1);
            for(int j=1; j<i; j++){ // 两边默认为1, 无需重复赋值
                temp[j] = res[i-1][j-1]+res[i-1][j];// i和j的值只有在大于1时才会进入循环, 所以无需担心i-1或j-1<0
            }
            res.push_back(temp);
        }
        return res;
    }
};

121. Best Time to Buy and Sell Stock

获取最大的股票利润

Description

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

解法一: 穷举

计算所有可能性, $O(n^2)$

解法二: 一次遍历

时间复杂度: $O(n)$
空间复杂度: $O(1)$

维护两个变量 min_price 和 max_profit, 每次检查元素, 一方面如果当前价格更低, 则更改 min_price 变量, 另一方面如果当前利润超过 max_profit, 则更新之.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int min_price=prices[0], max_profit=0;
        for(int i=0; i<prices.size(); i++){
            if(prices[i] <= min_price){
                min_price = prices[i];
            }
            if(prices[i]-min_price > max_profit) max_profit = prices[i]-min_price;
        }
        return max_profit;
    }
};

同样也是一次遍历, 下面的写法更加简洁, 我们这里记录一个变量 buy, 用来指示可能的买入下标, 之后, 如果下一个价格比 buy 对应的价格高, 我们就尝试更新最大利润, 否则, 就改变 buy 到当前的价格下标

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxfit = 0;
        int buy = 0;
        for(int i=1; i<prices.size(); i++){
            if(prices[buy] < prices[i]){
                maxfit = max(maxfit, prices[i] - prices[buy]);
            }else
                buy = i;
        }
        return maxfit;
    }
};

实际上, 我们只需要用一个变量记录迄今为止遇到的最小的股票值即可, 然后对于每一个新值, 我们都更新最高利润和最小值即可, 代码如下:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int low = prices[0];
        int res = 0;
        for (auto const p : prices) {
            res = std::max(res, p - low);
            low = std::min(low, p);
        }
        return res;
    }
};

122. Best Time to Buy and Sell Stock II

可以多次交易, 统计最大利润和

Description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

解法一: 用变量维护最低价格

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(1)$

寻找递增序列, 一旦出现递减的情况, 则说明应该及时卖出, 并将 min_price 重新赋值. 因为最后一个元素后面没有值来判断是否递减, 因此需要对最后一个元素进行单独判断

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() ==0) return 0 ;

        int min_price = prices[0];
        int sum_profit = 0, pre_price=prices[0];
        for(int i=1; i<prices.size(); i++){
            if(prices[i] < pre_price){ //如果小于之前的price, 则说明此时应该卖出
                sum_profit += pre_price-min_price; //计算卖出利润
                min_price = prices[i];
            }
            pre_price = prices[i];
            if(i==prices.size()-1 && prices[i] > min_price) //到了最后一个元素, 查看是否应该卖出
                sum_profit += prices[i] - min_price;
        }
        return sum_profit;
    }
};

同样和上一道题一样, 利用 buy 可以更加整洁的实现:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        int buy = 0;
        for(int i=1; i<prices.size(); i++){
            if(prices[buy] < prices[i])
                max_profit += prices[i] - prices[buy];
            buy = i;
        }
        return max_profit;
    }
};

解法二: 每两个相邻数字当做一次交易

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(1)$

实际上和解法一本质相同, 只不过在累加利润上有一点小区别.
该解法是将每两个相邻数字看做是一次交易, 如果后者大于前者, 说明应该执行交易, 并累加交易所的利润.

Cclass Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum_profit = 0;
        for(int i =1 ; i<prices.size(); i++){
            if(prices[i] > prices[i-1]) sum_profit += prices[i] - prices[i-1];
        }
        return sum_profit;
    }
};

125 Valid Palindrome

判断是否为回文子串

Description

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: “A man, a plan, a canal: Panama”
Output: true
Example 2:

Input: “race a car”
Output: false

解法一: 前后两个指示变量, 向中间遍历判断

时间复杂度: $O(n)$, 遍历一次
空间复杂度: $O(1)$, 只额外用了两个变量

需要注意的是将大小写字母转换成同大写或者同小写的形式再进行判断

写法一:

class Solution {
public:
    bool isPalindrome(string s) {
        for(int i=0, j=s.size()-1; i<j; ){
            if(is_alphanumeric(s[i]) == false){
                i++; continue;
            }
            if(is_alphanumeric(s[j]) == false){
                j--; continue;
            }
            if(std::tolower(s[i]) != std::tolower(s[j])) return false;
            i++; j--;

        }
        return true;
    }

    bool is_alphanumeric(char c){
        if(c>='0' && c<='9') return true;
        else if(c>='a' && c<='z') return true;
        else if(c>='A' && c<='Z') return true;
        else return false;
    }
};

写法二:

class Solution {
public:
    bool isPalindrome(string s) {
        for(int i=0, j=s.size()-1; i<=j;i++,j-- ){
            while(i<s.size() && is_alphanumeric(s[i]) == false) i++;
            while(j>=0 && is_alphanumeric(s[j]) == false) j--;
            if(std::tolower(s[i]) != std::tolower(s[j])) return false;

        }
        return true;
    }

    bool is_alphanumeric(char c){
        if(c>='0' && c<='9') return true;
        else if(c>='a' && c<='z') return true;
        else if(c>='A' && c<='Z') return true;
        else return false;
    }
};

136. Single Number

数组中有一个数字出现了1次(奇数次), 其他均出现了2次(偶数次), 找到出现1次(奇数次)的数字.

Description

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

解法一: 哈希

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(n)$, 哈希表额外空间

遍历数组, 对于每一个数, 如果当前的数存在于hash表中, 则将表中哈希删除, 如果不存在, 则添加到哈希表中, 最终, 哈希表中存在的值就是只出现一次的值

解法二: 数学公式

$2\times (a + b + c) - (a+b+a+b+c) = c$.

将数组中的元素转换为 set(无重复元素), 然后利用上面的公式纠结
时间复杂度: $O(n + n)=O(n)$, 转换为 set 需要 $O(n), 公式求解遍历也需要 $O(n)$
空间复杂度: $O(n)$. set 所占额外空间

解法三: 异或

任何数和0异或不变, 和自身异或变为0

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(auto num : nums)
            res ^= num;
        return res;
    }
};

其他更多扩展问题可看剑指Offer第40题.

141. Linked List Cycle

Description

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

解法一: Floyd Cycle(Floyd 判圈算法)

时间复杂度: $O(n+k)$, 可以认为是$O(n)$, $n$ 为链表长度, $k$ 为环长
空间复杂度: $O(1)$

从头结点开始，slow每次走一步，fast每次走两步，那么只要有环，slow和fast就一定会在环中的某个节点处相遇，如果无环，则fast一定先到达空指针

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr or head->next == nullptr) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        do {
            slow = slow->next;
            fast = fast->next->next;
        } while (slow != fast and fast!=nullptr and fast->next != nullptr);
        return slow == fast ? true : false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr) return false;
        ListNode* slow=head, *fast=head->next;
        while(fast!=nullptr && slow != fast){
            slow= slow->next;
            if(fast->next == nullptr) return false;
            fast = fast->next->next;
        }
        if(fast==nullptr) return false;
        return true;

    }
};

更多扩展见牛客第55题, 链表中环的入口节点

155. Min Stack

获取栈中最小的元素

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); —> Returns -3.
minStack.pop();
minStack.top(); —> Returns 0.
minStack.getMin(); —> Returns -2.

解法一: 两个栈

时间复杂度: $O(1)$
空间复杂度: $O(n)$, 两个栈

申请两个栈, 一个栈正常操作, 另一个栈只有当当前元素小于或等于栈顶元素时才入栈

class MinStack {
private:
    stack<int> s1;
    stack<int> s2;
public:
    /** initialize your data structure here. */

    MinStack(){       

    }

    void push(int x) {
        s1.push(x);
        if(s2.empty() || x <= s2.top()) s2.push(x);
    }

    void pop() {
        if(s1.top() == s2.top()) s2.pop();
        s1.pop();
    }

    int top() {
        return s1.top();
    }

    int getMin() {
        return s2.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

160. Intersection of Two Linked Lists

两个链表的第一个公共节点

Description

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

解法一：栈

时间复杂度: $O(m+n)$, 遍历两个链表
空间复杂度: $O(m+n)$, 两个栈

分析公共子节点的特点，首先，是单向链表，因此，从第一个公共子节点开始，后面的都是一样的，所以最好是能从链表的最后一项还是比较。但由于是单向链表，因此只能从头访问，从能访问最后的节点。 就像是先进先出一样 因此，考虑用两个辅助栈来帮助实现～

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        stack<ListNode*> s1;
        stack<ListNode*> s2;
        for(ListNode* cur = pHead1; cur!=nullptr; cur = cur->next){
            s1.push(cur);
        }
        for(ListNode* cur = pHead2; cur!=nullptr; cur = cur->next){
            s2.push(cur);
        }
        ListNode* firstCN = nullptr;
        while(!s1.empty() && !s2.empty()){
            if(s1.top() == s2.top()){
                firstCN = s1.top();
                s1.pop();
                s2.pop();
            }else
                break;
        }

        return firstCN;
    }
};

解法二: 常数空间复杂度

时间复杂度: $O(m+n)$, 遍历两次
空间复杂度: $O(1)$, 不使用额外空间

首先遍历得到两个链表的长度, 然后先让长链表前进长度差个节点, 接着两个链表共同向前遍历, 当相遇时即为第一个公共节点.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lengthA = 0;
        ListNode* nodeA = headA;
        while (nodeA != nullptr) {
            nodeA = nodeA->next;
            lengthA++;
        }
        int lengthB = 0;
        ListNode* nodeB = headB;
        while (nodeB != nullptr) {
            nodeB = nodeB->next;
            lengthB++;
        }

        ListNode* longNode = lengthA > lengthB ? headA : headB;
        ListNode* shortNode = lengthA > lengthB ? headB : headA;
        int l = std::abs(lengthA - lengthB);
        while (l--) {
            longNode = longNode->next;
        }

        while (shortNode != longNode) {
            shortNode = shortNode->next;
            longNode = longNode->next;
        }
        return shortNode;
    }
};

169 Majority Element

Description: 找出数组中超过一半的数字

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

题目中指明了该数字一定存在, 所以无需进行count检查, 如果该数字有可能不存在, 则根据情况需要进行 $O(n)$ 复杂度的count检查(即检查当前的数字是否出现了大于 n/2 次).

解法一: 排序

时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$

先排序, 然后取中间元素, 即为 majority element.
(如有需要可进行count检查, $O(n)$)

解法二: 哈希

时间复杂度: $O(n)$
空间复杂度: $O(n)$

每个元素的值为哈希的 key, 每个元素出现的次数为哈希的 value, 如果某个 key 的 value 大于 n/2, 则该元素即为 majority element.
哈希法记录的元素的出现次数, 所以无需进行 count 检查.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map< int, int> hash;
        for(auto num: nums){
            hash[num]++;
            if(hash[num] > nums.size()/2) return num;
        }
    }
};

解法三: 同增异减

如果数组中存在这样一个数，那么这个数的出现次数一定大于其他所有数的出现次数总和，因此，设置两个变量，一个 cur_num 用来存储当前数组中的可能解，另一个 count 为统计差值. 即每遇到一个和可能解相同的元素, 就 count++, 否则, count—. 如果 count=0, 则说明当前的可能解已经注定不是最终的解, 则令新的元素为可能解.
最终, 对可能解进行 $O(n)$ 的 count 检查, 判断是否存在 majority element (题目假设一定存在, 所以可以不做此检查).

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = 0;
        int count = 0;
        for (auto const num : nums) {
            if (num == major) {
                count++;
            } else {
                count--;
                if (count < 0) {
                    major = num;
                    count = 1;
                }
            }
        }
        return major; // 因为题目保证major一定存在, 所以可以直接返回, 否则的话还需要再判断major的个数是否大于 n/2
    }
};

解法四: 随机

如果确定数组中存在 majority element 的话, 则我们可以从数组中随机选取一个元素, 并判断这个元素是否为 majority element. 这种解法依赖于统计学的概率知识, 实际的时间复杂度与数组的组成规律有关.

171. Excel Sheet Column Number

Description: Excel列表数字

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...

Example 1:

Input: “A”
Output: 1
Example 2:

Input: “AB”
Output: 28
Example 3:

Input: “ZY”
Output: 701

解法一: 遍历字符串

时间复杂度: $O(n)$
空间复杂度: $O(1)$

class Solution {
public:
    int titleToNumber(string s) {
        int res=0;
        for(auto c : s){
            res += res*25 + int(c-'A') + 1;
        }
        return res;
    }
};

172. Factorial Trailing Zeroes

Description: 阶乘的尾部含有0的个数

解法一: 统计5的个数

首先, 求出阶乘值在取余求0个数的方法肯定不可以, 阶乘会轻松溢出(n=13时就已经 int 溢出了)

时间复杂度: $O(logn)$, 以5位基数
空间复杂度: $O(1)$

因为尾部的0只可能来自于 $2\times 5$ 这样的数, 对于 $n$ 的阶乘 $1\times 2\times 3\times, …, n$ 来说, $2$ 一定是充足的, 所以我们只需要统计 $5$ 的个数就可以.
统计时, 每个5个数字会出现一次5, 每隔25个数字会额外出现一次5, 每个125个数字又会额外出现一次5…, 如此循环下去, 最终5的个数就是尾部0的个数.

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        for(long i =5; n/i >0; i*=5){
            //注意这里的i的字节数一定要大于n, 因为n有可能为INT_MAX, 而 n/i >0 时, i必须>n
            res += n/i;
        }
        return res;
    }
};

解法二: 另一个角度

时间复杂度: $O(logn)$, 以5位基数
空间复杂度: $O(1)$ (迭代), $O(logn)$ (递归需额外空间)

核心思想是相同的, 同样是统计5的出现个数, 只不过这里我们是先求出 n 中 5 的倍数, 然后再求 n/5 中 5 的倍数, 实际上这里就是相当于求 n 中 25 的倍数. 因此, 和解法一是相同的, 只不过解法二因为是通过减小 n, 而不是增大 i (5,25,125,..)的方式来统计 5 个数, 因此解法二有个好处就是可以不使用 long 类型的变量, 下面分别是该方法的递归实现和迭代实现.

递归:

class Solution {
public:
    int trailingZeroes(int n) {
        return n < 5 ? 0 : n / 5 + trailingZeroes(n / 5);        
    }
};

迭代:

class Solution {
public:
    int trailingZeroes(int n) {        
        int res=0;        
        while(n>=5){
            res += n/5;
            n /= 5;            
        }
        return res;
    }
};

189. Rotate Array

Description: 循环右移数组

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

解法一: 暴力

时间复杂度: $O(nk)$
空间复杂度: $O(1)$

所有的数字每次移动一步, 攻移动 k 次. 超时

解法二: 使用额外数组

时间复杂度: $O(n)$
空间复杂度: $O(n)$

申请一个长度相等的数组, 复制原数组中的 $i$ 号元素到新数组中的 $i+k$ 号位置.

解法三: 循环置换

时间复杂度: $O(n)$, 遍历一次
空间复杂度: $O(1)$

每次直接将元素放置在正确的位置, 放置前, 需要用一个临时变量将被放置的元素保存起来以防止覆盖, 然后将临时变量的元素再直接放到正确的位置, 循环进行, 知道临时变量指向了最开始的变量, 然后再继续从下一个元素开始这个过程. 在代码中设置一个 count 变量, 用来统计放置的次数, 当次数等于数组长度时, 说明已经完成移动.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int count=0;
        for(int start=0; count<nums.size(); start++){
            int cur_pos = start;
            int cur_val = nums[start];
            do{
                int next_pos = (cur_pos + k) % nums.size();
                int temp = nums[next_pos];
                nums[next_pos] = cur_val;
                cur_pos = next_pos;
                cur_val = temp;
                count++;
            }while(start!=cur_pos);
        }
    }
};

解法四: reverse

时间复杂度: $O(n)$, 调用扫除 reverse 函数
空间复杂度: $O(1)$

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        std::reverse(nums.begin(), nums.end()-k);
        std::reverse(nums.end()-k, nums.end());
        std::reverse(nums.begin(), nums.end());
    }
};

190. Reverse Bits

Description: 按位逆置

Reverse bits of a given 32 bits unsigned integer.

Example:

Input: 43261596
Output: 964176192
Explanation: 43261596 represented in binary as 00000010100101000001111010011100,
return 964176192 represented in binary as 00111001011110000010100101000000.
Follow up:
If this function is called many times, how would you optimize it?

解法一: 按位进行32次操作

每次取 n 的最后一位, 如果为 1, 则令res左移一位并加一, 如果为0, 则只左移一位. 进行32次(n的32位).

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res= 0;        
        for(int i=0; i<32; i++){
            res = (res<<1) | ((n>>i)&1); //res = (res<<1) | (n&1); n = (n>>1);            
        }
        return res;
    }
};

解法二: 按位二分进行5次操作

先将前16位和后16位交换(利用位移和位操作实现)
然后再将16位中的前8位和后8位交换
然后再将8位中的前4位和后4位交换
然后再将4位中的前2位和后2位交换
最后将2位中的前1位和后1位交换.

上述交换全部采用位操作实现, 因此, 速度上有所优化.

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n>>16) | (n<<16);
        n = ( ((n & 0xff00ff00)>>8) | ((n & 0x00ff00ff)<<8) );
        n = ( ((n & 0xf0f0f0f0)>>4) | ((n & 0x0f0f0f0f)<<4) );
        n = ( ((n & 0xcccccccc)>>2) | ((n & 0x33333333)<<2) );
        n = ( ((n & 0xaaaaaaaa)>>1) | ((n & 0x55555555)<<1) );
        return n;
    }
};

191. Number of 1 Bits

Description: 统计二进制中1的个数

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1:

Input: 11
Output: 3
Explanation: Integer 11 has binary representation 00000000000000000000000000001011
Example 2:

Input: 128
Output: 1
Explanation: Integer 128 has binary representation 00000000000000000000000010000000

解法一: 逐位统计

时间复杂度: $O(1)$, 循环32次
空间复杂度: $O(1)$

查看每一位上的二进制是否为1, 若为1, 则count++

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count=0;
        for(int i=0; i<32; i++){
            if( (n & (1<<i)) != 0) count++;
        }
        return count;
    }
};

解法二: 和 $n-1$ 按位与

时间复杂度: $O(1)$, 循环次数为二进制中1的个数.
空间复杂度: $O(1)$

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count=0;
        while(n!=0){
            count++;
            n = n&(n-1);
        }
        return count;
    }
};

198. House Robber

Description: 房屋小偷获取最大收益

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation:
Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation:
Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

解法一: DP

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(1)$

依据 DP 的思想, 对于一个任意价格的房子, 我们有两种选择: 偷或不偷. 如果选择不偷, 那么前 $(i+1)$ 个房子的最大收益, 就应该是前 $i$ 个房子的最大收益(偷或者不偷第 $i$ 个房子收益中的较大者), 如果选择偷, 那么就不能偷第 $i$ 个房子.
根据上面的描述, 我们可以维护两个变量 cur_rob 和 cur_nrob, 前者代表偷第 $i$ 个房子的收益, 后者代表不偷第 $i$ 个房子的收益, 则最大收益就应该为二者中的较大者. 详细代码如下:

class Solution {
public:
    int rob(vector<int>& nums) {
        int cur_rob=0;
        int cur_nrob=0;
        for(int i =0; i<nums.size(); i++){
            int temp = cur_nrob;
            cur_nrob = std::max(cur_rob, cur_nrob);            
            cur_rob = temp+nums[i];
        }
        return std::max(cur_rob, cur_nrob);
    }
};

解法二: 根据房屋的编号奇偶性

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(1)$

因为偷取的房屋不能相邻, 因此我们可以维护两个变量, even 是前偶数个房屋的最大收益, odd 是前奇数个房屋的最大收益, 对于任意的一个新来的房屋, 如果该新房屋的编号为奇数, 那么它的最大收益就是 odd+new 和 even 当中的较大者(因为不能相邻, 所以只能令 odd+new). 对于偶数的情况同理. 最终返回 odd 和 even 的较大者.(因为有可能包含最后一个元素, 也有可能不包含) 代码如下:

class Solution {
public:
    int rob(vector<int>& nums) {
        int odd=0;
        int even=0;
        for(int i=0; i<nums.size(); i++){
            if(i%2==0) even = std::max(odd, even+nums[i]);
            else odd = std::max(odd+nums[i], even);
        }
        return std::max(odd, even);
    }
};

202. Happy Number

Description: 判断一个数字是否是 Happer Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example:

Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解法一: 模拟计算过程

时间复杂度: $O(logn)$, 基数为10
空间复杂度: 未知, 取决于无序集合的size.

按照题目中的逻辑, 模拟整个计算过程, 如果出现1, 则返回 true, 如果出现循环(即在集合中发现已存在元素), 则返回 false.

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> num_set;
        while(n!=1 && num_set.find(n)==num_set.end()){
            num_set.insert(n);
            int temp = 0;
            while(n!=0){
                temp += (n%10) * (n%10);
                n = n/10;
            }
            n = temp;
        }
        if(n==1) return true;
        return false;
    }
};

解法二: Floyd 判圈算法

时间复杂度: $O(logn)$, 时间复杂度不变
空间复杂度: $O(1)$

利用 Floyd 判圈算法维护两个变量 slow 和 fast, fast 每次都比 flow 多走一步, 那么, 当 fast==1 时, 说明应该返回 true, 当 slow==fast 时, 说明存在循环, 应该返回 false.

class Solution {
public:
    bool isHappy(int n) {
        int slow=n, fast=n;
        do{
            slow = digitSquareSum(slow);
            fast = digitSquareSum(fast);
            fast = digitSquareSum(fast);
        }while(fast!=1 && slow!=fast);
        if(fast == 1) return true;
        return false;
    }
    int digitSquareSum(int n){
        int temp = 0;
        while(n!=0){
            temp += (n%10) * (n%10);
            n = n/10;
        }
        return temp;
    }
};

204. Count Primes

Description: 素数的个数

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

解法一: 填充非素数

时间复杂度: $O(n)$, 至多遍历两次 $n$ 大小的数组, 可优化为只遍历一次.
空间复杂度: $O(n)$, 申请了 $n$ 大小的一维布尔数组来标识是否为负数

如上图, 我们从 $2\times 2$ 开始填充, 将所有能与2相乘切乘积小于 $n$ 的数对应下标置为 false, 然后从 $3\times 3$ 开始填充(注意不是从 $3\times 2$, 因为这样会与前面的 $2\times 3$ 重复), 接着从 $4\times 4$ 开始填充, 因此, 填充的开始位置最大为 $\sqrt{n}$. 另外需要注意的是, 0 和 1 均不是素数.

class Solution {
public:
    int countPrimes(int n) {
        if(n==0 || n==1) return 0;
        int div_n = sqrt(n)+1; // 注意这里是开根号
        vector<bool> is_primes(n, true);
        for(int i=2; i<div_n; i++){            
            for(int j=i*i; j<n; j+=i){
                is_primes[j]=false;
            }
        }
        int res_count=0;
        for(auto primes : is_primes){
            if(primes==true) res_count++;
        }
        return res_count-2; //去掉0和1的情况
    }
};

优化1: 因为任何一个合数都可以拆分成素数的乘积, 因此我们只在当前元素为素数的时候才开始填充, 例如, 对于4, 我们不填充16, 20, ..等数字, 因为这些数字在开始元素为2的时候已经填充过了. 因此, 可以避免这些重复填充, 减少迭代次数, 代码如下(多加了一条if语句).

class Solution {
public:
    int countPrimes(int n) {
        if(n==0 || n==1) return 0;
        int div_n = sqrt(n)+1; // 注意这里是开根号
        vector<bool> is_primes(n, true);
        for(int i=2; i<div_n; i++){    
            if(is_primes[i]){
                for(int j=i*i; j<n; j+=i){
                    is_primes[j]=false;
                }
            }                
        }
        return std::count(is_primes.begin(), is_primes.end(), true)-2; //去掉0和1的情况
    }
};

优化2: 只遍历一次. 首先我们将判断数组isPrime的初始状态设为true, 这样, 每次只在遇到奇数时才检查其是否为素数, 如果该奇数是素数, 那么就将该奇数的倍数全部置为非素数, 同时, 将速度的count加1. 这样, 不仅可以减少判断次数(不再判断偶数), 同时可以在一次遍历的时间内完成素数统计.

class Solution {
public:
    int countPrimes(int n) {
        std::vector<bool> isPrime(n, true); // 默认全是素数
        int upper = std::sqrt(n); // 控制 i*i, 防止越界
        if (n <= 2) return 0; // 判断 0 ~ n-1 是否为素数, 当 n = 2 时, 返回0
        int count = 1; // 2 也为素数
        for (int i = 3; i < n; i+=2) { // 只有奇数才有可能是速度, 并且 1 不是素数
            if (isPrime[i]) {
                count++;
                if (i > upper) continue; // 这里必须进行判断, 否则 i*i 有可能越界
                for (int j = i*i; j < n; j+=i) { // 将 i 的倍数全部置为非素数
                    isPrime[j] = false;
                }
            }
        }
        return count;
    }
};

206. Reverse Linked List

Description: 逆置链表

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

解法一: 迭代

时间复杂度: $O(n)$, 遍历一次链表
空间复杂度: $O(1)$, 借助3个复制指针完成逆置

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr) return head;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* next = head->next;
        while(cur!=nullptr){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

解法二: 递归

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(n)$, 迭代需要占用 $O(n)$ 大小的栈空间

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr || head->next==nullptr) return head;
        ListNode *P = reverseList(head->next); //令下一个开始的节点逆置, 返回新链表的头结点
        head->next->next = head; // 将当前节点逆置
        head->next=nullptr; // 将当前节点的下一个置空, 主要是处理新的尾节点, 其他节点的next会在递归中正确赋值
        return P; //返回新的头结点
    }
};

217. Contains Duplicate

Description: 判断数组中是否有重复元素

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true
Example 2:

Input: [1,2,3,4]
Output: false
Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

解法一: 暴力

时间复杂度: $O(n^2)$, 暴力求解, 双重循环
空间复杂度: $O(1)$, 无需额外空间

时间超限, 无法通过 OJ

解法二: 排序+遍历

时间复杂度: $O(nlogn)$, 先排序, 然后遍历看是否有相邻元素相等, 即 $O(nlogn + n)$, 也就是 $O(nlogn)$.
空间复杂度: $O(1)$, 基于不同的排序算法决定, 使用堆排序则为 $O(1)$.

解法三: unordered_set(哈希)

时间复杂度: $O(n)$, 遍历一遍数组, 在 unordered_set 中查询的复杂度为常数
空间复杂度: $O(n)$, unordered_set占用额外空间

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::unordered_set<int> nums_set;
        for(auto num : nums){
            if(nums_set.find(num) == nums_set.end())
                nums_set.insert(num);
            else
                return true;
        }
        return false;
    }
};

234. Palindrome Linked List

Description: 回文链表判断

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

解法一: 借助辅助数组

时间复杂度: $O(n)$, 两次遍历
空间复杂度: $O(n)$, 额外数组

最简单的做法就是遍历链表, 将其转换成一个可随机访问的数组, 然后进行回文串的判断.

解法二: 不借助辅助数组

时间复杂度: $O(n)$
空间复杂度: $O(1)$

先利用两个指针变量slow和fast找到链表的中点(slow每次走一步, fast每次走两步), 然后将后半段逆置, 接着将前半段和后半段进行比较. 最后根据具体需要将链表后半段复原. (在实际工作中, 不存在 $O(1)$ 空间复杂度的解法, 因为通常情况下是不允许修改链表的值的).

不复原链表:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* node) {
        ListNode* prev = nullptr;
        while(node != nullptr) {
            auto tmp = node->next;
            node->next = prev;
            prev = node;
            node = tmp;
        }
        return prev;
    }
    bool isPalindrome(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        if (fast != nullptr) { // 奇数个节点, 始终令slow指向后半段的开始节点
            slow = slow->next;
        }
        slow = reverseList(slow); // 令slow指向后半段逆置后的开始节点
        fast = head;
        while(slow != nullptr && fast->val == slow->val) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow == nullptr ? true : false;
    }
};

复原链表:

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr || head->next==nullptr) return true;

        ListNode* slow = head;
        ListNode* fast = head->next;

        while(fast!=nullptr && fast->next!=nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *rail = slow; // 记录前半段的最后一个节点, 以便复原链表
        slow = slow->next; // 令slow指向回文串后半段的第一个节点
        ListNode *rhead = reverseList(slow); // 令fast 指向回文串后半段逆置后的连接头(奇数回文串时, 中间的节点算作前半段)
        slow = head;
        fast = rhead;
        bool res=true;
        while(slow!=nullptr && fast!=nullptr){
            if(slow->val != fast->val){
                res = false;
                break;
            }
            slow = slow->next;
            fast = fast->next;
        }        
        rail->next = reverseList(rhead); // 复原链表
        return res;
    }

    ListNode *reverseList(ListNode *cur){
        ListNode* next = cur->next;
        ListNode* pre = nullptr;
        while(cur != nullptr){
            cur->next = pre;
            pre = cur;
            cur = next;
            if(next!=nullptr) next = next->next;
        }
        return pre;
    }
};

237. Delete Node in a Linked List

Description: 删除链表中的某个节点

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list — head = [4,5,1,9], which looks like following:

4 -> 5 -> 1 -> 9

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Note:
The linked list will have at least two elements.
All of the nodes’ values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Do not return anything from your function.

解法一: 复制+跳过节点

时间复杂度: $O(1)$
空间复杂度: $O(1)$

这是一道非常取巧(也可以说是投机)的题, 题目给的参数是需要删除的节点指针, 同时该指针不会是最后一个节点, 因此我们可以利用先复制, 再跳过的方式实现删除.

c/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val; // 题目假设node 不是最后一个节点
        node->next = node->next->next; // 跳过node节点
    }
};

242. Valid Anagram

变位词: 改变某个词或短语的字母顺序后构成的新词或短语

Description: 判断变位词

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

解法一: 排序

时间复杂度: $O(nlogn)$, 对两个字符串进行排序
空间复杂度: $O(1)$, 可以原地排序, 不占用额外空间

对两个字符串排序后, 看是否相等. 该方式可以无缝的解决 Follow up 中的问题.

解法二: 哈希表

时间复杂度: $O(n1+n2)$, $n1$, $n2$ 分别为两个字符串的长度, 二者必须相等, 否则一定不是变位词.
空间复杂度: $O(1)$, 哈希表的 size 为 26, 常数级

构造一个字母哈希表, 先统计

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size()) return false;
        int ana_hash[26]={0};
        for(auto c : s){
            ana_hash[c-'a']++;
        }
        for(auto c : t){
            ana_hash[c-'a']--;
            if (ana_hash[c-'a'] < 0)
                return false;
        }
        /*
        因为长度相等, 所以一旦不是异构词, 就一定会出现某个哈希位上的值小于0的情况, 因此无需在这里再次判断
        for(auto i : ana_hash){
            if(i != 0) return false;
        }
        */
        return true;
    }
};

解答 Follow up:

用 unordered_map 来代替数组哈希表, 此时复杂度与输入的字符种类数目有关, 哈希表的空间复杂度变成 $O(n)$.

268. Missing Number

Description: 缺失的数字

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2
Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

解法一: 排序

时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$ 或 $O(n)$

解法二: 哈希表

时间复杂度: $O(n)$, 两次遍历, 第一次构建哈希, 第二次查询缺失数字
空间复杂度: $O(n)$, 哈希表所占空间

另一种解法: 用下表做哈希, 将数字放置在与下标相同的位置上, 最终放错位置的元素的下标就是缺失的数字, 如果位置都正确, 则缺失 n. 复杂度与哈希表相同, 代码实现如下:

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ) {
            if (i != nums[i] && nums[i] < n) {
                std::swap(nums[i], nums[nums[i]]);
            } else {
                i++;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i != nums[i]) {
                return i;
            }
        }
        return n;
    }
};

解法三: 异或

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(1)$, 无需额外空间

因为题目是从 0, 1, 2, ..., n 共 $n+1$ 个数字中选出了 $n$ 个不相同的数字, 因此, 如果将 $n+1$ 大小的数组和 $n$ 大小的数组合并成一个大数组, 那么在大数组中, 除了那个缺失的数字以外, 所有的数字都恰好出现了两次, 因此题目变成了求数组中出现一次的唯一数字, 此时可以利用异或在 $O(n)$ 时间复杂度内解决.

该解法还可以解决丢失两个数字, 丢失三个数字的情况, 具体可参考用异或解决奇数偶数数字的问题.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = n;
        for(int i=0; i<n; i++){
            res = res ^ i ^ nums[i];
        }
        return res;
    }
};

解法四: 高斯求和公式

时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(1)$, 无需任何额外空间

前 $n$ 项和的求和公式为: $1+2+3+\cdots+n = \frac{(n+1)n}{2}$
因此, 我们只需要计算出当前数组的和, 然后在计算当前和与高斯和之间的差即可.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int gauss_sum = n*(n+1)/2;
        int sum = 0;
        for(auto num : nums)
            sum += num;
        return gauss_sum - sum;
    }
};

283. Move Zeroes

Description: 将 0 移动到最后, 保持其他元素相对位置不变

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

解法一: 交换法

时间复杂度: $O(n)$
空间复杂度: $O(1)$, 无需额外空间

利用交换将不符合要求的元素交换, 具体做法如下:

1. 令 i 指向第一个 0 元素;
2. 令 j 指向 i 之后的第一个非 0 元素; (注意 j 必须在 i 的后面才能执行交换)
3. 交换 i 和 j 指向的元素, 更新 i 和 j 的值.
4. 重复以上步骤, 直到 j 越界.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0, j = 0;
        while(nums[i]!=0) i++;
        j = i;
        while(nums[j]==0) j++;

        while(j < nums.size()){
            std::swap(nums[i], nums[j]);
            while(nums[i]!=0) i++;
            j = i;
            while(nums[j]==0) j++;
        }
        return;
    }
};

解法二: 更简洁的交换法

时间复杂度: $O(n)$
空间复杂度: $O(1)$

这道题可以从另一个角度来理解, 即可以看做是要将所有的非 0 元素保持相对位置不变地移动到数组的前面, 那么我们可以遍历数组, 并用一个变量 i 来记录当前元素之前的非 0 元素的个数, 那么如果当前元素为非 0 元素, 则可以令当前元素与 nums[i] 交换, 同时 i++, 这样便可以同时保证将非 0 元素移动到数组前以及保持相对位置不变两个条件.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int i=0, j=0; j<nums.size(); j++){
            if(nums[j] != 0){
                std::swap(nums[i], nums[j]);
                i++; // 非0元素个数加1
            }
        }
        return;
    }
};

326. Power of Three

Description: 三的幂次

Given an integer, write a function to determine if it is a power of three.

Example 1:

Input: 27
Output: true

Example 2:

Input: 0
Output: false

Example 3:

Input: 9
Output: true

Example 4:

Input: 45
Output: false

解法一: 自下而上(超时)

时间复杂度: $O(logn)$, 计算3的幂次, 总共需要计算 $log_3n$ 次
空间复杂度: $O(1)$

该方法从 3 开始, 逐渐计算 3 的幂次, 但是由于对于任何数都要计算 $log3n$ 次, 故当数很大时会超时

class Solution {
public:
    bool isPowerOfThree(int n) {        
        int pow = 1;
        while(pow < n){
            pow = pow*3;
        }
        return pow==n ? true : false;
    }
};

解法二: 自上而下

时间复杂度: $O(logn)$, 利用除法判断是否能整除 3, 当不能整除时, 可以提前退出, 起到剪枝效果, 最多需要计算 $log_3n$ 次
空间复杂度: $O(1)$

解法一采用的自下而上的乘法方法对于任何的数字都需要进行 $log_3n$ 次乘法才能判断是否为 3 的幂次, 这显然是不需要的, 我们只需要利用除法, 不断判断是否能被 3 整除即可, 一旦发现不能整除, 则肯定不是 3 的幂次, 可提前退出, 代码如下:

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n<1) return false;        
        while (n%3 == 0){
            n /= 3;
        }
        return n==1;
    }
};

解法三: 进制转换(不使用循环或迭代)

十进制的 pow 形式为: 10, 100, 1000 (分别代表十, 一百, 一千)
二进制的 pow 形式为: 10, 100, 1000 (分别代表二, 四, 八)
因此我们可以推出三进制的形式为: 10, 100, 1000 (分别代表三, 九, 二十七)

故此, 我们可以将十进制先转换成三进制, 然后判断三进制形式是否首位为一, 其他位均为零, 如果满足, 则说明当前的数字是三的幂次. 该方法不需要循环和迭代(实际上在转换的过程仍然使用了循环和迭代).

344. Reverse String

Description: 反转字符串

Write a function that takes a string as input and returns the string reversed.

Example 1:

Input: "hello"
Output: "olleh"

Example 2:

Input: "A man, a plan, a canal: Panama"
Output: "amanaP :lanac a ,nalp a ,nam A"

解法一: 使用 reverse 函数

时间复杂度: $O(n)$
空间复杂度: $O(1)$

class Solution {
public:
    string reverseString(string s) {        
        std::reverse(s.begin(), s.end());
        return s;
    }
};

解法二: 基于 swap

时间复杂度: $O(n)$
空间复杂度: $O(1)$

class Solution {
public:
    string reverseString(string s) {
        int len = s.size();
        for(int i=0; i<len/2; i++){
            std::swap(s[i], s[len-1-i]);
        }
        return s;
    }
};

350. Intersection of Two Arrays II

Description: 求两数组的交集

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

解法一: 哈希

时间复杂度: $O(n1+n2)$, 构建哈希表和查询哈希表, 需要将两数组的元素都遍历一次
空间复杂度: $O(n1)$, 用 nums1 构建哈希表, 然后用 nums2 进行查询.(也可以多做一步判断, 选择用数组长度较小数组来构建哈希表, 减少空间复杂度)

用一个数组构建哈希表, 哈希表的键为元素值, 哈希表的值为元素的出现次数, 然后用另一个数组的元素对哈希表进行查询, 如果能找到, 则将该元素加入结果数组 res, 并将哈希表对应键的值减一, 如果减到零, 则删除该键.

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> hash; // 构建哈希
        for(auto &num : nums1) hash[num]++;

        vector<int> res;
        for(auto &num : nums2){
            if(hash.find(num) != hash.end()){
                res.push_back(num);
                hash[num]--;
                if(hash[num]==0) hash.erase(num); // 当键对应值为0时, 将该键擦除                    
            }
        }
        return res;
    }
};

解法二: 排序

时间复杂度: $O(n1logn1 + n2logn2 + n1 + n2) = max(n1, n2)\times log(max(n1, n2))$
空间复杂度: $O(1)$

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());

        int i1=0, i2=0; // 设置两个指示变量
        vector<int> res;
        while(i1<nums1.size() && i2<nums2.size()){
            if(nums1[i1] == nums2[i2]){
                res.push_back(nums1[i1]);
                i1++;
                i2++;
            }else if(nums1[i1] < nums2[i2])
                i1++;
            else
                i2++;                
        }        
        return res;
    }
};

Follow up

当给定数组已经有序时

可以设置两个指示变量, 分别指向两个数组, 然后按照指向元素的大小关系进行判断并递进, 这样, 时间复杂度为 $O(n1+n2)$, 空间复杂度为 $O(1)$, 代码可见解法二.

当 nums1 远远小于 nums2 时

正如前面所说, 选用元素数量较少的数组来构建哈希表, 可以降低空间复杂度

如果 nums2 存放在磁盘上, 同时内存不足以加载整个 nums2 数组

将 nums2 分片, 逐个求交集, 最后再合并

371. Sum of Two Integers

Description: 不用加减乘除做加法

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = -2, b = 3
Output: 1

解法一: 位操作(递归)

对于两个数相加, 例如 759+674, 在计算机中我们可以按照如下步骤求解:

1. 不考虑进位, 相加得到 323;
2. 只考虑进位, 进位为 1110;
3. 将上面两个数字相加, 得到 1433, 即为最终结果

因此, 我们可以用 异或 求得不考虑进位的加, 用 与操作 来得到当前数字的进位, 由于进位与数字相加后, 有可能产生新的进位, 所以我们还要假设将新的进位加上, 直到进位位为0, 此时可以此时返回当前的和, 代码如下所示

class Solution {
public:
    int getSum(int a, int b) {
        if(b==0) return a ; // 如果进位为0, 则可直接返回
        int sum = a ^ b; // 计算不带进位的加法
        int carry = (a & b) << 1;  // 计算进位
        return getSum(sum, carry); // 结合并返回        
    }
};

上面的代码可以简化成一行:

class Solution {
public:
    int getSum(int a, int b) {        
        return b==0 ? a : getSum(a^b, (a&b)<<1);
    }   
};

解法二: 位操作(迭代)

思路和解法一相同, 只不过写成了迭代的形式

class Solution {
public:
    int getSum(int a, int b) {        
        while(b!=0){
            int tmp = a ^ b; // 不考虑进位的加
            b = (a&b) << 1; // 进位
            a = tmp;
        }
        return a;
    }   
};

387. First Unique Character in a String

Description: 寻找字符串中的首个不重复字符

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

解法一: 哈希表

时间复杂度: $O(n+n)=O(n)$, 第一个 $n$ 用于建立哈希表, 第二个 $n$ 用于查询首个出现次数为 1 的字符, $n$ 为字符串的长度
空间复杂度: $O(26)$, 哈希表的大小为字符集的大小 26 (如果是 unicode 字符, 就为 256).

遍历两边字符串, 第一遍构建哈希表, 第二遍按照字符串序列查询, 遇到值 1 的字符出现时, 就将其下标返回

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> hash;
        for(auto c : s){
            hash[c]++;
        }
        for(int i=0; i<s.size(); i++){
            if(hash[s[i]]==1) return i;
        }
        return -1;
    }
};

412. Fizz Buzz

Description: 输出指定字符串

Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:

n = 15,

Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

解法一: 条件判断直接输出

时间复杂度: $O(n)$
空间复杂度: $O(1)$

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> res;
        for(int i=1; i<=n; i++){
            if(i%15==0)
                res.push_back("FizzBuzz");
            else if(i%5==0)
                res.push_back("Buzz");
            else if(i%3==0)
                res.push_back("Fizz");
            else
                res.push_back(std::to_string(i));
        }
        return res;
    }
};