理需求逻辑理的要精神分裂了，过来刷刷题换个心态。
数组中重复的数据
题目：给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
思路：这个题似曾相识。主要是时间空间复杂度的要求有点难度。这里一个惯性的想法就是标记。当出现二次标记说明出现两次。我去代码实现下。
实现了，性能一般，代码很简单，就是一个标记判断，我直接贴代码：
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
for(int i = 0;i<nums.length;i++){
int idx = Math.abs(nums[i]);
if(nums[idx-1]>0) {
nums[idx-1] = -nums[idx-1];
}else {
res.add(idx);
}
}
return res;
}
}
现在贴出来的代码是我一次次精简后的结果，其实就是获取每个元素的值，然后因为元素的范围限制，所以用这个元素的值-1的下标去表示（元素值的范围是1 ≤ a[i] ≤ n （n为数组长度））。然后因为最多只会出现两次，所以只要第二次是负数就记录就行了。只要分析明白题意还是很好理解的，唯一的点就是说不使用额外空间，所以我的第一版本是没有idx这一常量定义的，处处都用的 Math.abs(nums[i])，可想而知性能不好，所以我改动了一下。目前为止题目要求都做到了，就是性能不太好我去瞅瞅性能排行第一的代码。
// 要求： 空间复杂度为 O(1)
// 时间复杂度 O(n)
// 突破点为值的范围
// 标志是否出现过： 正负号表示
// 出现一次标定为负， 出现两次标定为正好
// 两次pass
// 区别没出现过的值
// mod 标志， 类似于赛列表
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
int n = nums.length;
for(int i=0; i<n; i++){
nums[((nums[i]-1) % n)] += n;
}
for(int i=0; i<n; i++){
if(nums[i] >= 2*n+1){
res.add(i+1);
}
}
return res;
}
}
不是，不使用额外空间和空间复杂度O(1)是一样的么？我是长见识了啊，反正思路差不多都是标记，就是具体怎么标记而已。我还特意去群里问了大佬，
image.png
这个题过，下一题。
两数相加2
题目：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
思路：这个题怎么说呢，说简单也简单，那就是没有任何限制条件，我最直接的方法就是两个链表解释成字符串进行运算。然后再把运算后的字符串拆分成链表，反正我觉得是能实现的（之所以用字符串而不是数字就是怕这个链表超过数字范围），先去试试。
在实现的过程中发现这个字符串处理太麻烦了，而且题目说到了翻转，所以这里立刻有个数据结构出现在脑子里：先入后出的栈，利用栈的先入后出的数据结构实现先从小位数开始计算的需求，我先直接贴代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
while(l1 != null){
s1.add(l1.val);
l1 = l1.next;
}
while(l2 != null){
s2.add(l2.val);
l2 = l2.next;
}
ListNode res = null;
int cur = 0;
while(!s1.isEmpty() || !s2.isEmpty() || cur != 0){
int sum = (s1.isEmpty()?0:s1.pop())+(s2.isEmpty()?0:s2.pop())+cur;
if(sum>=10){
cur = 1;
sum -= 10;
}else{
cur = 0;
}
ListNode temp = new ListNode(sum);
temp.next = res;
res = temp;
}
return res;
}
}
代码逻辑比较简单，而且这里其实有个小技巧：进位最多进1位，所以只要判断sum是不是大于等于10就行了。代码挺麻烦的，入栈，然后反向挂结果树。说实话这个性能都有点超出我的预期了，竟然超过百分之六十的人，哈哈。
我直接去看性能排行第一的代码了：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int len1 = len(l1);
int len2 = len(l2);
if(len1 < len2){
l1 = fill(l1, len2-len1);
}else{
l2 = fill(l2, len1-len2);
}
int bit = addTwoNumbers1(l1, l2);
if(bit > 0){
ListNode root = new ListNode(bit);
root.next = l1;
return root;
}
return l1;
}
public int addTwoNumbers1(ListNode l1, ListNode l2){
if(l1 == null || l2 == null){
return 0;
}
int bit = addTwoNumbers1(l1.next, l2.next);
int sum = l1.val + l2.val + bit;
if(sum >= 10){
l1.val = sum - 10;
return 1;
}else{
l1.val = sum;
return 0;
}
}
private ListNode fill(ListNode l, int len){
if(len == 0){
return l;
}
ListNode root = new ListNode(0);
ListNode c = root;
for(int i=1;i<len;i++){
c.next = new ListNode(0);
c = c.next;
}
c.next = l;
return root;
}
private int len(ListNode node){
int len = 0;
ListNode c = node;
while(c != null){
len++;
c = c.next;
}
return len;
}
}
当我觉得我写的已经够麻烦的时候，大佬用事实告诉我我还是太天真。emmmm....在能看懂但是自己写不会去这么写的范围内吧。这个题实现其实很简单，所以不多说了，下一题。
序列化和反序列化二叉搜索树
题目：序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。编码的字符串应尽可能紧凑。
注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
思路：简单来说题目有点没看懂。编码的字符串尽可能紧凑是说生成的字符串尽可能短？而且我记得是两个树的遍历才能确定一棵树（这句话的表述有点问题，大概是知道一个树的前序遍历中序遍历才能确定唯一一个树）。我去尝试想想这道题。再看了好几遍这个题，我觉得还是刚刚那个观点，转化成的字符串是一个前序遍历的一个中序遍历的，然后还原的时候也能还原回来。这样也能理解这个编码的字符串尽可能紧凑是什么意思了。
我先直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
StringBuilder ans = new StringBuilder("");
if(root!=null){
queue.add(root);
}
while(!queue.isEmpty()){
TreeNode cur = queue.poll();
if(cur==null){
ans.append("N ");
continue;
}else{
ans.append(cur.val).append(" ");
}
queue.add(cur.left);
queue.add(cur.right);
}
return ans.toString().trim();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("")){
return null;
}
String[] ss = data.split(" ");
Queue<TreeNode> queue = new LinkedList<>();
int val = Integer.parseInt(ss[0]);
TreeNode root = new TreeNode(val);
queue.add(root);
int i = 1;
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(ss[i].equals("N")){
i++;
}else{
TreeNode left = new TreeNode(Integer.parseInt(ss[i]));
i++;
node.left = left;
queue.add(left);
}
if(ss[i].equals("N")){
i++;
}else{
TreeNode right = new TreeNode(Integer.parseInt(ss[i]));
i++;
node.right = right;
queue.add(right);
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
这个题的思路是没啥问题的，其实就是一个树转字符串，字符串转树的实现。实现方法很多样，之前二叉树的转换做了好多遍了。但是因为题目要求字符串的编码尽量紧凑一点，所以才稍微有点复杂。
之前说了两个树的遍历才能确定唯一的树，但是我们这个题还是有点不同的，因为这个是一个二叉搜索树，所以这个树只要中序得出来的字符串就可以还原成唯一的树。然后代码如上，至于性能为啥不行我也不知道，刚刚看了性能排行第二（排第一的是用了一个静态变量存这个树，有点理解不了写出这个代码的人怎么想的）的代码，感觉差不多的思路，但是我这个性能就贼可怜，我直接贴上性能第二的代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
public int i = 0;
// Encodes a tree to a single string.
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder( );
toString(root ,sb);
return sb.toString();
}
static void toString(TreeNode node,StringBuilder sb){
if(node == null){
return;
}
toString(node.left,sb);
toString(node.right,sb);
sb.append((char) node.val);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if("".equals( data )){
return null;
}
char[] datas = data.toCharArray();
i = datas.length -1;
return toTree(datas,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
TreeNode toTree( char[] datas, Integer min,Integer max){
if(i < 0){
return null;
}
char val = datas[i];
if(val < min || val > max){
return null;
}
i--;
TreeNode node = new TreeNode(val);
node.right = toTree(datas,node.val,max);
node.left = toTree(datas,min,node.val);
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
区别感觉就是他这里用的递归，我用的是队列？不知道为啥性能差别这么大。反正这个题就这样了，下一题。
删除二叉搜索树中的节点
题目：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
思路：这个题怎么说呢，感觉单纯的删除是最简单的，但是这个题有两点：一个是二叉搜索树，还有一个是时间复杂度O(h)。暂时的想法是先找到这个删除的节点，然后删除的时候要么左节点上位，右节点挂在原本的左节点右节点为止，要么反过来。我先去代码实现试试吧。
这个题，怎么说呢，写完了，性能超过百分百，就是中间过程略煎熬，我直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return root;
if(root.val == key){
TreeNode left = root.left;
TreeNode right = root.right;
if(left == null) return right;
if(right == null) return left;
root = right;
while(root.left != null){
root = root.left;
}
root.left = left;
return right;
}
del(root,key);
return root;
}
public void del(TreeNode root, int key){
if(root.left!=null && root.val>key){
if(root.left.val == key){
TreeNode left = root.left.left;
TreeNode right = root.left.right;
if(left == null){
root.left = right;
return;
}
if(right == null){
root.left = left;
return;
}
root.left = right;
while(right.left != null){
right = right.left;
}
right.left = left;
return;
}
del(root.left,key);
}else if(root.right!=null && root.val<key){
if(root.right.val == key){
TreeNode left = root.right.left;
TreeNode right = root.right.right;
if(left == null){
root.right = right;
return;
}
if(right == null){
root.right = left;
return;
}
root.right = right;
while(right.left != null){
right = right.left;
}
right.left = left;
return;
}
del(root.right,key);
}
}
}
我就这么说吧，一步一步bug，最后在编译器中一行一行代码走通的，鬼知道我经历了什么。
提交记录
我去看看性能排行第一的代码怎么写的，看完完美的自闭了，人家的优雅简洁的代码，我的。。。一言难尽。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val>key) {
root.left = deleteNode(root.left, key);
}else if (root.val<key){
root.right = deleteNode(root.right, key);
}else {
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode leftMax = root.left;
while (leftMax.right != null){
leftMax = leftMax.right;
}
leftMax.right = root.right;
return root.left;
}
return root;
}
}
但是怎么说呢，整体思路是差不多的。所以这个题就这样了。
这篇笔记写了两周，最近项目比较紧，都没啥时间刷题，尤其是最近添加了新爱好，天天晚上去公园滑滑板，所以学习时间大大减少了，深刻反省自己，打算这周末补一篇笔记，flag先放这了。
如果本篇文章稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！java技术交流群130031711，欢迎各位踊跃加入！
网友评论