剑指offer-字符串&数字规律

1. 表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

解：

思考方向应该是把非法的情况列举出来，合法的情况太多了。这题比较繁琐。

 1 class Solution:

 2     # s字符串

 3     def isNumeric(self, s):

 4         # write code here

 5         if not s:

 6             return False

 7         n = len(s)

 8         sign, decimal, hasE = False, False, False

 9         for i in range(n):

10             if s[i] in {'e', 'E'}:

11                 if i == n-1:

12                     return False  # e后面要接数字

13                 if hasE:

14                     return False  # 不能有两个e

15                 hasE = True

16             elif s[i] in {'+', '-'}:

17                 if sign and s[i-1] not in {'e', 'E'}:  # 第二次出现+-，必须在e后面

18                     return False

19                 if not sign and i > 0 and s[i-1] not in {'e', 'E'}:  # 第一次出现+-，且不是开头，也必须在e后面

20                     return False

21                 sign = True

22             elif s[i] == '.':

23                 if hasE or decimal:  # e后面不能有小数点，小数点不能出现两次

24                     return False

25                 decimal = True

26             elif s[i] < '0' or s[i] > '9':  # 非法字符

27                 return False

28         return True

2. 字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

输出描述:

如果当前字符流没有存在出现一次的字符，返回#字符。

解：

用哈希表

 1 class Solution:

 2     # 返回对应char

 3     def __init__(self):

 4         self.strs = ''

 5         self.hashmap = dict()

 6

 7     def FirstAppearingOnce(self):

 8         # write code here

 9         if not self.strs:

10             return '#'

11         n = len(self.strs)

12

13         first_index = n

14         for key, value in self.hashmap.items():

15             if value[0] == 1:

16                 first_index = min(first_index, value[1])

17         return '#' if first_index == n else self.strs[first_index]

18

19     def Insert(self, char):

20         # write code here

21         self.strs += char

22         count, index = self.hashmap.get(self.strs[-1], (0, -1))

23         self.hashmap[self.strs[-1]] = (count+1, len(self.strs)-1)

3.替换空格

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

解：

递归实现

1 class Solution:

2     # s 源字符串

3     def replaceSpace(self, s):

4         # write code here

5         if not s:

6             return s

7         if s[0] == ' ':

8             return '%20' + self.replaceSpace(s[1:])

9         return s[0] + self.replaceSpace(s[1:])

扫一遍记录位置，然后挨个替换，注意替换过程中原先记录的索引会改变，要对应好。

 1 class Solution:

 2     # s 源字符串

 3     def replaceSpace(self, s):

 4         # write code here

 5         if not s:

 6             return s

 7         tobeReplace = []

 8         n = len(s)

 9         for i in range(n):

10             if s[i] == ' ':

11                 tobeReplace.append(i)

12         m = len(tobeReplace)

13         for j in range(m):

14             s = s[:tobeReplace[j]+2*j] + '%20' + s[tobeReplace[j]+2*j+1:]

15         return s

4. 扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何，如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

解：

这题表述有点蛋疼。。。其实就是给定一串字符，判断是不是顺子，其中大小王都是0可以当作赖子牌用。这题可以先sort一下然后统计有多少赖子牌，然后从第一张不是赖子的牌开始，如果后一张不是连续的，就可以拿赖子牌补。如果有两张同样的牌还不是赖子，那肯定不是顺子；如果赖子被补位完了还不够，也不是顺子。

 1 class Solution:

 2     def IsContinuous(self, numbers):

 3         # write code here

 4         if not numbers:

 5             return False

 6         n = len(numbers)

 7         numbers.sort()

 8         laizi = 0

 9         for i in range(n):

10             if numbers[i] == 0:

11                 laizi += 1

12             else:

13                 break

14

15         for j in range(i, n-1):

16             if numbers[j+1] == numbers[j]:

17                 return False

18             laizi -= numbers[j+1] - numbers[j] - 1

19             if laizi < 0:

20                 return False

21         return True

5. 字符串转化为整数

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。

解：

判断字符串能否转换为整数，加减号只能出现在开头，其他位置只能是数字字符。用栈来存

 1 class Solution:

 2     def StrToInt(self, s):

 3         # write code here

 4         if not s:

 5             return 0

 6         d = {'0','1','2','3','4','5','6','7','8','9'}

 7         stack = []

 8         for i, char in enumerate(s):

 9             if char in d:

10                 stack.append(int(char))

11             elif i == 0 and char in {'+', '-'}:

12                 continue

13             else:

14                 return 0

15         ans = 0

16         if not stack:

17             return 0

18         for num in stack:

19             ans = 10*ans + num

20         return -ans if s[0] == '-' else ans

6. 左旋转字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

解：

一个思路两种写法。一次左移一位，移n次；

 1 class Solution:

 2     def LeftRotateString(self, s, n):

 3         # write code here

 4         if not s or not n:

 5             return s

 6         for i in range(n):

 7             s = self.ROL(s)

 8         return s

 9

10     def ROL(self, s):

11         return s[1:]+s[0]

循环实现；一次截好所有要左移的部分，需要取 mod

1 class Solution:

2     def LeftRotateString(self, s, n):

3         # write code here

4         if not s or not n:

5             return s

6         n %= len(s)

7         return s[n:]+s[:n]

7. 翻转单词顺序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

解：

先全部翻转，再按空格切分后每个单词单独翻转，再用空格 join 起来

 1 class Solution:

 2     def ReverseSentence(self, s):

 3         # write code here

 4         s = self.Reverse(s)

 5         words = s.split(' ')

 6         n = len(words)

 7         for i in range(n):

 8             words[i] = self.Reverse(words[i])

 9         return ' '.join(words)

10

11     def Reverse(self, s):

12         return s[::-1]

8. 第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

解：

用哈希表统计次数。然后从头遍历判断即可。

 1 from collections import Counter

 2 class Solution:

 3     def FirstNotRepeatingChar(self, s):

 4         # write code here

 5         if not s:

 6             return -1

 7         count = dict(Counter(s))

 8

 9         for i in range(len(s)):

10             if count[s[i]] == 1:

11                 return i

12         return -1

9. 整数中1出现的次数

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解：

通过使用一个位置乘子m 遍历数字的位置, m 分别为1,10,100,1000…etc.（m<=n）

对于每个位置来说，把10进制数分成两个部分，比如说当m=100的时候，把十进制数 n=3141592 分成 a=31415 和 b=92 ，以此来分析百位数为1时所有数的个数和。

m=100时，百位数的前缀为3141，当百位数大于1时，为3142*100，因为当百位数大于1时，前缀可以为0，即百位数可以从100到199，共100个数；当百位数不大于1时，为3141*100

如何判断百位数是否大于1？假设百位数为x，若 (x+8)//10 等于1，则大于1，若 (x+8)//10 等于0，则小于1。因此前缀可用 (n//m + 8)//10 *m来计算(若计算2的个数，可以改为（n//m + 7）//10*m,若计算3的个数，改为（n//m + 6）//10*m，…以此类推)。

再例如m=1000时，n分为a=3141和 b=592；千位数的前缀为314，千位数不大于1，故前缀计算为314*1000；因为千位数为1，再加b+1(0到592)。即千位数为1的所有数的个数和为314*1000+592+1；公式（n//m + 8）//10*m + b +1。

注意：只有n的第m位为1时需要计算后缀，后缀计算为（n//m%10==1）*(b+1)，

即（n//m%10==1）判断第m位是否为1，若为1，则加上（b+1），若不为1，则只计算前缀。（若计算2的个数，可以改为（n//m%10==2）*(b+1)，若计算3的个数，可以改为（n//m%10==3）*(b+1)…以此类推）

 1 class Solution:

 2     def NumberOf1Between1AndN_Solution(self, n):

 3         # write code here

 4         cnt = 0

 5         a, b = 0, 0

 6         m = 1

 7         while m <= n:

 8             a = n//m

 9             b = n%m

10             cnt += (a+8)//10*m + (a%10 == 1)*(b+1)

11             m *= 10

12         return cnt

10. 把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解：

先把数字转成字符。自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较 s1+s2 和 s2+s1 那个大按字符比较，如果 s1+s2 大，那说明 s2 应该放前面

 1 class Solution:

 2     def PrintMinNumber(self, numbers):

 3         # write code here

 4         if not numbers:

 5             return ''

 6         def cmp(a, b):

 7             if a < b:

 8                 return -1

 9             elif a > b:

10                 return 1

11             return 0

12         numbers = list(map(lambda x: str(x), numbers))

13         numbers = sorted(numbers, cmp=lambda x, y: cmp(x+y, y+x))  # py3: key=functools.cmp_to_key(cmp)

14         return ''.join(numbers).lstrip('0') or '0'  # 去掉所有左边的0，以及避免全为0的测试用例

巴特西

剑指offer-字符串&数字规律

最新文章

热门文章