发表更新数据结构与算法 / LeetCode75学习计划23 分钟读完 (大约3393个字)

LeetCode75学习计划-数组/字符串

感觉自己的算法太过于薄弱了，正好在 LeetCode 上发现了 LeetCode 75 学习计划，准备画一些时间把这些题目看一下，记录一下解题思路。

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为数组/字符串。

交替合并字符串

题目标签：

- 双指针
- 字符串

题目难度： Easy

题目描述：

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

解题思路： 循环交替合并即可

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func MergeAlternately(word1 string, word2 string) string {
  // 取两个字符串的长度
  n := len(word1)
  m := len(word2)
  // 结果
  res := make([]byte, 0, n+m)
  // 循环交替取字符
  for i := 0; i < n || i < m; i++ {
    // 按照题目要求，从word1开始
    if i < n {
      res = append(res, word1[i])
    }
    if i < m {
      res = append(res, word2[i])
    }
  }
  // 返回结果的字符串
  return string(res)
}

字符串的最大公因子

题目标签：

  • 数学
  • 字符串

题目难度： Easy

题目描述：

对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次） 时，我们才认定 “t 能除尽 s”。

给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

示例：

输入：str1 = “ABCABC”, str2 = “ABC”
输出：”ABC”

解题思路：

  • 公因子肯定是字符串的一个前缀子串
  • 从大到小求公约数，然后判断该字符串是否是公因子

代码实现：

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
func gcdOfString(str1, str2 string) string {
  n := len(str1)
  m := len(str2)
  minLength := min(n, m)
  // 求最长的x，所以从大往小循环。这里的i是x的长度
  for i := minLength; i > 0; i-- {
    // 如果i同时被n和m整除，就是一个公约数
    if n%i == 0 && m%i == 0 {
      // 字符串的公因子肯定是字符串的一个前缀，所以从头开始到i-1的位置判断是不是公因子即可
      // 根据n、m和i的数值，判断str1和str2分别是循环了几次公因子
      rangeN := n / i
      rangeM := m / i
      // 将公因子按循环次数拼接成字符串与原始内容比对，判断是不是公因子
      if repeat(str1[:i], rangeN) == str1 && repeat(str1[:i], rangeM) == str2 {
        return str1[:i]
      }
    }
  }
  return ""
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}
// 把一个字符串重复n次后返回
func repeat(str string, n int) string {
  res := ""
  for i := 0; i < n; i++ {
    res += str
  }
  return res
}

拥有最多糖果的孩子

题目标签：

  • 数组

题目难度： Easy

题目描述：

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

解题思路：

  • 先求出数组中的最大值，即拥有糖果最多的孩子的糖果数 X
  • 循环数组，对每一个元素加上额外的糖果数，判断是否不小于 X

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func kidsWithCandies(candies []int, extraCandies int) []bool {
  // 孩子的数量
  n := len(candies)
  // 求拥有最多糖果的孩子的糖果数量
  maxCandies := 0
  for i := 0; i < n; i++ {
    maxCandies = max(maxCandies, candies[i])
  }
  // 存储结果
  res := make([]bool, n)
  for i := 0; i < n; i++ {
    res[i] = candies[i]+extraCandies >= maxCandies
  }
  return res
}

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

种花问题

题目标签：

  • 数组
  • 贪心

题目难度： Easy

题目描述：

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

解题思路：

  • 当花坛可种花的位置大于等于 n，则可以实现
  • 假设 i 与 j 位置已经种了花，那么[i+2, j-2] 区域是可以种花的。
  • [i+2, j-2] 之间的位置数量为 j - i - 3，我们假定其为 m， 假设 m 是奇数，可以种植的位置数为 m+1 / 2，假设是偶数也可以使用该公式，因为偶数 +1 并不会影响结果。

代码实现：

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
func canPlaceFlowers(flowerbed []int, n int) bool {
  // 可种植的数量
  count := 0
  m := len(flowerbed)
  prev := -1
  for i := 0; i < m; i++ {
    // 当前位置种花了，判断当前位置与上一个种花的位置中间可以种几棵花
    if flowerbed[i] == 1 {
      if prev < 0 {
        // 如果前边都没有花，可以种植花的位置为[0, i-2],其位置长度为i-1， 可种植花的数量为i-1+1 / 2,即 i/2
        count += i / 2
      } else {
        // prev与i的位置有花，其相邻位置不能有，结果为 (i - prev - 3 + 1) / 2
        count += (i - prev - 2) / 2
      }
      // 如果已经满足了则中断程序
      if count >= n {
        return true
      }
      prev = i
    }
  }
  if prev < 0 {
    // 按照公式，m个位置则结果为 m+1 / 2
    count += (m + 1) / 2
  } else {
    // prev位置有花，后边都是空位，所以[prev+2, m-1]都是可以种植的，空位数量为m-1-prev-1, 结果就为m-prev-1 / 2
    count += (m - prev - 1) / 2
  }
  return count >= n
}

反转字符串中的元音字母

题目标签：

  • 双指针
  • 字符串

题目难度： Easy

题目描述：

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

解题思路：

  • 双指针查找元音、交换位置，有点类似于快排找中值的操作

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func ReverseVowels(s string) string {
	t := []byte(s)
	n := len(s)
	// 双指针
	i := 0
	j := n - 1
	for i < j {
		// 首指针不是元音则++
		for i < n && !strings.Contains("aeiouAEIOU", string(t[i])) {
			i++
		}
		// 尾指针不是元音则--
		for j > 0 && !strings.Contains("aeiouAEIOU", string(t[j])) {
			j--
		}
		// 交换位置
		if i < j {
			t[i], t[j] = t[j], t[i]
			i++
			j--
		}
	}
	return string(t)
}

反转字符串中的单词

题目标签：

  • 双指针
  • 字符串

题目难度： Medium

题目描述：

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

解题思路：

  • 字符串切割 -> 倒序 -> 合并为字符串

代码实现：

1
2
3
4
5
6
7
8
9
10
11
func reverseWords(s string) string {
    // 依据空格进行分割
	slice := strings.Fields(s)
	res := make([]string, len(slice))
	for i := range slice {
		// 循环倒序将元素加到结果上
		res[i] = slice[len(slice)-1-i]
	}
	// 以空格分割合并为字符串
	return strings.Join(res, " ")
}

除自身以外数组的乘积

题目标签：

  • 数组
  • 前缀和

题目难度： Medium

题目描述：

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

解题思路：

  • 分别计算每个元素左右两侧的乘积，然后相乘就是要求的值

代码实现：

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
func productExceptSelf(nums []int) []int {
    n := len(nums)
    // 左右两侧的乘积列表
    L := make([]int, n)
    R := make([]int, n)
    // 结果
    res := make([]int, n)
    // 左侧的乘积列表，下标0左侧没元素了，所以设置L[0]为1
    L[0] = 1
    for i := 1; i < n; i++ {
        // i位置的数据的左侧乘积 = i-1位置的数据的左侧乘积 * i-1位置的数据
        L[i] = L[i-1] * nums[i-1]
    }
    // 右侧的乘积列表，下标n-1右侧没元素了，所以设置L[n-1]为1
    R[n-1] = 1
    for i := n-2; i >= 0; i-- {
        // 与左侧乘积的计算思想一致
        R[i] = R[i+1] * nums[i+1]
    }
    // 计算结果
    for i := 0; i < n; i ++ {
        res[i] = L[i] * R[i]
    }
    return res
}

递增的三元子序列

题目标签：

  • 数组
  • 贪心

题目难度： Medium

题目描述：

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

解题思路：

  • 采用贪心算法，我们维护两个值 first 和 second ，始终保持 first 为最小值且 second 大于 first
  • 循环元素，如果大于 second 则找到了满足要求的结果，如果小于 second 但是大于 first 则更新 second 的值为该元素，否则更新 first 的值为该元素。
  • 贪心算法只保证了我们最后的答案是正确的，即是否有满足要求的数据，但是first, second, num三个的值并不一定是满足要求的数据的值。比如传入数据[5, 4, 3, 8, 2, 9]，我们得到的答案是 true， 然而我们的first是2， second是8, 最后返回true的时候的num是9，这几个元素并不是我们的结果数据。

代码实现：

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
func increasingTriplet(nums []int) bool {
	n := len(nums)
	// 如果不足3个元素则中断程序返回false
	if n < 3 {
		return false
	}
	// 贪心算法
	// 保证first始终为最小值，second始终大于first
	first := nums[0]
	second := math.MaxInt32
	for i := 1; i < n; i++ {
		num := nums[i]
		// 如果num大于second，那么则找到结果了
		if num > second {
			return true
			// 如果num小于second，但是num大于first，则second更新为num，因为这样在后边找到大于second的元素的几率更高
		} else if num > first {
			second = num
			// 如果num小于first，也就是说前边的元素并没有找到满足要求的结果，将first更新为num，更大概率在后边找到满足要求的结果
		} else {
			first = num
		}
	}
	return false
}

压缩字符串

题目标签：

  • 双指针
  • 字符串

题目难度： Medium

题目描述：

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

如果这一组长度为 1 ，则将字符追加到 s 中。
否则，需要向 s 追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

解题思路：

  • 通过三指针的形式来实现
  • 循环读取 chars， 读指针 read 指向读取的元素，写指针 write 指向该写入内容的位置， 还有一个 left 指针指向当前重复字符的最左边的一个的位置。
  • 当读指针读到最后一个元素，或者读指针指向的元素与下一个元素不同了，就意味着当前的重复字符已经读取完了，读指针指向的元素就是这个字符，read - left + 1 就是这个字符出现的数量。然后我们在写指针的位置写入字符和长度，更新指针的位置即可。
  • 对于大于 10 的数字需要额外拆分。
  • 因为是读取 chars 后再写入 chars ，所以没有占用额外的内存空间。

代码实现：

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
func Compress(chars []byte) int {
  // left 与 write 开始位于0
	write := 0
	left := 0
	for read, ch := range chars {
		// 如果读指针位于最后一个元素，或者读指针指向的元素于下一个元素不一致
		if read == len(chars)-1 || ch != chars[read+1] {
			// 在写指针的位置写入字符
			chars[write] = ch
			write++
			// 记录重复字符的数量
			num := read - left + 1
			if num > 1 {
				// num >= 10 要分开存储每一位
				anchor := write
				// 先按照数字从右往左写入到chars
				for ; num > 0; num /= 10 {
					chars[write] = '0' + byte(num%10)
					write++
				}
				// 将写入的数字部分使其倒序
				s := chars[anchor:write]
				for i, n := 0, len(s); i < n/2; i++ {
					s[i], s[n-1-i] = s[n-1-i], s[i]
				}
			}
			// 更新left指针的位置
			left = read + 1
		}
	}
	// write左边的元素就是结果的内容，所以write的下标就是结果的长度
	return write
}

LeetCode75学习计划-数组/字符串

https://zhaolei-hu.github.io/2023/07/05/LeetCode75学习计划-数组-字符串/

作者

胡兆磊

发布于

2023-07-05

更新于

2023-07-06

许可协议

#
关注我

分类

最新文章

归档

标签

BFS2
CSS5
DFS2
Dart1
Database1
Decorator1
EggJs3
EggJss1
ElementUI1
EventEmitter1
Flutter1
GetX1
Gin1
Go2
HarmonyOS1
IndexedDB1
JavaScript1
Javascript13
LeetCode12
Mongodb1
Mysql1
NestJs20
NodeJs28
Promise1
Proxy2
Python1
Reflect2
Sass3
Scss3
TypeScript1
Vue10
Vue-Router1
Web Storage1
axios7
canvas1
cli1
cron表达式1
hexo1
log4js1
lunarvim1
monorepo1
mustache1
neovim1
pinia1
typescript2
yarn1
二分查找1
二叉搜索树1
二叉树1
前缀和1
前缀树1
动态规划2
双指针1
哈希表1
哈希集合1
图1
字符串1
排序算法3
数组1
文件上传1
栈1
源码1
滑动窗口1
背包问题1
装饰器1
链表1
队列1
×