本文正在参加「金石方案 . 分割6万现金大奖」

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

题一：回转字符串

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

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

示例 1：

输入： s = ["h","e","l","l","o"]
输出： ["o","l","l","e","h"]

示例 2：

输入： s = ["H","a","n","n","a","h"]
输出： ["h","a","n","n","a","H"]

解题思路

核心思想就是首尾替换；

这里首选运用双指针，i = 0， j = n-i-1，首尾指针交流值。交流完结之后，一起向中间移动；

代码

/// 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

代码

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：

输入: s = "leetcode"
输出: 0

示例 2：

输入: s = "loveleetcode"
输出: 2

解题思路： 哈希表

判别只呈现一次的字符，经过哈希表缓存，应该算是比较简单解题的。
这里首要想到的是运用哈希表缓存字符的index{char:index}。
别的还有一种方法是：缓存字符呈现次数{char:count}。
这两种方法上还是有一定的差异。这个在后面详细的完成中，咱们能够看到。
除此之外，参考哈希表的完成，能够运用数组到达一样的效果。预设一个长度为26的数组，缓存a-z字母分别呈现的次数。

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

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

代码

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即可回来。

代码

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：

输入: s = "anagram", t = "nagaram"
输出: true

示例 2：

输入: s = "rat", t = "car"
输出: false

解题思路 哈希表、排序法

第一种思路：运用哈希表，处理的方法取决于倾向空间复杂度和时刻复杂度哪一种。

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

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

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

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

代码

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)

代码

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 初级算法之字符串>（下），看看你都学会了吗？》