# 牛课堂算法直播题目

## 二、code技巧的磨炼

【题目】荷兰国旗问题

```package tmp;

public class Code_01_NetherlandsFlag {

public static int[] partition(int[] arr, int l, int r, int p) {
int less = l - 1;
int more = r + 1;
int i = l;
while (l < more) {
if (arr[l] < p) {
swap(arr, ++less, l++);
} else if (arr[l] > p) {
swap(arr, --more, l);
} else {
l++;
}
}
return new int[] { less + 1, more - 1 };
}

// for test
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

// for test
public static int[] generateArray() {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 3);
}
return arr;
}

// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

public static void main(String[] args) {
int[] test = generateArray();

printArray(test);
int[] res = partition(test, 0, test.length - 1, 1);
printArray(test);
System.out.println(res[0]);
System.out.println(res[1]);

}
}```

## 三、算法思维的锻炼

【题目】已知一个整型数组arr，数组长度为size且size大于2，arr有size-1种可以划分成左右两部分的方案。

```package tmp;

public class Code_02_MaxABSBetweenLeftAndRight {

public static int maxABS1(int[] arr) {
int res = Integer.MIN_VALUE;
int maxLeft = 0;
int maxRight = 0;
for (int i = 0; i != arr.length - 1; i++) {
maxLeft = Integer.MIN_VALUE;
for (int j = 0; j != i + 1; j++) {
maxLeft = Math.max(arr[j], maxLeft);
}
maxRight = Integer.MIN_VALUE;
for (int j = i + 1; j != arr.length; j++) {
maxRight = Math.max(arr[j], maxRight);
}
res = Math.max(Math.abs(maxLeft - maxRight), res);
}
return res;
}

public static int maxABS2(int[] arr) {
int[] lArr = new int[arr.length];
int[] rArr = new int[arr.length];
lArr[0] = arr[0];
rArr[arr.length - 1] = arr[arr.length - 1];
for (int i = 1; i < arr.length; i++) {
lArr[i] = Math.max(lArr[i - 1], arr[i]);
}
for (int i = arr.length - 2; i > -1; i--) {
rArr[i] = Math.max(rArr[i + 1], arr[i]);
}
int max = 0;
for (int i = 0; i < arr.length - 1; i++) {
max = Math.max(max, Math.abs(lArr[i] - rArr[i + 1]));
}
return max;
}

public static int maxABS3(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
return max - Math.min(arr[0], arr[arr.length - 1]);
}

public static int[] generateRandomArray(int length) {
int[] arr = new int[length];
for (int i = 0; i != arr.length; i++) {
arr[i] = (int) (Math.random() * 1000) - 499;
}
return arr;
}

public static void main(String[] args) {
int[] arr = generateRandomArray(200);
System.out.println(maxABS1(arr));
System.out.println(maxABS2(arr));
System.out.println(maxABS3(arr));
}
}```

## 四、算法基础内容的学习与拓展

【题目】定义局部最小的概念。

arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i]<arr[i-1]，又有arr[i]<arr[i+1]，那么arr[i]是局部最小。

```package tmp;

public class Code_03_FindOneLessValueIndex {

public static int getLessIndex(int[] arr) {
if (arr == null || arr.length == 0) {
return -1; // no exist
}
if (arr.length == 1 || arr[0] < arr[1]) {
return 0;
}
if (arr[arr.length - 1] < arr[arr.length - 2]) {
return arr.length - 1;
}
int left = 1;
int right = arr.length - 2;
int mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] > arr[mid - 1]) {
right = mid - 1;
} else if (arr[mid] > arr[mid + 1]) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}

public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

public static void main(String[] args) {
int[] arr = { 6, 5, 3, 4, 6, 7, 8 };
printArray(arr);
int index = getLessIndex(arr);
System.out.println("index: " + index + ", value: " + arr[index]);

}

}```

## 五、算法敏感度的训练

【题目】折纸条。 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向。 例如：

N=1时，打印： down N=2时，打印： down down up

```package tmp;

public class Code_04_PaperFolding {

public static void printAllFolds(int N) {
printProcess(1, N, true);
}

public static void printProcess(int i, int N, boolean down) {
if (i > N) {
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? "down " : "up ");
printProcess(i + 1, N, false);
}

public static void main(String[] args) {
int N = 4;
printAllFolds(N);
}
}```

提示：将此题步骤推算下来，其实就是二叉树的中序遍历问题。

## 六、收获

• 学习算法还是要多刷题，至少要刷200道以上。
• 在练习完一道算法题时，应尽量找寻它的最优解。
• 有些大公司在面试你时会故意不把问题说清楚，这是因为他在考察你对算法的敏感度（如上述的折纸问题本质就是一个二叉树的中序遍历问题）。看你能否直接看到问题的本质。
• 代码书写命名要规范，在保证自己理解的前提下让阅读代码的人也能够读懂。
• 坚持。

230 篇文章45 人订阅

0 条评论

## 相关文章

### 20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数，然后将信息（只包含字...

3818

3956

4589

### POJ 刷题系列：1083. Moving Tables

POJ 刷题系列：1083. Moving Tables 传送门：POJ 1083. Moving Tables 题意： 一条走廊，两栏房间。搬运工每次从房价...

22010

2165

1733

4497

3675

4826

45212