More than half the numbers in the array
Topic describes
Find a number that occurs more than half the length of the array. For example, enter an array of length 9 {1,2,3,2,2,2,5,4,2}. Since the number 2 appears in the array five times, more than half the length of the array, 2 is printed. Prints 0 if none exists.
The sample
Input:,2,3,2,2,2,5,4,2 [1]
Return value: 2
Their thinking
The dict stores the number of occurrences of a certain number in the array. If the number of occurrences is greater than half the length of the array, the number is returned.
def MoreThanHalfNum(numbers):
length = len(numbers)
if length == 0: return 0
if length == 1: return numbers[0]
dict = {}
for i in range(length):
if numbers[i] in dict:
dict[numbers[i]] += 1
if dict[numbers[i]] > length/2:
return numbers[i]
else:
dict[numbers[i]] = 1
return 0
Copy the code- Time complexity: O(n), because the array is only iterated once
- Space complexity: O(1) ~ O(n), because of the dictionary dict, the best is 1 and the worst is N
Sort the array by the middle value.
def MoreThanHalfNum(numbers):
length = len(numbers)
if length == 0: return 0
if length == 1: return 1
numbers.sort()
num = numbers[int(length/2)]
if (numbers.count(num) > length/2):
return num
return 0
Copy the code- Time complexity: O(nlogn). Python’s sort() is O(nlogn)
- Space complexity: O(1)
If there is a number that matches the criteria, it appears more often than the sum of all the other numbers. So we can save two values as we traverse the array: one for a number in the array and one for the number of times. When iterating over the next number, if it is the same as the previous number, the degree is increased by 1; otherwise, the degree is decreased by 1; If the number is 0, the next number is saved and the number is set to 1. Equal to cancel out in pairs.
def MoreThanHalfNum(numbers):
length = len(numbers)
if length == 0: return 0
if length == 1: return 1
num = numbers[0]
count = 1
for i in range(1, length):
if count == 0:
num = numbers[i]
count = 1
elif numbers[i] == num:
count += 1
else:
count -= 1
if numbers.count(num) > length/2:
return num
return 0
Copy the code-
Time complexity: O(n), because the array is traversed
-
Space complexity: O(1)
Hexadecimal conversion
Topic describes
Given a decimal number M, and the base number N to be converted. Convert a decimal number M to an n-base number.
The sample
Input: 7, 2
Return value: “111”
Their thinking
The first thing you do is you convert to another base and essentially you use that base to take the remainder and put it in the last place, and then you take the remainder and insert it in the first place. We can just take the remainder and add it to the array, and then reverse the array. Points to be noted: one is less than or equal to 0; Two is more than decimal (such as hexadecimal) will appear non-numeric cases, can be stored in an array, and then according to the corresponding number of corresponding letters.
def solve(M, N): if M == 0: return 0 if M < 0: Return the '-' + solve (abs (M, N)) a = [0,1,2,3,4,5,6,7,8,9, 'a', 'B', 'C', 'D', 'E', 'F'] l = [] while True: M, reminder = divmod(M, N) l = l + [reminder] if M == 0: break l.reverse() result = '' for i in l: result += str(a[i]) return resultCopy the code- Time complexity: O(n)
- Space complexity: O(n)
- The divmod () function combines the result of a divisor and remainder operation and returns a tuple containing the quotient and remainder. Input (7,2) output (3,1)
Merges two ordered arrays
Topic describes
Note: We can assume that array A has enough space to hold elements of array B. The initial number of elements in A and B is m and N, respectively
The sample
Input: [1,4,7,9] [2,3,6]
Return value: [1,2,3,4,6,7,9]
Their thinking
Because they say that A has enough space for B, so we don’t have to create A new space. If A is larger than B, store that number to the end of the new ARRAY A (length m+n), and move the pointer to the array A one bit forward. The other case is the same. If array A is traversed but array B is not, place the remaining digits of array B in the new array A in the current order. Because the numbers are placed directly in array A, if B is iterated, the merge is done
def merge(A, m, B, n):
if m == 0 and n == 0: return []
while m > 0 and n > 0:
if A[m-1] > B[n-1]:
A[m+n-1] = A[m-1]
m -= 1
else:
A[m+n-1] = B[n-1]
n -= 1
if n > 0: A[:n] = B[:n]
Copy the code- Time complexity: O(n)
- Space complexity: O(1)
The sum of two Numbers
Topic describes
Given an array of integers, find two numbers in the array that add up to the target value. Your function twoSum needs to return the subscripts of these two numbers (index1, index2) such that index1 is less than index2. Note: The subscript starts at 1 and assumes that only unique solutions exist in the array
The sample
Input: 4-trichlorobenzene [3], 6
Return value: [2,3]
Their thinking
Define a dictionary to hold indexes of the difference between target and the current value of the loop, a and num. If num2 exists in the dictionary, the difference between target and num1 exists in the dictionary (a=num2). If num1+num2=target, the index of num1 must be less than the index of num2. Return the index of a and the index of num2. Note: index starts at 1, so you need to add 1 when you need to return
def twoSum(numbers, target):
d = {}
for n in range(len(numbers)):
a = target - numbers[n]
if numbers[n] in d:
return d[numbers[n]]+1,n+1
else:
d[a] = n
Copy the code- Time complexity: O(n)
- Space complexity: O(n)
Note: If the array is an ordered array, use the left and right subscripts to point to the beginning and end of the array. If the sum is less than the target value, then left+1. If the sum is greater than the target value, then right-1
Fibonacci numbers
Topic describes
We all know the Fibonacci sequence, and now we’re asking for an integer n, so please print the NTH term of the Fibonacci sequence (starting at 0, the 0th term is 0, and the first term is 1). n<=39
The sample
Input: 4
Return value: 3
Their thinking
We use temp to store an lvalue, and then an lvalue equals an rvalue, and the new rvalue equals the previous lvalue, that is, temp plus an rvalue
def Fibnacci(n):
left = 0
right = 1
if n < 1: return n
for i in range(n):
temp = left
left = right
right = temp + right
return left
Copy the code- Time complexity: O(n)
- Space complexity: the space of the recursive stack
Binary lookup of ordered arrays
Topic describes
Implement binary lookup of an ordered array with repeated numbers. Prints the first position in the array greater than or equal to the value searched for. If no such number exists in the array, the output array length is incremented by one.
The sample
Input: 5,4,[1,2,4,4,5] (array length, lookup value, ordered array)
Return value: 3 (output position calculated from 1)
Their thinking
First, use two Pointers to mark left and right, and then find the middle pointer mid. Then use mid position to compare with the keyword. If it is greater than or equal to the search value, then further compare whether the value of mid-1 position is less than the search value or mid is equal to 0. If so, return mid+1. If not, the right pointer points to mid (that is, the search continues in the left half of the array). If less than the search value, the left pointer points to mid (that is, the search continues in the right half of the array). If the traversal is complete and no trace is found, n+1 is returned.
def upper_bound_(n , v , a ):
left = 0
right = n - 1
while left < right:
middle = int(left + (right-left)/2)
if a[middle] >= v:
if middle == 0 or a[middle-1] < v:
return middle+1
else:
right = middle
else:
left = middle+1
return n + 1
Copy the code- Time complexity: O(logn)
- Space complexity: O(1)
Maximum summation problem for subarrays
Topic describes
Given an array arr, return the maximum sum of subarrays for example, arr = [1, -2, 3, 5, -2, 6, -1], of all subarrays, [3, 5, -2, 6] can add up to the maximum sum 12, so return 12.
[Requirement] The time complexity is O(n)O(n) and the space complexity is O(1)O(1).
The sample
Input: [1, -2, 3, 5, -2, 6, -1]
Return value: 12
Their thinking
Because space complexity is required to be O(1), operations are performed directly on array. Nums [i-1] does not mean the sum of the largest suborder up to the previous item in the array, compared to 0 because as long as greater than 0, you can add to construct the sum of the largest suborder. If less than 0, the sum is 0, nums[I]=nums[I], equivalent to the maximum suborder sum is recalculated.
def maxsumofSubarray(array):
for i in range(1, len(array)):
array[i] = array[i] + max(array[i-1], 0)
return max(array)
Copy the code- Time complexity: O(n)
- Space complexity: O(1)
A number that appears only once
Topic describes
Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.
Your algorithm should have linear time complexity. Can you do it without using extra space?
The sample
Input: [2, 2, 1]
Return value: 1
Their thinking
Use xOR. Commutative law: A ^ b ^ c <=> a ^ c ^ b; Any number equal to or equal to 0 ^ n => n; The same number is either 0: n ^ n => 0. So: 2 ^3 ^ 2 ^ 4 ^ 4 is equivalent to 2 ^ 2 ^ 4 ^ 4 ^3 => 0 ^ 0 ^3 => 3
def singleNumber(nums):
a = 0
for num in nums:
a = a ^ num
return a
Copy the code- Time complexity: O(n)
- Space complexity: O(1)
Yang hui triangle
Topic describes
Given a nonnegative index k, where k ≤ 33, return the KTH row of the Yang Hui triangle.
The sample
Input: 3
Return value: [1,3,3,1]
Their thinking
First, generate the required space directly (fill with 1), and then loop through the calculation to update the generation
def getRow(rowIndex):
for i in range(rowIndex+1):
now = [1] * (i+1)
if i >= 2:
for n in range(1, i):
now[n] = pre[n-1] + pre[n]
pre = now
return now
Copy the code- Time complexity: O(n^2)
- Space complexity: O(n^2)
Gal.
Topic describes
Given a non-negative integer represented by a non-empty array of integers, add one to that number. The highest digit is stored at the beginning of an array, where each element stores only a single digit. You can assume that this integer does not start with zero, except for the integer 0.
The sample
Input: [1, 2, 3]
Return value: [1,2,4]
Their thinking
Loop forward from the end, and return [1] + the current array. Otherwise, return after the current bit +1.
def plusOne(digits):
n = len(digits)
for i in range(n-1, -1, -1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
return [1]+digits
Copy the code- Time complexity: O(n)
- Space complexity: O(1)
Remove elements
Topic describes
Given an array of nums and a value of val, you remove all elements equal to val in place and return the new length of the array.
Instead of using extra array space, you must only use O(1) extra space and modify the input array in place.
The order of elements can be changed. You don’t need to worry about the element after the new length in the array.
The sample
Given nums = [3,2,2,3], val = 3,
The function should return a new length of 2, and the first two elements in nums are both 2.
Their thinking
Because you need to modify the array in place, you can use python’s built-in function POP (key), which is the key value to delete. Also, be aware that deleting elements in real time changes the length of the array, so loop forward from the end
def removeElement(nums,val):
n = len(nums)
for i in range(n-1, -1, -1):
if nums[i] == val:
nums.pop(i)
return len(nums)
Copy the code- Time complexity: O(n)
- Space complexity: O(1)
Convert Roman numerals to integers
Topic describes
Roman numerals contain the following seven characters :I: 1, V: 5, X: 10, L: 50, C: 100, D: 500 and M: 1000.
For example, the Roman numeral 2 is written as ‘II’, which is two ones side by side. 12 write ‘XII’ as ‘X’+’II’. 27 Write ‘XXVI’, which is ‘XX’+’V’+’II’.
Usually, the smaller Roman numerals are to the right of the larger numerals. But there are exceptions. For example, instead of writing 4 as ‘IIII’, you write 4 as ‘IV’. The number 1 is to the left of the number 5 and represents the number 4 when the larger number 5 decreases by 1. Likewise, the number 9 is represented as ‘IX. This particular rule applies only to the following six situations:
I can be placed to the left of V(5) and X(10) to represent 4 and 9; X can be placed to the left of L(50) and C(100) to represent 40 and 90; C can be placed to the left of D(500) and M(1000) to represent 400 and 900;
Given a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999.
The sample
Input: “LVIII”
Output: 58 (interpretation: L = 50, V= 5, III = 3)
Their thinking
Start by building a hashMap to map the correspondence between symbols and numbers. Then loop from left to right, adding the value if the current value is not less than the right, subtracting it otherwise.
def romanToInt(s):
num = 0
a = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
for i in range(len(s)):
if i < len(s)-1 and a[s[i]] < a[s[i+1]]:
num -= a[s[i]]
else:
num += a[s[i]]
return num
Copy the code-
Time complexity: O(n)
-
Space complexity: O(1)