20200505
Plan
leetcode每日一题
Notes
今天做的三道题都比较简单，记录一些比较增加效率的方法。
面试题 10.01. 合并排序的数组 给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。初始化 A 和 B 的元素数量分别为 m 和 n。
示例: 输入: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
刚开始的想法是暴力法，遍历B然后遍历A找到需要插入的位置，然后再插入。插入需要整体后移，所以时间复杂度时O（nmm） 后来想可以先把B放进A的最后，然后用快排排序，时间复杂度是O（（m+n）log(m+n)）。 上面两种方法都没有利用AB是有序数组的特性，还有一种高效的方法，设置两个指针pointerA和pointerB分别指向A/B有元素的最尾端（比如示例中都指向index=2），再设置一个指针tail指向A数组的最尾端（index=5），然后两个指针都从后往前遍历并比较，大的就放在A的最尾端。 结束时需要判断：如果是pointerB为0，则不需要做任何操作。如果是pointerA为0，则需要把pointerB前面的元素放在tail前面。
- 最长回文串 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意: 假设字符串的长度不会超过 1010。
示例 1: 输入: "abccccdd"
输出: 7
解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
这道题就统计每个字符出现的次数，次数为偶数的可以直接组成回文；次数为奇数的，第一个字符的次数可以直接加，因为可以有一个字符在中间，之后的次数为奇数的字符都要减1变成偶数然后累加即可。