byu_rself

Offer.P35[复杂链表的复制] 方法一：哈希表1234567891011121314151617181920212223242526272829303132/*// Definition for a Node.class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }}*/class Solution { public Node copyRandomList(Node head) { if (head == null) return null; Node p = head; Map<Node, Node> map = new HashMap<>(); while (p != nu ...

Offer.P24[反转链表] 方法一：迭代(双指针)1234567891011121314151617181920/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null, cur = head; while (cur != null) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } ...

Offer.P22[链表中倒数第k个节点] 方法一：模拟1234567891011121314151617181920212223/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode p = head; int n = 0; while (p != null) { ++n; p = p.next; } p = head; for (int i = 1; i <= n - k; ++i ...

LC.P2352[相等行列对] 方法一：暴力123456789101112131415161718class Solution { public int equalPairs(int[][] grid) { int n = grid.length, ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (isEqual(i, j, n, grid)) ++ans; } } return ans; } private boolean isEqual(int row, int col, int n, int[][] grid) { for (int i = 0; i < n; ++i) { if (grid[row ...

LC.P472[连接词] 方法一：Trie+记忆化搜索123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657class Solution { Trie trie; public List<String> findAllConcatenatedWordsInADict(String[] words) { trie = new Trie(); List<String> ans = new ArrayList<>(); Arrays.sort(words, (a, b) -> a.length() - b.length()); for (String word : words) { int n = word.length(); if (n == 0) con ...

LC.P2460[对数组执行操作] 方法一：模拟123456789101112131415161718192021class Solution { public int[] applyOperations(int[] nums) { int n = nums.length; for (int i = 0; i < n - 1; ++i) { if (nums[i] == nums[i + 1]) { nums[i] *= 2; nums[i + 1] = 0; } } int k = 0; for (int i = 0; i < n; ++i) { if (nums[i] != 0) { nums[k++] = nums[i]; } ...

LC.P583[两个字符串的删除操作] 方法一：转化为最长公共子序列求将两个字符串删除任意字符后能相同的最短步数，可以等价于求两个字符串的最长公共子序列LCS，最后使得两字符串删除任意字符后能相同的最短步数$= n - lcs + m - lcs$ 123456789101112131415161718class Solution { public int minDistance(String word1, String word2) { int n = word1.length(), m = word2.length(); int[][] f = new int[n + 1][m + 1]; // 求最长公共子序列 (LC.P1143) for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (word1.charAt(i - 1) == ...

LC.P2465[不同的平均值数目] 方法一：排序+哈希表1234567891011class Solution { public int distinctAverages(int[] nums) { Arrays.sort(nums); int n = nums.length; Set<Integer> set = new HashSet<>(); for (int i = 0, j = n - 1; i < j; ++i, --j) { set.add(nums[i] + nums[j]); } return set.size(); }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(n)$

LC.P1143[最长公共子序列] 方法一：动态规划12345678910111213141516class Solution { public int longestCommonSubsequence(String text1, String text2) { int n = text1.length(), m = text2.length(); int[][] f = new int[n + 1][m + 1]; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { f[i][j] = f[i - 1][j - 1] + 1; } else { ...

LC.P1035[不相交的线] 方法一：动态规划12345678910111213141516class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int n = nums1.length, m = nums2.length; int[][] f = new int[n + 1][m + 1]; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (nums1[i - 1] == nums2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i ...