Ascendlogo

Posted on Edited on In

70.Climbing Stairs

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

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

Example 1:

1
2
3
4
5
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: n = 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

动态规划：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q; 
        q = r; 
        r = p + q;//爬到第r阶楼梯可能用1步或2步故第r阶楼梯等于第r-1阶加第r-2阶
    }
    return r;
}

快速矩阵幂：

  • 时间复杂度：O(log ⁡n)
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {
        vector<vector<long long>> c(2, vector<long long>(2));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }

    vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {
        vector<vector<long long>> ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    int climbStairs(int n) {
        vector<vector<long long>> ret = {{1, 1}, {1, 0}};
        vector<vector<long long>> res = matrixPow(ret, n);
        return res[0][0];
    }
};

Posted on Edited on In

69.Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

Example 1:

1
2
3
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

1
2
3
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

个人解答：

1
2
3
4
5
int mySqrt(int x) {
        long long i = 0;
        while(i*i <= x)i++;
        return i-1;
    }

二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
int mySqrt(int x) {
    int l = 0, r = x, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if ((long long)mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

牛顿迭代：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }

    double C = x, x0 = x;
    while (true) {
        double xi = 0.5 * (x0 + C / x0);
        if (fabs(x0 - xi) < 1e-7) {
            break;
        }
        x0 = xi;
    }
    return int(x0);
}

Posted on Edited on In

67.Add Binary

Given two binary strings a and b, return their sum as a binary string.

Example 1:

1
2
Input: a = "11", b = "1"
Output: "100"

Example 2:

1
2
Input: a = "1010", b = "1011"
Output: "10101"

个人解答：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
string addBinary(string a, string b) {
    string ans_str = "";
    int a_size = a.size();
    int b_size = b.size();
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    if (a_size < b_size) {
        int temp = b_size - a_size;
        while (temp--)a += "0";
    }
    else {
        int temp = a_size - b_size;
        while (temp--)b += "0";
    }
    char carry = '0';
    for (int i = 0; i < a_size || i<b_size; ++i) {
        if (a[i] + b[i] + carry == 144) {//'0'+'0'+'0' ASCII
            ans_str += "0";
            carry = '0';
        } 
        else if (a[i] + b[i] + carry == 145) {//'1'+'0'+'0' ASCII
            ans_str += "1";
            carry = '0';
        } 
        else if (a[i] + b[i] + carry == 146) {//'1'+'1'+'0' ASCII
            ans_str += "0";
            carry = '1';
        } 
        else if (a[i] + b[i] + carry == 147) {//'1'+'1'+'1' ASCII
            ans_str += "1";
            carry = '1';
        } 
        else cout << "mistake" << endl;
    }
    if (carry == '1')ans_str += "1";
    reverse(ans_str.begin(), ans_str.end());
    return ans_str;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
string addBinary(string a, string b) {
    if (a.empty()) return b;
    if (b.empty()) return a;
    int index_a = a.size() - 1;
    int index_b = b.size() - 1;
    int carry = 0;
    int bit_a = 0, bit_b = 0;
    string result;
    const int radix = 2;
    while (index_a >= 0 || index_b >= 0) {
        bit_a = 0, bit_b = 0;
        if (index_a >= 0) {
            bit_a = a[index_a] - '0';
        }
        if (index_b >= 0) {
            bit_b = b[index_b] - '0';
        }
        auto sum = bit_a + bit_b + carry;
        auto bit = sum % radix;
        carry = sum / radix;
        result += bit + '0';
        --index_a;
        --index_b;
    }
    if (carry) {
        result += carry + '0';
    }
    reverse(begin(result), end(result));
    return result;
}

Posted on Edited on In

66.Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0‘s.

Increment the large integer by one and return the resulting array of digits.

Example 1:

1
2
3
4
5
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

1
2
3
4
5
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

1
2
3
4
5
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

个人解答：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> plusOne(vector<int>& digits) {
    int digits_size = digits.size();
    if (digits[digits_size - 1] != 9) {
        digits[digits_size - 1] += 1;
        return digits;
    }
    else {
        if (digits_size == 1)return{ 1,0 };
        int index = digits_size - 2;
        digits[digits_size - 1] = 0;
        while (digits[index] == 9) {
            digits[index] = 0;
            index--;
            if (index == -1) {
                vector<int> digits(digits_size + 1);
                digits[0] = 1;
                while (digits_size > 0) {
                    digits[digits_size] = 0;
                    digits_size--;
                }
                return digits;
            }
        }
        digits[index] += 1;
        return digits;
    }
}

Posted on Edited on In

58.Length of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:

1
2
3
Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:

1
2
3
Input: s = "   fly me   to   the moon  "
Output: 4
Explanation: The last word is "moon" with length 4.

Example 3:

1
2
3
Input: s = "luffy is still joyboy"
Output: 6
Explanation: The last word is "joyboy" with length 6.

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
int lengthOfLastWord(string s) {
    int s_size = s.size();
    int count = 0;
    for (int i = s_size; i >= 0; --i) {
        if (isalpha(s[i]))
            count++;
        else {
            if (count > 0)
                return count;
        }
    }
    return count;//单词前不存在空格的情况
}

Posted on Edited on In

35.Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

1
2
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

1
2
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

1
2
Input: nums = [1,3,5,6], target = 7
Output: 4

个人解答：

时间复杂度O(logn)；

空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1, ans = n;
    while (left <= right) {
        int mid = left + ((right - left) / 2);
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return ans;
}

Posted on Edited on In

27.Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

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

Example 1:

1
2
3
4
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

1
2
3
4
5
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

个人解答：

时间复杂度：O(n^2)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
int removeElement(vector<int>& nums, int val) {
    vector<int>::iterator pos = find(nums.begin(), nums.end(), val);
    while (pos != nums.end()) {
        nums.erase(pos);
        pos = find(nums.begin(), nums.end(), val);
    }
    return nums.size();
}

双指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
int removeElement(vector<int>& nums, int val) {
    int left = 0, right = nums.size();
    while (left < right) {
        if (nums[left] == val) {
            nums[left] = nums[right - 1];
            right--;
        }
        else {
            left++;//直到right指针指向数据不等于val,left左移
        }
    }
    return left;
}

Posted on Edited on In

26.Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

return k after placing the final result in the first k slots of nums.

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

Example 1:

1
2
3
4
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

1
2
3
4
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
int removeDuplicates(vector<int>& nums) {
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    return nums.size();
}

双指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int removeDuplicates(vector<int>& nums) {
    int nums_size = nums.size();
    if (nums_size == 1)return 1;
    int left = 0;
    int right = 1;
    while (right < nums_size) {
        if (nums[right] != nums[left]) {
            if (right - left > 1) {//right和left相邻不用复制
                nums[left + 1] = nums[right];
            }
            left++;
        }
        right++;
    }
    return left+1;
}
1
2
3
4
5
6
7
8
9
10
int removeDuplicates(vector<int> arr) {
    if (arr.empty()) return 0;
    int index = 0;
    for (int val : arr) {
        if (val != arr[index]) {
            arr[++index] = val;
        }
    }
    return index + 1;
}

Posted on Edited on In

21.Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

img

1
2
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

1
2
Input: list1 = [], list2 = []
Output: []

Example 3:

1
2
Input: list1 = [], list2 = [0]
Output: [0]

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* ans_list = new ListNode;
    ListNode* node = ans_list;
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            node->next = list1;
            list1 = list1->next;
        }
        else {
            node->next = list2;
            list2 = list2->next;
        }
        node = node->next;
    }
    node->next = list1 == nullptr ? list2 : list1;//将未合并完的一个链表直接接在ans_list之后
    return ans_list->next;
}

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) {
        return l2;
    } else if (l2 == nullptr) {
        return l1;
    } else if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

Posted on Edited on In

20.Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

1
2
Input: s = "()"
Output: true

Example 2:

1
2
Input: s = "()[]{}"
Output: true

Example 3:

1
2
Input: s = "(]"
Output: false

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
bool isValid(string s) {
    int s_size = s.size();
    stack<char> stack_char;
    for (char c:s) {
        if (c == '(' || c == '{' || c == '[')stack_char.push(c);
        else if (!stack_char.empty() && c == ')' && stack_char.top() == '(')stack_char.pop();
        else if (!stack_char.empty() && c == ']' && stack_char.top() == '[')stack_char.pop();
        else if (!stack_char.empty() && c == '}' && stack_char.top() == '{')stack_char.pop();
        else return false;
    }
    return stack_char.empty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char, char> m{{')', '('}, {'}', '{'}, {']', '['}};
        for (char c: s) {
            switch (c) {
                case ')':
                case ']':
                case '}':
                    if (st.empty() || m[c] != st.top()) return false;
                    st.pop();
                    break;
                default:
                    st.push(c);
                    break;
            }
        }
        return st.empty();
    }
};