赞
踩
题目 | 难度 | 出现频率 |
---|---|---|
3. 无重复字符的最长子串 | medium | ★★★★★ |
206. 反转链表 | easy | ★★★★★ |
25. K 个一组翻转链表 | 困难 | ★★★★★ |
215. 数组中的第K个最大元素 | medium | ★★★★★ |
103. 二叉树的锯齿形层序遍历 | medium | ★★★★★ |
160. 相交链表 | easy | ★★★★☆ |
146. LRU 缓存机制 | medium | ★★★★☆ |
1. 两数之和 | easy | ★★★★☆ |
15. 三数之和 | medium | ★★★★☆ |
121. 买卖股票的最佳时机 | easy | ★★★★☆ |
122. 买卖股票的最佳时机 II | easy | ★★★★☆ |
21. 合并两个有序链表 | easy | ★★★★☆ |
53. 最大子序和 | easy | ★★★☆☆ |
236. 二叉树的最近公共祖先 | medium | ★★★☆☆ |
42. 接雨水 | 困难 | ★★★☆☆ |
415. 字符串相加 | easy | ★★★☆☆ |
199. 二叉树的右视图 | medium | ★★★☆☆ |
141. 环形链表 | easy | ★★☆☆☆ |
88. 合并两个有序数组 | easy | ★★☆☆☆ |
20. 有效的括号 | easy | ★★☆☆☆ |
105. 从前序与中序遍历序列构造二叉树 | medium | ★★☆☆☆ |
102. 二叉树的层序遍历 | medium | ★★☆☆☆ |
200. 岛屿数量 | medium | ★★☆☆☆ |
54. 螺旋矩阵 | medium | ★★☆☆☆ |
33. 搜索旋转排序数组 | medium | ★☆☆☆☆ |
142. 环形链表 II | medium | ★☆☆☆☆ |
69. x 的平方根 | easy | ★☆☆☆☆ |
300. 最长递增子序列 | medium | ★☆☆☆☆ |
23. 合并K个升序链表 | 困难 | ★☆☆☆☆ |
56. 合并区间 | medium | ★☆☆☆☆ |
124. 二叉树中的最大路径和 | 困难 | ★☆☆☆☆ |
232. 用栈实现队列 | easy | ★☆☆☆☆ |
46. 全排列 | medium | ★☆☆☆☆ |
155. 最小栈 | easy | ★☆☆☆☆ |
5. 最长回文子串 | medium | ★☆☆☆☆ |
113. 路径总和 II | medium | ★☆☆☆☆ |
143. 重排链表 | medium | ★☆☆☆☆ |
958. 二叉树的完全性检验 | medium | ★☆☆☆☆ |
94. 二叉树的中序遍历 | medium | ★☆☆☆☆ |
41. 缺失的第一个正数 | 困难 | ★☆☆☆☆ |
101. 对称二叉树 | easy | ★☆☆☆☆ |
169. 多数元素 | easy | ★☆☆☆☆ |
70. 爬楼梯 | easy | ★☆☆☆☆ |
240. 搜索二维矩阵 II | medium | ★☆☆☆☆ |
39. 组合总和 | medium | ★☆☆☆☆ |
31. 下一个排列 | medium | ★☆☆☆☆ |
110. 平衡二叉树 | easy | ★☆☆☆☆ |
92. 反转链表 II | easy | ★☆☆☆☆ |
98. 验证二叉搜索树 | medium | ★☆☆☆☆ |
剑指 Offer 22. 链表中倒数第k个节点 | easy | ★☆☆☆☆ |
补充题1. 排序奇升偶降链表 | medium | ★☆☆☆☆ |
112. 路径总和 | easy | ★☆☆☆☆ |
543. 二叉树的直径 | easy | ★☆☆☆☆ |
234. 回文链表 | easy | ★☆☆☆☆ |
83. 删除排序链表中的重复元素 | easy | ★☆☆☆☆ |
230. 二叉搜索树中第K小的元素 | medium | ★☆☆☆☆ |
1143. 最长公共子序列 | medium | ★☆☆☆☆ |
162. 寻找峰值 | medium | ★☆☆☆☆ |
328. 奇偶链表 | medium | ★☆☆☆☆ |
695. 岛屿的最大面积 | medium | ★☆☆☆☆ |
22. 括号生成 | medium | ★☆☆☆☆ |
198. 打家劫舍 | medium | ★☆☆☆☆ |
148. 排序链表 | medium | ★☆☆☆☆ |
32. 最长有效括号 | 困难 | ★☆☆☆☆ |
165. 比较版本号 | medium | ★☆☆☆☆ |
718. 最长重复子数组 | medium | ★☆☆☆☆ |
209. 长度最小的子数组 | medium | ★☆☆☆☆ |
129. 求根节点到叶节点数字之和 | medium | ★☆☆☆☆ |
108. 将有序数组转换为二叉搜索树 | easy | ★☆☆☆☆ |
322. 零钱兑换 | medium | ★☆☆☆☆ |
518. 零钱兑换 II | medium | ★☆☆☆☆ |
1299. 将每个元素替换为右侧最大元素 | easy | ★☆☆☆☆ |
139. 单词拆分 | medium | ★☆☆☆☆ |
67. 二进制求和 | easy | ★☆☆☆☆ |
503. 下一个更大元素 II | medium | ★☆☆☆☆ |
221. 最大正方形 | medium | ★☆☆☆☆ |
560. 和为K的子数组 | medium | ★☆☆☆☆ |
134. 加油站 | medium | ★☆☆☆☆ |
1438. 绝对差不超过限制的最长连续子数组 | medium | ★☆☆☆☆ |
463. 岛屿的周长 | easy | ★☆☆☆☆ |
76. 最小覆盖子串 | 困难 | ★☆☆☆☆ |
1115. 交替打印 FooBar | 中等 | ★☆☆☆☆ |
26. 删除有序数组中的重复项 | easy | ★☆☆☆☆ |
128. 最长连续序列 | 困难 | ★☆☆☆☆ |
297. 二叉树的序列化与反序列化 | 困难 | ★☆☆☆☆ |
51. N 皇后 | 困难 | ★☆☆☆☆ |
207. 课程表 | medium | ★☆☆☆☆ |
739. 每日温度 | medium | ★☆☆☆☆ |
498. 对角线遍历 | medium | ★☆☆☆☆ |
93. 复原 IP 地址 | medium | ★☆☆☆☆ |
补充题2 字符串计算 | medium | ★☆☆☆☆ |
111. 二叉树的最小深度 | easy | ★☆☆☆☆ |
题目描述:给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
思路:滑动窗口
代码实现:时间复杂度:O(n),空间复杂度:O(min(m, n))
public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) { return 0; } int left = 0; int maxLength = 0; Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < s.length(); i++) { if (map.containsKey(s.charAt(i))) { left = Math.max(map.get(s.charAt(i)) + 1, left); } maxLength = Math.max(maxLength, i - left + 1); map.put(s.charAt(i), i); } return maxLength; }
题目描述:反转一个单链表。
思路:递归或迭代
代码实现:
public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode pre = null; while (head != null) { ListNode tmp = head.next; head.next = pre; pre = head; head = tmp; } return pre; }
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = reverseList(head.next);
head.next.next = head;
head.next = null;
return pre;
}
题目描述:(hard)给出一个链表,每 k个节点一组进行翻转,并返回翻转后的链表。
思路:三种解法:借用栈实现、尾插法或递归。
代码实现:时间复杂度:O(n),空间复杂度:O(n)
public ListNode reverseKGroup(ListNode head, int k) { if (head == null || head.next == null || k < 1) { return head; } ListNode pre = head; int count = 0; while (pre != null && count < k) { pre = pre.next; count++; } if (count == k) { pre = reverseKGroup(pre, k); while (count > 0) { count--; ListNode tmp = head.next; head.next = pre; pre = head; head = tmp; } head = pre; } return head; }
题目描述:在未排序的数组中找到第 k 个最大的元素。
思路:基于快速排序的选择方法,保证基准值左边的元素都小于基准值,优化点:基准下标取随机值。也可使用大顶堆解法。
代码实现:时间复杂度:O(n),空间复杂度:O(log n)
public int findKthLargest(int[] nums, int k) { if (nums == null || nums.length == 0 || k < 1) { return 0; } return this.quickSelect(nums, 0, nums.length - 1, nums.length - k); } public int quickSelect(int[] nums, int left, int right, int target) { int mid = randomPartition(nums, left, right); if (mid == target) { return nums[mid]; } if (mid < target) { left = mid + 1; } else { right = mid - 1; } return quickSelect(nums, left, right, target); } public int randomPartition(int[] nums, int left, int right) { int i = left, pivotVal = nums[right]; for (int j = left; j < right; j++) { if (nums[j] < pivotVal) { swap(nums, i++, j); } } swap(nums, i, right); return i; } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
题目描述:给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
思路:BFS,利用标志位记录应该从左往右还是从右往左遍历。
代码实现:时间复杂度:O(n),空间复杂度:O(n)
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> stack = new LinkedList<>(); stack.add(root); boolean flag = true; while (!stack.isEmpty()) { int size = stack.size(); LinkedList<Integer> list = new LinkedList<>(); for (int i = 0; i < size; i++) { TreeNode tmp = stack.poll(); if (flag) { list.addLast(tmp.val); } else { list.addFirst(tmp.val); } if (tmp.left != null) { stack.add(tmp.left); } if (tmp.right != null) { stack.add(tmp.right); } } flag = !flag; res.add(list); } return res; }
题目描述:找到两个单链表相交的起始节点。
思路:双指针,依次往后遍历,末尾更换链表继续遍历,比较长的链表指针指向较短链表head时,长度差消除。
代码实现:时间复杂度:O(n),空间复杂度:O(1)
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA;
ListNode pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
题目描述:实现一个 LRU (最近最少使用) 缓存机制
思路:通过哈希表+双向链表实现,将访问到key移动到双向链表的头部,put时当前大小如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的key;将一个节点移到双向链表的头部,可以分成「删除该节点」和「在双向链表的头部添加节点」两步,都可以在 O(1)时间内完成。
代码实现:时间复杂度:O(1),空间复杂度:O(capacity)
public class ListNode { int key; int val; ListNode pre; ListNode next; ListNode () { } ListNode (int key, int val) { this.key = key; this.val = val; } } Map<Integer, ListNode> cache = new HashMap<>(); // 数组大小 private int size; // 数组容量 private int capacity; // 头结点 private ListNode head; // 尾结点 private ListNode tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; this.head = new ListNode(); this.tail = new ListNode(); head.next = tail; tail.pre = head; } public int get(int key) { if (!cache.containsKey(key) ) { return -1; } ListNode node = cache.get(key); moveToHead(node); return node.val; } public void put(int key, int value) { if (cache.containsKey(key)) { ListNode node = cache.get(key); node.val = value; moveToHead(node); return; } ListNode newNode = new ListNode(key, value); cache.put(key, newNode); ++size; addToHead(newNode); if (size > capacity) { ListNode deleteNode = removeTailNode(); cache.remove(deleteNode.key); --size; } } private void moveToHead(ListNode node) { removeNode(node); addToHead(node); } private void removeNode(ListNode node) { node.pre.next = node.next; node.next.pre = node.pre; } private void addToHead(ListNode node) { node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; } private ListNode removeTailNode() { ListNode node = tail.pre; removeNode(node); return node; }
题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
思路:一遍哈希表
代码实现:时间复杂度:O(n),空间复杂度:O(n)
public int[] twoSum(int[] nums, int target) { if (nums == null || nums.length == 0) { return null; } Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int num = target - nums[i]; if (map.containsKey(num)) { return new int[]{ i, map.get(num)}; } map.put(nums[i], i); } return null; }
题目描述:给定一个包含n个整数的数组nums,判断nums中是否存在三个元素a、b、c,使得 a+b+c=0。找出所有满足条件且不重复的三元组。
思路:排序 + 双指针,每次循环过滤重复的元素。
代码实现:时间复杂度:O(n²),空间复杂度:O(logN),排序需要额外的空间
public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); if (nums == null || nums.length == 0) { return res; } Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (i != 0 && nums[i] == nums[i-1]) { continue; } int j = i + 1; int k = nums.length - 1; while (j < k) { if (j != i + 1 && nums[j] == nums[j-1]) { j++; continue; } int target = nums[i] + nums[j] + nums[k]; if (target == 0) { res.add(Arrays.asList(nums[i], nums[j], nums[k])); j++; k--; } else if (target > 0) { k--; } else { j++; } } } return res; }
题目描述:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。注意:你不能在买入股票前卖出股票。
思路:获取最大利润。
代码实现:时间复杂度:O(n),空间复杂度:O(1)
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for (int i = 0; i < prices.length; i++) { minPrice = Math.min(prices[i], minPrice); maxProfit = Math.max(prices[i] - minPrice, maxProfit); } return maxProfit; }
题目描述:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
思路:动态规划,卖出dp0,买入dp1。或贪心算法
代码实现:时间复杂度:O(n),空间复杂度:O(1)
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int res = 0;
for (int i = 1; i < prices.length; i++) {
res += Math.max(0, prices[i] - prices[i - 1]);
}
return res;
}
题目描述:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:迭代或递归。如果 l1 或者 l2 一开始就是 null ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1 和 l2 哪一个的头元素更小,然后递归地决定下一个添加到结果里的值。
代码实现:递归,时间复杂度:O(m+n),空间复杂度:O(m+n)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } ListNode newHead; if (l1.val < l2.val) { newHead = l1; newHead.next = mergeTwoLists(l1.next, l2); } else { newHead = l2; newHead.next = mergeTwoLists(l1, l2.next); } return newHead; }
题目描述:给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
思路:动态规划。
代码实现:时间复杂度:O(n),空间复杂度:O(1)
public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int sum = 0; int res = nums[0]; for (int i = 0; i < nums.length; i++) { sum = Math.max(sum + nums[i], nums[i]); res = Math.max(res, sum); } return res; }
题目描述:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。一个节点也可以是它自己的祖先。
思路:通过递归对二叉树进行后序遍历,当遇到节点 p 或 q 时返回。从底至顶回溯,当节点 p, q在节点 root 的异侧时,节点 root 即为最近公共祖先,则向上返回 root 。
代码实现:时间复杂度:O(n),空间复杂度:O(n)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p ,q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left == null) { return right; } if (right == null) { return left; } if (left == null && right == null) { return null; } return root; }
题目描述:给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
思路: 双指针法,若height[left]<height[right],则必有leftMax < rightMax,下标 left 处能接的雨水量等于 leftMax−height[left],将下标 left 处能接的雨水量加到能接的雨水总量,然后将 left 加 1;
代码实现:时间复杂度:O(n),空间复杂度:O(1)
public int trap(int[] height) { if (height == null || height.length == 0) { return 0; } int sum = 0; int left = 0, right = height.length - 1; int leftMax = 0, rigthMax = 0; while (left < right) { leftMax = Math.max(height[left], leftMax); rigthMax = Math.max(height[right], rigthMax); if (height[left] < height[right]) { sum += leftMax - height[left]; left++; } else { sum += rigthMax - height[right]; right--; } } return sum; }
题目描述:给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
思路:定义两个指针 i 和 j 分别指向 num1 和 num2 的末尾,即最低位,同时定义一个变量 add 维护当前是否有进位,然后从末尾到开头逐位相加。指针当前下标处于负数的时候返回 0,等价于对位数较短的数字进行了补零操作。
代码实现:时间复杂度:O(n),空间复杂度:O(n),因为使用了StringBuilder
public String addStrings(String num1, String num2) {
if (num1 == null || num1.length() == 0<
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。