相关疑难解决方法(0)

Python允许从给定base的字符串中轻松创建整数

int(str, base). 

我想执行逆向:从整数创建一个字符串,即我想要一些函数int2base(num, base),这样:

int(int2base(x, b), b) == x

函数名称/参数顺序并不重要.

对于任何数量x和底座b是int()会接受的.

这是一个很容易编写的函数:实际上它比在这个问题中描述它更容易.但是,我觉得我必须遗漏一些东西.

我知道的功能bin,oct,hex,但我不能使用他们的几个原因:

• 这些函数在旧版本的Python上不可用,我需要与它兼容(2.2)

• 我想要一个通用的解决方案,可以用不同的基础调用相同的方法

• 我想允许2,8,16以外的碱基

有关

• Python优雅的反函数int(字符串,基数)
• 使用python中的递归整数到base-x系统
• 在Python中进行Base 62转换
• 如何在Python中将整数转换为最短的url-safe字符串？

我正在研究CTCI的一个问题.

第1章的第三个问题是你带一个字符串如

'Mr John Smith '

并要求您用以下内容替换中间空格%20:

'Mr%20John%20Smith'

作者在Python中提供了这个解决方案,称之为O(n):

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    counter = 0
    output = ''
    for char in string:
        counter += 1
        if counter > length:
            return output
        elif char == ' ':
            output = output + '%20'
        elif char != ' ':
            output = output + char
    return output

我的问题:

我理解这是从左到右扫描实际字符串的O(n).但是Python中的字符串不是不可变的吗？如果我有一个字符串,我用+操作符添加另一个字符串,它是否分配必要的空格,复制原始字符串,然后复制附加字符串？

如果我有一个n长度为1 的字符串集合,则需要:

1 + 2 + 3 + 4 …

这是我学校过去一年中期论文的问题.下面附有一张图,用于显示机器人如何从同一张纸上移动.我的担忧在橙色部分中说明.

基本上,只要机器人遇到左侧未看到的网格方块,机器人就会向前移动并向左转.

给予机器人横向3号网格的指令序列是:('F','T','F','T','F','F','T','F',' F','T','F','F','F')其中'F'表示向前移动一个方格,'T'表示向左转90度.请注意,最后一条指令会导致机器人退出网格.函数gen_seq将网格的大小作为输入,并返回机器人横向网格的指令序列.指令序列是一个包含字符串'F'和'T'的元组,它们代表forward和turn命令.

提供函数gen_seq的递归或迭代实现.提示:Recall int可以与元组相乘.

说明实施时间和空间的增长顺序,并解释您的答案.

这些是markscheme中建议的答案.

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (n-1)*('F',)
        seq += side + side + ('F',)
    return seq

时间:O(n ^ 3).在每个函数调用(递归)或循环(迭代)中,创建螺旋的每个"层"的路径长度的新元组.由于螺旋的长度是n ^ 2,并且有n个函数调用或循环运行n次,因此总时间是n ^ 2*n = O(n3).换句话说,它是平方和:1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ::: + …

如果我需要在Python 2.7中实现字符串反向而不是使用系统库,那么想知道是否有更高效的解决方案？我试过我的代码运行速度很慢很长的字符串(例如几千个字符).谢谢.

对于字符串反转,我的意思是,例如,给定s ="hello",返回"olleh".

def reverseString(self, s):
    """
    :type s: str
    :rtype: str
    """
    if not s:
        return ''
    temp = []
    result=''
    for i in range(len(s)-1,-1,-1):
        result += s[i]
    return result

问候,林

在这两个语句中，我都将一个字符附加"a"到字符串中s：

1. s += "a"
2. s = s + "a"

Python 中哪个语句的时间复杂度更好？