每日LeetCode力扣（16~20）

愿君学长松，慎勿作桃李。这篇文章主要讲述每日LeetCode力扣（16~20）相关的知识，希望能为你提供帮助。
16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。
返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 < = nums.length < = 10^3
-10^3 < = nums[i] < = 10^3
-10^4 < = target < = 10^4

解题

fun _0016_threeSumClosest()
println("--------_0016_threeSumClosest-------")
println(threeSumClosest(intArrayOf(-1, 2, 1, -4), 1))
println(threeSumClosest(intArrayOf(-1, -2, 2, 1, -4), 1))
println(threeSumClosest(intArrayOf(2, 1, -4), 1))

fun threeSumClosest(nums: IntArray?, target: Int): Int
if (nums == null || nums.size < 3) return 0
var result = nums[0] + nums[1] + nums[2]
Arrays.sort(nums)
for (i in 0..nums.size - 2)
var start = i + 1
var end = nums.size - 1
while (start < end)
val sum = nums[i] + nums[start] + nums[end]
if (sum > target)
end--
else
start++

if (abs(sum - target) < abs(result - target))
result = sum

return result

17. 电话号码的字母组合(九宫格键盘)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解题

fun _0017_letterCombinations()
println("--------_0017_letterCombinations-------")
println(letterCombinations("23"))
println(letterCombinations("13"))
println(letterCombinations("333"))

/**
* 在遍历 digits 中所有的数字时，先建立一个临时的字符串数组t，通过数字到 dict 中取出字符串 str，
* 然后遍历取出字符串中的所有字符，再遍历当前结果 res 中的每一个字符串，将字符加到后面，并加入到临时字符串数组t中。
* 取出的字符串 str 遍历完成后，将临时字符串数组赋值给结果 res，具体实现参见代码如下：
*/
fun letterCombinations(digits: String?): ArrayList< String>
if (digits == null || digits.isEmpty()) return ArrayList()
val dict = arrayListOf("0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
var res = arrayListOf("")
for (i in digits.indices)
val t = ArrayList< String> ()
val str = dict[digits[i] - 0]
for (j in str.indices)
for (s in res)
t.add(s + str[j])

res = t

return res

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，
使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1,0, 0, 1],
[-2, -1, 1, 2],
[-2,0, 0, 2]
]

解题

fun _0018_fourSum()
println("--------_0018_fourSum-------")
println(fourSum(intArrayOf(1, 0, -1, 0, -2, 2), 0))

fun fourSum(nums: IntArray?, target: Int): List< List< Int> >
if (nums == null || nums.size < 4) return ArrayList()
val res = ArrayList< List< Int> > ()
val n = nums.size
Arrays.sort(nums)
for (i in 0..n - 3)
if (i > 0 & & nums[i] == nums[i - 1]) continue
for (j in i + 1..n - 2)
if (j > i + 1 & & nums[j] == nums[j - 1]) continue
var left = j + 1
var right = n - 1
while (left < right)
val sum = nums[i] + nums[j] + nums[left] + nums[right]
if (sum == target)
val oneResult = arrayListOf(nums[i], nums[j], nums[left], nums[right])
res.add(oneResult)
while (left < right & & nums[left] == nums[left + 1]) left++
while (left < right & & nums[right] == nums[right - 1]) right--
left++
right--
else if (sum < target)
left++
else right--

return res

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1-> 2-> 3-> 4-> 5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1-> 2-> 3-> 5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗

解题

fun _0019_removeNthFromEnd()
println("--------_0019_removeNthFromEnd-------")
removeNthFromEnd(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 1)?.print()
removeNthFromEnd(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 2)?.print()
removeNthFromEnd(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 3)?.print()
removeNthFromEnd(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 4)?.print()
removeNthFromEnd(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 5)?.print()

/**
* 这道题让我们移除链表倒数第N个节点，限定n一定是有效的，即n不会大于链表中的元素总数。
* 还有题目要求一次遍历解决问题，那么就得想些比较巧妙的方法了。比如首先要考虑的时，如何找到倒数第N个节点，
* 由于只允许一次遍历，所以不能用一次完整的遍历来统计链表中元素的个数，而是遍历到对应位置就应该移除了。
* 那么就需要用两个指针来帮助解题，pre 和 cur 指针。首先 cur 指针先向前走N步，如果此时 cur 指向空，
* 说明N为链表的长度，则需要移除的为首元素，那么此时返回 head-> next 即可，如果 cur 存在，再继续往下走，
* 此时 pre 指针也跟着走，直到 cur 为最后一个元素时停止，此时 pre 指向要移除元素的前一个元素，
* 再修改指针跳过需要移除的元素即可
*/
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode?
if (head?.next == null) return null
var n = n
var pre = head
var cur = head
for (i in 0 until n)
cur = cur?.next

if (cur == null) return head.next //说明n为链表长度
while (cur?.next != null)
cur = cur.next
pre = pre?.next

pre?.next = pre?.next?.next
return head

20. 有效的括号

给定一个只包括 (，)，，，[，] 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "[]"
输出: true

解题

fun _0020_isValid()
println("--------_0020_isValid-------")
println(isValid("()"))
println(isValid("()[]"))
println(isValid("(]"))
println(isValid("[]"))

/**
* 这里需要用一个栈，开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，
* 若此时栈为空，则直接返回 false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回 false，代码如下：
*/
fun isValid(s: String): Boolean
val stack = Stack< Char> ()
for (i in s.indices)
val c = s[i]
if (c == ( || c ==|| c == [)
stack.push(c)
else
if (stack.isEmpty()) return false
if (c == ) & & stack.peek() != () return false
if (c == ] & & stack.peek() != [) return false
if (c ==& & stack.peek() != ) return false
stack.pop()

return stack.isEmpty()