1 介绍
本博客用来记录代码随想录leetcode200题之额外题目相关题目。
2 训练
解题思路：二分查找。
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 False
if 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 = 0
j = 0
while j < n:
if a[j] == 0:
pass
else:
a[i], a[j] = a[j], a[i]
i += 1
j += 1
return
题目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
解题思路：二分查找。
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 -= 1
return [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 = 0
j = 1
while 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.next
b = 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 = b
return 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
#翻转链表b
b = 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 = b
return 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 = b
prev = b
a = na
b = nb
if a is not None and prev is not None:
prev.next = a
return res
文章评论