神奇海螺🐚

面试题 08.06. 汉诺塔问题 时间复杂度O(nlogn) 归并排序 class Solution { public ListNode sortList(ListNode head) { return sortList(head, null); } // 左右分别排序，然后合并 public ListNode sortList(ListNode head, ListNode tail) { if (head == null) { return head; } if (head.next == tail) { head.next = null; return head; } ListNode mid = head, fast = head; while (fast != tail) { mi ...

面试题 08.06. 汉诺塔问题 递归 class Solution { public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) { move(A.size(), A, B, C); } public void move(int size, List<Integer> a, List<Integer> b, List<Integer> c) { if (size == 1) { c.add(a.remove(a.size() - 1)); return; } move(size - 1, a, c, b); c.add(a.remove(a.size() - 1)); move(size - 1 , b, a, c); ...

剑指 Offer 59 - I. 滑动窗口的最大值 时间复杂度O(n) 单调栈，每次保证栈顶是最大值，不在滑动窗口中的元素删除 public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 0 || k == 0) { return new int[]{}; } int[] result = new int[nums.length - k + 1]; Deque<Integer> deque = new LinkedList<>(); int left = 0; for (int i = 0; i < nums.length; i++) { while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()])
...

剑指 Offer 59 - II. 队列的最大值 剑指 Offer 59 - II. 队列的最大值 解法一 均摊时间复杂度O(1) 空间复杂度O(n) 题目是队列，所以先进先出，所以当插入最大值时，可以删除之前的值，因为后面插入的总是后删除 class MaxQueue { private Deque<Integer> list; private Deque<Integer> max; public MaxQueue() { list = new LinkedList<>(); max = new LinkedList<>(); } public int max_value() { return list.isEmpty()? -1: max.peekFirst(); } public void push_back(int value) { list.offerLast(va ...

LeetCode 739. 每日温度 解法一 双循环 时间复杂度O(n²) 空间复杂度O(n) public int[] dailyTemperatures(int[] T) { int[] num = new int[T.length]; for (int i = 0; i < T.length - 1; i++) { for (int j = i + 1; j < T.length; j++) { if (T[i] < T[j]) { num[i] = j - i; break; } num[i] = 0; } } return num; } 解法二 反向循环 时间复杂度O(nlgn)（我猜的 空间复杂度O(n) publi ...

https://leetcode-cn.com/problems/calculator-lcci/ LeetCode 16.26. 计算器 时间复杂度 O(n) public int calculate(String s) { Stack<Integer> nums = new Stack<>(); int i = 0, sum = 0; while (i < s.length()) { while (i < s.length() && s.charAt(i) == ' ') { i++; } if (i >= s.length()) break; char c = s.charAt(i); if (c == '*' || c == '/' || c ...

LeetCode 2.两数相加 时间复杂度O(n) 解法一：递归 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l2 == null) { return l1; } else if (l1 == null && l2 != null) { return l2; }else { l1.val = l1.val + l2.val; jinwei(l1); l1.next = addTwoNumbers(l1.next, l2.next); return l1; } } public void jinwei(ListNode l1) { if (l ...

LeetCode 206. 反转链表 时间复杂度 O(n) Java class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; while (head != null){ ListNode temp = head.next; head.next = prev; prev = head; head = temp; } return prev; }}//runtime:0 ms//memory:38.3 MB Python class Solution: def reverseList(self, head): cur, prev = head, None while cur: cur.next, prev, ...

LeetCode 1528.重新排列字符串 时间复杂度O(n) class Solution { public String restoreString(String s, int[] indices) { char[] chars = s.toCharArray(); for (int i = 0; i < indices.length; i++) { chars[indices[i]] = s.charAt(i); } return new String(chars); }}//runtime:1 ms//memory:38.5 MB

面试题 01.03. URL化 解题一: 先计算长度，然后再遍历 class Solution { public String replaceSpaces(String S, int length) { int ln = 0; for (int i = 0; i < length; i++) { if (S.charAt(i) == ' ') { ln += 3; } else { ln ++; ...