LeetCode算法题解答记录，不常更新，随缘维护。

PS：经过几次更新，并非按照LeetCode上的顺序进行解答记录的，各位看官自行摘取需要的内容进行阅读。

1 两数之和

记得面试时是被问到过这个题的，但当时被前面的面试题搞的有些发懵，理解错了“不能重复利用这个数组中同样的元素”这句话的含义，实在惭愧，再看到这道题时一时感慨万千。

问题描述

给定一个整数数组 nums 和一个目标值 target ，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答过程

首先分析下问题：

参数：数组 nums 是一个无序整数数组，元素可重复；target 是一个整数
需求：target是数组中两个元素的和；数组中必有也只有两个元素能满足条件；不能重复利用两个数组中同样的元素
结果：满足需求的两个元素的下标
疑问：未能理解 不能重复利用两个数组中同样的元素 这个要求
思路：两个循环嵌套找出所需元素，返回下标

虽然下面的两次代码都通过了测试，但是没有满足 不能重复利用两个数组中同样的元素 这个条件。
带着疑问我们看了标准答案，发现也是正确答案，不过是占用资源最多的解法，最优解思路确实很妙。

/**
 * 执行用时 : 55 ms, 在Two Sum的Java提交中击败了31.73% 的用户
 * 内存消耗 : 40.3 MB, 在Two Sum的Java提交中击败了0.99% 的用户
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int x = 0;x < nums.length - 1;x++) {
            for (int y = x + 1;y < nums.length;y++) {
                if ((nums[x] + nums[y]) == target) {
                    return new int[] {x, y};
                }
            }
        }
        return null;
    }
}

/**
 * 执行用时 : 49 ms, 在Two Sum的Java提交中击败了37.38% 的用户
 * 内存消耗 : 37.8 MB, 在Two Sum的Java提交中击败了0.99% 的用户
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int y; // 相比上个解法只是减少了y的创建
        for (int x = 0;x < nums.length - 1;x++) {
            for (y = x + 1;y < nums.length;y++) {
                if ((nums[x] + nums[y]) == target) {
                    return new int[] {x, y};
                }
            }
        }
        return null;
    }
}

标准答案

暴力法

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

两遍哈希表

该方法利用了HashMap#containsKey函数，大幅提升了执行效率。

资源占用：
执行用时 : 12 ms, 在Two Sum的Java提交中击败了68.76% 的用户
内存消耗 : 38.7 MB, 在Two Sum的Java提交中击败了0.99% 的用户

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

一遍哈希表

该方法也是利用了HashMap实现，但是原理与两遍哈希表的解法不同，通过将遍历过的元素和元素下标缓存起来，在下个循环判断缓存中是否有本循环元素相加等于目标值，有则返回。妙！

资源占用：
执行用时 : 11 ms, 在Two Sum的Java提交中击败了73.97% 的用户
内存消耗 : 41.2 MB, 在Two Sum的Java提交中击败了0.99% 的用户

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

7 整数反转

问题描述

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

注意：
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解答过程

首先分析下问题：

参数：有符号整数
需求：将数字进行反转
结果：返回反转后的整数
思路：
1. 将整数转化为字符串，取出负数符号
2. 循环字符重新排列
3. 将负数符号和重新排列后的字符进行组合
4. 将组合后的字符串转化为整数
5. 返回整数

/**
 * 执行用时 : 45 ms, 在Reverse Integer的Java提交中击败了48.85% 的用户
 * 内存消耗 : 48.5 MB, 在Reverse Integer的Java提交中击败了0.95% 的用户
 */
class Solution {
    public int reverse(int x) {
        String xStr = String.valueOf(Math.abs(x));
        StringBuilder xrSb = new StringBuilder();
        char[] xCharArray = xStr.toCharArray();
        for (int i = xCharArray.length - 1;i >= 0;i--) {
            xrSb.append(xCharArray[i]);
        }
        try {
            int result = Integer.parseInt(xrSb.toString());
            return x > 0 ? result : -result;
        } catch (Exception e) {

        }
        return 0;
    }
}

标准答案

弹出和推入数字 & 溢出前进行检查

思路

我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。

算法

请原谅我才疏学浅并没有看懂详解。附上链接：整数反转-题解

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

9 回文数

问题描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
进阶：你能不将整数转为字符串来解决这个问题吗？

示例1：

1 2	输入: 121 输出: true

示例2：

1 2	输入: -121 输出: false

问题分析

参数：整数，有符号
需求：判断是否是回文数
结果：返回结果
思路-1：
1. 将整数转化为字符串
2. 循环字符进行倒序排列，得到倒序字符串
3. 比较参数字符串和倒序后的字符串是否相同
4. 返回比较结果

我的答案

/**
 * 执行用时 : 50 ms, 在Palindrome Number的Java提交中击败了84.03% 的用户
 * 内存消耗 : 36 MB, 在Palindrome Number的Java提交中击败了97.33% 的用户
 */
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        String xStr = String.valueOf(x);
        StringBuilder xrSb = new StringBuilder();
        char[] xCharArray = xStr.toCharArray();
        for (int i = xCharArray.length - 1;i >= 0;i--) {
            xrSb.append(xCharArray[i]);
        }
        return xStr.equals(xrSb.toString());
    }
}

官方题解

public class Solution {
    public bool IsPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if(x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while(x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber/10;
    }
}

为了更好的理解，我执行了下面的代码进行分析：

class Test {
    public static void main(String[] args) {
        isPalindrome(121);
        isPalindrome(-121);
        isPalindrome(9);
        isPalindrome(12321);
    }

    public static boolean isPalindrome(int x) {
        System.out.println("------------------");
        System.out.println("参数：" + x);
        boolean result = true;
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            result = false;
        } else {
            int revertedNumber = 0;
            while (x > revertedNumber) {
                revertedNumber = revertedNumber * 10 + x % 10;
                x /= 10;
                System.out.println("x=" + x + "; num=" + revertedNumber);
            }
            result = x == revertedNumber || x == revertedNumber / 10;
        }

        System.out.println("结果：" + result);
        return result;
    }
}

输出结果：

------------------
参数：121
x=12; num=1
x=1; num=12
结果：true
------------------
参数：-121
结果：false
------------------
参数：9
x=0; num=9
结果：true
------------------
参数：12321
x=1232; num=1
x=123; num=12
x=12; num=123
结果：true

13 罗马数字转整数

问题描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例：

输入	输出
III	3
IV	4
IX	9
LVIII	58
MCMXCIV	1994

问题分析

刚看到这个问题时感觉比较棘手，实际分析后发现并没有那么复杂，难的是算法最优解。

字符和数值是一对一的关系
有6种特殊字符表示其他的数值
各个字符对应的数值相加，可以得到最终值

我的答案

答案一

思路：

首先要建立一个字符和数值的对应表，特殊字符和数值对应表
遍历字符串，先取两个一组的字符判断是否是特殊字符，不是的话取单个字符对应的数值
对所有的数值进行累加，得到最终值
返回最终值

/**
 * 执行用时 : 33 ms, 在Roman to Integer的Java提交中击败了71.16% 的用户
 * 内存消耗 : 42.7 MB, 在Roman to Integer的Java提交中击败了67.73% 的用户
 */
class Solution {
    // 两个Map减少循环次数
    private static Map<String, Integer> romanArray = new HashMap<String, Integer>();
    private static Map<String, Integer> romanArray2 = new HashMap<String, Integer>();

    static {
        romanArray.put("I", 1);
        romanArray.put("V", 5);
        romanArray.put("X", 10);
        romanArray.put("L", 50);
        romanArray.put("C", 100);
        romanArray.put("D", 500);
        romanArray.put("M", 1000);

        romanArray2.put("IV", 4);
        romanArray2.put("IX", 9);
        romanArray2.put("XL", 40);
        romanArray2.put("XC", 90);
        romanArray2.put("CD", 400);
        romanArray2.put("CM", 900);
    }

    public int romanToInt(String s) {
        int result = 0;
        String tmpStr;
        Integer tmpVal;
        for (int i = 0; i < s.length();) {
            String startStr = String.valueOf(s.charAt(i));
            if (i + 1 < s.length()) {
                tmpStr = startStr + String.valueOf(s.charAt(i + 1));
                tmpVal = romanArray2.get(tmpStr);
                if (tmpVal == null) {
                    tmpStr = startStr;
                    tmpVal = romanArray.get(tmpStr);
                }
            } else {
                tmpStr = startStr;
                tmpVal = romanArray.get(tmpStr);
            }
            result += tmpVal.intValue();
            i += tmpStr.length();
        }
        return result;
    }
}

答案二

上面的代码提交后虽然通过了，但是代码看起来着实不太优雅，对效率和资源占用不太满意，随之做出了下面的修改

/**
 * 执行用时 : 执行用时 : 20 ms, 在Roman to Integer的Java提交中击败了96.95% 的用户
 * 内存消耗 : 内存消耗 : 35.8 MB, 在Roman to Integer的Java提交中击败了99.61% 的用户
 */
class Solution {
    private static Map<String, Integer> romanArray = new HashMap<String, Integer>();

    static {
        romanArray.put("I", 1);
        romanArray.put("V", 5);
        romanArray.put("X", 10);
        romanArray.put("L", 50);
        romanArray.put("C", 100);
        romanArray.put("D", 500);
        romanArray.put("M", 1000);
    }

    public int romanToInt(String s) {
        int result = 0;
        for (int i = 0; i < s.length();i++) {
            int val1 = romanArray.get(String.valueOf(s.charAt(i)));
            if (i < s.length() - 1) {
                int val2 = romanArray.get(String.valueOf(s.charAt(i + 1)));
                if (val1 < val2) {
                    result += (val2 - val1);
                    i++;
                    continue;
                }
            }
            result += val1;
        }
        return result;
    }
}

14 最长公共前缀

这个问题给我的启发很大，分治和问题变体部分扩展了我解决某些问题的思路，应着重看下。

问题描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串””。
说明：所有输入只包含小写字母a-z。

我的解答

根据最小长度的元素，使用二分查找法截取元素字符，再拿截取的字符串去遍历数组。

/**
 * 执行用时 : 288 ms, 在所有 Kotlin 提交中击败了69.35%的用户
 * 内存消耗 : 34.6 MB, 在所有 Kotlin 提交中击败了88.24%的用户
 */
 class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.isNullOrEmpty()) return ""
        val shortestEl = findShortestEl(strs)
        if (shortestEl.isEmpty()) return ""
        if (checkCommonPrefix(strs, shortestEl)) return shortestEl
        var commonPrefix = ""

        var minPosition = 0
        var maxPosition = shortestEl.length
        var position = getPosition(minPosition, maxPosition)
        while (position != -1) {
            val prefix = shortestEl.substring(0, position)
            if (checkCommonPrefix(strs, prefix)) {
                commonPrefix = prefix
                minPosition = position
            } else {
                maxPosition = position
            }
            val tmpPosition = getPosition(minPosition, maxPosition)
            if (position != tmpPosition) {
                position = tmpPosition
            } else {
                break
            }
        }
        return commonPrefix
    }

    private fun findShortestEl(strs: Array<String>): String {
        var shortestEl = strs[0]
        strs.forEach {
            if (it.length < shortestEl.length) {
                shortestEl = it
            }
        }
        return shortestEl
    }

    private fun getPosition(min: Int, max: Int): Int {
        if (min >= max) return -1
        var diff = max - min
        return min + diff / 2 + diff % 2
    }

    private fun checkCommonPrefix(strs: Array<String>, prefix: String): Boolean {
        strs.forEach {
            if (!it.startsWith(prefix)) {
                return false
            }
        }
        return true
    }
}

提交后，发现执行用时有些高，想了下，我的解法在参数数组越长执行用时可能就越长。所以在解答该题时，越少遍历数组效率越高。
不过看了下官方题解，发现二分查找也是其中的一个解法。

官方题解

官方给出了四种解法，下面依次来看。
这里只给出解题思路，具体实现代码可在官方题解找到。

水平扫描法

随机取一个元素，遍历数组元素，将其取出的元素依次从尾部减去一个字符，与其他数组元素进行比较。
最坏的情况下，需要进行（（取出的元素字符数 - 1） * （数组长度 - 1））次比较.

水平扫描

随机取一个元素，从前往后枚举这个元素字符串的每一列，先比较每个字符串相同列上的字符（即不同字符串相同下标的字符）然后再进行对下一列的比较。

分治

使用分治技巧，将原问题分成两个子问题（left，right），再将每个子问题分成两个子问题，直到不能分出子问题。在子问题中获取公共前缀，从头到尾挨个比较left和right，最终得到原问题的解。

懒得画图了，凑合看吧～～闪～～
过程：
原问题：[“leetcode”,”leetcod”,”leetco”,”leetc”,”leet”,”lee”,”le”,”l”]
子问题：[“leetcode”,”leetcod”,”leetco”,”leetc”]和[“leet”,”lee”,”le”,”l”]
子问题：[“leetcode”,”leetcod”]、[“leetco”,”leetc”]和[“leet”,”lee”],[“le”,”l”]
子结果：”leetcod”、”leetc”和”lee”、”l”
子问题：[“leetcod”,”leetc”]和[“lee”,”l”]
子结果：”leetc”和”l”
子问题：[“leetcod”,”l”]
原问题结果=子问题结果=”l”

二分查找法

取出一个元素，将元素字符从前到后分成两部分，每次都用前一部分字符去匹配，如果不能匹配说明答案在前一部分中，能匹配说明答案在后一部分（加上前一部分），再对匹配到的这一部分执行同样的流程，最终得到公共前缀。

过程：
数组：[“leetcode”,”leetco”,”leetc”,”leet”,”lees”]
取出元素：”leetcode”
匹配区间：”leetcode”
不能匹配
匹配区间：”leet”
不能匹配
匹配区间：”le”
能匹配
匹配区间：”lee”
能匹配
得到答案->”lee”

问题变体

原文地址

问题描述

给定一些字符串数组Array，我们要找到字符串S与Array中元素的最长公共前缀。这样的查询操作可能会非常频繁。

官方解答

将所有的字符（数组中所有元素的字符）存储到字典树中来优化最长公共前缀查询操作。
在字典树中，从根向下的每一个节点都代表一些元素的公共前缀。
要找到字符串S与Array中元素的最长公共前缀，需要从根开始找到一条最深的路径，满足以下条件：

这是所查询的字符串S的一个前缀.
路径上的每一个子节点都有且只有一个孩子。否则，找到的路径就不是所有字符串的公共前缀。
路径不包含任一元素字符串结尾代表的节点。因为最长公共前缀不可能比任意一个字符串长。

20 有效的括号

问题描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

注意：空字符串可被认为是有效字符串。

我的解答

思考了小半个小时，期间进行了几次尝试，没能想出解法。为了避免浪费太多时间，就去看了官方解答动画演示后进行了代码实现。
我好菜，2333～

import java.util.*

// 耗时：260 ms	内存占用：33.3 MB
class Solution {
    private val charMap = mapOf(')' to '(', ']' to '[', '}' to '{')
    fun isValid(s: String): Boolean {
        if (s.isEmpty()) return true
        val stack = Stack<Char>()
        s.forEach {
            if (!stack.empty() && stack.peek() == charMap[it]) {
                stack.pop()
            } else {
                stack.push(it)
            }
        }
        return stack.empty()
    }
}

官方题解

我看评论中有看了题解半个小时才弄懂的，所以建议先看动画演示再细看文字解释，比较容易理解。
我上面的代码实现可能不是最好的实现，所以还是建议看下官方题解。

21 合并两个有序链表

问题描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

我的解答

1
2
3

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

根据上面的数据结构定义，可以看出参数和返回值都是一个链表结构，而且参数链表都是有序的。所以只要创建一个结果链表，存放两个参数链表迭代比较得出的数据就行了，关键在于控制好指针在链表中的移动。

/**
 * 执行用时:284 ms, 在所有 Kotlin 提交中击败了87.76%的用户
 * 内存消耗:33.9 MB, 在所有 Kotlin 提交中击败了36.36%的用户
 */

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
        if (l1 == null) return l2
        if (l2 == null) return l1
        // 为了使用方便，对结果进行初始化
        val result = ListNode(0)
        // 定义指针变量在Node间移动
        var tmpResult = result
        var node1: ListNode? = l1
        var node2: ListNode? = l2
        fun refreshResult(node: ListNode) {
            tmpResult.next = ListNode(node.`val`)
            tmpResult = tmpResult.next ?: tmpResult
        }
        loop@ while (true) {
            when {
                node1 == null || node2 == null -> {
                    tmpResult.next = node1 ?: node2
                    break@loop
                }
                node1.`val` < node2.`val` -> {
                    refreshResult(node1)
                    node1 = node1.next
                }
                else -> {
                    refreshResult(node2)
                    node2 = node2.next
                }
            }
        }
        return result.next
    }
}

官方解答

官方解答地址

递归

将两个链表中头部较小的值，与合并剩下的两个链表的结果进行合并。递归这个过程，直到得出最终结果。
官方的这个Java代码实现真是简洁，忍不住放了出来。但是实际开发中可不要这么写，因为改变了参数链表的内容。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        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;
        }
    }
}

迭代

将元素少的链表逐一插入到另一个链表中正确的位置。
这个解法字面上就能理解，不再多诉。

26 删除排序数组中的重复项

问题描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

问题分析

这个问题初次看时有些看不明白，有几个“点”需要知道。

理解下“原地算法”。
不能使用额外的数组去解决问题。
需要删除原数组中的重复元素，但不需要考虑数组中超出新长度后面的元素。
如：输入[1,1,2]后，返回值是2，数组被修改为[1,2,2]。

我的解答

最方便的做法是创建一个数组，存放过滤后的元素，在以往的开发中经常这么做。今天看到这道题，也是第一次认真的思考了下此类题的更好的解法。

/**
 * 执行用时:388ms,在所有Kotlin提交中击败了73.77%的用户
 * 内存消耗:40.1 MB, 在所有Kotlin提交中击败了70.59%的用户
 */
class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        if (nums.size <= 1) return nums.size
        var pos1 = 0
        var pos2 = 1
        while (pos2 < nums.size) {
            if (nums[pos1] != nums[pos2]) {
                pos1++
                nums[pos1] = nums[pos2]
                pos2++
            } else {
                pos2++
            }
        }
        return pos1 + 1
    }
}

官方题解

看完后才发现，我的解法就是双指针法。官方题解地址

双指针法

数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

27 移除元素

此题的官方地址

问题描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

问题分析

此题和删除排序数组中的重复项这道题目很相似，都要满足原地算法，并且不能使用额外的数组去解决问题，此外，解答时不需要考虑数组中超出新长度后面的元素。

我的解答

由于刚做了上面删除排序数组中的重复项这道算法题，所以很简单的就写出了下面的答案。
解答实现了两次，解题思路一样，只是具体实现有所优化。然后才发现LeetCode提交代码的结果（执行用时和内存消耗）并不准确，所以关于这个结果大家看看就好。

解题思路：用一个指针变量I记录在数组中的位置，如果I位置的元素不需要移除将I递增，否则检查I后面是否还有不需要移除的元素，有的话将这个元素值和I位置的元素调换位置。然后递增I继续向后检查。最后I的值也就是数组的新长度。

代码实现一：

/**
 * 执行用时:276ms, 在所有Kotlin提交中击败了90.63%的用户
 * 内存消耗:34.7MB, 在所有Kotlin提交中击败了54.55%的用户
 */
class Solution {
    fun removeElement(nums: IntArray, `val`: Int): Int {
        if (nums.isEmpty()) return 0
        var count = 0
        nums.forEachIndexed { index, i ->
            if (i != `val`) {
                count++
            } else if (index < nums.lastIndex) {
                var hasNext = false
                for (pos in index + 1..nums.lastIndex) {
                    if (nums[pos] != `val`) {
                        nums[index] = nums[pos]
                        nums[pos] = `val`
                        count++
                        hasNext = true
                        break
                    }
                }
                if (!hasNext) {
                    return count
                }
            }
        }
        return count
    }
}

代码实现二：

/**
 * 执行用时:284ms, 在所有Kotlin提交中击败了81.25%的用户
 * 内存消耗:35.4MB, 在所有Kotlin提交中击败了9.09%的用户
 */
class Solution {
    fun removeElement(nums: IntArray, `val`: Int): Int {
        if (nums.isEmpty()) return 0
        var count = 0
        while (count < nums.size) {
            if (nums[count] != `val`) count++
            else if (count < nums.lastIndex) {
                var goOn = false
                for (pos in count + 1..nums.lastIndex) {
                    if (nums[pos] != `val`) {
                        nums[count] = nums[pos]
                        nums[pos] = `val`
                        count++
                        goOn = pos < nums.lastIndex
                        break
                    }
                }
                if (!goOn) break
            } else break
        }
        return count
    }
}

官方题解

看完官方题解后，发现代码实现其实可以更简洁高效，惭愧～

提示：

尝试双指针法。
你是否使用“元素顺序可以更改”这一属性？
当要删除的元素很少时会发生什么？

双指针

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

双指针 — 当要删除的元素很少时

与上面解法的区别是，考虑到了数组包含很少的要删除的元素的情况。

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

28 实现strStr()

此题的官方地址

问题描述

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = “hello”, needle = “ll”
输出: 2

示例 2:

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

我的解答

String.indexOf()

看到该题，就想到了Java中有 String.indexOf() 这个函数可以直接调用。现成的轮子，不用白不用～

/*
    执行用时 : 256 ms, 在所有 Kotlin 提交中击败了 91.30% 的用户
    内存消耗 : 34.8 MB, 在所有 Kotlin 提交中击败了 62.50% 的用户
*/
class Solution {
    fun strStr(haystack: String, needle: String): Int {
        if (needle.isEmpty()) return 0
        /* Kotlin函数 */
        return haystack.indexOf(needle)
    }
}

双指针

虽然有现成的轮子可以使用，但是做算法题的目的还没有达到。所以费了点功夫，写出了下面的代码。没错，也是用双指针法进行求解，谁让前面几道算法题用双指针多呢～

/*
    执行用时 : 284 ms, 在所有 Kotlin 提交中击败了 43.48% 的用户
    内存消耗 : 34.5 MB, 在所有 Kotlin 提交中击败了 62.50% 的用户
*/
class Solution {
    fun strStr(haystack: String, needle: String): Int {
        if (needle.isEmpty()) return 0
        if (needle.length > haystack.length) return -1

        var walkIndex = 0
        var index = 0
        while (index <= haystack.lastIndex) {
            // 满足了要求，这里haystack长度大于needle长度
            if (walkIndex > needle.lastIndex) {
                return index - needle.length
            }
            val char = haystack[index]
            if (char == needle[walkIndex]) {
                walkIndex++
            } else {
                index -= walkIndex
                walkIndex = 0
            }
            index++
        }
        // haystack长度等于needle长度，并满足了要求（循环结束walkIndex未被重置为0）
        if (walkIndex == needle.length) {
            return index - needle.length
        }
        return -1
    }
}

官方题解

此题没有官方题解，还是看下Java中 String.indexOf 这个轮子的实现吧。注释部分使用Google翻译翻译了一下，就是这么贴心～

/**
 * String和StringBuffer共享的代码进行搜索。
 * 该source是要搜索的字符数组和目标是要搜索的字符串。
 *
 * @param   source       正在搜索的字符.
 * @param   sourceOffset 源字符串的偏移量.
 * @param   sourceCount  源字符串的计数.
 * @param   target       要搜索的字符.
 * @param   targetOffset 目标字符串的偏移量.
 * @param   targetCount  目标字符串的计数.
 * @param   fromIndex    要开始搜索的索引.
 */
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    if (targetCount == 0) {
        return fromIndex;
    }

    char first = target[targetOffset];
    int max = sourceOffset + (sourceCount - targetCount);

    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        /* 寻找第一个字符. */
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        /* 找到第一个字符，现在看看v2的其余部分 */
        if (i <= max) {
            int j = i + 1;
            int end = j + targetCount - 1;
            for (int k = targetOffset + 1; j < end && source[j]
            == target[k]; j++, k++);

            if (j == end) {
                /* 找到整个字符串. */
                return i - sourceOffset;
            }
        }
    }
    return -1;
}

35 搜索插入位置

此题的官方地址

问题描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

我的解答

这道题非常简单，随手便写出了下面的代码（暴力法）。如果考虑到数组较大的情况，还有其他的解法：二分查找法。

/*
执行用时 : 280 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
内存消耗 : 34.8 MB, 在所有 Kotlin 提交中击败了 64.29% 的用户
*/
class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        for ((index, el) in nums.withIndex()) {
            if (target <= el) return index
        }
        return nums.size
    }
}

精选解答

二分查找法

作者：liweiwei1419
链接：点这里
来源：力扣（LeetCode）

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (nums[len - 1] < target) {
            return len;
        }

        int left = 0;
        int right = len - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            // 等于的情况最简单，我们应该放在第 1 个分支进行判断
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 题目要我们返回大于或者等于目标值的第 1 个数的索引
                // 此时 mid 一定不是所求的左边界，
                // 此时左边界更新为 mid + 1
                left = mid + 1;
            } else {
                // 既然不会等于，此时 nums[mid] > target
                // mid 也一定不是所求的右边界
                // 此时右边界更新为 mid - 1
                right = mid - 1;
            }
        }
        // 注意：一定得返回左边界 left，
        // 如果返回右边界 right 提交代码不会通过
        // 【注意】下面我尝试说明一下理由，如果你不太理解下面我说的，那是我表达的问题
        // 但我建议你不要纠结这个问题，因为我将要介绍的二分查找法模板，可以避免对返回 left 和 right 的讨论

        // 理由是对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
        // 在上面的 while (left <= right) 退出循环以后，right < left，right = 0 ，left = 1
        // 根据题意应该返回 left，
        // 如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right

        return left;
    }
}

38 报数

此题的官方地址

问题描述

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1 —> 1
2 —> 11
3 —> 21
4 —> 1211
5 —> 111221
省略～
1 被读作 “one 1” (“一个一”) , 即 11。
11 被读作 “two 1s” (“两个一”）, 即 21。
21 被读作 “one 2”, “one 1” （”一个二” , “一个一”) , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。

示例 1:

输入: 1
输出: “1”

示例 2:

输入: 4
输出: “1211”

问题分析

这个算法问题我缕了几遍，着实没看懂，去评论区一看同样情况的大有人在，最后看了网友的评论才理解题目的意思，2333～
题目的意思是对序列前一个数进行报数。数列第一项是1，那第二项就报第一项的有1个1，输出11。然后第三项就在第二项的基础上报数，第二项是11，第三项不就是2个1么，然后输出21。

我的解答

字典

使用Map集合将 1～30 所有的答案预先存放到Map集合，调用函数时取出返回。该方法虽然效率高、占用内存空间小，但是只适用于求解该题，我们可以换个更优雅的方法来解决。

/*
执行用时 : 236 ms, 在所有 Kotlin 提交中击败了92.31%的用户
内存消耗 : 32.5 MB, 在所有 Kotlin 提交中击败了100.00%的用户
*/
class Solution {
    fun countAndSay(n: Int): String {
        val map = mapOf(
            1 to "1",
            2 to "11",
            3 to "21",
            4 to "1211",
            5 to "111221",
            6 to "312211",
            7 to "13112221",
            8 to "1113213211",
            9 to "31131211131221",
            10 to "13211311123113112211",
            11 to "11131221133112132113212221",
            12 to "3113112221232112111312211312113211",
            13 to "1321132132111213122112311311222113111221131221",
            14 to "11131221131211131231121113112221121321132132211331222113112211",
            15 to "311311222113111231131112132112311321322112111312211312111322212311322113212221",
            16 to "132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211",
            17 to "11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221",
            18 to "31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211",
            19 to "1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221",
            20 to "11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211",
            21 to "311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
            22 to "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
            23 to "111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
            24 to "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
            25 to "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
            26 to "1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
            27 to "31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
            28 to "13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
            29 to "11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
            30 to "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211"
            )
        return map.getValue(n)
    }
}

常规法

使用字典预存1的报数，在获取n的报数时，从1～n依次进行翻译，并将1～n中间的结果存入字典，方便下次直接使用。没有更深入的去研究，下面的实现执行用时有些高。

/*
执行用时 : 272 ms, 在所有 Kotlin 提交中击败了46.15%的用户
内存消耗 : 33.7 MB, 在所有 Kotlin 提交中击败了100.00%的用户
*/
class Solution {
    private val MAP = mutableMapOf(1 to "1")

    fun countAndSay(n: Int): String {
        var countOff = MAP[n]
        if (countOff != null) return countOff

        for (num in 1..n) {
            val mapVal = MAP[num]
            if (mapVal != null) {
                countOff = mapVal
            } else {
                countOff = transform(countOff!!)
                MAP[num] = countOff
            }
        }
        return countOff!!
    }

    private fun transform(str: String): String {
        val countOff = StringBuilder()
        var count = 0 // 有几个数（重复次数）
        str.forEachIndexed { index, c ->
            if (c != str[index - count]) {
                countOff.append(count)
                countOff.append(str[index - count])
                count = 1
            } else {
                count++
            }
            if (index == str.lastIndex) {
                countOff.append(count)
                countOff.append(str[index])
            }
        }
        return countOff.toString()
    }
}

官方题解

此题官方没有给出解答，我找了个优质题解来看下。
作者：jimmy00745
原文地址
来源：力扣（LeetCode）

具体思路：

先设置上一人为’1’
开始外循环
每次外循环先置下一人为空字符串，置待处理的字符num为上一人的第一位，置记录出现的次数为1
开始内循环，遍历上一人的数，如果数是和num一致，则count增加。
若不一致，则将count和num一同添加到next_person报的数中，同时更新num和count
别忘了更新next_person的最后两个数为上一个人最后一个字符以及其出现次数！

class Solution:
    def countAndSay(self, n: int) -> str:
        prev_person = '1'
        for i in range(1,n):
            next_person, num, count = '', prev_person[0], 1
            for j in range(1,len(prev_person)):
                if prev_person[j] == num:count += 1
                else:
                    next_person += str(count) + num
                    num = prev_person[j]
                    count = 1
            next_person += str(count) + num
            prev_person = next_person
        return prev_person

53 最大子序和

此题的官方地址

问题描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

我的解答

我在尝试求解该题时，陷入了思维误区，代码实现也越来越复杂，在继续尝试一番后无奈放弃。转到评论区，看到有人说这道题是清华考研专业课算法题，能上清华的果然有实力～

精选解答

动态规划

动态规划的思路：
声明两个变量，一个变量存最终结果，一个缓存对目前状态有增益的子序列之和。
如果之前缓存的子序列之和大于零，说明其是对之后状态有增益的，加上当前状态的值并更新缓存；反之则舍弃，只取当前状态的值更新至缓存。

作者：guanpengchn
链接：原文地址
来源：力扣（LeetCode）

思路：

这道题用动态规划的思路并不难解决，比较难的是后文提出的用分治法求解，但由于其不是最优解法，所以先不列出来
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
时间复杂度：O(n)

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for (int num: nums) {
            if (sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

分治法

还记得吗？分治法在前面最长公共前缀这道算法题出现过。

作者：pandawakaka
链接：原文地址
来源：力扣（LeetCode）

分治法其他题解里将的很清楚了。其实就是它的最大子序和要么在左半边，要么在右半边，要么是穿过中间，对于左右边的序列，情况也是一样，因此可以用递归处理。中间部分的则可以直接计算出来，时间复杂度应该是 O(nlogn)。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        #递归终止条件
        if n == 1:
            return nums[0]
        else:
            #递归计算左半边最大子序和
            max_left = self.maxSubArray(nums[0:len(nums) // 2])
            #递归计算右半边最大子序和
            max_right = self.maxSubArray(nums[len(nums) // 2:len(nums)])

        #计算中间的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加
        max_l = nums[len(nums) // 2 - 1]
        tmp = 0
        for i in range(len(nums) // 2 - 1, -1, -1):
            tmp += nums[i]
            max_l = max(tmp, max_l)
        max_r = nums[len(nums) // 2]
        tmp = 0
        for i in range(len(nums) // 2, len(nums)):
            tmp += nums[i]
            max_r = max(tmp, max_r)
        #返回三个中的最大值
        return max(max_right,max_left,max_l+max_r)

58 最后一个单词的长度

链接：原文地址
来源：力扣（LeetCode）

问题描述

给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。

示例:

输入: “Hello World”
输出: 5

我的解答

目前为止，得到的最好的解答成绩，美滋滋～。由于解该题并没有花费太多时间，所以又思考了一下其他解法：

将字符串中的单词裁剪出来存放到集合，获取最后一个集合元素的长度。
分治法，只是想到能处理该问题，并没有写代码实现。

/*
 执行用时 : 244 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
 内存消耗 : 33.1 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution {
    fun lengthOfLastWord(s: String): Int {
        var length = 0
        var lastLength = length
        s.forEach { c ->
            if (c != ' ') {
                length++
            } else if (length > 0) {
                lastLength = length
                length = 0
            }
        }
        return if (length > 0) length else lastLength
    }
}

注：下面的代码实现并不适合求解该题，更适用于获取字符串中的所有单词。

/*
 执行用时 : 300 ms, 在所有 Kotlin 提交中击败了 27.27% 的用户
 内存消耗 : 34.4 MB, 在所有 Kotlin 提交中击败了 66.67% 的用户
 */
class Solution {
    fun lengthOfLastWord(s: String): Int {
        val words = mutableListOf<String>()
        var startIndex: Int? = null
        s.forEachIndexed { index, c ->
            if (c == ' ') {
                if (startIndex != null && index > startIndex!!) {
                    words.add(s.substring(startIndex!!, index))
                    startIndex = null
                }
            } else if (startIndex == null) {
                startIndex = index
            }
            if (startIndex != null && index == s.lastIndex) {
                words.add(s.substring(startIndex!!))
            }
        }
        return if (words.isEmpty()) 0 else words[words.lastIndex].length
    }
}

精选题解

作者：guanpengchn
链接：原文地址
来源：力扣（LeetCode）

看了该题解后，发现可以继续优化我的解法，我的解法是从前往后找最后一个单词，其实可以反过来从后往前找。

思路

标签：字符串遍历
从字符串末尾开始向前遍历，其中主要有两种情况
第一种情况，以字符串”Hello World”为例，从后向前遍历直到遍历到头或者遇到空格为止，即为最后一个单词”World”的长度5
第二种情况，以字符串”Hello World “为例，需要先将末尾的空格过滤掉，再进行第一种情况的操作，即认为最后一个单词为”World”，长度为5
所以完整过程为先从后过滤掉空格找到单词尾部，再从尾部向前遍历，找到单词头部，最后两者相减，即为单词的长度
时间复杂度：O(n)，n为结尾空格和结尾单词总体长度

class Solution {
    public int lengthOfLastWord(String s) {
        int end = s.length() - 1;
        while(end >= 0 && s.charAt(end) == ' ') end--;
        if(end < 0) return 0;
        int start = end;
        while(start >= 0 && s.charAt(start) != ' ') start--;
        return end - start;
    }
}

66 加一

链接：原文地址
来源：力扣（LeetCode）

问题描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

我的解答

类型转换求解

思路：将IntArray转换为整数，+1后再转换回IntArray进行返回。

/*
 执行用时 : 288 ms, 在所有 Kotlin 提交中击败了 66.67% 的用户
 内存消耗 : 33.2 MB, 在所有 Kotlin 提交中击败了 60.00% 的用户
 */
class Solution {
    fun plusOne(digits: IntArray): IntArray {
        return (digits.toBigDecimal() + BigDecimal(1)).toString().toIntArray()
    }

    private fun IntArray.toBigDecimal(): BigDecimal {
    val builder = StringBuilder()
        for (el in this) {
            builder.append(el)
        }
        // 如果使用 toInt 和 toLong，值超出类型范围会报下面的错误：java.lang.NumberFormatException.
        return builder.toString().toBigDecimal()
    }

    private fun String.toIntArray(): IntArray {
        val intArray = IntArray(this.length)
        this.forEachIndexed { index, c ->
            intArray[index] = c.toString().toInt()
        }
        return intArray
    }
}

数组遍历

遍历数组求解，该想到的点都想到了，就是代码实现惨不忍睹，原因一是想到IntArray是指针变量，该题需要返回值那就不应该修改原数组的元素，原因之二是这次求解有些依赖Kotlin的语法糖了，不用的话代码可以写的更简洁一些。

/*
 执行用时 : 296 ms, 在所有 Kotlin 提交中击败了 66.67% 的用户
 内存消耗 : 35.9 MB, 在所有 Kotlin 提交中击败了 60.00% 的用户
 */
class Solution {
    fun plusOne(digits: IntArray): IntArray {
        if (digits[digits.lastIndex] < 9) {
            return digits.clone().apply { this[lastIndex] = this[lastIndex] + 1 }
        }
        val newArray = MutableList(digits.size + 1) { -1 }
        var plus1Index = digits.size // 记录需要+1的位置
        for (index in digits.lastIndex downTo 0) {
            if (plus1Index < 0) {
                newArray[index + 1] = digits[index]
                continue
            }
            if (digits[index] < 9) {
                newArray[index + 1] = digits[index] + 1
                plus1Index = -1
            } else {
                newArray[index + 1] = 0
                plus1Index--
            }
        }
        if (plus1Index >= 0) {
            newArray[0] = 1
        } else {
            newArray.removeAt(0)
        }
        return newArray.toIntArray()
    }
}

精选题解

作者：yhhzw
链接：原文地址
来源：力扣（LeetCode）

根据题意加一，没错就是加一这很重要，因为它是只加一的所以有可能的情况就只有两种：

除9之外的数字加一；
数字9。

加一得十进一位个位数为0加法运算如不出现进位就运算结束了且进位只会是一。
所以只需要判断有没有进位并模拟出它的进位方式，如十位数加1个位数置为0，如此循环直到判断没有再进位就退出循环返回结果。
然后还有一些特殊情况就是当出现99、999 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

由于后期改成了使用算法标签进行解答，不再根据顺序和页数进行分类，所以将下面的题移了过来。

860 柠檬水找零

LeetCode简单算法题：860～1013

LeetCode官网地址

闹了个乌龙，打算每篇博客50到题，从简单算法题第一道往后一道道刷的，结果不知怎的从第五页开始了。。。

so，这篇博客就先做了一道放在了这里，立个flag，看看刷到这里需要多久～

期待我尽早刷到这里吧，哈哈

问题描述

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

解答过程（2019.03.25）

这是我最开始提交的Java实现，结果提交后发现错了，梳理了几遍后依旧没有头绪。迫不得已点击了答案，发现把该问题想简单了：顾客支付的钱只有固定的5，10，20三种，只需要梳理三种支付方式可能出现的情况，就能正确解答。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        if (bills == null || bills.length <= 0) return false;
        int change = 0;
        int diff = 0;
        for (int bill : bills) {
            diff = bill - 5;
            if (diff == 0) {
                change += bill;//这里bill等于5
            } else if (diff > 0 && change >= diff) {
                change = change - diff + bill;
            } else {
                return false;
            }
        }
        return true;
    }
}

官方解答

思路

最初，没有5美元和10美元的钞票，收到20美元的钞票后，该20美元不能用于找零。

顾客支付5美元钞票，得到一张5美元的钞票
顾客支付10美元钞票
- 有5美元钞票，找零
- 没有5美元钞票，无法找零，返回false
顾客支付20美元钞票
- 有5美元和10美元钞票，用一张10美元和5美元钞票找零更有利于以后找零
- 只有5美元钞票，用三张5美元进行找零
- 其他情况，无法找零。
  - 只有20美元钞票
  - 只有10美元钞票
  - 没有钞票

class Solution {
    public boolean lemonadeChange(int[] bills) {
        // 定义局部变量记录5美元和10美元钞票的数量
        int five = 0, ten = 0;
        for (int bill: bills) {
            // @1 第一种情况
            if (bill == 5)
                five++;
            // @2 第二种情况
            else if (bill == 10) {
                if (five == 0) return false;
                five--;
                ten++;
            }
            // @3 第三种情况
            else {
                // @3.1 第三种情况的第一种可能
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                }
                // @3.2 第三种情况的第二种可能
                else if (five >= 3) {
                    five -= 3;
                }
                // @3.3 第三种情况的第三种可能
                else {
                    // 无法找零
                    return false;
                }
            }
        }
        // 能找零
        return true;
    }
}

118 杨辉三角

作者：LeetCode
链接：地址
来源：力扣（LeetCode）

问题描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。

示例：

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

我的解答

经过之前几十道算法题的洗礼，我在解答这道题时并没有花费什么功夫，思路也很简单，明白了每行的每个元素怎么求值题就解了。元素求值有两种方式：

每行的第一个和最后一个元素值恒为1
每对相邻的元素值的和是下一行对应元素的值。

Java语言实现。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> rowList = new ArrayList<>(numRows);
        for (int row = 0; row < numRows; row++) {
            List<Integer> colList = new ArrayList<>(row + 1);
            rowList.add(colList);
            for (int col = 0; col <= row; col++) {
                if (col == 0 || col == row) {
                    colList.add(1);
                } else {
                    List<Integer> lastRowList = rowList.get(row - 1);
                    colList.add(lastRowList.get(col - 1) + lastRowList.get(col));
                }
            }
        }
        return rowList;
    }
}

Kotlin语言实现，思路同上面的Java实现。

/*
 执行用时 : 248 ms, 在所有 Kotlin 提交中击败了 72.22% 的用户
 内存消耗 : 32.1 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val list = mutableListOf<MutableList<Int>>()
        for (row in 0 until numRows) {
            list.add(mutableListOf())
            for (col in 0..row) {
                if (col == 0 || col == row) {
                    list[row].add(1)
                } else {
                    list[row].add(list[row-1][col-1] + list[row-1][col])
                }
            }
        }
        return list
    }
}

官方解答

作者：LeetCode
链接：地址
来源：力扣（LeetCode）

方法：动态规划

实现思路和我的思路一致，这里不再累述，只贴出代码实现。但还是建议看下原文链接，有动态演示，很方便理解。
虽然这一算法非常简单，但用于构造杨辉三角的迭代方法可以归类为动态规划，因为我们需要基于前一行来构造每一行。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        // First base case; if user requests zero rows, they get zero rows.
        if (numRows == 0) {
            return triangle;
        }

        // Second base case; first row is always [1].
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum-1);

            // The first row element is always 1.
            row.add(1);

            // Each triangle element (other than the first and last of each row)
            // is equal to the sum of the elements above-and-to-the-left and
            // above-and-to-the-right.
            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }

            // The last row element is always 1.
            row.add(1);

            triangle.add(row);
        }

        return triangle;
    }
}

169 求众数

作者：LeetCode
链接：地址
来源：力扣（LeetCode）

问题描述

给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于n/2的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

我的解答

这道题正确解答很简单，解法也有很多种，但是想解的好却不容易。短时间内我也只写出了下面两种解法，虽然想到了分治法也能求解，但是没有用代码实现。建议看看下面的官方题解，一些解法真的巧妙！

哈希表

思路很简单，用一个循环遍历数组，将元素和元素出现的次数存入到哈希表，最后迭代哈希表得到众数。

class Solution {
    /*
     执行用时 : 456 ms, 在所有 Kotlin 提交中击败了 48.15% 的用户
     内存消耗 : 50.2 MB, 在所有 Kotlin 提交中击败了 75.00% 的用户
    */
    fun majorityElement(nums: IntArray): Int {
        val map = mutableMapOf<Int, Int>()
        for (num in nums) {
            map[num] = (map[num] ?: 0) + 1
        }
        val tmp = nums.size.div(2)
        map.forEach { (key, value) ->
            if (value > tmp) {
                return key
            }
        }
        throw Error()
    }
}

暴力法

双重循环求解，外层循环控制元素，内层循环计算元素出现的次数，当出现满足众数条件时返回元素。
由于该解法使用双重循环，导致执行用时过高，远超出我预期。

class Solution {
    /*
     执行用时 : 2604 ms, 在所有 Kotlin 提交中击败了 7.41% 的用户
     内存消耗 : 50.3 MB, 在所有 Kotlin 提交中击败了 75.00% 的用户
    */
    fun majorityElement(nums: IntArray): Int {
        val majorityCount = nums.size.div(2)
        var count: Int
        for (num in nums) {
            count = 0
            for (num2 in nums) {
                if (num2 == num) {
                    count++
                }
            }
            if (count > majorityCount) {
                return num
            }
        }
        throw Error()
    }
}

官方题解

作者：LeetCode
链接：地址
来源：力扣（LeetCode）

这里过滤了一些常规解答，只列出了比较巧妙的解法，对其他解法感兴趣的同学可以点击地址看下。

排序

所有解法中代码行数最少，只有两行：

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

思路：满足众数条件的元素，出现的次数超出了数组总长度的一半，那么在为数组排序后，数组最中间的元素肯定就是众数！

[3,2,3] 排序后：[2,3,3]，最中间的元素是：3
[2,2,1,1,1,2,2] 排序后：[1,1,1,2,2,2,2]，最中间的元素是：2

随机化

思路：由于一个给定的下标对应的数字很有可能是众数，我们随机挑选一个下标，检查它的值是否是众数，如果是就返回，否则继续随机挑选。

class Solution {
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }
    // 统计指定数字在数组中出现的次数
    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }
    public int majorityElement(int[] nums) {
        Random rand = new Random();
        int majorityCount = nums.length/2;
        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }
}

Boyer-Moore 投票算法

该算法的思路及其巧妙，在看完时对作者竖然起敬，然后发现这不是“开心消消乐”吗？！

思路

如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
定义一个候选众数 candidate，再维护一个计数器 count。遇到和 candidate 相同的数字， count 加一，否则 count 减一。当 count 等于0时，忽略钱买额数字，将候选众数 candidate 改为下一个数字，计数器 count 重置为0。这样最后剩下的候选众数 candidate 就是要求的众数。
来看两个示例（竖线用来划分每次计数器归零的情况）。
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 5, 5, 5, 5]

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

448 找到所有数组中消失的数字

作者：LeetCode
链接：地址
来源：力扣（LeetCode）

问题描述

给定一个范围在1 ≤ a[i] ≤ n（n=数组大小）的整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内

示例:

输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]

我的解答

该题还是有一定的难度的，尤其是要求不使用额外空间且时间复杂度为O(n)的情况下完成这个任务。

思索来思索去，并没有想到优雅些的解决办法，所以使用暴力法进行求解，结果提交后没有通过。又审了几遍题，发现是我忽略了一点：n=数组大小，找出[1, n]范围之间没有出现在数组中的数字，惭愧的很。
修改后再次提交，顺利通过，但执行结果惨不忍睹。再来！
使用动态规划求解，执行结果有些超出预期，但代码实现可读性有些差。再来！
修改后的动态规划代码实现看起来就舒服了一些！
收工，看下官方题解。

暴力法

/**
 * 解答错误
 */
class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val disNums = arrayListOf<Int>()
        if (nums.size <= 1) return disNums
        nums.sort()
        for (el in nums[0]..nums[nums.lastIndex]) {
            if (!nums.contains(el)) {
                disNums.add(el)
            }
        }
        return disNums
    }
}

修改后的暴力法

/**
 * 执行用时 : 2232 ms, 在所有 Kotlin 提交中击败了 25.00% 的用户
 * 内存消耗 : 52.4 MB, 在所有 Kotlin 提交中击败了 50.00% 的用户
 */
class Solution2 {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val disNums = arrayListOf<Int>()
        for (el in 1..nums.size) {
            if (!nums.contains(el)) {
                disNums.add(el)
            }
        }
        return disNums
    }
}

动态规划

/**
 * 执行用时 : 472 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
 * 内存消耗 : 50.8 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val disNums = arrayListOf<Int>()
        nums.sort()
        nums.forEachIndexed { index, el ->
            val tmp = if (index > 0) nums[index-1]+1 else 1
            if (el > tmp) {
                for (diff in tmp until el) {
                    disNums.add(diff)
                }
            }
            if (index == nums.lastIndex && el < nums.size) {
                for (diff in el+1..nums.size) {
                    disNums.add(diff)
                }
            }
        }
        return disNums
    }
}

优化过的动态规划

/**
 * 执行用时 : 480 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
 * 内存消耗 : 51 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val disNums = arrayListOf<Int>()
        if (nums.isEmpty()) return disNums
        nums.sort()

        fun addByDiff(from: Int, untilTo: Int) {
            for (el in from until untilTo) {
                disNums.add(el)
            }
        }
        nums.forEachIndexed { index, el ->
            if (index == 0) {
                if (el > 1) {
                    addByDiff(1, el)
                }
            } else if (el > nums[index-1]+1) {
                addByDiff(nums[index-1]+1, el)
            }
        }
        if (nums[nums.lastIndex] < nums.size) {
            for (el in nums[nums.lastIndex]+1..nums.size) {
                disNums.add(el)
            }
        }
        return disNums
    }
}

精选题解

作者：haydenmiao
链接：地址
来源：力扣（LeetCode）

思路：

将数组元素对应为索引的位置加n
遍历加n后的数组，若数组元素值小于等于n，则说明数组下标值不存在，即消失的数字

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        if(nums.empty()) return nums;
        for(int i=0;i<nums.size();i++)
        {
            int index=(nums[i]-1)%nums.size();
            nums[index]+=nums.size();
        }
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]<=nums.size())
                res.push_back(i+1);
        }
        return res;
    }
};

作者没有使用Java和Kotlin语言实现该解题思路，我使用Kotlin语言进行了实现。

/**
 * 执行用时 : 392 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
 * 内存消耗 : 49.6 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution4 {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val disNums = arrayListOf<Int>()
        if (nums.isEmpty()) return disNums
        for (el in nums) {
            nums[(el-1) % nums.size] += nums.size
        }
        nums.forEachIndexed { index, el ->
            if (el <= nums.size) {
                disNums.add(index+1)
            }
        }
        return disNums
    }
}

566 重塑矩阵

作者：LeetCode
来源：力扣（LeetCode）
链接：地址

在MATLAB中，有一个非常有用的函数reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1:

输入:
nums = [[1,2],[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。

示例 2:

输入:
nums = [[1,2],[3,4]]
r = 2, c = 4
输出:
[[1,2],[3,4]]
解释:
没有办法将 2 2 矩阵转化为 2 4 矩阵。所以输出原矩阵。

注意：

给定矩阵的宽和高范围在 [1, 100]。
给定的 r 和 c 都是正数。

我的解答

解题思路：

先判断原始矩阵和转换后的新矩阵的元素个数是否相等。
若相等，说明可以转换；若不相等，说明不能转换。
使用“双指针”：rowCount和colCount代表原始矩阵的行和列，依次取出原始矩阵中的元素存放到新矩阵中即可。

/**
 * 执行用时 : 328 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
 * 内存消耗 : 44.9 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution {
    fun matrixReshape(nums: Array<IntArray>, r: Int, c: Int): Array<IntArray> {
        if (r * c != nums.size * nums[0].size) {
            return nums
        }
        val result = mutableListOf<IntArray>()
        var rowCount = 0
        var colCount = 0
        for (_r in 0 until r) {
            val rowArray = mutableListOf<Int>()
            for (_c in 0 until c) {
                rowArray.add(nums[rowCount][colCount])
                colCount++
                if (colCount > nums[rowCount].lastIndex) {
                    rowCount++
                    colCount = 0
                }
            }
            result.add(rowArray.toIntArray())
        }
        return result.toTypedArray()
    }
}

官方题解

作者：LeetCode
链接：题解
来源：力扣（LeetCode）

看了官方题解后，发现我的解答法是“不用额外空间”，不过官方给出的题解思路很相似，复杂度上也都相同，该题并没有特别“巧妙”的解法。

使用队列 [通过]

最简单的方法是通过以行方式读取元素来提取给定矩阵的所有元素。在此实现中，我们使用队列来放置提取的元素。然后，我们可以取出以串行顺序形成的队列元素，并再次按行逐行排列所得到的所需矩阵中的元素。
如果原始矩阵中的元素数量不等于所得矩阵中的元素数量，则不可能形成所得矩阵。

public class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int[][] res = new int[r][c];
        if (nums.length == 0 || r * c != nums.length * nums[0].length)
            return nums;
        int count = 0;
        Queue < Integer > queue = new LinkedList < > ();
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                queue.add(nums[i][j]);
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                res[i][j] = queue.remove();
            }
        }
        return res;
    }
}

不用额外空间 [通过]

我们不必像在暴力方法中那样不必要地使用队列，而是可以在逐行顺序迭代给定矩阵的同时，直接将数字放在结果矩阵中。在将数字放入结果数组时，我们固定一个特定的行，并继续增加列数，直到我们到达cc指示的所需列的末尾。此时，我们通过递增来更新行索引，并将列索引重置为从0开始。因此，我们可以节省队列消耗的空间，以便存储只需要复制到新数组中的数据。

public class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int[][] res = new int[r][c];
        if (nums.length == 0 || r * c != nums.length * nums[0].length)
            return nums;
        int rows = 0, cols = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                res[rows][cols] = nums[i][j];
                cols++;
                if (cols == c) {
                    rows++;
                    cols = 0;
                }
            }
        }
        return res;
    }
}

除法和取模 [通过]

在上一种方法中，我们需要跟踪我们何时到达结果矩阵的列的末尾，并且需要通过每次检查当前索引来更新当前行和列号以放置提取的元素。我们可以利用数学来帮助解决，而不是在每一步都进行限制性检查。

这种方法背后的想法如下。

你知道二维数组是如何存储在主存中的（本质上是一维）吗？它仅在内部表示为一维阵列。
元素 nums[i][j]nums 数组通过使用以下形式的索引以一维数组的形式表示：$ nums [n * i + j]，其中 m 是给定矩阵中的列数。
以相反的顺序查看相同的内容，同时将元素放在结果矩阵中的元素中，我们可以使用 count 变量，该变量对于遍历的每个元素都会递增，就像我们将元素放在一维中一样结果数组。
但是，要将 count 转换回列数为转换回列数为 c 的二维矩阵索引，我们可以获得 res [count / c] [count \％c] 的索引，其中 count / c 是行号和是行号和 count \％c $是列数字。因此，我们可以节省每一步所需的额外检查。

public class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int[][] res = new int[r][c];
        if (nums.length == 0 || r * c != nums.length * nums[0].length)
            return nums;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                res[count / c][count % c] = nums[i][j];
                count++;
            }
        }
        return res;
    }
}

661 图片平滑器

作者：LeetCode
来源：力扣（LeetCode）
链接：地址

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

示例 1:

输入:
[[1,1,1],
[1,0,1],
[1,1,1]]
输出:
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0

注意:

给定矩阵中的整数范围为 [0, 255]。
矩阵的长和宽的范围均为 [1, 150]。

我的解答

思路：“双重嵌套”+“补位”

创建一个新的矩阵，双重嵌套遍历矩阵。
通过“补位”使原矩阵中每个单位周围有8个单位格。
在双重嵌套最内部计算单位的平均值，通过单元在矩阵中的坐标判断是否是“补位”单元，来计算平均值。

/**
 * 执行用时 : 392 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
 * 内存消耗 : 38.3 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution {
    fun imageSmoother(M: Array<IntArray>): Array<IntArray> {
        if (M.isEmpty() || M[0].isEmpty()) return M
        fun getEl(row: Int, col: Int): Int {
            return when {
                row < 0 || row >= M.size -> -1
                col < 0 || col >= M[0].size -> -1
                else -> M[row][col]
            }
        }
        var elCount = 0
        var elSum = 0
        fun handle(el: Int) {
            if (el >= 0) {
                elCount++
                elSum += el
            }
        }
        val resetArray = arrayOfNulls<IntArray>(M.size)
        for (row in M.indices) {
            resetArray[row] = IntArray(M[0].size) { col ->
                elCount = 0
                elSum = 0
                handle(getEl(row - 1, col - 1))
                handle(getEl(row - 1, col))
                handle(getEl(row - 1, col + 1))
                handle(getEl(row, col - 1))
                handle(getEl(row, col))
                handle(getEl(row, col + 1))
                handle(getEl(row + 1, col - 1))
                handle(getEl(row + 1, col))
                handle(getEl(row + 1, col + 1))

                elSum / elCount
            }
        }
        return resetArray as Array<IntArray>
    }
}

精选题解

见我的解答，得瑟一波～

我在看了部分题解后，并没有发现特别好的解题思路，有些解法思路复杂、实现繁琐，并没有我的解法简洁，所以毛（hoz）遂（yan）自（wu）荐（chi）把自己的解法贴了出来。貌似，“矩阵”类的算法题并没有特别好的解法？

再毛（chou）遂（bu）自（yao）荐（lian）一次，我把我的题解也发布到LeetCode上了，点这里查看，欢迎点赞和交流！

941 有效的山脉数组

作者：LeetCode
来源：力扣（LeetCode）
链接：地址

给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

A.length >= 3
在 0 < i < A.length - 1 条件下，存在 i 使得：
- A[0] < A[1] < … A[i-1] < A[i]
- A[i] > A[i+1] > … > A[B.length - 1]

示例 1：

输入：[2,1]
输出：false

示例 2：

输入：[3,5,5]
输出：false

示例 3：

输入：[0,3,2,1]
输出：true

提示：

0 <= A.length <= 10000
0 <= A[i] <= 10000

我的解答

思路：只需要一次循环

要解答该题，首先要找到”山脉”最高点maxElIndex。
在找到maxElIndex前，后面的元素小于等于前面的元素，说明不是有效的”山脉数组”。
在找到maxElIndex后，后面的元素大于等于前面的元素，说明不是有效的”山脉数组”。
排除上面两种情况后，最后再检查一下找到的最高点不能是第一个和最后一个元素。

/**
 * 执行用时 : 288 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
 * 内存消耗 : 38.8 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
class Solution {
    fun validMountainArray(A: IntArray): Boolean {
        var maxElIndex: Int? = null
        A.forEachIndexed { index, el ->
            when {
                // 找到"山脉"最高点
                maxElIndex == null && index-1 >= 0 && index+1 < A.size && el > A[index-1] && el > A[index+1] -> {
                    maxElIndex = el
                    maxElIndex = index
                }
                // 在找到最高点前，后面的元素小于等于前面的元素，说明不是有效的"山脉数组"
                maxElIndex == null && index-1 >= 0 && el <= A[index-1] -> {
                    return false
                }
                // 在找到最高点后，后面的元素大于等于前面的元素，说明不是有效的"山脉数组"
                maxElIndex != null && index-1 >= 0 && el >= A[index-1] -> {
                    return false
                }
            }
        }
        // 最后，找到的最高点不能是第一个和最后一个元素
        return maxElIndex != null && maxElIndex != 0 && maxElIndex != A.lastIndex
    }
}

官方题解

作者：LeetCode
链接：地址
来源：力扣（LeetCode）

线性扫描

我们从数组的最左侧开始扫描，直到找到第一个不满足 A[i] < A[i + 1] 的 i，那么 i 就是这个数组的最高点。如果 i = 0 或者不存在这样的 i（即整个数组都是单调递增的），那么就返回 false。否则从 i 开始继续扫描，判断接下来的的位置 j 是否都满足 A[j] > A[j + 1]，若都满足就返回 true，否则返回 false。

class Solution {
    public boolean validMountainArray(int[] A) {
        int N = A.length;
        int i = 0;
        // walk up
        while (i+1 < N && A[i] < A[i+1])
            i++;
        // peak can't be first or last
        if (i == 0 || i == N-1)
            return false;
        // walk down
        while (i+1 < N && A[i] > A[i+1])
            i++;
        return i == N-1;
    }
}

509 斐波那契数

作者：LeetCode
来源：力扣（LeetCode）
链接：地址

很著名的一道算法，以至于我在没研究算法之前就听说过它的名头。

问题描述

斐波那契数，通常用F(n)表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示：

0 ≤ N ≤ 30

我的解答

递归+缓存

效率稍高，最多会递归计算 N-2 次。使用map缓存数据，多次调用后，会大大地减少递归次数，比较适合应用于实际项目开发。

class Solution {
    private val MAP = mutableMapOf(0 to 0, 1 to 1, 2 to 1)
    /**
     * 执行用时 : 144 ms, 在所有 Kotlin 提交中击败了 100.00% 的用户
     * 内存消耗 : 31.2 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
     */
    fun fib(N: Int): Int {
        if (MAP[N] != null) return MAP[N]!!
        MAP[N] = if (MAP[N-1] != null) {
            MAP[N-1]!!+MAP[N-2]!!
        } else {
            fib3(N-1)+MAP[N-2]!!
        }
        return MAP[N]!!
    }
}

递归

代码最少的一个解法，缺点是效率低，因为会递归计算 N-2+N-1-2 次。

class Solution {
    fun fib(N: Int): Int {
        return when(N) {
            0 -> 0
            1,2 -> 1
            else -> fib(N-1)+fib(N-2)
        }
    }
}

11 盛最多水的容器

作者：LeetCode
来源：力扣（LeetCode）
链接：地址

问题描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

盛最多水的容器

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

我的解答

看到这道题后，我经过一番思考，想出了两种方法：暴力法、动态规划（不推荐）。

暴力法

/**
 * 执行用时 : 632 ms, 在所有 Kotlin 提交中击败了 12.50% 的用户
 * 内存消耗 : 37.7 MB, 在所有 Kotlin 提交中击败了 100.00% 的用户
 */
import kotlin.math.abs
import kotlin.math.min
import kotlin.math.max
class Solution {
    fun maxArea(height: IntArray): Int {
        var maxArea = 0
        height.forEachIndexed { p1, v1 ->
            for(p2 in p1+1..height.lastIndex) {
                maxArea = max(maxArea, abs(p1 - p2) * min(v1, height[p2]))
            }
        }
        return maxArea
    }
}

动态规划（不推荐）

思路：

形成容器需有两条垂直线，计算盛水量，需要两个因素：两条垂直线在X轴的距离 * 较短的一条垂直线长度。
那么就可以使用其中任意一个因素，从大到小依次计算容器，这样可以减少遍历次数。

注意：

上面的思路初看起来没有问题，但题目要求求解最大容器，那么就没有办法知道根据计算因素从大到小计算的容器大小是否是最大容器，虽然最终还是能求解，但执行用时比暴力求解还高。代码实现比较复杂，这里就不贴出来了献丑了，惭愧～

官方题解

作者：LeetCode
链接：地址
来源：力扣（LeetCode）

暴力法

在这种情况下，我们将简单地考虑每对可能出现的线段组合并找出这些情况之下的最大面积。

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
        return maxarea;
    }
}

复杂度分析：

时间复杂度：O(n^2)，计算所有 frac{n(n-1)}{2} 种高度组合的面积。
空间复杂度：O(1)，使用恒定的额外空间。

双指针法

这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。此外，我们会使用变量maxarea 来持续存储到目前为止所获得的最大面积。在每一步中，我们会找出指针所指向的两条线段形成的区域，更新maxarea，并将指向较短线段的指针向较长线段那端移动一步。

此解有幻灯片进行动态的展示，可以更好的理解该算法，如果文字描述理解困难，建议看下幻灯片。

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0, l = 0, r = height.length - 1;
        while (l < r) {
            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
}

复杂度分析：

时间复杂度：O(n)，一次扫描。
空间复杂度：O(1)，使用恒定的空间。

18 四数之和

作者：LeetCode
来源：力扣（LeetCode）
链接：地址

问题描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：

[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

我的解答

预先告知，我是没能求解，23333～。第一时间想到的暴力法超时，然后想到了双指针法，但时间不充裕就没尝试代码实现，直接看了别人的解答，学到了“拍平”的思路。中等难度的算法果然又开阔了解题思路～。

暴力法（超时，不可取）

修改了三次答案，最后一次的答案能求出正确结果，但是超出了时间限制。很遗憾，暴力法并不能用于求解该题。

class Solution {
    /**
     * 超出时间限制
     * 本地执行最后执行的输入，耗时：137 ms
     * 测试用例执行最后执行的输入，耗时: 328 ms
     */
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val minSize = 4
        if (nums.size < minSize) return emptyList()
        fun sum(els: List<Int>): Int {
            var sum = 0
            els.forEach {
                sum += it
            }
            return sum
        }
        fun filterRepeat(els: List<Int>): Boolean {
            val elsString = els.sorted().toString()
            result.forEach {
                if (it.sorted().toString() == elsString) {
                    return false
                }
            }
            return true
        }
        for (index1 in 0..(nums.size - minSize)) {
            for (index2 in index1 + 1 until nums.size) {
                for (index3 in index2 + 1 until nums.size) {
                    for (index4 in index3 + 1 until nums.size) {
                        val els = listOf(
                            nums[index1], nums[index2],
                            nums[index3], nums[index4]
                        )
                        if (target == sum(els)) {
                            if (filterRepeat(els)) {
                                result.add(els)
                            }
                        }
                    }
                }
            }
        }
        return result
    }
}

精选题解

作者：jerry4free
链接：地址
来源：力扣（LeetCode）

双指针法

模拟两数之和，采用双指针，时间复杂度是O(N^3)。防止重复需要判断。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        
        int start = 0;
        int end = n-1;
        for (int i = start; i < n-3; i++){
            if (i > start && nums[i] == nums[i-1]){    // 确保i不重复
                continue;
            }
            for (int j = i+1; j < n-2; j++){
                if (j > (i+1) && nums[j] == nums[j-1]){    // 确保i不重复
                    continue;
                }
                int k = j+1;
                int l = n-1;
                while (k < l){
                    if (k > (j+1) && nums[k] == nums[k-1]){   // 确保k不重复
                        k++;
                        continue;
                    }
                    if (l < (n-1) && nums[l] == nums[l+1]){   // 确保l不重复
                        l--;
                        continue;
                    }
                    int s = nums[i] + nums[j] + nums[k] + nums[l];
                    if (s == target){
                        ret.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        k++;
                        l--;
                    } else if (s < target){
                        k++;
                    } else {
                        l--;
                    }
                }
            }
        }
        return ret;
    }
}

哈希表

如何才能O(N^2)呢？需要将两层循环拍平，拍成一层循环，那么就可以达到O(N^2).
可以将2层的数字预先计算求和，存储到哈希表里方便快速查找。防止重复可以用集合

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        HashMap<Integer, List<List<Integer>>> t = new HashMap<>();
        HashSet<List<Integer>> ret = new HashSet<>();
        Arrays.sort(nums);
        int n = nums.length;
        
        int start = 0;
        int end = n-1;
        for (int i = start; i <= end-1; i++){
            for (int j = i+1; j <= end; j++){
                int s = nums[i] + nums[j];
                List<Integer> tmp = new ArrayList<>();
                tmp.add(i);
                tmp.add(j);
                if (t.containsKey(s)){
                    // TODO:
                    List<List<Integer>> tmp1 = t.get(s);
                    tmp1.add(tmp);
                    t.put(s, tmp1);
                } else {
                    // TODO:
                    List<List<Integer>> tmp1 = new ArrayList<>();
                    tmp1.add(tmp);
                    t.put(s, tmp1);
                }
            }
        }
        start = 0;
        end = n-1;
        for (int i = start; i <= end-1; i++){
            for (int j = i+1; j <= end; j++){
                int s = target-(nums[i] + nums[j]);
                if (t.containsKey(s)){
                    // TODO:
                    for (List<Integer> pairs: t.get(s)){
                        int k = pairs.get(0);
                        int l = pairs.get(1);
                        if (j != k && j != l && i != k && i != l){
                            List<Integer> tmp = new ArrayList<>();
                            tmp.add(nums[k]);
                            tmp.add(nums[l]);
                            tmp.add(nums[i]);
                            tmp.add(nums[j]);
                            tmp.sort(Comparator.comparingInt(o -> o));
                            ret.add(tmp);
                        }
                    }
                }
            }
        }
        return new ArrayList<>(ret);
    }
}