头像

minecraft-齿轮




离线:4个月前



题目描述

请实现一个函数,把字符串中的每个空格替换成”%20”。

你可以假定输入字符串的长度最大是1000。
注意输出字符串的长度可能大于1000。

样例


输入:"We are happy."

输出:"We%20are%20happy."



算法1

直接调用str对象自带的split()方法来割裂字符串

时间复杂度

最坏情况下O(k+n) ,程序的运算速度取决于split方法的速度

python 代码

class Solution(object):
    def replaceSpaces(self, s):
        """
        :type s: str
        :rtype: str
        """
        dat = s.split(' ')
        data = ''
        for i in dat:data += i + r'%20'
        data = data[:-3]
        return data

算法2

python大法好!
我们直接调用标准库urllib.parse的quote
其效率之高,我无法形容

python 代码

from urllib.parse import quote
class Solution(object):
    def replaceSpaces(self, s):
        """
        :type s: str
        :rtype: str
        """
        return quote(s)



题目描述

blablabla

样例

输入:9
输出:2
解释:9的二进制表示是1001,一共有2个1。
——————
输入:-2
输出:31
解释:-2在计算机里会被表示成11111111111111111111111111111110,
      一共有31个1。

算法

先转化成二进制数,然后判断大小(正数负数)。
正数直接循环找1即可
负数要用32 减去 二进制数的长度。然后找1,找到一个加一个

复杂度

有那么亿点点复杂

Python3 代码

class Solution(object):
    def NumberOf1(self,n):
        """
        :type n: int
        :rtype: int
        """
        bin_num = str(bin(n))
        if n >= 0:
            new_bin_num = bin_num[2:]
            j = 0
            for i in new_bin_num:
                if i == '1':
                    j += 1
            return j
        else:
            new_bin_num = bin_num[3:]
            index =32 - len(new_bin_num)
            for i in new_bin_num:
                if i == '1':
                    index += 1
            return index



算法

准备两个数组,把奇数和偶数分开。
然后把偶数数组链接到奇数数组后面
接着对号入座回array数组即可

Python 代码

class Solution(object):
    def reOrderArray(self, array):
        """
        :type array: List[int]
        :rtype: void
        """
        index = 0
        temp0 = []
        temp1 = []
        while index < len(array):
            if array[index] % 2 == 0:
                temp1.append(array[index])
            else:
                temp0.append(array[index])
            index += 1
        index = 0
        temp0.extend(temp1)
        while index < len(temp0):
            array[index] = temp0[index]
            index += 1