算法题-字符串相关

反转字符串

题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

解法1：递归

def reverseString(s, left, right):
    if left >= right:
        return
    s[left], s[right] = s[right], s[left]
    reverseString(s, left+1, right-1)
alist = ["h","e","l","l","o"]
reverseString(alist, 0, len(alist)-1)
print(alist)

方法2：双指针法：

def reverseString(s):
    left = 0
    right = len(s) - 1
    while(left < right):
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
alist = ["h","e","l"]
reverseString(alist)
print(alist)

无重复字符的最长子串

题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

def lengthOfLongestSubString(s):
    n = len(s)
    ans = 0
    # 定义空字典，记录字符与索引的映射关系
    m = {}
    l = 0
    # 遍历右指针
    for r in range(n):
        if s[r] in m.keys():
            # 如果出现重复字符，左指针直接跳过重复元素之前的字符
            l = max(m[s[r]], l)
        # 取当前字符串长度和原先记录的子字符串长度最大值
        ans = max(ans, r-l+1)
        # 定义字符到索引的映射，即某个字符在字符串中出现的最大位置
        m[s[r]] = r+1
        r += 1
    print(ans)
    return ans

lengthOfLongestSubString("abacddtyghkja")

Fizz Buzz

写一个程序，输出从 1 到 n 数字的字符串表示。

1. 如果 n 是3的倍数，输出“Fizz”；
2. 如果 n 是5的倍数，输出“Buzz”；
   3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
   方法1：模拟法

def fizzBuzz(n):
    ans = []
    for num in range(1, n+1):
        divisible_by_3 = (num % 3 == 0)
        divisible_by_5 = (num % 5 == 0)

        if divisible_by_3 and divisible_by_5:
            ans.append('FizzBuzz')
        elif divisible_by_3:
            ans.append('Fizz')
        elif divisible_by_5:
            ans.append('Buzz')
        else:
            ans.append(str(num))

    return ans

m = fizzBuzz(16)
print(m)

方法2：字符串连接

def fizzBuzz(n):
    ans = []
    for num in range(1, n + 1):
        divisible_by_3 = (num % 3 == 0)
        divisible_by_5 = (num % 5 == 0)
        num_ans_str = ""
        if divisible_by_3:
            num_ans_str += 'Fizz'
        if divisible_by_5:
            num_ans_str += 'Buzz'
        if not num_ans_str:
            num_ans_str = str(n)
        ans.append(num_ans_str)
    return ans

方法3：用散列表

def fizzBuzz(n):
    ans = []
    fizz_buzz_dict = {3: "Fizz", 5: 'Buzz'}
    for num in range(1, n+1):
        num_ans_str = ""
        for key in fizz_buzz_dict.keys():
            if num % key == 0:
                num_ans_str += fizz_buzz_dict[key]
        if not num_ans_str:
            num_ans_str = str(num)
        ans.append(num_ans_str)
    return ans

罗马数字转整数

def romanToInt(s):
    sum = 0
    hashmap = {'I':1,'V':5,'X':10,'L':50,'C':100,
               'D':500,'M':1000}
    pre_num = hashmap[s[0]]
    for i in range(1, len(s)):
        num = hashmap[s[i]]
        if pre_num < num:
            sum -= pre_num
        else:
            sum += pre_num
        pre_num = num
    sum += pre_num
    return sum


s = "LVIII"
print(romanToInt(s))