每日归档： 2022年1月25日

给你一个整数数组 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