每日LeetCode力扣（26~30）

行是知之始,知是行之成。这篇文章主要讲述每日LeetCode力扣（26~30）相关的知识，希望能为你提供帮助。
26. 删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++)
print(nums[i]);

解题

fun _0026_removeDuplicates()
println("--------_0026_removeDuplicates-------")
println(removeDuplicates(intArrayOf(1, 1, 2)))
println(removeDuplicates(intArrayOf(0, 0, 1, 1, 1, 2, 2, 3, 3, 4)))

/**
* 用变量i表示当前覆盖到到位置，由于不能有重复数字，则只需要用当前数字 num 跟上一个覆盖到的
* 数字 nums[i-1] 做个比较，只要 num 大，则一定不会有重复（前提是数组必须有序）
*/
fun removeDuplicates(nums: IntArray): Int
var i = 0
for (num in nums)
if (i < 1 || num > nums[i - 1])
nums[i++] = num

return i

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++)
print(nums[i]);

解题

fun _0027_removeElement()
println("--------_0027_removeElement-------")
println(removeElement(intArrayOf(3, 2, 2, 3), 3))
println(removeElement(intArrayOf(0, 1, 2, 2, 3, 0, 4, 2), 2))

/**
* 只需要一个变量用来计数，然后遍历原数组，如果当前的值和给定值不同，就把当前值覆盖计数变量的位置，并将计数变量加1
*/
fun removeElement(nums: IntArray, k: Int): Int
var res = 0
for (i in nums.indices)
if (nums[i] != k)
nums[res++] = nums[i]

return res

28. 实现 strStr()函数

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回-1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 java的 indexOf() 定义相符。

解题

fun _0028_strStr()
println("--------_0028_strStr-------")
println(strStr("hello", "ll"))
println(strStr("hello", "o"))
println(strStr("hello", "he"))
println(strStr("aaaaa", "bba"))

/**
* 开头直接套两个 for 循环，不写终止条件，然后判断假如j到达 needle 的末尾了，此时返回i；
* 若此时 i+j 到达 haystack 的长度了，返回 -1；否则若当前对应的字符不匹配，直接跳出当前循环
*/
fun strStr(haystack: String, needle: String): Int
var i = 0
var j = 0
while (i > = 0)
while (j > = 0)
if (j == needle.length) return i
if (i + j == haystack.length) return -1
if (needle[j] != haystack[i + j]) break
j++

i++

return -1

29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231,231 ? 1]。本题中，如果除法结果溢出，则返回 231 ? 1。

解题

fun _0029_divide()
println("--------_0029_divide-------")
println(divide(10, 3))
println(divide(7, -3))

/**
* 通过递归的方法来解
* kotlin常用的7种中缀表达式
var a = 5,b = 11
and对应位都为1，则为1，如：a and b= 001 => 1
or对应位有一个是1，则为1 如：a or b= 111 => 7
xor对应位值相同，则结果为0，否则为1 如：a xor b= 110 => 6
inv对应位取相反的值，如： a.inv() => 1010 => 1001 => 1110 => -110 => -6
shl按位左移指定的位数，相当于乘以2的N次方。移掉的省略，右边缺失的位，用0补齐
shr按位右移指定的位数，相当于除以2的N次方，移掉的省略，左边缺失的位，如果是正数则补0，若为负数，可能补0或补1，这取决于所用的计算机系统
ushr 按位右移指定的位数，移掉的省略，左边缺失的位，用0补齐
*/
fun divide(dividend: Int, divisor: Int): Int
val m = abs(dividend)
val n = abs(divisor)
var res = 0
if (m < n) return 0
var t = n
var p = 1
while (m > (t shl 1))
t = t shl 1
p = p shl 1

res += p + divide(m - t, n)
if ((dividend < 0) xor (divisor < 0)) res = -res
return if (res > Int.MAX_VALUE) Int.MAX_VALUE else res

30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]

解题

fun _0030_findSubstring()
println("--------_0030_findSubstring-------")
println(findSubstring("barfoothefoobarman", arrayOf("foo", "bar")))
println(findSubstring("wordgoodgoodgoodbestword", arrayOf("word", "good", "best", "word")))
println(findSubstring("findsubstring", arrayOf("sub", "str")))

/**
* 把 words 数组中的所有单词放入 HashMap ，同时统计每个单词的出现次数。借助 HashMap 快速查找的特点，来匹配 s 字符串。
* 整体的思路很简单明了，就是挨个匹配。
*/
@SuppressLint("NewApi")
fun findSubstring(s: String, words: Array< String> ): List< Int>
val result = ArrayList< Int> ()
if (s.isEmpty() || words.isEmpty()) return result
val countMap = HashMap< String, Int> ()
for (i in words.indices)
countMap.put(words[i], countMap.getOrDefault(words[i], 0) + 1);

val wordLen = words[0].length
val wordsLen = words.size * wordLen
for (i in 0..s.length - wordsLen)
val workMap: MutableMap< String, Int> = HashMap()
var j = 0
while (j < words.size)
val word = s.substring(i + j * wordLen, i + (j + 1) * wordLen)
workMap[word] = workMap.getOrDefault(word, 0) + 1
if (workMap[word]!! > countMap.getOrDefault(word, 0)) break // 匹配失败
++j

if (j == words.size) result.add(i)

return result