文章 224
评论 6
浏览 200761
String - 58. Length of Last Word

String - 58. Length of Last Word

58. Length of Last Word Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. Examples: s = “leetcode” return 0. s = “loveleetcode”, return 2. Note: You may assume the string contain only lowercase letters. 思路: 找出第一个不重复出现的字母,这题最容易想到的是用一个map记录下每个字母出现的次数,然后根据map去寻找只出现一次的字母的索引。这样做的时间消耗太多,采用另一种思路:题目中的字母默认只会有小写字母,那就可以以a - z来遍历字符串,如果第一次出现的索引下标和最后一次相同,就是结果,然后记录这其中下标最小的。 代码: java: class Solution { /*public int firstUniqChar(Stri....

String - 14. Longest Common Prefix

String - 14. Longest Common Prefix

14. Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: [“flower”,“flow”,“flight”] Output: “fl” Example 2: Input: [“dog”,“racecar”,“car”] Output: "" Explanation: There is no common prefix among the input strings. Note: All given inputs are in lowercase letters a-z. 思路: leetcode 一共有四种解法,这里就只写第一种,就是以一个string为标准,不断的调用api接口判断子串是否在字符串开头(注意,这一题只用判断从索引为....

String - 28. Implement strStr()

String - 28. Implement strStr()

28. Implement strStr() Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = “hello”, needle = “ll” Output: 2 Example 2: Input: haystack = “aaaaa”, needle = “bba” Output: -1 Clarification: What should we return when needle is an empty string? This is a great question to ask during an interview. For the purpose of this problem, we will return 0 when needle&nbs....

Array - 508. Wiggle Sort

Array - 508. Wiggle Sort

508. Wiggle Sort Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3].... Example Example 1: Input: [3, 5, 2, 1, 6, 4] Output: [1, 6, 2, 5, 3, 4] Explanation: This question may have multiple answers, and [2, 6, 1, 5, 3, 4] is also ok. Example 2: Input: [1, 2, 3, 4] Output: [2, 1, 4, 3] Notice Please complete the problem in-place. 思路: 仔细分析输出数组,可以发现下标索引为奇数的数是极大值点,下标索引是偶数的是极小值点,只要遍历数组的时候,移动相邻两个数,就可以。 代码: java: public c....

Array - 376. Wiggle Subsequence

Array - 376. Wiggle Subsequence

376. Wiggle Subsequence A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence. For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,....

Array - 283. Move Zeroes

Array - 283. Move Zeroes

283. Move Zeroes Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements. Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0] Note: You must do this in-place without making a copy of the array. Minimize the total number of operations. 思路: 把零放到数组最后,使用two points做,就是使用一个指针记录0和非零的数的分界线,另一个指针去寻找非零的数来和这个分界线的数进行交换。 代码: java: class Solution { public void moveZeroes(int[] nums) { if (nums == null || ....

Array - 75. Sort Colors

Array - 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Array - 88. Merge Sorted Array

Array - 88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Array - 228. Summary Ranges

Array - 228. Summary Ranges

Summary Ranges Given a sorted integer array without duplicates, return the summary of its ranges. Example 1: Input: [0,1,2,4,5,7] Output: [“0->2”,“4->5”,“7”] Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range. Example 2: Input: [0,2,3,4,6,8,9] Output: [“0”,“2->4”,“6”,“8->9”] Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range. 思路: 把一个数组连续的字串变成0->3,单独的间断点就没有->这样一个字符串有序表。思路就是遍历数组,记录数组连续的开始点(间断点的下一位)。然后判断间断点加入链表就可以。 代码: jav....

Array - 152. Maximum Product Subarray

Array - 152. Maximum Product Subarray

152. Maximum Product Subarray Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. Example 2: Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray. 思路: 这一题是让找出一个字串的乘积最大,因为负数乘负数就是正数,所以在遍历数组找乘积最大的时候同时找一个最大的正数和一个最小的负数,同时记录过程中最大的数,就是结果。 代码: class Solution { publi....

Array - 238. Product of Array Except Self

Array - 238. Product of Array Except Self

238. Product of Array Except Self Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of numsexcept nums[i]. Example: Input: [1,2,3,4] Output: [24,12,8,6] Note: Please solve it without division and in O(n). Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for t....

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 - 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 - 56. Merge Intervals

Array - 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Array - 4. Median of Two Sorted Arrays

Array - 4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 思路: 最优解是O(min(m, n)),采用二分的思想,来找到两个有序数组的中间切分位置。 代码: java: class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { i....

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

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