public static void preOrderUnRecur(Node head) { //1先将头结点压入栈 //2 弹出栈顶元素，再将该节点的左右节点压入栈(先右后左) //3 不断重复2 ，直到stack为空 if (head == null) return; Stack<Node> stack = new Stack<>(); stack.push(head); while (!stack.isEmpty()) { Node cur = stack.pop(); System.out.println(cur.data + " "); if (cur.right != null) { stack.push(cur.right); } if (cur.left != null) { stack.push(cur.left); } } }
public static void midOrderUnrecur(Node head) { //1 申请一个栈 cur=head // 2 将栈左子树依次压入 cur=cur.left // 不断重复2，直到cur==null ，弹出node 并打印，并cur=node.right ，继续重复 if (head == null) return; Stack<Node> stack = new Stack<>(); stack.push(head); while (!stack.isEmpty() || head != null) { if (head!= null) { stack.push(head); head = head.left; }else{ Node node=stack.pop(); System.out.println(node.data); head=node.right; } } }
使用递归方式 不理解
TreeNode prev =null;// 中序遍历这棵树，并保存前驱节点至prev中
//使用递归
public boolean isValidBST(TreeNode root){
if(root != null){
if(!isValidBST(root.left))
return false;
if(prev!=null && root.val<=prev.val){
return false;
}
prev = root;
return isValidBST(root.right);
}
return true;
}1 使用递归方式
2 使用层序遍历方式 层序遍历使用了队列
/* *@description:将二叉树转换为字符串 * # 表示节点为null ,每个节点以 '!' 分割 *@params:[head] *@return:java.lang.String *@author:Mao *@date:2019/4/12 8:46 **/ public static String seriaByPre(Node head) { if (head == null) return "#!"; String res = head.data + "!"; res += seriaByPre(head.left); res += seriaByPre(head.right); return res; } /* *@description:反序列化 将str转换为二叉树 *@params:[str] *@return:com.mao.tree.Node *@author:Mao *@date:2019/4/12 8:53 **/ public static Node reconByPre(String str) { if (str == null) return null; //将str 按照'!'分割成数组 String[] strs = str.split("!"); Queue<String> queue = new LinkedList<>(); for (int i = 0; i < strs.length; i++) { queue.offer(strs[i]); } return reconByPreOrder(queue); } /* *@description:前序递归 *@params:[strs] *@return:com.mao.tree.Node *@author:Mao *@date:2019/4/12 8:59 **/ private static Node reconByPreOrder(Queue<String> queue) { String value = queue.poll(); if ("#".equals(value)) { return null; } Node node = new Node(Integer.valueOf(value)); // 将值与节点的左右子树相连接 node.left = reconByPreOrder(queue); node.right = reconByPreOrder(queue); return node; }
//层序遍历 public static String seriaByLevel(Node node) { if (node == null) return "#!"; String res = node.data + "!"; Queue<Node> queue = new LinkedList<Node>(); queue.offer(node); while (!queue.isEmpty()) { Node head = queue.poll(); if (head.left != null) { res += head.left.data + "!"; queue.offer(head.left); } else { res += "#!"; } if (head.right != null) { res += head.right.data + "!"; queue.offer(head.right); } else { res += "#!"; } } return res; } /* *@description:层序遍历反序列化 *@params:[args] *@return:void *@author:Mao *@date:2019/4/12 9:55 **/ public static Node reconByLevel(String str) { if (str == null) return null; String[] strs = str.split("!"); int index = 0; Node head = generatedNode(strs[index++]); Queue<Node> queue = new LinkedList<>(); queue.offer(head); Node node = null; while (!queue.isEmpty()&& index!=strs.length) { node = queue.poll(); node.left = generatedNode(strs[index++]); node.right = generatedNode(strs[index++]); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } return head; } private static Node generatedNode(String str) { if ("#".equals(str)) { return null; } return new Node(Integer.valueOf(str)); }
注意 ：需检查是否为null
1 先进行 t1树的前序遍历
2 在与t1 和t2 的每个节点进行比较
public static boolean contains(Node t1,Node t2){ //需检查t1 是否为null 为null则停止 if(t1==null){ return false; } return check(t1,t2)|| contains(t1.left,t2)|| contains(t1.right,t2); } private static boolean check(Node tt1, Node tt2) { if(tt2==null){ return true; } if(tt1==null || tt2.data!=tt1.data){ return false; } return check(tt1.left,tt2.left) && check(tt1.right,tt2.right); }
- 难度一星
采用递归方式实现
public Node generateTree(int[] sortArr) { if (sortArr == null) return null; return generate(sortArr, 0, sortArr.length - 1); } private Node generate(int[] sortArr, int start, int end) { if (start > end) return null; int mid = (start + end) / 2; Node head = new Node(sortArr[mid]); head.left = generate(sortArr, start, mid - 1); head.right = generate(sortArr, mid + 1, end); return head; }
- 思路一：
- 时间复杂度O(n) 空间复杂度 O(n)
- 1 先找到根结点
- 2 根据根节点就行中序遍历
- 3 遍历结果即为节点的后一个节点
- 找到两个节点最近的祖先
- 思路：
- 采用后序遍历
- 1 如果cur 节点下 左右子树，均无法找到o1 或o2，则返回null
- 2 若cur 节点，左右子树能找到，则返回cur
- 3 如果有一个子树返回为null，另一个子树找到，假设不为空的记为node，则存在两种情况
- 1）则node该节点是O1 或 O2
- 2）node是最近的公共祖先
- 例如遍历节点1 ，发现node节点为3 则 3是o1和o2的父节点
- 时间复杂度： O(n) p172
- 在中序数组找位置i过程可以用hash表来实现，复杂度为O(n)
- 思路：
- 1 先序数组最左边为树的头结点h，中序找到h，假设位置i。则中序
- 数组中，i左边数组就是的头结点左子树的中序数组，长度L，则左子树
- 的先序数组就是先序数组的h+L
- 2 用左子树先序和中序，递归整个过程建立左子树left
- 3 用右子树的的先序和中序数组，递归右子树right
- 4 把head左右孩子设为lef 和 right
public Node preInToTree(int[] preArr,int[] midArr){ if(preArr==null || midArr==null){ return null; } //使用HashMap将midArr数组存储 HashMap<Integer,Integer> map=new HashMap<>(); for (int i=0;i<midArr.length;i++){ map.put(midArr[i],i); } return preTree(preArr,0,preArr.length-1,midArr,0,midArr.length-1,map); } private Node preTree(int[] preArr, int preStart, int preEnd, int[] midArr, int midStart, int midEnd, Map<Integer, Integer> map) { if (preStart> preEnd){ return null; } Node head=new Node(preArr[preStart]); int index=map.get(preArr[preStart]); head.left=preTree(preArr,preStart+1,preStart+midEnd-index,midArr,midStart,index-1,map); head.right=preTree(preArr,preStart+index-midStart+1,midEnd,midArr,index+1,midEnd,map); return head; }
public Node inPosToTree(int[] mid,int[] pos){ if(mid==null || pos==null){ return null; } HashMap<Integer,Integer> map=new HashMap<>(); for (int i=0;i<mid.length;i++){ map.put(mid[i],i); } return posToTree(pos,0,pos.length-1,mid,0,mid.length-1,map); } private Node posToTree(int[] pos, int posStart, int posEnd, int[] mid, int midStart, int midEnd, HashMap<Integer, Integer> map) { if(posStart>posEnd){ return null; } int arr=pos[posEnd]; int index=map.get(arr); Node node=new Node(arr); node.left=posToTree(pos,posStart,posStart+index-midStart-1,mid,midStart,index-1,map); node.right=posToTree(pos,posStart+index-midStart,posEnd-1,mid,index+1,midEnd,map); return node; } public static void main(String[] args) { int[] pos=new int[]{4,5,2,6,7,3,1}; int[] in=new int[]{4,2,5,1,6,3,7}; InPosToTree test=new InPosToTree(); Node head=test.inPosToTree(in,pos); test.pre(head); } public void pre(Node head){ if (head==null) return; System.out.print(head.data); pre(head.left); pre(head.right); }
-
时间复杂度： O(n)
-
思路：
-
1 后序数组的最右边为树的头结点h，中序找到h，假设位置为i。
-
则中序数组中，i 左边数组就是头结点左子树的中序数组，长度为L。
-
则左子树的后序数组就是后序数组的h-L
-
2 用左子树的后序和中序，递归建立左子树left
-
3 用右子树的后序和中序，递归建立右子树right
-
4 把head和左右子树设为left和right
public class GetPosArray { // 根据先序和中序 设置后序数组的最右边的值， // 然后根据先序和中序的右子树设置后序数组， // 左子树同样 public int[] getPostArray(int[] pre,int[] mid){ if(pre==null||mid==null){ return null; } int len=pre.length; int[] pos=new int[len]; HashMap<Integer,Integer> map=new HashMap<>(); for (int i=0;i<mid.length;i++){ map.put(mid[i],i); } setPos(pre,0,pre.length-1,mid,0,mid.length-1,pos,pos.length-1,map); return pos; } //从右往左依次填写数组pos //posEnd为后序数组该填的位置 //返回值为该填的位置 private int setPos(int[] pre, int preStart, int preEnd, int[] mid, int midStart, int midEnd, int[] pos, int posEnd, HashMap<Integer, Integer> map) { if(preStart>preEnd){ return posEnd; } pos[posEnd--]=pre[preStart]; int index=map.get(pre[preStart]); posEnd= setPos(pre,preStart+index-midStart+1,preEnd,mid,index+1,midEnd,pos,posEnd,map); return setPos(pre,preStart+1,preStart+index-midStart,mid,midStart,index-1,pos,posEnd,map); } public static void main(String[] args) { int[] pre=new int[]{1,2,4,5,3,6,7}; int[] in=new int[]{4,2,5,1,6,3,7}; GetPosArray arr=new GetPosArray(); int[] pos=arr.getPostArray(pre,in); for (int i=0;i<pos.length;i++){ System.out.println(pos[i]); } } }
要求：不要重建整个树，直接生成后序数组
- 1 根据当前的先序和中序，设置后序数组的最右边值
- 2 划分出左子树的先序、中序数组；
- 右子树的先序、中序数组。
- 3 根据右子树划分设置好后序数组，再根据左子树划分
判断是否为平衡二叉树 左右子树高度差不大于1
//boolean res 相当于全局变量 /* 当不满足时立刻返回 if(!res[0]) { return level; } */ public static boolean isBanlance(Node head){ boolean[] res=new boolean[1]; res[0]=true; System.out.println("height:"+getHeight(head,1,res)); return res[0]; } private static int getHeight(Node head, int level, boolean[] res) { if(head==null) return level; int lh= getHeight(head.left,level+1,res); if(!res[0]){ return level; } int rh=getHeight(head.right,level+1,res); if(!res[0]) return level; if(Math.abs(lh-rh)>1){ res[0]=false; } return Math.max(lh,rh); } public static void main(String[] args) { String str = "1!2!#!4!#!#!#!"; Node head = reconByLevel(str); System.out.println( isBanlance(head)); }
-
根据数组 判断是否为二叉搜索树
**性质：**依据二叉树后序遍历性质 头结点一定是数组的最后一个元素
根据平衡二叉树的性质 比头结点大的数组一定在二叉树的右边，
比头结点小的在二叉树的左边
思路：
1 声明less 和 more 表示 左右子树的右边界 和 左边界
2 从start 到 end 开始遍历 找到less 和more
3 如果 less==-1 或者 more==end 说明 只存在左子树或右子树
4 若 less==more-1 说明当前左右子树符号条件 分别判断左子树和右子树内部是否满足
5 终止条件 当 起始位置和终止位置 相等时 则证明符号条件
public class IsPostArray { public boolean isPostArray(int[] arrs){ if(arrs==null ||arrs.length==0) return false; return isPost( arrs, 0 , arrs.length-1); } private boolean isPost(int[] arrs, int start, int end) { // 整个递归的终止条件 if(start==end){ return true; } int less=-1; //找到左子树右边界临界点 int more=end; //找到右子树最左边 //找到左子树的右边界，右子树的左边界 for(int i=start;i<end;i++){ if(arrs[end]>arrs[i]){ less=i; }else { //找到第一个比根节点大的索引 more=more==end?i:more; } } //只存在左子树或只存在右子树 if(less==-1 || more==end){ return isPost(arrs,start,end-1); } //若左边界和右边界-1 相等 则继续遍历，不等直接返回false if(less!=more-1){ return false; } //进行左子树和右子树的遍历 return isPost(arrs,start,less)&& isPost(arrs,more,end-1); } }
public Node postArrayToBST(int[] arrs){ if(arrs==null) return null; return posToBST(arrs,0,arrs.length-1); } private Node posToBST(int[] arrs, int start, int end) { if(start>end) return null; int less=-1; int more=end; Node node=new Node(arrs[end]); for (int i=0;i<arrs.length;i++){ if(arrs[end]>arrs[i]){ less=i; }else { more=more==end?i:more; } } node.left=posToBST(arrs,start,less); node.right=posToBST(arrs,more,end); return node; }
完全二叉树性质 每层节点都得填满 ，运行最后一层右节点为null
思路：
-
1 按照层序遍历
-
2 若当前节点有右子树，无左子树 则 返回false
-
3 若当前节点并不是左右子树都有（有左子树无右子树， 均为左右子树），则后续节点必须为叶子节点
public boolean isCBT(Node head){ if(head==null) return false; Queue<Node> queue=new LinkedList<>(); boolean leaf=true; Node left=null; Node right=null; queue.offer(head); while(!queue.isEmpty()){ head=queue.poll(); left=head.left; right=head.right; if(leaf &&(left!=null || right!=null) || (left==null&&right!=null)){ return false; } if(left!=null){ queue.offer(left); } if(right!=null){ queue.offer(right); }else{ leaf=true; } } return true; }
leetcode 98
思路：进行中序遍历 则搜索二叉树节点值为升序
注意： 搜索二叉树的性质 BST
非递归的中序遍历
public boolean isValidBST(TreeNode root) { Stack<TreeNode> stack=new Stack(); double inOrder=-Double.MAX_VALUE; while(!stack.isEmpty() || root!=null){ while(root!=null){ stack.push(root); root=root.left; } root=stack.pop(); if(root.val<=inOrder){ return false; } inOrder=root.val; root=root.right; } return true; }
public boolean isValidBST(TreeNode root) { Stack<TreeNode> stack=new Stack(); double inOrder=-Double.MAX_VALUE; while(!stack.isEmpty() || root!=null){ if(root!=null){ stack.push(root); root=root.left; }else{ root=stack.pop(); if(root.val<=inOrder){ return false; } inOrder=root.val; root=root.right; } } return true; }
思路 ： 数组的中间数为二叉树的头结点 ，左侧 为左子树 右侧为右子树
public class GenerateBSTByOrderArr { public static Node generateBST(int[] arr){ if(arr==null){ return null; } return getBst(arr,0,arr.length-1); } /* *@description: 使用递归生成平衡搜索二叉树 *@params:[arr, i, i1] *@return:com.mao.tree.Node *@author:Mao *@date:2019/4/23 8:31 **/ private static Node getBst(int[] arr, int start, int end) { if(start> end){ return null; } int mid=(start+end)/2; Node node=new Node(arr[mid]); node.left=getBst(arr,start,mid-1); node.right=getBst(arr,mid+1,end); return node; }
不懂
使用后序遍历
//使用后序遍历 /* 1 / \ 2 3 / \ / \ 4 5 6 7 / 8 */ public Node lowestAncestors(Node head,Node o1,Node o2){ if(head==null || head==o1 || head==o2){ return head; } Node left=lowestAncestors(head.left,o1,o2); Node right=lowestAncestors(head.right,o1,o2); if(left!=null && right!=null){ return head; } //若其中有一个为null 不为null记为node //说明node要么是o1 要么是o2 //或者 是o1 和o2的最近祖先 return left!=null?left:right; }
若两个字符串str1和str2，如果str1和str2出现字符种类一样且每种字符出现次数一样，
则str1和str2互为变形词。
如 str1=123 str2=132 返回true
str1=123 str2=1223 返回false
思路：
- 字符串转化为char[] ,使用 toCharArray();
- 假设字符串编码在 0到255范围内，用来统计每个字符出现的次数，记为map
- 通过str1确定出现次数
- str2来减少map内字符出现次数，若出现小于0，则不匹配
要求：1 忽略小数点
2 若左侧出现‘-’，当连续为奇数时，则数字为负，相反则为偶数
例：str="ab-----1111223a------1111c34"
思路要点：
- 1 采用3个变量 res 结果 num 当前数字 isN 是否为正负,cur表示当前值
- 2 连续数字 num=num*10+( isN ? cur : -cur)
- 3 如何判断正负 ，判断 “-” 之前的是否为 “-”
如 str=“AB00DF” k=2 str="ABDF"
注意：
1 记录首次出现位置 start=start==-1 ? i : start
若为-1 ，表示重新开始记录0出现的首次位置
若不为-1，则一直保持首次出现位置
2 ASCII NULL值 是 0
思路要点：
- 记录0出现的次数，以及首次出现位置
- 当当前字符非0时，检查0出现的次数是否满足
- 字符串最后一个未检查，需遍历完后检查最后是否满足
- 将两个a拼接起来成A，则A的子串就包含旋转词
- 复杂度若为O(n), 则需要kmp算法
- 使用 jdk 自带的 str.indexOf() , 返回某个指定的字符串值在字符串中首次出现的位置,不是则返回-1
给定str form to三个字符串，把str中所有from的自串全部替换成to字符串，
对连续出现的 from部分要求只替换成一个to字符串，返回最终的结果。
思路：
- 1 将str包含to中的替换为ascii中的0值
- 2 将非0的字符串开始合并
具体过程：
1 遍历，判断str的位置和chaf位置是否相等
1.1 若相等，继续遍历from后继位置，判断from的长度与匹配长度一致
1.1.1 若长度相等则替换为0
1.2 若字符不配，则更新match，重新匹配
2 替换后的str进行转换，拼接
2.1 非0直接拼接
2.2 若为0，则且前一个位置为非0
5.1 补充问题：
给定字符串统计字符串，以及一个整数index，返回cstr的原始字符串上的第index个字符
如 a_1_b_100 第0个位啊 第50位b。
tip：
1 获得连续出现字母数量 num = num * 10 + strs[i] - '0'
2 切换连续字母状态 stage=!stage
3 最后一个需单独计算
使用hashSet 或者数组 boolean[] iscontain=new boolean[255];
char[] 数组中的空格字符，替换为%20
1 统计非空格字符和字符长度
2 从后往前遍历，将空格字符替换为 “%20”
时间复杂度： 0(N) 空间复杂度o(1)
举例：dog love pig 反转 pig love dog
思路：先将字符整体反转，然后将每个单词反转
提示：
start = i == 0 || chars[i - 1] == ' ' ? i : start; end = i == chars.length - 1 || chars[i + 1] == ' ' ? i : end;
给定一个字符串类型的数组chars 和一个整数size，请把大小为size的半区整体移到右边区，右半区整体移到左边
思路：先反转部分，在整体反转
题目：给定一个字符串str，判断是不是有整体有效的括号字符串
思路：1 从左到右依次遍历字符串，判断每一个字符是不是‘（’ 或‘）’，不是直接返回false
2 依次遍历每一个，检查'(' 和 ')' 的数量，如果‘）’更多则直接返回
3 遍历后检查检查'(' 和 ')' 的数量
思路2： 使用动态规划
ASCII 大写字母 65-90
小写字母 97-122
题目： 指出新的字符， 小写字母 一个 大写字母 两个 包括 AA Ab型
思路1：从前遍历，遍历时，划分
思路2 ：从k位置向前遍历,并记录大写字母个数num，直到遇到小写字母停止
-
若num为奇数，则为 k-1,k -
若num为偶数，且k为大写字母，则 (K,K+1) -
且K为小写字母,则为 k
Hash函数概念介绍：（4个性质）
位运算
如果给定整数a和b，则可以如下设置：
a=a^b; 记录了a和b整数位信息的所有不同信息
b=a^b;
a=a^b;
题目：给定两个32位整数a和b，返回a和b中较大的
要求：不要做任何比较判断
思路：直到起点 (tl,tr) 和终点 (dl,dr) tl++ tr++ dl-- dr--
矩阵颠倒
保证对角线打印 分为上下两个坐标，分别移动 p335
- 需要排序的最短子数组长度
- 从右向左 找出最小的位置minIndex
- 从左向右 记录最大值，以及maxIndex
- 范围为(minIndex,maxIndex)
- 思路：从右上角开始找 目标k
- 若当前值小于K 则行row+1
- 若当前值大于K，则列col-1
arr=[1,-2,3,5,-2,6,-1] ，则 [3,5,-2,6]累加最大值为12
累加称为负数清零，重新累加
- 思路一：
- 使用除法，重点在零的个数
- 当非零，则除当前数
- 当一个零，则，非零位置，均为零，零位置为其他乘积
- 当大于一个零，则均为零
思路二：
不使用除法，分为左右两个组累乘 lr[] 和rl[]
若不能申请额外空间，则复用res[]
分为左区域无重复区域 右侧重复区域
当当前值不等于左侧区域最后一个数时，将当前值放大左侧区域
还有很多变种问题
如： 给定一个数组arr，其中包含0,1,2 实现arr排序
有一个数组，其中有红、蓝黄 ，红色左边蓝色中间黄色右边
put get isContain setAll 要求时间复杂度都为O(1)
需要考虑泛型的使用方法，泛型类和泛型方法 （泛型数组？）
思路，设计时间戳
题目： 给定一个长度为N且没有重复元素的数组arr和一个整数n，实现函数等概论随机打印arr中的M个数 时间复杂度o(m) 空间复杂度 O(1) 思路一：使用hash表来记录是否打印 思路二：与最后一个元素位置交换
给定一个32位整数，判断是否是回文数
如 121 22 -121 -22
注意：32位整数最小值为 -2147483648 绝对值会产生溢出
"/" 获得高位 "%"获得低位
- 题目： 实现一个特殊的栈，在栈的基础功能上，返回栈中最小元素
- 思路：使用两个栈，一个用来存储数据，一个用来存储当前最小值
- 需要考虑栈入栈和出栈规则
- 1 入栈 stack_min 中与栈顶比较，若比当前小或者相等则入栈，否则不变
- 2 出栈时，stackMin元素总是小于等stackData栈顶元素 相等则都出，min小于data则只出data
- add
- pollAll
- pollDog
- pollCat
- isEmpty
- 思路： 使用时间戳 添加PetEnter类 最后在CatDogQueue内实现
题目： 一个栈中元素的类型为整型，现将该栈从顶到底按从大到小顺序排序，只允许申请一个额外栈。可申请额外变量，但不能申请额外数据结构，如何排序。
思路：排序栈为stack 申请辅助栈为help stack上执行pop，弹出元素为pop
1 若cur小于 或等于 help的栈顶元素，直接压入help
2 若大于 则将help元素逐一弹出，逐一压入stack，直到cur <= help 的栈顶元素
while (!s1.isEmpty()) { int tmp = s1.pop(); // 此处不能有等于 会无限循环 while (!s2.isEmpty() && tmp < s2.peek()) { s1.push(s2.pop()); } s2.push(tmp); }
题目：给定两个有序链表的头指针head1和head2 ，打印公共部分
思路 head1 <head2 head1 往下移动 同理
注意：加强如何构建链表，如何打印链表，以及打印完链表指针后移的要素
原因：没有考虑边界问题 删除时可以利用之前的K
- 边界问题 删除倒数K节点是否超出数组范围，以及头结点和其他节点的不同的删除方式
- 思路： 每移动一次k就减一，根据K是否大于0来判断
- K>0 证明 超出范围
- k=0 恰好头结点，删除头结点
- k<0 则正常情况，删除该节点需获取前一个节点
public static Node removeLastKthNode(Node head, int k,int length) { if (head == null) { return head; } Node cur = head; int k2=k; while (cur != null) { cur = cur.next; k--; } Node cur2 = head; if (k < 0) { int tmp=k2-length; //直接使用K while(++k!=o) while (tmp++ != 0) { cur2 = cur2.next; } Node next = cur.next; cur2.next = next.next; next.next = null; return head; } else if (k == 0) { head = head.next; return head; } else { return head; }
-
进阶问题 a/b处的节点（后序完成）
-
原因：如何删除前一个节点 让h2开始就从头节点移动两次（比h1多移动一次） 此时h1就是前一个节点
-
思路：申请两个节点h1,h2 h1每次只移动一次，h2移动两次
-
当h2的下一次为null 则返回当前h1
public static Node removeMiddleNode(Node node) { if (node == null) { return node; } if (node.next.next == null) { return node.next; } Node pre = node; Node cur = node.next.next; while (cur.next != null && cur.next.next != null) { pre = pre.next; cur = cur.next.next; } pre.next = pre.next.next; return node; }
注意：还可以使用递归方式
https://blog.csdn.net/wxm349810930/article/details/46724691
思路：将头结点从链表拆除，然后对剩余节点逆序，最后将表头节点连接到新链表尾部
4.1 反转单向链表
-
思路：声明两个节点next和pre
-
next 保存头结点后面的节点
-
pre 保存前一个节点
-
head.next=pre //此事head指向pre 已经和原先节点断链
-
pre=head //更新pre节点
-
head=next //将保存后序节点在重新给head
-
最后pre就是头结点head此时为空
-
public static Node reverse(Node head) { Node next = null; Node pre = null; while (head != null) { next = head.next;// 保存头结点后面的节点 head.next = pre; // 此时head指向pre 已经和原先节点断链 pre = head; head = next;// 将保存后序节点在重新给head } // 返回pre而不是head？ return pre; }
4.2 反转双向链表
public static DoubleNode reverseDouble(DoubleNode node) { DoubleNode next = null; DoubleNode pre = null; while (node != null) { next = node.next; node.next = pre; node.pre = next; pre = node; node = next; } return pre;
难点：如何获得要反转部分的前一个及最后一个，以及如何正确连接节点
思路：
1 先获得要反转节点from的前一个 preFrom 和反转to的后一个postTo
2 先将反转的第from位置节点和postTo连接 （注意此时断链，需要声明一个节点保存后序信息）
3 反转部分节点
4 若preFrom为null 则是反转了头结点，若反转不为空，返回新节点，
（此时head节点已不是头结点 而是指向了postTo位置节点
public static Node partReverse(Node head, int from, int to) { // 找到要反转节点的前一个节点，且不是头结点 int i = 0; Node h1 = head; Node preFrom = null; Node postTo = null; // 获得链表from前一个preFrom.to的后一个postTo while (h1 != null) { i++; preFrom = i == from - 1 ? h1 : preFrom; postTo = i == to + 1 ? h1 : postTo; h1 = h1.next; } //拿到要反转的第一个节点 h1 = preFrom == null ? head : preFrom.next; //连接翻转后的尾节点 Node h2 = h1.next; h1.next = postTo; // 反转节点 Node next = null; int j = to - from; while (h2 != postTo) { next = h2.next; h2.next = h1; h1 = h2; h2 = next; } // h1.next = pre; if (preFrom != null) { preFrom.next = h1; // 返回旧节点 return head; } // 返回新节点 return h1; }
注意：掌握循环链表，如何找到最后一个节点 注意循环链表的判断条件
-
单向环形链表
-
每m个就删除当前节点，并重新计数
-
直到剩下最后一个
public static Node jsoepuseKill(Node head, int m) { if (head == null || head.next == head || m < 1) return head; // 找到last节点 Node last = head; while (last.next != head) { last = last.next; } int count = 0; while (head != last) { if (++count == m) { last.next = head.next; count = 0; } else { last = last.next; } head = head.next; } return head; }
-
注意：思路二中移动时 Node cur = head.next;
在移动后cur就是右链的第一个节点（这块出错）
-
思路1 ：使用栈（没想到），入栈顺序和出栈顺序一致
-
思路2：同样使用栈，只讲链表的一半压入栈，比较左链和右链是否相等
需要进行奇数偶数判断。
注意： 1 需考虑当两个栈都为空，且还存在进位时
2 如何更新节点
3 相加时精简写法
val1=s1.isEmpty()?0:s1.pop(); val2=2.isEmpty()?0:s2.pop(); val3=val1+val2+cal; cal=val3/10; //进位 pre=cur; cur=new Node(cal%10); cur.next=pre;
pre = cur; cur = new Node(val3); cur.next = pre;
- 思路1：加完在生成链表 ，有可能相加时会存在溢出
- 思路2：利用栈，需考虑进位
public static Node addList1(Node head1, Node head2) { if (head1 == null || head2 == null) { return head1 == null ? head1 : head2; } Stack<Integer> s1 = new Stack<Integer>(); Stack<Integer> s2 = new Stack<Integer>(); while (head1 != null || head2 != null) { if (head1 != null) { s1.push(head1.data); head1 = head1.next; } if (head2 != null) { s2.push(head2.data); head2 = head2.next; } } Node pre = null; Node cur = null; int val1 = 0; int val2 = 0; int cal = 0; while (!s1.isEmpty() || !s2.isEmpty()) { if(!s1.isEmpty()){ val1 = s1.pop(); } else { val1 = 0; } if(!s2.isEmpty()){ val2=s2.pop(); } else { val2 = 0; } int val3 = val1 + val2 + cal; if (val3 >= 10) { cal = 1; val3 = val3 % 10; } else { cal = 0; } pre = cur; cur = new Node(val3); cur.next = pre; } // 当两个栈都为空，且还存在进位时 if (cal == 1) { Node n = new Node(cal); n.next = cur; return n; } return cur; }
- 难点：思路1中推荐使用hashset
- 思路1 使用hashMap 时间复杂度O(n) 空间复杂度O(n)
- 思路2 使用选择排序 时间复杂度O(n2) 空间复杂度O(1)
public static Node removeRepeat(Node head) { if(head==null) return null; HashMap<Integer, Integer> map=new HashMap<Integer, Integer>(); map.put(head.data, 1); Node n1 = head; Node pre = head; Node cur = head.next; while (cur != null) { if (map.containsKey(cur.data)) { pre.next = cur.next; cur = cur.next; } else { map.put(cur.data, 1); pre = cur; cur = cur.next; } } return n1; }
难点 ：思路二连接链表存在更简单做法
stack.peek().next=head; head=stack.pop();
- 思路1 直接删除 时间复杂度O(N) 空间复杂度O(1)
- 思路2 借助容器 将值不等的节点收集起来然后重新连接（没想到）
//直接删除 public static Node removeSpecialValue(Node head, int num) { if(head==null) return head; Node h = head; Node pre = head; Node cur = head.next; while (cur != null) { if (cur.data == num) { pre.next = cur.next; } else { pre = pre.next; } cur = cur.next; } return h; }
//使用栈 public static Node removeSpecialValueByStack(Node head, int num) { Stack<Node> s = new Stack<Node>(); while (head != null) { if (head.data != num) { s.push(head); } head = head.next; } Node pre = null; Node cur = null; while (!s.isEmpty()) { cur = s.pop(); cur.next = pre; pre = cur; } return cur; }
要求：额外空间复杂度O(1)
选择排序要点：从未排序的部分中找到最小值，然后放在排好序的尾部
- 获取最小节点的前一个节点
// 获得最小节点的前一个节点 private static Node getSmallPre(Node head) { Node smallPre = null; Node small = head; Node pre = head; Node cur = head.next; while (cur != null) { if(cur.data<pre.data){ smallPre=pre; small = cur; } pre = cur; cur = cur.next; } return smallPre; }
-
使用链表进行选择排序
public static Node selectionSort(Node head) { if (head == null) { return null; } Node tail = null; //排序部分的尾部 Node cur=head; //未排序的尾部 Node smallPre = null; // 最小节点的前一个节点 Node small=null; //最小节点 while (cur != null) { small = cur; // 找到最小节点 smallPre = getSmallPre(cur); if (smallPre != null) { small = smallPre.next; smallPre.next = small.next; } // cur==small 则cur节点就是最小节点，然后继续遍历 // cur!=small 则cur节点不是，需继续从cur遍历找到整个未排序部分的最小节点 cur = small == cur ? cur.next : cur; if (tail == null) { tail = small; } else { tail.next = small; } tail = small; } return head; }
只给定一个节点node ，不给的头结点 要求删除该节点
当该节点为null，不能使用复制方式，无法删除
public static void removeNodeWired(Node node) { if (node == null) { return; } if (node.next == null) { throw new RuntimeException("无法删除"); } //把node.next的节点复制给node 删除node.next node.data = node.next.data; node.next = node.next.next; }
- 特殊情况 当num 遍历完后 ，没有找到插入的地方，会有两种情况
1 该节点比头结点小
2该节点比头结点大
- 在环形链表中遍历的 cur ！=head
- pre=head cur=head.next;
//经典实现 public static Node insertByCircle2(Node head, Node num) { if (head == null) { num.next = num; return num; } Node pre = head; Node cur = head.next; while (cur != head) { if (pre.data <= num.data && num.data <= cur.data) { break; } pre = cur; cur = cur.next; } pre.next = num; num.next = cur; return head.data > num.data ? num : head; }
//自己实现 public static Node insertByCircle(Node head, Node num) { if (head == null) return null; Node cur = head; Node tail = null; // 获取taile节点 while (cur.next != head) { cur = cur.next; } tail = cur; cur = tail.next; while (cur != tail) { if (cur.data >= num.data && cur.next.data <= num.data) { //插入节点 Node next=cur.next; cur.next=num; num.next=next.next; } cur = cur.next; } if (num.data < head.data ) { tail.next = num; num.next = head; head = num; } if (num.data > tail.data) { tail.next=num; num.next=head; tail = num; } return head; }
public static Node merge(Node head1, Node head2) { if (head1 == null || head2 == null) { return head1 == null ? head2 : head1; } // 头结点为两个中最小的一个 Node head = head1.data < head2.data ? head1 : head2; Node cur1 = head == head1 ? head1 : head2; Node cur2 = head == head1 ? head2 : head1; Node pre=null; //书上 Node next=null; while (cur1 != null && cur2 != null) { if(cur1.data<cur2.data){ pre=cur1; cur1 = cur1.next; } else { Node next = cur2.next; pre.next = cur2; cur2.next = cur1; cur2 = next; pre = cur2; } } pre.next = cur1 == null ? cur2 : cur1; return head; }
思路：1首先要划分出左右半区 需要声明一个mid变量
2 组合左右两半区
public static Node relocate(Node head){ if(head==null) return null; //将链表划分左右两半区 Node mid=head; Node right=head.next; while(right.next!=null && right.next.next!=null){ mid=mid.next; right=right.next.next; } System.out.println("node:"+mid.next.data); Node cur=head; right=mid.next; // 标准写法 // mid.next=null; //while(cur.next!=null) while(cur!=mid){ Node next_left=cur.next; Node next_right=right.next; cur.next=right; right.next=next_left; right=next_right; cur=next_left; } cur.next=right; return head; }
leetcode 62
只能右爬和下爬，输入各自行数和列数，输出需要多种可能性
public class UniquePath{ public int uniquePath(int m,int n){ int[][] res=new int[m-1][n-1]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0 ||j==0){ res[i][j]=1; }else{ res[i][j]=res[i-1][j]+res[i][j-1]; } } } return res[m-1][n-1]; } }
- 使用递归方式 保存已有信息（记忆化搜索）
public class UniquePath{ public int uniquePaths(int m, int n) { int[][] memo=new int[m][n]; return dfs(m-1,n-1,memo); } public int dfs(int m,int n,int[][] memo){ if(memo[m][n]!=0){ return memo[m][n]; } if( m==0 || n==0){ return 1; } memo[m][n]=dfs(m-1,n,memo)+dfs(m,n-1,memo); return memo[m][n]; } }
leetcode 70
题目描述： 有n阶台阶 可以爬一阶，也可以爬2阶，计算有多少不同方法
与斐波那契数方法一致
Leetcode 509
- 使用递归
public int fib(int n){ int[] memo=new int[n+1]; return cal(n,memo); } private int cal(int n ,int[] memo){ if(n==0) return 0; if(n==1){ return 1; } if(memo[n]!=0){ return memo[n]; } return cal(n-1,memo)+cal(n-2,memo); } public static void main(String[] args) { Fibonacci sol=new Fibonacci(); System.out.println(sol.fib(4)); }
leetcode 121 Best Time to Buy and Sell Stock
//暴力破解 时间复杂度为O(n2) public int maxProfit(int[] prices) { int max=0; for(int i=0;i<prices.length;i++){ for (int j=i+1;j<prices.length;j++){ int tmp=prices[j]-prices[i]; if (tmp>max){ max=tmp; } } } return max; } //时间复杂度为O(n) public int maxProfit2(int[] prices){ int minPrice=Integer.MAX_VALUE; //最低价格 int maxPro=0;//最大利润 for (int i=0;i<prices.length;i++){ if(prices[i]<minPrice){ minPrice=prices[i]; }else if(prices[i]-minPrice>maxPro){ maxPro=prices[i]-minPrice; } } return maxPro; } //考虑使用动态规划？？ public int maxProfit3(int[] prices) { if(prices.length == 0 || prices.length == 1) return 0; int maxProfit = 0; int min = prices[0]; for(int i = 0; i < prices.length; i++) { min = Math.min(min, prices[i]); maxProfit = Math.max(maxProfit, prices[i] - min); } return maxProfit; }