简单算法杂例
原创
链表
- 删除链表中的重复的元素（hashset）
- 找出单链表中倒数第k个元素（双指针）
- 实现链表的翻转（）
- 从尾到头输出单链表（递归）
- 寻找单链表的中间节点（双指针）
- 检测一个链表是否有环（快慢指针）
- 在不知道头指针的情况下，删除指定的节点
- 如何判断两个链表是否相交（相交必然尾节点相同）
- 如果两个链表相交，如何找到相交的第一节点（两个链表的长短可能不一，长链表的指针移动到离尾部距离与短链表的长度一致，如此一来，二者到第一个相交的节点的距离相同）
如何实现栈（数组与链表均可）
A为插入栈，B为弹出栈；如果人队列，之需要入A栈即可。弹出栈则分为两种：
第一：如果B栈为空，那么将A中的所有元素依次弹出后放入B栈中（负负为正，FILO顺序颠倒，再颠倒依次就为原始的顺序），此时B栈中已经有了元素，弹出的方式见“第二”
第二：如果B栈非空，那么直接将B中的元素弹出即可
public class MyQueue<E> {
// use two Stack to consist a Queue
private Stack<E> stack1 = new Stack<>();
private Stack<E> stack2 = new Stack<>();
public void put(E e){
stack1.push(e);
}
public E pop(){
if (stack2.isEmpty())
while (!stack1.isEmpty())
stack2.push(stack1.pop());
return stack2.pop();
}
public boolean isEmpty(){
return stack1.isEmpty()&&stack2.isEmpty();
}
public static void main(String[] args) {
MyQueue<Integer> myQueue = new MyQueue();
myQueue.put(1);
myQueue.put(5);
myQueue.put(55);
while (!myQueue.isEmpty())
{
System.out.println(myQueue.pop());
}
}
}也可以采用两个队列实现站栈，只是稍微复杂；
位运算
- 用位移操作实现乘法运算（<< 、>>分别为乘2、除以2）
- 如何判断一个数是否为2的N次方（2的N次方的数都是最高位为1 ，例如16:10000，但是16-1的二进制为：
01111，与16的二进制的每一位都是不同的，可以n&(n-1)==0来判断n是不是2的N次方的数）
- 求二进制中的1的个数（每次进行n&（n-1）计算，其结果就会少一位）
while（n>0）{
if(n!=0){
n=n&(n-1);
count++;
}
}Leetcode172
判断n!的阶乘有多少个0？
我们知道2*5 =10 ，两个数相乘为10一定要包含2和10，阶乘过程中，偶数都可以分解出来2，因此只需要看能有几个5就行了，但是要注意的是25可以分解为5*5 因此可以继续分，所以代码如下：
判断n有几个5就行了，
public int trailingZeroes(int n) {
int ret = 0;
int pow = 5;
while (pow * 5 > pow && n / pow >= 1) {
ret += n / pow;
pow *= 5;
}
return ret;
}求一个二叉树的最低深度
public int minDepth(TreeNode root) {
return minDepth_recursion(root);
}
public int minDepth_recursion(TreeNode root){
if (root == null) return 0;
if (root.left == null && root.right==null) return 1;
if (root.left == null) return 1+minDepth_recursion(root.right);
if (root.right == null) return 1+minDepth_recursion(root.left);
return 1+Math.min(minDepth_recursion(root.left),minDepth_recursion(root.right));
}求二叉树的最大深度
public int maxDepth(TreeNode root) {
if (root == null ) return 0;
return 1+Math.max( maxDepth(root.left),maxDepth(root.right) ) ;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
