算法-练习题目
链表
逆序遍历链表
简单一个递归，先递归再取值
public static void reverseTraverse(Node node) {
if (node == null) {
return ;
}
reverseTraverse(node.next);
System.out.println(node.value);
}
删除倒数第N个节点
和逆序遍历链表一个思路。递归处理，就是反转了，i++就是从后边开始算。 调试下边界即可。
static int i = 0;
public static void reverseDel(Node node, int num) {
if (node == null) {
return;
}
reverseDel(node.next, num);
i++;
// 最后1个，i=2; 倒数第二个，i=3; 这里调试一下即可，边界处理
if (i == num + 1) {
// System.out.println(node.value);
node.next = node.next.next;
}
}
翻转链表
双指针解决问题
next、node.next、pre、node
public static void main(String[] args) {
Node node = new Node(1);
node.next = new Node(2);
node.next.next = new Node(3);
Node newHead = reverse(node);
while (newHead != null) {
System.out.println(newHead.value);
newHead = newHead.next;
}
}
public static Node reverse(Node node) {
Node pre = null;
Node next = null;
while (node != null) {
// 保存下一个节点
next = node.next;
// 下个节点反转成前边的，pre在下行代码里做保存
node.next = pre;
// pre保存成当前的，为上一行代码服务
pre = node;
// 继续往下走
node = next;
}
return pre;
}
链表排序
归并排序
思路：一个链表拆成两个，最后两两merge归并排序 递归
- 单链表拆成俩链表
- 合并两个有序链表
public class LinkedListSort {
public static void main(String[] args) {
Node node2 = new Node(23);
node2.next = new Node(9);
node2.next.next = new Node(95);
node2.next.next.next = new Node(3);
node2.next.next.next.next = new Node(118);
node2.next.next.next.next.next = new Node(98);
Node sort = sort(node2);
while (sort != null) {
System.out.println(sort.value);
sort = sort.next;
}
}
/**
* 思路：一个链表拆成两个，最后两两merge归并排序 递归
* 1. 单链表拆成俩链表
* 2. 合并两个有序链表
* @param node
* @return
*/
static Node sort(Node node) {
if (node == null || node.next == null) {
return node;
}
Node node1 = new Node();
Node node2 = new Node();
Node tmpNode1 = node1;
Node tmpNode2 = node2;
Node cur = node;
// 一个链表按奇偶数拆成两个
while (cur != null) {
// System.out.println(cur.value);
tmpNode1.next = cur;
tmpNode2.next = cur.next;
// 步长是2 这是把一个链表拆分成两个链表的关键思路
if (cur.next != null) {
cur = cur.next.next;
} else {
// cur.next是空，表示链表到头了 可以退出了
break;
}
tmpNode1 = tmpNode1.next;
tmpNode2 = tmpNode2.next;
// 这里可以调试下，因为上边tmpNode1.next = cur; cur是原链表元素，这里要强制null，否则最后的元素会继承原来的链表
tmpNode1.next = null;
}
// 归并思路
return merge(sort(node1.next), sort(node2.next));
}
/**
* 合并两个有序链表
* @param a
* @param b
* @return
*/
static Node merge(Node a, Node b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
Node ret = new Node();
Node c = ret;
while (a != null && b != null) {
if (a.value < b.value) {
c.next = new Node(a.value);
a = a.next;
} else {
c.next = new Node(b.value);
b = b.next;
}
c = c.next;
}
while (a != null) {
c.next = new Node(a.value);
a = a.next;
c = c.next;
}
while (b != null) {
c.next = new Node(b.value);
b = b.next;
c = c.next;
}
return ret.next;
}
}
快排
思路：
- 分三个链表，小于中枢点值组成一个链表，等于的一个链表，大于的一个链表
- 这三个链表组合连接起来
static ListNode quickSort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 定义三个链表头尾节点
ListNode left = new ListNode(-1);
ListNode leftTail = left;
ListNode mid = new ListNode(-1);
ListNode midTail = mid;
ListNode right = new ListNode(-1);
ListNode rightTail = right;
int pivot = head.value;
while (head != null) {
// 比 pivot 小的 给到left链表
if (head.value < pivot) {
leftTail.next = head;
leftTail = leftTail.next;
} else if (head.value == pivot) {
midTail.next = head;
midTail = midTail.next;
} else {
rightTail.next = head;
rightTail = rightTail.next;
}
head = head.next;
}
// 每个链表隔断
leftTail.next = midTail.next = rightTail.next = null;
// 递归左链表
left.next = quickSort(left.next);
// 递归右链表
right.next = quickSort(right.next);
// 左 中 右 三个链表 连接起来
getTail(left).next = mid.next;
getTail(left).next = right.next;
// 返回最左边的链表头结点
return left.next;
}
static ListNode getTail(ListNode head) {
// 判断head.next 需要返回尾节点
while (head != null && head.next != null) {
head = head.next;
}
return head;
}
二叉树
后序遍历框架：
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}
层序遍历
public class LevelTraverse {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(8);
root.right.right = new TreeNode(18);
root.left.right = new TreeNode(5);
root.left.left = new TreeNode(4);
root.left.left.right = new TreeNode(9);
traverse(root);
}
static void traverse(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
System.out.println(treeNode.value);
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
}
}
}
最大深度
- 层序遍历计算深度
- 递归方式(后序遍历框架 涉及左右子树遍历后决策)
static int traverse(TreeNode root) {
int deep = 0;
if (root == null) {
return deep;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
// 把当前队列的元素个数排除完，意味着这一层结束
for (int i = size; i > 0; i--) {
TreeNode treeNode = queue.poll();
// System.out.println(treeNode.value);
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
}
deep++;
}
return deep;
}
/**
* 递归运算 每一层的深度=子节点最大深度+1
* @param root
* @return
*/
static int deep(TreeNode root) {
if (root == null) {
return 0;
}
// 递归运算 每一层的深度=子节点最大深度+1
return Math.max(deep(root.left), deep(root.right)) + 1;
}
最近公共祖先
妥妥后序遍历框架，因为涉及到左右子树都要遍历完做决策。
一旦发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
static Node lowestCommonAncestor(Node root, Node p, Node q) {
if (root == null || root == p || root == q) {
return root;
}
Node left = lowestCommonAncestor(root.left, p, q);
Node right = lowestCommonAncestor(root.right, p, q);
if (left == null) {
return right;
}
if (right == null) {
return left;
}
return root;
}
翻转二叉树
又一个典型的后序遍历框架，左右子树处理完，做一个交换策略。
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
相同结构的子树
// TreeNode为根的树序列化
static Map<String, TreeNode> map = new HashMap<>();
// 重复的树根
static Set<TreeNode> set = new HashSet<>();
static String traverse(TreeNode root) {
if (root == null) {
return "";
}
String left = traverse(root.left);
String right = traverse(root.right);
// 序列化
String strs = root.value + "(" + left + ")(" + right + ")";
if (map.containsKey(strs)) {
set.add(root);
} else {
map.put(strs, root);
}
return strs;
}
滑动窗口
框架套路：
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
最长不重复子串
思路：左右窗口界限往后推进，下一个元素已经在窗口，则把left移动到出现过的元素
static int window(char[] chars) {
LinkedList<String> window = new LinkedList<>();
if (chars == null || chars.length == 0) {
return 0;
}
int left = 0, right = 0;
int max = 0;
while (right < chars.length) {
max = Math.max(max, window.size());
String s = String.valueOf(chars[right]);
// 下一个元素已经在窗口，则把left移动到出现过的元素
if (window.size() > 0 && window.contains(s)) {
int i = window.indexOf(s);
System.out.println(i);
for (int j = 0; j <= i; j++) {
left++;
window.removeFirst();
}
}
window.addLast(s);
right++;
}
return max;
}
最小覆盖子串
static String window(String str, String need) {
if (str == null || need == null) {
return "";
}
Map<Character, Integer> needMap = new HashMap<>();
Map<Character, Integer> windowMap = new HashMap<>();
for (int i = 0; i < need.length(); i++) {
needMap.put(need.charAt(i), needMap.getOrDefault(need.charAt(i), 0) + 1);
}
// System.out.println(needMap);
int left = 0, right = 0, start = 0;
int valid = 0;
int len = Integer.MAX_VALUE;
while (right < str.length()) {
char c = str.charAt(right);
right++;
if (needMap.containsKey(c)) {
windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
if (windowMap.get(c).equals(needMap.get(c))) {
valid++;
}
}
// System.out.println(windowMap);
while (valid == needMap.size()) {
if (right - left < len) {
len = right - left;
start = left;
}
char c1 = str.charAt(left);
left++;
if (needMap.containsKey(c1)) {
if (needMap.get(c1).equals(windowMap.get(c1))) {
valid--;
}
windowMap.put(c1, windowMap.get(c1) - 1);
}
}
}
return len == Integer.MAX_VALUE ?
"" : str.substring(start, len + start);
}
排序
堆排序
public class Heap {
public static void main(String[] args) {
// 第一个元素充当一个占用值，方便*2
List<Integer> list = Arrays.asList(-1, 2, 1, 9, 4);
System.out.println(list);
// 调整成最大堆，从中间非叶子节点开始 2倍关系
for (int i = list.size() / 2; i > 0; i--) {
heapAdjust(i, list.size() - 1, list);
}
// 第一个和最后一个交换，最后的逐渐有序
for (int j = list.size() - 1; j > 0; j--) {
swap(list, 1, j);
// 注意这里最大索引是j-1，因为已经被替换完了
heapAdjust(1, j - 1, list);
}
System.out.println(list);
}
/**
* 堆调整
* @param begin
* @param end
* @param arr
*/
static void heapAdjust(int begin, int end, List<Integer> arr) {
// 从左叶子开始
for (int k = begin * 2; k <= end; k = k * 2) {
if (k + 1 <= end && arr.get(k + 1) > arr.get(k)) {
k++;
}
if (arr.get(begin) > arr.get(k)) {
break;
}
swap(arr, k, begin);
// 再从begin的孩子继续，因为调整的时候可能下移，得需要再继续以孩子做调整
begin = k;
}
}
static void swap(List<Integer> list, int a, int b) {
Integer integer = list.get(a);
list.set(a, list.get(b));
list.set(b, integer);
}
}
归并排序
二叉树后序遍历框架应用
static List<Integer> mergeSort(List<Integer> list) {
if (list.size() == 1) {
return list;
}
// 二叉树后序遍历框架
List<Integer> left = mergeSort(list.subList(0, list.size() / 2));
List<Integer> right = mergeSort(list.subList(list.size() / 2, list.size()));
return mergeTwoList(left, right);
}
static List<Integer> mergeTwoList(List<Integer> list1, List<Integer> list2) {
List<Integer> list = new ArrayList<>();
int i = 0, j = 0;
while (i < list1.size() && j < list2.size()) {
if (list1.get(i) < list2.get(j)) {
list.add(list1.get(i));
i++;
} else {
list.add(list2.get(j));
j++;
}
}
if (i < list1.size()) {
list.addAll(list1.subList(i, list1.size()));
}
if (j < list2.size()) {
list.addAll(list2.subList(j, list2.size()));
}
return list;
}
快排
二叉树前序遍历框架应用
static void quickSort(List<Integer> list, int low, int high) {
if (low < high) {
// 前序遍历框架
int k = partition(list, low, high);
quickSort(list, 0, k - 1);
quickSort(list, k + 1, high);
}
}
static int partition(List<Integer> list, int low, int high) {
Integer pivot = list.get(low);
while (low < high) {
while (low < high && list.get(high) > pivot) {
high--;
}
swap(list, low, high);
while (low < high && list.get(low) < pivot) {
low++;
}
swap(list, low, high);
}
return low;
}
static void swap(List<Integer> list, int a, int b) {
Integer integer = list.get(a);
list.set(a, list.get(b));
list.set(b, integer);
}
二分法
static int bsearch(int[] arr, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (obj > arr[mid]) {
return bsearch(arr, mid + 1, high);
}
if (obj < arr[mid]) {
return bsearch(arr, 0, mid - 1);
}
return mid;
}