题目描述 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 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 。 解法 动态规划写法 public int rob(int[] nums) { int length = nums.length; if (length <=0) { return 0; } if (length < 2) {....
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。 找到所有在 [1, n] 范围之间没有出现在数组中的数字。 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。 示例: 输入: [4,3,2,7,8,2,3,1] 输出: [5,6] 解法 遍历每个元素，对索引进行标记 将对应索引位置的值变为负数； 遍历下索引，看看哪些索引位置上的数不是负数的。 位置上不是负数的索引，对应的元素就是不存在的。 public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> res = new ArrayList<>(); for(int num: nums) { int index = Math.abs(num) - 1; if (nums[index] > 0) { nums[index] = nums[index] ....
题目 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 解法 利用hash表记录每个元素出现的次数，维护一个k大的优先队列， 优先队列中维护每个元素及出现次数，根据出现次数排序，取前K个即可。 public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> countMap = new HashMap<>(); for(int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1); } PriorityQueue<int []> queue = new PriorityQueue<>(new Comparator<int []>() { public int co....
题目描述 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 解题 排序后取第k大值 public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; } 利用堆排序 public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> queue = new PriorityQueue<>(); for(int i=0; i<nums.length; i++) { queue.add(nums[i]); if (queue.size() > k) { queue.poll(); } } return queu....
题目描述： 给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例： 输入：head = 1->4->3->2->5->2, x = 3 输出：1->2->2->4->3->5 解法： 只需要遍历链表的所有节点，小于x的放到一个小的链表中，大于等于x的放到一个大的链表中，最后再把这两个链表串起来即可。 代码 public ListNode partition(ListNode head, int x) { //小链表的头 ListNode smallHead = new ListNode(0); //大链表的头 ListNode bigHead = new ListNode(0); //小链表的尾 ListNode smallTail = smallHead; //大链表的尾 ListNode bigTail = bigHead; //遍历head链表 while (head != null) { i....
题目描述 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。 示例 1： 输入：s = "3[a]2[bc]" 输出："aaabcbc" 示例 2： 输入：s = "3[a2[c]]" 输出："accaccacc" 示例 3： 输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef" 示例 4： 输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz" 解法： 字符串有多层嵌套的情况，利用栈解决。使用两个栈，一个数字栈，一个字符串栈 public String decodeString(String s) { StringBuilde....