文章 217
评论 6
浏览 143919
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 - 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 - 55. Jump Game

Array - 55. Jump Game

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.

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

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 - 189. Rotate Array

Array - 189. Rotate Array

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

Array - 277 Find the Celebrity

Array - 277 Find the Celebrity

277、Find the Celebrity Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A. Do you know B?” to get information of whether A knows B. You n....

Array - 80. Remove Duplicates from Sorted Array II

Array - 80. Remove Duplicates from Sorted Array II

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

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

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