源于 Leetcode 344 题
举一反三 Leetcode 151 题（反转单词）
思路 - 双指针
一开始，i 指针指向数组起始元素，j 指针指向数组结束元素，交换 i、j 指向的元素。
i 向后移动，j 向前移动，重复以上过程 ，直至 i、j 相遇，算法结束。
参考代码
Plain Text
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static void sort(int[] a) {
heapify(a, a.length);
for (int right = a.length - 1; right > 0; right--) {
swap(a, 0, right);
down(a, 0, right);
}
}
// 建堆 O(n)
private static void heapify(int[] array, int size) {
for (int i = size / 2 - 1; i >= 0; i--) {
down(array, i, size);
}
}
// 下潜 O(log n)
private static void down(int[] array, int parent, int size) {
// 比较 parent 和它的左、右孩子
while (true) {
int left = parent * 2 + 1;
int right = left + 1;
// max 代表 parent 和它的左、右孩子中最大值
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
// 最大的就是 parent 自己
if (max == parent) {
break;
}
// parent 与孩子中较大者交换
swap(array, max, parent);
// 继续下潜
parent = max;
}
}
Plain Text
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void reverseString(char[] s) {
reverseString(s, 0, s.length - 1);
}
static void reverseString(char[] s, int begin, int end) {
int i = begin;
int j = end;
while (i < j) {
swap(s, i, j);
i++;
j--;
}
}
static void swap(char[] array, int i, int j) {
char c = array[i];
array[i] = array[j];
array[j] = c;
}
