题目

原题在此

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
  Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Example 1:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:
Input: root = [0,null,1]
Output: [1,null,1]

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

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

Constraints:

• The number of nodes in the tree is in the range [0, $10^4$].
• $-10^4$ <= Node.val <= $10^4$
• All the values in the tree are unique.
• root is guaranteed to be a valid binary search tree.

解析

以右中左的顺序遍历BST, 将节点的值累加写入. 右中左的遍历就是把Inorder反过来.

代码

recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return NULL;
        sum(root, 0);
        return root;
    }
    int sum(TreeNode* root, int large){
        if(!root) return large;
        root->val += sum(root->right, large);
        return sum(root->left, root->val);
    }
};

iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        TreeNode* tmp = root;
        stack<TreeNode*> s;
        int sum = 0;
        while(tmp || !s.empty()){
            while(tmp){
                s.push(tmp);
                tmp = tmp -> right;
            }
            tmp = s.top();
            s.pop();
            sum += tmp -> val;
            tmp -> val = sum;
            tmp = tmp -> left;                                
        }
        return root;
    }
};

题目

原题在此

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().

Example:

Assume that the iterator is initialized to the beginning of the list: [1,2,3].

Call next() gets you 1, the first element in the list.
Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
You call next() the final time and it returns 3, the last element.
Calling hasNext() after that should return false.
Follow up: How would you extend your design to be generic and work with all types, not just integer?

解析

next()和hasNext()直接调用Iterator的就好, peek()可以copy一个再调用next().

代码

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

/*
 * Below is the interface for Iterator, which is already defined for you.
 * **DO NOT** modify the interface for Iterator.
 *
 *  class Iterator {
 *		struct Data;
 * 		Data* data;
 *		Iterator(const vector<int>& nums);
 * 		Iterator(const Iterator& iter);
 *
 * 		// Returns the next element in the iteration.
 *		int next();
 *
 *		// Returns true if the iteration has more elements.
 *		bool hasNext() const;
 *	};
 */

class PeekingIterator : public Iterator {
public:
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
	    
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	int peek() {
        return Iterator(*this).next();
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() {
	    return Iterator::next();
	}
	
	bool hasNext() const {
	    return Iterator::hasNext();
	}
};

题目

原题在此

Given a string s and a character c that occurs in s, return an array of integers answer where answer.length == s.length and answer[i] is the shortest distance from s[i] to the character c in s.

Example 1:
Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]

Example 2:
Input: s = "aaab", c = "b"
Output: [3,2,1,0]

Constraints:
1 <= s.length <= $10^4$
s[i] and c are lowercase English letters.
c occurs at least once in s.

解析

找到第一个和最后一个c, 第一遍从第一个c到s.end()按规则填写, 第二遍从最后一个c到s.begin()按规则填写或如果已填写的值较小则跳过.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        vector<int> res(s.size(), INT_MAX);
        int first = s.find(c), last = s.find_last_of(c);
        int n = s.size(), tmp = 0;
        for(int i = first; i < n; ++i) {
            if(s[i] == c) tmp = 0;
            res[i] = tmp++;
        }
        tmp = 0;
        for(int i = last; i >= 0; --i) {
            if(!res[i]) tmp = 0;
            res[i] = min(res[i], tmp++);
        }
        return res;
    }
};

题目

原题在此

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]

Explanation:

1
2
3
4
5
6

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

解析

使用反向BFS, 先右后左, 在遍历每一层的第一个节点是将此节点值插入vector.

代码

C++

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<int> res;
        TreeNode* tmp;
        while(!q.empty()) {
            res.push_back(q.front() -> val);
            int n = q.size();
            for(int i = 0; i < n; ++i) {
                tmp = q.front();
                q.pop();
                if(tmp -> right) q.push(tmp -> right);
                if(tmp -> left ) q.push(tmp -> left );
            }
        }
        return res;
    }
};

题目

原题在此
Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

• The path starts with a single slash '/'.
• Any two directories are separated by a single slash '/'.
• The path does not end with a trailing '/'.
• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')
  Return the simplified canonical path.

解析

将字符串以'/'为界分开遍历, 是'..'就退栈; 是空串(连续的两个’/‘分隔的结果)或’.’就不作处理, 其他情况就入栈. 最后将栈内元素全部join再一起.

代码

rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

impl Solution {
    pub fn simplify_path(path: String) -> String {
        let mut stack = vec![];
        for p in path.split("/") {
            if p == "." || p == "" {
                continue;        
            } else if p == ".." {
                stack.pop();
            } else {
                stack.push(p);
            }
        }
        format!("/{}", stack.join("/"))
    }
}

题目

原题在此
We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.

Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example 1:
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Example 2:
Input: nums = [1,2,3,4]
Output: 2

Example 3:
Input: nums = [1,1,1,1]
Output: 0

Constraints:

• 1 <= nums.length <= 2 * $10^4$
• $-10^9$ <= nums[i] <= $10^9$

解析

Solution_0

将每个元素的出现次数记录在map里. 因为map是sorted order, 遍历map 更新最大值就好.

Solution_1

排序后处理, 在每次数字变了的时候重新计算最大值. (虽然排序是$O(logN)$, 但因为是built_in反而更快, 且空间复杂度是$O(1)$.)

代码

Solution_0

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int,int>mp;
        for(auto i: nums)
            mp[i]++;
        int res = 0;
        for (auto [key, val] : mp)
            if(mp.count(key + 1))
                res = max(res, val + mp[key + 1]);
        return res;
    }
};

Solution_1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = 0, n = nums.size();
        int i = 0, j = 0;
        while (j < nums.size()) {
            while (j < n && (nums[j] - nums[i] <= 1)) j++;
            res = max(res, (nums[j - 1] == nums[i]) ? 0 : (j - i));
            if(j == n) break;
            while (i < n && (nums[j] - nums[i] >  1)) i++;
        }
        return res;
    }
};

题目

原题在此

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• $-10^5$ <= Node.val <= $10^5$
• pos is -1 or a valid index in the linked-list.

解析

用两个指针, 一个一次前进一步, 另一个一次前进两步, 如果有loop 它俩终会有相等的时候.

代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * 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) {
        ListNode* foo = head;
        while(head && head -> next && foo && foo -> next && foo -> next -> next) {
            head = head -> next;
            foo = foo -> next -> next;
            if(head == foo) return true;
        }
        return false;
    }
};

题目

原题在此
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

Example 3:
Input: root = [1], low = 1, high = 2
Output: [1]

Example 4:
Input: root = [1,null,2], low = 1, high = 3
Output: [1,null,2]

Example 5:
Input: root = [1,null,2], low = 2, high = 4
Output: [2]

Constraints:

• The number of nodes in the tree in the range [1, $10^4$].
• 0 <= Node.val <= $10^4$
• The value of each node in the tree is unique.
• root is guaranteed to be a valid binary search tree.
• 0 <= low <= high <= $10^4$

解析

根据题意有如下关系:

1. 当前节点val < low时, 此节点的左子树全部小于low. 换言之, 若root -> left -> val < low, root -> left = root -> left -> right.
2. 同理val > high时, 右子树全部大于high. 既若root -> right -> val > high, root -> right = root -> right -> left
3. 传入的root也有可能不在区间内, 要先根据上述关系找到return的root.

代码

iterative

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root) return root;
        while(root -> val < low || root -> val > high) {
            if(root -> val < low ) root = root -> right;
            if(root -> val > high) root = root -> left;
        }
        TreeNode* tmp = root;
        while(tmp) {
            while(tmp -> left && tmp -> left -> val < low) tmp -> left = tmp -> left -> right;
            tmp = tmp -> left;
        }
        
        tmp = root;
        while(tmp) {
            while(tmp -> right && tmp -> right -> val > high) tmp -> right = tmp -> right -> left;
            tmp = tmp -> right;
        }
        return root;
    }
};

recursive

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (root == NULL) return NULL;
        if (root->val < L) return trimBST(root->right, L, R);
        if (root->val > R) return trimBST(root->left, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};

题目

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

Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3 above, the input represents the signed integer. -3.
  Follow up: If this function is called many times, how would you optimize it?

Example 1:
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.

Example 2:
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one ‘1’ bit.

Example 3:
Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one ‘1’ bits.

Constraints:

• The input must be a binary string of length 32

解析

输入为固定长的32bits, 所以咋做都不会超时.
有一种$O(\log{2}{N}$的方法. 其本质上是一种分治法:

• 先将每1bit与相邻与相邻bit相加, 结果存在那2bits里(16个结果). i = (i & 0x55555555) + ((i >> 1) & 0x55555555);
• 再将每2bits与相邻2bits相加结果存入那4bits中.(8个结果). i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
• 重复直到剩下一个结果为止.

代码

c++

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int hammingWeight(uint32_t i) {
      i = (i  & 0x55555555) + ((i >> 1) & 0x55555555);
      i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
      i = (i + (i >> 4)) & 0x0f0f0f0f;
      i = (i + (i >> 8)) & 0x00ff00ff;
      i = i + (i >>16) & 0x0000ffff;
      return (int)i;
    }
};

题目

原题在此

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:
Input: nums = [1]
Output: [1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

解析

有std::next_permutation可用, 一行搞定.
或者, 根据wiki有如下方法:

1. 找到最大下标k满足a[k] < a[k+1]. 若没有则已经是最后一个置换.
2. 找到最大下边l满足l > k && a[l] > a[k].
3. swap(a[k], a[l]).
4. 调换a[k+1]至结尾的所有元素.

代码

std

1
2
3
4
5
6

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(begin(nums), end(nums));
    }
};

impl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
    	int n = nums.size(), k, l;
    	for (k = n - 2; k >= 0; k--) {
            if (nums[k] < nums[k + 1]) {
                break;
            }
        }
    	if (k < 0) {
    	    reverse(nums.begin(), nums.end());
    	} else {
    	    for (l = n - 1; l > k; l--) {
                if (nums[l] > nums[k]) {
                    break;
                }
            } 
    	    swap(nums[k], nums[l]);
    	    reverse(nums.begin() + k + 1, nums.end());
        }
    }
};