Kosmos
---我们总得选择一条路去前行---
剑指offer_Part3
友情提示: 代码在这里
本文参照该仓库学习,大家可以star
20 表示数值的字符串
true
"+100"
"5e2"
"-123"
"3.1416"
"-1E-16"
false
"12e"
"1a3.14"
"1.2.3"
"+-5"
"12e+4.3"
链接：https://www.nowcoder.com/questionTerminal/6f8c901d091949a5837e24bb82a731f2
来源：牛客网
使用正则表达式来解决
[\+\-]? -> 正或负符号出现与否
\d* -> 整数部分是否出现，如-.34 或 +3.34均符合
(\.\d+)? -> 如果出现小数点，那么小数点后面必须有数字；
否则一起不出现
([eE][\+\-]?\d+)? -> 如果存在指数部分，那么e或E肯定出现，+或-可以不出现，
紧接着必须跟着整数；或者整个部分都不出现
21 调整数组顺序使奇数位于偶数前面
需要保证奇数和奇数，偶数和偶数之间的相对位置不变，这和书本不太一样。
先统计出奇数的个数然后在空出位置放奇数,后面放偶数
22 链表中倒数第 K 个结点
设链表的长度为 N。设两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到 N - K 个节点处，该位置就是倒数第 K 个节点。
23 链表中环的入口结点
一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。
使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。假设相遇点在下图的 z1 位置，此时 fast 移动的节点数为 x+2y+z，slow 为 x+y，由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。
在相遇点，slow 要到环的入口点还需要移动 z 个节点，如果让 fast 重新从头开始移动，并且速度变为每次移动一个节点，那么它到环入口点还需要移动 x 个节点。在上面已经推导出 x=z，因此 fast 和 slow 将在环入口点相遇。
链接：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
来源：牛客网
这个说的清楚一点
第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
24 反转链表
递归
迭代(头插法)
25 合并两个排序的链表
递归
迭代(头插法)
26 树的子结构
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null||root2==null)
{
return false;
}
return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2)||isSubtreewithRoot(root1,root2);
}
private boolean isSubtreewithRoot(TreeNode root1, TreeNode root2) {
if(root2==null)
{
return true;
}
if(root1== null)
{
return false;
}
if(root1.val!=root2.val)
{
return false;
}
return isSubtreewithRoot(root1.left,root2.left)&&isSubtreewithRoot(root1.right, root2.right);
}
27 二叉树的镜像
将左右结点交换,一层一层下去
28 对称的二叉树
先比较root结点,然后在用结点的左结点和右结点比较 右结点和左结点比较
29 顺时针打印矩阵
就照着顺序打印,用四个变量,定义一下边界值
标题：剑指offer_Part3