[leetcode]第十二部分

68-Text Justification

问题描述

给定一个单词的数组和一个宽度值maxWidth,将文本格式化,使得每一行有正好maxWidth个字符,并且两边对齐.

使用贪心算法进行打包,也就是说:在每一行打包尽可能多的单词.在必要的时候可以使用' '进行填充,使得每一行正好有maxWidth个字符.

单词之间的空格应该尽可能分布均匀.如果一行中的空格数目无法均匀分布在单词之间,左边的空格应该要分配更多的空间.

对于文本的最后一行,应该向左对齐并且在单词之间不需要额外的空间.

注意
– 由非空字符组成的字符序列定义为一个单词
– 每个字符的长度限定在0maxWidth之间
– 输入的单词数组words至少包含一个单词.

示例1

Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例2

Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行是 "shall be    "而不是 "shall     be",因为最后一行是左对齐,而不是两边对齐.注意,第二行也是左边对齐,因为它值包含一个单词.

示例3

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

解题思路

首先解决分行的问题:维护一个临时数组now_arr以及当前的字符数now_num,从前往后遍历数组,判断当前单词的长度加上now_num是否超过maxWidth-len(now_arr),如果不超过,则将其加入now_arr并且增加now_num,否则:space_num=(maxWidth-now_num)/(len(now_arr)-1),特别需要注意的是分布不均匀的情况,需要在前面n个单词之间多增加一个空格.

下列两种情况需要向左对齐:
– 最后一行
– 该行只有一个单词

代码

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        cur_words = list()
        cur_num = 0
        ans = list()
        for i in range(len(words)):
            word = words[i]
            if cur_num + len(cur_words) + len(word) <= maxWidth:
                cur_words.append(word)
                cur_num += len(word)
            else:
                cur_word = self.pad(cur_words, cur_num, maxWidth, False)
                ans.append(cur_word)
                cur_words = [word]
                cur_num = len(word)
        if len(cur_words) > 0:
            ans.append(self.pad(cur_words, cur_num, maxWidth, True))
        return ans


    def pad(self, cur_words, cur_num, maxWidth, isLeft):
        cur_word = ""
        if not isLeft and len(cur_words) > 1:
            avg_space = (maxWidth - cur_num) / (len(cur_words)- 1)
            more_space = maxWidth - cur_num - avg_space * (len(cur_words) - 1)
            avg_space_str, more_space_str = "", ""
            for j in range(avg_space + 1):
                more_space_str = more_space_str + " "
                if j < avg_space:
                    avg_space_str = avg_space_str + " "
            for j in range(len(cur_words)-1):
                if j < more_space:
                    cur_word = cur_word + cur_words[j] + more_space_str
                else:
                    cur_word = cur_word + cur_words[j] + avg_space_str                  
            cur_word += cur_words[-1]
        else:
            cur_word = cur_words[0]
            for j in range(len(cur_words)):
                if len(cur_word) < maxWidth:
                    cur_word = cur_word + " " + cur_words[j] 
            space_num = maxWidth - len(cur_word)
            for _ in range(space_num):
                cur_word = cur_word + " "
        return cur_word

69-Sqrt(x)

问题描述

实现int sqrt(int x).
计算并且返回x的平方根,其中x保证为非负的整数.
由于返回类型是一个整数,将小数点后面的数字直接截取即可,只返回结果的整数部分.

示例1

Input: 4
Output: 2

示例2

Input: 8
Output: 2
解释: 8 的平方根是 2.82842..., 将小数部分进行截取,返回2.

解题思路

最简单的想法…不考虑任何时间复杂度的因素,从1开始向前遍历,判断当前数的平方与x的比较,如果大于x,则返回n-1,如果等于x则返回n,否则n=n+1,继续向前遍历.

果然…超出了时间的限制.

解法1:二分搜索

左边从0开始,右边是x,根据情况分别向左或者向右移动

解法2:牛顿迭代法

x^2=n,令f(x)=x^2-n,需要使得f(x)接近0


参考Annie Kim’s Blog,得到下面的推导公式:

首先取x_0,如果x_0不是解,做一个经过(x_0,f(x_0))这个点的切线,与x轴的交点为x_1
同样的道理,如果x_1不是解,做一个经过(x_1,f(x_1))这个点的切线,与x轴的交点为x_2
以此类推。
以这样的方式得到的xi会无限趋近于f(x)=0的解
判断x_i是否是f(x)=0的解有两种方法:
一是直接计算f(x_i)的值判断是否为0,二是判断前后两个解x_ix_{i-1}是否无限接近。
经过(x_i, f(x_i))这个点的切线方程为f(x) = f(x_i) + f’(x_i)(x - x_i),其中f'(x)f(x)的导数,本题中为2x。令切线方程等于0,即可求出x_{i+1}=x_i - f(x_i) / f'(x_i)
继续化简,x_{i+1}=x_i - (x_i^2 - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2

代码

解法1

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x <= 1:
            return x
        left, right = 0, x
        while left < right:
            mid = left + (right - left) / 2
            if x / mid >= mid:
                left = mid + 1
            else:
                right = mid
        return right - 1

解法2

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        ans = x
        while ans * ans > x:
            ans = (ans + x / ans) / 2
        return ans

70-Climbing Stairs

问题描述

我们需要爬一个楼梯,需要花n步到达顶端.
每次只能爬1步或者2步,有多少种不同的方式到达顶端?

注意:给定的n为正整数.

示例1

Input: 2
Output: 2
解释: 有两种到达顶端的方式:
1. 1 step + 1 step
2. 2 steps

示例2

Input: 3
Output: 3
解释: 有三种到达顶端的方式:
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解题思路

n个台阶,每次可以走1个或者2个,那么一共有以下几种情况:

  • 02步,n-01步,有1种方法
  • 12步,n-2*11步,有C_{n-2+1}^1种方法
  • 22步,n-2*21步,有C_{n-2*2+2}^2种方法
  • n/22步,n-n/2*21步,有C_{n-n/2*2+n/2}^n/2种方法

找下规律,i0遍历到n/2,共有1+C_{n-2+1}^1+...+C_{n-n/2*2+n/2}^n/2种方法.

代码

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        for i in range(n/2+1):
            one_num = n - i * 2
            total_num = i + one_num
            ans += self.calPro(total_num, i)
        return ans

    def calPro(self, n, digit):
        if n - digit < digit:
            digit = n - digit
        upper_sum, bottom_sum = 1, 1
        for i in range(1, digit + 1):
            upper_num = n - i + 1
            upper_sum *= upper_num
            bottom_sum *= i
        return upper_sum / bottom_sum

71-Simplify Path

问题描述

简化文件的绝对路径(Unix风格).

例如:

path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
path = "/a/../../b/../c//.//", => "/c"
path = "/a//b////c/d//././/..", => "/a/b/c"

在一个UNIX风格的文件系统中,一个.表示当前牡蛎,因此可以在简化的路径中忽略.此外,两个点..表示上级目录,可以忽略最后的目录.可以查看资料了解更多最新信息.

一些问题
– 当path="/../"时,应该返回什么?
– 在这种情况下,应该返回/
– 另一种情况时路径可能会包含多个斜杠'/',例如"/home//foo/"
– 此时,应该忽略多余的斜杠,并且返回"/home/foo"

解题思路

使用一个类似于堆栈的结构存储路径(sim_path),使用一个字符串存储当前字符序列(now_path),从前往后遍历path:

  • 当前字符为/,那么判断当前字符序列now_path是否为..,如果是,则将列表中最后一个元素删除;是否为.,如果是,不做任何处理,其它情况下,直接将now_path的值增加到list的末尾
  • 其它:直接添加到末尾

在遍历结束之后,同上判断下now_path的值,最后join下该列表即可.时间复杂度为O(n),其中npath的长度.

代码

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        sim_path = list()
        now_path = ""
        for i in range(len(path)):
            cur = path[i]
            if cur == "/":
                if len(now_path) > 0:
                    if now_path == '..':
                        if len(sim_path) > 0:
                            sim_path = sim_path[:-1]
                    elif now_path != '.':
                        sim_path.append(now_path)
                    now_path = ""
            else:
                now_path += cur
        if len(now_path) > 0:
            if now_path == '..':
                if len(sim_path) > 0:
                    sim_path = sim_path[:-1]
            elif now_path != '.':
                sim_path.append(now_path)
        return "/" + "/".join(sim_path)

72-Edit Distance

问题描述

给定两个单词word1word2,找到需要将word1转化为word2的最少操作次数.

可以在单词上执行以下三种操作:

  • 插入1个字符
  • 删除1个字符
  • 替换1个字符

示例1

Input: word1 = "horse", word2 = "ros"
Output: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例2

Input: word1 = "intention", word2 = "execution"
Output: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

解题思路

使用动态规划法进行求解, 两个步骤:
– 用数学公式表示问题
– 推导出递归公式

数学公式表示问题

对于两个字符串,使用ST进行表示,使用一个二维数组ans[i][j]标识S中前i个字符序列和T中前j个字符序列的编辑距离.

转移方程的推导

  • 如果S[i] == T[j], 那么ans[i][j] = ans[i-1][j-1]
  • 否则, 需要对队尾的元素进行操作, 此时编辑距离需要加1
    • ST的末尾进行修改, 那么ans[i][j] = ans[i-1][j-1] + 1
    • 删除ST的末尾字符, 那么ans[i][j] = ans[i-1][j] + 1 或者 ans[i][j] = ans[i][j-1] + 1
    • ST的末尾增加字符, 那么 ans[i][j] = ans[i][j-1] + 1 或者 ans[i][j] = ans[i-1][j] + 1
  • 边界情况: 当i=0或者j=0时, 只能一直增加元素, ans[0][j] = j 或者ans[i][0] = i

整理一下:
– 当i=0或者j=0时, ans[0][j] = j 或者ans[i][0] = i
– 当i>0并且j>0时, ans[i][j] = min(ans[i-1][j]+1, ans[i][j-1]+1, ans[i-1][j-1] + flag),其中 flag = 0 if S[i] == T[j] else 0

代码

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m, n = len(word1), len(word2)
        ans = [[0 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(n+1):
            for j in range(m+1):
                if i == 0:
                    ans[i][j] = j
                elif j == 0:
                    ans[i][j] = i
                else:
                    flag = 0 if word1[j-1] == word2[i-1] else 1
                    min_val = ans[i-1][j-1] + flag
                    if min_val > ans[i-1][j] + 1:
                        min_val = ans[i-1][j] + 1
                    if min_val > ans[i][j-1] + 1:
                        min_val = ans[i][j-1] + 1
                    ans[i][j] = min_val
        return ans[n][m]

73-Set Matrix Zeroes

问题描述

给定一个m*n的矩阵,如果一个元素是0,那么将该行和该列均设置为0. 原地进行替换.

示例1

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例2

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

一些小挑战:
– 直接使用O(mn)空间复杂度的方法不是很好
– 简单的改进使用O(m+n)的方法仍然不是一个好的解决方案
– 考虑使用常数空间解决?

解题思路

O(mn)的方法: 先遍历一遍矩阵, 将0元素的坐标记录下来,后面再将矩阵中相应的行列置为0

O(m+n)的方法: 维护两个list分别存储行和列,遍历矩阵,遇到0元素,则将坐标对应的下标设置为1,后面再将矩阵中相应的行列置为0.代码见解法1

常数的方法: 还是得需要两个list来存储行和列是否为需要重置,但是又不能申请额外的空间,于是乎,我们就想到直接利用矩阵中的第0行和第0列来作为这两个list,当然,前提是需要先判断是否这两个list中是否有0

一点想法: 感觉这题还是挺巧妙的, 使用递进的方式来解决问题, 怎么利用现有空间来较少额外空间的申请.

代码

解法1

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return
        m, n = len(matrix), len(matrix[0])
        col_list = [0 for _ in range(m)]
        row_list = [0 for _ in range(n)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    col_list[i] = 1
                    row_list[j] = 1
        for i in range(m):
            if col_list[i] == 1:
                self.setColRowZeros(matrix, i, m, n)
        for i in range(n):
            if row_list[i] == 1:
                self.setColRowZeros(matrix, i, m, n, False)

    def setColRowZeros(self, matrix, idx, m, n, is_col=True):
        if is_col:
            for i in range(n):
                matrix[idx][i] = 0
        else:
            for i in range(m):
                matrix[i][idx] = 0

解法2

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return
        m, n = len(matrix), len(matrix[0])
        col_zero = False
        for i in range(n):
            if matrix[0][i] == 0:
                col_zero = True
        row_zero = False
        for i in range(m):
            if matrix[i][0] == 0:
                row_zero = True
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        for i in range(1, m):
            if matrix[i][0] == 1:
                self.setColRowZeros(matrix, i, m, n)
        for i in range(1, n):
            if matrix[0][i] == 1:
                self.setColRowZeros(matrix, i, m, n, False)
        if col_zero:
            self.setColRowZeros(matrix, 0, m, n)
        if row_zero:
            self.setColRowZeros(matrix, 0, m, n, False)

    def setColRowZeros(self, matrix, idx, m, n, is_col=True):
        if is_col:
            for i in range(n):
                matrix[idx][i] = 0
        else:
            for i in range(m):
                matrix[i][idx] = 0

74-Search a 2D Matrix

问题描述

完成一个高效的算法在一个m*n的矩阵中检索一个给定值. 矩阵有下列属性:

  • 每行的整数从左到右升序排列
  • 每一行的第一个数均小于上一行的最后一个数

示例1

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

示例2

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

解题思路

考虑二分搜索,只不过把list改成了矩阵. 大致思路如下:
– 初始化: row_l= 0, row_r = len(matrix)
– 当row_l <= row_r
row_m = (row_r-row_l)/2, 判断matrix[row_m][-1]target的比较:
– 如果大于:
– 判断matrix[row_m][0]target的比较:
– 如果大于, 那么row_r = row_m-1
– 如果小于, 那么直接在matrix[row_m]中进行列表的二分搜索
– 否则, 直接返回True
– 如果小于, row_l = row_m + 1
– 否则,直接返回True
– 返回False

代码

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        row_l, row_r = 0, len(matrix)-1
        while row_l <= row_r:
            row_m = (row_l + row_r) / 2
            if matrix[row_m][-1] == target:
                return True
            elif matrix[row_m][-1] < target:
                row_l = row_m + 1
            else:
                if matrix[row_m][0] == target:
                    return True
                elif matrix[row_m][0] > target:
                    row_r = row_m - 1
                else:
                    return self.searchList(matrix[row_m], target)
        return False

    def searchList(self, data_list, target):
        start, end = 0, len(data_list) - 1
        while start <= end:
            mid = (start + end) / 2
            if data_list[mid] == target:
                return True
            elif data_list[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return False
打赏

mickey

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注