每日一题02

每日一题

双指针算法

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