#
leetcode 标签

42. Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 思路： 题目意思是给定一个数组，数值代表了高度，求解可以装多少水，仔细分析可以发现，对于任意一位能存储多少水是取....
11. Container With Most Water Given n non-negative integers a1, a2, …, _an _, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. **Note: **You may not slant the container and n is at least 2. Example: Input: [1,8,6,....
219、Contains Duplicate II Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k. Example 1: Input: nums = [1,2,3,1], k = 3 Output: true Example 2: Input: nums = [1,0,1,1], k = 1 Output: true 思路： 这题是217题的变形，多加了在k范围内重复才返回true，思路也是使用map来做，遍历的同时查重，时间复杂度O(N),空间复杂度为O(N),使用滑动窗口的思想可以优化空间....
41、First Missing Positive Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. 思路： 寻找消失的正数，使用桶排序的思想，对数组排完序之后，比对对应位置与位置上的值，就能找出结果。 代码： java： class Solution { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length <= 0) return 1; // 1. sort fo....
189、Rotate Array Given an array, rotate the array to the right by k steps, where k is non-negative. Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] 思路： 翻转数组有很多种做法，这里就只说一种 time:O(n) space:O(1),思路就是经过三次翻转数组，达到只翻转到k的目的。 代码： java: class Solution { public void rotate(int[] nums, int k) { k= k % nums.length; reve....
80、Remove Duplicates from Sorted Array II 相似题型： 26 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example 1: Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. ....