每日一题
March
896. 单调数列
题目描述
如果数组是单调递增或单调递减的，那么它是单调的。
如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。
当给定的数组 A 是单调数组时返回 true，否则返回 false。
示例
示例 1：
输入：[1,2,2,3]
输出：true
示例 2：
输入：[6,5,4,4]
输出：true
示例 3：
输入：[1,3,2]
输出：false
示例 4：
输入：[1,2,4,5]
输出：true
示例 5：
输入：[1,1,1]
输出：true
分析
简单题，循环暴力破解即可
- 循环遍历数组，用前一个和后一个做比较
- 在比较的时候，要注意第一次比较的结果
- 如果第一次比较是小于，那么后面不能出现大于
- 如果第一次比较是大于，那么后面不能出现小于
- 如果第一次比较是等于，那么继续比较下一个
- 时间复杂度O(n)
代码
func isMonotonic(A []int) bool {
flag := 0
// flag 初始等于0，表示还未存在大于小于关系
// flag 为1 表示递增；flag 为2，表示递减
var val1, val2 int
for index := 0; index < len(A)-1; index++ {
val1 = A[index] // 前一个变量
val2 = A[index+1] // 后一个变量
// 相等则继续判断，无论递增递减都满足
if val1 == val2 {
continue
}
// 小于的判定
if val1 < val2 {
// 如果flag == 2, 说明之前是递减序列，返回false
if flag == 2 {
return false
// 如果flag == 0，第一次出现小于，赋值1
} else if flag == 0 {
flag = 1
}
}
// 大于的判定
if val1 > val2 {
// 如果flag == 1，说明之前是递增序列，返回false
if flag == 1 {
return false
// 如果flag == 0，第一次出现大于，赋值2
} else if flag == 0 {
flag = 2
}
}
}
// 全部遍历结束，到这步说明都满足
return true
}
303. 区域和检索 - 数组不可变
题目描述
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
示例
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
分析
1. 暴力破解
题目较为简单，所以暴力破解即可。
构建NumArray的时间复杂度O(n)。这一条不可避免，所以不作算法比较的考虑
构建完成后，遍历i--->j，求和，时间复杂度O(n)。
代码
type NumArray struct {
nums []int
}
func Constructor(nums []int) NumArray {
return NumArray{nums: nums}
}
func (this *NumArray) SumRange(i int, j int) int {
ret := 0
for index := i; index <= j; index++ {
ret += this.nums[index]
}
return ret
}
2. 构建数组进行巧妙的解决
在NumArray构建的时候同时给其进行运算，也就是说构建出来的数组是这样的。
如此，构建出来的ArrayNum存储的Num[i]就是前i个元素的和，欲求解i--->j的元素和，就等于ArrayNum[j]-ArrayNum[i-1]; 如果i<=0，那么就直接等于ArrayNum[j]
代码
type NumArray struct {
nums []int
}
func Constructor(nums []int) NumArray {
for i := 1; i < len(nums); i++ {
nums[i] += nums[i-1]
}
return NumArray{nums}
}
func (this *NumArray) SumRange(i int, j int) int {
if i > 0 {
return this.nums[j] - this.nums[i-1]
}
return this.nums[j]
}
304. 二维区域和检索 - 矩阵不可变
题目描述
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为
(row1, col1)，右下角为(row2, col2)。
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
示例
给定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
提示：
- 你可以假设矩阵不可变。
- 会多次调用
sumRegion方法。- 你可以假设
row1 ≤ row2且col1 ≤ col2。
分析
与303方式类似，可以暴力破解，也可用求和构建数组的方式，具体如下：
代码
type NumMatrix struct {
NumMatrix [][]int
}
func Constructor(matrix [][]int) NumMatrix {
row := len(matrix)
if row == 0 {
return NumMatrix{matrix}
}
col := len(matrix[0])
for i := 1; i < col; i++ {
matrix[0][i] += matrix[0][i-1]
}
for i := 1; i < row; i++ {
matrix[i][0] += matrix[i-1][0]
}
for i := 1; i < row; i++ {
for j := 1; j < col; j++ {
matrix[i][j] = matrix[i][j] + matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1]
}
}
return NumMatrix{
matrix,
}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
if row1 > 0 && col1 > 0 {
return this.NumMatrix[row2][col2] - this.NumMatrix[row1-1][col2] - this.NumMatrix[row2][col1-1] + this.NumMatrix[row1-1][col1-1]
}
if row1 ==0 && col1 == 0 {
return this.NumMatrix[row2][col2]
}
if row1 == 0 {
return this.NumMatrix[row2][col2] - this.NumMatrix[row2][col1-1]
}
return this.NumMatrix[row2][col2] - this.NumMatrix[row1-1][col2]
}