46. 全排列 Permutations

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]

输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]

输出：[[1]]

提示：

1 <= nums.length <= 6

-10 <= nums[i] <= 10

nums 中的所有整数互不相同

代码：回溯法

package main
import "fmt"
func permute(nums []int) [][]int {
  res := [][]int{}
  if len(nums) == 0 {
    return res
  }
  used := make([]bool, len(nums))
  var backtrack func(path []int)
  backtrack = func(path []int) {
    if len(path) == len(nums) {
      tmp := make([]int, len(path))
      copy(tmp, path)
      res = append(res, tmp)
      return
    }
    for i := 0; i < len(nums); i++ {
      if !used[i] {
        used[i] = true
        path = append(path, nums[i])
        backtrack(path)
        path = path[:len(path)-1]
        used[i] = false
      }
    }
  }
  backtrack([]int{})
  return res
}
func main() {
  fmt.Println(permute([]int{1, 2, 3}))
  fmt.Println(permute([]int{0, 1}))
  fmt.Println(permute([]int{1}))
}

输出：

[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

[[0 1] [1 0]]

[[1]]

代码2： 字典序法

package main
import (
  "fmt"
  "sort"
)
func permute(nums []int) [][]int {
  res := [][]int{}
  if len(nums) == 0 {
    return res
  }
  sort.Ints(nums)
  for {
    tmp := make([]int, len(nums))
    copy(tmp, nums)
    res = append(res, tmp)
    i, j := len(nums)-2, len(nums)-1
    for i >= 0 && nums[i] >= nums[i+1] {
      i--
    }
    if i < 0 {
      break
    }
    for nums[j] <= nums[i] {
      j--
    }
    nums[i], nums[j] = nums[j], nums[i]
    reverse(nums[i+1:])
  }
  return res
}
func reverse(nums []int) {
  for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
    nums[i], nums[j] = nums[j], nums[i]
  }
}
func main() {
  fmt.Println(permute([]int{1, 2, 3}))
  fmt.Println(permute([]int{0, 1}))
  fmt.Println(permute([]int{1}))
}

代码3： DFS

package main
import "fmt"
func permute(nums []int) [][]int {
  if len(nums) == 0 {
    return [][]int{}
  }
  used, p, res := make([]bool, len(nums)), []int{}, [][]int{}
  dfs(nums, 0, p, &res, &used)
  return res
}
func dfs(nums []int, index int, p []int, res *[][]int, used *[]bool) {
  if index == len(nums) {
    temp := make([]int, len(p))
    copy(temp, p)
    *res = append(*res, temp)
    return
  }
  for i := 0; i < len(nums); i++ {
    if !(*used)[i] {
      (*used)[i] = true
      p = append(p, nums[i])
      dfs(nums, index+1, p, res, used)
      p = p[:len(p)-1]
      (*used)[i] = false
    }
  }
  return
}
func main() {
  fmt.Println(permute([]int{1, 2, 3}))
  fmt.Println(permute([]int{0, 1}))
  fmt.Println(permute([]int{1}))
}

47. 全排列 II Permutations II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

输出：

[[1,1,2],

[1,2,1],

[2,1,1]]

示例 2：

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

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8

-10 <= nums[i] <= 10

代码：回溯法

package main
import (
  "fmt"
  "sort"
)
func permuteUnique(nums []int) [][]int {
  res := [][]int{}
  if len(nums) == 0 {
    return res
  }
  sort.Ints(nums)
  used := make([]bool, len(nums))
  var backtrack func(path []int)
  backtrack = func(path []int) {
    if len(path) == len(nums) {
      tmp := make([]int, len(path))
      copy(tmp, path)
      res = append(res, tmp)
      return
    }
    for i := 0; i < len(nums); i++ {
      if used[i] || (i > 0 && !used[i-1] && nums[i] == nums[i-1]) {
        continue
      }
      used[i] = true
      path = append(path, nums[i])
      backtrack(path)
      path = path[:len(path)-1]
      used[i] = false
    }
  }
  backtrack([]int{})
  return res
}
func main() {
  fmt.Println(permuteUnique([]int{1, 1, 2}))
  fmt.Println(permuteUnique([]int{1, 2, 3}))
}

输出：

[[1 1 2] [1 2 1] [2 1 1]]

[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

代码2： 字典序法

package main
import (
  "fmt"
  "sort"
)
func permuteUnique(nums []int) [][]int {
    res := [][]int{}
    if len(nums) == 0 {
        return res
    }
    sort.Ints(nums)
    for {
        tmp := make([]int, len(nums))
        copy(tmp, nums)
        res = append(res, tmp)
        i, j := len(nums)-2, len(nums)-1
        for i >= 0 && nums[i] >= nums[i+1] {
            i--
        }
        if i < 0 {
            break
        }
        for nums[j] <= nums[i] {
            j--
        }
        if nums[j] == nums[i] && j > i+1 {
            continue
        }
        nums[i], nums[j] = nums[j], nums[i]
        reverse(nums[i+1:])
    }
    return res
}
func reverse(nums []int) {
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}
func main() {
  fmt.Println(permuteUnique([]int{1, 1, 2}))
  fmt.Println(permuteUnique([]int{1, 2, 3}))
}

代码3： DFS

package main
import (
  "fmt"
  "sort"
)
func permuteUnique(nums []int) [][]int {
  if len(nums) == 0 {
    return [][]int{}
  }
  used, p, res := make([]bool, len(nums)), []int{}, [][]int{}
  sort.Ints(nums)
  dfs(nums, 0, p, &res, &used)
  return res
}
func dfs(nums []int, index int, p []int, res *[][]int, used *[]bool) {
  if index == len(nums) {
    temp := make([]int, len(p))
    copy(temp, p)
    *res = append(*res, temp)
    return
  }
  for i := 0; i < len(nums); i++ {
    if !(*used)[i] {
      if i > 0 && nums[i] == nums[i-1] && !(*used)[i-1] {
        continue
      }
      (*used)[i] = true
      p = append(p, nums[i])
      dfs(nums, index+1, p, res, used)
      p = p[:len(p)-1]
      (*used)[i] = false
    }
  }
  return
}
func main() {
  fmt.Println(permuteUnique([]int{1, 1, 2}))
  fmt.Println(permuteUnique([]int{1, 2, 3}))
}

48. 旋转图像 Rotate Image

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在

原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]

输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

n == matrix.length == matrix[i].length

1 <= n <= 20

-1000 <= matrix[i][j] <= 1000

代码1：转置加翻转

先转置矩阵，然后翻转每一行即可得到顺时针旋转 90 度后的矩阵。

package main
import "fmt"
func rotate(matrix [][]int) {
  n := len(matrix)
  // 转置矩阵
  for i := 0; i < n; i++ {
    for j := i; j < n; j++ {
      matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    }
  }
  // 翻转每一行
  for i := 0; i < n; i++ {
    for j := 0; j < n/2; j++ {
      matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
    }
  }
}
func main() {
  matrix := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
  rotate(matrix)
  fmt.Println(matrix)
  matrix2 := [][]int{{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}
  rotate(matrix2)
  fmt.Println(matrix2)
}

输出：

[[7 4 1] [8 5 2] [9 6 3]]

[[15 13 2 5] [14 3 4 1] [12 6 8 9] [16 7 10 11]]

代码2： 分块翻转

将矩阵分成四个部分，并将每个部分按顺时针旋转 90 度。

package main
import "fmt"
func rotate(matrix [][]int) {
    n := len(matrix)
    // 分块翻转
    for i := 0; i < n/2; i++ {
        for j := i; j < n-i-1; j++ {
            tmp := matrix[i][j]
            matrix[i][j] = matrix[n-j-1][i]
            matrix[n-j-1][i] = matrix[n-i-1][n-j-1]
            matrix[n-i-1][n-j-1] = matrix[j][n-i-1]
            matrix[j][n-i-1] = tmp
        }
    }
}
func main() {
  matrix := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
  rotate(matrix)
  fmt.Println(matrix)
  matrix2 := [][]int{{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}
  rotate(matrix2)
  fmt.Println(matrix2)
}

代码3： 对角线变换+水平翻转

将矩阵分成四个部分，并将每个部分按顺时针旋转 90 度。

1.package main
import "fmt"
func rotate(matrix [][]int) {
  row := len(matrix)
  if row <= 0 {
    return
  }
  column := len(matrix[0])
  // 对⻆线变换
  for i := 0; i < row; i++ {
    for j := i + 1; j < column; j++ {
      tmp := matrix[i][j]
      matrix[i][j] = matrix[j][i]
      matrix[j][i] = tmp
    }
  }
  // 竖直轴对称翻转
  halfColumn := column / 2
  for i := 0; i < row; i++ {
    for j := 0; j < halfColumn; j++ {
      tmp := matrix[i][j]
      matrix[i][j] = matrix[i][column-j-1]
      matrix[i][column-j-1] = tmp
    }
  }
}
func main() {
  matrix := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
  rotate(matrix)
  fmt.Println(matrix)
  matrix2 := [][]int{{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}
  rotate(matrix2)
  fmt.Println(matrix2)
}

翻转+旋转原理C代码

/*
* clockwise rotate 顺时针旋转
* first reverse up to down, then swap the symmetry
* 1 2 3      7 8 9      7 4 1
* 4 5 6 => 4 5 6 => 8 5 2
* 7 8 9      1 2 3      9 6 3
*/
void rotate(vector<vector<int> > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}
/*
* anticlockwise rotate 逆时针旋转
* first reverse left to right, then swap the symmetry
* 1 2 3      3 2 1      3 6 9
* 4 5 6 => 6 5 4 => 2 5 8
* 7 8 9      9 8 7      1 4 7
*/
void anti_rotate(vector<vector<int> > &matrix) {
    for (auto vi : matrix) reverse(vi.begin(), vi.end());
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = i + 1; j < matrix[i].size(); ++j)
                swap(matrix[i][j], matrix[j][i]);
        }
}