20200531
Plan
leetcode 每日一题
Notes
- 全排列 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
解法：比较经典的回溯法，从其中选一个数字，获取剩下的数组的全排列，然后把选择的数字加在最后。当剩下的数组中元素个数为1时，直接返回。
- 二叉树的右视图 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释:
1 <---
/
2 3 <---
\
5 4 <---
解法：用层序遍历就可以，每一层记录最右边的元素。go里面因为没有自带队列，所以用了两个slice，当前slice记录当前这层的元素，另一个记录下一层，然后把另一个数组的元素赋给当前slice。有一个地方需要注意，go里面如果直接用copy（A,B），且A的长度小于B，那么只会复制A长度的B。所以最好是先把A删除，即A=A[0:0]，然后再把B全部append到A。
面试题56 - I. 数组中数字出现的次数 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1：
输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1] 示例 2：
输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]
解法：因为空间复杂度要求O（1），所以不能用额外的map记录。如果只有一个数字与其他数字不同，那么把全部的数字异或就可以得到这个数字。现在要想想如何扩展。分为如下几步： 1.将全部数字异或，可以得到两个不同数字的异或结果，记为A。 2.将A&（-A），可以得到A中最右边为1且其他位数都为0的结果，记为lowbit. 原理：假设A的十进制为12，二进制为1100,因为前面还有一个符号位，所以实际上12为01100，那么-12为10100（符号位取反，剩余位取反+1），二者异或结果为00100。 3.考虑将原来的数组分为不同的两组，其中lowbit为1的位置也为1的元素为1组，lowbit为1的位置为0的元素为另一组，这样的原因是为了把原数组中两个不同的数分开，然后再分开的两个子数组中，分别全部异或，就可以得到两个结果。