python code practice（二）：KMP算法、二分搜索的实现、哈希表

1、替换空格

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

分析：

将长度为1的空格替换为长度为3的“%20”，字符串的长度变长。 如果允许我们开辟一个新的数组来存放替换空格后的字符串， 那么这道题目就非常简单。设置两个指针分别指向新旧字符串首元素， 遍历原字符串，如果碰到空格就在新字符串上填入“%20”， 否则就复制元字符串上的内容。但是如果面试官要求 在原先的字符串上操作，并且保证原字符串有足够长的空间来存放替换后的字符串，那么我们就得另想方法。

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；

讲的比较麻烦，不直观，直接看代码吧。

# -*- 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