344_反转字符串
387_字符串中的第一个唯一字符
389_找不同
344_反转字符串
题目描述
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：
输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
解题思路
原地修改数组
先获取字符串的长度；获取中间元素的下标，以此为分界线，通过 for 循环，将前后元素进行交换。
方法一：
class Solution:
def reverseString(self, s) :
"""
Do not return anything, modify s in-place instead.
"""
m = len(s) - 1
n = len(s) // 2
for i in range(n):
s[i], s[m - i] = s[m - i], s[i]
return s
方法二：
class Solution: def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
i, j = 0, len(s) - 1
while i<j:
s[i],s[j]=s[j],s[i]
i+=1
j-=1
return s
387_字符串中的第一个唯一字符
题目描述
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = “leetcode”
返回 0.
s = “loveleetcode”,
返回 2.
注意事项：您可以假定该字符串只包含小写字母。
方法一：有序字典（OrderedDict）
from collections import OrderedDict
class Solution(object):
def firstUniqChar(self, s: str) -> int:
odict = OrderedDict()
# 记录字符出现次数
for c in s:
odict[c] = odict[c] + 1 if c in odict else 1
# 利用有序的特性，在字典中找出首个出现次数为一的字符串
for k, v in odict.items():
if v == 1:
# 返回字符串首次出现的位置
return s.index(k)
return -1
方法二：散列表
class Solution:
def firstUniqChar(self, s: str) -> int:
"""
:type s: str
:rtype: int
"""
# build hash map : character and how often it appears
count = collections.Counter(s)
# find the index
for idx, ch in enumerate(s):
if count[ch] == 1:
return idx
return -1
389. 找不同
题目描述
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例:
输入： s = “abcd”
t = “abcde”
输出： e
解释：
‘e’ 是那个被添加的字母。
方法一 ：collections.Counter()
collections.Counter 提供了加减方法。
Counter(t) - Counter(s)后返回值就是多出来的字母，list()后返回即可。
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
return list(collections.Counter(t) - collections.Counter(s))[0]
方法二 ：ASCII 和之差
每一个字符都对应一个 ASCII 数字，那么那个不同的数字的 ASCII 码就等于 t 的所有字符码之和 - s 的
ord 函数将单个字符转换为 ASCII 码， chr 相反
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
return chr(sum(map(ord, t)) - sum(map(ord, s)))