[leetcode]第九部分(047-053)

47-Permutations II

问题描述

给定一个可能包含重复数字的集合,返回所有唯一的遍历。

示例

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解题思路

这一题和之前碰到的题目类似,唯一区别在于:数组中可能有重复的数字。因此,只需要对这种情况做特殊处理就行。

思考之前的解法:

  • 两个数求全排列
  • 第三个数插入…

只需要使用一个字段或者集合存储已经出现过的排列即可。

代码

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = [[]]
        nums.sort()
        for i in range(len(nums)):
            ans = self.permute(nums[i], ans)
            print ans
        return ans

    def permute(self, num, pre_list):
        now_list = []
        tmp_dict = dict()
        for i in range(len(pre_list)):
            tmp_list = pre_list[i]
            for j in range(len(tmp_list)+1): 
                val_list = tmp_list[:j] + [num] + tmp_list[j:]
                if str(val_list) not in tmp_dict:
                    now_list.append(val_list)
                    tmp_dict[str(val_list)] = 1 
        return now_list

48-Rotate Image

问题描述

给定一个n*n的矩阵表示一张图片。
顺时旋转图片90°

注意
我们只能就地旋转图片,这就意味着我们只能直接修改输入的2D矩阵。不要声明另一个2D矩阵进行旋转。

示例1

给定 input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

就地旋转矩阵,得到:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例2

给定 input matrix = 
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
],

就地旋转矩阵,得到:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

解题思路

这种类型的题目可以直接找找规律:从第一行开始,先选定i=0,j=0,将其与它最后应该在的位置的数字交换i=0,j=n-1,这样一直替换,直到所有的数字都不用交换,然后i=i+1,直到i到达n-i-1即可;接下来,继续遍历第二列,直到i=n/2为止,可以把所有地方都遍历完。时间复杂度为O(n/2*3*n)

###代码

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n/2):
            self.rotateSub(matrix, i, i, n-1-i, n)


    def rotateSub(self, matrix, row, start_col, end_col, n):
        for i in range(start_col, end_col):
            now_pos = [row, i]
            # after pos: i, n-1-row
            after_pos = [i, n-1-row]
            while now_pos != after_pos:
                next_pos = [after_pos[1], n-1-after_pos[0]]
                self.swap(matrix, now_pos, after_pos)
                after_pos = next_pos
                #print now_pos, after_pos

    def swap(self, matrix, now_pos, after_pos):
        now_row, now_col = now_pos
        after_row, after_col = after_pos
        tmp = matrix[now_row][now_col]
        matrix[now_row][now_col] =  matrix[after_row][after_col]
        matrix[after_row][after_col] = tmp

49-Group Anagrams

问题描述

给定一个字符串数组,将字谜进行分组。

示例

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

注意
– 所有输入都是小写
– 输出的顺序不影响最终结果

解题思路

😶其实这一题的题目中没定义清楚字谜的定义。于是,我们只能按照给的示例去揣测,字谜需要满足两个要求:
– 所有字母相同
– 上一个单词的最后一个字母是下一个单词的首字母

因此,这道题目从头开始遍历:
– 判断结果数据集中是否已经有相应的单词集合,如果已经有了,则直接将其append到队尾;如果没有,则新建一个list存储。

所以重点应该是在如何识别一个字母组合是否已经出现,在这里,我们使用的是将字符按照语义的顺序排列,这样保证只要字符相同,那么

代码

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        ans = []
        set_dict = dict()
        for i in range(len(strs)):
            now_str = strs[i]
            order_str = "".join((lambda x:(x.sort(),x)[1])(list(now_str)))
            if order_str in set_dict:
                idx = set_dict[order_str]               
                ans[idx].append(now_str)
            else:
                ans.append([now_str])
                set_dict[order_str] = len(ans) - 1
        return ans

50-Pow(x, n)

问题描述

实现pow(x,n),计算xn次方。

示例1

Input: 2.00000, 10
Output: 1024.00000

示例2

Input: 2.10000, 3
Output: 9.26100

示例3

Input: 2.00000, -2
Output: 0.25000
解释: 2^-2 = 1/2^2 = 1/4 = 0.25

注意
-100.0 < x < 100.0
n是一个32位有符号的整数,范围在[-2^31,2^31-1]

解题思路

感觉这道题目主要考察n<0的时候需要将x转化为1/x

但是有点担心溢出的问题…

如果直接从i1遍历到n的话,果然遇到了超时的问题… 因此,考虑二分法能减少时间复杂度。其实就是将x乘以n次。如果n%20的话,那么ans=x^n/2 * x^n/2即可,否则ans=x^n/2 * x^n/2 * x。因此,需要计算x^n/2。这样一步一步细分,直到n==0返回1即可。就能减少时间复杂度。(没想到这样的做法提交能够beat 100%。)

代码

解法1

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if x == 0:
            return 0
        if n < 0:
            return self.myPow(1.0/x, -n)
        ans = 1.0
        while n != 0:
            if n % 2 != 0:
                ans *= x
            x *= x
            n = n / 2
        return ans

解法2:递归

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if x == 0:
            return 0
        if n < 0:
            return self.myPow(1.0/x, -n)
        if n == 0:
            return 1
        ans = self.myPow(x, n/2)
        if n % 2 == 0:
            return ans * ans
        else:
            return ans * ans * x

51-N-Queens

问题描述

n皇后迷宫是一个将n个皇后放置在一个n*n的棋盘上使得没有两个皇后相互攻击。

Alt text

给定一个整数n,返回所有n皇后问题的唯一解。

每一种方案都包含一个n皇后位置的唯一板配置,其中'Q''.'分别表示一个皇后和一个空位置。

示例

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 对4皇后迷宫问题有两个不重复的解如上所示。

解题思路

其实刚看到这个题目的时候还有点没弄明白,查了下n皇后问题的定义:任意两个皇后都不能处于同一行、同一列或同一斜线上。对这个问题的定义有了一定的了解。

这类题目是典型的回溯题。从起始位置开始,向前试探,直到有一个满足条件为止,否则将当前指针向前移动。

代码

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        ans = []
        cur_ans = ["." * n] * n
        self.backtrack(cur_ans, ans, n, 0)
        return ans



    def backtrack(self, cur_ans, ans, n, row):
        if row == n:
            tmp = [data for data in cur_ans]
            ans.append(tmp)
            return
        for col in range(n):
            if self.valid(cur_ans, n, row, col):
                self.replace(cur_ans, row, col, 'Q')
                self.backtrack(cur_ans, ans, n, row+1)
                self.replace(cur_ans, row, col, '.')


    def valid(self, board, n, i, j):
        if i >= n or j >= n:
            return False
        # check row and column
        for tmp in range(n):
            if board[i][tmp] == 'Q' or board[tmp][j] == 'Q':
                return False
        # check hypotenuse
        tmp_row, tmp_col = i, j
        while tmp_row >= 0 and tmp_col >= 0:
            if board[tmp_row][tmp_col] == 'Q':
                return False
            tmp_col -= 1
            tmp_row -= 1
        tmp_row, tmp_col = i, j
        while tmp_row >= 0 and tmp_col < n:
            if board[tmp_row][tmp_col] == 'Q':
                return False
            tmp_col += 1
            tmp_row -= 1
        return True

    def replace(self, cur_ans, i, j, char):
        tmp = cur_ans[i]
        tmp = tmp[:j] + char + tmp[j+1:]
        cur_ans[i] = tmp

52-N-Queens II

问题描述

n皇后迷宫是一个将n个皇后放置在一个n*n的棋盘上使得没有两个皇后相互攻击。

Alt text

给定一个整数n,返回所有n皇后问题的唯一解的个数。

示例

Input: 4
Output: 2
解释: 对4皇后迷宫问题有两个不重复的解如下所示。
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

解题思路

这一题的思路和上一题类似,用回溯的方法进行求解,最后返回len(ans)即可。

代码

class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        ans = []
        cur_ans = ["." * n] * n
        self.backtrack(cur_ans, ans, n, 0)
        return len(ans)



    def backtrack(self, cur_ans, ans, n, row):
        if row == n:
            tmp = [data for data in cur_ans]
            ans.append(tmp)
            return
        for col in range(n):
            if self.valid(cur_ans, n, row, col):
                self.replace(cur_ans, row, col, 'Q')
                self.backtrack(cur_ans, ans, n, row+1)
                self.replace(cur_ans, row, col, '.')


    def valid(self, board, n, i, j):
        if i >= n or j >= n:
            return False
        # check row and column
        for tmp in range(n):
            if board[i][tmp] == 'Q' or board[tmp][j] == 'Q':
                return False
        # check hypotenuse
        tmp_row, tmp_col = i, j
        while tmp_row >= 0 and tmp_col >= 0:
            if board[tmp_row][tmp_col] == 'Q':
                return False
            tmp_col -= 1
            tmp_row -= 1
        tmp_row, tmp_col = i, j
        while tmp_row >= 0 and tmp_col < n:
            if board[tmp_row][tmp_col] == 'Q':
                return False
            tmp_col += 1
            tmp_row -= 1
        return True

    def replace(self, cur_ans, i, j, char):
        tmp = cur_ans[i]
        tmp = tmp[:j] + char + tmp[j+1:]
        cur_ans[i] = tmp

53-Maximum Subarray

问题描述

给定一个整数数组nums,找到连续的子数组(至少包含一个数字),有最大的和并且返回该值。

示例

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
解释: [4,-1,2,1] 有最大的值 6.

思考
如果有O(n)的解决方案,尝试使用另外一种使用分治法的解决方案。

解题思路

使用两个指针,第一个指针pre标识到i-1之前的和,如果pre<0,那么第二个指针now表示i的值,否则第二个指针now表示pre+nums[i]的值,如果now>max,那么now=max;接下来pre=now,…,直到到数组末尾。

时间复杂度为O(n)

考虑分治法,将数组均分为两个部分,那么最大子数组会存在于:

  • 左侧数组的最大子数组
  • 右侧数组的最大子数组
  • 左侧数组的以右侧边界为边界的最大子数组+右侧数组的以左侧边界为边界的最大子数组

代码

方法1

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return
        max, pre = nums[0], nums[0]
        for i in range(1, len(nums)):
            now = nums[i]
            if pre > 0:
                now += pre
            if now > max:
                max  = now
            pre = now
        return max
打赏

mickey

记录生活,写给几十年后的自己。