返回总目录

日刷leetcode–简单版

566. 重塑矩阵

image-20210122002325449

解题思路

创建固定的行，依次循环原数组，同时放入结果数组中，每一行存满后，就添加新的列继续存储

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func matrixReshape(nums [][]int, r int, c int) [][]int {
   x, y := len(nums), len(nums[0])
   if r*c != x*y {
      return nums
   }
   i, j := 0, 0
   arr := make([][]int, r)
   for _, row := range nums {
      for _, v := range row {
         arr[i] = append(arr[i], v)
         j++
         if j == c {
            j = 0
            i++
         }
      }
   }
   return arr
}

解题思路

将二维数组通过列行遍历改变为一维数组，我们会惊讶的发现原数组的下标nums[i][j]变成了一维数组newNums[n*i+j],其中n为原二维数组的列数。二维数组的下标i和j可以分别表示了在第i行，第j列，由此我们可将一维数组newNums[i]变回二维数组nums[i/c][i%c],其中c为二维数组的列数。

1
2
3
4
5
nums := [][]int{
[]int{1, 2, 3},
[]int{4, 5, 6},
}
newNums := []int{1,2,3,4,5,6}

值5在两个数组中分别表示为nums[1][1]和nums[4]，1(i)*3(n)+1(j) = 4(i)，[1(4/3)][1(4%3)]符合上述推导，故二维数组的转换都可基于一维数组实现

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func matrixReshape2(nums [][]int, r int, c int) [][]int {
	x, y := len(nums), len(nums[0])
	if r*c != x*y {
		return nums
	}
	newNums := make([][]int, r)
	for i := 0; i < r; i++ {
		newNums[i] = make([]int, c)
	}
	for i := 0; i < r*c; i++ {
		// 两个二维数组都是基于同一个一维数组变化而来,他们在一维数组中的值是相等的
		newNums[i/c][i%c] = nums[i/y][i%y]
	}
	return newNums
}

605. 种花问题

605.种花问题

解题思路

数组由0和1组成，循环一次数组，并分别处理即可

  • 当前元素为1表示有花，根据规则，下一次有花必定是两格后，直接跳到i+2处即可
  • 当前元素为0表示没有话，因为遇到花就会跳两个，所以前一个位置必定不是花，我们只需要判断下一格是否为1即可，不为1或者当前格子已经是最后一格，即可种，执行n--，然后此格变成了1，继续往后跳两格；如果是1，则不可种，两格后也不可种，直接跳三格即可

循环结束后查看n是否为0，为0则表示可种n朵花，返回true，反之返回false

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
func canPlaceFlowers(flowerbed []int, n int) bool {
   for i := 0; i < len(flowerbed) && n > 0; {
      if flowerbed[i] == 1 { // 当前格子已经有花,我们两格后见
         i += 2
      } else if i == len(flowerbed)-1 || flowerbed[i+1] == 0 { // 当前格子不是花,下一个格子也不是花或着当前格子已经是最后一个
         n--
         i += 2
      } else { // 当前格子不是花,但是下一格是
         i += 3
      }
   }
   return n == 0
}

628. 三个数的最大乘积

628. 三个数的最大乘积

解题思路

首先将数组排序，再根据数组内的数是正负数进行处理

  • 数组中的数全部为正数或者全部为负数时，最大乘机为最大的三个数
  • 数组中包含正数与负数，则最大乘积有可能是最大三个正数的乘积，也有可能是两个最小负数与最大正数的乘积

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
func maximumProduct(nums []int) int {
   sort.Ints(nums)
   l := len(nums)
   return max(nums[0]*nums[1]*nums[l-1], nums[l-1]*nums[l-2]*nums[l-3])
}

func max(a,b int) int {
   if a>b {
      return a
   }
   return b
}

解题思路

由方法一得知，我们所需的只是最大的3个数以及最小的两个数而已，直接循环一次找出这5个数即可，不用排序。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maximumProduct2(nums []int) int {
   min1, min2 := math.MaxInt64, math.MinInt64
   max1, max2, max3 := math.MinInt64, math.MinInt64, math.MinInt64
   for _, v := range nums {
      if v < min1 {
         min1, min2 = v, min1
      } else if v < min2 {
         min2 = v
      }

      if v > max1 {
         max1, max2, max3 = v, max1, max2
      } else if v > max2 {
         max2, max3 = v, max2
      } else if v > max3 {
         max3 = v
      }
   }
   return max(min1*min2*max1, max1*max2*max3)
}

643. 子数组最大平均数I

643

解题思路

使用窗口滑动的方式：先求出0-k的和sum，再往后依次遍历，求出最大的后除以K即可

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findMaxAverage(nums []int, k int) float64 {
   var maxSum, sum int
   for i := 0; i < k; i++ {
      sum += nums[i]
   }
   maxSum = sum
   for i := k; i < len(nums); i++ {
      sum += nums[i] - nums[i-k]
      if sum > maxSum {
         maxSum = sum
      }
   }
   return float64(maxSum) / float64(k)
}

661. 图片平滑器

image-20210123211333512

解题思路

循环遍历找到每个格子，找所有 9 个包括它自身在内的紧邻的格子，去除无用的格子，将他们的和存在当前位置中，同时记录邻居个数，最后用和除以个数即可。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func imageSmoother(M [][]int) [][]int {
   var x, y = len(M), len(M[0])
   newM := make([][]int, x)
   for i := 0; i < x; i++ {
      newM[i] = make([]int, y)
   }
   for i := 0; i < x; i++ {
      for j := 0; j < y; j++ {
         var count int
         // 寻找邻居格子
         for ii := i-1; ii <= i+1; ii++ {
            for jj := j-1; jj <= j+1; jj++ {
               if ii >=0 && ii < x && jj >=0 && jj < y { // 去除超出原数组范围的数据
                  newM[i][j] += M[ii][jj]
                  count ++
               }
            }
         }
         newM[i][j] /= count
      }
   }
   return newM
}

665. 非递减数列

665. 非递减数列

解题思路

这道题给了我们一个数组，说我们最多有1次修改某个数字的机会，
问能不能将数组变为非递减数组。题目中给的例子太少，不能覆盖所有情况，我们再来看下面三个例子：
4，2，3
-1，4，2，3
2，3，3，2，4
我们通过分析上面三个例子可以发现，当我们发现后面的数字小于前面的数字产生冲突后，
[1]有时候需要修改前面较大的数字(比如前两个例子需要修改4)，
[2]有时候却要修改后面较小的那个数字(比如前第三个例子需要修改2)，
那么有什么内在规律吗？是有的，判断当前数字(nums[i])跟再前面一个数(nums[i-2])的大小有关系，
首先如果再前面的数(nums[i-2])不存在，比如例子1，4前面没有数字了，我们直接修改前面的数字(nums[i-1])为当前的数字(nums[i])2即可。
而当再前面的数字(nums[i-2])存在，并且小于当前数(nums[i])时，比如例子2，-1小于2，我们还是需要修改前面的数字(nums[i-2])4为当前数字(nums[i])2；
如果再前面的数(nums[i-2])大于当前数(nums[i])，比如例子3，3大于2，我们需要修改当前数(nums[i])2为前面的数3(nums[i-1])。

参考：https://leetcode-cn.com/problems/non-decreasing-array/comments/59727

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func checkPossibility(nums []int) bool {
   if len(nums) == 0 {
      return true
   }
   var count int
   for i := 1; i < len(nums) && count < 2; i++ {
      if nums[i-1] <= nums[i] {
         continue
      }
      count++
      if i >= 2 && nums[i-2] > nums[i] {
         nums[i] = nums[i-1]
      } else {
         nums[i-1] = nums[i]
      }
   }
   return count <= 1
}