Leetcode 31-40

31. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解: 重点在于下一个的规则

• code

  func nextPermutation(nums []int)  {
      for i:=len(nums) -1; i>0; i-- {
          if nums[i] > nums[i-1]{
              ind:=i
              for j:=i+1;j<len(nums);j++{
                  if nums[j]>nums[i-1] && nums[j] <= nums[ind]{
                      ind = j
                  }
              }
              swap(nums, ind, i-1)
              reverse(nums[i:])
              return
          } 
      }
      reverse(nums)
  }
  
  
  func reverse(nums []int) {
       i := 0
       j := len(nums) -1
       for i < j {
           swap(nums,i,j)
          i++;
          j--;
      }
  }
  
  
  func swap(nums []int,i ,j int){
      tmp := nums[i]
      nums[i] = nums[j]
      nums[j] = tmp
  }

32. 最长有效括号

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

• code

  func longestValidParentheses(s string) int {
      bytes := []byte(s)
      if len(bytes) < 2 {
          return 0
      }
      lengthList := make([]int, len(bytes))
      var max int
      for i := 1; i < len(bytes); i++ {
          if bytes[i] == ')' {
              j := i - lengthList[i-1] - 1
              if j >= 0 && bytes[j] == '(' {
                  lengthList[i] = lengthList[i-1] + 2
                  if j-1 >= 0 {
                      lengthList[i] += lengthList[j-1]
                  }
              }
          }
          if lengthList[i] > max {
              max = lengthList[i]
          }
      }
      return max
  }

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

• code

  func search(nums []int, target int) int {
      length := len(nums)
      if length == 0 {
          return -1
      }
      if length == 1 {
          if nums[0] != target {
              return -1
          }
          return 0
      }
      return search1(nums, 0, length-1, target)
  }
  
  func search1(nums []int, left, right, target int) int {
      if left > right {
          return -1
      }
      if left == right {
          if nums[left] == target {
              return left
          }
          return -1
      }
      mid := left + (right-left)/2
      if nums[mid] == target {
          return mid
      }
      if nums[left] < nums[mid] && nums[left] <= target && nums[mid] > target {
          return binarySearch(nums, left, mid-1, target)
      }
      if nums[right] > nums[mid] && nums[mid] < target && nums[right] >= target {
          return binarySearch(nums, mid+1, right, target)
      }
      if nums[left] > nums[mid] {
          return search1(nums, left, mid-1, target)
      }
      if nums[right] < nums[mid] {
          return search1(nums, mid+1, right, target)
      }
      return -1
  }
  
  func binarySearch(nums []int, left, right, target int) int {
      if left > right {
          return -1
      }
      mid := left + (right-left)/2
      if nums[mid] == target {
          return mid
      }
      if target < nums[mid] {
          return binarySearch(nums, left, mid-1, target)
      }
      return binarySearch(nums, mid+1, right, target)
  
  }

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

• code

  func searchRange(nums []int, target int) []int {
      length := len(nums)
      if length == 0 || length == 1 && nums[0] != target {
          return []int{-1, -1}
      }
      return searchRangeI(nums, 0, length-1, target)
  }
  
  func searchRangeI(nums []int, left, right, target int) (ret []int) {
      length := len(nums)
      if length == 0 || left > right {
          return []int{-1, -1}
      }
      if left == right {
          if nums[left] == target {
              return []int{left, left}
          }
          return []int{-1, -1}
      }
      mid := left + (right-left)/2
      if nums[mid] == target {
          lower := findLower(nums, left, mid, target)
          upper := findUpper(nums, mid, right, target)
          return []int{lower, upper}
      } else if nums[mid] < target {
          return searchRangeI(nums, mid+1, right, target)
      }
      return searchRangeI(nums, left, mid-1, target)
  }
  
  func findLower(nums []int, left, right, target int) int {
      length := len(nums)
      if length == 0 || left > right {
          return -1
      }
      if left == right {
          if nums[right] == target {
              return right
          }
          return -1
      }
      mid := left + (right-left)/2
      if nums[mid] == target {
          if mid > left && nums[mid-1] == target {
              return findLower(nums, left, mid-1, target)
          }
          return mid
      }
      return findLower(nums, mid+1, right, target)
  }
  func findUpper(nums []int, left, right, target int) int {
      length := len(nums)
      if length == 0 || left > right {
          return -1
      }
      if left == right {
          if nums[left] == target {
              return left
          }
          return -1
      }
      mid := left + (right-left)/2
      if nums[mid] == target {
          if mid < right && nums[mid+1] == target {
              return findUpper(nums, mid+1, right, target)
          }
          return mid
      }
      return findUpper(nums, left, mid-1, target)
  }

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

• code

  func searchInsert(nums []int, target int) int {
      if len(nums) == 0{
          nums = append(nums, target)
          return 0
      }
      return find(nums, 0, len(nums)-1, target)
  
  }
  
  func find(nums []int, left, right ,target int) int{
      if left == right{
          if nums[left] >= target{
              return left
          }else{
              return right+1
          }
      }
  
      mid := left + (right - left)/2
      if nums[mid] == target{
          return mid
      }
      if nums[mid] > target{
          return find(nums, left, mid, target)
      }
      return find(nums, mid+1, right, target)
  }

36. 有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

• code

  func isValidSudoku(board [][]byte) bool {
      rows := [9][9]byte{}
      squars := [9][9]byte{}
      list := [9][9]byte{}
      for i, sb := range board {
          for j := range sb {
              rows[j][i] = sb[j]
              squars[(i/3)*3+(j/3)][(i%3)*3+(j%3)] = sb[j]
              list[i][j] = sb[j]
          }
      }
      for _, row := range list {
          if hasRepeted(row) {
              return false
          }
      }
      for _, row := range rows {
          if hasRepeted(row) {
              return false
          }
      }
      for _, row := range squars {
          if hasRepeted(row) {
              return false
          }
      }
      return true
  
  }
  
  func hasRepeted(bs [9]byte) bool {
      for i := 0; i < len(bs)-1; i++ {
          for j := i + 1; j < len(bs); j++ {
              if bs[i] != '.' && bs[i] == bs[j] {
                  return true
              }
          }
      }
      return false
  }

37. 解数独

编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。
Note:
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。

解: 暴力递归

38. 报数

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1. 1
2. 11
3. 21
4. 1211
5. 111221
   1 被读作 “one 1” (“一个一”) , 即 11。
   11 被读作 “two 1s” (“两个一”）, 即 21。
   21 被读作 “one 2”, “one 1” （”一个二” , “一个一”) , 即 1211。
   给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
   注意：整数顺序将表示为一个字符串。

• code

  func countAndSay(n int) string {
      if n == 1 {
          return "1"
      }
      base := countAndSay(n - 1)
      i := 0
      count := 1
      ret := ""
      for j := 1; j < len(base); j++ {
          if base[j] == base[i] {
              count++
          } else {
              ret += fmt.Sprint(count, string(base[i]))
              i = j
              count = 1
          }
      }
      ret += fmt.Sprint(count, string(base[i]))
      return ret
  }

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

• code

  func combinationSum(candidates []int, target int) [][]int {
      sort.Ints(candidates)
      return cbs(candidates,0, target)
  }
  
  
  func cbs(nums []int,start, target int) [][]int{
      if target <= 0 || nums[start] > target{
          return nil
      }
  
      ret := [][]int{}
      if nums[start] == target{
          ret = append(ret, []int{nums[start]})
          return ret
      }
      rs := cbs(nums, start, target-nums[start])
      for _,r1:=range rs{
          nr := make([]int, len(r1)+1)
          nr[0] = nums[start]
          copy(nr[1:], r1)
          ret = append(ret, nr)
      }
      if start < len(nums)-1{
          ret = append(ret, cbs(nums, start+1, target)...)
      }
      return ret
  }

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

• code

  func combinationSum2(candidates []int, target int) [][]int {
      sort.Ints(candidates)
      return DFS(candidates, 0, target, []int{}, [][]int{})
  }
  
  func DFS(candidates []int, start int, target int, solution []int, results [][]int) (rets [][]int) {
      rets = results
      if target < 0 {
          return
      }
      if target == 0 {
          rets = append(rets, solution)
          return
      }
      for i := start; i < len(candidates); i++ {
          if i > start && candidates[i] == candidates[i-1] {
              continue
          }
          candidate := candidates[i]
          repliaSolution := make([]int, len(solution))
          copy(repliaSolution, solution)
          repliaSolution = append(repliaSolution, candidate)
          rets = DFS(candidates, i+1, target-candidate, repliaSolution, rets)
          repliaSolution = repliaSolution[:len(repliaSolution)-1]
      }
      return
  }