每日一题
双指针算法
leetcode 27 移出元素
https://leetcode.cn/problems/remove-element/
代码:
cpp:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast = 0;
int slow = 0;
for (fast = 0; fast < nums.size(); fast++){
if(nums[fast] != val){
nums[slow++] = nums[fast];
}
}
return slow;
}
};
python:
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow, fast = 0, 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
leetcode 26.删除有序数组中的重复项
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
代码
cpp:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast;
int slow = 0;
for(fast = 1; fast < nums.size(); fast++){
if(nums[fast] != nums[slow]){
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
};
python:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow, fast = 0, 1
for fast in range(1, len(nums)):
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
leetcode 283.移动零
https://leetcode.cn/problems/move-zeroes/
代码
cpp:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int fast = 0;
int slow = 0;
for(fast = 0; fast < nums.size(); fast++){
if(nums[fast] != 0){
swap(nums[slow], nums[fast]);
slow++;
}
}
}
};
python:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
slow, fast = 0, 0
for fast in range(0, len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
leetcode 844比较含退格的字符串
https://leetcode.cn/problems/backspace-string-compare/
cpp
class Solution{
public:
string returnstringCount(string str){
int size=str.length();
int slow=0;
for(int fast=0; fast<size; fast++){
if(str[fast]!='#'){
str[slow++]=str[fast];
}
else{
if(slow>0){ // 如果回退到了最后一格就不能再回退了，这里要注意回退的范围
slow--;
}
}
}
string str1(str,0,slow); //这里返回实际的字符串
return str1;
}
bool backspaceCompare(string s,string t){
string sCount = returnstringCount(s);
string tCount = returnstringCount(t);
if(sCount==tCount){
return true;
}
return false; // 如果不等，就不用比较，肯定不相等
}
};
python
class Solution:
def return_string_count(self, s: str) -> str:
slow = 0
size = len(s)
s = list(s) # 将字符串转换为列表以便进行原地修改
for fast in range(size):
if s[fast] != '#':
s[slow] = s[fast]
slow += 1
else:
if slow > 0:
slow -= 1
return ''.join(s[:slow])
def backspaceCompare(self, s: str, t: str) -> bool:
return self.return_string_count(s) == self.return_string_count(t)
leetcode 977. 有序数组的平方
https://leetcode.cn/problems/squares-of-a-sorted-array/
cpp
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
int i = 0, j = n - 1;
for (int p = n - 1; p >= 0; p--) {
int x = nums[i] * nums[i];
int y = nums[j] * nums[j];
if (x > y) {
ans[p] = x;
i++;
} else {
ans[p] = y;
j--;
}
}
return ans;
}
};
python
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
i, j = 0, n - 1
for p in range(n - 1, -1, -1):
x = nums[i] * nums[i]
y = nums[j] * nums[j]
if x > y: # 更大的数放右边
ans[p] = x
i += 1
else:
ans[p] = y
j -= 1
return ans