[HashTable | Array ]
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
fun twoSum(nums: IntArray, target: Int): IntArray {
val map = mutableMapOf<Int, Int>()
for ((index, i) in nums.withIndex()) {
val complement = target - i
if (map[complement] != null) {
return intArrayOf(index, map[complement]!!)
}
map[i] = index
}
return intArrayOf()
}
NOTE：反向思维，通过和来找另一个加数 ，为了不用遍历且更快地找到，将元素的值和位置保存在map里面，空间换时间
[Linked List | Math]
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
val head = ListNode()
var headCur = head
var l1Cur = l1
var l2Cur = l2
while (true) {
if (l1Cur != null) {
headCur.`val` += l1Cur.`val`
l1Cur = l1Cur.next
}
if (l2Cur != null) {
headCur.`val` += l2Cur.`val`
l2Cur = l2Cur.next
}
if (headCur.`val` > 9) {
headCur.`val` %= 10
headCur.next = ListNode(1)
}
if (l1Cur == null && l2Cur == null) {
break
}
if (headCur.next == null) {
headCur.next = ListNode()
}
headCur = headCur.next!!
}
return head
}
NOTE: 同时遍历两个列表，注意进位操作
[Hash Table | Two Pointers | String | Sliding Window]
Given a string s, find the length of the longest substring without repeating characters.
fun lengthOfLongestSubstring(s: String): Int {
var result = 0
val cPosition = mutableMapOf<Char, Int>()
var i = 0
var j = 0
while (j < s.length) {
val pos = cPosition[s[j]]
if (pos != null && pos >= i) {
i++
} else {
result = Math.max(result, j - i + 1)
cPosition[s[j]] = j
j++
}
}
return result
}
NOTE: 双指针，一个不断往前移动，判断是否有重复的字符，用Hash Table加速查询，不满足条件移动后面指针
[Array | Binary Search | Divide Conquuer ]
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
Follow up: The overall run time complexity should be O(log (m+n)).
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
val totalLen = nums1.size + nums2.size
val center:Int
val even = totalLen % 2 == 0
if (even) {
center = (totalLen + 1) / 2
} else {
center = totalLen / 2
}
var index1 = 0
var index2 = 0
var result = 0.0
var last = 0
for (i in 0 .. (totalLen - 1)) {
var cur = 0
if (index1 < nums1.size && index2 < nums2.size) {
if (nums1[index1] < nums2[index2]) {
cur = nums1[index1]
index1++
} else{
cur = nums2[index2]
index2++
}
} else if (index1 < nums1.size) {
cur = nums1[index1]
index1++
} else if (index2 < nums2.size){
cur = nums2[index2]
index2++
}
if (i == center) {
if (even) {
result = (last + cur) / 2.0
} else {
result = cur.toDouble()
}
break
}
last = cur;
}
return result
}
NOTE: 归并排序的方式对两个数组进行遍历，记录上一个值与当前值，到达中间的位置直接求出结果
[String | Dynamic Programing ]
Given a string s, return the longest palindromic substring in s.
fun longestPalindrome(s: String): String {
if (s.length < 2) {
return s
}
var max = 1
var start = 0;
val dp = Array(s.length) { BooleanArray(s.length) }
for (j in 1 until s.length) {
for (i in 0 until j) {
if (s[i] == s[j]) {
dp[i][j] = j - i + 1 <= 3 || dp[i + 1][j - 1]
} else {
dp[i][j] = false
}
if (dp[i][j] && j - i + 1 > max) {
max = j - i + 1
start = i
}
}
}
return s.substring(start, start + max)
}
NOTE: 从前往后遍历，用dp[][]记录计算过的回文串区间，避免重复计算
[String]
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
fun convert(s: String, numRows: Int): String {
if (numRows == 1) return s
val sbuilderArr = Array(numRows) { StringBuilder() }
var switchIndex = 0
var verticalIndex = 0
s.forEachIndexed { index, c ->
if (switchIndex != 0) {
sbuilderArr[switchIndex--].append(c)
} else {
sbuilderArr[verticalIndex++].append(c)
if (verticalIndex == numRows) {
switchIndex = numRows - 2
verticalIndex = 0
}
}
}
val result = StringBuilder()
sbuilderArr.forEach {
result.append(it)
}
return result.toString()
}
NOTE: 每一行用一个StringBuilder保存，然后顺序遍历，根据行数切换保存的位置，然后合并结果
[Math]
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
fun reverse(x: Int): Int {
var ret = 0
var y = x
var pop = 0
while (y != 0) {
pop = y % 10
if (ret > 0 && Integer.MAX_VALUE - ret * 10 < pop) {
return 0
} else if (ret < 0 && (Integer.MIN_VALUE - ret * 10) > pop ) {
return 0
}
ret = ret * 10 + pop
y /= 10
}
return ret
}
NOTE: 求余数得到各位，除以10消除个位，计算前先判断是否溢出，溢出的判断方法为先列不等式，然后变换不等式消除不等式计算两端移除的可能
[Math | String]
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
The algorithm for myAtoi(string s) is as follows:
'-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present."123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).[-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 2^31 - 1 should be clamped to 2^31 - 1.fun myAtoi(s: String): Int {
var ret = 0
var neg = false
var invalid = false
for (c in s) {
if (c == '-' || c == '+') {
if (invalid) {
break
}
if (c == '-') {
neg = true
} else if (c == '+') {
neg = false
}
invalid = true
} else if ((c == ' ')) {
if (invalid) {
break
}
continue
} else if (c > '9' || c < '0') {
break
} else {
val bit = c.toInt() - '0'.toInt()
if (!neg && ret > (Integer.MAX_VALUE - bit) / 10) {
ret = Integer.MAX_VALUE
break
} else if (neg && -ret < (Integer.MIN_VALUE + bit) / 10) {
ret = Integer.MIN_VALUE
break
}
ret = ret * 10 + bit
invalid = true
}
}
return if (neg) -ret else ret
}
NOTE: 用 invalid来判断是否还可以出入其他的字符，当开始输入数字或者已经输入符号就再能在输入其他符号
An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.
[Math]
fun isPalindrome(x: Int): Boolean {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false
}
var x = x
var ret = 0
while (x > ret) {
val pop = x % 10
ret = ret * 10 + pop
x /= 10
}
return x == ret || x == ret / 10
}
NOTE: 隐含条件 : 计算反转数字的时候只用计算一半即可
[String]
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’ where:
The matching should cover the entire input string (not partial).
fun isMatch(s: String, p: String): Boolean {
if (p.isEmpty()) {
return s.isEmpty()
}
val firstCharMatch = s.isNotEmpty() && (s[0] == p[0] || p[0] == '.')
val firstStarMatch = p.length > 1 && p[1] == '*'
if (firstCharMatch && firstStarMatch) {
return isMatch(s.substring(1), p) || isMatch(s, p.substring(2))
} else if (firstStarMatch) {
return isMatch(s, p.substring(2))
} else if (firstCharMatch) {
return isMatch(s.substring(1), p.substring(1))
}else {
return false
}
}
//DP:
fun isMatch(s: String, p: String): Boolean {
val pLen = p.length
val sLen = s.length
val dp = Array(pLen + 1){BooleanArray(sLen + 1)}
dp[0][0] = true
for (i in 1 .. pLen - 1 step 2) {
if (p[i] == '*') {
dp[i][0] = true
dp[i + 1][0] = true
} else {
break
}
}
for (i in 0 .. pLen - 1) {
for (j in 0 .. sLen - 1) {
if (p[i] == '*') {
dp[i + 1][j + 1] = dp[i][j + 1]
} else if (p[i] == '.' || p[i] == s[j]) {
if (i + 1 < pLen && p[i + 1] == '*') {
dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j]
} else {
dp[i + 1][j + 1] = dp[i][j]
}
} else {
if (i + 1 < pLen && p[i + 1] == '*') {
dp[i + 1][j + 1] = dp[i][j + 1]
}
}
}
}
return dp[pLen][sLen]
}
NOTE: 递归逐字符对比，根据模式字符串与被匹配字符的前两个字符的匹配结果不断地向前移动字符串，如果模式字符串为空了，那么被匹配的字符串也要为空才能正确地匹配。DP解法注意初始的条件。
[Two Pointers | Array]
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
fun maxArea(height: IntArray): Int {
var start = 0
var end = height.size - 1
var max = 0
while (start < end) {
val area = Math.min(height[start], height[end]) * (end - start)
if (area > max) {
max = area
}
if (height[start] > height[end]) {
end--
} else {
start++
}
}
return max
}
NOTE: 面积大小取决于最矮高度， min(x, y) * width, 宽度一定只能尽可能地增加高度才能让面积最大
[Math]
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
Given an integer, convert it to a roman numeral.
fun intToRoman(num: Int): String {
val ret = StringBuilder()
val romanInt = intArrayOf(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
val romanStr = arrayOf("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I")
var num = num
var i = 0
while (num > 0) {
if (num - romanInt[i] >= 0) {
num -= romanInt[i]
ret.append(romanStr[i])
} else {
i++
}
}
return ret.toString()
}
NOTE: 罗马数字的特征，尽可能优先使用较大数值对应的字符，最后转换的结果字符最少，理由贪心算法思想，从最高位开始匹配，就能保证字符串最少。最开始想到的是另外一种方法查表法，将罗马数字的所有个位，十位..组合罗列出来，取低位的值不断地加，列表的时候较烦琐。
[Math]
fun romanToInt(s: String): Int {
var ret = 0
val romanMap = mapOf("M" to 1000, "CM" to 900, "D" to 500, "CD" to 400,
"C" to 100, "XC" to 90, "L" to 50, "XL" to 40, "X" to 10, "IX" to 9,
"V" to 5, "IV" to 4, "I" to 1)
var romanStr = s
while (romanStr.isNotEmpty()) {
if (romanStr.length > 1 && romanMap[romanStr.substring(0, 2)] != null) {
ret += romanMap[romanStr.substring(0, 2)]!!
romanStr = romanStr.substring(2)
} else {
ret += romanMap[romanStr.substring(0, 1)]!!
romanStr = romanStr.substring(1)
}
}
return ret
}
NOTE: 思路同12，利用贪心算法。罗马数字高位就包含了位置信息只需从高位得到阿拉伯数字的值加上低位即可。
[String]
fun longestCommonPrefix(strs: Array<String>): String {
if (strs.isEmpty()) return ""
var ret = strs[0]
for (i in 1 until strs.size) {
ret = computeCommonPrefix(ret, strs[i])
if (ret.isEmpty()) {
return ""
}
}
return ret
}
private fun computeCommonPrefix(s1: String, s2: String): String {
var i = 0
var j = 0
while (i < s1.length && j < s2.length) {
if (s1[i] == s2[j]) {
i++
j++
} else {
break
}
}
return s1.substring(0, i)
}
[Array | Two Pointer]
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.
fun threeSum(nums: IntArray): List<List<Int>> {
if (nums.size < 3) {
return listOf()
}
nums.sort()
val ret = mutableListOf<List<Int>>()
for ((index, value) in nums.withIndex()) {
if (index != 0 && nums[index] == nums[index - 1]) {
continue
}
var start = index + 1
var end = nums.size - 1
while (start < end) {
if (start != (index + 1) && nums[start] == nums[start - 1]) {
start++;
continue;
}
val threeSum = value + nums[start] + nums[end]
if (threeSum == 0) {
ret.add(listOf(value, nums[start], nums[end]))
end--
start++
} else if (threeSum > 0) {
end--
} else {
start++
}
}
}
return ret
}
NOTE: 排序，去重，利用双指针特性
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
fun threeSumClosest(nums: IntArray, target: Int): Int {
nums.sort()
var closest = 0
var distance = Integer.MAX_VALUE
for ((index, value) in nums.withIndex()) {
if (index != 0 && nums[index] == nums[index - 1]) {
continue
}
var start = index + 1
var end = nums.size - 1
while (start < end) {
if (start != index + 1 && nums[start - 1] == nums[start]) {
start++
continue
}
val treeSum = value + nums[start] + nums[end]
val curDistance = treeSum - target
if (curDistance == 0) {
return target
} else if (curDistance > 0) {
end--
} else if (curDistance < 0) {
start++
}
val absDis = Math.abs(curDistance)
if (absDis < distance) {
closest = treeSum
distance = absDis
}
}
}
return closest
}
[String | Backtracking | Depth-first Search | Recursion]
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
//使用数组记录进位信息
fun letterCombinations(digits: String): List<String> {
val ret = mutableListOf<String>()
val numberStrList = mutableListOf<String>()
for (c in digits) {
numberStrList.add(letterTable(c))
}
val arrIndex = Array(numberStrList.size) {0}
while (true) {
val strBuilder = StringBuilder()
for ((index, numStr) in numberStrList.withIndex()) {
strBuilder.append(numStr[arrIndex[index]])
}
if (strBuilder.isNotEmpty()) {
ret.add(strBuilder.toString())
}
var carry = 1
for (i in arrIndex.size - 1 downTo 0) {
if (carry == 0) {
break
}
if (arrIndex[i] + carry == numberStrList[i].length) {
carry = 1
arrIndex[i] = 0
} else {
arrIndex[i] += carry
carry = 0
}
}
if (carry == 1) {
break
}
}
return ret
}
fun letterTable(char: Char) = when (char) {
'2' -> "abc"
'3' -> "def"
'4' -> "ghi"
'5' -> "jkl"
'6' -> "mno"
'7' -> "pqrs"
'8' -> "tuv"
'9' -> "wxyz"
else -> ""
}
val ret = mutableListOf<String>()
fun letterCombinations(digits: String): List<String> {
if (digits.length == 0) {
return ret
}
val numberStrList = mutableListOf<String>()
for (c in digits) {
numberStrList.add(letterTable(c))
}
internalLetterCombination(0, numberStrList, StringBuilder())
return ret
}
fun internalLetterCombination(index: Int, numberStrList:List<String>, sb:StringBuilder) {
if (index == numberStrList.size) {
ret.add(sb.toString())
return
}
for (c in numberStrList[index]) {
sb.append(c)
internalLetterCombination(index + 1, numberStrList, sb)
sb.deleteCharAt(sb.length - 1)
}
}
NOTE：两种方法，递归与迭代
[Two Pointer | HashTable]
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.
fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
val ret = mutableListOf<List<Int>>()
nums.sort()
for (i in 0..nums.size - 1) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue
}
for (j in i + 1..nums.size - 1) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue
}
var start = j + 1
var end = nums.size - 1
while (start < end) {
val tmp = nums[i] + nums[j] + nums[start] + nums[end]
if (target == tmp) {
ret.add(listOf(nums[i], nums[j], nums[start], nums[end]))
start++
end--
} else if (tmp > target) {
end--
} else {
start++
}
}
}
}
return ret
}
NOTE：时间复杂度(o^3)
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Follow up: Could you do this in one pass?
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
val dummyHead = ListNode(0)
dummyHead.next = head
val recordList = mutableListOf<ListNode>()
var tmp: ListNode? = dummyHead
while (tmp != null) {
recordList.add(tmp)
tmp = tmp.next
}
val toRemove = recordList[recordList.size - n]
val preToRemove = recordList[recordList.size - n - 1]
preToRemove.next = toRemove.next
return dummyHead.next
}
NOTE: 构造Dummy节点就不用对头部单独处理； toRemove.next不用判断空；如果不用列表记录位置信息那么需要先遍历一遍算长度
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.
An input string is valid if:
fun isValid(s: String): Boolean {
val stack = LinkedList<Char>()
for (c in s) {
val opposite = convertRight(c)
if (opposite != ' ') {
if (stack.isEmpty() || stack.pop() != opposite) {
return false
}
} else {
stack.push(c)
}
}
return stack.isEmpty()
}
fun convertRight(c: Char) = when(c) {
')' -> '('
']' -> '['
'}' -> '{'
else -> ' '
}
NOTE: 注意stack.isEmpty()判断顺序
[LinkedList | Recursion]
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
if (l1 == null) {
return l2
} else if (l2 == null) {
return l1
} else if (l1.`val` < l2.`val`) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
Note: 递归简洁
[String | Backtracking]
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
val ret1 = mutableListOf<String>()
fun generateParenthesis(n: Int): List<String> {
generateParenthesisInternal(n, n , StringBuilder())
return ret1
}
fun generateParenthesisInternal(leftBracket: Int, rightBracket: Int, sb: StringBuilder) {
if (leftBracket == 0 && rightBracket == 0) {
ret1.add(sb.toString())
return
} else if (leftBracket > rightBracket) {
return
} else if (leftBracket < 0) {
return
}
sb.append('(')
generateParenthesisInternal(leftBracket - 1, rightBracket, sb)
sb.deleteCharAt(sb.length - 1)
sb.append(')')
generateParenthesisInternal(leftBracket, rightBracket - 1, sb)
sb.deleteCharAt(sb.length - 1)
}
Note: 回溯结束条件
[LinkedList | Divide and Conquer | Heap]
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
return mergeKListsIntern(lists)
}
fun mergeKListsIntern(lists: Array<ListNode?>): ListNode? {
if (lists.size == 1) {
return lists[0]
} else if (lists.isEmpty()) {
return null
}
val leftListNode = mergeKListsIntern(lists.sliceArray(0 .. lists.size / 2 - 1))
val rightListNode = mergeKListsIntern(lists.sliceArray(lists.size / 2 .. lists.size - 1))
return mergeTwoListNode(leftListNode, rightListNode)
}
fun mergeTwoListNode(l1: ListNode?, l2: ListNode?): ListNode? {
if (l1 == null) {
return l2
} else if (l2 == null) {
return l1
} else if (l1.`val` < l2.`val`) {
l1.next = mergeTwoListNode(l1.next, l2)
return l1
} else {
l2.next = mergeTwoListNode(l1, l2.next)
return l2
}
}
[LinkedList | ]
Given a linked list, swap every two adjacent nodes and return its head.
fun swapPairs(head: ListNode?): ListNode? {
val dummyListNode = ListNode()
dummyListNode.next = head
var ihead = head
var pre = dummyListNode
while (ihead != null && ihead.next != null) {
val node1: ListNode = ihead
val node2: ListNode = ihead.next!!
pre.next = node2
node1.next = node2.next
node2.next = node1
ihead = node1.next
pre = node1
}
return dummyListNode.next
}
fun swapPairs(head: ListNode?): ListNode? {
if (head == null || head.next == null) {
return head
}
val newHead: ListNode = head.next!!
head.next = swapPairs(newHead.next)
newHead.next = head
return newHead
}
NOTE：同时遍历两个节点；递归版本!!!
[LinkedList]
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
Follow up:
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
val dummyHead = ListNode()
dummyHead.next = head
var ihead = head
var cur = head
var cnt = 1
var preCur: ListNode? = dummyHead
while (ihead != null) {
if (k == cnt) {
//reverse from cur ...
val newTail = cur
var curN = cur?.next
var curNN:ListNode? = null
while (cnt > 1) {
curNN = curN?.next
curN?.next = cur
cur = curN
curN = curNN
cnt--
}
newTail?.next = curN
preCur?.next = cur
cur = curN
preCur = newTail
ihead = newTail?.next
//cnt = 1
} else {
cnt++
ihead = ihead.next
}
}
return dummyHead.next
}
NOTE: 利用三个指针反转链表到达空间复杂度O(1)
[Array | Two Pointer]
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
fun removeDuplicates(nums: IntArray): Int {
if (nums.isEmpty()) {
return 0
}
var i = 0
for (j in 1 .. nums.size - 1) {
if (nums[i] != nums[j]) {
i++
nums[i] = nums[j]
}
}
return i + 1
}
NOTE: 快慢指针移动赋值补位，不用移动后面的所有元素..
[Array | Two Pointer]
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
fun removeElement(nums: IntArray, `val`: Int): Int {
var i = -1
for (j in 0 .. nums.size - 1) {
if (nums[j] != `val`) {
i++
nums[i] = nums[j]
}
}
return i + 1
}
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
fun strStr(haystack: String, needle: String): Int {
val m = haystack.length
val n = needle.length
if (n == 0) return 0
if (n > m) {
return -1
}
for (i in 0 .. m - n) {
for (j in 0 .. n - 1) {
if (haystack[i + j] != needle[j]) break
if (j == n - 1) {
return i
}
}
}
return -1
}
[Math]
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, assume that your function returns 2^31 − 1 when the division result overflows.
fun divide(dividend: Int, divisor: Int): Int {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
val positive = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)
val absDividend = Math.abs(dividend)
val absDivisor = Math.abs(divisor)
var toDec = absDivisor
var total = absDividend
var ret = 0
var cnt = 1
while (total - toDec >= 0) {
total -= toDec
ret += cnt
if (total <=0 ) {
break
}
if (total - (toDec shl 1) < 0) {
toDec = absDivisor
cnt = 1
} else {
if (toDec < Int.MAX_VALUE - toDec) {
toDec = (toDec shl 1)
cnt += cnt
}
}
}
if (positive) {
return ret
} else {
return -ret
}
}
NOTE: 加法和就绝对值都可能溢出
[HashTable]
You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
fun findSubstring(s: String, words: Array<String>): List<Int> {
val ret = mutableListOf<Int>()
val wordCountMap = mutableMapOf<String, Int>()
for (word in words) {
wordCountMap.put(word, wordCountMap.getOrDefault(word, 0) + 1)
}
val wordLen = words[0].length
val totalWorldLen = words.sumBy { it.length }
for (i in 0 .. s.length - totalWorldLen) {
val subStrMap = mutableMapOf<String, Int>()
var matchedCnt = 0
for (j in i .. i + totalWorldLen - 1 step wordLen) {
val subStr = s.substring(j, j + wordLen)
val cnt = subStrMap.getOrDefault(subStr, 0) + 1
if (cnt > wordCountMap.getOrDefault(subStr, 0)) {
break
}
matchedCnt++
subStrMap.put(subStr, cnt)
}
if (matchedCnt == words.size) {
ret.add(i)
}
}
return ret
}
NOTE：使用HashMap加速匹配
[Array]
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in place and use only constant extra memory.
fun nextPermutation(nums: IntArray): Unit {
var end = nums.size - 1
var i = -1
var j = -1
//find i
for (k in end downTo 1) {
if (nums[k] > nums[k - 1]) {
i = k - 1
break
}
}
//find j
if (i != -1) {
for (k in end downTo i) {
if (nums[k] > nums[i]) {
j = k
break
}
}
}
//swap i and j
if (i != -1 && j != -1) {
swap(nums, i, j)
}
//reverse i .. tail
var start = i + 1
while (start < end) {
swap(nums, start++, end--)
}
}
fun swap(arr: IntArray, i: Int, j: Int) {
val tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
NOTE: 要让数变大->将右边较大的数与左边较小的数交换，要想使变化的幅度最小，要在较大的数里面找到最小的
[String | Dynamic Program]
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
fun longestValidParentheses(s: String): Int {
val dp = IntArray(s.length)
var ret = 0
for ((index, value) in s.withIndex()) {
if (value == ')') {
if (index > 0) {
if (s[index - 1] == '(') {
dp[index] = (if (index - 2 >= 0) dp[index - 2] else 0) + 2
} else if (s[index - 1] == ')' && index - dp[index - 1] - 1 >= 0 && s[index - dp[index - 1] - 1] == '(') {
dp[index] = dp[index - 1] + 2 + if (index - dp[index - 1] - 2 >= 0) dp[index - dp[index - 1] - 2] else 0
}
ret = Math.max(dp[index], ret)
}
}
}
return ret
}
NOTE: 使用例子列状态转移方程，尾部存在两张情况 “()”， “(…XX))”
[Binary Search]
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
fun search(nums: IntArray, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left <= right) {
val mid = (left + right) / 2
if (target == nums[mid]) {
return mid
}
if (nums[left] <= nums[mid]) {//left sorted， 注意这里的等号，left与mid在两个数的时候相等
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1
} else {
left = mid + 1
}
} else {//right sorted
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
Note: 二分法，有一边肯定是有序的，判断是否在有序的返回以内，如果在，那么就可以在这个范围查找，不在的话肯定在另外一边
[Binary Search]
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
Follow up: Could you write an algorithm with O(log n) runtime complexity?
fun searchRange(nums: IntArray, target: Int): IntArray {
var l = 0
var r = nums.size - 1
var retL = -1
var retR = -1
//search left bound
while (l <= r) {
val mid = (l + r) / 2
if (nums[mid] == target) {
retL = mid
r = mid - 1
} else if (nums[mid] > target) {
r = mid - 1
} else {
l = mid + 1
}
}
//search right bound
l = 0
r = nums.size - 1
while (l <= r) {
val mid = (l + r) / 2
if (nums[mid] == target) {
retR = mid
l = mid + 1
} else if (nums[mid] > target) {
r = mid - 1
} else {
l = mid + 1
}
}
return intArrayOf(retL, retR)
}
Note: 二分法核心是确定搜索区间
[Binary Search]
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
fun searchInsert(nums: IntArray, target: Int): Int {
var l = 0
var r = nums.size - 1
while (l <= r) {
val mid = (l + r) / 2
if (nums[mid] == target) {
return mid
} else if (nums[mid] > target) {
r = mid - 1
} else if (nums[mid] < target) {
l = mid + 1
}
}
return l
}
[Array | HashTable]
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Note:
fun isValidSudoku(board: Array<CharArray>): Boolean {
val rowMap = Array(10) {IntArray(10)}
val colMap = Array(10) {IntArray(10)}
val subBoxMap = Array(10) {IntArray(10)}
var row = 0
while (row < board.size) {
var col = 0
while (col < board[row].size) {
if (board[row][col] == '.') {
col++
continue
}
val digits = board[row][col] - '0'
//row exists
if (rowMap[row][digits] != 0) {
return false
} else {
rowMap[row][digits] = 1
}
//col exists
if (colMap[col][digits] != 0) {
return false
} else {
colMap[col][digits] = 1
}
//subbox exists
if (subBoxMap[(row / 3) * 3 + col / 3][digits] != 0) {
return false
} else {
subBoxMap[(row / 3) * 3 + col / 3][digits] = 1
}
col++
}
row++
}
return true
}
NOTE: 逐个遍历，然后使用表加速查找
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
The ‘.’ character indicates empty cells.
fun solveSudoku(board: Array<CharArray>): Unit {
val rowTable = Array(10) { IntArray(10) { 0 } }
val colTable = Array(10) { IntArray(10) { 0 } }
val subTable = Array(10) { IntArray(10) { 0 } }
for (row in 0..board.size - 1) {
for (col in 0..board[0].size - 1) {
if (board[row][col] != '.') {
val digit = board[row][col] - '0'
rowTable[row][digit] = 1
colTable[col][digit] = 1
subTable[3 * (row / 3) + col / 3][digit] = 1
}
}
}
solveSudoku(board, rowTable, colTable, subTable, 0, 0)
}
fun solveSudoku(board: Array<CharArray>, rowTable: Array<IntArray>, colTable: Array<IntArray>, subTable: Array<IntArray>, row: Int, col: Int): Boolean {
if (row == board.size) {
return true
}
var ret: Boolean = false
if (board[row][col] == '.') {
for (i in 1..9) {
if (rowTable[row][i] != 1 && colTable[col][i] != 1 && subTable[3 * (row / 3) + col / 3][i] != 1) {
rowTable[row][i] = 1
colTable[col][i] = 1
subTable[3 * (row / 3) + col / 3][i] = 1
board[row][col] = '0' + i
if (col == board[0].size - 1) {
ret = solveSudoku(board, rowTable, colTable, subTable, row + 1, 0)
} else {
ret = solveSudoku(board, rowTable, colTable, subTable, row, col + 1)
}
if (ret) {
return true
}
board[row][col] = '.'
rowTable[row][i] = 0
colTable[col][i] = 0
subTable[3 * (row / 3) + col / 3][i] = 0
}
}
} else {
if (col == board[0].size - 1) {
ret = solveSudoku(board, rowTable, colTable, subTable, row + 1, 0)
} else {
ret = solveSudoku(board, rowTable, colTable, subTable, row, col + 1)
}
}
return ret
}
Note: 万能的回溯..
[String]
The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
To determine how you “say” a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
fun countAndSay(n: Int): String {
var ret = StringBuilder()
for (i in 1..n) {
if (ret.isEmpty()) {
ret.append(i)
} else {
val tmp = StringBuilder()
var lastChar = 'x'
var cnt = 1
for ((index, c) in ret.withIndex()) {
if (index == 0) {
tmp.append(c)
} else {
if (lastChar == c) {
cnt++
} else {
tmp.append(cnt)
tmp.append(c)
cnt = 1
}
}
lastChar = c
}
tmp.append(cnt)
ret = tmp
}
}
return ret.reverse().toString()
}
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
val ret5 = mutableListOf<List<Int>>()
fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
//candidates.sort()
internalCombinationSum(candidates, target, mutableListOf(), 0)
return ret5
}
fun internalCombinationSum(candidates: IntArray, target: Int, tracer: MutableList<Int>, startIndex: Int) {
val sum = tracer.sum()
if (sum == target) {
ret5.add(ArrayList(tracer))
return
} else if (sum > target) {
return
}
for (i in startIndex..candidates.size - 1) {
tracer.add(candidates[i])
internalCombinationSum(candidates, target, tracer, i)
tracer.removeAt(tracer.size - 1)
}
}
Note: 可不排序，排序后减少回溯分支
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
val ret6 = mutableListOf<List<Int>>()
fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
candidates.sort()
combinationSum2Recur(candidates, target, 0, mutableListOf())
return ret6
}
fun combinationSum2Recur(candidates: IntArray, target: Int, startIndex: Int, tracer: MutableList<Int>) {
val sum = tracer.sum()
if (sum == target) {
ret6.add(ArrayList(tracer))
return
} else if (sum > target) {
return
}
for (i in startIndex..candidates.size - 1) {
if (i != startIndex && candidates[i] == candidates[i - 1]) {
continue
}
tracer.add(candidates[i])
combinationSum2Recur(candidates, target, i + 1, tracer)
tracer.removeAt(tracer.size - 1)
}
}
Note: 排序去重
Given an unsorted integer array nums, find the smallest missing positive integer.
fun firstMissingPositive(nums: IntArray): Int {
val len = nums.size + 1
val hash = Array(len){-1}
for ((index, value) in nums.withIndex()) {
if (value > 0 && value < len) {
hash[value] = index
}
}
for (i in 1 .. nums.size) {
if (hash[i] == -1) {
return i
}
}
return nums.size + 1
}
Note: 利用哈希表加速查找
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
//DP:
fun trap(height: IntArray): Int {
if (height.size <= 2) {
return 0
}
var ret = 0
val maxLefts = Array(height.size){0}
val maxRights = Array(height.size){0}
var tmpMax = 0
for (i in 0 .. height.size - 1) {
maxLefts[i] = Math.max(height[i], tmpMax)
tmpMax = maxLefts[i]
}
tmpMax = 0
for (i in height.size - 1 downTo 0) {
maxRights[i] = Math.max(height[i], tmpMax)
tmpMax = maxRights[i]
}
for (i in 1 .. (height.size - 2)) {
val area = Math.min(maxLefts[i], maxRights[i]) - height[i]
if (area > 0) {
ret += area
}
}
return ret
}
//Two Pointer
fun trap(height: IntArray): Int {
if (height.size < 3) {
return 0
}
var ret = 0
var maxLeft = height[0]
var maxRight = height[height.size - 1]
var left = 1
var right = height.size - 2
while (left <= right) {
if (maxLeft < maxRight) {
val area = maxLeft - height[left]
if (area > 0) {
ret += area
}
maxLeft = Math.max(maxLeft, height[left])
left++
} else {
val area = maxRight - height[right]
if (area > 0) {
ret += area
}
maxRight = Math.max(maxRight, height[right])
right--
}
}
return ret
}
Note: 当前条的面积等于左边的最大高度与右边最小高度的最小值减去当前条的高度。双指针可以利用隐含条件，当另外一边的最大大于已经遍历过的这一边的最大，就可以确定左右最大中的最小。
[String | Math]
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
fun multiply(num1: String, num2: String): String {
if (num1.equals("0") || num2.equals("0")) {
return "0"
}
var ret = ""
var tailZero = 0
for (c2 in num2.length - 1 downTo 0) {
val i2 = num2[c2] - '0'
var carry = 0
val tmp = StringBuilder()
for (c1 in num1.length - 1 downTo 0) {
val i1 = num1[c1] - '0'
val product = i1 * i2 + carry
val cur = product % 10
carry = product / 10
tmp.append(cur.toString())
}
if (carry > 0) {
tmp.append(carry)
}
for (i in 1..tailZero) {
tmp.insert(0, "0")
}
ret = plus(ret, tmp.toString())
tailZero++
}
return ret.reversed()
}
fun plus(num1: String, num2: String): String {
if (num1.isEmpty()) {
return num2
}else if (num2.isEmpty()) {
return num1
}
val ret = StringBuilder()
var i = 0
var j = 0
var carry = 0
while (true) {
if (i <= num1.length - 1 && j <= num2.length - 1) {
val i1 = num1[i] - '0'
val i2 = num2[i] - '0'
val addtion = i1 + i2 + carry
ret.append(addtion % 10)
carry = addtion / 10
} else if (i <= num1.length - 1) {
val v = num1[i] - '0'
val addtion = v + carry
ret.append(addtion % 10)
carry = addtion / 10
} else if (j <= num2.length - 1) {
val v = num2[j] - '0'
val addtion = v + carry
ret.append(addtion % 10)
carry = addtion / 10
} else {
break
}
i++
j++
}
if (carry > 0) {
ret.append(carry)
}
return ret.toString()
}
[Dynamic Programing]
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’ where:
The matching should cover the entire input string (not partial).
fun isMatch(s: String, p: String): Boolean {
val pLen = p.length
val sLen = s.length
val dp = Array(pLen + 1){ BooleanArray(sLen + 1)}
dp[0][0] = true
for (i in 0 .. pLen - 1) {
if (p[i] == '*') {
dp[i + 1][0] = true
} else {
break
}
}
for (i in 0 .. pLen-1) {
for (j in 0 .. sLen-1) {
if (p[i] == s[j] || p[i] == '?') {
dp[i + 1][j + 1] = dp[i][j]
} else if (p[i] == '*') {
dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j]
}
}
}
return dp[pLen][sLen]
}
Note: 注意号的转移方程，是左右匹配的，被消耗或者没有被消耗的情况
[Greedy]
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.
//reverse:
fun jump(nums: IntArray): Int {
var step = 0
val end = nums.size - 1
var position = end
var curEnd = end
while (position > 0) {
position--
for (i in 0 until position) {
if (i + nums[i] >= curEnd) {
position = i
break
}
}
curEnd = position
step++
}
return step
}
//forward:
fun jump(nums: IntArray): Int {
var steps = 0
var end = 0
var curMaxDistance = 0
for (i in 0 .. nums.size - 2) {
curMaxDistance = Math.max(nums[i] + i, curMaxDistance)
if (end == i) {
steps++
end = curMaxDistance
}
}
return steps
}
Note: 求局部最优解 —> 全局最优解
[Backtracking]
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
val ret7 = mutableListOf<List<Int>>();
fun permute(nums: IntArray): List<List<Int>> {
permuteRecur(nums, mutableListOf())
return ret7
}
fun permuteRecur(nums: IntArray, tracer: MutableList<Int>) {
if (tracer.size == nums.size) {
ret7.add(tracer.toList())
return
}
for (i in nums) {
if (!tracer.contains(i)) {
tracer.add(i)
permuteRecur(nums, tracer)
tracer.remove(i)
}
}
}
//Space O(1)
val ret8 = mutableListOf<List<Int>>();
fun permute(nums: IntArray): List<List<Int>> {
permuteRecur(nums, 0)
return ret8
}
fun permuteRecur(nums: IntArray, startIndex: Int) {
if (startIndex == nums.size) {
ret8.add(nums.toList())
return
}
for (index in startIndex .. nums.size - 1) {
swap(nums, index, startIndex)
permuteRecur(nums, startIndex + 1)
swap(nums, index, startIndex)
}
}
fun swap(x: IntArray, a: Int, b: Int) {
val t = x[a]
x[a] = x[b]
x[b] = t
}
[Backtracking]
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
val ret9 = mutableListOf<List<Int>>()
fun permuteUnique(nums: IntArray): List<List<Int>> {
nums.sort()
permuteUnique(nums, BooleanArray(nums.size), LinkedList())
return ret9
}
fun permuteUnique(nums: IntArray, visited: BooleanArray, path: LinkedList<Int>) {
if (path.size == nums.size ) {
ret9.add(path.toList())
return
}
for (i in 0 .. nums.size - 1) {
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue
}
if (visited[i]) {
continue
}
path.add(nums[i])
visited[i] = true
permuteUnique(nums, visited, path)
visited[i] = false
path.removeLast()
}
}
Note: 开始遍历了之后就不用判断相同的上一个
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
fun rotate(matrix: Array<IntArray>): Unit {
var level = 0
val end = matrix.size - 1
while (matrix.size - 2 * level >= 2) {
for (i in level .. matrix.size - level - 2) {
//(level, i) -> (i, end - level)
val leftTop = matrix[level][i]
val rightTop = matrix[i][end - level]
val rightBottom = matrix[end - level][end - i]
val leftBottom = matrix[end - i][level]
matrix[level][i] = leftBottom
matrix[i][end - level] = leftTop
matrix[end - level][end - i] = rightTop
matrix[end - i][level] = rightBottom
}
level++
}
}
Note: 注意边界条件
[HashTable]
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
fun groupAnagrams(strs: Array<String>): List<List<String>> {
val map = mutableMapOf<String, MutableList<String>>()
for (s in strs) {
val chars = s.toCharArray()
chars.sort()
val key = String(chars)
if (map.containsKey(key)) {
map[key]?.add(s)
} else {
map[key] = mutableListOf(s)
}
}
val values = map.values
val ret = mutableListOf<List<String>>()
values.forEach {
ret.add(it)
}
return ret
}
[Divide Conquer]
Implement pow(x, n), which calculates x raised to the power n (i.e. xn).
//递归：
fun myPow(x: Double, n: Int): Double {
if (n < 0) {
return 1.0f / myPowRecur(x, Math.abs(n))
} else {
return myPowRecur(x, Math.abs(n))
}
}
fun myPowRecur(x: Double, n: Int): Double {
if (n == 1) {
return x
} else if (n == 0) {
return 1.0
}
val part = myPowRecur(x, n / 2)
if (n % 2 == 0) {
return part * part
} else {
return part * part * x
}
}
//迭代：
fun myPow(x: Double, n: Int): Double {
var ret = 1.0
var N = Math.abs(n.toLong())
var tmp = x
while (N > 0) {
if (N and 1 == 1L) {
ret *= tmp
}
N = N shr 1
tmp *= tmp
}
return if (n > 0) ret else 1.0 / ret
}
Note: 指数二进制移位
[Backtracking]
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.
val ret = mutableListOf<List<String>>()
fun solveNQueens(n: Int): List<List<String>> {
solveNQueensRecur(n, 0, IntArray(n){-1})
return ret
}
fun solveNQueensRecur(n: Int, row: Int, path: IntArray) {
//check （row - 1）already placed
if (row == path.size) {
val listStr = mutableListOf<String>()
val tmp = StringBuilder()
for (i in path) {
tmp.clear()
for (j in 0 .. row - 1) {
if (i == j) {
tmp.append("Q")
} else {
tmp.append(".")
}
}
listStr.add(tmp.toString())
}
ret.add(listStr)
return
}
for (i in 0 .. n - 1) {
path[row] = i
if (!checkPathIsValid(path, row)) {
continue
}
solveNQueensRecur(n, row + 1, path)
path[row] = -1
}
}
fun checkPathIsValid(path: IntArray, row: Int) : Boolean {
if (row >= 1) {
val cur = path[row]
for (k in row - 1 downTo 0) {
if (cur == path[k]) {
return false
}
if ((path[k] + row - k) == cur || (path[k] - (row - k)) == cur) {
return false
}
}
}
return true
}
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
var ret2 = 0
fun solveNQueensRecur(n: Int, row: Int, path: IntArray) {
//check （row - 1）already placed
if (row == path.size) {
ret2++
return
}
for (i in 0 .. n - 1) {
path[row] = i
if (!checkPathIsValid(path, row)) {
continue
}
solveNQueensRecur(n, row + 1, path)
path[row] = -1
}
}
fun checkPathIsValid(path: IntArray, row: Int) : Boolean {
if (row >= 1) {
val cur = path[row]
for (k in row - 1 downTo 0) {
if (cur == path[k]) {
return false
}
if ((path[k] + row - k) == cur || (path[k] - (row - k)) == cur) {
return false
}
}
}
return true
}
fun totalNQueens(n: Int): Int {
solveNQueensRecur(n, 0, IntArray(n){-1})
return ret2
}
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
fun maxSubArray(nums: IntArray): Int {
var subMax = nums[0]
var max = subMax
for (i in 1 .. nums.size - 1) {
if (subMax < 0) {
subMax = nums[i]
} else {
subMax += nums[i]
}
max = Math.max(max, subMax)
}
return max
}
Note: 动态规划， 状态压缩，只取最大的那个
Given an m x n matrix, return all elements of the matrix in spiral order.
fun spiralOrder(matrix: Array<IntArray>): List<Int> {
val ret = mutableListOf<Int>()
var left = 0
var top = 0
var right = matrix[0].size - 1
var bottom = matrix.size - 1
while (left <= right && top <= bottom) {
for (i in left .. right) {
ret.add(matrix[top][i])
}
for (i in top + 1 .. bottom) {
ret.add(matrix[i][right])
}
if (bottom > top && right > left) {
for (i in right - 1 downTo left) {
ret.add(matrix[bottom][i])
}
for (i in bottom - 1 downTo top + 1) {
ret.add(matrix[i][left])
}
}
left++
top++
bottom--
right--
}
return ret
}
Note: bottom > top && right > left 不能转向的判断
[Greedy]
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
fun canJump(nums: IntArray): Boolean {
if (nums.size == 1) {
return true
}
var barrier = 0
var max = nums[0]
for (i in 0 .. nums.size - 2) {
max = Math.max(max, i + nums[i])
if (barrier == i) {
if (barrier >= max) {
return false
}
barrier = max
}
if (max >= nums.size - 1) {
return true
}
}
return false
}
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
fun merge(intervals: Array<IntArray>): Array<IntArray> {
// for (i in 0 .. intervals.size - 2) {
// for (j in i + 1 .. intervals.size - 1) {
// if (intervals[i][0] > intervals[j][0]) {
// val tmp = intervals[i]
// intervals[i] = intervals[j]
// intervals[j] = tmp
// }
// }
// }
val ret = mutableListOf<IntArray>()
fun quickSort(arr: Array<IntArray>, start: Int, end: Int) {
fun swap(arr: Array<IntArray>, i: Int, j: Int) {
val tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
if (start >= end) {
return
}
val mid = (start + end) / 2
swap(arr, mid, start)
val pivot = arr[start]
var last = start
var i = start + 1
while (i <= end) {
if (arr[i][0] < pivot[0]) {
swap(arr, i, ++last)
}
i++
}
swap(arr, last, start)
quickSort(arr, start, last - 1)
quickSort(arr, last + 1, end)
}
quickSort(intervals, 0, intervals.size - 1)
ret.add(intervals[0])
for (i in 1 .. intervals.size - 1) {
if (ret[ret.size - 1][1] >= intervals[i][0]) {
ret[ret.size - 1][0] = Math.min(intervals[i][0], ret[ret.size - 1][0])
ret[ret.size - 1][1] = Math.max(intervals[i][1], ret[ret.size - 1][1])
} else {
ret.add(intervals[i])
}
}
return ret.toTypedArray()
}
Note： 快排快慢指针的运用
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
val newIntervalList = intervals.toMutableList()
var i = 0
while (i <= newIntervalList.size - 1) {
if (newIntervalList[i][0] > newInterval[0]) {
newIntervalList.add(i, newInterval)
break
}
i++
}
if (newIntervalList.size == intervals.size) {
newIntervalList.add(newInterval)
}
val ret = mutableListOf<IntArray>()
ret.add(newIntervalList[0])
for (j in 1 .. newIntervalList.size - 1) {
if (ret[ret.size - 1][1] >= newIntervalList[j][0]) {
ret[ret.size - 1][0] = Math.min(newIntervalList[j][0], ret[ret.size - 1][0])
ret[ret.size - 1][1] = Math.max(newIntervalList[j][1], ret[ret.size - 1][1])
} else {
ret.add(newIntervalList[j])
}
}
return ret.toTypedArray()
}
Given a string s consists of some words separated by spaces, return the length of the last word in the string. If the last word does not exist, return 0.
A word is a maximal substring consisting of non-space characters only.
fun lengthOfLastWord(s: String): Int {
var ret = 0
var end = s.length - 1
//trim tail
while (end >= 0) {
if (s[end] != ' ') {
break
} else {
end--
}
}
while (end >= 0) {
if (s[end] == ' ') {
break
} else {
end--
ret++
}
}
return ret
}
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
fun generateMatrix(n: Int): Array<IntArray> {
val ret = Array(n) { IntArray(n) }
var x = 1
var left = 0
var top = 0
var right = n - 1
var bottom = n - 1
while (top <= bottom && left <= right) {
for (i in left .. right) {
ret[top][i] = x++
}
for (i in top + 1 .. bottom) {
ret[i][right] = x++
}
for (i in right - 1 downTo left) {
ret[bottom][i] = x++
}
for (i in bottom - 1 downTo top + 1) {
ret[i][left] = x++
}
top++
left++
right--
bottom--
}
return ret
}
The set [1, 2, 3, …, n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
fun getPermutation(n: Int, k: Int): String {
val exponents = IntArray(n)
exponents[0] = 1
for (i in 1 .. n - 1) {
exponents[i] = i * exponents[i - 1]
}
val ret = StringBuilder()
val readySelectArr = (1..n).toMutableList()
var k = k - 1
for (i in n downTo 1) {
val cur = k / exponents[i - 1]
ret.append(readySelectArr.removeAt(cur))
k -= cur * exponents[i - 1]
}
return ret.toString()
}
Note: 注意数组下标从0开始，即求k-1个
Given the head of a linked list, rotate the list to the right by k places.
fun rotateRight(head: ListNode?, k: Int): ListNode? {
if (head?.next == null) {
return head
}
var size = 0
var tmp = head
while (tmp != null) {
tmp = tmp.next
size++
}
val dummyHead = ListNode(0)
dummyHead.next = head
var n = k % size
while (n > 0) {
var cur = dummyHead.next
var curNext = cur?.next
while (curNext?.next != null) {
cur = cur?.next
curNext = curNext.next
}
cur?.next = null
curNext?.next = dummyHead.next
dummyHead.next = curNext
n--
}
return dummyHead.next
}
//way 2:
fun rotateRight(head: ListNode?, k: Int): ListNode? {
if (head?.next == null) {
return head
}
var size = 1
var iter = head
while (iter?.next != null) {
iter = iter.next
size++
}
iter?.next = head// tail
var pre = size - k % size
iter = head
while (pre > 1) {
iter = iter?.next
pre --
}
val ret = iter?.next
iter?.next = null
return ret
}
Note: 利用求余数的方法得到有效的的旋转次数。 way 2 闭合环遍历断开
[Dynamic Programing]
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
fun uniquePaths(m: Int, n: Int): Int {
val dp = IntArray(n)
for (i in 0..n - 1) {
dp[i] = 1
}
for (i in 1..m - 1) {
for (j in 1..n - 1) {
dp[j] = dp[j - 1] + dp[j]
}
}
return dp[n - 1]
}
Note: 回溯，递归超时; 滚动数组优化空间
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and space is marked as 1 and 0 respectively in the grid.
fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
val m = obstacleGrid.size
val n = obstacleGrid[0].size
if (obstacleGrid[m - 1][n - 1] == 1) {
return 0
}
val dp = IntArray(n) { 0 }
for (i in 0..n - 1) {
if (obstacleGrid[0][i] == 1) {
break
}
dp[i] = 1
}
for (i in 1 .. m - 1) {
for (j in 0 .. n - 1) {
if (j == 0) {
if (obstacleGrid[i][0] == 1) {
dp[j] = 0
}
} else {
val part1 = if(obstacleGrid[i][j] == 1) 0 else dp[j]
val part2 = if(obstacleGrid[i][j] == 1) 0 else dp[j - 1]
dp[j] = part1 + part2
}
}
}
return dp[n - 1]
}
Note：状态压缩
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
fun minPathSum(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val dp = IntArray(n)
dp[0] = grid[0][0]
for (i in 1..n - 1) {
dp[i] = grid[0][i] + dp[i - 1]
}
for (i in 1..m - 1) {
for (j in 0..n - 1) {
if (j == 0) {
dp[j] = grid[i][j] + dp[j]
} else {
dp[j] = grid[i][j] + Math.min(dp[j - 1], dp[j])
}
}
}
return dp[n - 1]
}
[String | FSM]
A valid number can be split up into these components (in order):
A decimal number or an integer.
(Optional) An 'e' or 'E', followed by an integer.
A decimal number can be split up into these components (in order):
(Optional) A sign character (either '+' or '-').
One of the following formats:
At least one digit, followed by a dot '.'.
At least one digit, followed by a dot '.', followed by at least one digit.
A dot '.', followed by at least one digit.
An integer can be split up into these components (in order):
(Optional) A sign character (either '+' or '-').
At least one digit.
For example, all the following are valid numbers: [“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”], while the following are not valid numbers: [“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”].
Given a string s, return true if s is a valid number.
data class ContextData(var decimal: Boolean, var exponential: Boolean)
enum class StateMachine {
INVALID {
override fun next(c: Char, context: ContextData): StateMachine {
TODO("Not yet implemented")
}
},
START {
override fun next(c: Char, context: ContextData): StateMachine {
if ((c == '+' || c == '-')) {
return INTEGER
} else if (c.isDigit()) {
context.decimal = true
return INTEGER
} else if (c == '.') {
return FRACTION
} else {
return INVALID
}
}
},
INTEGER {
override fun next(c: Char, context: ContextData): StateMachine {
if (c.isDigit()) {
context.decimal = true
return this
} else if (c == '.') {
return FRACTION
} else if (c == 'e' || c == 'E') {
context.exponential = false
return E_SIGN
} else {
return INVALID
}
}
},
FRACTION {
override fun next(c: Char, context: ContextData): StateMachine {
if (c.isDigit()) {
context.decimal = true
return this
} else if (c == 'e' || c == 'E') {
context.exponential = false
return E_SIGN
} else {
return INVALID
}
}
},
E_SIGN {
override fun next(c: Char, context: ContextData): StateMachine {
if (!context.decimal) {
return INVALID
}
if (c == '+' || c == '-') {
context.exponential = false
return E_INTEGER
} else if (c.isDigit()){
context.exponential = true
return E_INTEGER
} else {
return INVALID
}
}
},
E_INTEGER {
override fun next(c: Char, context: ContextData): StateMachine {
if (!context.decimal) {
return INVALID
} else if (c.isDigit()) {
context.exponential = true
return this
} else {
return INVALID
}
}
};
abstract fun next(c: Char, context: ContextData): StateMachine
}
fun isNumber(s: String): Boolean {
val context = ContextData(false, true)
var stateMachine = StateMachine.START
for (c in s) {
stateMachine = stateMachine.next(c, context)
if (stateMachine == StateMachine.INVALID) {
return false
}
}
return context.decimal && context.exponential
}
[Array]
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
fun plusOne(digits: IntArray): IntArray {
var carry = 1
for (i in digits.size - 1 downTo 0) {
if (carry == 0) {
break
}
val add = digits[i] + carry
digits[i] = add % 10
carry = add / 10
}
if (carry == 1) {
return IntArray(digits.size + 1){
if (it == 0) {
1
} else {
0
}
}
} else {
return digits
}
}
Given two binary strings a and b, return their sum as a binary string.
fun addBinary(a: String, b: String): String {
val ret = StringBuilder()
var ia = a.length - 1
var ib = b.length - 1
var carry = '0'
while (true) {
val ca = if (ia >= 0) a[ia--] else '0'
val cb = if (ib >= 0) b[ib--] else '0'
if (ca == cb) {
if (ca == '0') {
ret.append(carry)
carry = '0'
} else {
ret.append(carry)
carry = '1'
}
} else {
if (carry == '1') {
ret.append('0')
} else {
ret.append('1')
}
}
if (ia < 0 && ib < 0) {
if (carry == '1') {
ret.append('1')
}
break
}
}
return ret.reverse().toString()
}
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
Note:
fun fullJustify(words: Array<String>, maxWidth: Int): List<String> {
fun appendBlankChars(builder: StringBuilder, n: Int) {
for (i in 1..n) {
builder.append(" ")
}
}
fun processLine(startIndex: Int, endIndex: Int): String {
var totalBlankLen = 0
for (i in startIndex..endIndex) {
totalBlankLen += words[i].length
}
totalBlankLen = maxWidth - totalBlankLen
val intervals = endIndex - startIndex
val lineStr = StringBuilder()
if (intervals == 0) {
lineStr.append(words[startIndex])
appendBlankChars(lineStr, maxWidth - lineStr.length)
} else {
val blanksOfInterval = IntArray(intervals)
var i = 0
while (totalBlankLen > 0) {
blanksOfInterval[i]++
i++
if (i == blanksOfInterval.size) {
i = 0
}
totalBlankLen--
}
var j = 0
for (i in startIndex..endIndex) {
lineStr.append(words[i])
if (i != endIndex) {
appendBlankChars(lineStr, blanksOfInterval[j++])
}
}
}
return lineStr.toString()
}
val ret = mutableListOf<String>()
var curLineWidth = 0
var startWordIndex = 0
var endWordIndex = 0
for (wordIndex in 0..words.size - 1) {
curLineWidth = curLineWidth + words[wordIndex].length
if (curLineWidth == maxWidth) {
endWordIndex = wordIndex
ret.add(processLine(startWordIndex, endWordIndex))
curLineWidth = 0
startWordIndex = endWordIndex + 1
} else if (curLineWidth < maxWidth) {
curLineWidth++
continue
} else { //curLineWidth > maxWidth
endWordIndex = wordIndex - 1
ret.add(processLine(startWordIndex, endWordIndex))
startWordIndex = wordIndex
curLineWidth = words[startWordIndex].length + 1
}
}
if (startWordIndex <= words.size - 1) {
val lineStr = StringBuilder()
for (i in startWordIndex..words.size - 1) {
lineStr.append(words[i])
if (i != words.size - 1) {
lineStr.append(" ")
}
}
appendBlankChars(lineStr, maxWidth - lineStr.length)
ret.add(lineStr.toString())
}
return ret
}
Given a non-negative integer x, compute and return the square root of x.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
fun mySqrt(x: Int): Int {
var startVal = 1
var endVal = x
while (startVal <= endVal) {
val mid = startVal + (endVal - startVal) / 2
if (mid > Int.MAX_VALUE / mid) {
endVal = mid - 1
continue
}
val v = mid * mid
if (v == x) {
return mid
} else if (v > x) {
endVal = mid - 1
} else {
startVal = mid + 1
}
}
return endVal
}
Note: 防止溢出操作
[Dynamic Progroming]
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
fun climbStairs(n: Int): Int {
var first = 1
var second = 1
for (i in 2 .. n) {
val tmp = first
first += second
second = tmp
}
return first
}
Given a string path, which is an absolute path (starting with a slash ‘/‘) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.
In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e. ‘//‘) are treated as a single slash ‘/‘. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.
The canonical path should have the following format:
Return the simplified canonical path.
enum class PathState {
INIT,
SlashStart,
DotStart,
DotEnd,
CHAR
}
fun simplifyPath(path: String): String {
var curSlashStart = 0
var state = PathState.INIT
val stack = LinkedList<String>()
for ((index, c) in path.withIndex()) {
if (c == '/') {
if (state == PathState.INIT) {
curSlashStart = index
state = PathState.SlashStart
} else if (state == PathState.DotStart) {
state = PathState.SlashStart
curSlashStart = index
} else if (state == PathState.DotEnd) {
if (!stack.isEmpty()) {
stack.pop()
}
state = PathState.SlashStart
curSlashStart = index
} else if (state == PathState.CHAR) {
stack.push(path.substring(curSlashStart + 1..index - 1))
curSlashStart = index
state = PathState.SlashStart
} else if (state == PathState.SlashStart) {
curSlashStart = index
}
} else if (c == '.') {
if (state == PathState.SlashStart) {
state = PathState.DotStart
} else if (state == PathState.DotStart) {
state = PathState.DotEnd
} else if (state == PathState.DotEnd) {
state = PathState.CHAR
}
} else {
state = PathState.CHAR
}
}
if (state == PathState.DotEnd) {
if (stack.isNotEmpty()) {
stack.pop()
}
} else if (state == PathState.CHAR) {
stack.push(path.substring(curSlashStart + 1..path.length - 1))
}
val ret = StringBuilder()
ret.append("/")
while (stack.isNotEmpty()) {
ret.append(stack.removeLast())
ret.append("/")
}
if (ret.length > 1) {
ret.deleteCharAt(ret.length - 1)
}
return ret.toString()
}
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
fun minDistance(word1: String, word2: String): Int {
val A = word1.length
val B = word2.length
if (A * B == 0) {
return A + B
}
val dp = Array(A + 1) { IntArray(B + 1) }
for (i in 0 .. A) {
dp[i][0] = i
}
for (i in 0 .. B) {
dp[0][i] = i
}
for (i in 1 .. A) {
for (j in 1 ..B) {
dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j])
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i][j])
}
}
}
return dp[A][B]
}
Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
Follow up:
fun setZeroes(matrix: Array<IntArray>): Unit {
val m = matrix.size
val n = matrix[0].size
var row0Zero = false
var col0Zero = false
for (i in 0..m - 1) {
if (matrix[i][0] == 0) {
col0Zero = true
break
}
}
for (i in 0..n - 1) {
if (matrix[0][i] == 0) {
row0Zero = true
break
}
}
for (i in 1..m - 1) {
for (j in 1..n - 1) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0
matrix[i][0] = 0
}
}
}
for (i in 1..m - 1) {
for (j in 1..n - 1) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0
}
}
}
if (col0Zero) {
for (i in 0..m - 1) {
matrix[i][0] = 0
}
}
if (row0Zero) {
for (i in 0..n - 1) {
matrix[0][i] = 0
}
}
}
Note: O(1)空间
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
val m = matrix.size
val n = matrix[0].size
var start = 0
var end = m * n - 1
while (start <= end) {
val mid = (start + end) / 2
val midVal = matrix[mid / n][mid % n]
if (target == midVal) {
return true
} else if (target > midVal) {
start = mid + 1
} else {
end = mid - 1
}
}
return false
}
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
//counter sort
fun sortColors(nums: IntArray): Unit {
val counter = IntArray(3)
for (v in nums) {
counter[v]++
}
var i = 0
for ((index, c) in counter.withIndex()) {
for (ci in 1..c) {
nums[i++] = index
}
}
}
//two pointer
fun sortColors(nums: IntArray): Unit {
fun swap(i: Int, j: Int) {
val tmp = nums[i]
nums[i] = nums[j]
nums[j] = tmp
}
var left = 0
var right = nums.size - 1
var i = 0
while (i <= right) {
if (nums[i] == 0) {
swap(i, left)
left++
} else if (nums[i] == 2) {
swap(i, right)
right--
if (nums[i] != 1) {
i--
}
}
i++
}
}
[Sliding Window | Hash Table | Two Pointers]
Given two strings s and t, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string “”.
Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in s.
fun minWindow(s: String, t: String): String {
val tMap = mutableMapOf<Char, Int>()
for (c in t) {
tMap[c] = tMap.getOrDefault(c, 0) + 1
}
var found = false
var minStartIndex = 0
var minEndIndex = s.length - 1
var startIndex = 0
var endIndex = 0
var count = t.length
while (endIndex < s.length) {
val endEntryCnt = tMap.get(s[endIndex])
if (endEntryCnt != null) {
tMap.put(s[endIndex], endEntryCnt - 1)
if (endEntryCnt > 0) {
count--
}
}
while (count == 0) {
found = true
if (endIndex - startIndex < minEndIndex - minStartIndex) {
minStartIndex = startIndex
minEndIndex = endIndex
}
val startEntryCnt = tMap.get(s[startIndex])
if (startEntryCnt != null) {
tMap.put(s[startIndex], startEntryCnt + 1)
if (startEntryCnt + 1 > 0) {
count++
}
}
startIndex++
}
endIndex++
}
return if (found) s.substring(minStartIndex..minEndIndex) else ""
}
Note: 注意t会有重复的子串
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
You may return the answer in any order.
val ret8 = mutableListOf<List<Int>>()
fun combine(n: Int, k: Int): List<List<Int>> {
combineRecur(n, 1, k, mutableListOf())
return ret8
}
fun combineRecur(n: Int, start:Int, k: Int, path: MutableList<Int>){
if (k == 0) {
ret8.add(ArrayList(path))
return
}
for (i in start..n) {
path.add(i)
combineRecur(n, i + 1, k - 1, path)
path.removeAt(path.size - 1)
}
}
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
val ret10 = mutableListOf<List<Int>>()
fun subsets(nums: IntArray): List<List<Int>> {
subsetsRecur(nums, 0, mutableListOf())
return ret10
}
fun subsetsRecur(nums: IntArray, start: Int, path: MutableList<Int>) {
ret10.add(ArrayList(path))
if (start == nums.size || path.size == nums.size) {
return
}
for (i in start..nums.size - 1) {
path.add(nums[i])
subsetsRecur(nums, i + 1, path)
path.removeAt(path.size - 1)
}
}
Given an m x n grid of characters board and a string word, return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
fun exist(board: Array<CharArray>, word: String): Boolean {
val visited = Array(board.size){BooleanArray(board[0].size)}
for (i in 0..board.size - 1) {
for (j in 0..board[0].size - 1) {
if (existRecur(i, j, board, word, 0, visited)) {
return true
}
}
}
return false
}
fun existRecur(i: Int, j:Int, board: Array<CharArray>, word: String, wordCur: Int, visited: Array<BooleanArray>): Boolean {
if (i < 0 || i > board.size - 1 || j < 0 || j > board[0].size - 1 || visited[i][j] ||board[i][j] != word[wordCur]) {
return false
}
visited[i][j] = true
if (wordCur == word.length - 1) {
return true
}
if (existRecur(i, j - 1, board, word, wordCur + 1, visited)) {
return true
}
if (existRecur(i, j + 1, board, word, wordCur + 1, visited)) {
return true
}
if (existRecur(i - 1, j, board, word, wordCur + 1, visited)) {
return true
}
if (existRecur(i + 1, j, board, word, wordCur + 1, visited)) {
return true
}
visited[i][j] = false
return false
}
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.
Clarification:
Confused why the returned value is an integer, but your answer is an array?
Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
fun removeDuplicates(nums: IntArray): Int {
if (nums.size <= 2) {
return 2
}
nums.sort()
var slow = 2
for (fast in 2..nums.size - 1) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast]
slow++
}
}
return slow
}
Note: 移动慢指针条件； 和慢指针前两个元素对比
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
fun search(nums: IntArray, target: Int): Boolean {
var start = 0
var end = nums.size - 1
while (start <= end) {
val mid = (start + end) / 2
if (nums[mid] == target) {
return true
} else {
if (nums[mid] == nums[start] && nums[mid] == nums[end]) {
start++
end--
} else if (nums[mid] <= nums[end]) {//right sorted
if (target > nums[mid] && target <= nums[end]) {
start = mid + 1
} else {
end = mid - 1
}
} else if (nums[mid] >= nums[start]) {//left sorted
if (target >= nums[start] && target < nums[mid]) {
end = mid - 1
} else {
start = mid + 1
}
}
}
}
return false
}
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
fun deleteDuplicates(head: ListNode?): ListNode? {
val dummyNode = ListNode(0, head)
var pre = dummyNode
var cur = head
while (cur != null) {
if (cur.`val` == cur.next?.`val`) {
var tmp = cur
while (tmp != null && tmp.`val` == tmp.next?.`val`) {
tmp = tmp.next
}
cur = tmp?.next
pre.next = cur
} else {
pre = cur
cur = cur.next
}
}
return dummyNode.next
}
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
fun deleteDuplicates(head: ListNode?): ListNode? {
var cur = head
while (cur?.next != null) {
if (cur.`val` == cur.next?.`val`) {
cur.next = cur.next?.next
} else {
cur = cur.next
}
}
return head
}
!!!先跳过Hard….
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
fun partition(head: ListNode?, x: Int): ListNode? {
val dummyHeadLeft = ListNode(0)
var curLeft = dummyHeadLeft
val dummyHeadRight = ListNode(0)
var curRight = dummyHeadRight
var cur = head
while (cur != null) {
if (cur.`val` < x) {
curLeft.next = cur
curLeft = cur
} else{
curRight.next = cur
curRight = cur
}
cur = cur.next
}
//merge two list
curRight.next = null
curLeft.next = dummyHeadRight.next
return dummyHeadLeft.next
}
Note: 注意出现循环链表
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.
fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
if (n <=0) {
return
}
var cur = nums1.size - 1
var p1 = m - 1
var p2 = n - 1
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[cur--] = nums1[p1--]
} else {
nums1[cur--] = nums2[p2--]
}
}
while (p2 >= 0) {
nums1[cur--] = nums2[p2--]
}
}
The gray code is a binary numeral system where two successive values differ in only one bit.
Given an integer n representing the total number of bits in the code, return any sequence of gray code.
A gray code sequence must begin with 0.
val grayCodeRet = mutableListOf<Int>()
fun grayCode(n: Int): List<Int> {
val path = StringBuilder()
grayCodeRecur(0, n, true, path)
path.deleteCharAt(path.length - 1)
grayCodeRecur(1, n, false, path)
//println(grayCodeRet)
return grayCodeRet
}
fun grayCodeRecur(cur: Int, n: Int, left: Boolean, path: StringBuilder) {
path.append(cur)
if (path.length >= n) {
grayCodeRet.add(Integer.parseInt(path.toString(), 2))
return
}
if (left) {
grayCodeRecur(0, n, true, path)
path.deleteCharAt(path.length - 1)
grayCodeRecur(1, n, false, path)
path.deleteCharAt(path.length - 1)
} else {
grayCodeRecur(1, n, true, path)
path.deleteCharAt(path.length - 1)
grayCodeRecur(0, n, false, path)
path.deleteCharAt(path.length - 1)
}
}
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
val ret11 = mutableListOf<List<Int>>()
fun subsetsWithDup(nums: IntArray): List<List<Int>> {
nums.sort()
subsetsWithDupRecur(nums, 0, mutableListOf())
return ret11
}
fun subsetsWithDupRecur(nums: IntArray, start: Int, path: MutableList<Int>) {
ret11.add(ArrayList(path))
if (start >= nums.size) {
return
}
for (i in start..nums.size - 1) {
if (i > start && nums[i] == nums[i - 1]) {
continue
}
path.add(nums[i])
subsetsWithDupRecur(nums, i + 1, path)
path.removeAt(path.size - 1)
}
}
A message containing letters from A-Z can be encoded into numbers using the following mapping:
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:
"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.
Given a string s containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
fun numDecodings(s: String): Int {
val dp = IntArray(s.length + 1)
dp[0] = 1
for (i in 0..s.length - 1) {
if (s[i] != '0') {
dp[i + 1] = dp[i]
}
if (i > 0 && s[i - 1] != '0' && ((s[i - 1] - '0') * 10 + (s[i] - '0')) <= 26) {
dp[i + 1] += dp[i - 1]
}
}
return dp[s.length]
}
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
val dummyHead = ListNode(0)
dummyHead.next = head
var cur = head
var i = 1
var before: ListNode? = null
while (i < left) {
before = cur
cur = cur?.next
i++
}
val rangeTail = cur
var after = cur
var pre: ListNode? = null
while (cur != null && i <= right) {
val next = cur.next
cur.next = pre
pre = cur
cur = next
i++
after = next
}
val rangeHead = pre
before?.next = rangeHead
rangeTail?.next = after
if (before == null) {
return rangeHead
} else {
return dummyHead.next
}
}
Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.
A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses and “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses.
val ret = mutableListOf<String>()
fun restoreIpAddresses(s: String): List<String> {
restoreIpAddressesRecur(s, 0, mutableListOf())
return ret
}
fun restoreIpAddressesRecur(s: String, start: Int, path: MutableList<String>) {
if (path.size == 4 && start == s.length) {
val builder = StringBuilder()
for (it in path) {
builder.append(it).append('.')
}
builder.deleteCharAt(builder.length - 1)
ret.add(builder.toString())
return
}
for (i in start .. s.length - 1) {
if (path.size == 3 && (s.length - 1 - start) > 3) {
break
}
if (i - start > 0 && s[start] == '0') {
break
}
val item = s.subSequence(start .. i).toString()
if (Integer.parseInt(item) > 255) {
break
}
path.add(item)
restoreIpAddressesRecur(s, i + 1, path)
path.removeAt(path.size - 1)
}
}
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
//递归
fun inorderTraversal(root: TreeNode?): List<Int> {
val ret = mutableListOf<Int>()
inorderTraversalRecur(root, ret)
return ret
}
fun inorderTraversalRecur(node: TreeNode?, path: MutableList<Int>) {
if (node == null) {
return
}
inorderTraversalRecur(node.left, path)
path.add(node.`val`)
inorderTraversalRecur(node.right, path)
}
//迭代
fun inorderTraversal(root: TreeNode?): List<Int> {
val ret = mutableListOf<Int>()
val stack: Deque<TreeNode> = LinkedList<TreeNode>()
var cur = root
while (cur != null || stack.isNotEmpty()) {
while (cur != null) {
stack.push(cur)
cur = cur.left
}
cur = stack.pop()
ret.add(cur.`val`)
cur = cur.right
}
return ret
}
Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
fun generateTrees(n: Int): List<TreeNode?> {
return generateTreesInternal(IntArray(n) {
it + 1
}, 0, n - 1)
}
fun generateTreesInternal(arr: IntArray, start: Int, end: Int): List<TreeNode?> {
val ret = mutableListOf<TreeNode?>()
if (start > end) {
ret.add(null)
return ret
}
for (i in start..end) {
val leftTrees = generateTreesInternal(arr, start, i - 1)
val rightTrees = generateTreesInternal(arr, i + 1, end)
for (left in leftTrees) {
for (right in rightTrees) {
val root = TreeNode(arr[i])
root.left = left
root.right = right
ret.add(root)
}
}
}
return ret
}
Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.
//Divide Conquer
fun numTrees(n: Int): Int {
return numTreesRecur(1, n)
}
fun numTreesRecur(start: Int, end: Int) : Int{
var ret = 0
if (start > end) {
return 1
}
for (i in start..end) {
val leftNum = numTreesRecur(start, i - 1)
val rightNum = numTreesRecur(i + 1, end)
ret += leftNum * rightNum
}
return ret
}
//Dynamic Programing
fun numTrees(n: Int): Int {
val G = IntArray(n + 1)
G[0] = 1
G[1] = 1
for (i in 2 .. n) {
for (k in 1..i) {
G[i] += G[k - 1] * G [i - k]
}
}
return G[n]
}
Note: DP的状态转移方程可以从分治推导出来
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:
Note: a + b is the concatenation of strings a and b.
//递归超时.....:
fun isInterleave(s1: String, s2: String, s3: String): Boolean {
return isInterleave(s1, s1.length - 1, s2, s2.length - 1, s3, s3.length - 1)
}
fun isInterleave(s1: String, i1: Int, s2: String, i2: Int, s3: String, i3: Int): Boolean {
if (i1 < 0 && i2 < 0 && i3 < 0) {
return true
}
if (i1 >=0 && i3 >= 0 && s1[i1] == s3[i3] && isInterleave(s1, i1 - 1, s2, i2, s3, i3 - 1)) {
return true
} else if (i2 >= 0 && i3 >= 0 && s2[i2] == s3[i3] && isInterleave(s1, i1, s2, i2 - 1, s3, i3 - 1)) {
return true
} else {
return false
}
}
//DP:
fun isInterleave(s1: String, s2: String, s3: String): Boolean {
if (s1.length + s2.length != s3.length) {
return false
}
val dp = Array(s1.length + 1) {BooleanArray(s2.length + 1)}
dp[0][0] = true
for (i in 0 .. s1.length) {
for (j in 0 .. s2.length) {
if (i > 0 && s3[i + j - 1] == s1[i - 1] && dp[i - 1][j]) {
dp[i][j] = true
}
if (j > 0 && s3[i + j - 1] == s2[j - 1] && dp[i][j - 1]) {
dp[i][j] = true
}
}
}
return dp[s1.length][s2.length]
}
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
//递归：
var pre: Int? = null
fun isValidBST(root: TreeNode?): Boolean {
if (root == null) {
return true
}
if (!isValidBST(root.left)) {
return false
}
println(root.`val`)
if (pre != null && root.`val` <= pre!!) {
return false
} else {
pre = root.`val`
return isValidBST(root.right)
}
}
//迭代
fun isValidBST(root: TreeNode?): Boolean {
var pre: Int? = null
val stack = LinkedList<TreeNode>()
var cur = root
while (cur != null || stack.isNotEmpty()) {
while (cur != null) {
stack.push(cur)
cur = cur.left
}
val top = stack.pop()
if (pre != null && top.`val` <= pre) {
return false
} else {
pre = top.`val`
}
cur = top.right
}
return true
}
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
if (p?.`val` != q?.`val`) {
return false
}
if (p == null && q == null) {
return true
}
return isSameTree(p?.left, q?.left) && isSameTree(p?.right, q?.right)
}