1. Move Zeros
Give an array, Put the0 Move all to the end of the array.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums
should be [1, 3, 12, 0, 0].
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
LeetCode Many questions in”do this in-place”, The common understanding is that the output of the algorithm covers the input of the algorithm, This saves memory.
My code implementation is as follows：
class Solution(object): def moveZeroes(self, nums): for i in range(nums.count(0
)): nums.remove(0) nums.extend(*count0)
The idea is relatively simple, Becauseremove(x) Function can only delete the first encounteredx, So first of all, let's0 remove, And then at the endextend() The method will0 Add tonums Last.
2. Majority Element
Given an array of size n, find the majority element. The majority element is
the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always
exist in the array.
My first thought was to traversenums All elements in, Then?count Number of occurrences of each element, Code submission rejected, The conclusion is that：”Runtime Limited
Error” Overtime. Exactly, The time complexity of such implementation method isO(n2)O(n2)
, Too resource intensive and brainless. Later passedset() Function willnums Duplicate removal, Then traverse to calculate whether the number of occurrences of each element is greater thann/2, Final code submitted successfully, The code is as follows：
class Solution(object): def majorityElement(self, nums): """ :type nums:
List[int] :rtype: int """ nums_set = set(nums) for each in nums_set: if
nums.count(each) > (len(nums)/2): return each
Look at it.Discuss Code submitted by others, I'm really impressed.
There's an algorithm that's very simple, Because there must be a number in the array that exceedsN/2 second, So if you sort the array, Then the firstN//2 Elements must be the result we want.
class Solution: def majorityElement(self, nums): nums.sort() return
Another time, The complexity of space is onlyO(n) Our algorithm is to useHash surface.
class Solution: def majorityElement(self, nums): counts =
collections.Counter(nums)return max(counts.keys(), key=counts.get)
# Heremax Defined in functionkey=counts.get, The most frequent' key'
Python incollections Please move to module details：Python Standard library——collections ModularCounter class
3. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock
on day i.
If you were only permitted to complete at most one transaction (ie, buy one
and sell one share of the stock), design an algorithm to find the maximum
Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7
-1 = 6, as selling price needs to be larger than buying price) Example 2:
Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max
My solution to this problem is simple and rough, But I still have no choice but to submit the code”Runtime Limited Error” Processing time exceeded, The code is as follows, Time complexityO(n2)O(
class Solution(object): def maxProfit(self, prices): length = len(prices)
maxprofit =0 for each in prices: for i in range(prices.index(each)+1,length): if
prices[i]-each > maxprofit: maxprofit = prices[i]-eachif maxprofit > 0: return
maxprofitelse: return 0
class Solution(object): def maxProfit(self, prices): maxprofit = 0 minprice =
prices for i in range(1,len(prices)): if price[i] < minprice: minprice =
price[i] maxprofit = max(maxprofit,price[i] - minprice)return maxporfit