总结的笔试/面试算法题
2016-09-19 本文已影响983人
MigrationUK
目录
1. 栈和队列
1.用两个队列实现栈
2.用两个栈实现队列
3.实现一个栈，可以用常数级时间找出栈中的最小值
4.判断栈的压栈、弹栈序列是否合法
2. 链表
1.反转链表（使用递归和迭代两种解法，了解头插法）
2.删除链表的当前节点
3.删除倒数第 k 个节点
4.两个有序链表合并
5.判断链表是否有环
6.两个链表的第一个公共节点（提示：考虑链表有环的情况）
7.删除链表中重复节点
3. 树、二分
1.一个序列，它的形式是12349678，9是峰值，经历了一个上升又下降的过程，找出里面的最大值的位置O(logN)
2.深度优先遍历二叉树
3.广度优先遍历二叉树
4.前序遍历二叉树
5.中序遍历二叉树
6.输入一棵二叉树的根结点,求该树的深度
7.根据中序和后序遍历结果重建二叉树
8.根据中序和前序遍历结果重建二叉树
9.翻转二叉树
10.判断某个数组是不是二叉树的后序遍历结果
11.二叉树中和为某个值的路径
12.二叉树中某个节点的下一个节点
4. 递归、动态规划
1.股票买入卖出的最佳时间
2.递归方法求数组的最大值
3.背包问题
4.连续子数组的最大和
5.实现简单的正则表达式匹配
5.字符串
1.给一串字符串比如abbbcccd，输出a1b3c3d1,O(n)
2.例如输入字符串”I am a student. ”,则输出”student. a am I”
3.比如输入字符串”abcefg”和数字 2,该函数将返回左旋转 2 位得到的结”cdefab”
4.判断是否是回文字符
5.最长回文子串
6.最长无重复子串
7.字符串转数字
8.KMP 算法
9.字符串全排列
10.翻转字符串
6. 排序
1.归并排序、拓展：求数组中的逆序对个数
2.快速排序 重点：partion 函数的实现
3.堆排序
4.数组元素值域已知时，考虑 基数排序 和 桶排序
7. 大数据
1.海量N个数中求前M大个数（选择第M大数）
8. 数组、矩阵
1.回形，矩阵
2.蛇形矩阵
3.在排序数组中查找和为给定值的两个数字（思路）
9. 位运算
1.给一个十进制数字，求它的二进制表示中，有多少个 1 (n &= n - 1)
2.给一个数组，所有数字都出现了偶数次，只有一个出现了一次，找出这个数
3.给一个数组，所有数字都出现了三次，只有一个出现了一次，找出这个数
4.给一个数组，所有数组都出现了偶数次，只有两个数字出现了一次，找出这两个数
10. JAVA相关题
1.生产者/消费者（wait() / notify()方法）
2.生产者/消费者（await() / signal()方法）
3.生产者/消费者（BlockingQueue阻塞队列方法）
4.观察者设计模式
---持续跟新，欢迎纠错---
---【】数字越大问题越难---
--- 根据目录Ctrl C.V快速定位题解答---
栈和队列
- 【2】用两个队列实现栈
public class TwoQueue { private LinkedList<String> queue1; private LinkedList<String> queue2; public TwoQueue(){ queue1 = new LinkedList<String>(); queue2 = new LinkedList<String>(); } public String pop(){ String re =null; if(queue1.size() == 0 && queue2.size() == 0){ return null; } if(queue2.size() == 0){ while(queue1.size() >0){ re = queue1.removeFirst(); if(queue1.size() != 0){ //最后一个不存进去 queue2.addLast(re); } } }else if(queue1.size() == 0){ while(queue2.size() >0){ re = queue2.removeFirst(); if(queue2.size()!=0){ queue1.addLast(re); } } } return re; } public String push(String str){ if(queue1.size() ==0 && queue2.size() == 0){ queue1.addLast(str); } if(queue1.size()!=0){ queue1.addLast(str); }else if(queue2.size()!=0){ queue2.addLast(str); } return str; } - 【2】用两个栈实现队列
class MList<T> { // 插入栈,只用于插入的数据 private Stack<T> stack1 = new Stack<T>(); // 弹出栈,只用于弹出数据 private Stack<T> stack2 = new Stack<T>(); 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(); } } - 【2】实现一个栈，可以用常数级时间找出栈中的最小值
- 【3】判断栈的压栈、弹栈序列是否合法
链表
-
【2】反转链表（使用递归和迭代两种解法，了解头插法）
public static ListNode reverseList(ListNode head) { // 创建一个临时结点,当作尾插法的逻辑头结点 ListNode root = new ListNode(); // 逻辑头结点点的下一个结点为空 root.next = null; // 用于记录要处理的下一个结点 ListNode next; // 当前处理的结点不为空 while (head != null) { // 记录要处理的下一个结点 next = head.next; // 当前结点的下一个结点指向逻辑头结点的下一个结点 head.next = root.next; // 逻辑头结点的下一个结点指向当前处理的结点 root.next = head; // 上面操作完成了一个结点的头插 // 当前结点指向下一个要处理的结点 head = next; } // 逻辑头结点的下一个结点就是返回后的头结点 return root.next; } -
【3】删除链表的当前节点
-
【3】删除倒数第 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】两个有序链表合并
-
【2*】判断链表是否有环
-
【3*】两个链表的第一个公共节点（提示：考虑链表有环的情况）
public static ListNode findFirstCommonNode(ListNode head1, ListNode head2) { int length1 = getListLength(head1); int length2 = getListLength(head2); int diff = length1 - length2; ListNode longListHead = head1; ListNode shortListHead = head2; if (diff < 0) { longListHead = head2; shortListHead = head1; diff = length2 - length1; } for (int i = 0; i < diff; i++) { longListHead = longListHead.next; } while (longListHead != null && shortListHead != null && longListHead != shortListHead) { longListHead = longListHead.next; shortListHead = shortListHead.next; } // 返回第一个相同的公共结点,如果没有返回null return longListHead; } private static int getListLength(ListNode head) { int result = 0; while (head != null) { result++; head = head.next; } return result; } -
【3】删除链表中重复节点
树、二分
-
【2】一个序列，它的形式是12349678，9是峰值，经历了一个上升又下降的过程，找出里面的最大值的位置O(logN)
public static int findPeakElement(int [] nums){ if (nums.length ==1) return 0; int low = 0, high = nums.length - 1, mid; while (low+1 < high) { mid = low + ((high - low) >> 1); if (nums[mid] < nums[mid - 1]) high = mid; //上坡 else if (nums[mid] < nums[mid+1]) low = mid; //下坡 else return mid; } return nums[low ] >nums[high] ?low:high; } -
【2】深度优先遍历二叉树，其实就是前序遍历
public void depthOrderTraversal(){ if(root==null){ System.out.println("empty tree"); return; } ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>(); stack.push(root); while(stack.isEmpty()==false){ TreeNode node=stack.pop(); System.out.print(node.value+" "); if(node.right!=null){ stack.push(node.right); } if(node.left!=null){ stack.push(node.left); } } System.out.print("\n"); } -
【2】二叉树广度优先遍历
public void levelOrderTraversal(){ if(root==null){ System.out.println("empty tree"); return; } ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>(); queue.add(root); while(queue.isEmpty()==false){ TreeNode node=queue.remove(); //从队头移除 System.out.print(node.value+" "); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } System.out.print("\n"); } -
前序遍历二叉树
public void preOrderTraverse1(TreeNoderoot){ if(root!=null){ System.out.print(root.val+""); preOrderTraverse1(root.left); preOrderTraverse1(root.right); } } //非递归 public void preOrderTraverse2(TreeNoderoot){ LinkedList<TreeNode>stack=newLinkedList<>(); TreeNodepNode=root; while(pNode!=null||!stack.isEmpty()){ if(pNode!=null){ System.out.print(pNode.val+""); stack.push(pNode); pNode=pNode.left; }else{//pNode==null&&!stack.isEmpty() TreeNodenode=stack.pop(); pNode=node.right; } } } -
中序遍历二叉树
public void inOrderTraverse1(TreeNoderoot){ if(root!=null){ inOrderTraverse1(root.left); System.out.print(root.val+""); inOrderTraverse1(root.right); } } //非递归 public void inOrderTraverse2(TreeNoderoot){ LinkedList<TreeNode>stack=newLinkedList<>(); TreeNodepNode=root; while(pNode!=null||!stack.isEmpty()){ if(pNode!=null){ stack.push(pNode); pNode=pNode.left; }else{//pNode==null&&!stack.isEmpty() TreeNodenode=stack.pop(); System.out.print(node.val+""); pNode=node.right; } } } -
【2】输入一棵二叉树的根结点,求该树的深度
public static int treeDepth(BinaryTreeNode root) { if (root == null) { return 0; } int left = treeDepth(root.left); int right = treeDepth(root.right); return left > right ? (left + 1) : (right + 1); } -
【3】根据中序和后序遍历结果重建二叉树
-
【3】根据中序和前序遍历结果重建二叉树
public static BinaryTreeNode construct(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) { // 开始位置大于结束位置说明已经没有需要处理的元素了 if (ps > pe) { return null; } // 取前序遍历的第一个数字,就是当前的根结点 int value = preorder[ps]; int index = is; // 在中序遍历的数组中找根结点的位置 while (index <= ie && inorder[index] != value) { index++; } // 如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常 if (index > ie) { throw new RuntimeException("Invalid input"); } // 创建当前的根结点,并且为结点赋值 BinaryTreeNode node = new BinaryTreeNode(); node.value = value; // 递归构建当前根结点的左子树,左子树的元素个数:index-is+1个 // 左子树对应的前序遍历的位置在[ps+1, ps+index-is] // 左子树对应的中序遍历的位置在[is, index-1] node.left = construct(preorder, ps + 1, ps + index - is, inorder, is, index - 1); // 递归构建当前根结点的右子树,右子树的元素个数:ie-index个 // 右子树对应的前序遍历的位置在[ps+index-is+1, pe] // 右子树对应的中序遍历的位置在[index+1, ie] node.right = construct(preorder, ps + index - is + 1, pe, inorder, index + 1, ie); // 返回创建的根结点 return node; } -
【2】翻转二叉树
public static void mirror(BinaryTreeNode node) { // 如果当前结点不为空则进行操作 if (node != null) { // 下面是交换结点左右两个子树 BinaryTreeNode tmp = node.left; node.left = node.right; node.right = tmp; // 对结点的左右两个子树进行处理 mirror(node.left); mirror(node.right); } } -
【3】判断某个数组是不是二叉树的后序遍历结果 (剑指 offer 第 24 题)
public static boolean verifySequenceOfBST(int[] sequence, int start, int end) { // 如果对应要处理的数据只有一个或者已经没有数据要处理(start>end)就返回true if (start >= end) { return true; } // 从左向右找第一个不大于根结点(sequence[end])的元素的位置 int index = start; while (index < end - 1 && sequence[index] < sequence[end]) { index++; } // 执行到此处[end, index-1]的元素都是小于根结点的(sequence[end]) // [end, // index-1]可以看作是根结点的左子树 // right用于记录第一个不小于根结点的元素的位置 int right = index; // 接下来要保证[index, end-1]的所有元素都是大于根根点的【A】 // 因为[index, end-1]只有成为根结点的右子树 // 从第一个不小于根结点的元素开始,找第一个不大于根结点的元素 while (index < end - 1 && sequence[index] > sequence[end]) { index++; } // 如果【A】条件满足,那么一定有index=end-1, // 如果不满足那说明根结点的右子树[index, end-1]中有小于等于根结点的元素, // 不符合二叉搜索树的定义,返回false if (index != end - 1) { return false; } // 执行到此处说明直到目前为止,还是合法的 // [start, index-1]为根结点左子树的位置 // [index, end-1]为根结点右子树的位置 index = right; return verifySequenceOfBST(sequence, start, index - 1) && verifySequenceOfBST(sequence, index, end - 1); } -
【3】二叉树中和为某个值的路径
public static void findPath(BinaryTreeNode root, int curSum, int expectedSum, List<Integer> result) { // 如果结点不为空就进行处理 if (root != null) { // 加上当前结点的值 curSum += root.value; // 将当前结点入队 result.add(root.value); // 如果当前结点的值小于期望的和 if (curSum < expectedSum) { // 递归处理左子树 findPath(root.left, curSum, expectedSum, result); // 递归处理右子树 findPath(root.right, curSum, expectedSum, result); } // 如果当前和与期望的和相等 else if (curSum == expectedSum) { // 当前结点是叶结点,则输出结果 if (root.left == null && root.right == null) { System.out.println(result); } } // 移除当前结点，回溯吧 result.remove(result.size() - 1); } } -
【3*】二叉树中某个节点的下一个节点 (强烈推荐准备一下，剑指 offer 第 58 题)
递归、动态规划
- 股票买入卖出的最佳时间
public int maxProfit(int num[]){ int max=-1; int ans=-1; for(inti=len-1;i>=0;i--) if(num[i]>max) max=num[i]; if(max-num[i]>ans) ans=max-num[i]; return ans; } - 【2】递归方法求数组的最大值
int max(int arr[], int len) { if (1 == len){ // 只有一个元素 return arr[0]; } int a = arr[0]; // 第一个元素 int b = max(arr + 1, len - 1); // 第二个元素起的最大值 return a > b ? a : b; } - 【2】背包问题
- 【3】连续子数组的最大和
- 【4】实现简单的正则表达式匹配
字符串
-
【2】给一串字符串比如abbbcccd，输出a1b3c3d1,O(n)
public static void main(String[] args) { String str= "abbbcccd"; int[] count= new int[256]; for (int i = 0 ;i<str.length();i++) { count[str.charAt(i)]++; } for (int i = 0;i<256;i++) { if(count[i]>0){ System.out.printf("%c%d",i,count[i]); } } } -
【2】例如输入字符串”I am a student. ”,则输出”student. a am I”
public static void reverse(char[] data, int start, int end) { if (data == null || data.length < 1 || start < 0 || end > data.length || start > end) { return; } while (start < end) { char tmp = data[start]; data[start] = data[end]; data[end] = tmp; start++; end--; } } public static char[] reverseSentence(char[] data) { if (data == null || data.length < 1) { return data; } reverse(data, 0, data.length - 1);// 首先全局逆转 int start = 0; int end = 0; while (start < data.length) { if (data[start] == ' ') { // 排除开头空格 start++; end++; } else if (end == data.length || data[end] == ' ') {// 单词结束边界 reverse(data, start, end - 1); end++; start = end; } else { end++; } } return data; } -
【2】比如输入字符串”abcefg”和数字 2,该函数将返回左旋转 2 位得到的结”cdefab”
public static void reverse(char[] data, int start, int end) { if (data == null || data.length < 1 || start < 0 || end > data.length || start > end) { return; } while (start < end) { char tmp = data[start]; data[start] = data[end]; data[end] = tmp; start++; end--; } } public static char[] leftRotateString(char[] data, int n) { if (data == null || n < 0 || n > data.length) { return data; } reverse(data, 0, data.length - 1); reverse(data, 0, data.length - n - 1); reverse(data, data.length - n, data.length - 1); return data; } -
【2】java判断是否是回文字符
public static boolean isPalidrome(Stringstr){ char[] ch=str.toCharArray(); int len=ch.length; for(inti=0,intj=len-1;i<=j;){ if(ch[i++]==ch[j--]){ }else{ return false; } } return ture; } -
【3】最长回文子串
-
【3】最长无重复子串
-
【1*】字符串转数字
-
【4】KMP 算法
-
【2】字符串全排列
public static void permutation(char[] chars, int begin) { // 如果是最后一个元素了,就输出排列结果 if (chars.length - 1 == begin) { System.out.print(new String(chars) + " "); } else { char tmp; // 对当前还未处理的字符串进行处理,每个字符都可以作为当前处理位置的元素 for (int i = begin; i < chars.length; i++) { // 下面是交换元素的位置 tmp = chars[begin]; chars[begin] = chars[i]; chars[i] = tmp; // 处理下一个位置 permutation(chars, begin + 1); // 恢复 tmp = chars[begin]; chars[begin] = chars[i]; chars[i] = tmp; } } }``` -
【2*】翻转字符串
排序
- 归并排序、拓展：求数组中的逆序对个数
- 快速排序 重点：partion 函数的实现
- 堆排序
- 数组元素值域已知时，考虑 基数排序 和 桶排序
大数据
1.【3】海量N个数中求前M大个数（选择第M大数）
数组、矩阵
- 回形矩阵
public static void spiralOrderPrint(int[][] matrix) { int tR = 0; int tC = 0; int dR = matrix.length - 1; int dC = matrix[0].length - 1; while (tR <= dR && tC <= dC) { printEdge(matrix, tR++, tC++, dR--, dC--); } } public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) { if (tR == dR) { // 子矩阵只有一行时 for (int i = tC; i <= dC; i++) { System.out.print(m[tR][i] + " "); } } else if (tC == dC) { // 子矩阵只有一列时 for (int i = tR; i <= dR; i++) { System.out.print(m[i][tC] + " "); } } else { // 一般情况 int curC = tC; int curR = tR; while (curC != dC) { System.out.print(m[tR][curC] + " "); curC++; } while (curR != dR) { System.out.print(m[curR][dC] + " "); curR++; } while (curC != tC) { System.out.print(m[dR][curC] + " "); curC--; } while (curR != tR) { System.out.print(m[curR][tC] + " "); curR--; } } }``` - 蛇形矩阵
- 【2】在排序数组中查找和为给定值的两个数字（思路）
- 找到数组的第一个数字和最后一个数字。
- 当两个数字的和大于输入的数字时，把较大的数字往前移动；
- 当两个数字的和小于数字时，把较小的数字往后移动；
- 当相等时，输出等式。这样扫描的顺序是从数组的两端向数组的中间扫描。
位运算
- 【2】给一个十进制数字，求它的二进制表示中，有多少个 1 (n &= n - 1)
- 【3】给一个数组，所有数字都出现了偶数次，只有一个出现了一次，找出这个数
- 【4】给一个数组，所有数字都出现了三次，只有一个出现了一次，找出这个数
- 【3】给一个数组，所有数组都出现了偶数次，只有两个数字出现了一次，找出这两个数
JAVA相关题
-
【2】生产者/消费者（wait() / notify()方法）
public class Storage { // 仓库最大存储量 private final int MAX_SIZE = 100; // 仓库存储的载体 private LinkedList<Object> list = new LinkedList<Object>(); // 生产num个产品 public void produce(int num) { // 同步代码段 synchronized (list) { // 如果仓库剩余容量不足 while (list.size() + num > MAX_SIZE) { try { list.wait(); // 由于条件不满足，生产阻塞 } catch (InterruptedException e) { e.printStackTrace(); } } // 生产条件满足情况下，生产num个产品 for (int i = 1; i <= num; ++i) { list.add(new Object()); } list.notifyAll(); } } // 消费num个产品 public void consume(int num) { // 同步代码段 synchronized (list) { // 如果仓库存储量不足 while (list.size() < num) { try { list.wait(); // 由于条件不满足，消费阻塞 } catch (InterruptedException e) { e.printStackTrace(); } } // 消费条件满足情况下，消费num个产品 for (int i = 1; i <= num; ++i) { list.remove(); } list.notifyAll(); } } } -
【3】生产者/消费者（await() / signal()方法）
public class Storage { // 仓库最大存储量 private final int MAX_SIZE = 100; // 仓库存储的载体 private LinkedList<Object> list = new LinkedList<Object>(); // 锁 private final Lock lock = new ReentrantLock(); // 仓库满的条件变量 private final Condition full = lock.newCondition(); // 仓库空的条件变量 private final Condition empty = lock.newCondition(); // 生产num个产品 public void produce(int num) { // 获得锁 lock.lock(); // 如果仓库剩余容量不足 while (list.size() + num > MAX_SIZE) { try { full.await(); // 由于条件不满足，生产阻塞 } catch (InterruptedException e) { e.printStackTrace(); } } // 生产条件满足情况下，生产num个产品 for (int i = 1; i <= num; ++i) { list.add(new Object()); } // 唤醒其他所有线程 full.signalAll(); empty.signalAll(); // 释放锁 lock.unlock(); } // 消费num个产品 public void consume(int num) { // 获得锁 lock.lock(); // 如果仓库存储量不足 while (list.size() < num) { try { empty.await(); // 由于条件不满足，消费阻塞 } catch (InterruptedException e) { e.printStackTrace(); } } // 消费条件满足情况下，消费num个产品 for (int i = 1; i <= num; ++i) { list.remove(); } // 唤醒其他所有线程 full.signalAll(); empty.signalAll(); // 释放锁 lock.unlock(); } } -
【2】生产者/消费者（BlockingQueue阻塞队列方法）
public class Storage { // 仓库最大存储量 private final int MAX_SIZE = 100; // 仓库存储的载体 private LinkedBlockingQueue<Object> list = new LinkedBlockingQueue<Object>(100); // 生产num个产品 public void produce(int num) { // 如果仓库剩余容量为0 if (list.size() == MAX_SIZE) { System.out.println("暂时不能执行生产任务!"); } // 生产条件满足情况下，生产num个产品 for (int i = 1; i <= num; ++i) { try { // 放入产品，自动阻塞 list.put(new Object()); } catch (InterruptedException e) { e.printStackTrace(); } } } // 消费num个产品 public void consume(int num) { // 如果仓库存储量不足 if (list.size() == 0) { System.out.println("暂时不能执行消费任务!"); } // 消费条件满足情况下，消费num个产品 for (int i = 1; i <= num; ++i) { try { // 消费产品，自动阻塞 list.take(); } catch (InterruptedException e) { e.printStackTrace(); } } } } -
【3】观察者设计模式
public class SimpleObservable extends Observable{ private int data = 0; public int getData(){ return data; } public void setData(int i){ if(this.data != i) { this.data = i; setChanged(); //只有在setChange()被调用后，notifyObservers()才会去调用update()，否则什么都不干。 notifyObservers(); } } } public class SimpleObserver implements Observer{ public SimpleObserver(SimpleObservable simpleObservable){ simpleObservable.addObserver(this ); } public void update(Observable observable ,Object data){ // data为任意对象，用于传递参数 System.out.println(“Data has changed to” + (SimpleObservable)observable.getData()); } } public class SimpleTest{ public static void main(String[] args){ SimpleObservable doc = new SimpleObservable (); SimpleObserver view = new SimpleObserver (doc); doc.setData(1); doc.setData(2); doc.setData(2); doc.setData(3); } }
