代码随想录leetcode200题之额外题目

1 介绍

本博客用来记录代码随想录leetcode200题之额外题目相关题目。

2 训练

题目1：1365. 有多少小于当前数字的数字

解题思路：二分查找。

C++代码如下，

class Solution {
public:vector<int> smallerNumbersThanCurrent(vector<int>& a) {vector<int> b = a;sort(b.begin(), b.end());vector<int> res;for (auto x : a) {auto iter = lower_bound(b.begin(), b.end(), x);int i = distance(b.begin(), iter);res.emplace_back(i);}return res;}
};

python3代码如下，

class Solution:def smallerNumbersThanCurrent(self, a: List[int]) -> List[int]:b = copy.deepcopy(a)b.sort()res = []for x in a:i = bisect.bisect_left(b, x)res.append(i)return res 

题目2：941. 有效的山脉数组

解题思路：模拟。

C++代码如下，

class Solution {
public:bool validMountainArray(vector<int>& a) {int n = a.size();if (n < 3) return false;if (!(a[0] < a[1])) return false;if (!(a[n-2] > a[n-1])) return false;int i = 0;while (i+1 < n && a[i] < a[i+1]) i += 1;int j = i;while (j+1 < n && a[j] > a[j+1]) j += 1;if (j != n-1) return false;return true;}
};

python3代码如下，

class Solution:def validMountainArray(self, a: List[int]) -> bool:n = len(a)if n < 3:return False if not (a[0] < a[1]):return Falseif not (a[-2] > a[-1]):return False i = 0 while i + 1 < n and a[i] < a[i+1]:i += 1 j = i while j + 1 < n and a[j] > a[j+1]:j += 1 if j != n-1:return False return True 

题目3：1207. 独一无二的出现次数

解题思路：模拟。

C++代码如下，

class Solution {
public:bool uniqueOccurrences(vector<int>& a) {unordered_map<int, int> cnt1;for (auto x : a) cnt1[x]++;unordered_map<int, int> cnt2;for (auto [k, v] : cnt1) {cnt2[v]++;if (cnt2[v] > 1) return false;}return true;}
};

python3代码如下，

class Solution:def uniqueOccurrences(self, a: List[int]) -> bool:cnt = collections.Counter(a)res = collections.Counter(cnt.values())for k in res:if res[k] > 1:return False return True 

题目4：283. 移动零

解题思路：双指针。

C++代码如下，

class Solution {
public:void moveZeroes(vector<int>& a) {int n = a.size();int i = 0;int j = 0;while (j < n) {if (a[j] != 0) {swap(a[i], a[j]);i += 1;}j += 1;}return;}
};

python3代码如下，

class Solution:def moveZeroes(self, a: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""n = len(a)i = 0j = 0 while j < n:if a[j] == 0:pass else:a[i], a[j] = a[j], a[i]i += 1j += 1return 

题目5：189. 轮转数组

解题思路：分三步走。第1步，先翻转整个列表。第2步，翻转列表的[0,k)部分。第3步，翻转列表的[k,n)部分。

C++代码如下，

class Solution {
public:void rotate(vector<int>& a, int k) {int n = a.size();k %= n;reverse(a.begin(), a.end());reverse(a.begin(), a.begin()+k);reverse(a.begin()+k, a.end());return;}
};

python3代码如下，

class Solution:def reverse(self, a: list, i: int, j: int) -> None:while i < j:a[i], a[j] = a[j], a[i]i += 1 j -= 1 return def rotate(self, a: List[int], k: int) -> None:"""Do not return anything, modify nums in-place instead."""n = len(a)k %= n self.reverse(a, 0, n-1)self.reverse(a, 0, k-1)self.reverse(a, k, n-1)return 

题目6：724. 寻找数组的中心下标

解题思路：模拟。

C++代码如下，

class Solution {
public:int pivotIndex(vector<int>& a) {a.insert(a.begin(), 0);int n = a.size();vector<int> s(n, 0);for (int i = 1; i < n; ++i) {s[i] = s[i-1] + a[i];}for (int i = 1; i < n; ++i) {if (s[i-1] == s[n-1] - s[i]) {return i-1;}}return -1;}
};

python3代码如下，

class Solution:def pivotIndex(self, a: List[int]) -> int:a.insert(0, 0)n = len(a)s = [0] * n for i in range(1,n):s[i] = s[i-1] + a[i] for i in range(1,n):if s[i-1] == s[n-1] - s[i]:return i-1 return -1        

题目7：34. 在排序数组中查找元素的第一个和最后一个位置

解题思路：二分查找。

C++代码如下，

class Solution {
public:vector<int> searchRange(vector<int>& a, int target) {int n = a.size();auto iter = lower_bound(a.begin(), a.end(), target);if (iter == a.end() || *iter != target) {return {-1,-1};}int i = distance(a.begin(), iter);iter = upper_bound(a.begin(), a.end(), target);int j = distance(a.begin(), iter);j -= 1;return {i,j};}
};

python3代码如下，

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:i = bisect.bisect_left(nums, target)if i >= len(nums) or (i < len(nums) and nums[i] != target): #特判return [-1,-1]j = bisect.bisect_right(nums, target)j -= 1return [i,j]

题目8：922. 按奇偶排序数组 II

解题思路：双指针算法。

C++代码如下，

class Solution {
public:vector<int> sortArrayByParityII(vector<int>& a) {int n = a.size();int i = 0, j = 1;while (i < n && j < n) {while (i < n && a[i] % 2 == 0) {i += 2;}while (j < n && a[j] % 2 == 1) {j += 2;}if (i < n && j < n) {swap(a[i], a[j]);}}return a;}
};

python3代码如下，

class Solution:def sortArrayByParityII(self, a: List[int]) -> List[int]:n = len(a)i = 0j = 1while i < n and j < n:while i < n and a[i] % 2 == 0:i += 2 while j < n and a[j] % 2 == 1:j += 2 if i < n and j < n:a[i], a[j] = a[j], a[i]return a 

题目9：35. 搜索插入位置

解题思路：二分查找。

C++代码如下，

class Solution {
public:int searchInsert(vector<int>& nums, int target) {auto iter = lower_bound(nums.begin(), nums.end(), target);return distance(nums.begin(), iter);}
};

python3代码如下，

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:return bisect.bisect_left(nums, target)

题目10：24. 两两交换链表中的节点

解题思路：对于node->a->b->…，三步操作。第1步，a.next = b.next。第2步，b.next = a。第3步，node.next = b。

C++代码如下，

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode *dummy = new ListNode(0, head);ListNode *node = dummy;while (node->next != nullptr && node->next->next != nullptr) {ListNode *a = node->next;ListNode *b = node->next->next;a->next = b->next;b->next = a;node->next = b;node = node->next->next;}return dummy->next;}
};

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dummy = ListNode(0,head)node = dummy while node.next is not None and node.next.next is not None:a = node.nextb = node.next.next a.next = b.next b.next = a node.next = b node = node.next.next return dummy.next 

题目11：234. 回文链表

解题思路：将原链表拆分成2个链表（先切割后翻转链表）。比较这2个链表中的元素值。

C++代码如下，

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverse(ListNode* head) {ListNode *a = head;ListNode *prev = nullptr;while (a != nullptr) {ListNode *b = a->next;a->next = prev;prev = a;a = b;}return prev;}bool isPalindrome(ListNode* head) {ListNode *slow = head;ListNode *fast = head;while (slow->next != nullptr && fast->next != nullptr && fast->next->next != nullptr) {slow = slow->next;fast = fast->next->next;}//切割ListNode *a = head;ListNode *b = slow->next;slow->next = nullptr;//翻转b = reverse(b);while (a != nullptr && b != nullptr) {if (a->val != b->val) {return false;}a = a->next;b = b->next;}return true;}
};

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:a = head prev = None while a is not None:b = a.next a.next = prev prev = a a = breturn prev def isPalindrome(self, head: Optional[ListNode]) -> bool:slow = head fast = head while slow.next is not None and fast.next is not None and fast.next.next is not None:slow = slow.next fast = fast.next.next a = head b = slow.next slow.next = None#翻转链表bb = self.reverse(b) while a is not None and b is not None:if a.val != b.val:return False a = a.next b = b.next return True 

题目12：143. 重排链表

解题思路：先通过快慢指针分割原链表为a和b。然后翻转链表b。最后合并两个链表即可。

C++代码如下，

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:prev = None a = head while a is not None:b = a.next a.next = prev prev = a a = breturn prev def reorderList(self, head: Optional[ListNode]) -> None:"""Do not return anything, modify head in-place instead."""fast = head slow = head while slow.next is not None and fast.next is not None and fast.next.next is not None:slow = slow.next fast = fast.next.next #先分隔a = head b = slow.next #后翻转b = self.reverse(b)slow.next = None res = a prev = None while a is not None and b is not None:na = a.next nb = b.next if prev is not None:prev.next = a             a.next = bprev = b a = na b = nb if a is not None and prev is not None:prev.next = a return res 

3 参考

代码随想录