上一篇博客提到了HTTPS，今天就来回顾下HTTPS连接过程中的各个阶段和使用的加密机制吧。维基百科对其定义如下：

Hypertext Transfer Protocol Secure (HTTPS) is an extension of the Hypertext Transfer Protocol (HTTP). It is used for secure communication over a computer network, and is widely used on the Internet.[1][2] In HTTPS, the communication protocol is encrypted using Transport Layer Security (TLS) or, formerly, Secure Sockets Layer (SSL). The protocol is therefore also referred to as HTTP over TLS,[3] or HTTP over SSL.

简单的说，HTTPS仍然用HTTP进行通讯，但在此基础上使用SSL/TLS协议加密封包。引入该协议主要是因为HTTP协议明文传输数据，存在以下三大问题：

1. 由于数据是明文传输的，容易造成用户隐私泄漏。
2. 网站可靠性存疑，可能是恶意攻击者伪装。
3. 数据的完整性无法证明，可能被篡改。

解决方案

针对问题一，直观的解决方案是对数据进行加密。对称加密算法是一种常见的加密方式，加密/解密使用相同的密钥。使用了该加密算法后，黑客即使截获了数据，若没有密钥就无法解密。但是此时存在的问题是，浏览器/服务器如何发送密钥呢？密钥在传输过程中可能被黑客截获，那么数据就不再安全了。

此时可引进非对称加密算法解决上述问题。服务器可将「公钥」发送给用户，用户使用该「公钥」加密数据。由于只有服务器拥有对应的「私钥」可以解密数据。黑客即使截获了数据也无法破解。

这种方式下，用户发送给服务器的数据就都是经过加密的。但是，如果服务器要给用户发送数据呢？因为「公钥」是在网上传播的，用户可以拿「公钥」解密服务器发送的数据，黑客同样也可以。看来这时候一对公/私钥就不够了，用户也需要将自己的「公钥」发送给服务器。服务器发送数据前使用该「公钥」加密数据。这样就只有对应的用户能解密数据了。

这样看起来就比较"完美"了--但其实仍然存在问题：黑客可以截获服务器发送的「真公钥」，然后替换为「假公钥」再发送给用户。用户此时并没有感知，还以为是服务器发送的「真公钥」。用户使用黑客生成的「假公钥」加密数据，黑客就可以使用「假私钥」解密。知道了数据内容后，黑客甚至可以对数据进行修改，然后再使用服务器的「真公钥」加密后发给服务器。由此，黑客完成了用户数据的窃取和篡改。

上述攻击称为"中间人攻击"，对于用户和服务器而言，都没有感知到存在第三方。究其原因，主要是用户无法判别获取到的「公钥」的合法性。此时就需要使用「数字证书」来为网站和「公钥」做背书，「数字证书」是由权威机构签发。「数字证书」上会包含「公钥」、证书的授予机构、证书所有者、有效时间等信息。权威机构（Certificate Authority）先对上述证书中包含的信息做一次Hash计算，再使用自己的私钥对Hash计算的结果进行加密（加密结果称为数字签名）。用户拿到证书后，使用权威机构的「公钥」对数字签名进行解密，再对数字证书里的信息也做一次Hash计算。如果解密结果和Hash计算结果相同，则证明证书为真。网站和「公钥」都是可信的。

这里需要注意的一点是：用户持有权威机构的「公钥」。那么用户是怎么获得权威机构的「公钥」呢？其实这是预装在操作系统中的。所以千万不要安装来历不明的系统，否则就相当于在裸奔。

至此，黑客就彻底无法破解、篡改用户的数据了。网站方也能够证明自身的合法性。（即解决了HTTP的第二、三个问题）

趁着周末的时间给博客加了HTTPS，加上前段时间的服务器购买、环境搭建、域名备案、公安备案等一系列事项，博客算是初步搭建起来了。后面有空了再继续完善评论、点赞等功能。

今天是开始执行「每日一题」计划的第32天，刚开始以形成习惯为主，先从Easy题开始，每天坚持做一题。最初的想法是夯实基础，三五年后跳槽时有更多选择权。无奈最近互联网开始了"毕业季"，计划可能要被迫提前。因此开始做力扣的剑指Offer计划。早期为形成习惯，每天做完题后在博客"打卡"。坚持一个月后习惯基本养成了，后续不再更新刷题内容到博客中。后面博客的技术部分会更侧重学习笔记、知识点归纳总结等。

最近的"毕业季"，着实让我焦虑了很久。作为工作不到一年的校招毕业生，不再有校招生这层身份庇护，论工作经验又不及工作多年的社招员工。且互联网大环境不乐观又导致了招聘岗位收缩... 这种情况下，最好的选择似乎是苟在鹅厂，提高自身能力，静静等待互联网形势好转。然而，鹅厂各个BG的毕业典礼轮番开启，也为这种策略蒙上了一层不稳定因素。

想起来去年很喜欢的一部影视作品《沙丘》中的一段经典台词：

“我绝不能恐惧。恐惧是思维杀手。恐惧是带来彻底毁灭的小小死神。我将正视恐惧，任它通过我的躯体。当恐惧逝去，我会打开心眼，看清它的轨迹。恐惧所过之处，不留一物，唯我独存。”

依然无法做到完全「顺其自然」或者说「听天由命」，毕竟这可能会一定程度上影响后续的发展方向甚至人生轨迹。时代的一粒灰，落在个人头上就是一座山。既然不能完全放下「恐惧」，那就带着这份「恐惧」继续前行吧。

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1

解题思路：动态规划+滚动窗口。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int fib(int n) {
        int p = 0;
        int q = 1;
        int ans = 0;
        final int MOD = 1000000007;
        if (n < 2) return n;
        while (n > 1) {
            ans = (p + q)% MOD;
            p = q;
            q = ans;
            n--;
        }
        return ans;

    }
}

题目来源：剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解题思路：思路同上一题，动态规划+滚动窗口。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int numWays(int n) {
        final int MOD = 1000000007;
        if (n == 0) return 1;
        if (n < 3) return n;
        int p = 1;
        int q = 2;
        int ans = 0;
        while (n > 2) {
            ans = (p + q) % MOD;
            p = q;
            q = ans;
            n--;
        }
        return ans;
    }
}

题目来源：剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

解题思路：维护一个最低价格，维护一个最大获利值。遍历整个数组，若价格高于最小值，则判断获利是否大于之前的最大获利；若当前价格小于之前维护的最小价格，则更新最小价格。最后返回最大获利。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0 ) return 0;
        int min = prices[0];
        int profit = 0;
        for (int price : prices) {
            if (price > min){
                profit = Math.max(profit, price - min);
            } else {
                min = price;
            }
        }
        return profit;

    }
}

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

解题思路：如果树A或树B为空则不满足，直接返回。否则判断B是否为A节点的子结构，或A的左（右）子树的子结构。在递归函数中进行判断：如果B节点为空，表明已经匹配完成，返回true；如果B不为空，而A为空，或A、B节点的值不相同，则匹配失败，返回false；如果A、B的值相同则继续比较A、B的左右子树。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || 
        isSubStructure(A.left, B) || isSubStructure(A.right, B));

    }

    boolean recur(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);

    }
}

题目来源：剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

解题思路：对树的根节点调用递归函数。递归函数中执行：若节点为空直接返回；否则交换该节点的左右子树，并分别对其调用递归函数，最后返回节点本身。

时间复杂度：O(N)

空间复杂度：O(1)

 
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        return recur(root);

    }

    TreeNode recur(TreeNode root) {
        if (root == null) return null;
        TreeNode tmpNode = root.left;
        root.left = recur(root.right);
        root.right = recur(tmpNode);
        return root;
    }
}

题目来源：剑指 Offer 28. 对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

解题思路：如果根节点为空则满足，直接返回，否则将其左右子树传入递归函数。

递归函数执行过程如下：如果传入的两个节点都为空，则判断结束，条件满足；若有一个不为空或者两个节点的值不相同，则判断结束，条件不满足；如果两个节点的值相同，则继续递归调用，分别比较左左与右右、左右与右左是否满足。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return (root == null) || (recur(root.left, root.right));

    }

    boolean recur(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

解题思路：广度优先遍历二叉树。若根节点非空，则将其压入队列。当队列非空时，从队列中取出一个节点，将值加入可变列表。依次将其左右子树（非空）压入队列。从可变列表中取出值，依次放入数组，返回结果数组。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    fun levelOrder(root: TreeNode?): IntArray {
        if (root == null) return intArrayOf()
        val queue = LinkedList<TreeNode>()
        val arr = mutableListOf<Int>()
        queue.offer(root)
        while (queue.isNotEmpty()) {
            val node = queue.poll()
            arr.add(node.`val`)
            node.left?.let {
                queue.offer(node.left)
            }
            node.right?.let {
                queue.offer(node.right)
            }
        }

        val res = IntArray(arr.size)
        arr.forEachIndexed { index, i ->
            res[index] = i
        }
        return res

    }
}

题目来源：剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

解题思路：与上一题思路类似，这题复杂之处在于需要将二叉树分层输入到不同的字数组中。借鉴@Krahets的思路，使用队列的size来判断当前层遍历是否结束。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    fun levelOrder(root: TreeNode?): List<List<Int>> {
        val queue = LinkedList<TreeNode>()
        val res = ArrayList<ArrayList<Int>>()
        if (root != null) queue.offer(root) 
        while (queue.isNotEmpty()) {
            val tmp = ArrayList<Int>()
            for (i in 0 until queue.size) {
                val node = queue.poll()
                tmp.add(node.`val`)
                node.left?.let {
                    queue.offer(it)
                }
                node.right?.let {
                    queue.offer(it)
                }
            }
            res.add(tmp)
        }
        return res   

    }
}

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路：从二维数组的左上角或者右下角开始遍历。若查找目标小于当前位置的值，则向上走；反之向右侧走，直至找到目标值后返回true。若遍历到数组边界仍然未找到，则返回false。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun findNumberIn2DArray(matrix: Array<IntArray>, target: Int): Boolean {
        var row = matrix.size - 1
        var col = 0
        while (row >= 0 && col < matrix[0].size) {
            if (matrix[row][col] == target) {
                return true
            } else if (matrix[row][col] < target) {
                col++
            } else {
                row--
            }
        }
        return false
    }

}

题目来源：剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

解题思路：从前往后遍历，找到第一个比前一个元素小的值，即为最小值。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun minArray(numbers: IntArray): Int {
        var res = 0
        var cur = numbers[0]
        for (pos in 0 until numbers.size) {
            if (numbers[pos] < cur) {
                return numbers[pos]
            } 
            cur = numbers[pos]
        }
        return numbers[0]
    }
}

题目来源：剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

解题思路：创建一个长度为26的数组，用于存放每个字母出现的频率。遍历一遍字符串，每遇到一个字母即将数组的对应位置的值自增。再次遍历字符串，从数组中找对应字母的出现频率。找到频率为1的字母即返回。若遍历完成未找到，则返回空格。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun firstUniqChar(s: String): Char {
        var charArr = IntArray(26)
        for (pos in 0 until s.length) {
            charArr[s[pos] - 'a']++
        }
        for (pos in 0 until s.length) {
            if (charArr[s[pos] - 'a'] == 1) {
                return s[pos]
            }
        }
        return ' '
    }
}

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

解题思路：比较简单的做法是依次遍历，然后存HashMap。（时间、空间复杂度均为O(N)） 如果要求空间复杂度为O(1),则可以利用题目数据的特点，使用「交换位置法」和「置负数」法。

这里使用了「交换位置法」。依次遍历遍历数组，若当前的值与下标不相同，则将其与「当前值为下标」的数字相互交换，若这两个数字是相同的，则直接返回。注意，交换完成后仍然继续判断当前位置，直到下标和值相同，再把位置后移。

若遍历完数组，则说明不存在相同数字，返回-1。（按照题意不会出现这种情况）

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun findRepeatNumber(nums: IntArray): Int {
        var pos = 0
        while (pos < nums.size) {
            if (nums[pos] == pos) {
                pos++
                continue
            }

            if (nums[nums[pos]] == nums[pos]) {
                return nums[pos]
            }

            val tmp = nums[pos]
            nums[pos] = nums[tmp]
            nums[tmp] = tmp
        }
         return -1
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

解题思路：这题太简单了，就不解释了。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun search(nums: IntArray, target: Int): Int {
        var count = 0
        for (num in nums) {
            if (num == target) {
                count++
            }
        }
        return count
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

解题思路：依照题目特性，遍历数组时，若某个位置的值与下标不相同，说明缺了这个数，直接返回。若遍历完成，说明缺了最后一个数字，返回数组长度即可。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun missingNumber(nums: IntArray): Int {
        for (pos in 0 until nums.size) {
            if (nums[pos] != pos) {
                return pos
            }
        }
        return nums.size

    }
}

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

解题思路：使用StringBuilder，依次遍历字符串的字符，判断是否为空格，如果是空格则替换为"%20"。遍历完成后转换为string返回。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    fun replaceSpace(s: String): String {
        var sb = StringBuilder()
        for (pos in 0 until s.length) {
            var str = if (s[pos] == ' ') {
                "%20"
            } else {
                s[pos].toString()
            }
            sb.append(str)
        }
        return sb.toString()

    }
}

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

解题思路：使用StringBuilder，从n开始依次遍历字符串的字符，追加到StringBuilder中即可。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    fun reverseLeftWords(s: String, n: Int): String {
        val sb = StringBuilder()
        for (pos in n until s.length) {
            sb.append(s[pos].toString())
        }
        for (pos in 0 until n) {
            sb.append(s[pos].toString())
        }
        return sb.toString()

    }
}

ps：今天的两道题目整体比较简单，没有特别需要注意的地方。第二题看其他人的解答时有个取模的小技巧可以学习下。

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder res = new StringBuilder();
        for(int i = n; i < n + s.length(); i++)
            res.append(s.charAt(i % s.length()));
        return res.toString();
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/solution/mian-shi-ti-58-ii-zuo-xuan-zhuan-zi-fu-chuan-qie-p/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

解题思路：首先遍历一遍链表，获得链表长度。然后创建对应长度的数组，再从头遍历链表，依次存到数组中，存放的时候从右侧开始放。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun reversePrint(head: ListNode?): IntArray {
        var length = 0
        var p = head
        while (p != null) {
            p = p.next
            length++
        }
        var intArray = IntArray(length)
        p = head
        while (p != null) {
            intArray.set(--length,p.`val`)
            p = p.next
        }
        return intArray

    }
}

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

解题思路：创建一个新节点，依次将原来链表上的节点接到新节点后面。注意接的时候不要出现"断链"问题。最后返回新节点的后续节点即可。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        val resNode = ListNode(0)
        var p = head
        var pNext = head?.next
        while (p != null) {
            p.next = resNode.next
            resNode.next = p

            p = pNext
            pNext = pNext?.next
        }
        return resNode.next

    }
}

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

解题思路：（这题自己没想出来，参考的官方解法。）核心思想是用map存放了新旧节点的对应关系。对一个节点做copyRandomList操作，即先判断map中是否存在该节点，如果有说明已经创建过，直接返回即可。如果没有则创建一个新的节点，复制原节点的值。并将这两个节点存到map中。然后新节点的next和random指针同样通过调用copyRandomList获得。

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    HashMap<Node, Node> map = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) return head;

        if (!map.containsKey(head)) {
            Node newNode = new Node(head.val);
            map.put(head, newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }

        return map.get(head);


        
    }
}

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解题思路：定义两个栈inStack和outStack。入队操作比较简单：队列中元素入队时就push到inStack中。出队列时统一"倒"到outStack中，顺序上做了一次调换。要考虑以下几种情况：1.如果outStack中还有元素，直接pop即可；2.如果outStack没有元素，inStack也没有元素了，表明队列已经为空返回-1；3.如果outStack没有元素，inStack仍然有元素。先将所有元素"倒"到outStack中，然后弹出顶部元素即可。

class CQueue() {
    val inStack = Stack<Int>()
    val outStack = Stack<Int>()

    fun appendTail(value: Int) {
        inStack.push(value)
    }

    fun deleteHead(): Int {
        if (outStack.isEmpty().not()) {
            return outStack.pop()
        }

        if (inStack.isEmpty()) return -1

        while (inStack.isEmpty().not()) {
            outStack.push(inStack.pop())
        }

        return outStack.pop()

    }

}

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

解题思路：定义两个栈（一个栈存放压入的元素，一个栈存放每次更新后的最小值）和一个变量记录当前最小值。每次压入一个元素，都判断是否小于等于当前最小值，如果满足就将其存到最小数栈。要注意的是「等于」的情况也需要压入。每次弹出一个元素，就和最小值栈的栈顶比较下是否相同，如果相同则弹出一个元素。此时需要更新当前最小值变量。

class MinStack() {

    /** initialize your data structure here. */
    val stack = Stack<Int>()
    val minStack = Stack<Int>()
    var curMin = Int.MAX_VALUE
    
    fun push(x: Int) {
        stack.push(x)
        if (x <= curMin) {
            curMin = x
            minStack.push(x)
        }
    }

    fun pop() {
        var popNum = stack.pop()
        if (curMin == popNum) {
            minStack.pop()
            if (minStack.isEmpty().not()) {
                curMin = minStack.peek()
            } else {
                curMin = Int.MAX_VALUE
            }
        }

    }

    fun top(): Int {
        return stack.peek()
    }

    fun min(): Int {
        return curMin
    }

}

难度等级：Easy

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"
示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

思路：这里采用了模拟数字按位累加的做法，“逢二进一“。把累加的结果放到StringBuilder中，最后倒置一次（因为累加是从个位加起的）。

ps：这里有点坑的是一开始误以为kotlin的Char类型的toInt()（已被废弃，使用code属性替代）方法可以直接把字符转换为数字，其实这样直接转换得到的是该数字对应的ASCII码。需要先把Char转换为String再toInt()。

class Solution {
    fun addBinary(a: String, b: String): String {
        var posA = a.length - 1
        var posB = b.length - 1
        var carry = 0
        val sb = StringBuilder()
        while (posA >= 0 || posB >= 0 || carry > 0) {
            var a = if (posA >= 0) a[posA--].toString().toInt() else 0
            var b = if (posB >= 0 ) b[posB--].toString().toInt() else 0
            var sum = a + b+ carry
            val realSum = if (sum == 2) { 
                carry = 1
                0
             } else if(sum == 3) {
                 carry = 1
                 1
             } else {
                 carry = 0
                 sum
             }
             sb.append(realSum)
        }

        return sb.toString().reversed()


    }
}

难度等级：Easy

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：

输入：digits = [0]
输出：[1]

思路：本题题意还是比较好理解。直观的想，如果最后一位数字不是9，直接最后一位数字加1即可。需要考虑的是一些特殊情况，即末尾包含多个连续的9需要持续向前进位。最极端的情况是所有位置上都是9，则需要返回一个比原来数组长1的数组，首位为1，其他位置为0。

ps：我的解法是在力扣用户inuter的解法基础上调整了下。他的解法使用了取模操作，比较耗时。

class Solution {
    fun plusOne(digits: IntArray): IntArray {
        val size = digits.size
        for (pos in size - 1 downTo 0) {
            val curNum = digits.get(pos) + 1
            if (curNum == 10) {
                digits.set(pos,0)
            } else {
                digits.set(pos, curNum)
                return digits
            }
        }

		// 所有位都为9
        return IntArray(size + 1) { i ->
            if (i == 0) 1 else 0
        }
    }
}

难度等级：Easy

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为5。
示例 2：

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为4。
示例 3：

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为6的“joyboy”。

思路：从前往后依次遍历字符串的字符。维护一个变量curLen记录当前单词的长度，维护一个变量LastLen记录上一个单词的长度。若当前字符为空格，且curLen不为0，表示前一个位置为单词的结束。将LastLen赋值为curLen的值，同时将curLen置0；若当前字符不是空格，说明该单词仍未结束，则curLen自增1。

当整个字符串遍历完后，判断curLen是否为0。若其为0，则表示最后字符串最后不是空格，直接返回curLen；若curLen表示最后为空格，则返回LastLen。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    fun lengthOfLastWord(s: String): Int {
        var curLen = 0
        var lastLen = 0
        for (pos in 0 until s.length) {
            var curChar = s.get(pos)
            if (curChar == ' ' && curLen != 0) {
                lastLen = curLen
                curLen = 0
            } 
            
            if (curChar != ' ') {
                curLen++
            }
        }

        return if (curLen != 0) {
            curLen
        } else {
            lastLen
        }
    }
}

PS:看了LeetCode的官方解法，发现我的解法还是太蠢了，从后往前遍历会方便很多，贴一下官方的答案。

class Solution {
    public int lengthOfLastWord(String s) {
        int index = s.length() - 1;
        while (s.charAt(index) == ' ') {
            index--;
        }
        int wordLength = 0;
        while (index >= 0 && s.charAt(index) != ' ') {
            wordLength++;
            index--;
        }
        return wordLength;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/length-of-last-word/solution/zui-hou-yi-ge-dan-ci-de-chang-du-by-leet-51ih/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

难度等级：Easy

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

子数组 是数组中的一个连续部分。

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

思路：维护一个变量 max  作为输出的结果，即连续子数组的最大值。cur 变量为子数组累加至当前位置后的累加结果。pre 变量为前置数组的累积结果。依次循环遍历整个数组，将当前累加和与max比较大小，更新最大值。如果当前累加和小于0，则对后续数组累加和一定没有正向收益，因此把pre更新为0；如果当前累加和大于0，则对后续数组累加有正收益，pre加上当前位置的值。遍历完成后返回max即可。

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var max = nums.get(0) 
        var pre = 0

        for (pos in 0 until nums.size) {
            var cur = pre + nums.get(pos)
            max = Math.max(max, cur)
            if (cur > 0) {
                pre += nums.get(pos)
            } else {
                pre = 0
            }

        }
        return max
    }
}