Go 每周一刷1.0

图片

图片拍摄于2021年1月2日,舟山东极岛。

我说过了,会按照标签来刷题。每一个类别刷四到五题,分两篇文章,第一篇基础题,第二篇稍微变型的题。开篇就从二分开始吧。

Leetcode 704

图片

这是一道最典型的二分基础题,从一个有序集合中查找目标值,还不需要考虑元素重复问题,那么就简单了。


func search(nums []int, target int) int {
  left, right := 0, len(nums)-1
  var mid int
  for left <= right {
    // mid = (left + right) / 2
    // 获取中位数
    mid = left + ((right - left) >> 1)
    // 如果中位数的值等于目标值,找到了,直接返回
    if nums[mid] == target {
      return mid
      // 如果当前中位数的值 > 目标值,说明值只可能存在中位数的左区间,
      // 并且不包括中位数
    } else if nums[mid] > target {
      right = mid - 1
      // 否则当前中位数的值 < 目标值,说明值只可能存在中位数的右区间,
      // 并且不包括中位数
    } else { 
      left = mid + 1
    }
  }
  return -1
}

值得注意的是求中位数的时候如果只是单纯的 mid = (left + right) / 2 ,那么当数字过大时相加会造成溢出,因此这里直接使用位运算。

上面的代码还不是很严谨,比如说,开头过个滤。

if len(nums) == 0 {
    return -1
  }

另外值得讨论的一点是 left <= right ,不少人会在这上面纠结到底是 < 还是 <=。这是因为理解的角度不同,就会有大同小异的解法,就会产生差异化的代码。只要能理解边界的问题,那么咋么写都不重要。但是我依然觉得,好的代码不单单是多么精简和高级的技巧,而是简单易懂。

left 和 right 都是数组的下标,他们代表的是当前查找的范围区间。在程序中通过判断的结果,来更新接下来要查找的区间是往左区间缩小还是右区间缩小。

那什么时候结束呢?

第一,程序已经找到结果了,那当然直接运行结束。

第二,没找到结果,不断的缩小区间,最后这个区间已经缩小成 0,没区间值了,也结束了。

现在你明白上面为什么要 <= 了吧。首先 left 肯定是不能大于 right 的,比如 [5,4] 这能是一个正常区间嘛。至于 = ,道理也很简单,[5,5] 这个区间还有一个公共的 5,如果漏掉,会导致程序出错。

Leetcode 34

图片

这道题比刚才难度提高了一点,同样是查找目标值位置,我们需要返回两个值,一个值是目标值出现的第一个位置以及目标值出现的最后一个位置。

那我们上面还能用嘛?

改改就能用!

本质上对左右区间缩小的判断还是一样的道理。唯一不同的是,之前我们在查找到目标值之后就返回结果,现在不行了。我们得进一步确认目标值是不是对应第一个和最后一个的位置。

func searchRange(nums []int, target int) (res []int) {
  return append([]int{}, findFirstIndex(nums, target), findLastIndex(nums, target))
}

// 查找元素第一个
func findFirstIndex(nums []int, target int) int {
  var mid int
  left, right := 0, len(nums)-1
  for left <= right {
    //如果数字大会造成溢出
    // mid = (left + right)/2 
    //使用位运算
    mid = left + ((right - left) >> 1)
    // 如果当前中位数的值比目标值大,说明目标值只可能存在中位数的左区间(不包括中位数)
    if nums[mid] > target {
      right = mid - 1
      // 如果当前中位数的值比目标值小,说明目标值可能只可能存在中位数的右区间
    } else if nums[mid] < target {
      left = mid + 1
    } else { //说明 此时中位数的值等于目标值,但是不能确定它就是相同目标值的第一个
      //在相等的情况下,如果当前中位数索引处是0,或者当前中位数上一个索引位置的值不等于目标值,那肯定就它了,程序结束
      if mid == 0 || (nums[mid-1] != target) {
        return mid
      } else { //否则的话 肯定在左边,就往左区间再挤挤
        right = mid - 1
      }
    }
  }
  // 如果都没找到,那就返回-1
  return -1
}

// 查找元素最后一个
func findLastIndex(nums []int, target int) int {
  var mid int
  left, right := 0, len(nums)-1
  for left <= right {
    mid = left + ((right - left) >> 1)
    if nums[mid] > target {
      right = mid - 1
    } else if nums[mid] < target {
      left = mid + 1
    } else { //说明 此时中位数的值等于目标值,但是不能确定它就是相同目标值的最后一个
      //在相等的情况下,如果当前中位数索引处于最后一个位置,或者当前中位数下一个索引位置的值不等于目标值,那肯定就它了,程序结束
      if mid == len(nums)-1 || nums[mid+1] != target {
        return mid
      } else { //否则的话,肯定再右边 就往右区间再挤挤
        left = mid + 1
      }
    }
  }
  // 如果都没找到,那就返回-1 
  return -1
}

这期的题目就到这了,你有不一样的解法嘛?那么欢迎留言告诉我。代码放在:github.com/wuqinqiang/LeetCode-Go-...
图片

本作品采用《CC 协议》,转载必须注明作者和本文链接
吴亲库里
讨论数量: 1

感谢分享。 最近在学习golang,也试着用go来解题。 不过都是简单粗暴的解法,还是没有PHP用起来解的舒服啊。难受

3个月前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!