公司笔试算法题

public class Test {
	public static void main(String[] args) {
		int[] initData = { 1, 2, 3, 4, 5 };
		// 对数组进行全排列
		perm(initData, 0, initData.length);
	}

	/**
	 * 对数组进行全排列，并打印符合条件的数组（4不能在第3位，3跟5不能相连）
	 * 
	 * @param t 要排列的数组
	 * @param start 起始位置
	 * @param end 结束位置
	 */
	public static void perm(int[] t, int start, int end) {
		if (start == end) {
			// 如果4在第三位或者3跟5相连，则不打印
			if (t[2] == 4 || is3NextTo5(t)) {

			} else {
				// 打印符合条件的数据
				for (int i = 0; i < t.length; i++) {
					System.out.print(t[i]);
				}
				System.out.println();

			}
		} else {
			for (int i = start; i < end; i++) {
				int temp = t[start];
				t[start] = t[i];
				t[i] = temp;

				//递归
				perm(t, start + 1, end);

				temp = t[start];
				t[start] = t[i];
				t[i] = temp;
			}
		}
	}

	/**
	 * 判断3跟5是否相连
	 * 
	 * @param t 数组
	 * @return true or false
	 */
	public static boolean is3NextTo5(int[] t) {
		for (int i = 0; i < t.length - 1; i++) {
			if (t[i] == 3 && t[i + 1] == 5)
				return true;
		}

		for (int i = 0; i < t.length - 1; i++) {
			if (t[i] == 5 && t[i + 1] == 3)
				return true;
		}

		return false;
	}
}

public static void permutation(int[] src, int m) {
		if (m == src.length) {
			if (src.length > 3 && src[2] != 4) {
				boolean bPrint = true;
				for (int i = 0; i < src.length - 1; i++) {
					if ((src[i] == 3 && src[i + 1] == 5)
							|| (src[i] == 5 && src[i + 1] == 3)) {
						bPrint = false;
					}
				}
				if (bPrint)
					print(src);
			}
		} else {
			for (int i = m; i < src.length; i++) {
				swap(src, m, i);
				permutation(src, m + 1);
				swap(src, m, i);
			}
		}
	}

	public static void print(int[] src) {
		for (int i = 0; i < src.length; i++)
			System.out.print(src[i]);
		System.out.println();
	}

	private static void swap(int[] src, int m, int i) {
		int t = src[m];
		src[m] = src[i];
		src[i] = t;
	}

public static int allListNum = 0;

public void ListNum(ArrayList numList, ArrayList printList)
{
    if (numList.Count == 1)
    {
        printList.Add(numList[0]);
        if ((int)printList[0] == 4) return;
        int i, j;
        for (i = 0; i < printList.Count; i++) {
            if ((int)printList[i] == 3)
            {
                if (i - 1 >= 0) {
                    if ((int)printList[i - 1] == 5) return;
                }
                if (i + 1 <= printList.Count - 1) {
                    if ((int)printList[i + 1] == 5) return;
                }
            }
        }
        for (j = 0; j < printList.Count; j++)
        {
            Console.Write((int)printList[j]);
        }
        allListNum++;
        Console.Write(";");
        printList.Clear();
    }
    else
    {
        for (int i = 0; i < numList.Count; i++)
        {
            bool appeared = false;
            for (int j = 0; j < i; j++)
            {
                if ((int)numList[j] == (int)numList[i])
                {
                    appeared = true;
                    break;
                }
            }
            if (appeared)
            {
                continue;
            }
            ArrayList newList = new ArrayList();
            ArrayList printNewList = new ArrayList();
            newList = (ArrayList)numList.Clone();
            printNewList = (ArrayList)printList.Clone();
            printNewList.Add(numList[i]);
            newList.RemoveAt(i);
            ListNum(newList, printNewList);
        }
    }
}

public class Qiz {
    
    private static final int[] ORIGINAL = {1, 2, 2, 3, 4, 5};
    private static final int LAST_P = ORIGINAL.length - 1;
    private static int s[] = new int[ORIGINAL.length];  //全排列栈

    public static void main(String[] args) {
        boolean isLast2Used = false;  //第二个2已被使用
        Set<Integer> usedNums = new HashSet<Integer>(); 
        Arrays.fill(s, -1);
        int p = 0; //当前位置
        int count = 0;  //结果计数
        do {
            int num = ++s[p];  //当前位置的取值
            
            if (num > LAST_P) {
                //回溯
                p--;
                if (p >= 0) {
                    //清空当前取值标记，注意在这里不能用num来代替s[p]，因为p已经变了
                    usedNums.remove(s[p]);
                    if (s[p] == 3) {
                        isLast2Used = false;
                    }
                }
            } else {
                if (!(usedNums.contains(num) || is3NextTo5(p) || (p == 2 && ORIGINAL[num] == 4) || (num == 2 && isLast2Used))) {
                    //如果当前取值合法
                    if (p == LAST_P) {
                        //如果已找到一个解
                        System.out.print((++count) + ":");
                        for (int i : s) {
                            System.out.print(ORIGINAL[i] + " ");
                        }
                        System.out.println();
                    } else {
                        //继续搜索前先设置有关标志
                        usedNums.add(num); 
                        if (num == 3) {
                            isLast2Used = true;
                        }

                        s[++p] = -1;  //前进一个位置
                    }
                }
            }
        } while (p > -1);
    }

    private static boolean is3NextTo5(int p) {
        if (p > 0) {
            int num1 = ORIGINAL[s[p]];
            int num2 = ORIGINAL[s[p-1]];
            if ((num1 == 3 && num2 == 5) ||
                (num1 == 5 && num2 == 3)) {
                return true;
            }
        }
        return false;
    }
}

public class Qiz {
    private static final int LAST_P = N - 1;
    private static int s[] = new int[LAST_P];  //全排列栈

    public static void main(String[] args) {
        Arrays.fill(s, 0);  //初始化栈
        int p = 0;           //用于记录当前位置的指针
        //TODO **初始化其他标志变量**
        do {
            int num = ++s[p];  //当前位置的取值基于原来的值加1，作为当前位置取值。
            
            if (s[p] > M) { //如果当前位置的取值已经超过了最大允许取值，则回溯到上一位置
                //回溯
                p--;
                if (p >= 0) {
                    //TODO **这时指针指向前一位置，该位置的当前取值已不属于解中，清空与这个取值有关的所有标记**
                }
            } else {
                if (/**TODO 其他特殊的判断合法条件，例如如果要全排列可以加入判断当前值不能与之前已确认的值重复**/) {
                    //如果当前取值合法
                    if (p == LAST_P) {  //指针已到最后，说明找到了一个解
                        //TODO ** 做爱做的事 **
                    } else {   //当前位置取值合法，但指针未到最后，需要继续向前搜索
                        //TODO ** 当前位置的取值已经确认属于解中，继续搜索前先根据当前取值设置有关标志 **
                        s[++p] = 0;  //前进一个位置，并初始化该位置
                    }
                }
            }
        } while (p > -1);  //位置指针已经退回到起点（即第一个位置的取值已经超过M），结束
    }
}