byu_rself

LC.P167[两数之和II-输入有序数组] 方法一：双指针123456789101112class Solution { public int[] twoSum(int[] numbers, int target) { int l = 0, r = numbers.length - 1; while (l < r) { int sum = numbers[l] + numbers[r]; if (sum < target) ++l; else if (sum > target) --r; else return new int[]{l + 1, r + 1}; } return new int[]{}; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LC.P526[优美的排列] 方法一：回溯123456789101112131415161718192021222324class Solution { int n; boolean[] visited; public int countArrangement(int n) { this.n = n; visited = new boolean[n + 1]; return dfs(1); } private int dfs(int i) { if (i > n) return 1; int ans = 0; for (int x = 1; x <= n; ++x) { if (!visited[x] && (x % i == 0 || i % x == 0)) { visited[x] = true; ...

LC.P2532[过桥的时间] 方法一：堆+模拟1234567891011121314151617181920212223242526272829303132333435363738394041424344454647class Solution { public int findCrossingTime(int n, int k, int[][] time) { Arrays.sort(time, (a, b) -> a[0] + a[2] - b[0] - b[2]); PriorityQueue<int[]> workL = new PriorityQueue<>((a, b) -> a[1] - b[1]); PriorityQueue<int[]> workR = new PriorityQueue<>((a, b) -> a[1] - b[1]); PriorityQueue<int[]> waitL = new P ...

LC.P224[基本计算器] 方法一：栈123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { int i, n; char[] cs; public int calculate(String s) { cs = s.toCharArray(); n = cs.length; return cal(); } private int cal() { int num = 0; char sign = '+'; Deque<Integer> stack = new ArrayDeque<>(); for (; i < n; ++i) { char c = cs[i]; if (c == ' ...

LC.P227[基本计算器II] 方法一：栈12345678910111213141516171819202122232425262728293031class Solution { public int calculate(String s) { char[] cs = s.toCharArray(); int n = cs.length, num = 0; Deque<Integer> stack = new ArrayDeque<>(); char sign = '+'; for (int i = 0; i < n; ++i) { char c = cs[i]; // 数字 if (c >= '0' && c <= '9') { num = num * 1 ...

LC.P2178[拆分成最多数目的正偶数之和] 方法一：贪心123456789101112class Solution { public List<Long> maximumEvenSplit(long finalSum) { List<Long> ans = new ArrayList<>(); if (finalSum % 2 == 1) return ans; for (long i = 2; i <= finalSum; i += 2) { ans.add(i); finalSum -= i; } ans.add(ans.remove(ans.size() - 1) + finalSum); return ans; }} 时间复杂度：$O(\sqrt {finalSum})$ 空间复杂度：$O(1)$

LC.P535[TinyURL的加密与解密] 方法一：哈希表+模拟123456789101112131415161718192021222324252627282930313233public class Codec { String s = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; int k = 6; Map<String, String> originToTinyMap = new HashMap<>(), tinyToOriginMap = new HashMap<>(); Random random = new Random(); String prefix = "https://byurself.github.io/"; // Encodes a URL to a shortened URL. public String encode(String longU ...

LC.P468[验证IP地址] 方法一：模拟123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution { public String validIPAddress(String queryIP) { if (queryIP.contains(".") && checkIPv4(queryIP)) return "IPv4"; else if (queryIP.contains(":") && checkIPv6(queryIP)) return "IPv6"; else return "Neither"; } private boolean checkIPv4(String ip) { char[] s = ip ...

LC.P2600[K件物品的最大和] 方法一：贪心1234567class Solution { public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) { if (numOnes >= k) return k; else if (numOnes + numZeros >= k) return numOnes; else return numOnes - (k - numOnes - numZeros); }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$

LC.P65[有效数字] 方法一：模拟123456789101112131415161718192021222324252627282930313233343536373839404142class Solution { public boolean isNumber(String s) { char[] cs = s.toCharArray(); int index = -1, n = cs.length; for (int i = 0; i < n; ++i) { if (cs[i] == 'e' || cs[i] == 'E') { if (index == -1) index = i; else return false; } } boolean ans = true; if (in ...