11-Contains Duplicate II
题目大意
如果数组里面有重复数字，并且重复数字的下标差值小于等于 K 就输出 true，如果没有重复数字或者下标差值超过了 K ，则输出 flase。
解题思路
这道题可以维护一个只有 K 个元素的 map，每次只需要判断这个 map 里面是否存在这个元素即可。如果存在就代表重复数字的下标差值在 K 以内。map 的长度如果超过了 K 以后就删除掉 i-k 的那个元素，这样一直维护 map 里面只有 K 个元素。
map 键值根据具体业务灵活设置
代码
var nums3 = intArrayOf(1,2,3,1)
println(containsNearbyDuplicate(nums3,3))fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {if (nums.isEmpty()) return falseif (k < 0) return falsevar record = mutableMapOf<Int, Int>()for (i in nums.indices) {var index = record[nums[i]]if (index != null && i - index <= k) {return true} else {record[nums[i]] = i}}return false}
true
12- Summary Ranges
题目大意
给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
- “a->b” ，如果 a != b
- “a” ，如果 a == b
解题思路
按照题意，用一个游标变量累加寻找连续的区间。一旦出现了中断，就按照题意格式输出。输出的规则有多种，带箭头的区间，单个元素区间，空区间。
找临界点
代码
var nums3 = intArrayOf(0, 1, 2, 4, 5, 7)println(summaryRanges(nums3))fun summaryRanges(nums: IntArray): List<String> {if (nums.isEmpty()) return listOf()val res = ArrayList<String>()var left = 0for (i in 1 until nums.size) {if (nums[i - 1] + 1 < nums[i]) {res.add(format(nums[left], nums[i - 1]))left = i}println(i)}res.add(format(nums[left], nums.last()))return res
}fun format(i: Int, j: Int) = if (i == j) "$i" else "$i->$j"[0->2, 4->5, 7]
13-Missing Number
题目大意
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。算法应该具有线性时间复杂度。你能否仅使用额外常数空间来实现?
解题思路
要求找出 0, 1, 2, …, n 中缺失的那个数。还是利用异或的性质，X^X = 0。这里我们需要构造一个 X，用数组下标就可以了。数字下标是从 [0，n-1]，数字是 [0，n]，依次把数组里面的数组进行异或，把结果和 n 再异或一次，中和掉出现的数字，剩下的那个数字就是之前没有出现过的，缺失的数字。
代码
var nums3 = intArrayOf(3,0,1)
println(missingNumber(nums3))fun missingNumber(nums: IntArray): Int { //xorvar res = nums.sizefor (i in nums.indices) {res = res xor ires = res xor nums[i]}return res
}fun missingNumber(nums: IntArray): Int {return nums.size * (nums.size + 1) / 2 - nums.sum()
}
2
14-Range Sum Query - Immutable
题目大意
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
解题思路
给出一个数组，数组里面的数都是不可变的，设计一个数据结构能够满足查询数组任意区间内元素的和。
这一题由于数组里面的元素都是不可变的，所以可以用 2 种方式来解答，第一种解法是用 prefixSum，通过累计和相减的办法来计算区间内的元素和，初始化的时间复杂度是 O(n)，但是查询区间元素和的时间复杂度是 O(1)。第二种解法是利用线段树，构建一颗线段树，父结点内存的是两个子结点的和，初始化建树的时间复杂度是 O(log n)，查询区间元素和的时间复杂度是 O(log n)。
代码
var nums = intArrayOf(-2, 0, 3, -5, 2, -1)private lateinit var sums: IntArrayinit {var sum = 0sums = IntArray(nums.size + 1)sums[0] = 0for (i in 0..nums.size-1) {sum += nums[i]sums[i+1] = sum}}fun sumRange(left: Int, right: Int): Int {return sums[right+1] - sums[left]}
[[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]]
15- Intersection of Two Arrays
eg
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
题目大意
找到两个数组的交集元素，如果交集元素同一个数字出现了多次，只输出一次。
解题思路
把数组一的每个数字都存进字典中，然后在数组二中依次判断字典中是否存在，如果存在，在字典中删除它(因为输出要求只输出一次)
代码
var nums1 = intArrayOf(1, 2, 2, 1)
var nums2 = intArrayOf(2, 2)println(intersection(nums1,nums2).mapIndexed { index, value -> value })fun intersection(nums1: IntArray, nums2: IntArray): IntArray {var s = HashSet<Int>()nums1.forEach {s.add(it)}var t=HashSet<Int>()nums2.forEach {if (s.contains(it)){t.add(it)}}var res=IntArray(t.size)var i = 0for (num in t) {res[i++] = num}return res
}
[2]
16-Intersection of Two Arrays II
eg
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
题目大意
这题是第 349(上一题) 题的加强版。要求输出 2 个数组的交集元素，如果元素出现多次，要输出多次。
解题思路
这一题还是延续第 349 题的思路。把数组一中的数字都放进字典中，另外字典的 key 是数组中的数字，value 是这个数字出现的次数。在扫描数组二的时候，每取出一个存在的数组，把字典中的 value 减一。如果 value 是 0 代表不存在这个数字。
代码
var nums1 = intArrayOf(1, 2, 2, 1)
var nums2 = intArrayOf(2, 2)println(intersection(nums1,nums2).mapIndexed { index, value -> value })fun intersection(nums1: IntArray, nums2: IntArray): IntArray {var map = mutableMapOf<Int,Int>()for (i in nums1) {val freq: Int = map.getOrDefault(i, 0)map[i] = freq + 1}val list = ArrayList<Int>()for (i in nums2) {if (map[i] != null && map[i]!! > 0) {list.add(i)map[i] = map[i]!! - 1}}val ret = IntArray(list.size)for (i in list.indices) {ret[i] = list[i]}return ret
}
[2,2]
17-Third Maximum Number
题目大意
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是 O(n)。
代码
var nums1 = intArrayOf(2, 2, 3, 1)
nums1.sortDescending()
println(nums1.distinct().getOrNull(2)?:nums1[0])
1
18-Find All Numbers Disappeared in an Array
题目大意
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。你能在不使用额外空间且时间复杂度为 O(n) 的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
解题思路
找出 [1,n] 范围内没有出现在数组中的数字。要求不使用额外空间，并且时间复杂度为 O(n)。
要求不能使用额外的空间，那么只能想办法在原有数组上进行修改，并且这个修改是可还原的。时间复杂度也只能允许我们一层循环。只要循环一次能标记出已经出现过的数字，这道题就可以按要求解答出来。这里笔者的标记方法是把 |nums[i]|-1 索引位置的元素标记为负数。这里需要注意的是，nums[i] 需要加绝对值，因为它可能被之前的数置为负数了，需要还原一下。最后再遍历一次数组，若当前数组元素 nums[i] 为负数，说明我们在数组中存在数字 i+1。把结果输出到最终数组里即可。
代码
var nums1 = intArrayOf(4, 3, 2, 7, 8, 2, 3, 1)
println(findDisappearedNumbers(nums1).mapIndexed { index, i -> i })fun findDisappearedNumbers(nums: IntArray): IntArray {var list = ArrayList<Int>()var idx = -1for (item in nums) {idx = if (item < 0) {item * -1 - 1} else {item - 1}if (nums[idx] > 0) {nums[idx] = -nums[idx]}}for (i in nums.indices) {if (nums[i] > 0) {list.add(i + 1)}}return list.toIntArray()
}
[5, 6]
19-Assign Cookies
题目大意
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。
解题思路
假设你想给小朋友们饼干，每个小朋友最多能够给一块饼干。每个小朋友都有一个“贪心指数”，称为 g[i]，g[i] 表示的是这名小朋友需要的饼干大小的最小值。同时，每个饼干都有一个大小值 s[i]，如果 s[j] ≥ g[i]，我们将饼干 j 分给小朋友 i 后，小朋友会很开心。给定数组 g[] 和 s[]，问如何分配饼干，能让更多的小朋友开心。
这是一道典型的简单贪心题。贪心题一般都伴随着排序。将 g[] 和 s[] 分别排序。按照最难满足的小朋友开始给饼干，依次往下满足，最终能满足的小朋友数就是最终解。
代码
var g = intArrayOf(1, 2)var j = intArrayOf(1, 2,3)println(findContentChildren(g,j))
fun findContentChildren(g: IntArray, s: IntArray): Int {g.sort()s.sort()var i = 0var j = 0while (i < g.size && j < s.size) {if (g[i] <= s[j]) i++j++}return i
}
2
20. Island Perimeter
题目大意
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
解题思路
给出一个二维数组，二维数组中有一些连在一起的 1 ，这是一个岛屿，求这个岛屿的周长。
这是一道水题，判断四周边界的情况依次加一即可。
代码
var grid=arrayListOf<IntArray>()grid.add(intArrayOf(0,1,0,0))grid.add(intArrayOf(1,1,1,0))grid.add(intArrayOf(0,1,0,0))grid.add(intArrayOf(1,1,0,0))println(islandPerimeter(grid.toTypedArray()))
fun islandPerimeter(grid: Array<IntArray>): Int {var islands = 0var neighbours = 0for (i in grid.indices) {for (j in 0 until grid[i].size) {if (grid[i][j] === 1) {// count islandsislands++ // count down neighboursif (i < grid.size - 1 && grid[i + 1][j] === 1) neighbours++ // count right neighboursif (j < grid[i].size - 1 && grid[i][j + 1] === 1) neighbours++ }}}return islands * 4 - neighbours * 2
}
16
