月度归档： 2022年1月

Companies

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

# [81] 搜索旋转排序数组 II
#

# @lc code=start
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if target in nums:
            return True
        else:return False

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

# @lc app=leetcode.cn id=80 lang=python3
#
# [80] 删除有序数组中的重复项 II
#

# @lc code=start
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 2
        for i in range(2, len(nums)):
            if nums[i] != nums[j - 2]:
                nums[j] = nums[i]
                j += 1
        return j

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• 1 <= s.length, t.length <= 105
• s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

# @lc app=leetcode.cn id=76 lang=python3
#
# [76] 最小覆盖子串
#
#滑动窗口方法
# @lc code=start
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        dict1=dict()
        for i in t:
            if i in dict1:
                dict1[i]+=1
            else:
                dict1[i]=1
        def isempty(dicts):
            for i in dicts:
                if dicts[i]>0:
                    return False
            return True
        if len(t)==1:
            if t in s:return t
            else: return ""
        j=-1
        i=0
        m=i
        n=j
        lens= 10**5
        while  i<=len(s)-len(t):
            if isempty(dict1):
                if j-i+1<lens:
                    lens=j-i+1
                    m=i
                    n=j
                if s[i] in dict1:
                    dict1[s[i]]= dict1[s[i]]+1
                i=i+1
            elif j<len(s)-1:
                j=j+1
                if s[j] in dict1 :
                    dict1[s[j]]=dict1[s[j]]-1  
            elif j==len(s)-1:
                i=i+1             
                    
        if lens == 10**5:
            return ""
        else: return s[m:n+1]

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

思路：根据77题的解法：

# @lc app=leetcode.cn id=78 lang=python3
#
# [78] 子集
#

# @lc code=start
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def combine(n: int, k: int):
            rev=list()
            res=list()
            import copy
            def f(n,k):
                if k==0:
                    re=copy.deepcopy(rev)
                    res.append(re)
                    return 

                else:
                    for i in range(n,k-1,-1):
                        rev.append(nums[i-1])
                        f(i-1,k-1)
                        rev.pop()
            f(n,k)  
            return res
        re=list()
        for i in range(len(nums)+1):
            res=combine(len(nums),i)
            re=res+re
        return re

给定一个包含红色、白色和蓝色，一共 n个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

快速排序：选定基准，大于基准的在右边，小于基准的在左边

快速排序(Quick Sort)是对冒泡排序的一种改进，其的基本思想:选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成（类比二叉树的思想)。

# @lc app=leetcode.cn id=75 lang=python3
#
# [75] 颜色分类
#

# @lc code=start
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def quick_sort(lists,i,j):
            if i >= j:
                return list
            pivot = lists[i]
            low = i
            high = j
            while i < j:
                while i < j and lists[j] >= pivot:
                    j -= 1
                lists[i]=lists[j]
                while i < j and lists[i] <=pivot:
                    i += 1
                lists[j]=lists[i]
            lists[j] = pivot
            quick_sort(lists,low,i-1)
            quick_sort(lists,i+1,high)
            return lists

        quick_sort(nums,0, len(nums) - 1)
# @lc code=end

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

# [74] 搜索二维矩阵
#

# @lc code=start
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def twoserch(nums,i,j,target):
            # i=0
            # j=len(nums)-1
            if nums[0]==target:
                return True
            mid=(i+j)//2
            while i<j-1:
                mid=(i+j)//2
                if nums[mid]==target:
                    return True
                elif nums[mid]<target:
                    i=mid
                else:
                    j=mid
            return False


        j=-1
        for i in range(len(matrix)):
            if target<matrix[i][-1]:
                j=i
                break
            elif target==matrix[i][-1]:
                return True
        if j == -1:
            return False
        else:
            lens=len(matrix[j])
            return twoserch(matrix[j],0,lens-1,target)
# @lc code=end

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

代码：

# @lc app=leetcode.cn id=73 lang=python3
#
# [73] 矩阵置零
#

# @lc code=start
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m=len(matrix)
        n=len(matrix[0])
        res=list()
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==0:
                    res.append([i,j])
        for l in res:
            matrix[l[0]]=[0]*n
            for  x in matrix:
                x[l[1]]=0 

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

示例:

输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:

输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
         "to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

code：

# [68] 文本左右对齐
#

# @lc code=start
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        lens=len(words)
        rev=list()
        nowlens=0
        start=0
        i=0
        while i<lens:
            wordlen=len(words[i])
            nowlens=nowlens+wordlen
            #print(i,nowlens)
            if nowlens<maxWidth:
                nowlens+=1
                i=i+1
                #print(i)
                #print(nowlens)
            elif nowlens>maxWidth:
                nowlens=nowlens-wordlen-1
                
                reslens=maxWidth-nowlens
                m=(i-1-start)
                if m==0:
                    mid=""
                    mid=mid+words[start]+(maxWidth-len(words[start]))*" "
                    rev.append(mid)
                #print(reslens,reslens//(i-1-start),reslens/(i-1-start))
                elif reslens//(i-1-start)==reslens/(i-1-start):
                    mid=""
                    x=reslens//(i-1-start)+1
                    for j in range(start,i-1):
                        mid=mid+words[j]+x*" "
                    mid=mid+words[i-1]
                    rev.append(mid)
                else:
                    other=reslens%(i-1-start)
                    mid=""
                    x=reslens//(i-1-start)+1
                    print(x,other)
                    for j in range(start,i-1):
                        if other>0:
                            mid=mid+words[j]+x*" "+" "
                            other-=1
                        else:
                            mid=mid+words[j]+x*" "
                    mid=mid+words[i-1]
                    rev.append(mid)
                nowlens=0
                start=i
            elif nowlens==maxWidth:
                mid=""
                for j in range(start,i):
                    mid=mid+words[j]+" "
                mid=mid+words[i]
                rev.append(mid)
                start=i+1
                nowlens=0
                i=i+1
        if start<lens:
            mid=""
            for j in range(start,lens):
                mid=mid+words[j]+" "
            mid=mid[:-1]
            other=maxWidth-len(mid)
            mid=mid+other*" "
            rev.append(mid)
        return rev    
                
             
# @lc code=end

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

递归实现：

易错点： re=copy.deepcopy(rev) 需要深拷贝

# @lc app=leetcode.cn id=77 lang=python3
#
# [77] 组合
#
#递归：
# @lc code=start
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        rev=list()
        res=list()
        import copy
        def f(n,k):
            if k==0:
                re=copy.deepcopy(rev)
                res.append(re)
                return 

            else:
              for i in range(n,k-1,-1):
                  rev.append(i)
                  f(i-1,k-1)
                  rev.pop()
        f(n,k)
        return res

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

# @lc app=leetcode.cn id=83 lang=python3
#
# [83] 删除排序链表中的重复元素
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        head0=head
        end=head
        while end!=None:
            if end.next!=None and head.val==end.next.val:
                end=end.next
            elif end.next!=None and head.val!=end.next.val:
                head.next=end.next
                head=head.next
                end=head
            elif end.next==None and head.val==end.val:
                head.next=None
                end=end.next
            else:
                return head0

        return head0
# @lc code=end