一、常见算法
1 斐波那契数列
- 递归实现
public static int fib(int n) {
if(n <= 0) return 0;
if(n == 1) return 1;
return fib(n-1) + fib(n-2);
}
- 递推实现
public static int fib2(int n) {
int first = 0;
int second = 1;
int sum = 0;
if(n <= 0) return first;
if(n ==1 ) return second;
for(int i = 2; i <= n; i++) {
sum = first + second;
first = second;
second = sum;
}
return sum;
}
2、用两个栈实现一个队列。
队列的声明如下，请实现它的两个函数appendTail 和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
public class Test {
public static class MList<T> {
// 插入栈，只用于插入的数据
private Stack<T> stack1 = new Stack<>();
// 弹出栈，只用于弹出数据
private Stack<T> stack2 = new Stack<>();
public MList() {
}
// 添加操作，成在队列尾部插入结点
public void appendTail(T t) {
stack1.add(t);
}
// 删除操作，在队列头部删除结点
public T deleteHead() {
// 先判断弹出栈是否为空，如果为空就将插入栈的所有数据弹出栈，
// 并且将弹出的数据压入弹出栈中
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.add(stack1.pop());
}
}
// 如果弹出栈中还没有数据就抛出异常
if (stack2.isEmpty()) {
throw new RuntimeException("No more element.");
}
// 返回弹出栈的栈顶元素，对应的就是队首元素。
return stack2.pop();
}
}
}
二、 链表相关
- 1、链表反转
private static Node reverseHead(Node head) {
if (head == null) {
return head;
}
Node pre = head;
Node cur = head.nextNode;
Node next = null;
while(cur != null){
next = cur.nextNode;
cur.nextNode = pre;
pre = cur;
cur = next;
}
//将原本头节点的next指针置为null
head.nextNode = null;
return pre;
}
- 2、 链表节点删除，O(1)时间复杂度
public class Test {
/**
* 链表结点
*/
public static class ListNode {
int value; // 保存链表的值
ListNode next; // 下一个结点
}
/**
* 给定单向链表的头指针和一个结点指针，定义一个函数在0(1)时间删除该结点,
* 【注意1：这个方法和文本上的不一样，书上的没有返回值，这个因为JAVA引用传递的原因，
* 如果删除的结点是头结点，如果不采用返回值的方式，那么头结点永远删除不了】
* 【注意2：输入的待删除结点必须是待链表中的结点，否则会引起错误，这个条件由用户进行保证】
*
* @param head 链表表的头
* @param toBeDeleted 待删除的结点
* @return 删除后的头结点
*/
public static ListNode deleteNode(ListNode head, ListNode toBeDeleted) {
// 如果输入参数有空值就返回表头结点
if (head == null || toBeDeleted == null) {
return head;
}
// 如果删除的是头结点，直接返回头结点的下一个结点
if (head == toBeDeleted) {
return head.next;
}
// 下面的情况链表至少有两个结点
// 在多个节点的情况下，如果删除的是最后一个元素
if (toBeDeleted.next == null) {
// 找待删除元素的前驱
ListNode tmp = head;
while (tmp.next != toBeDeleted) {
tmp = tmp.next;
}
// 删除待结点
tmp.next = null;
}
// 在多个节点的情况下，如果删除的是某个中间结点
else {
// 将下一个结点的值输入当前待删除的结点
toBeDeleted.value = toBeDeleted.next.value;
// 待删除的结点的下一个指向原先待删除引号的下下个结点，即将待删除的下一个结点删除
toBeDeleted.next = toBeDeleted.next.next;
}
// 返回删除节点后的链表头结点
return head;
}
}
3 有序链表合并
https://github.com/LRH1993/android_interview/blob/master/algorithm/For-offer/14.md
4 链表第一个公共子节点
https://www.cnblogs.com/edisonchou/p/4822675.html
- 5、链表中倒数第k个结点
public class Test {
public static class ListNode {
int value;
ListNode next;
}
/**
* 输入一个键表，输出该链表中倒数第k 个结点．为了符合大多数人的习惯，
* 本题从1开始计数，即链表的尾结点是倒数第1个结点．例如一个链表有6个结点，
* 从头结点开始它们的值依次是1、2、3、4、5 6。这个链表的倒数第3个结点是值为4的结点．
*
* @param head 链表的头结点
* @param k 倒数第k个结点
* @return 倒数第k个结点
*/
public static ListNode findKthToTail(ListNode head, int k) {
// 输入的链表不能为空，并且k大于0
if (k < 1 || head == null) {
return null;
}
// 指向头结点
ListNode pointer = head;
// 倒数第k个结点与倒数第一个结点相隔k-1个位置
// pointer先走k-1个位置
for (int i = 1; i < k; i++) {
// 说明还有结点
if (pointer.next != null) {
pointer = pointer.next;
}
// 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
else {
// 返回结果
return null;
}
}
// pointer还没有走到链表的末尾，那么pointer和head一起走，
// 当pointer走到最后一个结点即，pointer.next=null时，head就是倒数第k个结点
while (pointer.next != null) {
head = head.next;
pointer = pointer.next;
}
// 返回结果
return head;
}
}
三、二叉树相关
- 1、从上往下打印出二叉树的每个结点，同一层的结点按照从左向右的顺序打印。
思路：
这道题实质是考查树的遍历算法。从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点， 则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。
public class Test {
/**
* 二叉树的树结点
*/
public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
}
/**
* 从上往下打印出二叉树的每个结点，向一层的结点按照从左往右的顺序打印。
* 例如下的二叉树，
* 8
* / \
* 6 10
* / \ / \
* 5 7 9 11
* 则依次打印出8、6、10、5、3 、9、11.
*
* @param root 树的结点
*/
public static void printFromToBottom(BinaryTreeNode root) {
// 当结点非空时才进行操作
if (root != null) {
// 用于存放还未遍历的元素
Queue<BinaryTreeNode> list = new LinkedList<>();
// 将根结点入队
list.add(root);
// 用于记录当前处理的结点
BinaryTreeNode curNode;
// 队列非空则进行处理
while (!list.isEmpty()) {
// 删除队首元素
curNode = list.remove();
// 输出队首元素的值
System.out.print(curNode.value + " ");
// 如果左子结点不为空，则左子结点入队
if (curNode.left != null) {
list.add(curNode.left);
}
// 如果右子结点不为空，则左子结点入队
if (curNode.right != null) {
list.add(curNode.right);
}
}
}
}
}
网友评论