程序员面试金典（一）

本文主要是介绍程序员面试金典（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.算法题的五种解法

方法一：举例法

举例法简单来讲就是数学中的归纳推理和演绎推理，根据特征找到通解，最常见的是在数列运算过程中，大家熟知的斐波那契数列，1+....+100,等等，都可以使用举例法解答。

方法二：模式匹配法

模式匹配法是指将现有问题与相似问题作类比，看看能否通过修改相关问题的解法来解决新问题。

方法三：简化推广法

采用简化推广法，具体做法对于问题可以分步进行处理。首先，我们会修改某个约束条件，比如数据类型或数据量，从而简化这个问题。接着，转而处理这个问题的简化版本。最后，一旦找到解决简化版问题的算法，我们就可以基于这个问题进行推广，并调整最终的解决方案，找到最优解。

方法四：简单构造法

对于某些问题，简单构造法非常高效。使用简单构造法，我们会从最基本的情况（比如n=1）来解决问题，还是拿斐波那契数列来举例子，最后可以发现，这是一个递归方法可以解决的问题。所以，简单构造法最后往往会演变成递归法。

方法五：数据结构头脑风暴法

数据结构头脑风暴法过程往往会相对来说较复杂。运用数据结构中的链表，数组，二叉树，堆来解决问题，根据具体情况选择最优解。

2.数组与字符串

2.1散列表

散列表是一种将键（key）映射为值（value）从而实现快速查找的数据结构。散列表包含一个底层数组和一个散列函数（hash function）。插入一个对象及对应的键时，散列函数会将键映射为数组的一个索引。这个对象就回储存到数组中该索引的位置。

public HashMap<Integer, Student> buildMap(Student[] students){HashMap<Integer, Student> map = new HashMap<>();for (student s : students) {map.put(s.getId(),s);}return map;}

2.2 ArrayList（动态数组）

ArrayList，即动态数组，是一种按需调整大小的数组，数据访问时间为O（1）。一种典型的实现是在数组存满时扩容，每次扩容时O（n），均摊下来还是O（1）。

public ArrayList<String> merges(String[] words,String[] more){ArrayList<String> sentence = new ArrayList<>();for (String w : words) {sentence.add(w);}for (String m : more) {sentence.add(m);}return sentence;
}

2.3 StringBuffer

在Java编程中把一组字符串拼接起来，可以使用String str = "hello" + "字符";但是这样操作相当于每次都创建一个string对象的字符串，运行效率低下而且还特别占用内存，为了简化这种状况可以使用StringBuffer。

public String mergeStr(String[] string){StringBuffer sb = new StringBuffer();for (String str : string) {sb.append(str);}return sb.toString();
}

3.链表

链表问题往往涉及递归操作，非常依赖概念。

3.1创建链表

以下代码为创建一个基本的单向链表。

class Node{Node next = null;int data;public Node(int d){data = d;}void appendToTail(int d){Node end = new Node(d);Node n = this;while(n.next != null){n = n.next;}n.next = end;}
}

3.2删除单向链表中的节点

删除单向链表，给定一个节点n，我们先找到它的前趋节点prev，并将prev.next设置为n.next。如果是双向链表，还要更新n.next，将n.next.prev置为n.prev.

注意：（1）检查空指针；（2）必要时更新表头（head）或表尾（tail）指针。

    Node deleteNode(Node head,int d){Node n = head;if (n.data == d) {return head.next;//表头指向下一个节点}while(n.next ! = null){if (n.next.data == d) {n.next = n.next.next;return head; //表头不变}n = n.next;}return head;}

3.3“快行指针”技巧

在处理链表问题时，“快行指针”（runner，或者称为第二个指针）是一种很常见的技巧，“快行指针”指的是同时用两个指针来迭代访问链表，只不过其中一个比另一个超前一些。“快”指针往往先行几步，或与“慢”指针相差固定的步数。

3.4递归问题

许多链表问题都要用到递归。当然，还需注意递归算法至少要占用O（n）空间，其中n为递归调用层数。

4.栈和队列

4.1实现一个栈

栈采用后进先出（LIFO）顺序。实际上，栈和链表本质上是一样的，用户只能看到栈顶元素。

class Stacks{Node top;Object pop(){if (top != null) {Object item = top.data;top = top.next;return item;}return null;}void push(Object item){Node t = new Node(item);t.next = top;top = t;}Object peek(){return top.data;}
}

以下是一个具体栈的实例：

public class Stacks {static String[] months = {"Jan","Feb","Mar","Apr","May","June","Aug","Sep","Oct","Nov","Dec"};public static void main(String[] args) {Stack stack = new Stack();//进栈，先进元素压入栈底，最后的元素在栈顶for (int i = 0; i < months.length; i++) {stack.push(months[i]+"");}System.out.println("stk = " + stack);stack.addElement("************");System.out.println("element 5 = " + stack.elementAt(5));System.out.println("popping elements: ");//出栈后进先出，栈顶元素最先被输出while (!stack.empty()) {System.out.println(stack.pop());}}
}

4.2实现一个队列

队列采用先进先出（FIFO）顺序。队列也可以用链表实现，新增元素追加至表尾。

class Queue{Node first,last;void enqueue(Object item){if (first == null) {last = new Node(item);first = last;}else{last.next = new Node(item);last = last.next;}}Object dequeue(){if (first != null) {Object item = first.data;first = first.next;return item;}}
}

5.树和图

5.1需要注意的潜在问题

二叉树与二叉查找树
二叉查找树一般会有附加条件：对于任意节点，左子节点小于或等于当前节点，后者又小于所有右子节点。
平衡与不平衡
树的平衡有多重方法，平衡一棵树只意味着子树的深度差不会超过一定值，并不表示左子树和右子树的深度完全相同。
完满和完整（Full and Complete）
完满和完整树的所有叶节点都在树的底部，所有非叶节点都有两个子节点。完满和完整树必须满足 $2^n-1$ 个节点。

5.2二叉树遍历

二叉树遍历一般分为中序、后序和前序遍历。

5.3树的平衡：红黑树和平衡二叉树

5.4单词查找树（trie）

trie树是n层树的一种变体，其中每个节点存储有字符。整棵树的每条路径自上而下表示一个单词。

5.5图的遍历

深度优先搜索（DFS）
在DFS中，先访问节点r，然后循环访问r的每个相邻节点。在访问r的相邻节点n时，会在访问r的其他相邻节点之前先访问n的所有相邻节点。前序和树遍历的其他形式都是一种DFS，区别是对图实现该算法时，必须先检查该节点是否已访问。否则，可能会死循环。
实现DFS伪代码：

void search(Node root){if(root == null) return;visit(root);root.visited = true;foreach(Node n in root.adjacent){if(n.visited == false) search(n);}
}

广度优先搜索（BFS）
在搜索r的“孙子节点”之前先访问节点r的所有相邻节点。一般用队列实现的迭代方案最有效。
实现BFS伪代码：

void search(Node root){Queue queue = new Queue();root.visited = true;visit(root);queue.enqueue(root);//加至队列尾部while(!queue.isEmpty()){Node r = queue.dequeue();//从队列头部移除foreach(Node n in r.adjacent){if(n.visited ==false){visit(n);n.visited = true;queue.enqueue(n);}}}
}