我不是魔法师

新手入门篇-数据结构、前缀和、对数器

数据结构算法基本上是数组和链表的变种，数组和链表是所有算法的基石。数组：内存分配是连续的、访问速度快，插入和删除速度慢，因为数组要移动位置。链表：内存分配是不连续的，插入和删除速度快，访问速度慢，因为需要遍历。前缀和对于一个数组，求从L到R位置的和一般大家都会这么做，从L遍历到R，累加求和。对于数量规模比较大的时候，这种普通求解方法就显得效率有些低下了，可以通过前缀和。public class Code01_PreSum { public static void main(String[] args) { int[] arr = {1, 2, 4, 5, 7}; RangeSum1 rangeSum1 = new RangeSum1(arr); System.out.println(rangeSum1.rangeSum(2, 4)); RangeSum2 rangeSum2 = new RangeSum2(arr); System.out.println(rangeSum2.rangeSum(2, 4)); RangeSum3 rangeSum3 = new RangeSum3(arr); System.out.println(rangeSum3.rangeSum(2, 4)); } public static class RangeSum1 { private int[] arr; public RangeSum1(int[] array) { this.arr = array; } // 普通求解 public int rangeSum(int L, int R) { int sum = 0; for (int i = L; i <= R; i++) { sum += arr[i]; } return sum; } } // 一维数组求解 public static class RangeSum2 { private int[] preSum; public RangeSum2(int[] arr) { preSum = new int[arr.length]; preSum[0] = arr[0]; for (int i = 1; i < arr.length; i++) { preSum[i] = preSum[i - 1] + arr[i]; } } public int rangeSum(int L, int R) { return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1]; } } // 二维数组求解 public static class RangeSum3 { private int[][] arr; public RangeSum3(int[] array) { arr = new int[array.length][array.length]; arr[0][0] = array[0]; for (int i = 1; i < array.length; i++) { for (int j = 1; j < arr.length; j++) { if (i > j) { continue; } arr[i][j] = (i == j) ? array[i] : arr[i][j - 1] + array[j]; } } } public int rangeSum(int L, int R) { return arr[L][R]; } } } 对数器验证自己写的算法对不对，可以通过对数器进行验证，验证规则可以自定义。随机等概率public class Code02_RandToRand { public static void main(String[] args) { int testTimes = 10000000; int count = 0; double x = 0.1; for (int i = 0; i < testTimes; i++) { if (Math.random() < x) { count++; } } System.out.println("x=" + x + "的概率为：" + (double) count / (double) testTimes); System.out.println("=================================="); count = 0; for (int i = 0; i < testTimes; i++) { if (Math.random() * 8 < 5) { count++; } } System.out.println("小于5的概率为：" + (double) count / (double) testTimes); System.out.println((double) 5 / (double) 8); System.out.println("=================================="); int K = 9; // [0,k) -> [0,8] int[] counts = new int[9]; for (int i = 0; i < testTimes; i++) { int ans = (int) (Math.random() * K);// [0,k-1] counts[ans]++; } for (int i = 0; i < K; i++) { System.out.println(i + "这个数，出现了 " + counts[i] + " 次"); } System.out.println("=================================="); count = 0; x = 0.8; for (int i = 0; i < testTimes; i++) { if (xToXPower2() < x) { count++; } } System.out.println((double) count / (double) testTimes); System.out.println(Math.pow(x, 2)); System.out.println("=================================="); count = 0; x = 0.8; for (int i = 0; i < testTimes; i++) { if (xToXPower22() < x) { count++; } } System.out.println((double) count / (double) testTimes); System.out.println((double) 1 - Math.pow((double) 1 - x, 2)); System.out.println("=================================="); count = 0; for (int i = 0; i < testTimes; i++) { if (f2() == 1) { count++; } } System.out.println((double) count / (double) testTimes); System.out.println("=================================="); counts = new int[8]; for (int i = 0; i < testTimes; i++) { int num = g(); counts[num]++; } for (int i = 0; i < 8; i++) { System.out.println(i + "这个数，出现了 " + counts[i] + " 次"); } } // 返回一个[0,1)的小数 // 任意的x，x属于[0,1)，【0,x)范围上的数出现概率由原来的x调整成x平方 public static double xToXPower2() { return Math.max(Math.random(), Math.random()); } public static double xToXPower22() { return Math.min(Math.random(), Math.random()); } // lib里的，不能改 public static int f1() { return (int) (Math.random() * 5) + 1; } // 随机机制，只能用f1， // 等概率返回0和1 public static int f2() { int ans = 0; do { ans = f1(); } while (ans == 3); return ans < 3 ? 0 : 1; } // 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个 public static int f3() { return (f2() << 2) + (f2() << 1) + f2(); } // 0 ~ 6等概率返回一个 public static int f4() { int ans = 0; do { ans = f3(); } while (ans == 7); return ans; } public static int g() { return f4() + 1; } // 你只能知道，x会以固定概率返回0和1，但是x的内容，你看不到！ public static int x() { return Math.random() < 0.84 ? 0 : 1; } // 等概率返回0和1 public static int y() { int ans = 0; do { ans = x(); } while (ans == x()); return ans; } } 校验算法是否正确public class Code03_Comp { public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr, i, minIndex); } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序 for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } } // 返回一个数组arr，arr长度[0,maxLen-1],arr中的每个值[0,maxValue-1] public static int[] lenRandomValueRandom(int maxLen, int maxValue) { int len = (int) (Math.random() * maxLen); int[] arr = new int[len]; for (int i = 0; i < len; i++) { int ans = (int) (Math.random() * maxValue); arr[i] = ans; } return arr; } public static int[] copyArray(int[] arr) { int[] ans = new int[arr.length]; for (int i = 0; i < arr.length; i++) { ans[i] = arr[i]; } return ans; } // arr1和arr2一定等长 public static boolean isSorted(int[] arr) { if (arr.length < 2) { return true; } int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (max > arr[i]) { return false; } max = Math.max(max, arr[i]); } return true; } public static void main(String[] args) { int maxLen = 5; int maxValue = 1000; int testTimes = 10000; for (int i = 0; i < testTimes; i++) { int[] arr1 = lenRandomValueRandom(maxLen, maxValue); int[] tmp = copyArray(arr1); selectionSort(arr1); if (!isSorted(arr1)) { for (int j = 0; j < tmp.length; j++) { System.out.print(tmp[j] + " "); } System.out.println(); System.out.println("选择排序错了！"); break; } } } }

我不是魔法师

新手入门篇-二叉树的面试案例

二叉树按层遍历并收集节点思路：拿出此时队列的size，size有多少，弹出多少弹出节点，先左后右放进去注意：LinkedList比ArrayList效率高，LinkedList底层通过链表实现，且是双端队列每轮队列的size，必须用临时变量接受，也就是需要弹出固定的sizepublic class Code01_BinaryTreeLevelOrderTraversalII { public static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public List<List<Integer>> levelOrderBottom(TreeNode root) { LinkedList<List<Integer>> ans = new LinkedList<>(); if (root == null) { return ans; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> curAns = new LinkedList<>(); for (int i = 0; i < size; i++) { TreeNode curNode = queue.poll(); curAns.add(curNode.val); if (curNode.left != null) { queue.add(curNode.left); } if (curNode.right != null) { queue.add(curNode.right); } } ans.addFirst(curAns); } return ans; } } 判断一颗树是否是平衡二叉树平衡二叉树的定义任意子树中，|left的高度 - right的高度| <= 1思路假设任意节点的左子树平衡，右子树平衡，并且左子树的高度-右子树的绝对值小于等于1，则认为当前节点下都平衡。public class Code02_BalanceBinaryTree { public static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public boolean isBalanced(TreeNode root) { return process(root).isBalanced; } public static class Info { public boolean isBalanced; public int height; public Info(boolean isBalanced, int height) { this.isBalanced = isBalanced; this.height = height; } } public static Info process(TreeNode root) { if (root == null) { return new Info(true, 0); } Info leftInfo = process(root.left); Info rightInfo = process(root.right); int height = Math.max(leftInfo.height, rightInfo.height) + 1; boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced && Math.abs(leftInfo.height - rightInfo.height) < 2; return new Info(isBalanced, height); } } 递归轨迹如下图判断一棵树是否是搜索二叉树搜索二叉树的定义Binary Search Tree，任意节点的left都比当前节点小，right都比当前节点大思路判断当前节点是否满足BST当前节点的左子树中最大值都比当前节点的值小当前节点的右子树中最小值都比当前节点的值大public class Code03_IsBinarySearchTree { public static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public static class Info { public boolean isBST; public int max; public int min; public Info(boolean isBST, int max, int min) { this.isBST = isBST; this.max = max; this.min = min; } } public static Info process(TreeNode x) { if (x == null) { return null; } Info leftInfo = process(x.left); Info rightInfo = process(x.right); int max = x.val; int min = x.val; if (leftInfo != null) { max = Math.max(leftInfo.max, max); min = Math.min(leftInfo.min, min); } if (rightInfo != null) { max = Math.max(rightInfo.max, max); min = Math.min(rightInfo.min, min); } boolean isBST = true; if (leftInfo != null && !leftInfo.isBST) { isBST = false; } if (rightInfo != null && !rightInfo.isBST) { isBST = false; } boolean leftMaxLessX = leftInfo == null ? true : leftInfo.max < x.val; boolean rightMixMoreX = rightInfo == null ? true : rightInfo.min > x.val; if (!(leftMaxLessX && rightMixMoreX)) { isBST = false; } return new Info(isBST, max, min); } } 判断一颗树是否是平衡搜索二叉树平衡搜索二叉树的定义满足平衡二叉树且满足搜索二叉树代码就不写了，判断平衡二叉树code && 判断搜索二叉树总结本篇介绍了二叉树面试高频的案例，算法练习其实对coding的能力是有帮助的。多多练习，必有回报！

我不是魔法师

新手入门篇-优先级队列、二叉树 2021-06-22 111 阅读3分钟 专栏： 数据结构与算法

优先级队列PriorityQueue的使用，默认小顶堆。基本的应用场景public class Code01_ShowComparator { public static class Student { public String name; public int id; public int age; public Student(String name, int id, int age) { this.name = name; this.id = id; this.age = age; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", id=" + id + ", age=" + age + '}'; } } public static class IdComparator implements Comparator<Student> { @Override public int compare(Student s1, Student s2) { return Integer.compare(s1.id, s2.id); } } public static void main(String[] args) { Student s1 = new Student("张三", 5, 27); Student s2 = new Student("李四", 1, 17); Student s3 = new Student("王五", 4, 29); Student s4 = new Student("赵六", 3, 9); Student s5 = new Student("左七", 2, 34); PriorityQueue<Student> heap = new PriorityQueue<>(new IdComparator()); heap.add(s1); heap.add(s2); heap.add(s3); heap.add(s4); heap.add(s5); while (!heap.isEmpty()) { System.out.println(heap.poll()); } } } 合并多个有序链表举例：1->2->4->63->5->72->8->9合并后链表为：1->2->2->3->4->5->6->7->8->9思路：首先把所有有序链表按照自定义比较器规则加入优先级队列中，则所有链表的头节点默认就排好序了，形成小顶堆。然后取出头节点，把头的下一个节点再次入队，周而复始。public class Code02_MergeKSortedLists { public static class ListNode { public int val; public ListNode next; } public static class ListNodeComparator implements Comparator<ListNode> { @Override public int compare(ListNode o1, ListNode o2) { return o1.val - o2.val; } } public static ListNode mergeKLists(ListNode[] lists) { if (lists == null) { return null; } PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator()); // 把所有链表都加入优先级队列中，按照比较器规则，添加完后自动形成小顶堆 for (int i = 0; i < lists.length; i++) { heap.add(lists[i]); } if (heap.isEmpty()) { return null; } ListNode head = heap.poll(); ListNode pre = head; if (pre.next != null) { heap.add(pre.next); } while (!heap.isEmpty()) { ListNode cur = heap.poll(); pre.next = cur; pre = cur; if (cur.next != null) { heap.add(cur.next); } } return head; } } 二叉树二叉树的遍历递归遍历思路：前序：头、左、右中序：左、头、右后序：左、右、头public class Code03_TraversalBinaryTree { public static class Node { public int value; public Node left; public Node right; public Node(int v) { this.value = v; } } // 前序遍历：头、左、右 public static void pre(Node head) { if (head == null) { return; } System.out.println(head.value); pre(head.left); pre(head.right); } // 中序遍历：左、头、右 public static void mid(Node head) { if (head == null) { return; } mid(head.left); System.out.println(head.value); mid(head.right); } // 后序遍历：左、右、头 public static void pos(Node head) { if (head == null) { return; } pos(head.left); pos(head.right); System.out.println(head.value); } public static void main(String[] args) { Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); head.right.right = new Node(7); pre(head); System.out.println("========"); mid(head); System.out.println("========"); pos(head); System.out.println("========"); } } 按层遍历判断两棵树是否结构相同思路：第一颗树的当前节点的left等于第二个树的当前节点的left第一颗树的当前节点的right等于第二颗树的当前节点的right边界判断public class Code04_SameTree { public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } public static boolean isSameTree(TreeNode p, TreeNode q) { // ^异或：相同为false，不同为true if (p == null ^ q == null) { return false; } if (p == null && q == null) { return true; } // p和q都不为空 return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } } 判断一棵树是否是镜面树思路：当前节点的left等于当前节点的right当前节点的right等于当前节点的left边界判断public class Code05_SymmetricTree { public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } public static boolean isSymmetric(TreeNode root) { return isMirror(root, root); } public static boolean isMirror(TreeNode h1, TreeNode h2) { // ^异或：相同为false，不同为true if (h1 == null ^ h2 == null) { return false; } if (h1 == null && h2 == null) { return true; } return h1.val == h2.val && isMirror(h1.left, h2.right) && isMirror(h1.right, h2.left); } } 总结本节首先介绍了下Java中优先级队列的基本使用，接着用优先级队列解决合并k个有序链表，要求合并后新的链表依然后续的场景。其次简单介绍了下二叉树的递归遍历、判断两课树是否结构相同、判断一棵树是否为镜面树案例code。

我不是魔法师

新手入门篇-位运算、选择排序、冒泡排序、插入排序

打印一个int类型数对应的32位二进制码int类型占用4个字节，共占32位。int数值范围：-2^31 ~ 2^31 - 1Integer.MIN_VALUE = -2147483648 对应的二进制为：10000000000000000000000000000000 Integer.MAX_VALUE = 2147483647 对应的二进制为：01111111111111111111111111111111 最高位来标识正负数，1代表负数，0代表整数举例说明：5对应的二进制位 00000000000000000000000000000101101 = 1 * 2^2 + 1 * 2^0 = 4 + 1 = 5正整数对应的负整数怎么算？正数取反 + 1比如正数5，对应的负数为-5。00000000000000000000000000000101 5对应的二进制 11111111111111111111111111111010 取反 11111111111111111111111111111011 加一 -5 对应的二进制码为：11111111111111111111111111111011代码如下： private static void print(int num) { for (int i = 31; i >= 0; i--) { System.out.print((num & (1 << i)) == 0 ? "0" : "1"); } System.out.println(); } 选择排序思路：选择排序就是选择最小数，依次放到指定的位置上。0 ~ N-1 从第0位到N-1位，选择一个最小数，放到第0位置上。1 ~ N-1 从第1位到N-1位，选择一个最小数，放到第1位置上。2 ~ N-1 从第2位到N-1位，选择一个最小数，放到第2位置上。public class Code03_SelectSort { /** * 0 ~ N-1 从第0位到N-1位选择一个最小数，放到第0位上 * 1 ~ N-1 从第1位到N-1位选择一个最小数，放到第1位上 * 2 ~ N-1 从第2位到N-1位选择一个最小数，放到第2位上 */ public static void selectSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int N = arr.length; // 外层循环控制循环次数 for (int i = 0; i < N; i++) { // 假设每次循环第一个数为最小 int mixValueIndex = i; // 找最小数 for (int j = i + 1; j < N; j++) { mixValueIndex = arr[j] < arr[mixValueIndex] ? j : mixValueIndex; } // 交换位置 swap(arr, i, mixValueIndex); } } public static void swap(int[] arr, int i, int j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } public static void print(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 = {10, 5, 8, 2, 1, 4, 9, 3, 2, 0}; print(arr); selectSort(arr); print(arr); } } 冒泡排序思路：每次比较相邻的两个数的大小，两两交换，第一趟下来，最大数在数组的最右边，依次类推。0 ~ N-10 ~ N-20 ~ N-30 ~ endpublic class Code04_BubbleSort { /** * 相邻两位，两两互换 * 0 ~ n-1 * 0 ~ n-2 * 0 ~ n-3 * 0 ~ end */ public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int N = arr.length; // 外层循环控制循环多少次 for (int end = N - 1; end >= 0; end--) { // 内存循环控制两两交换 // 0 1 1 2 2 3 ... for (int second = 1; second <= end; second++) { if (arr[second - 1] > arr[second]) { swap(arr, second - 1, second); } } } } public static void swap(int[] arr, int i, int j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } public static void print(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 = {10, 5, 8, 2, 1, 4, 9, 3, 2, 0}; print(arr); bubbleSort(arr); print(arr); } } 插入排序思路：类似玩扑克牌，左边已经排好序，每次来一张牌，从右向左进行比较，比较完后，从左到右都是已经排好序了。0 ~ 0 已经排好序了（第一张牌就是有序的）0 ~ 1 排好序0 ~ 2 排好序0 ~ 3 排好序0 ~ N 排好序public class Code04_InsertSort { /** * 插入排序类似玩扑克牌，每次来的牌插入之前已经排好序的牌中，类似插入一样。 */ public static void insertSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int N = arr.length; for (int end = 1; end < N; end++) { int newNumIndex = end; while ((newNumIndex - 1) >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) { swap(arr, newNumIndex - 1, newNumIndex); newNumIndex--; } } } public static void insertSort2(int[] arr) { if (arr == null || arr.length < 2) { return; } int N = arr.length; for (int end = 1; end < N; end++) { for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) { swap(arr, pre, pre + 1); } } } public static void swap(int[] arr, int i, int j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } public static void print(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 = {10, 5, 8, 2, 1, 4, 9, 3, 2, 0}; print(arr); insertSort(arr); print(arr); } }

我不是魔法师

新手入门篇-二分查找、局部最小、链表问题

二分法有序数组中找到num思路：数组是有序的，从小到大排序，利用这个特性，可以二分查找法，查找的数与中间的数比大小,如果中间的数大于查找的数，说明查找的数在左边，R = mid - 1。如果中间的数小于查找的数，说明查找的数在右边，L = mid + 1。public class Code01_BSExist { // 有序数组 public static boolean find(int[] arr, int num) { if (arr == null || arr.length == 0) { return false; } int L = 0; int R = arr.length - 1; while (L <= R) { int middle = (L + R) / 2; if (arr[middle] == num) { return true; } else if (arr[middle] < num) { L = middle + 1; } else { R = middle - 1; } } return false; } // for test public static boolean test(int[] arr, int num) { for (int cur : arr) { if (cur == num) { return true; } } return false; } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int len = (int) (Math.random() * maxSize) + 1; int[] arr = new int[len]; for (int i = 0; i < len; i++) { int ans = (int) (Math.random() * maxValue); arr[i] = ans; } return arr; } public static void main(String[] args) { int testTimes = 1000000; int maxSize = 100; int maxValue = 1000; boolean succeed = true; for (int i = 0; i < testTimes; i++) { int[] arr = generateRandomArray(maxSize, maxValue); Arrays.sort(arr); int num = (int) (Math.random() * maxValue); if (find(arr, num) != test(arr, num)) { System.out.println("出错了！"); succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); } } 有序数组中找到>=num最左的位置思路：利用二分查找法，如果中间数大于查找的数，说明查找的数在左边，则 R = mid - 1，此时需要用变量记住当前索引位置，如果中间数小于查找的数，说明查找的数在右边，则 L = mid + 1，此时不需要用变量记录当前索引，因为题目要求>=num最左的位置，而从中间的数左半部分都小于num，就不用考虑了。public class Code02_BSNearLeft { // arr有序的，>=num 最左 public static int mostLeftNoLessNumIndex(int[] arr, int num) { if (arr == null || arr.length == 0) { return -1; } int L = 0; int R = arr.length - 1; int ans = -1; while (L <= R) { int middle = (L + R) / 2; if (arr[middle] >= num) { R = middle - 1; ans = middle; } else { L = middle + 1; } } return ans; } // for test public static int test(int[] arr, int value) { for (int i = 0; i < arr.length; i++) { if (arr[i] >= value) { return i; } } return -1; } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } 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 testTime = 500000; int maxSize = 10; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr = generateRandomArray(maxSize, maxValue); Arrays.sort(arr); int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); if (test(arr, value) != mostLeftNoLessNumIndex(arr, value)) { printArray(arr); System.out.println(value); System.out.println(test(arr, value)); System.out.println(mostLeftNoLessNumIndex(arr, value)); succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); } } 有序数组中找到<=num最右的位置思路：利用二分查找法，如果中间的数小于查找的数，则 L = mid + 1，记录当前索引的位置。如果中间的数大于查找的数，则 R = mid - 1，此时不需要记录当前索引的位置，因为题目要求<=num最有的位置，中间的数及右边部分都大于查找的数，直接排除。public class Code03_BSNearRight { // 在arr上，找满足<=value的最右位置 public static int nearestIndex(int[] arr, int value) { int L = 0; int R = arr.length - 1; int index = -1; // 记录最右的对号 while (L <= R) { int mid = L + ((R - L) >> 1); if (arr[mid] <= value) { index = mid; L = mid + 1; } else { R = mid - 1; } } return index; } // for test public static int test(int[] arr, int value) { for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] <= value) { return i; } } return -1; } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } 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 testTime = 500000; int maxSize = 10; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr = generateRandomArray(maxSize, maxValue); Arrays.sort(arr); int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); if (test(arr, value) != nearestIndex(arr, value)) { printArray(arr); System.out.println(value); System.out.println(test(arr, value)); System.out.println(nearestIndex(arr, value)); succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); } } 局部最小值问题局部最小值问题推出二分查找的前提，数组不一定必须是有序的！！！思路：如果数组只有一个元素，则返回，如果数组有2个元素，则比较2个元素的大小，进行返回索引位。抛出这两种可能外，则L...R 肯定有最小值，局部最小值问题，它不是说在数组里找找最小值，而是局部只要最小就行，只要当前这个数比左边小，且比右边小，就满足局部最小原则。public class Code04_BSAwesome { // arr 整体无序 // arr 相邻的数不相等！ public static int oneMinIndex(int[] arr) { if (arr == null || arr.length == 0) { return -1; } int N = arr.length; if (N == 1) { return 0; } if (arr[0] < arr[1]) { return 0; } if (arr[N - 1] < arr[N - 2]) { return N - 1; } int L = 0; int R = N - 1; // L...R 肯定有局部最小 while (L < R - 1) { int mid = (L + R) / 2; if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) { return mid; } else { if (arr[mid] > arr[mid - 1]) { R = mid - 1; } else { L = mid + 1; } } } return arr[L] < arr[R] ? L : R; } // 生成随机数组，且相邻数不相等 public static int[] randomArray(int maxLen, int maxValue) { int len = (int) (Math.random() * maxLen);// [0,maxLen - 1] int[] arr = new int[len]; if (len > 0) { arr[0] = (int) (Math.random() * maxValue); for (int i = 1; i < len; i++) { do { arr[i] = (int) (Math.random() * maxValue); } while (arr[i] == arr[i - 1]); } } return arr; } // 也用于测试 public static boolean check(int[] arr, int minIndex) { if (arr.length == 0) { return minIndex == -1; } int left = minIndex - 1; int right = minIndex + 1; boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true; boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true; return leftBigger && rightBigger; } public static void printArray(int[] arr) { for (int num : arr) { System.out.print(num + " "); } System.out.println(); } public static void main(String[] args) { int maxLen = 100; int maxValue = 200; int testTime = 1000000; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int[] arr = randomArray(maxLen, maxValue); int ans = oneMinIndex(arr); if (!check(arr, ans)) { printArray(arr); System.out.println(ans); break; } } System.out.println("测试结束"); } } 单链表和双链表的定义单链表：值，一条next指针双链表：值，一条pre指针，一条next指针玩出无尽的花样！单双链表的反转经典题目：给定一个单链表的头head，完成链表的逆序调整public class Code01_ReverseList { public static class Node { public int value; public Node next; public Node(int data) { this.value = data; } } // 单链表反转 public static Node reverseLinkedList(Node head) { Node pre = null; Node next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } public static void main(String[] args) { // 单链表反转测试 Node node1 = new Node(1); node1.next = new Node(2); node1.next.next = new Node(3); Node head = reverseLinkedList(node1); while (head != null) { System.out.print(head.value + " "); head = head.next; } System.out.println(); } } 给定一个双链表的头head，完成链表的逆序调整public class Code01_ReverseList { public static class DoubleNode { public int value; public DoubleNode last; public DoubleNode next; public DoubleNode(int data) { this.value = data; } @Override public String toString() { return value + ""; } } // 双链表反转 public static DoubleNode reverseDoubleList(DoubleNode head) { DoubleNode pre = null; DoubleNode next = null; while (head != null) { next = head.next; head.next = pre; head.last = next; pre = head; head = next; } return pre; } public static void main(String[] args) { // 双链表反转测试 DoubleNode doubleNode1 = new DoubleNode(1); doubleNode1.next = new DoubleNode(2); doubleNode1.next.next = new DoubleNode(3); doubleNode1.next.next.last = doubleNode1.next; doubleNode1.next.last = doubleNode1; DoubleNode doubleNodeHead = reverseDoubleList(doubleNode1); while (doubleNodeHead != null) { System.out.println(doubleNodeHead.next + "<-" + doubleNodeHead + "->" + doubleNodeHead.last); doubleNodeHead = doubleNodeHead.next; } System.out.println(); } } 用单链表实现队列和栈用单链表结构实现队列结构public class Code02_LinkedListToQueueAndStack { public static class Node<V> { public V value; public Node<V> next; public Node(V data) { this.value = data; } } public static class MyQueue<V> { private Node<V> head; private Node<V> tail; private int size; public boolean isEmpty() { return size == 0; } public int size() { return size; } public void offer(V data) { Node<V> cur = new Node<>(data); if (tail == null) { head = tail = cur; } else { tail.next = cur; tail = cur; } size++; } public V poll() { V ans = null; if (head != null) { ans = head.value; head = head.next; size--; } if (head == null) { tail = null; } return ans; } public V peek() { V ans = null; if (head != null) { ans = head.value; } return ans; } } public static void main(String[] args) { MyQueue queue = new MyQueue(); queue.offer(1); queue.offer(3); queue.offer(2); while (!queue.isEmpty()) { System.out.print(queue.poll() + " "); } System.out.println(); } } 用单链表结构实现栈结构public class Code02_LinkedListToQueueAndStack { public static class Node<V> { public V value; public Node<V> next; public Node(V data) { this.value = data; } } public static class MyStack<V> { private Node<V> head; private int size; public boolean isEmpty() { return size == 0; } public int size() { return size; } public void push(V data) { Node<V> cur = new Node<>(data); if (head != null) { cur.next = head; } head = cur; size++; } public V pop() { V ans = null; if (head != null) { ans = head.value; head = head.next; size--; } return ans; } public V peek() { return head != null ? head.value : null; } } public static void main(String[] args) { MyStack stack = new MyStack(); stack.push(6); stack.push(1); stack.push(3); while (!stack.isEmpty()) { System.out.print(stack.pop() + " "); } System.out.println(); } } 用双链表实现双端队列用双链表结构实现双端队列public class Code03_DoubleLinkedListDeque { public static class Node<V> { public V value; public Node<V> next; public Node<V> last; public Node(V data) { this.value = data; } } public static class MyDeque<V> { private Node<V> head; private Node<V> tail; private int size; public boolean isEmpty() { return size == 0; } public int size() { return size; } // 头部添加 public void pushHead(V data) { Node<V> cur = new Node<>(data); if (head == null) { head = tail = cur; } else { cur.next = head; head.last = cur; head = cur; } size++; } // 尾部添加 public void pushTail(V data) { Node<V> cur = new Node<>(data); if (head == null) { head = tail = cur; } else { tail.next = cur; cur.last = tail; tail = cur; } size++; } // 头部取出 public V pollHead() { V ans = null; if (head == null) { return ans; } size--; ans = head.value; if (head == tail) { head = tail = null; } else { head = head.next; head.last = null; } return ans; } // 尾部取出 public V pollTail() { V ans = null; if (head == null) { return ans; } size--; ans = tail.value; if (head == tail) { head = tail = null; } else { tail = tail.last; tail.next = null; } return ans; } // 查看头部 public V peekHead() { return head != null ? head.value : null; } // 查看尾部 public V peekTail() { return tail != null ? tail.value : null; } } } K个节点的组内逆序调整给定一个单链表的头节点head，和一个正数k，实现k个节点的小组内部逆序，如果最后一组不够k个就不调整。例子：调整前：1->2->3->4->5->6->7->8 k = 3调整后：3->2->1->6->5->4->7->8public class Code04_ReverseNodesInKGroup { public static class ListNode { public int val; public ListNode next; public ListNode(int data) { this.val = data; } } public static ListNode reverseKGroup(ListNode head, int k) { ListNode start = head; ListNode end = getKGroupEnd(start, k); if (end == null) { return head; } head = end; reverse(start, end); ListNode lastEnd = start; while (lastEnd.next != null) { start = lastEnd.next; end = getKGroupEnd(start, k); if (end == null) { return head; } reverse(start, end); lastEnd.next = end; lastEnd = start; } return head; } // 从start开始，返回k位置上的节点 public static ListNode getKGroupEnd(ListNode start, int k) { while (--k != 0 && start != null) { start = start.next; } return start; } // 从start到end，反转链表 public static void reverse(ListNode start, ListNode end) { end = end.next; ListNode cur = start; ListNode pre = null; ListNode next = null; while (cur != end) { next = cur.next; cur.next = pre; pre = cur; cur = next; } start.next = end; } public static void print(ListNode head) { while (head != null) { System.out.print(head.val + "->"); head = head.next; } System.out.println(); } public static void main(String[] args) { // 1->2->3->4->5->6->7->8 k = 3 ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); ListNode node6 = new ListNode(6); ListNode node7 = new ListNode(7); ListNode node8 = new ListNode(8); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; node7.next = node8; print(node1); // 开始 ListNode head = reverseKGroup(node1, 3); print(head); } } 两个链表相加给定两个链表的头节点head1和head2，认为从左到右是某个数字从低位到高位，返回相加之后的链表例子 4->3->6    2->5->3返回 6->8->9解释 634 + 352 = 986public class Code05_AddTwoNumbers { public static class ListNode { private int val; private ListNode next; public ListNode(int data) { this.val = data; } } public static ListNode addTwoNumbers(ListNode head1, ListNode head2) { int len1 = listLength(head1); int len2 = listLength(head2); ListNode l = len1 >= len2 ? head1 : head2; ListNode s = l == head1 ? head2 : head1; ListNode curL = l; ListNode curS = s; ListNode last = curL; int carry = 0; int curNum = 0; while (curS != null) { curNum = curL.val + curS.val + carry; curL.val = (curNum % 10); carry = curNum / 10; last = curL; curL = curL.next; curS = curS.next; } while (curL != null) { curNum = curL.val + carry; curL.val = (curNum % 10); carry = curNum / 10; last = curL; curL = curL.next; } if (carry != 0) { last.next = new ListNode(1); } return l; } // 求链表长度 public static int listLength(ListNode head) { int len = 0; while (head != null) { len++; head = head.next; } return len; } } 两个有序链表的合并给定两个有序链表的头节点head1和head2，返回合并之后的大链表，要求依然有序。例子 1->3->3->5->7  2->2->3->3->7返回 1->2->2->3->3->3->3->5->7->7public class Code06_MergeTwoSortedLinkedList { public static class ListNode { public int val; public ListNode next; public ListNode(int data) { this.val = data; } } public static ListNode mergeTwoSortedLinkedList(ListNode head1, ListNode head2) { if (head1 == null || head2 == null) { return head1 == null ? head2 : head1; } // 从两个有序的链表中找见头位置，谁小谁做头 ListNode head = head1.val <= head2.val ? head1 : head2; ListNode cur1 = head.next; ListNode cur2 = head == head1 ? head2 : head1; ListNode pre = head; while (cur1 != null && cur2 != null) { if (cur1.val <= cur2.val) { pre.next = cur1; cur1 = cur1.next; } else { pre.next = cur2; cur2 = cur2.next; } pre = pre.next; } pre.next = cur1 != null ? cur1 : cur2; return head; } public static void main(String[] args) { ListNode firstListNode = new ListNode(1); firstListNode.next = new ListNode(3); firstListNode.next.next = new ListNode(5); ListNode secondListNode = new ListNode(1); secondListNode.next = new ListNode(2); ListNode head = mergeTwoSortedLinkedList(firstListNode, secondListNode); while (head != null) { System.out.print(head.val + " "); head = head.next; } System.out.println(); } }

biubiuuuuu

如何替换JavaScript对象数组中的键和值，同时保持顺序，求大佬指导？

原数据 tableData = [ { A: '12A', B: '12B' }, { A: '13A', B: '13B' } ] D替换key和value中的A之后，顺序变了 https://wmprod.oss-cn-shanghai.aliyuncs.com/c/user/20241011/668016b2e1f276122492b7b3035c66c5.png HTML渲染 {{ scope.row[keysData[index]] }} 禁用 {{ scope.row[keysData[index]] }} 启用 https://wmprod.oss-cn-shanghai.aliyuncs.com/c/user/20241011/33530f1196918550546e181ef63f67d4.png https://wmprod.oss-cn-shanghai.aliyuncs.com/c/user/20241011/668016b2e1f276122492b7b3035c66c5.png 替换方法 this.tableData.forEach(item => { for (let k in item) { if (k == column.property && item[k] != null) { item[k] = item[k].replace(k, value) if (item.hasOwnProperty(column.property)) { item[value] = item[k] delete item[k] } } } }) 这个是座位图，每一个key是每一列的编号，编号修改了，那一列的座位号中的字母也要跟着变，现在头疼的是改完后数据顺序变了，编码和座位号对不上，所以我希望得到结果是替换完之后，数据顺序保持不变。或者大家有别的好方法好思路可以指导一下 tableData = [ { D: '12D', B: '12B' }, { D: '13D', B: '13B' } ]

桃子爱吃玉米

如何快速在可变区间内求元素总和？

有没有一种数据结构，可以快速求区间内的元素总和、快速修改区间元素值、区间大小可变（头插头删尾插尾删），最好空间占用不超过4N 目前研究了下树状数组和线段树，头插头删一个元素时都需要重新建树，这样开销太大

型男不是我还是谁

数据类型(DT)和抽象数据类型(ADT)的区别是什么？我看概念没有差异呢？

数据类型(DT)和抽象数据类型(ADT)的区别是什么？我看概念没有看出差异呢？ 1、数据类型是`一组性质相同的值的集合`以及`定义于这个值集合上的一组操作`的统称。 2、抽象数据类型(Abstract Data Type，简称 ADT) 是指一个`数学模型`以及`定义在该模型上的一组操作`的统称。 1、这里的差别就是"一组性质相同的值的集合" 和 "数学模型" 的区别吗，能否举例解释一下是什么差异呢？ 2、数据类型是否是指的是比如：int 和 add()/ multi() 等？

感觉对了

python为什么DFS中append到ans的结果不是预期的独立的列表？

求教做了一道OJ题目,调试发现ans的格式是ans: [[[0, 0], [0, 1], [0, 2], [0, 3]], [[0, 0], [0, 1], [0, 2], [1, 2]]] 为什么明明每次执行dfs的都是同级别的对path的append操作,会产生两个大的list. 和预期的每个都是独立元素的list不一致ans: [[0, 0], [0, 1], [0, 2], [0, 3], [0, 0], [0, 1], [0, 2], [1, 2]] https://wmprod.oss-cn-shanghai.aliyuncs.com/c/user/20240917/3f807af5d2b6488f97e7c696dc1ecfcd.png IR = [(0, 1), (1, 0), (0, -1), (-1, 0)] # input n = int(input()) code = list(map(int, input().split())) m = int(input()) book = [] for i in range(m): book.append(list(map(int, input().split()))) ans = [] path = [] visited = [[False] * m for i in range(m)] #dfs def dfs(code, index, path, visited, ans): if index == len(code): # ans.append("".join(map(str, path)) ans.append(path[:]) return for direction in DIR: x, y = path[-1][0] + direction[0], path[-1][1] + direction[1] if 0 <= x < m and 0 <= y < m and not visited[x][y] and book[x][y] == code[index]: path.append([x, y]) visited[x][y] = True dfs(code, index + 1, path, visited, ans) path.pop() visited[x][y] = False #map track for i in range(m): for j in range(m): if book[i][j] == code[0]: path.append([i, j]) visited[i][j] = True dfs(code, 1, path, visited, ans) path.pop() visited[i][j] = False #ans format if len(ans) == 0: print("error") else: res = [] for i in range(len(ans)): new_list = [] for j in range(len(ans[i])): new_list+=ans[i][j] res.append(new_list) res.sort() print(" ".join(str(i) for i in res[0])) 因为预期不同 所以改变了format部分 单纯是没想到为什么是这个格式

MaxClick

从扁平的数据结构数组，转换为嵌套式的数据结构，请问需要什么算法才能实现呢？

请问下，这种算法叫什么呢，如何才能进行实现： 定义的interface如下： type PropertyDataType = { name: string, isFrom: ItemDataType, // 从哪个类/抽象类/接口来的 value: string | number | undefined, // 接口无实现 = undefined } type MethodDataType = { name: string, isFrom: ItemDataType, value: string | undefined // 接口无实现 = undefined isAbstract: boolean // 是否是抽象方法 } //#region 类接口之间的关系 type InheritanceRelationType = { name: 'inheritance', relationToId: ItemDataTypeId } type ImplementationRelationType = { name: 'implementation', relationToId: ItemDataTypeId } type AggregationRelationType = { name: 'aggregation', relationToId: ItemDataTypeId } type CompositionRelationType = { name: 'composition', relationToId: ItemDataTypeId } type RelationType = InheritanceRelationType | ImplementationRelationType | AggregationRelationType | CompositionRelationType //#endregion type ItemDataTypeId = string | number // 类数据类型: 类/抽象类/接口 export type ItemDataType = { id: ItemDataTypeId, type: 'Class' | 'AbstractClass' | 'Interface', name: string, // 类名称 properties: PropertyDataType[], // 属性 methods: MethodDataType[], relations: RelationType[] // 与其他ItemDataType的关系 } 现在有数据（很多的ItemDataType类型数据组成的数组）： const dataList = [ { id: 1, type: 'Class', name: 'AnimalBase', properties: [], methods: [], relations: [] }, { id: 2, type: 'Class', name: 'Animal', properties: [], methods: [], relations: [{name: 'inheritance', relationToId: 1}] }, { id: 3, type: 'Class', name: 'Cat', properties: [], methods: [], relations: [{name: 'inheritance', relationToId: 2}] } ] 想要 设定一个方法： "getInheritanceChain(id:number): ReturnType" 返回ReturnType数据内容为嵌入式数据，举例： { name: 'Cat', comesFrom: [ { relationName: 'inheritance', name: 'Animal', type: 'Class', comesFrom: [ { relationName: 'inheritance', name: 'AnimalBase', type: 'Class', comesFrom: [] } ] } ] } 请问这个需要如何进行处理呢？是否有现有的库进行直接处理呢？