数据结构和算法
反转单向链表
public class Node {
public int value;
public Node next;
}
public Node reverseList(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = head.next
}
return pre;
}
在顺序表中插入和删除一个结点平均移动多少个结点？
在等概率的情况下，顺序表插入一个结点需要平均移动n/2个结点。删除一个结点需要平均移动(n-1)/2个结点。具体的移动次数取决于长度n和位置i，两者越近，移动的越少。
如何以递归和非递归方式实现二分查找
非递归：
private int binarySearch(int[] arr, int searchKey) {
if (arr == null) {
return -1;
}
int n = arr.length;
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + ((right -left) >> 1);
if (arr[mid] > searchKey) {
right = mid - 1;
} else if (arr[mid] < searchKey) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
递归：
private int binarySearchRecursive(int[] arr, int left, int right) {
if (arr == null) {
return -1;
}
int n = arr.length;
int left = 0;
int right = n -1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (arr[mid] > searchKey) {
binarySearchRecursive(arr, left, mid - 1);
} else if (arr[mid] < searchKey) {
binarySearchRecursive(arr, mid + 1, right);
} else {
return mid;
}
}
return -1;
}
需要注意的是，二分查找算法的时间复杂度为O(logn)，最坏情况下的时间复杂度为O(logn)
求二叉树的深度
private int getDepth(Node node) {
if (node == null) {
return 0;
}
int left = getDepth(node.left);
int right = getDepth(node.right);
return left > right ? (left + 1) : (right + 1);
}
如何在排序的数组中，找出给定数字出现的次数
其实我的想法是通过hashmap来实现，其实也没必要在乎数组是否是排序的。时间复杂度方面，遍历整个数组，将数组元素添加到hash中，最后再查询，时间复杂度应该是O(n).
function getTimes(arr, key) {
var n = arr.length;
var hash = {};
for (var i = 0; i < n; i ++) {
var ele = arr[i];
if (!hash[ele]) {
hash[ele] = 1;
} else {
hash[ele] ++;
}
}
if (hash[key]) {
return hash[key];
} else {
return -1;
}
}
.
private static void stasTimes(int[] arr, int key) {
int len = arr.length;
HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
for (int i =0; i < len; i++) {
if (hash.containsKey(arr[i])) {
Integer val = hash.get(arr[i]) + 1;
hash.put(arr[i], val);
} else {
hash.put(arr[i], 1);
}
}
for (Integer hashKey: hash.keySet()) {
if (hashKey.intValue() == key) {
System.out.println(key + " has appeared " + hash.get(hashKey) + " times");
}
}
}
如何把字符串中的指定字符移动到字符串的前面
private char[] moveChar(String str, char a) {
char[] arr = str.toCharArray();
int i = arr.length - 1;
while (arr[i] != a) {
i --;
}
for (int j = i - 1; j >= 0; j --) {
if (arr[j] != a) {
arr[i] = arr[j];
arr[j] = a;
i --;
}
}
return arr;
}
排序算法总结
冒泡排序
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]]) {
swap(arr, j+1, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
数组和链表的区别
- 数组必须事先定义固定的长度，链表采用动态分配内存的形式实现。
- 数组从栈中分配空间，自由度小；链表从对中分配内存，自由度大，但管理麻烦。
- 数组中的数据在内存中时顺序存储的，链表是随机存储的。
- 数组便于查询；链表便于插入删除。
什么排序元素比较次数和数组初始状态无关
选择排序
排序算法比较
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) | O(nlog^2n) | O(nlog^2n) | O(1) | 不稳定 |
| 归并排序 | O(nlog(n)) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | O(n^2) | O(n+k) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
