目录
- 1 介绍
- 2 训练
- 3 参考
1 介绍
本博客用来记录代码随想录leetcode200题中双指针算法部分的题目。
2 训练
题目1：27. 移除元素
C++代码如下，
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int j = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == val) {
//
} else {
nums[j++] = nums[i];
}
}
return j;
}
};
python3代码如下，
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
j = 0
for i in range(len(nums)):
if nums[i] == val:
pass
else:
nums[j] = nums[i]
j += 1
return j
题目2：344. 反转字符串
C++代码如下，
class Solution {
public:
void reverseString(vector<char>& s) {
int l = 0, r = s.size() - 1;
while (l <= r) swap(s[l++], s[r--]);
return;
}
};
python3代码如下，
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
l = 0
r = len(s) - 1
while l <= r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
return
题目3：54. 替换数字（第八期模拟笔试）
C++代码如下，
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
string res;
for (auto c : s) {
if (c >= 'a' && c <= 'z') res += c;
else res += "number";
}
cout << res << endl;
return 0;
}
python3代码如下，
s = str(input())
res = ""
for c in s:
if c.isdigit():
res += "number"
else:
res += c
print(res)
题目4：151. 反转字符串中的单词
C++代码如下，
class Solution {
public:
string reverseWords(string s) {
vector<string> words;
int n = s.size();
for (int i = 0; i < n; ++i) {
if (s[i] != ' ') {
string t = "";
while (i < n && s[i] != ' ') {
t += s[i];
i += 1;
}
words.emplace_back(t);
}
}
reverse(words.begin(), words.end());
string res = "";
for (auto word : words) {
res += word + " ";
}
res = res.substr(0, res.size()-1);
return res;
}
};
python3代码如下，
class Solution:
def reverseWords(self, s: str) -> str:
ls = s.split()
ls = ls[::-1]
res = ""
for x in ls:
res += x + " "
res = res[0:-1]
return res
题目5：206. 反转链表
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* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) { //特判空集或一个结点的时候
return head;
}
ListNode* a = head;
ListNode* b = a->next;
while (a != nullptr && b != nullptr) {
ListNode* t = b->next;
b->next = a;
a = b;
b = t;
}
head->next = nullptr;
return a;
}
};
python3代码如下，
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None: #特判空集和一个结点的情况
return head
a = head
b = a.next
while a is not None and b is not None:
t = b.next
b.next = a
a = b
b = t
head.next = None
return a
题目6：19. 删除链表的倒数第 N 个结点
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* removeNthFromEnd(ListNode* head, int k) {
//删除倒数第k个结点，快慢指针法
ListNode* dummy = new ListNode(0, head);
ListNode* a = dummy;
ListNode* b = dummy;
while (k--) { //b先走k步
b = b->next;
}
while (b->next != nullptr) { //b走到最后一个结点
a = a->next;
b = b->next;
}
if (a->next != nullptr) a->next = a->next->next;
else cout << "a->next is nullptr!" << endl;
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 removeNthFromEnd(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
a = dummy
b = dummy
while k > 0:
b = b.next
k -= 1
while b.next is not None:
b = b.next
a = a.next
a.next = a.next.next
return dummy.next
题目7：面试题 02.07. 链表相交
C++代码如下，
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr) { //特判都为空集，或者有一方为空集的情况
return nullptr;
}
ListNode* a = headA;
ListNode* b = headB;
bool flaga = true;
bool flagb = true;
while (a != b) {
a = a->next;
b = b->next;
if (a == nullptr) {
if (flaga) {
a = headB;
flaga = false;
} else {
break;
}
}
if (b == nullptr) {
if (flagb) {
b = headA;
flagb = false;
} else {
break;
}
}
}
if (a == b) return a;
else return nullptr;
}
};
python3代码如下，
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA is None or headB is None:
return None
a = headA
b = headB
flaga = True
flagb = True
while a != b:
a = a.next
b = b.next
if a is None:
if flaga:
a = headB
flaga = False
else:
break
if b is None:
if flagb:
b = headA
flagb = False
else:
break
if a == b:
return a
else:
return None
题目8：142. 环形链表 II
C++代码如下，
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
//这次的快慢指针，是速度上的快慢指针，而非提前走的快慢指针
ListNode* a = head;
ListNode* b = head;
while (b != nullptr && b->next != nullptr) {
a = a->next;
b = b->next->next;
//起点到环入口的距离为x
//快慢指针相遇点到环入口的距离为y
//环的周长为c
//有x % c = y恒成立
if (a == b) {
ListNode* t = head;
while (t != a) {
t = t->next;
a = a->next;
}
return a;
}
}
return nullptr;
}
};
python3代码如下，
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
a = head
b = head
while b is not None and b.next is not None:
a = a.next
b = b.next.next
if a == b:
t = head
while t != a:
t = t.next
a = a.next
return a
return None
题目9：15. 三数之和
C++代码如下，
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
map<int, int> map_val_cnt;
for (auto x : nums) map_val_cnt[x]++;
vector<int> vals;
for (auto [k, v] : map_val_cnt) vals.emplace_back(k);
set<int> vis;
for (auto x : vals) vis.insert(x);
int n = vals.size();
set<vector<int>> ans;
for (int i = 0; i < n; ++i) {
int a = vals[i];
for (int j = 0; j < n; ++j) {
int b = vals[j];
int c = 0 - a - b;
if (vis.count(c) != 0) {
unordered_map<int,int> curr_cnt;
curr_cnt[a]++;
curr_cnt[b]++;
curr_cnt[c]++;
if (curr_cnt[a] <= map_val_cnt[a] &&
curr_cnt[b] <= map_val_cnt[b] &&
curr_cnt[c] <= map_val_cnt[c]) {
vector<int> t = {a, b, c};
sort(t.begin(), t.end());
ans.insert(t);
}
}
}
}
vector<vector<int>> res(ans.begin(), ans.end());
return res;
}
};
python3代码如下，
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
map_val_cnt = collections.defaultdict(int)
for x in nums:
map_val_cnt[x] += 1
vals = []
for val in map_val_cnt:
vals.append(val)
vis = set()
for val in vals:
vis.add(val)
ans = set()
n = len(vals)
for i in range(n):
a = vals[i]
for j in range(n):
b = vals[j]
c = 0 - a - b
if c in vis:
curr_cnt = collections.defaultdict(int)
curr_cnt[a] += 1
curr_cnt[b] += 1
curr_cnt[c] += 1
if curr_cnt[a] <= map_val_cnt[a] and \
curr_cnt[b] <= map_val_cnt[b] and \
curr_cnt[c] <= map_val_cnt[c]:
t = [a, b, c]
t.sort()
ans.add(tuple(t))
ans = list(ans)
ans = [list(x) for x in ans]
return ans
题目10：18. 四数之和
C++代码如下，
typedef long long LL;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
map<int, int> map_val_cnt;
for (auto x : nums) map_val_cnt[x] += 1;
vector<int> vals;
set<int> vis;
for (auto [k, v] : map_val_cnt) {
vals.emplace_back(k);
vis.insert(k);
}
set<vector<int>> ans;
int n = vals.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
int a = vals[i];
int b = vals[j];
int c = vals[k];
LL t = (LL)target - a - b - c;
if (t > INT_MAX || t < INT_MIN) { //如果t超出了整型范围，那么vis.count(d)一定为0
continue;
}
int d = (LL)target - a - b - c;
if (vis.count(d) != 0) {
unordered_map<int,int> curr_cnt;
curr_cnt[a]++;
curr_cnt[b]++;
curr_cnt[c]++;
curr_cnt[d]++;
if (curr_cnt[a] <= map_val_cnt[a] && curr_cnt[b] <= map_val_cnt[b] &&
curr_cnt[c] <= map_val_cnt[c] && curr_cnt[d] <= map_val_cnt[d]) {
vector<int> t = {a, b, c, d};
sort(t.begin(), t.end());
ans.insert(t);
}
}
}
}
}
vector<vector<int>> res(ans.begin(), ans.end());
return res;
}
};
python3代码如下，
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
map_val_cnt = collections.defaultdict(int)
for x in nums:
map_val_cnt[x] += 1
vals = []
vis = set()
for x in map_val_cnt:
vals.append(x)
vis.add(x)
ans = set()
n = len(vals)
for i in range(n):
for j in range(n):
for k in range(n):
a = vals[i]
b = vals[j]
c = vals[k]
d = target - a - b - c
if d in vis:
curr_cnt = collections.defaultdict(int)
curr_cnt[a] += 1
curr_cnt[b] += 1
curr_cnt[c] += 1
curr_cnt[d] += 1
if curr_cnt[a] <= map_val_cnt[a] and curr_cnt[b] <= map_val_cnt[b] and \
curr_cnt[c] <= map_val_cnt[c] and curr_cnt[d] <= map_val_cnt[d]:
t = [a, b, c, d]
t.sort()
t = tuple(t)
ans.add(t)
res = list(ans)
res = [list(x) for x in res]
return res
3 参考
代码随想录官网
![[Kubernetes] Rancher 2.7.5 部署 k8s](https://img-blog.csdnimg.cn/direct/22a22b8705fe4a738f1640dfa90bef46.png)