yunshuipiao / rice-noodles Goto Github PK

View Code? Open in Web Editor NEW

2.0 2.0 0.0 53 KB

solve leetcode with different language

License: Apache License 2.0

Kotlin 100.00%

algorithm kotlin leetcode

rice-noodles's People

Contributors

Stargazers

Watchers

rice-noodles's Issues

28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

解法

最简单的字符串匹配，直接看代码，注意边界条件。

import org.testng.annotations.Test

fun strStr(haystack: String, needle: String): Int {
    if (needle.isEmpty()) {
        return 0
    }
    var result = -1
    val len = needle.length
    for (index in 0 until haystack.length) {
        if ((index + len) <= haystack.length &&
            haystack.substring(index, index + len) == needle
        ) {
            return index
        }
    }
    return result
}

fun strStr2(haystack: String, needle: String): Int {
    for (i in 0 until Int.MAX_VALUE) {
        for (j in 0 until Int.MAX_VALUE) {
            if (j == needle.length) {
                return i
            }
            if (i + j == haystack.length) {
                return -1
            }
            if (haystack[i + j] != needle[j]) {
                break
            }
        }
    }
    return -1
}

@Test
fun _0028() {
    arrayListOf(arrayListOf("hello", "ll")).forEach {
        println(strStr2(it[0], it[1]))
    }
}

14. Longest Common Prefix

Easy

1334

1283

Favorite

Share
Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.

解法

import org.testng.annotations.Test

fun longestCommonPrefix(strs: Array<String>): String {
    var result = ""
    if (strs.isEmpty()) {
        return result
    }
    var index = 0
    while (index < strs[0].length) {
        for (i in 1 until strs.size) {
            if (index >= strs[i].length || strs[0][index] != strs[i][index]) {
                return result
            }
        }
        result += strs[0][index]
        index += 1
    }
    return result
}


@Test
fun _0014() {
    val strs = arrayListOf("flower").toTypedArray()
    println(longestCommonPrefix(strs))
}

15.3Sum

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.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解法：

题目不难，主要在于边界条件的检查。

首先将数组排序，少于3个值的直接返回空；

然后固定第一个数，用头尾指针结合 sum 进行判断；

这里说一点，因为要求无重复结果，所以出现过的情况可以不在重复判断。

代码如下：

import org.testng.annotations.Test

fun threeSum(nums: IntArray): List<List<Int>> {

    val result = arrayListOf<ArrayList<Int>>()
    val tempNums = nums
    if (tempNums.size < 3) {
        return result
    }
    tempNums.sort()
    for (index in 0..tempNums.size - 3) {
        // 出去重复结果
        if (index - 1 >= 0 && tempNums[index - 1] == tempNums[index]) {
            continue
        }
        var l = index + 1
        var r = tempNums.size - 1
        while (l < r) {
            val sum = tempNums[index] + tempNums[l] + tempNums[r]
            if (sum > 0) {
                do {
                    r -= 1
                } while (r > l && tempNums[r] == tempNums[r + 1])
            } else if (sum < 0) {
                do {
                    l += 1
                } while (r > l && tempNums[l] == tempNums[l - 1])
            } else {
                result.add(arrayListOf(tempNums[index], tempNums[l], tempNums[r]))
                do {
                    r -= 1
                } while (r > l && tempNums[r] == tempNums[r + 1])
                do {
                    l += 1
                } while (r > l && tempNums[l] == tempNums[l - 1])
            }
        }
    }
    return result
}


@Test
fun _0015() {
    arrayListOf(intArrayOf(-2, 0, 1, 1, 2)).forEach {
        println(threeSum(it))
    }
}

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

解法一

fun swapPairs(head: ListNode?): ListNode? {
    val newHead = ListNode(0)
    newHead.next = head
    var temp: ListNode? = newHead
    while (temp?.next != null && temp.next?.next != null) {
        val node1 = temp.next
        temp.next = temp.next?.next
        node1?.next = temp.next?.next
        temp.next?.next = node1

        temp = temp.next?.next
    }
    return newHead.next
}

解法二

递归解法

/**
 * 递归方法
 */
fun swapPairs2(head: ListNode?): ListNode? {
    if (head?.next == null) {
        return head
    }
    val temp = head.next
    head.next = swapPairs2(head.next?.next) // important
    temp?.next = head
    return temp
}

19.Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

题目分析：删除列表中的倒数第 n 个结点，其中 n 总是有效的，不超过链表长度。

解法

很容易想到用双指针，一快一慢，找到要删除结点的前一个结点。不过还是有问题，有技巧。

技巧如下：

链表问题，首先新建一个额外的头结点，方便后续操作

newHead = ListHead(0), newHead.next = head

找到要删除结点的前一个结点

node.next = node.next.next
分析，要删除倒数第 n 个结点，那么要找的结点为倒数 n + 1 个。

首先使用快指针先走 n + 1 步；使两指针之前相差 n + 1; 然后快慢指针同时向前，当快指针到链表末尾时，慢指针刚好在倒数 n + 1 的位置。

比如 [1, 2, 3, 4, 5], 新建头结点。[0 ,1, 2, 3, 4, 5]。两个指针分别位于 0 处。

快指针先走 n + 1 步到 3 的位置；然后慢指针以同速度往前走。当快指针的结点为空时，慢指针刚好到 3 的位置，删除 4 结点。

同时针对头结点，当 n = 5 时，快指针前进 6 步为空，即 newHead 为要找的点；

当 n = 1, 同样可以得出结果。

import model.ListNode
import org.testng.annotations.Test

class ListNode(var `val`: Int) {
    var next: ListNode? = null

    fun forEach(f: ((String) -> Unit) = ::print) {
        f("${this.`val`}")
        var node: ListNode? = this.next
        while (node != null) {
            f(" --> ${node.`val`}")
            node = node.next
        }
        println()
    }
}

/**
 * 借助一个新的头结点，来省去判断当删除的结点为头结点的情况
 *
 * 找到要删除结点的前一个结点
 */
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val newHead: ListNode? = ListNode(0)
    var first = newHead
    var second = newHead
    newHead?.next = head
    for (index in 0..n) {
        first = first?.next
    }
    while (first != null) {
        first = first.next
        second = second?.next
    }
    second?.next = second?.next?.next
    return newHead?.next
}

@Test
fun _0019() {
    var head: ListNode? = ListNode(1)
    var tHead = head
    for (n in 2..5) {
        val node = ListNode(n)
        tHead?.next = node
        tHead = tHead?.next
    }
    arrayListOf(head).forEach {
        removeNthFromEnd(head, 2)?.forEach()
    }
}

fun removeNthFromEnd2(head: ListNode?, n: Int): ListNode? {
    var first = head
    var second = head
    var num = n
    while ( num > 0) {
        first = first?.next
        num -= 1
    }
    // 最重要的一句，意味着删除的是头结点
    if (first == null) {
        return head?.next
    }
    while (first?.next != null) {
        first = first.next
        second = second?.next
    }
    second?.next = second?.next?.next
    return head
}

25. Reverse Nodes in k-Group

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.


**Example:**

Given this linked list: `1->2->3->4->5`

For *k* = 2, you should return: `2->1->4->3->5`

For *k* = 3, you should return: `3->2->1->4->5`

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

解法一

递归解法

fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    var curr = head
    var tHead = head
    var count = 0
    while (curr != null && count != k) {
        curr = curr.next
        count += 1
    }
    if (count == k) {
        curr = reverseKGroup(curr, k) //递归反转后面的结点
        while (count > 0) {  // 反转前 k 个结点
            val tmp = tHead?.next
            tHead?.next = curr
            curr = tHead
            tHead = tmp
            count -= 1
        }
        tHead = curr
    }
    return tHead
}

解法二

由于要求 O(1) 的空间，因此不能使用递归。

采用一次遍历，遇到 k 个结点逐次反转。理解不难，但是代码细节多。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 *
 *----------------------------
 *prev
 *tail   head
 *dummy   1    2    3   4    5
 *----------------------------
 *prev   head      tail
 *dummy   1    2    3   4    5
 *       cur
 *----------------------------
 * 每次让prev.next的元素插入到当前tail之后,这样tail不断前移,被挪动的元素头插入tail之后的链表
 *prev        tail head
 *dummy   2    3    1   4    5
 *       cur
 *----------------------------
 *prev   tail      head
 *dummy   3    2    1   4    5
 *       cur
 *----------------------------
 *                 prev
 *                 tail
 *                 head
 *dummy   3    2    1   4    5
 *----------------------------
 *                 prev  head     tail
 *dummy   3    2    1     4    5  null
 *----------------------------
 */
fun reverseKGroup2(head: ListNode?, k: Int): ListNode? {
    val dummy: ListNode? = ListNode(0)
    dummy?.next = head

    var tHead = head
    var prev = dummy
    var tail = dummy
    var cur: ListNode?= null
    var n = 0
    while (true) {
        n = k
        while (n > 0 && tail != null) {
            tail = tail.next
            n -= 1
        }
        if (tail == null) {
            break
        }
        tHead = prev?.next
        while (prev?.next != tail) {  // 反转 prev.next 和 tail 之间的元素
            cur = prev?.next
            prev?.next = cur?.next
            cur?.next =  tail.next
            tail.next = cur
        }
        tail = tHead
        prev = tHead
    }
    return dummy?.next
}

附：反转链表的两种方法

fun reverse(head: ListNode?): ListNode? {
    val newHead = ListNode(0)
    var temp: ListNode? = head
    while (temp != null) {
        val node = temp
        temp = temp.next
        node.next = newHead.next
        newHead.next = node
    }
    return newHead.next
}

fun reverse2(head: ListNode?): ListNode? {
    if (head?.next == null) {
        return head
    }
    val newHead = reverse2(head.next)
    head.next?.next = head
    head.next = null
    return newHead
}

13. Roman to Integer

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, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven 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:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

解法：使用map保存

import org.testng.annotations.Test

fun romanToInt(s: String): Int {
    var result = 0
    if (s.isEmpty()) {
        return 0
    }
    val map = hashMapOf(
        'M' to 1000,
        'D' to 500, 'C' to 100, 'L' to 50, 'X' to 10, 'V' to 5, 'I' to 1
    )
    result = map[s[0]] ?: 0
    for (i in 1 until s.length) {
        var cur = map[s[i]] ?: 0
        var before = map[s[i - 1]] ?: 0
        if (cur > before) {
            result += cur - 2 * before
        } else {
            result += cur
        }
    }
    return result
}


@Test
fun _0013() {
    arrayListOf("III", "IV", "IX", "LVIII", "MCMXCIV").forEach {
        println(romanToInt(it))
    }
}

11.Container With Most Water

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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

解法一：暴力搜索

解法二：双指针法

不难理解，两高度之间的水量有下标差 * 两高度的较小值。

那么可以使用头尾两个指针，计算出当前水量和目前水量比较，取较大值。

然后再取两高度中的较小值，向左或者向右移动下标。

解释一下：

水量取决于两高度的较小值，如果移动较大值，水量只可能会减少；

而选择移动较小值下标，宽度较少，而高度可能增加，因此增加水量。

import org.testng.annotations.Test

fun maxArea(height: IntArray): Int {
    if (height.size < 2) {
        return 0
    }
    var l = 0
    var r = height.size - 1
    var result = 0
    while (l <= r) {
        val tempR = (r - l) * Math.min(height[r], height[l])
        result = Math.max(tempR, result)
        if (height[l] < height[r]) {
            l += 1
        } else {
            r -= 1
        }
    }
    return result
}

@Test
fun _0011() {
    val height = intArrayOf(1,9,6,2,5,4,8,3,7)
    arrayListOf(height).forEach {
        println(maxArea(it))
    }
}

16. 3Sum Closest

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.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解法

与上一题的方法相同，不过这题判断更为简单，绝对值为0 就返回。

特别注意下标合法性的判断

import org.testng.annotations.Test

fun threeSumClosest(nums: IntArray, target: Int): Int {
    var result = 0
    if (nums.size < 3) {
        return 0
    }
    var tempNums = nums
    tempNums.sort()
    result += tempNums[0] + tempNums[1] + tempNums[2]
    for (index in 0..tempNums.size - 3) {
        var l = index + 1
        var r = tempNums.size - 1
        while (l < r) {
            val tempResult = tempNums[index] + tempNums[l] + tempNums[r]
            if (tempResult > target) {
                r -= 1
            } else if (tempResult < target) {
                l += 1
            } else {
                return tempResult
            }
            if (Math.abs(tempResult - target) <= Math.abs(result - target)) {
                result = tempResult
            }
        }
    }
    return result
}


@Test
fun _0016() {
    arrayListOf(intArrayOf(1, 1, -1, -1, 3)).forEach {
        println(threeSumClosest(it, 1))
    }
}

26.Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once 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.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

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 modification to the input array will be known to the caller as well.

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]);
}

题目意思：取出排序数组中的重复元素，要求空间在 O(1)，返回不重复的元素的个数。

注意最后的题目意思，要求返回的 len 长度中就是不重复的元素。

解法

很简单，遍历的过程中，遇到不一样的元素就将其赋值到前面的位置。

直接看代码：

import org.testng.annotations.Test

fun removeDuplicates(nums: IntArray): Int {
    if (nums.isEmpty()) {
        return 0
    }
    var result = 0
    for (index in 0 until nums.size) {
        if (nums[index] != nums[result]) {
            result += 1
            nums[result] = nums[index]
        }
    }
    return result + 1
}


@Test
fun _0026() {
    arrayListOf(intArrayOf(0,0,1,1,1,2,2,3,3,4)).forEach {
        println(removeDuplicates(it))
    }
}

27. Remove Element

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.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.
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 modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// 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]);
}

解法

和上一题一样，也是在遍历过程中将满足条件的值往前复制即可。

import org.testng.annotations.Test

fun removeElement(nums: IntArray, `val`: Int): Int {
    if (nums.isEmpty()) {
        return 0
    }
    var result = 0
    for (index in 0 until nums.size) {
       if (nums[index] != `val`) {
           nums[result] = nums[index]
           result += 1
       }
    }
    return result
}


@Test
fun _0027() {
    arrayListOf(intArrayOf(0,1,2,2,3,0,4,2)).forEach {
        println(removeElement(it, 2))
    }
}

1: Two Sum

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

kotlin

20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true
Example 3:

Input: "(]"
Output: false
Example 4:

Input: "([)]"
Output: false
Example 5:

Input: "{[]}"
Output: true

解法

简单题目，借助栈来保存即可。要注意有亮点：

当前字符必须和栈顶字符匹配
假设字符为 "( { [ [ } )", 栈中保存的为 "[ [ "。因此最后需要判断栈是否为空。

fun isValid(s: String): Boolean {
    val map = hashMapOf('(' to ')', '{' to '}', '[' to ']')
    val result = ArrayList<Char>()
    for (c in s) {
        println(c)
        if (c in map.keys) {
            result.add(c)
        } else {
            if (result.isEmpty() || map[result.last()] != c) {
                return false
            } else {
                result.removeAt(result.size - 1)
            }
        }
    }
    return result.isEmpty()
}

17 Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

解法一: 常规解法

算是一种组合问题

不难理解，首先拿出一个数字，组成列表；比如 "23"，拿出"2" ，组成 [a, b, c]

然后第二个数字，讲前列表分别加载下一个数字的字母，组成新的列表；比如 3，组成 3 * 3个列表，直到全部数字遍历完。

/**
 * 常规解法
 */
fun letterCombinations(digits: String): List<String> {
    val map = hashMapOf(
        "2" to "abc",
        "3" to "def",
        "4" to "ghi",
        "5" to "jkl",
        "6" to "mno",
        "7" to "pqrs",
        "8" to "tuv",
        "9" to "wxyz"
    )
    val tempResult = arrayListOf<String>()
    val result = arrayListOf<String>()
    if (digits.isBlank()) return tempResult
    var tempDigits = digits
    do {
        val digit = tempDigits[0].toString()
        if (result.isEmpty()) {
            map[digit]?.forEach { c ->
                tempResult.add("$c")
            }
        } else {
            result.forEach { s ->
                map[digit]?.forEach { c ->
                    tempResult.add("$s$c")
                }
            }
        }
        result.clear()
        result.addAll(tempResult)
        tempResult.clear()
        tempDigits = tempDigits.substring(1, tempDigits.length)
    } while (tempDigits.isNotBlank())
    return result
}

解法二：递归解法

在解法一的基础上，实现递归解法，代码几乎是一样的，用于尝试去了解递归。

fun letterCombinations2(digits: String): List<String> {
    val map = hashMapOf(
        "2" to "abc",
        "3" to "def",
        "4" to "ghi",
        "5" to "jkl",
        "6" to "mno",
        "7" to "pqrs",
        "8" to "tuv",
        "9" to "wxyz"
    )
    val result = arrayListOf<String>()
    if (digits.isBlank()) {
        return result
    }
    return letterComRecursion(result, digits, map)
}

fun letterComRecursion(
    result: ArrayList<String>,
    digits: String,
    map: HashMap<String, String>
): List<String> {
    if (digits.isBlank()) {
        return result
    }
    val tempResult = arrayListOf<String>()
    tempResult.addAll(result)
    result.clear()
    if (tempResult.isEmpty()) {
        map[digits[0].toString()]?.forEach {
            result.add("$it")
        }
    } else {
        tempResult.forEach { s ->
            map[digits[0].toString()]?.forEach { c ->
                result.add("$s$c")
            }
        }
    }
    return letterComRecursion(result, digits.substring(1, digits.length), map)
}

@Test
fun _0017() {
    arrayListOf("235").forEach {
        println(letterCombinations2(it))
    }
}

9. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true
Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:

Coud you solve it without converting the integer to a string?

看代码即可

29. Divide Two Integers

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.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

解法

这道题目主要在于越界的判断。

计算除法结果可以用减法来代替

需要注意的是：Int.MIN_VALUE 计算绝对值时，防止溢出，结果为本身。

/**
 * Returns the absolute value of an {@code int} value.
 * If the argument is not negative, the argument is returned.
 * If the argument is negative, the negation of the argument is returned.
 *
 * <p>Note that if the argument is equal to the value of
 * {@link Integer#MIN_VALUE}, the most negative representable
 * {@code int} value, the result is that same value, which is
 * negative.
 *
 * @param   a   the argument whose absolute value is to be determined
 * @return  the absolute value of the argument.
 */
public static int abs(int a) {
    return (a < 0) ? -a : a;

import org.testng.annotations.Test

fun divide(dividend: Int, divisor: Int): Int {
    // 当除数为 Int.MIN_VALUE)
    if (dividend == Int.MIN_VALUE){
        // 此结果越界
        if (divisor == -1) {
            return Int.MAX_VALUE
        }
        if (divisor == 1) {
            return Int.MIN_VALUE
        }
        // 这种情况较为特殊，这里的处理是当除数为 Int.MIN_VALUE, 取除数为Int.MAX_VALUE, 2 为被除数是结果加1。
        if (divisor == 2) {
            return -(divide(Int.MAX_VALUE, divisor) + 1)
        }
        if (divisor == Int.MIN_VALUE) {
            return 1
        }
    }
    // 当除数为 Int.MIN_VALUE)
    if (divisor == Int.MIN_VALUE) {
        return 0
    }
    var result = 0
    var d1 = Math.abs(dividend)
    // 除数为Int.MIN_VALUE， 取为 Int.MAX_VALUE
    if (d1 == Int.MIN_VALUE) {
        d1 = Int.MAX_VALUE
    }
    val d2 = Math.abs(divisor)
    println("$d1, $d2")
    val flag = (dividend > 0).xor(divisor > 0)
    while (d1 >= d2) { // 优化
        d1 -= d2
        result += 1
    }
    if (flag) {
        return -result
    }
    return result
}

@Test
fun _0029() {
    arrayListOf(arrayListOf(Int.MIN_VALUE, 3)).forEach {
        println(divide(it[0], it[1]))
    }
}

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解法

回溯法，可以解决背包，排列等相关问题

直接看代码分析，插入打印代码方便理解

import org.testng.annotations.Test

fun generateParenthesis(n: Int): List<String> {
    val result = arrayListOf<String>()
    backtracking(result, "", 0, 0, n)
    return result.toList()
}

fun backtracking(result: ArrayList<String>, s: String, open: Int, close: Int, max: Int) {
    println(s)
    if (s.length == 2 * max) {
        result.add(s)
        println("----")
        return
    }
    if (open < max) {
        backtracking(result, "$s(", open + 1, close, max)
    }
    if (close < open) {
        backtracking(result, "$s)", open ,close + 1, max)
    }
}


@Test
fun _0022() {
    arrayListOf(3).forEach {
        println(generateParenthesis(it))
    }
}

10.Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

解法：前10个题最难的一题

尝试过进行字符串匹配，情况太多，不容易考虑完。
解法参考一招解决4道leetcode hard题，动态规划在字符串匹配问题中的应用, 使用动态规划，空间换时间。

理解题目要求的情况下，实现简单的正则匹配：
一张二维表格，遍历 pattern 字符串，看以当前字符串为终点是否能够匹配；
比如对于 s = "aabb", p = "a*b*" 来说，构建二维数组；

	""	a	a	b	b
""	1	0	0	0	0
a	0	1	0	0	0
*	1	1	1	0	0
b	0	0	0	1	0
*	1	1	1
如上图，`dp[j][i]` 就表示 p(0, j) 和 s(0, i) 是否匹配。匹配为1，否则为0.

可以对上面的表格一行一行的填满：

首先第一行表示空字符串能否匹配 s ,除了 dp(0 ,0) 为1，其余都为 0.

而第一列表示 p 能否匹配字符串：注意 * 可以表示出现0次。

那么对于剩下的部分：

假设需要求 dp[j][i]=1, 那么当 p[j - 1] == '*', 需要满足下面两种情况：

dp[j - 2][i] == 1 , 此时 x* 表示空串。（x 表示 a-z 中的字符）
看前一个字符 p[j - 2], 如果 p[j - 2] == s[i - 1] 并且之前的结果匹配成功 dp[j][i - 1] == 1, 匹配成功；

或者 p[j - 2] == '.' 并且之前的结果匹配成功 dp[j][i - 1] == 1, 匹配成功；

当 p[j - 1] == s[ i - 1] 或者 p[j - 1] 两种情况都比较好判断。

看代码：

import model.printTwoDimenArray
import org.testng.annotations.Test

/**
 * 字符串匹配 dp 问题: 放弃
 * Regular Expression Matching
 */
fun isMatch(s: String, p: String): Boolean {
    val dp = Array(p.length + 1){Array(s.length + 1) {false}}
    dp[0][0] = true
    // 第0行和第0列分别表示空字符和对应字符串的匹配
    for (i in 1..p.length) {
        // p 的第一个字符为*， 则无法匹配
        if (i > 1 && p[i - 1] == '*') {
            dp[i][0] = dp[i - 2][0]
        }
    }
    for (i in 1..s.length) {
        for (j in 1..p.length) {
            if (p[j - 1] == '*') {
                dp[j][i] = dp[j - 2][i] || (p[j - 2] == s[i - 1] || p[j - 2] == '.') && dp[j][i - 1]
            }
            if (p[j - 1] == s[i - 1]) {
                dp[j][i] = dp[j - 1][i - 1]
            }
            if (p[j - 1] == '.') {
                dp[j][i] = dp[j - 1][i - 1]
            }
        }
    }
    printTwoDimenArray(dp)
    return dp[p.length][s.length]
}

@Test
fun _0010() {
    val s = "aabb"
    val p = "a*b*"
    val result = isMatch(s, p)
    println(result)
}

3. Longest Substring Without Repeating Characters

[TOC]

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解法一：使用额外列表保存中间结果

遍历字符串，求出以当前字符为终点的满足条件的字符串，与当前结果比较，取最大者。

代码如下：

/**
 * 注意空格, 空格也算一个字符
 * 空间复杂度 O(n), 时间复杂度O(n*n)
 */
fun lengthOfLongestSubstring(s: String): Int {
    var result = 0
    if (s.isEmpty()) {
        return 0
    }
    val l = arrayListOf<Char>()
    for (index in 0 until s.length) {
        l.clear()
        for (i in index downTo 0) {
            val findIndex = l.indexOf(s[i])
          	// 没找到重复字符串
            if (findIndex != -1) {
                break
            } else {
                l.add(0, s[i])
            }
        }
        if (l.size > result) {
            result = l.size
        }
    }
    return result
}

解法二：优化

使用一个 tempStr 来保存当前最长的无重复子串，比第一种解法更容易理解.

/**
 * 注意空格
 * 空间复杂度 O(n), 时间复杂度O(n*n)
 */
fun lengthOfLongestSubstring(s: String): Int {
    var result = 0
    var tempStr = ""
    for (index in 0 until s.length) {
        val i = tempStr.indexOf(s[index])
        if (i != -1) {
            // 当前中有重复元素
            tempStr = tempStr.substring(i + 1) + s[index]
        } else {
            tempStr += s[index]
        }
        result = Math.max(tempStr.length, result)

    }
    return result
}

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解法

简单题目，对结点进行判断，小的加入新的结点链表中，往后移动即可。

这里注意当长度不一样，其中一个结点为 null 的处理。

另一种时递归解法

import model.ListNode
import org.testng.annotations.Test

fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    var newHead = ListNode(0)
    var node: ListNode? = newHead
    var tl1 = l1
    var tl2 = l2
    while (tl1 != null && tl2 != null) {
        if (tl1.`val` < tl2.`val`) {
            node?.next = tl1
            tl1 = tl1.next
        } else {
            node?.next = tl2
            tl2 = tl2.next
        }
        node = node?.next
    }
    if (tl1 == null) {
        node?.next = tl2
    }
    if (tl2 == null) {
        node?.next = tl1
    }
    return newHead.next
}

// 递归解法
fun mergeTwoLists2(l1: ListNode?, l2: ListNode?): ListNode? {
    if (l1 == null) {
        return l2
    }
    if (l2 == null) {
        return l1
    }
    if (l1.`val` < l2.`val`) {
        l1.next = mergeTwoLists2(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists2(l1, l2.next)
        return l2
    }
}


@Test
fun _0021() {
    var head: ListNode? = ListNode(1)
    var tHead = head
    for (n in 2..5) {
        val node = ListNode(n)
        tHead?.next = node
        tHead = tHead?.next
    }
    var head2: ListNode? = ListNode(1)
//    tHead = head2
//    for (n in 2..5) {
//        val node = ListNode(n)
//        tHead?.next = node
//        tHead = tHead?.next
//    }
    mergeTwoLists2(head, head2)?.forEach()
}

12.Integer to Roman

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

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

解法一

将可能的结果表示出来，包括4， 9，等。

然后用给定的数字判断大小，依次减去当前的最大数字，配合移动下标。代码如下：

import org.testng.annotations.Test

fun intToRoman(num: Int): String {
    var result = ""
    var tempNum = num
    if (tempNum < 1 || tempNum > 3999) {
        return result
    }
    val intArray = arrayListOf(
        1000, 900, 500, 400, 100,
        90, 50, 40, 10, 9, 5, 4, 1
    )
    val romanArray = arrayListOf(
        "M", "CM", "D", "CD", "C",
        "XC", "L", "XL", "X", "IX", "V", "IV", "I"
    )
    var index = 0
    while (tempNum > 0 && index < intArray.size) {
        if (tempNum >= intArray[index]) {
            tempNum -= intArray[index]
            result += romanArray[index]
        } else {
            index += 1
        }
    }
    return result

}

fun intToRoman2(num: Int): String {
    val M = arrayListOf("", "M", "MM", "MMM")
    val C = arrayListOf("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM")
    val X = arrayListOf("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC")
    val I = arrayListOf("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX")
    return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] + I[num % 10]
}


@Test
fun _0012() {
    arrayListOf(3, 4, 9, 58, 1994).forEach {
        println(intToRoman2(it))
    }
}

解法二：理解题目意思

在解法一的基础上，充分理解题目，分别将可能的千，百，十，个位表示出来进行计算。

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题解

这题难度为 hard，我思考了一天做不出来，因此参考了star 数目最高的答案，下面就贴一下该解法，学习其**，还要考虑各种边界条件。kotlin 代码见 _0004.kt 文件。解法如下：

为了解决这个问题，首先需要明白中位数是什么概念：一组数据分为两组，其中一组总是比另一组小。

Wiki：对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，则中位数不唯一，通常取最中间的两个数值的平均数作为中位数。

针对此题来说，用随机的 i 将 A 分为两部分，注意 i 的位置；

  left_A（i 个）          |        right_A （m - i 个）
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

因为 A 有 m 个元素，因此一共有 m + 1 中分割的方法。当 i = 0，左边为空；

B 也是一样分割方法：

 left_B                  |        right_B
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

此时将两个部分合并在一起：

  left_part              |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

此时思考，怎么找到满足题解的答案：

既然求中位数，因此只需要确认：

1.len(left_part) == len(left_right)
2.max(left_part) <= min(left_right)

两个条件，就可以把 A，B 分为长度相等两部分，此时 median = (max(left_part) + min(left_right))/2

上述就是针对中位数作出的分析。

详细步骤

为了确认上述两个条件，只需要确认：

1. i + j = m - i + n - j, 可以得到 i，j 的关系
  所以 i = 0～m， j = (m + n) / 2 - i (n >= m)
2 A[i - 1] <= B[j] && B[j - 1] <= A[i]: 保证左边始终比右边小

这里解释一下为什么需要 n >= m, 因为在算式中，j = (m + n) / 2 - i 可能会取到负值，导致结果错误；

上述的 A[i-1],B[j-1],A[i],B[j] 即使在 i=0/i=m/j=0/j=n 条件下也成立，后续解释。

因此问题就变为二分查找：

在 [0, m] 找到满足条件的 i，使得 B[j - 1] <= A[i] && A[i - 1] <= B[j], (j =(m + n) / 2 - i )

步骤如下：

1. low =0， high = m, 在[low, high] 中进行查找。
2. 令 i = low + (high - low) / 2, j = (m + n)  / 2 - i;
3. 这时，肯定满足 len(left) == len(right)， 此时会遇到三种情况：
   - B[j - 1] <= A[i] && A[i - 1] <= B[j], 这就是需要找的情况；
   - B[j - i] > A[i] ,说明左边还存在数大于右边， i 需要增加，使得 B[j - 1] <= A[i];
     Low = i + 1
   - A[i - 1] >= B[j]， 同样说明说明左边还存在数大于右边， 需要减小 A[i - 1] 的值来满足条件， i 需要减小；
     high = i - 1
4. 更新完 low, high， 继续进行二分查找；

当需要的 i 值找到，中位数即可得出：

当（m + n ）% 2 == 1 : median =( max(B[j - 1], A[i - 1]) + min(B[j], A[i]) )/ 2
当（m + n ）% 2 == 0: median = min(A[i], B[j])。

举个例子：

当 A = [1, 2, 3 ,4], B = [2, 3], 时，i = 2, j = 1, left = [1, 2, 2], right = [3, 3, 4], median = 2.5

当 A = [1, 2, 3, 4], B = [2 ,3, 4] i = 2 , j = 1 left = [1, 2, 2], right = [3, 3, 4, 4], median = min(A[i], B[j]) = 3

这里的 j = (m + n) / 2 - i，当为偶数时，平均分配；当为奇数是，右边比左边多一个，且右边最小值为中位数。

这时来考虑一下边界条件：

当 i=0,i=m,j=0,j=n 值 A[i-1],B[j-1],A[i],B[j] 不存在，那怎么防止程序崩溃。

目的是找打值满足 max(left_part) <= min(left_right)。

如果 i, j 都不是边界值(意味着 A[i-1],B[j-1],A[i],B[j] 都存在有效)，那么需要确认 B[j-1] <= A[i] && A[i-1] <= B[j]。如果 A[i-1],B[j-1],A[i],B[j] 不存在，那么就没必要去确认上述两个条件；比如，i = 0, A[i - 1] 不存在，因此没必要去确认 A[ i - 1] <= B[j]. 因此，只需要确认：

 (j == 0 or i == m or B[j-1] <= A[i]) and (i == 0 or j == n or A[i-1] <= B[j])

因此在二分查找的循环中，只需要判断以下条件：

<a> (j == 0 or i == m or B[j-1] <= A[i]) and
    (i == 0 or j = n or A[i-1] <= B[j])
    找到需要的 i 值

<b> j > 0 and i < m and B[j - 1] > A[i]
    i 太小，需要增加，但不能超过 m
    
<c> i > 0 and j < n and A[i - 1] > B[j]
    i 太大，需要较少，但要大于 0， 等于0 则进行 a 条件判断

上述条件中，因为 i < m, j = (m+n+1)/2 - i > (m+n+1)/2 - m >= (2*m+1)/2 - m >= 0，因此可以不用判断 j > 0; c 条件同上；

上述三个条件互斥，因此先判断后续两个条件即可。

Accepted

Runtime: 240 ms, faster than 100.00% of Kotlin online submissions for Median of Two Sorted Arrays.

Memory Usage: 44.1 MB, less than 66.67% of Kotlin online submissions for Median of Two Sorted Arrays.

import org.testng.annotations.Test

fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    val m = nums1.size
    val n = nums2.size
    if (m > n) {
        return findMedianSortedArrays(nums2, nums1)
    }
    var low = 0
    var high = m
    while (low <= high) {
        // 针对 nums1 进行 二分查找
        val i = low + (high - low).shr(1)
        val j = (m + n).shr(1) - i

        if (i < m && nums2[j - 1] > nums1[i]) {
            low = i + 1
        } else if (i > 0 && nums1[i - 1] > nums2[j]) {
            high = i - 1
        } else {
            // 找到想要的 i 值
            println(i)
            var minRight = 0
            minRight = when {
                i == m -> nums2[j]
                j == n -> nums1[i]
                else -> Math.min(nums1[i], nums2[j])
            }
            if ((m + n) % 2 == 1) {
                return minRight * 1.0
            }
            var maxLeft = 0
            maxLeft = when {
                i == 0 -> nums2[j - 1]
                j == 0 -> nums1[i - 1]
                else -> Math.max(nums1[i - 1], nums2[j - 1])
            }
            return 0.5 * (maxLeft + minRight)


//            var maxLeft = 0
//            maxLeft = when {
//                i == 0 -> nums2[j - 1]
//                j == 0 -> nums1[i - 1]
//                else -> Math.max(nums1[i - 1], nums2[j - 1])
//            }
//            if ((m + n) % 2 == 1) {
//                return maxLeft * 1.0
//            }
//            // 偶数逻辑
//            var minRight = 0
//            minRight = when {
//                i == m -> nums2[j]
//                j == n -> nums1[i]
//                else -> Math.min(nums1[i], nums2[j])
//            }
//            return 0.5 * (maxLeft + minRight)
        }
    }
    return 0.0
}

fun findMedianSortArray(nums1: ArrayList<Int>): Double {
    val m = nums1.size
    if (m == 0) {
        return 0.0
    }
    val low = 0
    val high = m
    val mid = low + (high - low).shr(1)
    if (m % 2 == 0) {
        return 0.5 * (nums1[mid] + nums1[mid - 1])
    } else {
        return nums1[mid] * 1.0
    }
}

@Test
fun _0004() {
    // 10    2 4 6 8 9
    val nums1 = IntArray(5)
    nums1[0] = 1
    nums1[1] = 2
    nums1[2] = 3
    nums1[3] = 4
    nums1[4] = 5
    val nums2 = IntArray(1)
    nums2[0] = 3
    val result = findMedianSortedArrays(nums1, nums2)
//    val result = findMedianSortArray(arrayListOf(1, 2))
    print(result)
}

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321
Example 2:

Input: -123
Output: -321
Example 3:

Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

解法一：陷阱多多

很简单的容易想到如下代码：

fun reverse(x: Int): Int {
    var result: Int = 0
    var tempx = x
        result = result * 10 + (tempx % 10)
        tempx /= 10
    }
    return result
}

由于题目要求，最大只能使用32位整数，所以使用 Long 型保存的方法都不能用。
很容易想到如下判断代码来进行溢出判断（分正负数）

result * 10 + (temp % 10) < Int.MAX_VALUE

但是但是，不能这样判断：因为 result * 10 可能会溢出， result * 10 + (temp % 10) 可能也会溢出
所以必须使用 result > (Int.MAX_VALUE - (tempx % 10) / 10) 保证每一次原子运算都不会溢出(正)，负数同样如此处理

全部代码如下：

/**
 *  7. Reverse Integer
 *  // 只可以使用32位数据 [-2^32, 2^32 - 1]
 */

fun reverse(x: Int): Int {
    var result: Int = 0
    var tempx = x
    val symbol = if (tempx >= 0) 1 else -1
    while (tempx != 0) {
        // 对每一次可能溢出进行判断
        if (result  > (Int.MAX_VALUE  - (tempx % 10) ) / 10 && symbol == 1) {
            println("-")
            return 0
        }
        if (result < (Int.MIN_VALUE - (tempx % 10) ) / 10 && symbol == -1 ) {
            println("--")
            return 0
        }
        result = result * 10 + (tempx % 10)
        tempx /= 10
    }
    return result
}

解法二（最完美解法）

在解法一第一步的结果下，result = result * 10 + (tempx % 10) 结果溢出，那么按照相同方法计算得到的结果肯定不一样，判断如下：

fun reverse2(x: Int): Int {
    var result: Int = 0
    var tempx: Int = x
    while (tempx != 0) {

        val newResult = result * 10 + (tempx % 10)
        // 如果不溢出，那么结果必然一样
        if (result !=  (newResult - tempx % 10 ) / 10 ) {
            return 0
        }

        result = newResult
        tempx /= 10
    }
    return result
}

18. 4Sum

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.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解法一

之前做了三个数的和，那么对于四个数的和，就是很简单了。

可以理解为 index 后面三个数的和为 target - nums[index]，转化为3个数的和。

由此可以推广到 N 个数的和。

import org.testng.annotations.Test

/**
 * 常规解法
 */

fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
    val result = arrayListOf<ArrayList<Int>>()
    if (nums.size < 4) {
        return result
    }
    nums.sort()
    var index = 0
    while (index < nums.size) {
        if (index > 0 && nums[index] == nums[index - 1]) {
        } else {
            val tempNums = nums.filterIndexed { i, v -> i > index }.toIntArray()
            val tResult = threeSum(tempNums, target - nums[index])
            tResult.forEach {
                val l = it as ArrayList
                l.add(nums[index])
                result.add(l)
            }
        }
        index += 1
    }
    return result
}


fun threeSum(nums: IntArray, target: Int): List<List<Int>> {

    val result = arrayListOf<ArrayList<Int>>()
    val tempNums = nums
    if (tempNums.size < 3) {
        return result
    }
    tempNums.sort()
    for (index in 0..tempNums.size - 3) {
        if (index - 1 >= 0 && tempNums[index - 1] == tempNums[index]) {
            continue
        }
        var l = index + 1
        var r = tempNums.size - 1
        while (l < r) {
            val sum = tempNums[index] + tempNums[l] + tempNums[r]
            if (sum > target) {
                do {
                    r -= 1
                } while (r > l && tempNums[r] == tempNums[r + 1])
            } else if (sum < target) {
                do {
                    l += 1
                } while (r > l && tempNums[l] == tempNums[l - 1])
            } else {
                result.add(arrayListOf(tempNums[index], tempNums[l], tempNums[r]))
                do {
                    r -= 1
                } while (r > l && tempNums[r] == tempNums[r + 1])
                do {
                    l += 1
                } while (r > l && tempNums[l] == tempNums[l - 1])
            }
        }
    }
    return result
}

@Test
fun _0018() {
    arrayListOf(intArrayOf(-1,-5,-5,-3,2,5,0,4)).forEach {
        fourSum(it, -7).forEach {
            println(it)
        }
    }
}

解法二

这里不借助三数和的结果，直接从 N 个数求解，参考该题解决方法的最高赞数的答案

核心**是从 Nsum 通过递归降低到 2sum来求解。

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

分析：求字符串的最长回文子串(连续)

此题大概有4种解法：

a. 暴力求解

求出所有子串，判断是不是回文串，并取长度最大者。

分析：

长度为1: n 个

长度为2: n - 1 个

….

长度为n, 1 个，共计 n( n + 1) / 2，乘上回文串的判断n，时间复杂度为 O(n^3)

fun isPalindrome(s: String): Boolean {
    var l = 0
    var r = s.length - 1
    while (l <= r) {
        if (s[l] != s[r]) {
            return false
        }
        l += 1
        r -= 1
    }
    return true
}

b. 最长公共子串

此题目可以演变为将 s 反转，求两个字符串的最长公共子串。

比如 abcdcb, 反转字符串为 bcdcba, 最长公共子串为 bcdcb, 即结果。

这时可使用动态规划，使用一个二维数组来记录， map[i][j]表示 s 和 s1 两个字符串在 s[0, i] 和 s1[0, j] 两个字符串的最长公共子串。

   b  c  d  c  d  a
a  0  0  0  0  0  1  
b  1  0  0  0  1  0  
c  0  2  0  1  0  0  
d  0  0  3  0  0  0  
c  0  1  0  4  0  0  
b  1  0  0  0  5  0

上述就是求的的二维数组，在 O(n^2) 的时间复杂度得到 map 的值, 当 map[i][j] 的值大于当前结果的长度时，保存当前结果。比如上述的 map[5][4] 的值最大，即可得到结果。

result = s.subString(i - map[5][4] + 1, i + 1)

fun longCommonSubString(s: String): String {
    if (s.isBlank()) {
        return s
    }
    var result = ""
    val rs = s.reversed()
    val map = Array(s.length) { Array(s.length) { 0 } }
    for (i in 0 until s.length) {
        for (j in 0 until rs.length) {
            if (s[i] == rs[j]) {
              // 边界条件
                if (i - 1 < 0 || j - 1 < 0) {
                    map[i][j] = 1
                } else {
                    map[i][j] = map[i - 1][j - 1] + 1
                }
            } else {
                map[i][j] = 0
            }
            if (map[i][j] > result.length) {
                val temp = s.substring(i - map[i][j] + 1, i + 1)
              	// 得出最长结果，判断回文串
                if (isPalindrome(temp)) {
                    result = temp
                }
            }
        }
    }
    return result
}

注意

还有一种情况， aacdefdcaa 字符串，由于其反转字符串与其的最长公共子串为 aac, 不满足条件。

由于 aac 的反转字符串也在其中，所以在上面的过程中，保存当前结果之前，还有判断当前是不是回文串。

时间复杂度 O(n^3), 空间复杂度 O(n^2)

c. 动态规划

由于回文串的性质，由于 s[i] == s[j] 并且 s[i + 1, j + 1] 是回文串，那么 s[i, j] 也是回文串。

所以可以使用一个二维数组来记录， map[i][j] , 表示 s[i, j] 是不是回文串。

1  0  0  0  0  0  
0  1  0  0  0  1  
0  0  1  0  1  0  
0  0  0  1  0  0  
0  0  1  0  1  0  
0  1  0  0  0  1

是得出的二维数组，对角线表示当前字符，为回文串。

map[1][5] 为1，表示 s[1, 5] 是回文串。取最大值即可。

时间复杂度为 O(n^2)

fun dp(s: String): String {
    if (s.isBlank()) {
        return s
    }
    var result = ""
    val map = Array(s.length) { Array(s.length) { 0 } }
    for (i in 0 until map.size) {
        for (j in 0 until map[0].size) {
            if (s[j] == s[i]) {
                if (i - j <= 1) {
                    map[j][i] = 1
                } else if (map[j + 1][i - 1] == 1) {
                    map[j][i] = 1
                }
            }
            if (map[j][i] == 1 && i - j + 1 >= result.length) {
                result = s.substring(j, i + 1)
            }
        }
    }
    return result
}

d. 最佳判断法

根据回文串的性质，遍历字符串，分别求 s[i] 为中心点，s[i, j] 为中心点的字符串的最长子回文串。

比如 abcdcb:

a 为中心点：结果为 a

ab 为中心点，结果为 ""

...

d 为中心点，结果 bcdcb；

dc 为中心点，结果 ""；

fun bestMethod(s: String): String {
    if (s.isBlank()) {
        return s
    }
    var result = ""
    for (i in 0 until s.length) {
       // 以 s[i] 为中心进行计算
        val len1 = getPalindromeLen(s, i, i)
        if (len1 >= result.length) {
            result = s.substring(i - len1 / 2, i + len1 / 2 + 1)
        }
      	// 以 s[i，j] 为中心进行计算
        val len2 = getPalindromeLen(s, i, i + 1)
        if (len2 >= result.length) {
            result = s.substring(i - len2 / 2 + 1, i + len2 / 2 + 1)
        }
    }
    return result
}

/**
 * 判断回文串, 并返回最大长度
 */
fun getPalindromeLen(s: String, i: Int, j: Int): Int {
    var l = i
    var r = j
    while (l >= 0 && r < s.length) {
        if (s[l] == s[r]) {
            l -= 1
            r += 1
        } else {
            break
        }
    }
    return r - l - 1
}

Test code

@Test
fun _0005() {
//    var str = "aacdefdcaa"
    var str = "abcdcb"
    val result = dp(str)
    println(result)
}

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

解法一

可以每两个链表进行排序，得到最后结果

解法二

使用归并排序的**。

/**
 * 典型的归并排序的应用
 */
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    if (lists.isEmpty()) {
        return null
    }
    return mergeKLists(lists, 0, lists.size - 1)
}

fun mergeKLists(list: Array<ListNode?>, left: Int, right: Int): ListNode? {
    if (left == right) {
        return list[left]
    }
    val mid = left + (right - left) / 2
    val node1 = mergeKLists(list, left, mid)
    val node2 = mergeKLists(list, mid + 1, right)
    return mergeTwoLists(node1, node2)
}

解法三

使用优先队列实现，利用最小堆的**

/**
 * 使用优先队列，最小堆实现
 */
fun mergeKLists2(lists: Array<ListNode?>): ListNode? {
    val newHead = ListNode(0)
    var temp: ListNode? = newHead

    val p = PriorityQueue<ListNode>(Comparator<ListNode> { o1, o2 ->
        when {
            o1.`val` < o2.`val` -> -1
            o1.`val` == o2.`val` -> 0
            else -> 1
        }
    })
    lists.forEach {
        if (it != null) {
            p.add(it)
        }
    }
    while (p.isNotEmpty()) {
        val node = p.poll()
        temp?.next = node
        temp = temp?.next

        if (node.next != null) {
            p.add(node.next)
        }
    }
    return newHead.next
}


@Test
fun _0023() {
    val node1 = arrayListOf(1, 4, 5).toListNode()
    val node2 = arrayListOf(3, 3, 4).toListNode()
    val node3 = arrayListOf(2, 6).toListNode()
    val lists = arrayOf(node1, node2, null)
    mergeKLists2(lists)?.forEach()
}

6. ZigZag Conversion

[TOC]

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);
Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

解法一

使用 numRows 个列表，遍历字符串分别进行保存，最后统一打印。

Time: O(n); Space : O(n)

解法二：找规律

首先将字符串分组，比如上述的字符串可以分为三组，求出每一组的个数，然后计算下标打印

P     | I    | N
A   L | S  I | G
Y A   | H R
P     | I

求每一组的个数：每列 numRows 个，减去第一行和最后一行，得到个数；如果为1，则个数为1.

val count = if (numRows == 1) 1 else (2 * numRows - 2)

接着求下标：

首先打印第一行，P 后面为 I，下标为 i + count；最后一行也是一样；

其余行数中间还有元素，比如 A, L; 计算如下：看中间隔了几个元素：

第一行隔了4个元素；

第二行隔了2个元素；

可得下标：

// 非 第一行和 最后一行的 另外的元素下标计算
val index2  = index + (count - 2 * i)

全部代码如下：

import org.testng.annotations.Test

fun convert(s: String, numRows: Int): String {
    if (s.isBlank()) {
        return s
    }
    var result = ""
    // 每一组的字符串
    val count = if (numRows == 1) 1 else (2 * numRows - 2)
    for (i in 0 until numRows) {
        var index = i
        while (index < s.length) {
            result += s[index]

            // 非 第一行和 最后一行的 另外的元素下标计算
            val index2  = index + (count - 2 * i)
            if (i != 0 && i != numRows - 1 && index2 < s.length) {
                result += s[index2]
            }
            index += count
        }
    }
    return result
}

@Test
fun _0006() {
    val s = "PAYPALISHIRING"
    val numRows = 4
    val result = convert(s, numRows)
    println(result)
}

2. Add Two Numbers

Add Two Numbers

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 contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Input: (0) + (7 -> 3)
Output: 7 -> 3 ->
Explanation: 0 + 37 = 37.

注意事项：

链表的操作，循环判断时针对当前节点，而不是 next 节点，思维定式
在任何情况都考虑哨兵(sentinel) 带来的帮助

8. String to Integer (atoi)

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ' ' is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

解答：坑好多

对于这个题目来讲，坑太多。

首先理解题目意思：

一个字符串，若干个空格开头，直到出现字符；

可以选择 - + 字符表示符号，紧着个若干个数字字符；

接着可以跟其他字符或者空格。

因此，对此题的处理顺序如下：

处理空格开头的字符
处理符号字符
处理数字字符
在第三步中判断溢出

代码和注释如下：

import org.testng.annotations.Test

/**
 * 8. String to Integer (atoi)
 * 读懂题目要求，理解清楚题目意思
 *
 */
fun myAtoi(str: String): Int {
    if (str.isBlank()) {
        return 0
    }
    var result: Int = 0
    var symbol = 1
    var index = 0
    // 找到第一个非空字符
    while (str[index] == ' ') {
        index += 1
    }
    // 如果是符号，则后面必然接数字，否则不合法
    if (str[index] == '-' || str[index] == '+') {
        symbol *= if (str[index] == '-') -1 else 1
        index += 1
    }
    // 处理数字字符
    while (index < str.length && str[index] in '0'..'9') {

        val digit = (str[index].toInt() - 48)

        // 判断溢出
        if (result > ( Int.MAX_VALUE - digit) / 10 ) {
            return if (symbol == 1) Integer.MAX_VALUE else Integer.MIN_VALUE
        }
        result = result * 10 + digit
        index += 1
    }
    return result * symbol
}

@Test
fun _0008() {
    val strs = arrayListOf("2147483648", "-2147483649", "  -42")
    strs.forEach {
        println("$it, ${myAtoi(it)}")
    }
}

上面有两个点需要注意：

index 在变化过程中一定要判断合法性
溢出的判断：

result = result * 10 + digit, 计算的过程中可能会溢出：

所以要判断if (result > ( Int.MAX_VALUE - digit) / 10 ) 溢出。

yunshuipiao / rice-noodles Goto Github PK

rice-noodles's People

Contributors

Stargazers

Watchers

rice-noodles's Issues

28. Implement strStr()

解法

14. Longest Common Prefix

解法

15.3Sum

解法：

24. Swap Nodes in Pairs

解法一

解法二

19.Remove Nth Node From End of List

解法

25. Reverse Nodes in k-Group

解法一

解法二

附：反转链表的两种方法

13. Roman to Integer

解法：使用map保存

11.Container With Most Water

解法一：暴力搜索

解法二：双指针法

16. 3Sum Closest

解法

26.Remove Duplicates from Sorted Array

解法

27. Remove Element

解法

1. Two Sum

20. Valid Parentheses

解法

17 Letter Combinations of a Phone Number

解法一: 常规解法

解法二：递归解法

9. Palindrome Number

看代码即可

29. Divide Two Integers

解法

22. Generate Parentheses

解法

10.Regular Expression Matching

解法：前10个题最难的一题

3. Longest Substring Without Repeating Characters

解法一：使用额外列表保存中间结果

解法二： 优化

21. Merge Two Sorted Lists

解法

12.Integer to Roman

解法一

解法二：理解题目意思

4. Median of Two Sorted Arrays

题解

详细步骤

Accepted

7. Reverse Integer

解法一：陷阱多多

解法二（最完美解法）

18. 4Sum

解法一

解法二

5. Longest Palindromic Substring

a. 暴力求解

b. 最长公共子串

c. 动态规划

d. 最佳判断法

Test code

23. Merge k Sorted Lists

解法一

解法二

解法三

6. ZigZag Conversion

解法一

解法二： 找规律

8. String to Integer (atoi)

解答：坑好多

Recommend Projects

解法二：优化

解法二：找规律