161. 单个编辑距离 One Edit Distance
给定两个字符串 s 和 t，判断他们的编辑距离是否为 1。
注意：
满足编辑距离等于 1 有三种可能的情形：
往 s 中插入一个字符得到 t
从 s 中删除一个字符得到 t
在 s 中替换一个字符得到 t
示例 1：
输入: s = "ab", t = "acb"
输出: true
解释: 可以将 'c' 插入字符串 s 来得到 t。
示例 2：
输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。
示例 3：
输入: s = "1203", t = "1213"
输出: true
解释: 可以将字符串 s 中的 '0' 替换为 '1' 来得到 t。
代码1： 暴力枚举
package main import "fmt" func isOneEditDistance(s string, t string) bool { m, n := len(s), len(t) if m > n { return isOneEditDistance(t, s) } if n-m > 1 { return false } for i := 0; i < m; i++ { if s[i] != t[i] { if m == n { return s[i+1:] == t[i+1:] } else { return s[i:] == t[i+1:] } } } return m+1 == n } func main() { s := "ab" t := "acb" fmt.Println(isOneEditDistance(s, t)) s = "cab" t = "ad" fmt.Println(isOneEditDistance(s, t)) s = "1203" t = "1213" fmt.Println(isOneEditDistance(s, t)) }
暴力枚举2：
```go func findPeakElement(nums []int) int { n := len(nums) for i := 0; i < n; i++ { if (i == 0 || nums[i] > nums[i-1]) && (i == n-1 || nums[i] > nums[i+1]) { return i } } return -1 } ```
代码2： 递归
package main import "fmt" func isOneEditDistance(s string, t string) bool { if len(s) > len(t) { return isOneEditDistance(t, s) } if len(t)-len(s) > 1 { return false } if len(s) == 0 && len(t) == 0 { return false } else if len(s) == 0 || len(t) == 0 { return true } else if s[0] == t[0] { return isOneEditDistance(s[1:], t[1:]) } else if len(s) == len(t) { return s[1:] == t[1:] || s[1:] == t[:] || s[:] == t[1:] } else { return s[:] == t[1:] } } func main() { s := "ab" t := "acb" fmt.Println(isOneEditDistance(s, t)) s = "cab" t = "ad" fmt.Println(isOneEditDistance(s, t)) s = "1203" t = "1213" fmt.Println(isOneEditDistance(s, t)) }
代码3： 迭代
package main import "fmt" func isOneEditDistance(s string, t string) bool { m, n := len(s), len(t) if m > n { return isOneEditDistance(t, s) } if n-m > 1 { return false } i, j := 0, 0 edited := false for i < m && j < n { if s[i] == t[j] { i++ j++ } else { if edited { return false } edited = true if m == n { i++ j++ } else { j++ } } } return edited || i < m } func main() { s := "ab" t := "acb" fmt.Println(isOneEditDistance(s, t)) s = "cab" t = "ad" fmt.Println(isOneEditDistance(s, t)) s = "1203" t = "1213" fmt.Println(isOneEditDistance(s, t)) }
输出：
true
false
true
162. 寻找峰值 Find Peak Element
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]
代码1： 暴力枚举
package main import "fmt" func findPeakElement(nums []int) int { n := len(nums) if n == 1 { return 0 } for i := 0; i < n; i++ { if i == 0 { if nums[i] > nums[i+1] { return i } } else if i == n-1 { if nums[i] > nums[i-1] { return i } } else { if nums[i] > nums[i-1] && nums[i] > nums[i+1] { return i } } } return -1 } func main() { nums := []int{1, 2, 3, 1} fmt.Println(findPeakElement(nums)) nums = []int{1, 2, 1, 3, 5, 6, 4} fmt.Println(findPeakElement(nums)) }
输出：
2
1
代码2： 二分查找
package main import "fmt" func findPeakElement(nums []int) int { n := len(nums) if n == 1 { return 0 } left, right := 0, n-1 for left < right { mid := left + (right-left)/2 if nums[mid] < nums[mid+1] { left = mid + 1 } else { right = mid } } return left } func main() { nums := []int{1, 2, 3, 1} fmt.Println(findPeakElement(nums)) nums = []int{1, 2, 1, 3, 5, 6, 4} fmt.Println(findPeakElement(nums)) }
递归形式：
```go func findPeakElement(nums []int) int { return search(nums, 0, len(nums)-1) } func search(nums []int, left, right int) int { if left == right { return left } mid := left + (right-left)/2 if nums[mid] > nums[mid+1] { return search(nums, left, mid) } return search(nums, mid+1, right) } ``
输出：
2
5
