题目：一个长度为N的数，组中的所有数字都是在0~N-1的范围内，数组中某些数字是重复的，但是不知道有几个数的重复，也不知道每个数字重复了几次，请找出数组中任意一个重复的数字作为返回值。
- 充分利用下标和数值之间的对应关系
- 和桶排序有异曲同工之妙
public class Main {
public static Integer repetition(int[] arr) {
for (int i = 0; i < arr.length; i++) {
while (arr[i] != i) {
// 若果没有这样的return 语句那么可能导致该循环不会退出
// 该条件的意思是已经存在arr[i]为下标值为arr[i]的值，此时出现俩个arr[i]
if (arr[arr[i]] == arr[i]) {
return arr[i];
}
// 交换此时下标为i和下标为arr[i]的值
int temp = arr[i];
arr[i] = arr[temp];
arr[temp] = temp;
}
}
return null;
}
}
思考：输出数组中缺失和重复的元素。
public class Main {
// 存储数组中重复出现的元素
public static HashSet repetitionHashSet = new HashSet<>();
// 存储数组中在0~N-1之间缺失的元素
public static ArrayList restNumList = new ArrayList<>();
public static void repetition(int[] arr) {
for (int i = 0; i < arr.length; i++) {
modify(arr, i);
}
// 此时所以元素都应该在对应位置，除非不存在对应值
// 不存在的位置都会存在一个和其他值重复的值
for (int i = 0; i < arr.length; i++) {
if (arr[i] != i) {
repetitionHashSet.add(arr[i]);
restNumList.add(i);
}
}
}
private static void modify(int[] arr, int index) {
// 首先要保证arr[index]和对应的值不为index
// 另外arr[index]为下标的元素不能已经在正确位置,防止进入死循环
// 每一次运行都仅仅改变元素位置，不能改变arr中元素值
while (arr[index] != index && !(arr[arr[index]] == arr[index])) {
// 将下标为index和下标为arr[index]的两个值进行交换
int temp = arr[index];
arr[index] = arr[temp];
arr[temp] = temp;
}
}
}
不修改数组寻找重复元素
问题 ：在长度为N+1的数组里面的所有数字都在1~N的范围内，所以数组中至少有一个数字是重复的，请找出数组中任意一个重复数字，但不能够修改输入的数组。要求空间复杂度O( 1 )
- 二分法将数据进行分类，判断重复数据在二分情况下的左右位置。
- 数据个数大于范围中整数个数就在该范围中定存在重复值
public class Main {
public static Integer repetition(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
int left = 1;
int right = arr.length - 1;
// 当left==right时，我们并不知道是否为重复数据，所以还要进行一次countRange方法调用进行判断。
while (left <= right) {
int med = ((right - left) >> 1) + left;
// 计算left..med之间数据个数
int count = countRange(arr, left, med);
if (left == right) {
if (count > 1) {
return left;
} else {
break;
}
}
// 若数据个数比left...med之间的整数个数多则定有重复值
// 根据数据个数定重复值范围，从而缩小重复数据所在范围
if (count > (med - left + 1)) {
right = med;
} else {
left = med + 1;
}
}
return -1;
}
private static int countRange(int[] arr, int left, int med) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (left <= arr[i] && arr[i] <= med) {
++count;
}
}
return count;
}
}
二维数组中的查找
题目 ： 在一个二维数组中每一行都按照从左到右递增的顺序排序，每一列都按照从上到下的递增的顺序排序，完成一个函数输入这样的一个二维数组和一个整数，判断数组中是否还有这样的整数。
- 在arr中邻近目标值的数值附近的范围进行数据搜索
public class Main {
public static boolean process(int[][] arr, int x) {
// 异常条件
if (arr == null || arr.length == 0 || arr[0].length == 0 || arr[0][0] > x
|| arr[arr.length - 1][arr[0].length - 1] < x) {
return false;
}
int row = 0;
int line = 0;
// 控制范围
while (row >= 0 && row < arr.length && line >= 0 && line < arr[0].length) {
// 目标值比arr[row][line]大就有向右和向下两个方向
if (arr[row][line] < x) {
// 向右满足吗？
if (line + 1 < arr[0].length && arr[row][line + 1] < x) {
++line;
} else {
++row;
}
// 目标值比arr[row][line]小
} else if (arr[row][line] > x) {
--line;
} else {// 等于目标值
return true;
}
}
// 因为范围出界返回不存在
return false;
}
}
字符串
替换空格
题目 ： 请实现一个函数，把字符串中的每个空格转换为 %20
- 若是从左向右依次进行时间复杂度O（N²），造成时间浪费的主要原因就是没能够将字符直接填到他应该在的位置。
- 要想能够直接将它放在相应的位置，就需要知道一共有多少个空格。
- 并且在便利扩充的过程中，必须要从右向左，以防数据的覆盖。
public class Main {
public static void main(String[] args) {
char[] arr = new char[100];
System.out.println(arr.length);
arr[0] = ' ';
arr[1] = 'a';
arr[2] = ' ';
arr[3] = 'a';
arr[4] = 'a';
arr[5] = 'a';
arr[6] = ' ';
arr[7] = 'a';
arr[8] = 'a';
arr[9] = ' ';
process(arr, 10, 100);
}
public static void process(char[] arr, int thisLen, int maxLen) {
if (arr == null || maxLen <= 0 || thisLen <= 0) {
return;
}
// 统计空格数量
int sumK = 0;
for (int i = 0; i < thisLen; i++) {
if (arr[i] == ' ') {
++sumK;
}
}
// 计算新数组长度
int newLen = sumK * 2 + thisLen;
if (newLen > maxLen) {
return;
}
// 两个指针进行遍历
int index = thisLen - 1;
int newIndex = newLen - 1;
while (index >= 0) {
if (arr[index] == ' ') {
arr[newIndex--] = '0';
arr[newIndex--] = '2';
arr[newIndex] = '%';
} else {
arr[newIndex] = arr[index];
}
--index;
--newIndex;
}
}
}
链表
从尾到头打印链表
题目 : 输入一个链表的头节点，从尾到头反过来打印出每个节点的值。
- 三种方式之实现
- 其中栈结构和递归实现时间复杂度常数较低 1 * O(N)，反序实现为 3 * O(N)
- 栈结构空间复杂度O(N)，递归和反序为O(1)
public class Main {
//栈实现
public static void process_1(Node header) {
if (header == null) {
return;
}
Stack stack = new Stack<>();
Node tail = header;
while (tail != null) {
stack.push(tail);
tail = tail.nextNode;
}
while (!stack.isEmpty()) {
System.out.println(stack.pop().num);
}
}
// 递归实现
public static void process_2(Node header) {
if (header == null) {
return;
}
process_2(header.nextNode);
System.out.println(header.num);
}
// 反序链表实现
public static void process_3(Node header) {
if (header == null) {
return;
}
Node pre = null;
Node tail = header;
Node post = null;
while (tail != null) {
post = tail.nextNode;
tail.nextNode = pre;
pre = tail;
tail = post;
}
header = pre;
while (pre != null) {
System.out.println(pre.num);
pre = pre.nextNode;
}
pre = null;
tail = header;
post = null;
while (tail != null) {
post = tail.nextNode;
tail.nextNode = pre;
pre = tail;
tail = post;
}
}
public static class Node {
int num;
Node nextNode;
public Node(int num, Node nextNode) {
this.num = num;
this.nextNode = nextNode;
}
}
}
树
重建二叉树讀
题目 ： 输入某二叉树的前序遍历和中序遍历的结果，请重建二叉树。假设输入的前驱和后继的节点都没有重复的数字，函数要返回树的根节点 。
