【算法】算法题-20231118

一、16.17. 连续数列

简单
给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

输入： [-2,1,-3,4,-1,2,1,-5,4]
输出： 6
解释： 连续子数组 [4,-1,2,1] 的和最大为 6。
进阶：

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

class Solution:
    def maxSubArray(self,nums):
        cnt=0
        ret=nums[0]
        for num in nums:
            cnt=max(num,cnt+num)
            ret=max(ret,cnt)
        return ret

s=Solution()
nums=[-2,1,-3,4,-1,2,1,-5,4]
print(s.maxSubArray(nums))
1
2
3
4
5
6
7
8
9
10
11
12

二、合并两个有序数组（力扣88）

提示
简单
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

def test1(nums1,m,nums2,n):
    if n!=0:
        if m==0:
            nums1[:]=nums2[:]
    else:
        p=0
        q=0
        result=[0]*(m+n)
        for i in range(m+n):
            if nums1[p]>nums2[q]:
                result[i]=nums2[q]
                q+=1
            else:
                result[i]=nums1[p]
                p+=1
            if p==m and q!=n:
                result[i+1:]=nums2[q:]
            if p!=m and q==n:
                result[i+1:]=nums1[p:m]
        nums1[:]=result[:]
    return nums1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、存在重复元素（217）

简单

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：
输入：nums = [1,2,3,1]
输出：true

示例 2：
输入：nums = [1,2,3,4]
输出：false

示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
“”"

def test2(nums):
    return len(nums) != len(set(nums))


nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
print(test2(nums))
1
2
3
4
5
6

四、有效的字母异位词（242）

简单

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

def test3(s, t):
    ss = Counter(s)
    tt = Counter(t)
    return ss == tt


s = "rat"
t = "car"
print(test3(s, t))
1
2
3
4
5
6
7
8
9