Golang每日一练(leetDay0027) 单词搜索、删除有序数组中的重复项 II、搜索旋转排序数组 II-阿里云开发者社区

Golang每日一练(leetDay0027) 单词搜索、删除有序数组中的重复项 II、搜索旋转排序数组 II

2024-01-30 65

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0027) 单词搜索、删除有序数组中的重复项 II、搜索旋转排序数组 II

79. 单词搜索 Word Search

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"

输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"

输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

代码：

package main
import (
  "fmt"
)
func exist(board [][]byte, word string) bool {
  m, n := len(board), len(board[0])
  visited := make([][]bool, m)
  for i := range visited {
    visited[i] = make([]bool, n)
  }
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if dfs(board, visited, i, j, word, 0) {
        return true
      }
    }
  }
  return false
}
func dfs(board [][]byte, visited [][]bool, i, j int, word string, k int) bool {
  if k == len(word) {
    return true
  }
  if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || visited[i][j] || board[i][j] != word[k] {
    return false
  }
  visited[i][j] = true
  if dfs(board, visited, i+1, j, word, k+1) || dfs(board, visited, i-1, j, word, k+1) ||
    dfs(board, visited, i, j+1, word, k+1) || dfs(board, visited, i, j-1, word, k+1) {
    return true
  }
  visited[i][j] = false
  return false
}
func main() {
  board := [][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}
  fmt.Println(exist(board, "ABCCED"))
  fmt.Println(exist(board, "SEE"))
  fmt.Println(exist(board, "ABCB"))
}

输出：

true

false

80. 删除有序数组中的重复项 II Remove-duplicates-from-sorted-array-II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]

输出：5, nums = [1,1,2,2,3]

解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]

输出：7, nums = [0,0,1,1,2,3,3]

解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列

相关题目： 26. 删除有序数组中的重复项

代码：

package main
import (
  "fmt"
)
func removeDuplicates(nums []int) int {
  if len(nums) <= 2 {
    return len(nums)
  }
  i := 1
  for j := 2; j < len(nums); j++ {
    if nums[j] != nums[i-1] {
      i++
      nums[i] = nums[j]
    }
  }
  return i + 1
}
func main() {
  nums := []int{1, 1, 1, 2, 2, 3}
  fmt.Println(removeDuplicates(nums))
  nums = []int{0, 0, 1, 1, 1, 1, 2, 3, 3}
  fmt.Println(removeDuplicates(nums))
}

输出：

暴力枚举：

package main
import (
  "fmt"
)
func removeDuplicates(nums []int) int {
  if len(nums) <= 2 {
    return len(nums)
  }
  for i := 0; i < len(nums); i++ {
    count := 1
    for j := i + 1; j < len(nums); j++ {
      if nums[j] == nums[i] {
        count++
      } else {
        break
      }
    }
    if count > 2 {
      for j := i + 2; j < len(nums); j++ {
        nums[j-2] = nums[j]
      }
      nums = nums[:len(nums)-count+2]
      i--
    }
  }
  return len(nums)
}
func main() {
  nums := []int{1, 1, 1, 2, 2, 3}
  fmt.Println(removeDuplicates(nums))
  nums = []int{0, 0, 1, 1, 1, 1, 2, 3, 3}
  fmt.Println(removeDuplicates(nums))
}

81. 搜索旋转排序数组 II Search-in-rotated-sorted-array-II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0

输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3

输出：false

提示：

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4

进阶：

这是搜索旋转排序数组(题号33)的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

代码：

package main
import (
  "fmt"
)
func search(nums []int, target int) bool {
  left, right := 0, len(nums)-1
  for left <= right {
    mid := left + (right-left)/2
    if nums[mid] == target {
      return true
    }
    // 无法确定左右区间是否有序，只能缩小范围
    if nums[left] == nums[mid] && nums[mid] == nums[right] {
      left++
      right--
    } else if nums[left] <= nums[mid] { // 左区间有序
      if nums[left] <= target && target < nums[mid] {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else { // 右区间有序
      if nums[mid] < target && target <= nums[right] {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }
  return false
}
func main() {
  nums := []int{2, 5, 6, 0, 0, 1, 2}
  fmt.Println(search(nums, 0))
  fmt.Println(search(nums, 3))
}