文章 224
评论 11
浏览 167375
Array - 209. Minimum Size Subarray Sum

Array - 209. Minimum Size Subarray Sum

209. Minimum Size Subarray Sum Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead. **Example: ** Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint. Follow up: If you have figured out the O(n) solution, try coding another solution of which the time compl....

Array - 53. Maximum Subarray

Array - 53. Maximum Subarray

53. Maximum Subarray Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. 思路: 找出数组中最大字串和,使用动态规划求解,转移方程是:f[i] = f[i-1] > 0 ? nums[i] + f[i-1] : nums....

Array - 295. Find Median from Data Stream

Array - 295. Find Median from Data Stream

295. Find Median from Data Stream Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For example, [2,3,4], the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all eleme....

Array - 11. Container With Most Water

Array - 11. Container With Most Water

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,....

Array - 45. Jump Game II

Array - 45. Jump Game II

45、Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. Example: Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index. Note: You can assume that you can always reach the last in....

Array - 41. First Missing Positive

Array - 41. First Missing Positive

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....

Array - 27. Remove Element

Array - 27. Remove Element

27、 Remove Element 相似题型:83(list), 26,80 Given an array nums and a value val, remove all instances of that value in-place 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. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. Example 1: Given _nums_ = [3,2,2,3], _val_ = 3, Your function should return length = 2, with....

Array - 26. Remove Duplicates from Sorted Array

Array - 26. Remove Duplicates from Sorted Array

26、Remove Duplicates from Sorted Array 相似题型:83(list), 26,80 Given a sorted array nums, remove the duplicates in-place such that each element appear only once 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,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't m....

关于leetcode刷题顺序和刷题思路的声明

关于leetcode刷题顺序和刷题思路的声明

1. 刷题顺序:我leetcode的刷题顺序是根据刷题3000题的Edward老师在Youtube上的视频推荐的400题基础来刷的。 该老师有自己的网站和全程课(因为YouTube上老师只开放了50题,后面的要付费),网址:https://cspiration.com 。如果有需要购买全程课的同学可以去加老师他的微信去买全程课。 2. 代码及思路:因为Edward老师的视频在YouTube上只开放了前50,我又没买课,所以后面的有些题目思路还参考学习了花花酱老师和花嫂的视频。还有就是参考国内的博客和leetcode的Discuss。 花花酱老师的YouTube:https://www.youtube.com/user/xxfflower Edward老师的YouTube:https://www.youtube.com/channel/UCTWuRL33U8xBPqk3LehXjFw

Array - 239. Sliding Window Maximum

Array - 239. Sliding Window Maximum

239. Sliding Window Maximum Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the _k_numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 ** 5** 1 3 -....

Array - 164. Maximum Gap

Array - 164. Maximum Gap

164. Maximum Gap Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either   (3,6) or (6,9) has the maximum difference 3. Example 2: Input: [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0. Note: You may assume all elements in the array are non-....

Array - 128. Longest Consecutive Sequence

Array - 128. Longest Consecutive Sequence

128. Longest Consecutive Sequence Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. 思路: 题目提示必须跑在O(n),可以使用set或者map来做,就是online和offline,offline非常简单直接,就是利用set的O(1)操作来解。 代码: java: class Solution { // online public int longestConsecutive(int[] nums)....

Array - 334. Increasing Triplet Subsequence

Array - 334. Increasing Triplet Subsequence

334. Increasing Triplet Subsequence Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists _i, j, k _ such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. **Note: **Your algorithm should run in O(n) time complexity and O(1) space complexity. Example 1: Input: [1,2,....

Array - 123. Best Time to Buy and Sell Stock III

Array - 123. Best Time to Buy and Sell Stock III

123. Best Time to Buy and Sell Stock III Say you have an array for which the _i_th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. **Note: **You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1: Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), pr....

Array - 122. Best Time to Buy and Sell Stock II

Array - 122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II Say you have an array for which the _i_th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1: Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on....

Array - 121. Best Time to Buy and Sell Stock

Array - 121. Best Time to Buy and Sell Stock

Say you have an array for which the _i_th element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. Example 1: Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.   Not 7-1 = 6, as selling price needs to be la....

Array - 220. Contains Duplicate III

Array - 220. Contains Duplicate III

220、 Contains Duplicate III Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k. Example 1: Input: nums = [1,2,3,1], k = 3, t = 0 Output: true 思路: 这道题是217和219的变形题,题意是说有一个整数数组,如果数组中有两个数的差在t内,并且这两个数的索引之差在k内,就返回true否则返回fals....

Array - 219. Contains Duplicate II

Array - 219. Contains Duplicate II

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),使用滑动窗口的思想可以优化空间....

Array - 217. Contains Duplicate

Array - 217. Contains Duplicate

217、Contains Duplicate Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. Example 1: Input: [1,2,3,1] Output: true Example 2: Input: [1,2,3,4] Output: false 思路: 很简单的一题,只用找出数组中有没有重复的数字,用set或者map做就可以。 代码: java: class Solution { public boolean containsDuplicate(int[] nums) { return IntStream.of(nums).distinct().count() != nums.length; ....

Array - 299. Bulls and Cows

Array - 299. Bulls and Cows

299、Bulls and Cows You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to event....

Nothing just happens, it's all part of a plan.