一些简单的面试经典算法题目

1. 反转二叉树

解：运用递归；反转左子树，反转右子树，交换左右子树

2.反转单链表

解:

1. 递归解法：
   Java
   public ListNode reverseList(ListNode head) {
   if(head == null || head.next == null){
   return head;
   }
   ListNode p = head.next;
   ListNode q = reverseList(p);
   head.next = null;
   p.next = head;
   return q;
   }

2. 头插法
```java```
 public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = head.next;
        head.next = null;      //注意此句
        ListNode q;
        while(p!=null){
             q = p.next;
             p.next = head;
             head = p;
             p = q;
        }
        return head;
    }

3.通过两个栈实现一个队列

解： A栈负责装入，B栈负责取出。取出操作的时候若B栈没有元素，将A栈元素全部取出压栈入B。

4. Tencent2013 笔试题：

题目： 用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
解析：该题的直观思想是将6个数组进行全排列，然后去除不符合条件的结果。关于全排列的实现算法，大家可以参考这个链接 全排列（含递归和非递归的解法）,这里我们给出两种其他思路。
解法一：将6个节点构成3和5不连通的无向图，分别以每个节点为初始节点进行图的遍历。结果去重（可以考虑直接将遍历结果存入set结构中），然后去“4”在第三位的。
Java
public class Tencent2013 {
private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet<String> set = new TreeSet<String>();
private void run() { //构建图
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}
// 3 is the 4th num, 5 is the 6th num. can not be neighbor
a[3][5] = 0;
a[5][3] = 0;
for (int i = 0; i < n; i++) {
depthFirstSearch(i);
}
//
for (String str : set) {
if (str.indexOf("4") != 2) {
System.out.println(str);
}
}
}
//深度优先遍历 graph
private void depthFirstSearch(int i) {
visited[i] = true;
result += b[i];
if (result.length() == n) {
set.add(result);
}
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
}
}
result = result.substring(0, result.length() - 1);
visited[i] = false;
}
public static void main(String[] args) {
new Tencent2013().run();
}
}

**解法二**：（思路广）
该算法的性能比较差，对于有n个数的话，循环的次数是10的n次方级，n如果比较大的话绝对不能采用该法解题。这里只是给出作为一种新颖的思路。
```Java```
//Java代码
for (int i = 122345; i <= 543221; i++) {    
  String sb = String.valueOf(i);    
  String temp = sb.replaceFirst("1", "a");    
  temp = temp.replaceFirst("2", "a");    
  temp = temp.replaceFirst("2", "a");   
  temp = temp.replaceFirst("3", "a");    
  temp = temp.replaceFirst("4", "a");    
  temp = temp.replaceFirst("5", "a");    
  if (!"aaaaaa".equals(temp))      continue;    
  //排除4在第三位    
  if (sb.indexOf("4") == 2)       continue;    
  //3 and 5 be together    
  if (sb.indexOf("35") > -1 || sb.indexOf("53") > -1)    continue;      
  System.out.println(i);
}

5.旋转字符串

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
解：三步反转法：

1. 将要旋转的部分反转
2. 将剩余的部分反转
3. 反转整个字符串
   Java
   public String reverse(String s) {
   StringBuilder builder = new StringBuilder(s);
   builder = builder.reverse();
   return builder.toString();
   }
   public String moveToTail(String s, int n) {
   String s1 = this.reverse(s.substring(0, n));
   String s2 = this.reverse(s.substring(n));
   return this.reverse(s1 + s2);
   }