LeetCode 初级算法之字符串（上），看看你都学会了吗？

语言: CN / TW / HK
时间 2022-12-21 03:15:13

theme: juejin highlight: xcode

本文正在参加「金石计划 . 瓜分6万现金大奖」

前言：最近自己也开始系统的刷面试题了，算法是过不去的坎，希望自己能够坚持下去✊，同行的朋友们共勉。

题一：反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1： swift 输入： s = ["h","e","l","l","o"] 输出： ["o","l","l","e","h"] 示例 2： swift 输入： s = ["H","a","n","n","a","h"] 输出： ["h","a","n","n","a","H"]

解题思路

核心思想就是首尾替换；

这里首选使用双指针，i = 0， j = n-i-1，首尾指针交换值。交换完成之后，同时向中间移动；

代码

swift /// s[i] = s[n-i-1] func reverseString(_ s: inout [Character]) { for i in 0..<s.count/2 { s.swapAt(i, s.count-i-1) } }

题二：整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31^,  2^31^ − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

解题思路 数学计算(取余、取商)

  1. 截取个位数
    • 提取个位数 （取余的过程%）
    • 整数截掉个位数 （取商的过程/）
  2. 将个位数添加翻转结果的尾部

推演：\ x:    123 —> 12 —> 1 —> 0\ digit: 0   —>  3  —> 2  —> 1\ res:  0    —>  3 —> 32 —> 321

代码

swift func reverse(_ x: Int) -> Int { var x = x var resource = 0 while x != 0 { // 取出个位数，并弹出 let digit = x%10 x/=10 // 把个位数推入到结果末尾 resource = resource * 10 + digit // swift中有32位数字的最大、最小可以判断是否溢出 if resource > Int32.max || resource < Int32.min { return 0 } } return resource }

题三：字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1： swift 输入: s = "leetcode" 输出: 0 示例 2： swift 输入: s = "loveleetcode" 输出: 2

解题思路： 哈希表

判断只出现一次的字符，通过哈希表缓存，应该算是比较容易解题的。\ 这里首先想到的是使用哈希表缓存字符的index{char:index}。\ 另外还有一种方式是：缓存字符出现次数{char:count}。 这两种方式上还是有一定的区别。这个在后面具体的实现中，我们可以看到。 除此之外，参考哈希表的实现，可以使用数组达到一样的效果。预设一个长度为26的数组，缓存a-z字母分别出现的次数。

解法一：哈希表 （存储下标）

两次循环：第一次循环存储哈希表，第二次循环寻找最小下标\ 如果字典中不存在，则通过key=char，value=index来 存储；\ 如果存在，index改为不合法参数 -1

代码

```swift func firstUniqChar(_ s: String) -> Int { var dict = Character: Int for i in 0..<s.count { let charIndex = s.index(s.startIndex, offsetBy: i) let char = s[charIndex] if dict[char] != nil { dict[char] = -1 } else { dict[char] = i } }

var index = s.count;
for (_,value) in dict {
    if value != -1 && value < index {
        index = value
    }
}
if index == s.count { return -1 }
return index

} ```

解法二：哈希表 （存储频次）

上面的解法中，我们看到还需要再排序，不存在提前跳出的可能性，而哈希表存储次数，在后面的循环中，我们只需要判断次数dict[char] == 1即可返回。

代码

swift func firstUniqChar(_ s: String) -> Int { var dict = [Character: Int]() for char in s { if dict[char] != nil { dict[char]! += 1 } else { dict[char] = 1 } } var index = 0 for char in s { if dict[char] == 1 { return index } index+=1 } return -1 }

题四：有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1： swift 输入: s = "anagram", t = "nagaram" 输出: true 示例 2： swift 输入: s = "rat", t = "car" 输出: false

解题思路 哈希表、排序法

第一种思路：使用哈希表，解决的形式取决于倾向空间复杂度和时间复杂度哪一种。

第二种思路：使用排序法，有效的字母异位词排序后，两个字符串是相同的。

解法一：哈希表，转成字典集合，判断相等

把两个字符串都转成字典，存放每个字符出现的数量。然后再判断两个字典是否相等。

时间复杂度：O(n)\ 空间复杂度：O(2n)

代码

swift func isAnagram(_ s: String, _ t: String) -> Bool { guard s.count == t.count else { return false } var res = true var sDict = [Character: Int]() var tDict = [Character: Int]() var i = 0 while i < s.count { let sChar = s[s.index(s.startIndex, offsetBy: i)] if sDict[sChar] != nil { sDict[sChar]! += 1 } else { sDict[sChar] = 1 } let tChar = t[t.index(t.startIndex, offsetBy: i)] if tDict[tChar] != nil { tDict[tChar]! += 1 } else { tDict[tChar] = 1 } i+=1 } if sDict != tDict { res = false } return res }

解法二：哈希表

将其中一个字符串转成哈希表，哈希表存放字符的频次，index: char - "a",  value: count\ 使用另一个字符串判断是否其中的字符在缓存中，如果没有出现，即count == 0，跳出循环，如果出现，count-1。

时间复杂度：O(2n)\ 空间复杂度：O(n)

代码

swift func isAnagram(_ s: String, _ t: String) -> Bool { var charList = Array<Int>.init(repeating: 0, count: 26) for char in s { let index = (char.asciiValue ?? 0) - (Character("a").asciiValue ?? 0) charList[Int(index)] += 1 } for char in t { let index = (char.asciiValue ?? 0) - (Character("a").asciiValue ?? 0) if charList[Int(index)] == 0 { return false } charList[Int(index)] -= 1 } return true }

解法三：排序法

通过对两字符串进行排序，然后我们再比较两字符串是否相等就可以了。

下篇请看👉《LeetCode 初级算法之字符串>（下），看看你都学会了吗？》

「」
「」