算法 1.双指针 2.一个指针在奇数位置上移动，一个指针在偶数位置上移动 3.每次移动到奇数位置上是偶数，偶数位置上是奇数，交换二者，继续移动 public int[] sortArrayByParityII(int[] A) { int n = A.length; int i = 0, j = 1; while (i < n && j < n) { while (i < n && (A[i] & 1) == 0) { i += 2; } ...

算法 1.动态规划：dp[i][j]表示匹配到key的第i个字符且ring的第j个字符在12：00位置的最小步数 2.初始状态：dp[0][j] = Math.min(j, n - j) + 1; j ∈ key的第一个字符ring中的位置 3.转移公式： dp[i][j]的计算：只需要计算key中第i个字符出现在ring中的位置的那些j（其他没出现的初始化为MAX_VALUE），如何计算呢？利用key中第i-1个字符出现在ring中的位置的那些k，也即dp[i-1][k]的值，求这些位置到dp[i][j]的最小值，最终就是dp[i][j] 4.最后的答案是dp[m-1]中的最小值，m是k...

算法 1.分别验证IPv4和IPv6 2.注意事项 2.1 分割字符串时，使用limit = -1的split函数，使得字符串末尾或开头有一个'.'或':'也能分割出空的字符串 2.2 使用Integer.parseInt()函数检查异常 public String validIPAddress(String IP) { return validIPv4(IP) ? "IPv4" : (validIPv6(IP) ? "IPv6" : "Neither"); } private boolean validIPv4(String IP) { String[] strs...

算法 1.首先找到最大的i使得nums[i]<nums[i+1] 2.如果没有这样的i，当前排列是字典序最大的排列，翻转整个数组即是下一个排列 3.如果找到这样的i，接着找到最大的j使得nums[j]>nums[i] 4.交换i和j，再翻转数组的[i+1, n-1]部分即是下一个排列 public void nextPermutation(int[] nums) { int n = nums.length; int i = 0; for (i = n - 2; i >= 0; i--) { if (nums[i] < num...

算法 1.递归 2.当当前节点是null时，新建节点插入 3.当当前节点不是null时 如果插入值比当前节点值大，插入到右子节点 如果插入值比当前节点值小，插入到左子节点 public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } if (val < root.val) { root.left = insertIntoBST(root.left, val); } el...

算法 1.快排 2.每次寻找基准数后判断基准数是否刚好在K-1位置 如果在，那么左侧刚好是最小的K个point 如果不在，递归寻找 public int[][] kClosest(int[][] points, int K) { int left = 0, right = points.length - 1; int index = partition(points, left, right); while (index != K - 1) { if (index < K - 1) { left = index +...

算法 1.找到前K个节点范围，当不足K个时返回head 2.记录接下来K个的开头 3.翻转前K个节点 4.用刚才记录的接下来K个节点的开头递归翻转后面的，然后连接到前K个翻转前的head节点 ps：2和3顺序不能反过来，因为翻转后会改变原链表的指向 public ListNode reverseKGroup(ListNode head, int k) { if (head == null || k == 1) { return head; } ListNode right = head; for (int i = 1; i < k;...

题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。 算法 1.在头节点前面建立伪节点 2.双指针，前指针先走到第k个节点，随后前后指针一起走，当前指针走到结尾null节点时，后指针即指向倒数第k个节点 public ListNode getKthFromEnd(ListNode head, int k) { ListNode dummy = new ListNode(-1); dumm...

算法 1.动态规划：dp[i][0]表示第i天没有持有股票的最大收益，dp[i][1]表示第i天持有这支股票的最大收益 2.初始状态：dp[0][0] = 0;dp[0][1] = -prices[0]; 3.状态转移： 第i天没有持有这只股票有两种情况：第i-1天也没有持有这只股票；第i-1天持有这只股票，第i天以prices[i]卖出 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); 第i天持有这只股票也有两种情况：第i-1天也持有这只股票；第i-1天没有持有这只股票，第i天以prices[i]买入 dp[i][1...

算法 归并排序 1.计算前缀和sums[i]表示[0, i)的元素之和 2.对前缀和进行归并排序，在归并的过程中对已有序的数组统计左半部分和右半部分组成的下标对满足sum[j]-sum[i]的个数 有序数组sum[left, mid]和sum[mid+1, right] 左下标对在外层循环[left, mid]，右下标对在内层l和r双指针做循环，找到可以和左下标对匹配的范围，加到最终结果中 public int countRangeSum(int[] nums, int lower, int upper) { long[] sums = new long[nums.lengt...

算法 Java-Integer, Comparator public int[] sortByBits(int[] arr) { Integer[] integers = new Integer[arr.length]; for (int i = 0; i < arr.length; i++) { integers[i] = arr[i]; } // Arrays.sort(integers, (o1, o2) -> Integer.bitCount(o1) == Integer.bitCount(o2) ? o1 - o2 ...

算法 1.BFS 2.每次把队列中的所有元素逐个出队，寻找他们可以转换的下一个字符串添加到队列 2.1 当遇到目标字符串时，结束BFS 2.2 当队列空时还没遇到目标字符串时，无法转换 2.3 寻找可以转换的下一个字符串的方法：常数时间复杂度，使用a-z逐个替换字符判断是否存在于wordList中并且没有访问过 public int ladderLength(String beginWord, String endWord, List<String> wordList) { HashSet<String> wordDict = new HashSet&...

算法 1.把前面不能和新插入区间合并的区间添加到结果：区间的右侧小于新插入区间的左侧 2.把中间可以和新插入区间合并的区间与新插入区间合并 区间的右侧大于等于新插入区间的左侧 区间的左侧小于等于新插入区间的右侧 3.把后面不能和新插入区间合并的区间添加到结果 public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) { ArrayList<Interval> result = new ArrayList<>(10)...

算法 从两侧向上爬山，最终都能爬到同一个山顶的就是一个山脉数组 public boolean validMountainArray(int[] A) { int length = A.length; int i = 0, j = length - 1; while (i < length - 1 && A[i] < A[i+1]) { i++; } while (j > 0 && A[j-1] > A[j]) { j--; } return i ...