1, 替换空格
题目描述: 请实现一个函数, 将一个字符串中的每个空格替换成 " ". 例如, 当字符串为 We Are Happy. 则经过替换之后的字符串为 We Are Happy.
分析:
将长度为 1 的空格替换为长度为 3 的 " ", 字符串的长度变长. 如果允许我们开辟一个新的数组来存放替换空格后的字符串, 那么这道题目就非常简单. 设置两个指针分别指向新旧字符串首元素, 遍历原字符串, 如果碰到空格就在新字符串上填入 " ", 否则就复制元字符串上的内容. 但是如果面试官要求 在原先的字符串上操作, 并且保证原字符串有足够长的空间来存放替换后的字符串, 那么我们就得另想方法.
- class Solution:
- def replaceSpace(self, s):
- s = s.replace('','20%')
- return s
- s = Solution()
- print(s.replaceSpace('We Are Happy'))
方法 2:
首先遍历原字符串, 找出字符串的长度以及其中的空格数量, 根据原字符串的长度和空格的数量我们可以求出最后新字符串的长度. 设置两个指针 point1 和 point2 分别指向原字符串和新字符串的末尾位置. (这里为什么取末尾开始遍历, 而不是取起始开始遍历, 是为了利用 point1==point2 这个判断条件) 如果 point1 指向内容不为空格, 那么将内容赋值给 point2 指向的位置, 如果 point1 指向为空格, 那么从 point2 开始赋值 "02%" 直到 point1==point2 时表明字符串中的所有空格都已经替换完毕.
- class Solution:
- def replaceSpace(self, oldStringList):
- blankNumber = 0 #空格数量
- oldStringLen = len(oldStringList)
- #遍历原字符串, 统计字符串中的空格数量
- for i in range(oldStringLen):
- if oldStringList[i] == ' ':
- blankNumber += 1
- #计算新字符串所需要的长度
- newStringLen = oldStringLen + blankNumber*2
- #声明新字符串列表
- newStringList = [' '] * newStringLen
- #设置两个指针, 分别指向原字符串和新字符串的末尾位置
- point_old = oldStringLen - 1
- point_new = newStringLen - 1
- #遍历替换
- while point_old != point_new: #如果两个指针位置不同, 表示没有替换完成
- if oldStringList[point_old] != ' ':
- newStringList[point_new] = oldStringList[point_old]
- point_old -= 1
- point_new -= 1
- else:
- newStringList[point_new] = '0'
- newStringList[point_new-1] = '2'
- newStringList[point_new-2] = '%'
- point_old -= 1
- point_new -= 3
- #指针恰好相同时, 将之前的字符也补上
- if point_old> 0:
- for i in range(point_old, -1, -1):
- newStringList[i] = oldStringList[i]
- #将字符串数组 / 列表组合为字符串
- newString = ''
- for i in range(newStringLen):
- newString += str(newStringList[i])
- return newString
- s = Solution()
- print(s.replaceSpace('We Are Happy'))
2, 正则表达式匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式. 模式中的字符'.'表示任意一个字符, 而'*'表示它前面的字符可以出现任意次 (包含 0 次). 在本题中, 匹配是指字符串的所有字符匹配整个模式. 例如, 字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配, 但是与 "aa.a" 和 "ab*a" 均不匹配.
这道题需要把题意首先仔细研究清楚.
先分享一个较为清晰的思路:
前提条件:'.'表示任意一个字符;'*'表示它前面的字符可以出现任意次 (包含 0 次).
首先, 考虑特殊情况:
1) 两个字符串都为空, 返回 true
2) 当第一个字符串不空, 而第二个字符串空了, 返回 false(因为这样, 就无法匹配成功了, 而如果第一个字符串空了, 第二个字符串非空, 还是可能匹配成功的, 比如第二个字符串是 "a*a*a*a*", 由于'*'之前的元素可以出现 0 次, 所以有可能匹配成功)
之后就开始匹配第一个字符, 这里有两种可能: 匹配成功或匹配失败. 但考虑到 pattern 下一个字符可能是'*', 这里我们分两种情况讨论: pattern 下一个字符为'*'或不为'*':
1)pattern 下一个字符不为'*':
这种情况比较简单, 直接匹配当前字符. 如果匹配成功, 继续匹配下一个; 如果匹配失败, 直接返回 false. 注意这里的 "匹配成功", 除了两个字符相同的情况外, 还有一种情况, 就是 pattern 的当前字符为'.', 同时 str 的当前字符不为'\0'.
2)pattern 下一个字符为'*':
pattern 下一个字符为'*'时, 稍微复杂一些, 因为'*'可以代表 0 个或多个. 这里把这些情况都考虑到:
a) 当'*'匹配 0 个字符时, str 当前字符不变, pattern 当前字符后移两位, 跳过这个'*'符号;
b) 当'*'匹配 1 个或多个时, str 当前字符移向下一个, pattern 当前字符不变.(这里匹配 1 个或多个可以看成一种情况, 因为: 当匹配一个时, 由于 str 移到了下一个字符, 而 pattern 字符不变, 就回到了上边的情况 a; 当匹配多于一个字符时, 相当于从 str 的下一个字符继续开始匹配)
C++ code:
- class Solution {
- public:
- bool match(char* str, char* pattern)
- {
- if(*str=='\0' && *pattern=='\0')
- return true;
- if(*str!='\0' && *pattern=='\0')
- return false;
- if(*(pattern+1)!='*'){
- if(*str==*pattern || (*str!='\0' && *pattern=='.'))
- return match(str+1,pattern+1);
- else return false;
- }
- else{
- if(*str==*pattern || (*str!='\0' && *pattern=='.'))
- return match(str,pattern+2) || match(str+1,pattern);
- else return match(str,pattern+2);
- }
- }
- };
python 版本:
思路: 当模式中的第二个字符是 "*" 时:
如果字符串第一个字符跟模式第一个字符不匹配, 则模式后移 2 个字符, 继续匹配. 如果字符串第一个字符跟模式第一个字符匹配, 可以有 3 种匹配方式:
1. 模式后移 2 字符, 相当于 x * 被忽略;
2. 字符串后移 1 字符, 模式后移 2 字符, 相当于 x * 匹配一位;
3. 字符串后移 1 字符, 模式不变, 即继续匹配字符下一位, 相当于 x * 匹配多位;
当模式中的第二个字符不是 "*" 时:
如果字符串第一个字符和模式中的第一个字符相匹配, 那么字符串和模式都后移一个字符, 然后匹配剩余的部分.
如果字符串第一个字符和模式中的第一个字符相不匹配, 直接返回 False.
- def match(self, s, pattern):
- # write code here
- #如果两者都为空, 则匹配成功
- if (len(s) == 0 and len(pattern) == 0):
- return True
- #如果模式为空, 字符串不为空, 则匹配不成功
- if (len(s)> 0 and len(pattern) == 0):
- return False
- if len(pattern)> 1 and pattern[1] == '*':
- if s and (pattern[0] == '.' or s[0] == pattern[0]):
- f1 = self.match(s[1:], pattern)# 多个
- f2 = self.match(s[1:], pattern[2:])# 一个
- f3 = self.match(s, pattern[2:])# 零个
- if f1 or f2 or f3:
- return True
- else:
- return False
- else:
- return self.match(s, pattern[2:])
- elif s and (pattern[0] == '.' or s[0] == pattern[0]):
- return self.match(s[1:], pattern[1:])
- #如果字符串为空, 模式不为空, 但模式长度等于 1, 或者模式长度大于 1 但第二个字符不为'*', 则匹配不成功
- else:
- return False
另一个:
这道题边界情况也有点多, 首先判断 s 和 pattern 的长度, 分出了四种情况, 其中
1. 如果 s 与 pattern 都为空, 则 True;
2. 如果 s 不为空, 而 pattern 为空, 则 False;
3. 如果 s 为空, 而 pattern 不为空, 判断 pattern 是否是 a... 这种情况,* 可以代表 0 次, 这样一来可以将 pattern 往后移两位再进行 match 递归;
4. 如果 s,pattern 不为空, 又可以分为两种情况:
4.1. 如果 pattern 的第二个字符不为 * 时, 如果 s[0] 与 pattern[0] 能匹配上就将 s 和 pattern 都往后移 1 位再进行 match, 否则不匹配为 False;
4.2. 如果 pattern 的第二个字符为 * 时, 如果 s[0] 与 pattern[0] 匹配不上, 则将 pattern 后移 2 位再进行 match; 如果 s[0] 与 pattern[0] 能匹配上, 会出现三种情况, 分别是 pattern[1] = '\'的 * 代表的三种情况 0,1 或多个, 分别对应 pattern 后移 2 位 s 不变, pattern 后移 2 位, s 后移 1 位, pattern 不变 s 后移 1 位, 这三种情况都有可能出现所以用 or 或运算连接三种情况的递归.
讲的比较麻烦, 不直观, 直接看代码吧.
- # -*- coding:utf-8 -*-
- class Solution:
- # s, pattern 都是字符串
- def match(self, s, pattern):
- # write code here
- len_s = len(s)
- len_pattern = len(pattern)
- # 如果 s 与 pattern 都为空, 则 True
- if len_s == 0 and len_pattern == 0:
- return True
- # 如果 s 不为空, 而 pattern 为空, 则 False
- elif len_s != 0 and len_pattern == 0:
- return False
- # 如果 s 为空, 而 pattern 不为空, 则需要判断
- elif len_s == 0 and len_pattern != 0:
- # pattern 中的第二个字符为 *, 则 pattern 后移两位继续比较
- if len_pattern> 1 and pattern[1] == '*':
- return self.match(s, pattern[2:])
- else:
- return False
- # 如果 s 不为空, pattern 也不为空, 则需要判断
- else:
- # pattern 的第二个字符为 * 的情况
- if len_pattern> 1 and pattern[1] == '*':
- # s 与 pattern 的第一个元素不同, 则 s 不变, pattern 后移两位, 相当于 pattern 前两位当成空
- if s[0] != pattern[0] and pattern[0] != '.':
- return self.match(s, pattern[2:])
- # 如果 s[0] 与 pattern[0] 相同, 且 pattern[1] 为 *
- else:
- # 会有三种情况
- # pattern 后移 2 个, s 不变; 相当于把 pattern 前两位当成空, 匹配后面的, 把 * 当做 0 次
- F1 = self.match(s, pattern[2:])
- # pattern 后移 2 个, s 后移 1 个; 相当于 pattern 前两位与 s[0] 匹配, 把 * 当做 1 次
- F2 = self.match(s[1:], pattern[2:])
- # pattern 不变, s 后移 1 个; 相当于 pattern 前两位, 与 s 中的多位进行匹配, 把 * 当做多次
- F3 = self.match(s[1:], pattern)
- # 有一个为真就能返回真值
- return F1 or F2 or F3
- # pattern 的第二个字符不为 * 的情况
- else:
- # s 和 pattern 的第一个字符匹配上了, 都往后移 1 位
- if s[0] == pattern[0] or pattern[0] == '.':
- return self.match(s[1:],pattern[1:])
- else:
- return False
3, 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值 (包括整数和小数). 例如, 字符串 "+100","5e2","-123","3.1416" 和 "-1E-16" 都表示数值. 但是 "12e","1a3.14","1.2.3","+-5" 和 "12e+4.3" 都不是.
思路: 首先要想到所有的情况, 然后进行分类讨论.-123.45e-67
1,+- 号后面必定为数字或后面为.(-.123 = -0.123)
2,+- 号只出现在第一位或在 eE 的后一位
3,. 后面必定为数字或为最后一位 (233. = 233.0)
4,eE 后面必定为数字或 +- 号
- # -*- coding:utf-8 -*-
- class Solution:
- # s 字符串
- def isNumeric(self, s):
- # write code here
- # 标记符号, 小数点, e 是否出现过
- sign = False
- decimal = False
- hasE = False
- for i in range(len(s)):
- if (s[i] == 'e' or s[i] == 'E'):
- # e 后面一定要接数字
- if (i == len(s)-1):
- return False
- # 不能同时存在两个 e
- if (hasE == True):
- return False
- hasE = True
- elif (s[i] == '+' or s[i] == '-'):
- # 第二次出现 +- 符号, 则必须紧接在 e 之后
- if (sign and s[i-1] != 'e' and s[i-1] != 'E'):
- return False
- # 第一次出现 +- 符号, 且不是在字符串开头, 则也必须紧接在 e 之后
- elif (sign == False and i> 0 and s[i-1] != 'e' and s[i-1] != 'E'):
- return False
- sign = True
- elif (s[i] == '.'):
- # e 后面不能接小数点, 小数点不能出现两次
- if (hasE or decimal):
- return False
- decimal = True
- # 非法字符
- elif(s[i] <'0' or s[i]> '9'):
- return False
- return True
4, 字符流中第一个不重复的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符. 例如, 当从字符流中只读出前两个字符 "go" 时, 第一个只出现一次的字符是 "g". 当从该字符流中读出前六个字符 "google" 时, 第一个只出现一次的字符是 "l".
输出描述:
如果当前字符流没有存在出现一次的字符, 返回 #字符.
分析:
这题其实并不难, 里面需要唯一注意的点就是我们需要返回的字符是 第一次只出现一次的字符, 所以当我们用 map 存储的时候, 因为 map 是乱序的, 所以我们需要额外判断我们返回的字符在字符流中的序号是不是最小.
这题分三步:
新建一个 string input 用来存储我们接收到的所有字符, 同时也能给我们后续判断字符出现的顺序做参照, 再新建一个 hashmap, 用来存储每个字符我们接收过的次数.
insert function 填写: 我们首先判断 hashmap 的 keyset 里有没有当前收到字符, 没有我们需要把 keyset 更新, 有的话我们需要把对应的 value 更新, 同时我们将收到的字符串放进前面我们新建的 string input 里.
FirstAppearingOnce function 填写: 我们需要先新建一个 int index, 来储存我们现在找到的最小的只出现一次的字符的 index, 然后我们新建一个 char result, 因为题目里提到, 如果没有找到符合的字符, 我们需要返回 "#", 所以我们将 char result 设为默认值 "#". 接下来我们遍历整个 hashmap, 如果有只出现一次的字符, 我们记录下它的 index, 如果小于我们创建的 int index, 我们更新 int index, 同时更新我们对应的 result. 最后, 我们 return result 即可.
根据该思路写的 java code:
- import java.util.*;
- public class Solution {
- //Insert one char from stringstream
- String input = "";
- Map<Character,Integer> map = new HashMap<>();
- public void Insert(char ch)
- {
- if(!map.keySet().contains(ch)){
- map.put(ch,1);
- }else{
- map.put(ch,map.get(ch)+1);
- }
- input += ch;
- }
- //return the first appearence once char in current stringstream
- public char FirstAppearingOnce()
- {
- int index = Integer.MAX_VALUE;
- char result = '#';
- for(Character c: map.keySet()){
- if(map.get(c) == 1){
- if(input.indexOf(c) <index){
- index = input.indexOf(c);
- result = input.charAt(index);
- }
- }
- }
- return result;
- }
- }
贴一个 python 的:
- # -*- coding:utf-8 -*-
- class Solution:
- def __init__(self):
- self.s=''
- self.dict={} #创建字典, key 为读取的字符串中的每一个字符, val 为每个字符出现的个数的计数值
- # 返回对应 char
- def FirstAppearingOnce(self):
- # write code here
- for i in self.s: #遍历字符串 s 中的字符
- if self.dict[i]==1: #如果某个字符对应的计数为 1, 则返回该字符
- return i
- return '#' #在所有字符遍历完后, 进行判断
- def Insert(self, char):
- # write code here
- self.s=self.s+char #从字符流中读入字符到字符串 s 中
- if char in self.dict:
- self.dict[char]=self.dict[char]+1 #如果读入的字符在字符串中已存在, 在字典中对应的字符计数加一
- else:
- self.dict[char]=1 #如果读入的字符在字符串中不存在, 则字典中对应的字符计数为一 (即新增了一个新的字符)
5, 二分搜索
leetcode 69. x 的平方根
题目描述:
实现 int sqrt(int x) 函数.
计算并返回 x 的平方根, 其中 x 是非负整数.
由于返回类型是整数, 结果只保留整数的部分, 小数部分将被舍去.
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数, 小数部分将被舍去.
分析: 基本不等式 + 二分法
基本不等式 (a+b)/2>=√ab 推导自 (a-b)^2>= 0, 注意 a>0 且 b>0
- class Solution:
- def mySqrt(self, x: int) -> int:
- r = x
- while r*r> x:
- r = (r + x/r) // 2
- return int(r)
- class Solution:
- def mySqrt(self, x: int) -> int:
- l, h = 0, x
- while l <h:
- m = (l + h) // 2
- if m**2 <= x < (m+1)**2:
- return m
- elif m**2 < x:
- l = m + 1
- else:
- h = m - 1
- return l
方法 1: 库函数
- def mySqrt(self, x):
- """
- :type x: int
- :rtype: int
- """
- return int(math.sqrt(x))
方法 2: 二分法
- class Solution:
- def mySqrt(self, x: int) -> int:
- left = 0
- right = math.ceil(x / 2) #math.ceil(x) 返回大于等于参数 x 的最小整数, 即对浮点数向上取整
- res = 0
- while left <= right:
- mid = left + (right - left) // 2
- tmp = mid * mid
- if tmp == x:
- return mid
- elif tmp <x:
- left = mid + 1
- else:
- right = mid - 1
- return right
方法 3:
- class Solution:
- def mySqrt(self, x: int) -> int:
- r = x
- while r * r> x:
- r = (r + x // r) // 2
- return r
来源: https://www.cnblogs.com/ariel-dreamland/p/12525762.html