用python手刃Lintcode（一）

古城微笑少年丶 2021-12-15 01:55 220阅读 0赞

### lintcode（8） ###

#### 题目： ####

给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)。

**样例**

> 对于字符串 “abcdefg”.
> 
> offset=0 => “abcdefg”
> 
> offset=1 => “gabcdef”  
> offset=2 => “fgabcde”
> 
> offset=3 => “efgabcd”

**挑战**

在数组上原地旋转，使用O(1)的额外空间

#### 解答: ####

首先，想到利用python的切片操作。

class Solution:
        """
        @param str: An array of char
        @param offset: An integer
        @return: nothing
        """
        def rotateString(self, str, offset):
            # write your code here
            ret = str[-offset:]
            for i in range(offset):
                t = str.pop()
                str.insert(0,t)

这道题目里蕴含着出栈入栈的思想。

当然，如果在面试中，一定要考虑以下几个特殊情况：

1.  offset的值大于数组的长度：除以数组长度，直到在数组长度范围之内。  
    比如说：offset = 7，len（str）=4。可以用7%4,得到3作为新的offset值。
2.  基本的用户输入，输出有错问题。比如说str为空，offset为空的问题。  
    即加入如下代码：

##判断输入是否为空
    if not offset: return
    if not s: return
    
    ##防止offset超出数组长度
    n = len(s)
    offset = offset%n

#### 附：本题知识点 ####

1.  list.pop()：默认删除列表(或者字符串)的最后一个函数，返回删除的值。当然，也可以指定参数，删除列表里的任一值。  
    比如：

list =[1,2,3,4,5]
    t = list.pop()##list变为[1,2,3,4],t = 5
    t = list.pop(index = 1)##list变为[1,3,4,5],t = 2

1.  list.insert(索引,值)：在list的某个索引位置插入值。

list =[1,2,3,4,5]
    list.insert(0,6)##list变为[6,1,2,3,4]

以上两个函数配合使用，可以达到队列的效果【大话数据结构中提及过】

1.  本题目要求返回值为空，也就说说要直接更改原来数组的内容，  
    【直接用str = 'efgabcd’为什么不行？？】

### lintcode（9）Fizz Buzz 问题 ###

#### 问题： ####

给你一个整数n. 从 1 到 n 按照下面的规则打印每个数：

如果这个数被3整除，打印fizz.  
如果这个数被5整除，打印buzz.  
如果这个数能同时被3和5整除，打印fizz buzz.  
如果这个数既不能被 3 整除也不能被 5 整除，打印数字本身。

**样例**

> 比如 n = 15, 返回一个字符串数组：
> 
> \[ “1”, “2”, “fizz”, “4”, “buzz”, “fizz”, “7”, “8”, “fizz”,  
> “buzz”, “11”, “fizz”, “13”, “14”, “fizz buzz” \]

#### 解答： ####

重点是对条件语句的考察。首先可以想到这样一个解答方案。（注意，对于这种需要判断两个整除条件的，可以先判断他们的最小公倍数）

def fizzBuzz(self, n):
            # write your code here
            ret = []
            for i in range(1,n+1):
                if i%15 == 0:
                    ret.append('fizz buzz')
                elif i%3 == 0:
                    ret.append('fizz')
                elif i%5 == 0:
                    ret.append('buzz')
                else :
                    ret.append(str(i))
            return ret

但是这种方案代码比较冗余，现在考虑只使用一个if语句进行判断。  
【待做】

### lintcode（13） ###

这道题的主要难点在于边界情况特别繁琐：

1.  source 和target 都为空：判断条件是source == ‘’
2.  source 和target 都为null：判断条件是source == None(或者是’null’)  
    【这两个情况不一样,一个是空字符串，一个是没有输入，同时，不能用`not source`来判断，因为这个语句下以上两个边界情况都为真】

最终代码：

class Solution:
        """
        @param: source: source string to be scanned.
        @param: target: target string containing the sequence of characters to match
        @return: a index to the first occurrence of target in source, or -1  if target is not part of source.
        """
        def strStr(self, source, target):
            if target == '' :
                return 0
            if not source or target ==None:
                return -1
    
            
            n_s = len(source)
            n_t = len(target)
            for i in range(n_s):
                if source[i] == target[0]:
                    if source[i:i+n_t] == target:
                        return i
            return -1

知识点：python中null，None的区别

当然，也可以使用KMP算法来使时间复杂度降到O（n）：【待做[KMP算法最浅显理解——一看就明白][KMP]

[KMP]: https://blog.csdn.net/starstar1992/article/details/54913261