【 Two 】Leetcode of Python The way to brush questions
1. Move Zeros
Give an array , Put the 0 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 , because remove(x) Function can only delete the first encountered x, So first of all, let's 0 remove , And then at the end extend() Method will 0 Add to nums 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 traversal nums All elements in , then count Number of occurrences of each element , Code was rejected when it was submitted , The conclusion is ：”Runtime Limited
Error” Time out . exactly , The time complexity of such implementation method is O(n2)O(n2)
, Too resource intensive and brainless . Later adopted set() The function will nums duplicate removal , Then traverse to calculate whether the number of occurrences of each element is greater than n/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 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 exceeds N/2 second , So if you sort the array , Then N//2 Elements must be the result we want .
class Solution: def majorityElement(self, nums): nums.sort() return
Another time , The complexity of space is only O(n) Our algorithm is to use Hash surface .
class Solution: def majorityElement(self, nums): counts =
collections.Counter(nums)return max(counts.keys(), key=counts.get)
# here max Defined in function key=counts.get, The most frequent ' key '
Python in collections Please move to module details ：Python Standard library ——collections Modular Counter 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 complexity O(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
right key ：
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