Catalogue of series articles
leetcode: Week 1
preface
.
The blogger has just finished the study of RHCE. Next, he decides to brush the algorithm problem of leetcode, 2-3 times a day, and consolidate the review at the weekend.
first day
1. Binary search
Given an n-element ordered (ascending) integer array nums and a target value target, write a function to search the target in nums. If the target value exists, return the subscript, otherwise return - 1.
Example 1:
Input: num = [- 1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 appears in nums with subscript 4
Example 2:
Input: num = [- 1,0,3,5,9,12], target = 2
Output: - 1
Explanation: 2 does not exist in nums, so - 1 is returned
class Solution:
def search(self, nums: List[int], target: int) -> int:
low = 0
height = len(nums)-1
mid = (height + low) // 2
while low != height:
if nums[mid] == target:
return mid
if nums[mid] < target:
low = mid+1
else:
height = mid
mid = int((low + height) / 2)
if nums[low]==target:
return low
return -1
2. First wrong version
Suppose you have n versions [1, 2,..., n], you want to find the first wrong version that causes errors in all subsequent versions.
You can call the bool isBadVersion(version) interface to determine whether the version number is wrong in the unit test. Implement a function to find the first wrong version. You should minimize the number of calls to the API.
Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
Call isbadversion (3) - > false
Call isbadversion (5) - > true
Call isbadversion (4) - > true
Therefore, 4 is the first wrong version.
Example 2:
Input: n = 1, bad = 1
Output: 1
class Solution:
def firstBadVersion(self, n):
low=1
height=n
mid = int(low + (height - low) / 2)
while low != height:
print(low,mid,height)
if isBadVersion(mid):
if isBadVersion(mid-1):
height=mid-1
if isBadVersion(mid):
if isBadVersion(mid-1) is False:
return mid
if isBadVersion(mid) is False:
if isBadVersion(mid-1) is False:
low=mid+1
if isBadVersion(mid) is False:
if isBadVersion(mid+1):
return (mid+1)
mid = int(low + (height - low) / 2)
return 1
Note: when the length of both low and height exceeds half of int type, mid = (low+height) / / 2 will generate overflow, which should be used. mid = int(low + (height - low) / 2)
3. Search insertion location
Given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.
You must use an algorithm with a time complexity of O(log n).
Example 1:
Input: num = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: num = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: num = [1,3,5,6], target = 7
Output: 4
Example 4:
Input: num = [1,3,5,6], target = 0
Output: 0
Example 5:
Input: num = [1], target = 0
Output: 0
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
low = 0
height = len(nums) - 1
mid = (height + low) // 2
while low != height:
#print(low, mid, height)
if nums[mid] == target:
return mid
if nums[mid] < target:
low = mid + 1
else:
height = mid
mid = int((low + height) / 2)
if nums[low] == target:
return low
if nums[0]>target:
return 0
if nums[-1]<target:
return len(nums)
return low
Simply modify the first question directly.
the second day
1. Square of ordered array
Give you an integer array nums sorted in non decreasing order, and return a new array composed of the square of each number. It is also required to sort in non decreasing order.
Example 1:
Input: num = [- 4, - 1,0,3,10]
Output: [0,1,9,16100]
Explanation: after squaring, the array becomes [16,1,0,9100]
After sorting, the array becomes [0,1,9,16100]
Example 2:
Input: num = [- 7, - 3,2,3,11]
Output: [4,9,9,49121]
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
sqrt=[]
for i in nums:
z=pow(i,2)
sqrt.append(z)
sqrt.sort()
return sqrt
2. Rotation array
Give you an array, rotate the elements in the array K positions to the right, where k is a non negative number.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
Turn right for one step: [7,1,2,3,4,5,6]
Rotate right for 2 steps: [6,7,1,2,3,4,5]
Rotate right for 3 steps: [5,6,7,1,2,3,4]
Example 2:
Input: num = [- 1, - 100,3,99], k = 2
Output: [3,99, - 1, - 100]
Explanation:
Turn right for one step: [99, - 1, - 100,3]
Rotate right for 2 steps: [3,99, - 1, - 100]
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k=k%len(nums)
for i in range(k):
a=nums.pop()
nums.insert(0,a)
Note: the title will only return the source address of the array at the end, so the address pointing of the array cannot be modified.
on the third day
1. Move zero
Given an array num, write a function to move all zeros to the end of the array while maintaining the relative order of non-zero elements.
Note that you must operate on the array in place without copying it.
Example 1:
Input: num = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: num = [0]
Output: [0]
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
for i in range(nums.count(0)):
nums.remove(0)
nums.append(0)
2. Sum of two numbers II - input ordered array
Give you an integer array numbers with subscript starting from 1. The array has been arranged in non decreasing order. Please find two numbers in the array that meet the sum of addition and equal to the target number target. If the two numbers are numbers[index1] and numbers[index2] respectively, then 1 < = index1 < index2 < = numbers length .
Return the subscripts index1 and index2 of these two integers in the form of an integer array [index1, index2] with length 2.
You can assume that each input only corresponds to a unique answer, and you can't reuse the same elements.
The solution you design must use only constant level extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: the sum of 2 and 7 is equal to the target number 9. So index1 = 1, index2 = 2. Return to [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: the sum of 2 and 4 is equal to the target number 6. So index1 = 1, index2 = 3. Return to [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: the sum of - 1 and 0 is equal to the target number - 1. So index1 = 1, index2 = 2. Return to [1, 2]
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers)-1
while left != right:
if numbers[left] + numbers[right] == target:
return [left + 1, right + 1]
if numbers[left] + numbers[right] < target:
left = left + 1
else:
right = right - 1
Note: this problem adopts the double pointer solution. There is one pointer at the head and one pointer at the tail. The sum is equal to the target return index. The left pointer less than the target moves to the right, and the right pointer moves to the left when it is greater than the target.
the forth day
1. Reverse string
Write a function that inverts the input string. The input string is given as a character array s.
Do not allocate additional space to another array. You must modify the input array in place and use the additional space of O(1) to solve this problem.
Example 1:
Input: s = ["h", "e", "l", "l", "o"]
Output: ["o", "l", "l", "e", "h"]
Example 2:
Input: s = ["H", "a", "n", "n", "a", "H"]
Output: ["H", "a", "n", "n", "a", "H"]
class Solution:
def reverseString(self, s: List[str]) -> None:
left = 0
right = len(s) - 1
while left < right:
if s[left] == s[right]:
left = left + 1
right = right - 1
continue
s[left], s[right] = s[right], s[left]
left = left + 1
right = right - 1
Note: Double pointers move to the center after head and tail exchange.
2. Reverse the word III in the string
Given a string s, you need to reverse the character order of each word in the string, while still retaining the initial order of spaces and words.
Example 1:
Input: S = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Example 2:
Enter: s = "God Ding"
Output: "doG gniD"
def reverseString(s):
s=list(s)
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left = left + 1
right = right - 1
s="".join(s)
return s
class Solution:
def reverseWords(self, s: str) -> str:
ls=s.split()
reult=[]
for i in ls:
item=reverseString(i)
reult.append(item)
s=" ".join(reult)
return s
The Fifth Day
1. Intermediate node of linked list
Given a non empty single linked list with head node, return the intermediate node of the linked list.
If there are two intermediate nodes, the second intermediate node is returned.
Example 1:
Input: [1,2,3,4,5]
Output: node 3 in this list (serialized form: [3,4,5])
The returned node value is 3. (the serialization expression of this node in the evaluation system is [3,4,5]).
Note that we returned an object ans of ListNode type, as follows:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next next. next = NULL.
Example 2:
Input: [1,2,3,4,5,6]
Output: node 4 in this list (serialized form: [4,5,6])
Since the list has two intermediate nodes with values of 3 and 4, we return the second node.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow=fast=head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
return slow
Note: the fast and slow pointers are used here. The fast pointer moves two bits to the right at a time, and the slow pointer moves one bit to the right at a time. When the fast pointer moves to the end, the slow pointer moves to the intermediate node.
2. Delete the penultimate node of the linked list
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
slow=fast=head
if head.next is None:
return None
for i in range(n):
fast=fast.next
while fast is not None and fast.next is not None:
slow=slow.next
fast=fast.next
if fast is None:
head=slow.next
return head
slow.next=slow.next.next
return head
Note: double pointer, the right pointer is now n steps, and then the left and right pointers move right at the same time. When the right pointer reaches the end, the pointer reaches the previous node to be deleted.
Day 6
1. Longest substring without repeated characters
Given a string s, please find the length of the longest substring that does not contain duplicate characters.
Example 1:
Enter: s = "abcabcbb"
Output: 3
Explanation: because the longest substring without repeated characters is "abc", its length is 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: because the longest substring without repeated characters is "b", its length is 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: because the longest substring without repeated characters is "wke", its length is 3.
Please note that your answer must be the length of the substring, "pwke" is a substring, not a substring.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
string_dict = {}
start = 0
end=0
max=0
if s == "":
return 0
for i in range(len(s)):
end = i
if s[end] in s[start:end]:
start = string_dict[s[end]] + 1
string_dict[s[i]] = i
else:
string_dict[s[i]] = i
item=(end - start) + 1
if item>max:
max=item
return max
Note: double pointer is adopted, and the right pointer moves to the right to add new characters. If the characters are within the range of left and right pointers, the left pointer moves to the next bit of the character, and then the right pointer moves to the right. If the character is not within the range, the left pointer does not move, and the right pointer continues to move to the right. Each time the pointer moves, record the spacing of the pointer, and return to the maximum value after the end.
2. String arrangement
Give you two strings s1 and s2 and write a function to judge whether s2 contains the arrangement of s1. If yes, return true; Otherwise, false is returned.
In other words, one of the permutations of s1 is a substring of s2.
Example 1:
Input: s1 = "ab" s2 = "eidbaooo"
Output: true
Explanation: s2 contains one of the permutations of s1 ("ba")
Example 2:
Input: s1 = "ab" s2 = "eidboaoo"
Output: false
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
#n1,n2 record character length
n1 = len(s1)
n2 = len(s2)
#dict1 and dict2 record the type and quantity of strings
dict1 = {}
dict2 = {}
#Fill dict1
for i in s1:
if i in dict1:
dict1[i] = dict1[i] + 1
else:
dict1[i] = 1
#When s1 length > S2, it does not meet the meaning of the question
if n1 > n2:
return False
#When the length of s1 is 1, the result is judged directly
if n1 ==1:
if s1 in s2:
return True
else:
return False
#When s1 and s2 are the same, the result is returned directly
while n1 == n2:
if s1 == s2:
return True
else:
break
#Record the type and quantity of the first s2 sliding window
for i in s2[0:n1]:
if i in dict2:
dict2[i] = dict2[i] + 1
else:
dict2[i] = 1
#If the results of two dictionaries are the same, the result will appear
if dict1 == dict2 :
return True
for i in range(1,(n2 - n1) + 1):
#Move the window, change dict2, and compare the two dictionaries to return the results
s = s2[i:i + n1]
x=s2[i-1]
y=s2[i+n1-1]
if x==y:
continue
dict2[x]=dict2[x]-1
if dict2[x]==0:
del dict2[x]
if y in dict2:
dict2[y]=dict2[y]+1
else:
dict2[y]=1
if dict1==dict2:
return True
return False
summary
leetcode has a long way to go.