字符串

一、题目列表

题目1、第一个只出现一次的字符

题目2、替换空格 JZ5

题目3、整数中1出现的次数（从1到n整数中1出现的次数）

二、所有题目

题目1、第一个只出现一次的字符

JZ50
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

数据范围：1≤n≤10000，且字符串只有字母组成。
要求：空间复杂度 O(n)，时间复杂度 O(n)

1.思路

比较简单

2.代码

class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        # write code here
        mp = dict()
        #统计每个字符出现的次数
        for i in str:
            if i in mp:
                mp[i] += 1
            else:
                mp[i] = 1
        #找到第一个只出现一次的字母
        for i in range(len(str)):
            if mp[str[i]] == 1:
                return i
        #没有找到
        return -1

题目2、替换空格

JZ5
描述
请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

数据范围:1≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。

1.思路

比较简单

2.代码

class Solution:
    def replaceSpace(self , s: str) -> str:
        # write code here
        res=""
        for char in s:
            if(char==" "):
                res+="%20"
            else:
                res+=char
        return res

题目3、JZ43 整数中1出现的次数（从1到n整数中1出现的次数）

描述
输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

示例1
输入：
13
复制
返回值：
6

1.思路

方法一：循环所有数字，然后转换为字符串，每一位比对
方法二：循环所有数字，按照数学每一位比对

时间复杂度：O(nlog10n)
外循环一共循环nnn次，内循环最大循环次数不会超过最大数字n的位数即log10n
空间复杂度：O(1)，常数级变量，无额外辅助空间使用

2.代码

方法一：
class Solution:
    def NumberOf1Between1AndN_Solution(self , n: int) -> int:
        res = 0
        #遍历1-n
        for i in range(n):
            #遍历每个数的每一位
            for j in str(i+1):
                if j=='1':
                    res +=1
        return res


方法二：
class Solution:
    def NumberOf1Between1AndN_Solution(self , n: int) -> int:
        res = 0
        #遍历1-n
        for i in range(1, n + 1):
            #遍历每个数的每一位
            j = i
            while j > 0:
                #遇到数字1计数
                if j % 10 == 1:
                    res += 1
                j = j // 10
        return res