发表更新LeetCode2 分钟读完 (大约359个字)

37. 解数独--题解

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

img

1
2
3
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

思路

  1. 循环尝试每一个数字，如果不行就直接回溯
  2. 如果行就尝试下一个数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

func solveSudoku(arr [][]byte) bool {
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if arr[i][j] == '.' {
				for k := 1; k < 10; k++ {
          //证书转字符对应的整数
					arr[i][j] = byte(k + 48)
					if isValide(arr, i, j) && solveSudoku(arr) {
						return true
					}
                    // 这里进行回溯
					arr[i][j] = '.'
				}
				return false
			}
		}
	}
	return true
}

func isValide(arr [][]byte, x, y int) bool {
	for i := 0; i < 9; i++ {
		if i != x && arr[i][y] == arr[x][y] {
			return false
		}

	}
	for j := 0; j < 9; j++ {
		if j != y && arr[x][j] == arr[x][y] {
			return false
		}
	}
	for i := 3 * (x / 3); i < 3*(x/3+1); i++ {
		for j := 3 * (y / 3); j < 3*(y/3+1); j++ {
			if (i != x || j != y) && arr[i][j] == arr[x][y] {
				return false
			}
		}

	}
	return true
}

发表更新LeetCode3 分钟读完 (大约455个字)

1839. 所有元音按顺序排布的最长子字符串--题解

1839. 所有元音按顺序排布的最长子字符串

当一个字符串满足如下条件时，我们称它是 美丽的 ：

  • 所有 5 个英文元音字母（'a' ，'e' ，'i' ，'o' ，'u'）都必须 至少 出现一次。
  • 这些元音字母的顺序都必须按照 字典序 升序排布（也就是说所有的 'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推）

比方说，字符串 "aeiou" 和 "aaaaaaeiiiioou" 都是 美丽的 ，但是 "uaeio" ，"aeoiu" 和 "aaaeeeooo" 不是美丽的 。

给你一个只包含英文元音字母的字符串 word ，请你返回 word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串，请返回 0 。

子字符串 是字符串中一个连续的字符序列。

示例 1：

1
2
3
输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出：13
解释：最长子字符串是 "aaaaeiiiiouuu" ，长度为 13 。

示例 2：

1
2
3
输入：word = "aeeeiiiioooauuuaeiou"
输出：5
解释：最长子字符串是 "aeiou" ，长度为 5 。

示例 3：

1
2
3
输入：word = "a"
输出：0
解释：没有美丽子字符串，所以返回 0 。

提示：

  • 1 <= word.length <= 5 * 105
  • word 只包含字符 'a'，'e'，'i'，'o' 和 'u' 。

解答思路

  1. 如果 word[i]>=word[i-1] 代表有效的排序
  2. 如果 word[i]>word[i] 代表需要切换到下一个字符比较
  3. 如果都不满足，则需要重置类型和长度
  4. 只有完全匹配字符 才计算长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestBeautifulSubstring(word string) int {
	t, m, max := 1, 1, 0
	for i := 1; i < len(word); i++ {
		if word[i] >= word[i-1] {
			m++
		}
		if word[i] > word[i-1] {
			t++
		}
		if word[i] < word[i-1] {
			t = 1
			m = 1
		}
		if t == 5 {
			if m > max {
				max = m
			}

		} //更新最大字符串

	}
	return max
}
发表更新LeetCode3 分钟读完 (大约450个字)

1838. 最高频元素的频数--题解

1838. 最高频元素的频数

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

示例 1：

1
2
3
4
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。

示例 2：

1
2
3
4
5
6
输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。

示例 3：

1
2
输入：nums = [3,9,6], k = 2
输出：1

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

题解

总体思路采用滑动窗口的方式：

  1. 计算窗口内的差值，如果转变成最后一个值的变化数量小于 k 时，直接向后移动窗口
  2. 如果窗口的值大于 K 时，移动左侧指针，计算出最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxFrequency(nums []int, k int) int {
	sort.Ints(nums)
	start,sum := 0,0
	ans := 1
	for i := 1; i < len(nums); i++ {
         //计算差值
         //1,2,5  (2-1)*1+(5-2)*2=7.
         //此处需要多想一下
		sum += (nums[i] - nums[i-1]) * (i - start)
		for sum > k {
			sum -= nums[i] - nums[start]
			start++

		}
		if i-start+1 > ans {
			ans = i - start + 1
		}

	}
	return ans

}
发表更新LeetCode3 分钟读完 (大约439个字)

36. 有效的数独--题解

36. 有效的数独

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。

示例 1：

img

1
2
3
4
5
6
7
8
9
10
11
输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'

题解

思路：

  1. 使用一个维度相同的二位数组，把当前数独中的值映射到新数组中
  2. 如果数组的值为 1 ，代表是重复，否则是个新值
  3. index_box 代表是同一个 3*3 的单元内都是一个索引
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func isValidSudoku(board [][]byte) bool {
	var row,col,sbox [9][9]int
	for i := 0 ; i < 9; i++ {
		for j := 0 ; j < 9; j++ {
			if board[i][j] != '.' {
				//代表当前的索引
				num := board[i][j]-'1'
				index_box := (i/3)*3+j/3
				if row[i][num] == 1 {
					return false
				}else{
					row[i][num] = 1
				}
				if col[j][num] == 1 {
					return false
				}else{
					col[j][num] = 1
				}
				if sbox[index_box][num] == 1 {
					return false
				}else {
					sbox[index_box][num] = 1
				}
			}
		}
	}
	return true
}

发表更新LeetCode2 分钟读完 (大约319个字)

34. 在排序数组中查找元素的第一个和最后一个位置--题解

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

1
2
输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
  //找到头
	start := findFirst(nums, target)
	if start == -1 {
		return []int{-1, -1}
	}
  //找到尾
	end := findLast(nums, target)
	return []int{start, end}
}

func findFirst(nums []int, target int) int {
	start, end := 0, len(nums)-1
	for start < end {
		mid := (start + end) / 2
		if nums[mid] > target {
			end = mid - 1
		} else if nums[mid] == target {
			end = mid
		} else {
			start = mid + 1
		}
	}
  //此处防止数组第一个数是 target ，所以校验下是否相等
	if nums[start] == target {
		return start
	}
	return -1
}

func findLast(nums []int, target int) int {
	start, end := 0, len(nums)-1
	for start < end {
    //此处注意,为了防止 start=mid<end 导致死循环的问题
		mid := (start + end + 1) / 2
		if nums[mid] > target {
			end = mid - 1
		} else if nums[mid] == target {
			start = mid
		} else {
			start = mid + 1
		}
	}
	return end
}

发表更新LeetCode2 分钟读完 (大约343个字)

3. 无重复字符的最长子串--题解

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

1
2
输入: s = ""
输出: 0

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

题解

思路：

  1. 把已经过滤的字符放入 map，key 为当前字符，value 是当前索引
  2. 如果当前 map 中存在字符，说明当前是一个重复的字符
    1. 计算当前已经走过的长度和最长长度比
    2. 计算长度方法是 i - start + 1
  3. v>=start+1 说明有重复，但当前索引在 start 后面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func lengthOfLongestSubstring(s string) int {
    start := 0
	m := make(map[byte]int)
	max := 0
	for i, ch := range []byte(s) {
		if v, hasKey := m[ch]; hasKey && v >= start {
			start = v + 1
		}
		if i-start+1 > max {
			max = i - start + 1
		}
		m[ch] = i
	}
	return max
}
关注我

归档

标签

.Net4
DDD2
DOS1
Docker1
GO1
Guava2
IO4
JVM7
Java52
Kafka4
Linux8
MySQL11
Netty2
Redis7
Spring6
SpringMVC1
Vue1
bash1
docker1
elasticsearch7
github2
go1
jekyll4
js4
linux1
python12
sublime2
tensorflow13
win101
原理12
多线程2
插件1
数据结构1
杂货铺8
架构5
比赛错题2
消息中间件4
爬虫2
算法2
算法-回溯法1
算法-数组4
算法-滑动窗口1
设计模式5

最新文章

分类

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×