难度中等653收藏分享切换为英文关闭提醒反馈
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
解法
- 就按照题意逆时针遍历
- 注意最后一次遍历的情况处理
rust
impl Solution {
pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
let mut res = Vec::new();
if matrix.len()==0{
return res;
}
let rows = matrix.len();
let cols = matrix[0].len();
let iter_num = std::cmp::min(rows, cols)/2; //迭代次数 如果是奇数的话 最后一次就是一个行或列 单独考虑
for iter in 0..iter_num{
//上面遍历
for col_id in iter..(cols-iter-1){
res.push(matrix[iter][col_id]);
}
//右边遍历
for row_id in iter..(rows-iter-1){
res.push(matrix[row_id][cols-iter-1]);
}
//下方遍历
for col_id in (iter+1..cols-iter).rev(){
res.push(matrix[rows-iter-1][col_id]);
}
//左边遍历
for row_id in (iter+1..rows-iter).rev(){
res.push(matrix[row_id][iter]);
}
}
//考虑剩下单行的情况
if rows <=cols && (rows&1>0){
for col_id in iter_num..cols-iter_num{
res.push(matrix[iter_num][col_id]);
}
}
//考虑剩下单列的情况
if cols < rows && (cols&1>0){
for row_id in iter_num..rows-iter_num{
res.push(matrix[row_id][iter_num]);
}
}
res
}
}
go
func spiralOrder(matrix [][]int) []int {
row := len(matrix)
if row == 0 {
return nil
}
if row == 1 {
return matrix[0]
}
col := len(matrix[0])
nums := make([]int, row*col)
if col == 1 {
for i := 0; i < row; i++ {
nums[i] = matrix[i][0]
}
return nums
}
nRoundEven := false
nRound := row
if nRound > col {
nRound = col
}
if nRound%2 == 0 {
nRoundEven = true
}
nRound = (nRound + 1) / 2
id := 0
// rowEven := false
// if row%2 == 0 {
// rowEven = true
// }
// colEven := false
// if col%2 == 0 {
// colEven = true
// }
for i := 0; i < nRound; i++ {
// fmt.Println(i, nRound, row, col)
if (nRoundEven) || (i < nRound-1) {
for j := i; j < col-i-1; j++ {
nums[id] = matrix[i][j]
id++
}
// fmt.Println(nums)
for j := i; j < row-i-1; j++ {
nums[id] = matrix[j][col-i-1]
// fmt.Println(nums)
id++
}
// fmt.Println(nums)
for j := col - i - 1; j > i; j-- {
nums[id] = matrix[row-i-1][j]
id++
}
// fmt.Println(nums)
for j := row - i - 1; j > i; j-- {
nums[id] = matrix[j][i]
id++
}
// fmt.Println(nums)
continue
}
if (nRoundEven == false) && (row <= col) {
for j := i; j < col-i; j++ {
nums[id] = matrix[i][j]
id++
}
continue
}
// fmt.Println(nums, i, row)
if (nRoundEven == false) && (row > col) {
for j := i; j < row-i; j++ {
nums[id] = matrix[j][col-i-1]
id++
}
}
// fmt.Println(nums)
}
return nums
}
func spiralOrder(matrix [][]int) []int {
n, m := len(matrix), len(matrix[0])
mark := make([][]bool, n*m)
for i := 0; i < n; i++ {
mark[i] = make([]bool, m)
}
result := make([]int, 0, n*m)
x, y := 0, 0
for len(result) < n*m {
for y < m && !mark[x][y] {
mark[x][y] = true
result = append(result, matrix[x][y])
y++
}
y--
x++
for x < n && !mark[x][y] {
mark[x][y] = true
result = append(result, matrix[x][y])
x++
}
x--
y--
for y >= 0 && !mark[x][y] {
mark[x][y] = true
result = append(result, matrix[x][y])
y--
}
y++
x--
for x >= 0 && !mark[x][y] {
mark[x][y] = true
result = append(result, matrix[x][y])
x--
}
x++
y++
}
return result
}
func generateMatrix(n int) [][]int {
matrix := make([][]int, n)
for i := 0; i < n; i++ {
matrix[i] = make([]int, n)
}
i, j, num := 0, 0, 1
for num <= n*n {
for j < n && matrix[i][j] == 0{
matrix[i][j] = num
j++
num++
}
j--
i++
for i < n && matrix[i][j] == 0 {
matrix[i][j] = num
i++
num++
}
i--
j--
for j >= 0 && matrix[i][j] == 0 {
matrix[i][j] = num
j--
num++
}
j++
i--
for i >= 0 && matrix[i][j] == 0 {
matrix[i][j] = num
i--
num++
}
i++
j++
}
return matrix
}
// 最近打算用 c++ 刷一阵子了。。。
class Solution {
public:
bool find132pattern(vector<int>& nums) {
multiset<int> stats;
int minVal = nums[0], n = nums.size();
if(n < 3) {
return 0;
}
for(int i = 1; i < n; i++) {
stats.insert(nums[i]);
}
multiset<int>::iterator it;
for(int i = 1; i < n - 1; i++) {
it = stats.find(nums[i]);
stats.erase(it);
// 按 val 删除会删除所有值相同的元素
//stats.erase(nums[i]);
it = stats.upper_bound(minVal);
if (it != stats.end() && *it < nums[i]) {
return true;
}
minVal = min(minVal, nums[i]);
}
return false;
}
};
func calOne(start, end int) int {
ans := start
for i:=0;i<3 && start-1-i>end;i++ {
switch i {
case 0:
ans = ans * (start-1-i)
case 1:
ans = ans / (start-1-i)
case 2:
ans = ans - (start-1-i) // 最后整体减了，所以这里要用- 负负得正。
}
}
return ans
}
func max(a, b int) int {
if a>b{return a}
return b
}
/*
总是* / +-可以发现 每4项* /+可以先计算，最后再做减法，
*/
func clumsy(N int) int {
marr := []int{}
for i:=N;i>=1; i-=4 {
marr = append(marr, calOne(i, max(i-4, 0)))
}
sum :=marr[0]
for i:=1;i<len(marr);i++ {
sum -= marr[i]
}
// 第一项多减了，这里要加回来。
if N>=4 {
sum += 2*(N-3)
}
return sum
}
package main
import (
"fmt"
"math"
)
var bitNum = [][2]int{} // 保存2^n, bitNum[i][0] = 2^i, bitNum[i][1] = -2^i
var ind = []int{} // 构造出32，31，。。。0序列
/*
利用二进制从高到低判断每一位，并求出一半与余
*/
func getHalf(a int) (half int, left bool) {
if a == 0 {
return 0, false
}
total := 0
half = 0
left = false
if a < 0 {
goto Neg
}
for i := 0; i < 33; i++ {
j := ind[i]
if j == 0 {
left = total+1 == a
break
}
half = half + half
if total+bitNum[j][0] <= a {
total = total + bitNum[j][0]
half += 1
}
}
return
Neg:
for i := 0; i < 33; i++ {
j := ind[i]
if j == 0 {
left = total+bitNum[0][1] == a
break
}
if total+bitNum[j][1] >= a {
total += bitNum[j][1]
half += bitNum[ind[i+1]][1]
}
}
return
}
// 快速幂，利用溢出求得负数
func fastPow(a, b int32) int32 {
sum := int32(0)
for b != 0 {
half, left := getHalf(int(b))
if left {
sum += a
}
b = int32(half)
a = a + a
}
return sum
}
// 获取相反负数
func getNegNum(a int) int {
if a == 0 {
return 0
}
if a == math.MinInt32 {
return math.MaxInt32 + 1
}
if a > 0 {// 当 n>0时 ， b = n+ n*(math.MaxInt32+math.MaxInt32) = -n
return int(int32(a) + fastPow(int32(math.MaxInt32), int32(a)) + fastPow(int32(math.MaxInt32), int32(a)))
} else {
return int(fastPow(1, int32(a))) // 小于0时 1^-a
}
}
type Operations struct {
}
func Constructor() Operations {
// 生成二进制
bitNum = [][2]int{[2]int{1, -1}}
ind = []int{0}
for i := 1; i <= 32; i++ {
newBit := [2]int{bitNum[i-1][0] + bitNum[i-1][0], bitNum[i-1][1] + bitNum[i-1][1]}
bitNum = append(bitNum, newBit)
//fmt.Println(i, newBit)
ind = append([]int{ind[0] + 1}, ind...)
}
//fmt.Println(ind)
return Operations{}
}
func (this *Operations) Minus(a int, b int) int {
return a + getNegNum(b) // a-b = a+(-b)
}
func (this *Operations) Multiply(a int, b int) int {
// 保证b是正数, 这样符号就由a决定
if b<0 { return this.Multiply(getNegNum(a), getNegNum(b))}
sum := int(0)
for b != 0 {
half, left := getHalf(int(b))
if left {
sum += a
}
b = half
a = a + a
}
return sum
}
func (this *Operations) Divide(a int, b int) int {
if a==0 {return 0}
if b<0 {return this.Divide(getNegNum(a), getNegNum(b))}
if a<0 {return getNegNum(this.Divide(getNegNum(a), b))}
/*
利用二进制求解
*/
res := 0
for i := 0; i < 33; i++ {
j := ind[i]
if m :=this.Multiply(bitNum[j][0],b);m <= a {
res = res + bitNum[j][0]
a = this.Minus(a, m)
}
}
return res
}
/**
* Your Operations object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Minus(a,b);
* param_2 := obj.Multiply(a,b);
* param_3 := obj.Divide(a,b);
*/
func main() {
op := Constructor()
fmt.Println(op.Minus(math.MaxInt32, math.MinInt32))
fmt.Println(op.Multiply(0, 0))
fmt.Println(op.Multiply(10, 10))
fmt.Println(op.Multiply(10, -10))
fmt.Println(op.Multiply(-10, -10))
fmt.Println(op.Multiply(-10, 10))
fmt.Println(op.Multiply(math.MaxInt32, -10))
fmt.Println(op.Multiply(math.MinInt32, -10))
fmt.Println(op.Divide(1, 2))
fmt.Println(op.Divide(2, 2))
fmt.Println(op.Divide(9, 2))
fmt.Println(op.Divide(-1, 2))
fmt.Println(op.Divide(-11, 2))
fmt.Println(op.Divide(2, -2))
fmt.Println(op.Divide(-9, -2))
return
for i := -10000; i < 10000; i++ {
fmt.Print(i, i&1 == 1, " ")
fmt.Println(getHalf(i))
}
fmt.Println(math.MaxInt32 + 1)
fmt.Println(getHalf(math.MaxInt32))
fmt.Println(getNegNum(math.MinInt32))
fmt.Println(getNegNum(math.MaxInt32))
fmt.Println(getNegNum(0))
fmt.Println(getNegNum(1))
fmt.Println(getNegNum(2))
fmt.Println(getNegNum(12395034))
fmt.Println(getNegNum(-12395034))
fmt.Println(getNegNum(-95034))
fmt.Println(getNegNum(-34))
fmt.Println(getNegNum(-1))
fmt.Println(getNegNum(-2))
}
// 当 n>0时 ， b = n+ n*(math.MaxInt32+math.MaxInt32) = -n