[leetcode]第二十九部分(188-194)

188. Best Time to Buy and Sell Stock IV

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

假设有一个数组, 数组的第i个元素为给定股票在第i天的价格.

设计一个算法来找到最大的利润. 最多进行k次交易.

注意:

不能同时参加多个交易(也就是说: 我们必须在再次买入之前把之前的股票卖掉).

示例1

Input: [2,4,1], k = 2
Output: 2
解释: 在第1天买入 (price = 2), 然后在第2天卖出 (price = 4), 利润为: 4-2 = 2.

示例2

Input: [3,2,6,5,0,3], k = 2
Output: 7
解释: 在第2天买入 (price = 2), 然后在第3天卖出 (price = 6), 利润为: 6-2 = 4. 然后在第5天买入(price = 0), 然后在第6天卖出 (price = 3), 利润为: 3-0 = 3.

解题思路

考虑使用动态规划法进行求解, 用数学形式描述问题:

  • 使用一个global[i][j]来表示前i天最多进行j次交易的最大利润
  • 使用一个local[i][j]来表示前i天最多进行j次交易并且第i天进行进行最后一次交易的最大利润

接下来需要获得两个变量的推导公式, 首先, global[i][j] 有两种情况:

  • i天进行第j次交易(局部)
  • i-1天之前已经进行了j次交易(全局)

因此, global[i][j] = max(local[i][j], global[i-1][j]), 注意: 不做特殊说明的话, diff = prices[i] - prices[i-1]

接下来, local[i][j]也有两种情况:

  • i-1天之前进行了j-1次交易(全局), 然后在第i天进行第j次交易, 那么分歧点在于是前一天买入还是当天买入: global[i-1][j-1] + max(diff, 0)
  • 把第i-1天进行的第j次交易挪到第i天进行, 也就是: local[i-1][j] + diff

从而得到: local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)

这样, 得到遍历公式之后最后取到glocal[len(prices)-1][k]的值即可.

最后, 需要特别考虑: 当k远大于len(prices)时, 用动态规划法算法复杂度就很复杂了…

这个时候, 问题就退化为了可以进行无限次数交易了, 非常简单: 只要后一天的价格高于当天, 那么就可以买入啦.

代码

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        def solveMaxProfit(prices):
            res = 0
            for i in range(1, len(prices)):
                if prices[i] - prices[i-1] > 0:
                    res += prices[i] - prices[i-1]
            return res
        def max(x, y):
            return x if x > y else y
        if k > len(prices):
            # 如果k大于天数, 那么就可以随意交易了
            return solveMaxProfit(prices)
        days = len(prices)
        local_profit = [[0 for _ in range(k+1)] for _ in range(days)]
        global_profit = [[0 for _ in range(k+1)] for _ in range(days)]
        for i in range(1, days):
            diff = prices[i] - prices[i-1]
            for j in range(k, 0, -1):
                local_profit[i][j] = max(global_profit[i-1][j-1] + max(diff, 0), local_profit[i-1][j] + diff)
                global_profit[i][j] = max(local_profit[i][j], global_profit[i-1][j])
        #print(global_profit)
        return global_profit[days-1][k]
s = Solution()
prices = [2,4,1]
k = 2
print(s.maxProfit(k, prices))
prices = [3,2,6,5,0,3]
k = 2
print(s.maxProfit(k, prices))
2
7

189. Rotate Array

问题难度: ♣

问题描述

给定一个数组, 从右边开始旋转数组, 一共旋转k次, 其中k为非负数.

示例1

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
解释:
从右边起旋转1步: [7,1,2,3,4,5,6]
从右边起旋转2步: [6,7,1,2,3,4,5]
从右边起旋转3步: [5,6,7,1,2,3,4]

示例2

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
解释: 
从右边起旋转1步: [99,-1,-100,3]
从右边起旋转2步: [3,99,-1,-100]

注意:
– 试着使用尽可能多的方法, 至少有3种不同的方法解决这个问题
– 能否只使用O(1)的额外空间来解决这个问题?

解题思路

首先, 当k >= len(nums)的时候, 等价于移动k % len(nums)步.

方法1: 从右其旋转k步, 其实就是将nums[-k:] 挪到前面, 将nums[:-k]挪到后面就行了

方法2: 一步一步地挪动, 直到挪到k步为止(然而, 这种方法超时了…)

方法3: 基于方法2 改进一下, 不用挪动k步, 其实一开始就能直到每个数字挪动到哪儿:

- 针对`0~ -k`的数, 应该要向右移动`k`步
- 针对`-k~ len(nums)`的数, 应该要向左移动`len(nums) - i`步

这样, 移动一次就行, 这种方法其实也是第1种方法的改进版, 减少内存的使用, 只用存储一个after就行了.

方法4: 基于方法3, 可以看出一步交换的位置, 但是, 涉及到一个循环, 例如[-1,-100,3,99] k=2:
i=0 nums[0] = -1时, next_i = i + k = 2, tmp = nums[2] = 3, nums[2] = -1, nums = [-1, -100, -1, 99]
i=2 tmp = 3时, next_i = i-k = 0, tmp = nums[0] = -1, nums[0] = 3, nums = [3, -100, -1, 99]

此时, next_i = 0 就终止了.

  • i=1 nums[1] = -100时, next_i = i + k = 3, tmp = nums[3] = 99, nums[3] = -100, nums = [-1, -100, -1, -100]
  • i=3 tmp = 99时, next_i = i - k = 1, tmp = nums[1] = -100, nums[1] = 99, nums = [-1, 99, -1, 100]

循环终止.

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        num_len = len(nums)
        if k >= num_len:
            k = k % num_len
        after, before = nums[:-k], nums[-k:]
        for i in range(len(before)):
            nums[i] = before[i]
        for i in range(len(after)):
            nums[i+len(before)] = after[i]

    def rotateStep(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        num_len = len(nums)
        if k >= num_len:
            k = k % num_len
        #print k
        while k > 0:
            right = nums[-1]
            tmp = nums[0]
            for i in range(1, num_len):
                now = nums[i]
                nums[i] = tmp
                tmp = now
            nums[0] = right
            k -= 1

    def rotateLess(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        num_len = len(nums)
        if k >= num_len:
            k = k % num_len
        after = nums[:-k]
        for i in range(k):
            nums[i] = nums[num_len - k + i]
        for i in range(len(after)):
            nums[i+k] = after[i]

    def rotateSwap(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        num_len = len(nums)
        if k >= num_len:
            k = k % num_len
        def nextPos(i):
            if i >=0 and i < num_len - k:
                return i + k
            else:
                return i + k - num_len
        if k > 0:
            change_num = 0
            start_i = 0
            while change_num < num_len:
                start = nums[start_i]
                next_i = nextPos(start_i)
                while next_i != start_i:
                    # 当下一个i不等于起始i时, 继续遍历
                    tmp = nums[next_i]
                    nums[next_i] = start
                    start = tmp
                    next_i = nextPos(next_i)
                    change_num += 1
                nums[next_i] = start
                change_num += 1
                start_i += 1
s = Solution()
nums = [-1,-100,3,99]
k = 1
s.rotate(nums, k) 
print nums
nums = [-1,-100,3,99]
s.rotateLess(nums, k)
print nums
nums = [-1,-100,3,99]
s.rotateStep(nums, k)
print nums
nums = [-1,-100,3,99]
s.rotateSwap(nums, k)
print nums
nums = [1,2,3,4,5,6,7]
k = 32
s.rotate(nums, k) 
print nums
nums = [1,2,3,4,5,6,7]
s.rotateLess(nums, k)
print nums
nums = [1,2,3,4,5,6,7]
s.rotateStep(nums, k)
print nums
nums = [1,2,3,4,5,6,7]
s.rotateSwap(nums, k)
print nums
[99, -1, -100, 3]
[99, -1, -100, 3]
[99, -1, -100, 3]
[99, -1, -100, 3]
[4, 5, 6, 7, 1, 2, 3]
[4, 5, 6, 7, 1, 2, 3]
[4, 5, 6, 7, 1, 2, 3]
[4, 5, 6, 7, 1, 2, 3]

190. Reverse Bits

问题难度: ♣

问题描述

翻转32位无符号整数的位.

示例1

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
解释: 输入的二进制字符串为 00000010100101000001111010011100 表示无符号整数 43261596, 因此返回二进制表示为 00111001011110000010100101000000 的 964176192.

示例2

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
解释: 输入的二进制字符串 11111111111111111111111111111101 表示无符号整数 4294967293, 因此返回二进制表示为 10101111110010110010011101101001 的 3221225471.

注意:
– 在一些类似于java的语言中, 没有无符号整数类型. 在这种情况下, 输入和输出都给定为有符号整数类型, 由于整数的内部二进制表示无论是有符号还是无符号的都不会影响我们的实现
– 在Java中, 表一起使用2的补位表示有符号整数, 因此, 在示例2中, 输入表示有符号整数-3, 而输出表示为有符号的整数-1073741825.

延伸:
– 如果函数调用多次, 如何进行优化?

解题思路

最简单的想法: 直接分析字符串, 将整数转化为二进制, 然后再将二进制进行翻转, 最后再将二进制转化为整数即可.

代码

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        bin_str = bin(n).replace('0b', '')
        bit_size = 32
        bin_size = len(bin_str)
        reverse_str = ""
        for i in range(bin_size):
            index = bin_size - i - 1
            reverse_str += bin_str[index]
        for i in range(bit_size-bin_size):
            reverse_str += "0"
        return int(reverse_str, 2)
s = Solution()
n = 10
print(s.reverseBits(n))
n = 43261596
print(s.reverseBits(n))
n = 4294967293
print(s.reverseBits(n))
1342177280
964176192
3221225471

191. Number of 1 Bits

问题难度: ♣

问题描述

写一个函数, 输入是一个无符号的整数, 然后返回其二进制中1的个数(也被称为”汉明权重”).

示例1

Input: 00000000000000000000000000001011
Output: 3
解释: 二进制字符串 00000000000000000000000000001011 总共有3个'1'.

示例2

Input: 00000000000000000000000010000000
Output: 1
解释: 二进制字符串 00000000000000000000000010000000 总共有1个'1'.

示例3

Input: 11111111111111111111111111111101
Output: 31
解释: 二进制字符串 11111111111111111111111111111101 一共有31个'1'.

注意:
– 在一些类似于java的语言中, 没有无符号整数类型. 在这种情况下, 输入和输出都给定为有符号整数类型, 由于整数的内部二进制表示无论是有符号还是无符号的都不会影响我们的实现
– 在Java中, 表一起使用2的补位表示有符号整数, 因此, 在示例2中, 输入表示有符号整数-3.

解题思路

移位操作: 针对当前数字, 将其于1进行位与操作, 然后右移一位, 算总数即可.

代码

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        for _ in range(32):
            res += (n&1)
            n = n >> 1
        return res
s = Solution()
n = 0b00000000000000000000000010000000
print(s.hammingWeight(n))

n = 0b00000000000000000000000000001011
print(s.hammingWeight(n))

n = 0b11111111111111111111111111111101
print(s.hammingWeight(n))
1
3
31

192. Word Frequency

问题难度: ♣ ♣ ♣

问题描述

写一个bash脚本来计算文本文件words.txt中每个单词的频率.

为了简单表示, 可以假设:

  • words.txt只包含小写字母或者' '空格
  • 每个单词只有小写字母组成
  • 每个单词之间由一个或多个空格分割

示例

假设words.txt中包含下列内容:

the day is sunny the the
the sunny is is

脚本输出下面的内容, 倒序进行排列:

the 4
is 3
sunny 2
day 1

注意:

  • 不用担心中间点, 可以假设没有相同计数的单词
  • 能否使用Unix pipe的方式完成?

解题思路

算法思路其实挺简单的: 先分割字符串, 然后使用一个dict来存储相应的计数, 再基于计数进行倒序排列, 最后输出对应的单词和计数即可.

现在重点是怎么使用bash脚本完成这个算法过程了~~~

  • grep 查找
  • [[:alpha:]]表示字母
  • grep -E -o "\b[[:alpha:]]+\b" 匹配出所有的单词
  • count[XXX]shell中的字典
  • awk BEGIN 为处理文件之前的操作, 而END 为处理文件之后的操作, 不匹配任何行, 常用语输出一些总结信息

代码

grep -E -o "\b[[:alpha:]]+\b" words.txt | awk ' { count[$0]++ }
END{
for(word in count)
{printf("%s %s\n",word,count[word])}
}' | sort -k2nr

193. Valid Phone Numbers

问题难度: ♣

问题描述

给定一个包含多行电话号码列表的文件file.txt(每一行表示一个电话号码), 写一个一行bash脚本输出所有有效的电话号码.

可以假设一个有效的电话号码必须满足下面两种形式之一:(xxx) xxx-xxxx 或者 xxx-xxx-xxxx. (x表示一个数字)

也可以假设文本文件中的每一行开头和结尾都不会包含空格.

示例:

假设file.txt有下列内容:

987-123-4567
123 456 7890
(123) 456-7890

我们的脚本应该要输入下面有效的电话号码:

987-123-4567
(123) 456-7890

解题思路

题目中提到了两种形式:

  • (xxx) xxx-xxxx对应\(\d{3}\) \d{3}-\d{4}
  • xxx-xxx-xxxx对应\d{3}-\d{3}-\d{4}

合在一起表达为: /^(\([0-9]{3}\) |[0-9]{3}-)[0-9]{3}-[0-9]{4}/, 前面使用awk.

而前面为grep时, 脚本为:^(\d{3}-|\(\d{3}\) )\d{3}-\d{4}, 前面使用grep.

代码

awk '/^(\([0-9]{3}\) |[0-9]{3}-)[0-9]{3}-[0-9]{4}$/' file.txt

grep -P '^(\d{3}-|\(\d{3}\) )\d{3}-\d{4}$' file.txt

194. Transpose File

问题难度: ♣ ♣ ♣

问题描述

给定一个文本文件file.txt, 转置其内容.

可以假设每一行有相同的列数并且每个字段使用' '字符进行分割.

示例:

如果file.txt有下面的内容:

name age
alice 21
ryan 30

输出下面的内容:

name alice ryan
age 21 30

解题思路

这里使用awk脚本进行转置, 可以先阅读参考资料了解下awk的基本用法. 在这里, 我们使用了两个内置变量:
NF: 当前记录中的字段个数,就是有多少列
NR: 已经读出的记录数,就是行号,从1开始

基本思想是:
遍历每一行, 判断下当前行是否为1,如果为1的话, 就新建一个变量; 在后面的每一行中, 就在之前的变量后面加一个空格加新字符.

代码

awk '{
    for(i=1; i<=NF; ++i){
        if(NR==1){s[i]=$i}
        else{s[i]=s[i]" "$i}
    }
}END{
    for(i=1;s[i]!="";++i){
        print s[i]
    }
}' file.txt
打赏

mickey

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

发表评论

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