byu_rself

LC.P31[下一个排列] 方法一：双指针1234567891011121314151617181920212223242526272829class Solution { public void nextPermutation(int[] nums) { int n = nums.length, i = n - 2; // 从后往前找到第一个 (i, i + 1) 满足 nums[i] < nums[i + 1] while (i >= 0 && nums[i] >= nums[i + 1]) --i; if (i >= 0) { int j = n - 1; // 在 [i + 1, n) 中从后往前找到第一个元素 j，满足nums[i] < nums[j] while (j >= 0 && nums[j] <= nums[i]) --j; ...

LC.P1749[任意子数组和的绝对值的最大值] 方法一：动态规划1234567891011121314class Solution { public int maxAbsoluteSum(int[] nums) { int n = nums.length, ans = Math.abs(nums[0]); int[] f = new int[n], g = new int[n]; f[0] = nums[0]; g[0] = nums[0]; for (int i = 1; i < n; ++i) { f[i] = Math.max(f[i - 1], 0) + nums[i]; g[i] = Math.min(g[i - 1], 0) + nums[i]; ans = Math.max(ans, Math.max(f[i], Math.abs(g[i]))); } re ...

LCR.P67[数组中两个数的最大异或值] 方法一：贪心+Trie12345678910111213141516171819202122232425262728293031323334353637383940414243class Solution { public int findMaximumXOR(int[] nums) { int ans = 0; Trie trie = new Trie(); for (int num : nums) { trie.add(num); int x = trie.getVal(num); ans = Math.max(ans, num ^ x); } return ans; } private static class Trie { Trie[] node = new Trie[2]; public voi ...

LC.P1268[搜索推荐系统] 方法一：排序+Trie123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960class Solution { public List<List<String>> suggestedProducts(String[] products, String searchWord) { Trie trie = new Trie(); Arrays.sort(products); for (int i = 0; i < products.length; ++i) trie.insert(products[i], i); List<List<String>> ans = new ArrayList<>(); StringBuilder pre ...

LC.P344[反转字符串] 方法一：双指针123456789class Solution { public void reverseString(char[] s) { for (int left = 0, right = s.length - 1; left < right; ++left, --right) { char temp = s[left]; s[left] = s[right]; s[right] = temp; } }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P24[两两交换链表中的节点] 方法一：递归12345678910111213141516171819/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead ...

LC.P21[合并两个有序链表] 方法一：迭代123456789101112131415161718192021222324252627/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode ans = new ListNode(), p = ans; ...

LC.P448[找到所有数组中消失的数字] 方法一：原地修改1234567891011121314class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int n = nums.length; List<Integer> ans = new ArrayList<>(); for (int num : nums) { int index = (num - 1) % n; nums[index] += n; } for (int i = 0; i < n; ++i) { if (nums[i] <= n) ans.add(i + 1); } return ans; }} 时间复杂度：$O(n) ...

Offer.P3[数组中重复的数字] 方法一：原地哈希12345678910111213141516class Solution { public int findRepeatNumber(int[] nums) { int i = 0; while (i < nums.length) { if (nums[i] == i) { ++i; continue; } if (nums[i] == nums[nums[i]]) return nums[i]; int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } return -1; }} 时间复杂度：$O(n)$ 空间复杂度： ...

LC.P287[寻找重复数] 方法一：快慢指针123456789101112131415class Solution { public int findDuplicate(int[] nums) { int slow = nums[0], fast = nums[nums[0]]; while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$