leetcode-cn 2021年3月第三周 每日一题

54. 螺旋矩阵

难度中等653收藏分享切换为英文关闭提醒反馈

给你一个 mn 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

解法

  1. 就按照题意逆时针遍历
  2. 注意最后一次遍历的情况处理

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;
    }
};

1006. 笨阶乘

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
}

面试题 16.09. 运算

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