leetcode

Posted on | In
  1. Permutations

Medium

Given a collection of distinct integers, return all possible permutations.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

这个题可以考虑循环和递归（深度优先、广度优先搜索）

一个递归的思路如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def rec(nums):
            if len(nums)==1:
                return [nums]
            outs=[]
            for i in nums:
                tnum=nums.copy()
                tnum.remove(i)
                out=rec(tnum)
                for o in out:
                    o.append(i)
                    outs.append(o)
            return outs
        return rec(nums)
  1. Permutations II

Medium

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

这个题在上题的基础上增加了难度

依旧考虑递归（dfs），不过考虑到不重复，首先排序，然后不搜索重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        result = []
        nums.sort()
        self.dfs(result,[],nums)
        return result
    
    def dfs(self, result, subset, nums):
        if not nums:
            result.append(subset)
            return 
        for i in range(len(nums)):
            if i >= 1 and nums[i-1] == nums[i]:
                continue
            self.dfs(result,subset + [nums[i]], nums[:i] + nums[i+1:])
  1. Rotate Image

Medium

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

这个题原地旋转，考虑一次旋转4个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range((n+1)//2):
            for j in range((n)//2):
                tmp=matrix[i][j]
                for _ in range(4):
                    a=matrix[j][n-1-i]
                    matrix[j][n-1-i]=tmp
                    tmp=a
                    i,j=j,n-1-i
  1. Group Anagrams

Medium

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
  1. Group Anagrams

Medium

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

这是一个哈希的问题，最好的办法就是存字典了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic={}
        for i,st in enumerate(strs):
            st=[s for s in st]
            st.sort()
            st=tuple(st)
            if st in dic:
                dic[st].append(i)
            else:
                dic[st]=[i]
        out=[]
        for k,v in dic.items():
            o=[]
            for i in v:
                o.append(strs[i])
            out.append(o)
        return out