代码随想录算法训练营第六天 |18. 四数之和、344.反转字符串、541. 反转字符串II

今天是代码随想录算法训练营的第六天，写了三道题目：18. 四数之和、344.反转字符串、541. 反转字符串II

四数之和之后或许还要再看看的；

18. 四数之和代码如下：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:

        # 同样是使用双指针法，不过这道题目，我还需要更清晰；
        
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n):
            if nums[i] > target and nums[i] > 0 and target > 0:# 剪枝（可省）
                break
            if i > 0 and nums[i] == nums[i-1]:# 去重
                continue
            for j in range(i+1, n):
                if nums[i] + nums[j] > target and target > 0: #剪枝（可省）
                    break
                if j > i+1 and nums[j] == nums[j-1]: # 去重
                    continue
                left, right = j+1, n-1
                while left < right:
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

344.反转字符串代码如下：

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # # Solution1 用双指针
        # left, right = 0, len(s) - 1
        # while left < right:
        #     # 交换“类”首尾的两个数值
        #     s[left], s[right] = s[right], s[left]
        #     left += 1
        #     right -= 1

        # # Solution2 使用栈
        # stack = [] # 这个时候栈就用列表[]来进行表达
        # for char in s:
        #     stack.append(char)
        
        # for i in range(len(s)):
        #     s[i] = stack.pop()

        # # Solution3 使用range（也就是元素本身在数组里面的index规律）
        # n = len(s)
        # for i in range(n // 2):
        #     s[i], s[n - i - 1] = s[n - i - 1], s[i]

        # # Solution4 使用reversed
        # s[:] = reversed(s)

        # Solution5 使用切片
        s[:] = s[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

541. 反转字符串II代码如下：

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        """
        1. 使用range(start, end, step)来确定需要调换的初始位置
        2. 对于字符串s = 'abc'，如果使用s[0:999] ===> 'abc'。字符串末尾如果超过最大长度，则会返回至字符串最后一个值，这个特性可以避免一些边界条件的处理。
        3. 用切片整体替换，而不是一个个替换.
        """
        def reverse_substring(text):
            left, right = 0, len(text) - 1
            while left < right:
                text[left], text[right] = text[right], text[left]
                left += 1
                right -= 1
            return text
        
        res = list(s)

        for cur in range(0, len(s), 2 * k): # 这里是这道题目的核心；请注意，是2k这个步子来跳的；
            res[cur: cur + k] = reverse_substring(res[cur: cur + k])
        
        return ''.join(res)```

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22