[线上课程题目]2014-12-22_YY线上课程题目及代码

12月22日, 2014 代码 knockgater 126次

[线上课程题目]2014-12-22_YY线上课程题目及代码

12月22日, 2014 126次

题目一：

给定一个字符串str，判断字符串中是否所有字符都只出现过一次。
例如:
str: “abc”
返回true

str: “1231″
返回false

如果字符串的长度为N，分别根据两种要求实现这个功能：
第一种实现：时间复杂度O(N)
第二种实现：额外空间复杂度O(1)，并有尽可能低的时间复杂度

	public static boolean isUniqueLessTime(String str) {
		if (str == null) {
			return false;
		}
		char[] charArr = str.toCharArray();
		boolean[] map = new boolean[256];
		for (int i = 0; i != charArr.length; i++) {
			if (map[charArr[i]]) {
				return false;
			}
			map[charArr[i]] = true;
		}
		return true;
	}

	public static boolean isUniqueLessSpace(String str) {
		if (str == null) {
			return false;
		}
		char[] charArr = str.toCharArray();
		heapSort(charArr);
		for (int i = 1; i != charArr.length; i++) {
			if (charArr[i] == charArr[i - 1]) {
				return false;
			}
		}
		return true;
	}

	public static void heapSort(char[] arr) {
		for (int i = 0; i != arr.length; i++) {
			heapInsert(arr, i);
		}
		for (int i = arr.length - 1; i != 0; i--) {
			swap(arr, 0, i);
			heapify(arr, 0, i);
		}
	}

	public static void heapInsert(char[] arr, int index) {
		while (index != 0) {
			int parent = (index - 1) / 2;
			if (arr[parent] < arr[index]) {
				swap(arr, parent, index);
				index = parent;
			} else {
				break;
			}
		}
	}

	public static void heapify(char[] arr, int index, int heapSize) {
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int largest = index;
		while (left < heapSize) {
			if (arr[left] > arr[index]) {
				largest = left;
			}
			if (right < heapSize && arr[right] > arr[largest]) {
				largest = right;
			}
			if (largest != index) {
				swap(arr, largest, index);
			} else {
				break;
			}
			index = largest;
			left = index * 2 + 1;
			right = index * 2 + 2;
		}
	}

	public static void swap(char[] arr, int index1, int index2) {
		char tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}

public static boolean isUniqueLessTime(String str) {

if (str == null) {

return false;

}

char[] charArr = str.toCharArray();

boolean[] map = new boolean[256];

for (int i = 0; i != charArr.length; i++) {

if (map[charArr[i]]) {

return false;

}

map[charArr[i]] = true;

}

return true;

}

public static boolean isUniqueLessSpace(String str) {

if (str == null) {

return false;

}

char[] charArr = str.toCharArray();

heapSort(charArr);

for (int i = 1; i != charArr.length; i++) {

if (charArr[i] == charArr[i - 1]) {

return false;

}

return true;

}

public static void heapSort(char[] arr) {

for (int i = 0; i != arr.length; i++) {

heapInsert(arr, i);

}

for (int i = arr.length - 1; i != 0; i--) {

swap(arr, 0, i);

heapify(arr, 0, i);

}

public static void heapInsert(char[] arr, int index) {

while (index != 0) {

int parent = (index - 1) / 2;

if (arr[parent] < arr[index]) {

swap(arr, parent, index);

index = parent;

} else {

break;

}

public static void heapify(char[] arr, int index, int heapSize) {

int left = index * 2 + 1;

int right = index * 2 + 2;

int largest = index;

while (left < heapSize) {

if (arr[left] > arr[index]) {

largest = left;

}

if (right < heapSize && arr[right] > arr[largest]) {

largest = right;

}

if (largest != index) {

swap(arr, largest, index);

} else {

break;

}

index = largest;

left = index * 2 + 1;

right = index * 2 + 2;

}

public static void swap(char[] arr, int index1, int index2) {

char tmp = arr[index1];

arr[index1] = arr[index2];

arr[index2] = tmp;

}

题目二：

给一个很长很窄的纸条，把纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开，此时折痕是凹下去的，也就是突起的方向指向纸条的下方；
如果从纸条的下边向上方对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是：下折痕、下折痕、上折痕；
如果纸条每次都从下边向上方对折，在对折n次之后展开。此时所有折痕突起的方向是什么样的呢？
请写一个函数，输入一个整数代表纸条的对折次数记为fTimes，从上到下依次打印所有折痕的突起方向。
例如：
fTimes = 1
打印：down
fTimes = 2
打印：down down up

	public static void printAllFolds(int fTimes) {
		if (fTimes < 1) {
			return;
		}
		printProcess(1, fTimes, true);
		System.out.println();
	}

	public static void printProcess(int fIndex, int length, boolean isDown) {
		if (fIndex == length) {
			System.out.print(isDown ? "down " : "up ");
			return;
		}
		printProcess(fIndex + 1, length, true);
		System.out.print(isDown ? "down " : "up ");
		printProcess(fIndex + 1, length, false);
	}