简单算法杂例

链表

  1. 删除链表中的重复的元素(hashset)
  2. 找出单链表中倒数第k个元素(双指针)
  3. 实现链表的翻转()
  4. 从尾到头输出单链表(递归)
  5. 寻找单链表的中间节点(双指针)
  6. 检测一个链表是否有环(快慢指针)
  7. 在不知道头指针的情况下,删除指定的节点
  8. 如何判断两个链表是否相交(相交必然尾节点相同)
  9. 如果两个链表相交,如何找到相交的第一节点(两个链表的长短可能不一,长链表的指针移动到离尾部距离与短链表的长度一致,如此一来,二者到第一个相交的节点的距离相同)

如何实现栈(数组与链表均可)

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());
 }
 }
}

也可以采用两个队列实现站栈,只是稍微复杂;

位运算

  1. 用位移操作实现乘法运算(<< 、>>分别为乘2、除以2)
  2. 如何判断一个数是否为2的N次方(2的N次方的数都是最高位为1 ,例如16:10000,但是16-1的二进制为:

01111,与16的二进制的每一位都是不同的,可以n&(n-1)==0来判断n是不是2的N次方的数)

  1. 求二进制中的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) ) ;
 }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏微信公众号:Java团长

Java HashMap的工作原理

面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下...

632
来自专栏菩提树下的杨过

javascript:双链表-插入排序

数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。 换成链表时,显然无需做这种大量移动,根据每个节点的...

24210
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

1021
来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头...

45611
来自专栏F_Alex

数据结构与算法(四)-线性表之循环链表

前言:前面几篇介绍了线性表的顺序和链式存储结构,其中链式存储结构为单向链表(即一个方向的有限长度、不循环的链表),对于单链表,由于每个节点只存储了向后的指针,到...

2553
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

784
来自专栏眯眯眼猫头鹰的小树杈

leetcode347. Top K Frequent Elements

这里有一个额外要求即时间复杂度要优于O(n log n),也就是说我们无法采用先排序再顺序计算的方式来进行统计,因为最好的排序算法其平均的时间复杂度也需要O(n...

942
来自专栏于晓飞的专栏

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

1052
来自专栏java技术学习之道

HashMap的实现原理

1342
来自专栏java一日一条

HashMap的实现原理

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒...

6282

扫码关注云+社区

领取腾讯云代金券