LeetCode 146 LRU缓存
标题详情
运用你所掌握的数据结构，计划和实现一个 LRU (近来最少使用) 缓存机制。它应该支持以下操纵： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 假如关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 假如关键字已经存在，则变动其数据值；假如关键字不存在，则插入该组「关键字/值」。当缓存容量到达上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
函数 get 和 put 必须以 O(1) 的均匀时间复杂度运行。
进阶:
你是否可以在O(1) 时间复杂度内完成这两种操纵？
示例:
LRUCache cache = new LRUCache( 2 ); //2为缓存容量 cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操纵会使得关键字 2 取消 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操纵会使得关键字 1 取消 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4代码
public class LeetCode146 { /* 计划类 */ public static void main(String[] args) { } /* 实现本题的两种操纵，需要用到一个哈希表和一个双向链表。在口试中，口试官一般会渴望读者可以大概自己实现一个简朴的双向链表，而不是使用语言自带的、封装好的数据结构。 在 Python 语言中，有一种联合了哈希表与双向链表的数据结构 OrderedDict，只需要短短的几行代码就可以完本钱题。 在 Java 语言中，同样有雷同的数据结构 LinkedHashMap。这些做法都不会符合口试官的要求，因此下面只给出使用封装好的数据结构实现的代码，而不多做任何阐述。 */ static class LRUCache extends LinkedHashMap<Integer, Integer> { private int capacity; public LRUCache(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity; } } /* LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护全部在缓存中的键值对。双向链表按照被使用的序次存储了这些键值对，靠近头部的键值对是近来使用的，而靠近尾部的键值对是最久未使用的。哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。这样以来，我们首先使用哈希表举行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)O(1) 的时间内完成 get 大概 put 操纵。具体的方法如下： */ public class CLRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() { } public DLinkedNode(int _key, int _value) { key = _key; value = _value; } } private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>(); private int size; private int capacity; private DLinkedNode head, tail; public CLRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 假如 key 存在，先通过哈希表定位，再移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // 假如 key 不存在，创建一个新的节点 DLinkedNode newNode = new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); ++size; if (size > capacity) { // 假如超出容量，删除双向链表的尾部节点 DLinkedNode tail = removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } } else { // 假如 key 存在，先通过哈希表定位，再修改 value，并移到头部 node.value = value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; } }}LeetCode148 排序链表
标题详情
给你链表的头结点 head ，请将其按 升序 分列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数量在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表举行排序吗？
代码
class LeetCode148 { public static void main(String[] args) { ListNode.printNode(new Solution1().sortList(ListNode.buildNode(new int[]{3, 2, 0, -4}))); ListNode.printNode(new Solution2().sortList(ListNode.buildNode(new int[]{3, 2, 0, -4}))); } /* 解答一：归并排序（递归法） */ static class Solution1 { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode fast = head.next, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode tmp = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(tmp); ListNode h = new ListNode(0); ListNode res = h; while (left != null && right != null) { if (left.val < right.val) { h.next = left; left = left.next; } else { h.next = right; right = right.next; } h = h.next; } h.next = left != null ? left : right; return res.next; } } static class Solution2 { public ListNode sortList(ListNode head) { // 1、递归竣事条件 if (head == null || head.next == null) { return head; } // 2、找到链表中心节点并断开链表 & 递归下探 ListNode midNode = middleNode(head); ListNode rightHead = midNode.next; midNode.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); // 3、当前层业务操纵（归并有序链表） return mergeTwoLists(left, right); } // 找到链表中心节点（876. 链表的中心结点） private ListNode middleNode(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 归并两个有序链表（21. 归并两个有序链表） private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode sentry = new ListNode(-1); ListNode curr = sentry; while (l1 != null && l2 != null) { if (l1.val < l2.val) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; } curr.next = l1 != null ? l1 : l2; return sentry.next; } }}LeetCode152 乘积最大子数组
标题详情
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包罗一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
表明: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
表明: 效果不能为 2, 由于 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104
-10 <= nums <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
代码
public class LeetCode152 { public static void main(String[] args) { System.out.println(new Solution().maxProduct(new int[]{2, 3, -2, 4})); System.out.println(new Solution2().maxProduct(new int[]{2, 3, -2, 4})); } /* 暴力解法 */ static class Solution { public int maxProduct(int[] nums) { //思绪：暴力穷举全部子数组，然后得出最大值 int len = nums.length; if (len == 0) { return 0; } long max = Long.MIN_VALUE; for (int i = 0; i < len; i++) { int numCount = 1; for (int j = i; j < len; j++) { numCount *= nums[j]; max = Math.max(numCount, max); } } return (int) max; } } /* 动态规划 */ static class Solution2 { public int maxProduct(int[] nums) { int[] maxF = new int[nums.length]; int[] minF = new int[nums.length]; maxF[0] = nums[0]; minF[0] = nums[0]; int ans = nums[0]; for (int i = 1; i < nums.length; ++i) { maxF = Math.max(maxF[i - 1] * nums, Math.max(nums, minF[i - 1] * nums)); minF = Math.min(minF[i - 1] * nums, Math.min(nums, maxF[i - 1] * nums)); ans = Math.max(ans, maxF); } return ans; } }}LeetCode155 最小栈
标题详情
计划一个支持 push ，pop ，top 操纵，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
表明：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1
pop、top 和 getMin 操纵总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
代码
public class LeetCode155 { public static void main(String[] args) { MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); minStack.pop(); minStack.top(); minStack.getMin(); } static class MinStack { // 数据栈 private Stack<Integer> data; // 辅助栈 private Stack<Integer> helper; /* 在这里初始化你的数据结构。 */ public MinStack() { data = new Stack<>(); helper = new Stack<>(); } // 思绪 1：数据栈和辅助栈在任何时间都同步 public void push(int x) { // 数据栈和辅助栈肯定会增加元素 data.add(x); if (helper.isEmpty() || helper.peek() >= x) { helper.add(x); } else { helper.add(helper.peek()); } } public void pop() { // 两个栈都得 pop if (!data.isEmpty()) { helper.pop(); data.pop(); } } public int top() { if (!data.isEmpty()) { return data.peek(); } throw new RuntimeException("栈中元素为空，此操纵非法"); } public int getMin() { if (!helper.isEmpty()) { return helper.peek(); } throw new RuntimeException("栈中元素为空，此操纵非法"); } }}LeetCode160 相交链表
标题详情
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。假如两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
标题数据 保证 整个链式结构中不存在环。
注意，函数返回效果后，链表必须 保持其原始结构 。
自界说评测：
评测体系 的输入如下（你计划的步伐 不实用 此输入）：
intersectVal - 相交的起始节点的值。假如不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（重新节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（重新节点开始）跳到交叉节点的节点数
评测体系将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 通报给你的步伐。假如步伐可以大概精确返回相交节点，那么你的办理方案将被 视作精确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
表明：相交节点的值为 8 （注意，假如两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
表明：相交节点的值为 2 （注意，假如两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
表明：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，以是 intersectVal 必须为 0，而 skipA 和 skipB 可以是恣意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数量为 m
listB 中节点数量为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
假如 listA 和 listB 没有交点，intersectVal 为 0
假如 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你可否计划一个时间复杂度 O(m + n) 、仅用 O(1) 内存的办理方案？
代码
public class LeetCode160 { public static void main(String[] args) { ListNode.printNode(new Solution().getIntersectionNode(ListNode.buildNode(new int[]{4, 1, 8, 4, 5}), ListNode.buildNode(new int[]{5, 0, 1, 8, 4, 5}))); ListNode.printNode(new Solution2().getIntersectionNode(ListNode.buildNode(new int[]{4, 1, 8, 4, 5}), ListNode.buildNode(new int[]{5, 0, 1, 8, 4, 5}))); } /* 双指针 */ static class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { /* 界说两个指针, 第一轮让两个到达末端的节点指向另一个链表的头部, 末了假如相遇则为交点(在第一轮移动中恰好抹除了长度差) 两个指针即是移动了雷同的隔断, 有交点就返回, 无交点就是各走了两条指针的长度 **/ if (headA == null || headB == null) return null; ListNode pA = headA, pB = headB; // 在这里第一轮体如今pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体如今假如pA或pB相交就返回交点, 不相交末了就是null==null while (pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } } /* 哈希聚集 */ static class Solution2 { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> visited = new HashSet<ListNode>(); ListNode temp = headA; while (temp != null) { visited.add(temp); temp = temp.next; } temp = headB; while (temp != null) { if (visited.contains(temp)) { return temp; } temp = temp.next; } return null; } }}LeetCode169 多数元素
标题详情
给定一个巨细为 n 的数组 nums ，返回此中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组黑白空的，而且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums <= 109
进阶：实行计划时间复杂度为 O(n)、空间复杂度为 O(1) 的算法办理此题目。
代码
public class LeetCode169 { public static void main(String[] args) { System.out.println(new Solution().majorityElement(new int[]{1, 7, 7, 2, 7, 3, 7, 4, 7, 5, 7})); System.out.println(new Solution2().majorityElement(new int[]{1, 7, 7, 2, 7, 3, 7, 4, 7, 5, 7})); System.out.println(new Solution3().majorityElement(new int[]{1, 7, 7, 2, 7, 3, 7, 4, 7, 5, 7})); } static class Solution { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length / 2]; } } static class Solution2 { private Map<Integer, Integer> countNums(int[] nums) { Map<Integer, Integer> counts = new HashMap<Integer, Integer>(); for (int num : nums) { if (!counts.containsKey(num)) { counts.put(num, 1); } else { counts.put(num, counts.get(num) + 1); } } return counts; } public int majorityElement(int[] nums) { Map<Integer, Integer> counts = countNums(nums); Map.Entry<Integer, Integer> majorityEntry = null; for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) { majorityEntry = entry; } } return majorityEntry.getKey(); } } /* 投票法 假如候选人不是maj 则 maj,会和其他非候选人一起反对 会反对候选人,以是候选人肯定会下台(maj==0时发生换届推举) 假如候选人是maj , 则maj 会支持自己，其他候选人会反对，同样由于maj 票数凌驾一半，以是maj 肯定会乐成当选 */ static class Solution3 { public int majorityElement(int[] nums) { int count = 0; Integer candidate = null; for (int num : nums) { if (count == 0) { candidate = num; } count += (num == candidate) ? 1 : -1; } return candidate; } }}LeetCode198 打家劫舍
标题详情
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有肯定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗体系，假如两间相邻的房屋在同一晚上被小偷突入，体系会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，盘算你 不触动警报装置的环境下 ，一夜之内可以大概偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
表明：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
表明：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums <= 400
代码
public class LeetCode198 { public static void main(String[] args) { System.out.println(new Solution().rob(new int[]{3, 3, 24, 5, 2, 1, 9})); System.out.println(new Solution2().rob(new int[]{3, 3, 24, 5, 2, 1, 9})); System.out.println(new Solution3().rob(new int[]{3, 3, 24, 5, 2, 1, 9})); System.out.println(new Solution4().rob(new int[]{3, 3, 24, 5, 2, 1, 9})); } static class Solution { public int rob(int[] nums) { int prevMax = 0; int currMax = 0; for (int x : nums) { int temp = currMax; currMax = Math.max(prevMax + x, currMax); prevMax = temp; } return currMax; } } /* 动态规划 */ static class Solution2 { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int[] dp = new int[length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp = Math.max(dp[i - 2] + nums, dp[i - 1]); } return dp[length - 1]; } } static class Solution3 { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int first = nums[0], second = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { int temp = second; second = Math.max(first + nums, second); first = temp; } return second; } } static class Solution4 { public int rob(int[] nums) { int pre = 0, cur = 0, tmp; for (int num : nums) { tmp = cur; cur = Math.max(pre + num, cur); pre = tmp; } return cur; } }}LeetCode200 岛屿数量
标题详情
给你一个由 '1'（陆地）和 '0'（水）构成的的二维网格，请你盘算网格中岛屿的数量。
岛屿总是被水困绕，而且每座岛屿只能由程度方向和/或竖直方向上相邻的陆地毗连形成。
别的，你可以假设该网格的四条边均被水困绕。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.length
n == grid.length
1 <= m, n <= 300
grid[j] 的值为 '0' 或 '1'
代码
public class LeetCode200 { public static void main(String[] args) { char[][] grid1 = { {'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'} }; System.out.println(new Solution().numIslands(grid1)); char[][] grid2 = { {'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'} }; System.out.println(new Solution2().numIslands(grid2)); } /* 广度优先搜刮同样地，我们也可以使用广度优先搜刮代替深度优先搜刮。为了求出岛屿的数量，我们可以扫描整个二维网格。假如一个位置为 11，则将其到场队列，开始举行广度优先搜刮。在广度优先搜刮的过程中，每个搜刮到的 11 都会被重新标志为 00。直到队列为空，搜刮竣事。终极岛屿的数量就是我们举行广度优先搜刮的次数。 */ static class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int nr = grid.length; int nc = grid[0].length; int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; grid[r][c] = '0'; Queue<Integer> neighbors = new LinkedList<>(); neighbors.add(r * nc + c); while (!neighbors.isEmpty()) { int id = neighbors.remove(); int row = id / nc; int col = id % nc; if (row - 1 >= 0 && grid[row - 1][col] == '1') { neighbors.add((row - 1) * nc + col); grid[row - 1][col] = '0'; } if (row + 1 < nr && grid[row + 1][col] == '1') { neighbors.add((row + 1) * nc + col); grid[row + 1][col] = '0'; } if (col - 1 >= 0 && grid[row][col - 1] == '1') { neighbors.add(row * nc + col - 1); grid[row][col - 1] = '0'; } if (col + 1 < nc && grid[row][col + 1] == '1') { neighbors.add(row * nc + col + 1); grid[row][col + 1] = '0'; } } } } } return num_islands; } } static class Solution2 { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int nr = grid.length; int nc = grid[0].length; int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; dfs(grid, r, c); } } } return num_islands; } /* 深度优先 */ void dfs(char[][] grid, int r, int c) { int nr = grid.length; int nc = grid[0].length; if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') { return; } grid[r][c] = '0'; dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1); } }}LeetCode206 反转链表
标题详情
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数量范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你可否用两种方法办理这道题？
代码
public class LeetCode206 { public static void main(String[] args) { ListNode.printNode(new Solution().reverseList(ListNode.buildNode(new int[]{1,2,3,4,5}))); ListNode.printNode(new Solution2().reverseList(ListNode.buildNode(new int[]{1,2,3,4,5}))); } /* 迭代 */ static class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) return head; ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; } } /* 循环 */ static class Solution2 { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } }}LeetCode207 课程表
标题详情
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，此中 prerequisites = [ai, bi] ，表现假如要学习课程 ai 则 必须 先学习课程 bi 。
比方，先修课程对 [0, 1] 表现：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否大概完成全部课程的学习？假如可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
表明：统共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是大概的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
表明：统共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；而且学习课程 0 之前，你还应先完成课程 1 。这是不大概的。
提示：
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites.length == 2
0 <= ai, bi < numCourses
prerequisites 中的全部课程对 互不雷同
代码
public class LeetCode207 { public static void main(String[] args) { System.out.println(new Solution().canFinish(2, new int[][]{{1, 0}, {0, 1}})); System.out.println(new Solution2().canFinish(2, new int[][]{{1, 0}, {0, 1}})); } /* 深度优先 */ static class Solution { List<List<Integer>> edges; int[] visited; boolean valid = true; public boolean canFinish(int numCourses, int[][] prerequisites) { edges = new ArrayList<List<Integer>>(); for (int i = 0; i < numCourses; ++i) { edges.add(new ArrayList<Integer>()); } visited = new int[numCourses]; for (int[] info : prerequisites) { edges.get(info[1]).add(info[0]); } for (int i = 0; i < numCourses && valid; ++i) { if (visited == 0) { dfs(i); } } return valid; } public void dfs(int u) { visited = 1; for (int v : edges.get(u)) { if (visited[v] == 0) { dfs(v); if (!valid) { return; } } else if (visited[v] == 1) { valid = false; return; } } visited = 2; } } /* 广度优先 */ static class Solution2 { List<List<Integer>> edges; int[] indeg; public boolean canFinish(int numCourses, int[][] prerequisites) { edges = new ArrayList<List<Integer>>(); for (int i = 0; i < numCourses; ++i) { edges.add(new ArrayList<Integer>()); } indeg = new int[numCourses]; for (int[] info : prerequisites) { edges.get(info[1]).add(info[0]); ++indeg[info[0]]; } Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < numCourses; ++i) { if (indeg == 0) { queue.offer(i); } } int visited = 0; while (!queue.isEmpty()) { ++visited; int u = queue.poll(); for (int v : edges.get(u)) { --indeg[v]; if (indeg[v] == 0) { queue.offer(v); } } } return visited == numCourses; } }}LeetCode208 实现Trie树（前缀树）
标题详情
Trie（发音雷同 "try"）大概说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据会合的键。这一数据结构有相当多的应用景象，比方自动补完和拼写查抄。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 假如字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 假如之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
表明
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英笔墨母构成
insert、search 和 startsWith 调用次数 总计 不凌驾 3 * 104 次
代码
public class LeetCode208 { public static void main(String[] args) { Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True Trie2 trie2 = new Trie2(); trie2.insert("apple"); trie2.search("apple"); // 返回 True trie2.search("app"); // 返回 False trie2.startsWith("app"); // 返回 True trie2.insert("app"); trie2.search("app"); // 返回 True } static class Trie { private boolean is_string = false; private Trie next[] = new Trie[26]; public Trie() { } public void insert(String word) {//插入单词 Trie root = this; char w[] = word.toCharArray(); for (int i = 0; i < w.length; ++i) { if (root.next[w - 'a'] == null) root.next[w - 'a'] = new Trie(); root = root.next[w - 'a']; } root.is_string = true; } public boolean search(String word) {//查找单词 Trie root = this; char w[] = word.toCharArray(); for (int i = 0; i < w.length; ++i) { if (root.next[w - 'a'] == null) return false; root = root.next[w - 'a']; } return root.is_string; } public boolean startsWith(String prefix) {//查找前缀 Trie root = this; char p[] = prefix.toCharArray(); for (int i = 0; i < p.length; ++i) { if (root.next[p - 'a'] == null) return false; root = root.next[p - 'a']; } return true; } } static class Trie2 { private Trie2[] children; private boolean isEnd; public Trie2() { children = new Trie2[26]; isEnd = false; } public void insert(String word) { Trie2 node = this; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { node.children[index] = new Trie2(); } node = node.children[index]; } node.isEnd = true; } public boolean search(String word) { Trie2 node = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private Trie2 searchPrefix(String prefix) { Trie2 node = this; for (int i = 0; i < prefix.length(); i++) { char ch = prefix.charAt(i); int index = ch - 'a'; if (node.children[index] == null) { return null; } node = node.children[index]; } return node; } }} |
