1.给定整数N，输出所有匹配的小括号序列。（2014-03北京某移动互联网公司面试题）
例如：N=3
输出：
((()))
(()())
(())()
()(())
()()()
public void output(int n){
//.....
}
参考答案：
public static void test(){
brackets(3,0, "");
System.out.println("-----------------------------");
brackets(3, 0, 0, new char[3 * 2]);
}
/**
* 方法1
* @param openStock
* @param closeStock
* @param s
*/
public static void brackets(int openStock, int closeStock, String s) {
if (openStock == 0 && closeStock == 0) {//当开括号的数据和比括号的数目都为零时
System.out.println(s);
}
//如果开括号数大于0，那么就添加一个开括号，开括号的数目-1，闭括号的数目+1
if (openStock > 0) {
brackets(openStock-1, closeStock+1, s + "(");
}
//如果闭括号的数目大于0，那么就添加一个闭括号，闭括号的数目-1
if (closeStock > 0) {
brackets(openStock, closeStock-1, s + ")");
}
}
/**
* 方法2
* @param openStock
* @param closeStock
* @param index
* @param arr
*/
public static void brackets(int openStock, int closeStock, int index, char[] arr) {
while (closeStock >= 0) {
if (openStock > 0) {
arr[index] = '(';
brackets(openStock-1, closeStock+1, index+1, arr);
}
if (closeStock-- > 0) {
arr[index++] = ')';
if (index == arr.length) {
System.out.println(arr);
}
}
}
}
2.字符串反转（2014-03北京某移动互联网公司面试题）
输入字符串：I am a student
输出：student a am I
要求：不能使用字符串的高级函数，空间复杂度为O(1)
public void reverse(String str){
//....
}
3.给定整数N，按要求输出如下Z字型矩阵（N*N）：（2014-03北京某移动互联网公司面试题）
例如：N=4
输出：
要求：空间复杂度为O（N）
public void output(int n){
//.....
}
public static void display(int N){
int []a=new int[N];//先声明一个数组
for(int i=1;i<=N;i++){//先打印第一行
if(i%2==1){//第一行中奇数序列的数
for (int j = 1; j <=i; j++) {
a[i-1]+=j;
}
}else {
a[i-1]=a[i-2]+1;
}
System.out.print(a[i-1]+"\t");
}
System.out.println();
for(int k=2;k<=N;k++){
if(k%2==0){
for (int i = 1; i <=N-1; i++) {
if(i%2==1){
a[i-1]=a[i]+1;
}else {
a[i-1]=a[i]-1;
}
System.out.print(a[i-1]+"\t");
}
a[N-1]=N*(N+1)/2;
for(int i=N-1;i>=N-k+1;i--){
a[N-1]+=i;
}
System.out.print(a[N-1]+"\t");
}else {
for (int i = 1; i <=N-1; i++) {
if(i%2==1){
a[i-1]=a[i]-1;
}else {
a[i-1]=a[i]+1;
}
System.out.print(a[i-1]+"\t");
}
a[N-1]=a[N-1]+1;
System.out.print(a[N-1]+"\t");
}
System.out.println();
}
}
参考答案：
4.求二叉树任意两个节点的最低公共祖先节点.（2014-03北京某移动互联网公司面试题）
public class Node{
int data;
Node left;
Node right;
}
public Node find(Node root,Node node1,Node node2){
//..............
}
5.有序循环链表，插入方法（2014-03北京某移动互联网公司面试题）
public class Node{
int value;
Node next;
}
public void insert(Node root,int v){
//.............
}
6.堆排序（2014-3国内某著名互联网公司-实习生笔试题）
7.Dijkstra算法（2014-3国内某著名互联网公司-实习生笔试题）
先写这么多，后续再搜集添加。