Ascendlogo

Posted on Edited on In

258.Add Digits

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

1
2
3
4
5
6
Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

Example 2:

1
2
Input: num = 0
Output: 0

个人解答：

时间复杂度：O(log num)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int addDigits(int num) {
        int sum = 0;
        do {
            while(num != 0) {
                sum += num%10;
                num/=10;
            }
            num = sum;
            sum = 0;
        }while(num > 9);
        return num;
    }
};

进阶：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
class Solution {
public:
    int addDigits(int num) {
        return (num - 1) % 9 + 1;
    }
};

Posted on Edited on In

257.Binary Tree Paths

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

img

1
2
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

1
2
Input: root = [1]
Output: ["1"]

深度优先遍历：

时间复杂度：O(n2)

空间复杂度：O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> ret;
    void next(TreeNode* root, string path) {
        if (root != nullptr) {
            path += to_string(root->val);
            if (root->left != nullptr || root->right != nullptr) {
                path += "->";
                next(root->left, path);
                next(root->right, path);
            }
            else {
                ret.push_back(path);
            }
        }
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        next(root,"");
        return ret;
    }
};

广度优先遍历：

时间复杂度：O(n2)

空间复杂度：O(n2)

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
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if (root == nullptr) {
            return paths;
        }
        queue<TreeNode*> node_queue;
        queue<string> path_queue;

        node_queue.push(root);
        path_queue.push(to_string(root->val));

        while (!node_queue.empty()) {
            TreeNode* node = node_queue.front(); 
            string path = path_queue.front();
            node_queue.pop();
            path_queue.pop();

            if (node->left == nullptr && node->right == nullptr) {
                paths.push_back(path);
            } else {
                if (node->left != nullptr) {
                    node_queue.push(node->left);
                    path_queue.push(path + "->" + to_string(node->left->val));
                }

                if (node->right != nullptr) {
                    node_queue.push(node->right);
                    path_queue.push(path + "->" + to_string(node->right->val));
                }
            }
        }
        return paths;
    }
};

Posted on Edited on In

242.Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

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

排序法：

时间复杂度：O(nlogn)

空间复杂度：O(logn)

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

哈希表：

时间复杂度：O(n)

空间复杂度：O(s)，s为字符集大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        vector<int> table(26, 0);
        for (auto& ch: s) {
            table[ch - 'a']++;
        }
        for (auto& ch: t) {
            table[ch - 'a']--;
            if (table[ch - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

Posted on Edited on In

234.Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

img

1
2
Input: head = [1,2,2,1]
Output: true

Example 2:

img

1
2
Input: head = [1,2]
Output: false

递归法：

时间复杂度：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
class Solution {
public:
    ListNode* frontPointer;
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) {
                return false;
            }
            if (currentNode->val != frontPointer->val) {
                return false;
            }
            frontPointer = frontPointer->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

这种方法不仅使用了 O(n)的空间，且比将链表复制到数组方法更差，因为在许多语言中，堆栈帧的开销很大（如 Python），并且最大的运行时堆栈深度为 1000（可以增加，但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小。

快慢指针：

时间复杂度：O(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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

Posted on Edited on In

232.Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.
  • int pop() Removes the element from the front of the queue and returns it.
  • int peek() Returns the element at the front of the queue.
  • boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

两个堆栈：

时间复杂度：O(1)

空间复杂度：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
class MyQueue {
public:
    stack<int> stk1;
    stack<int> stk2;
    MyQueue() {

    }

    void push(int x) {
        while(!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        stk2.push(x);
        while(!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }
    }

    int pop() {
        int value = stk1.top();
        stk1.pop();
        return value;
    }

    int peek() {
        return stk1.top();
    }

    bool empty() {
        return stk1.empty();
    }
};

Posted on Edited on In

231.Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Example 1:

1
2
3
Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

1
2
3
Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

1
2
Input: n = 3
Output: false

个人解答：

时间复杂度：O(logn)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isPowerOfTwo(int n) {
        long num = 1;
        while (num <= n) {
            if (num == n)return true;
            num *= 2;
        }
        return false;
    }
};

位运算：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};

约数法：

时间复杂度：O(1)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
class Solution {
private:
    static constexpr int BIG = 1 << 30;
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && BIG % n == 0;
    }
};

Posted on Edited on In

228.Summary Ranges

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

  • "a->b" if a != b
  • "a" if a == b

Example 1:

1
2
3
4
5
6
Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Example 2:

1
2
3
4
5
6
7
Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int nums_size = nums.size();
        if(nums_size == 0)return {};
        if(nums_size == 1)return {to_string(nums[0])};
        vector<string> ans_vec;
        for (int i = 0; i < nums_size-1; i++) {
            if (nums[i] != nums[i + 1] - 1)
                ans_vec.push_back(to_string(nums[i]));
            else {
                int temp = nums[i];
                while (i < nums_size - 1 && nums[i] == nums[i + 1] - 1)i++;
                ans_vec.push_back(to_string(temp) + "->" + to_string(nums[i]));
            }
        }
        if(nums[nums_size-1]!=nums[nums_size-2]+1)
            ans_vec.push_back(to_string(nums[nums_size-1]));
        return ans_vec;
    }
};

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ret;
        int i = 0;
        int n = nums.size();
        while (i < n) {
            int low = i;
            i++;
            while (i < n && nums[i] == nums[i - 1] + 1) {
                i++;
            }
            int high = i - 1;
            string temp = to_string(nums[low]);
            if (low < high) {
                temp.append("->");
                temp.append(to_string(nums[high]));
            }
            ret.push_back(move(temp));
        }
        return ret;
    }
};

Posted on Edited on In

226.Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

img

1
2
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

img

1
2
Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

1
2
Input: root = []
Output: []

递归法：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void tree_next(TreeNode* root) {
        if(!root)return;
        tree_next(root->left);
        tree_next(root->right);
        TreeNode* temp;
        temp = root->right;
        root->right = root->left;
        root->left = temp;
    }
    TreeNode* invertTree(TreeNode* root) {
        tree_next(root);
        return root;
    }
};

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

Posted on Edited on In

225.Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.
  • int pop() Removes the element on the top of the stack and returns it.
  • int top() Returns the element on the top of the stack.
  • boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

  • You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
  • Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

两个队列：

时间复杂度：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
39
40
class MyStack {
public:
    queue<int> que1;
    queue<int> que2;
    MyStack() {

    }

    void push(int x) {
        que2.push(x);
        while(!que1.empty()) {
            que2.push(que1.front());
            que1.pop();
        }
        swap(que1,que2);
    }

    int pop() {
        int r = que1.front();
        que1.pop();
        return r;
    }

    int top() {
        return que1.front();
    }

    bool empty() {
        return que1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

一个队列：

时间复杂度：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
39
class MyStack {
public:
    queue<int> que;
    MyStack() {

    }

    void push(int x) {
        int que_size = que.size();
        que.push(x);
        while(que_size--) {
            que.push(que.front());
            que.pop();
        }
    }

    int pop() {
        int r = que.front();
        que.pop();
        return r;
    }

    int top() {
        return que.front();
    }

    bool empty() {
        return que.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

Posted on Edited on In

219.Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

哈希表：

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int nums_size = nums.size();
        for (int i = 0; i < nums_size; i++) {
            int num = nums[i];
            if (hash.count(num) && i - hash[num] <= k)return true;
            hash[num] = i;
        }
        return false;
    }
};

滑动窗口：

时间复杂度：O(n)

空间复杂度：O(k+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> hash;
        int nums_size = nums.size();
        for (int i = 0; i < nums_size; i++) {
            if (i > k)hash.erase(nums[i - k - 1]);
            if (hash.count(nums[i]))return true;
            hash.emplace(nums[i]);
        }
        return false;
    }
};