20:算法小练(2)

继续算法的日常练习

字符串

最大公共前缀

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

编写一个函数来查找字符串数组的最大公共前缀；如果不存在，则返回 ""

def longestCommonPrefix(self, strs:List(str))->str:
        min_str = min(strs, key=len)
        result = ""
        p = 0
        while p < len(min_str):
            char = strs[0][p]
            for s in strs:
                if s[p] != char:
                    return result
            result += char
            p += 1
        return result

先纵向比对第一个字符，如果均为相同，则加入返回值中；若不正确，则直接返回

最长回文子串

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个字串s找到s中最长的子串,并返回

class Solution(object):
    def longestPalindrome(self, s:str)->str:
        ans = ""
        for i in range(len(s)):
            temp = self.search(s,i,i)
            if len(temp) > len(ans):
                ans = temp
            temp = self.search(s,i,i+1)
            if len(temp) > len(ans):
                ans = temp
        return ans

    def search(self,s,first,end):
        while first>=0 and end<len(s) and s[first] == s[end]:
            first -= 1
            end += 1
        return s[first+1:end]

首先构造一个中心回文的函数 search,先为两边设置边界条件，然后当中心索引两边的值相等时，则向外拓展。我们构造这个辅助函数之后，在主函数中调用。（需要考虑奇偶回文的情况）

翻转字符串里的单词

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个字符串s，反转字符串中单词的顺序

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

1 2	def reverseWords(self, s:str)->str: return (" ").join(s.split()[::-1])

啊，因为python丰富的内置函数，直接做完了。可以稍微讲下这几个函数的用法：

("拼接符号").join(待拼接数组)
(待分隔数组).split(分隔符号)

双指针

指针常用的两种用法：

首尾指针
快慢指针

反转字符串

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题

def reverseString(self, s):
    i,j = 0,len(s)-1
    while i<j:
        s[i],s[j] = s[j],s[i]
        i += 1
        j -= 1
    return s

这里实际上是用了双指针的思想，相对移动然后互换位置。python中虽然没有指针，但是我们仍然可以通过数组去模拟这个过程，不过设置边界条件时一定要注意

数组拆分

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该最大总和

class Solution(object):
    def arrayPairSum(self, nums:List[int])->int:
        ans = 0
        nums = self.quick_sort(nums)
        print(nums)
        for i in range(len(nums)//2):
            ans += nums[i*2]
        return ans

    def quick_sort(self,array):
        if len(array) <= 1:
            return array
        else:
            reference = array[0]
            small = [s for s in array[1:] if s < reference]
            equal = [e for e in array if e == reference]
            large = [l for l in array[1:] if l > reference]
        return self.quick_sort(small) + equal + self.quick_sort(large)

这道题主要在于分析怎么得到最大总和，观察可以发现先对数组进行排序，再将已排序数组的偶数位累加即可。排序的话要尽量使用，较快的排序，不然会超时（冒泡就超了），所以这里使用快速排序

两数之和

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

def twoSum(self, numbers:List[int], target:int)->List[int]:
	i,j = 0,len(numbers)-1
	while True:
		a = numbers[i]+numbers[j]
		if a>target:
			j -= 1
		elif a<target:
			i += 1
		else:
			return [i+1,j+1]

对于这类题可以用一种匹配方式，有效的减少重复的索引：

双指针指向首尾，求和与target进行比较
当值较小时，我们将首指针前移
当值较大时，我们将尾指针后移

移除元素

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
nums 的其余元素和 nums 的大小并不重要。
返回 k

def removeElement(self, nums:List[int], val:int)->int:
       slow = 0
       for fast in range(len(nums)):
           if nums[fast] != val:
               nums[slow] = nums[fast]
               slow += 1
       return slow

快慢指针，一个负责定位，一个负责向前索引匹配。这个思想十分常见

最大连续的1的个数

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定一个二进制数组 nums ，计算其中最大连续 1 的个数

def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
    a,b = 0,0  # 分别存储当前最大连续数与历史最大连续数
    for i in range(len(nums)):
        if nums[i] == 0:
            if a > b:
                b = a
            a = 0
        else:
            a += 1
    return max(a,b)

这里，我用了一个比较清晰的答案，同时这里也体现了快慢指针的思想，很优雅

长度最小的子数组

数组和字符串 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

def minSubArrayLen(self, target:int, nums:List[int])->int:
    left,right = 0,0
    count = len(nums)+1
    sum = 0
    while right < len(nums):
        sum += nums[right]
        while sum >= target:
            count = min(count,right-left+1)
            sum -= nums[left]
            left += 1
        right += 1
    return 0 if count==len(nums)+1 else count

这里使用了尺缩法，其大致流程如下：

右边界右移，直到和大于target，令左边界右移
若和仍然大于target，左边界继续右移
若和小于target，右边界右移

这种和上面的相对收缩有着异曲同工之妙，但是这里是追及收缩，要注意边界条件