Hello,teams(*´ω｀)
I have studied some algorithms for two month.
Yes, I am going to keep practice it.
BTW, I will try to solve problems by my knowledge in parallel.
If you know more simple and fast program, please teach to me.
time stamp
2020 12/03 :Add Q1,Q7,Q9,Q33,Q35
2020 12/17 :Add Q104
2020 12/18 :Add Q112
2020 12/19 :Add Q617
2020 12/20 :Add Q83
2020 12/31 :Add Q206,Q252
2021 1/1 :Add Q283
Q1.TWO SUM
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1,len(nums),1):
if nums[i]+nums[j] == target:
return[i,j]
#48ms
Q7.REVERSE INTEGER
Given a 32-bit signed integer, reverse digits of an integer.
Note:
Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
class Solution:
def reverse(self, x: int) -> int:
if x > 0:
x = int(str(x)[::-1])
else:
x = int(str(abs(x))[::-1])*-1
if x in range(-2**31,2**31-1):
return x
else:
return 0
#32ms
Q9.PALINDROME NUMBER
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
class Solution:
def isPalindrome(self, x: int) -> bool:
return str(x) == str(x)[::-1]
Q20.VALID PARENTHESES
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1.Open brackets must be closed by the same type of brackets.
2.Open brackets must be closed in the correct order.
class Solution:
def isValid(self, s: str) -> bool:
while "()" in s or "{}" in s or "[]" in s:
s = s.replace("()","").replace("{}","").replace("[]","")
return s == ""
#60ms
Q33.SEARCH IN ROTATED SORTED ARRAY
You are given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
If target is found in the array return its index, otherwise, return -1.
class Solution:
def search(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
#36ms
Q35.SEARCH INSERT POSITION
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if target in nums:
for i in range(len(nums)):
if nums[i] == target:
return i
else:
nums.append(target)
nums.sort()
for j in range(len(nums)):
if nums[j] == target:
return j
#52ms
104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if root == None:
return 0
if root.left is None and root.right is None and root.val is not None:
return 1
def search(root,i):
M = 0
if root.left == None and root.right == None:
#print(f"final is {i}")
return i
if root.left:
#print(f"test,i={i}")
M = max(search(root.left,i+1),M)
if root.right:
#print(f"test,i={i}")
M = max(search(root.right,i+1),M)
return M
return search(root,1)
#40ms
112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root is None:
return sum == None
if root.left is None and root.right is None and root.val is not None:
return sum - root.val == 0
if self.hasPathSum(root.left,sum-root.val):
return True
if self.hasPathSum(root.right,sum-root.val):
return True
return False
#44ms
617. Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
SUM = TreeNode(0)
def Tsum(SUM,t1,t2):
if t1 is None:
return t2
if t2 is None:
return t1
SUM = TreeNode(t1.val+t2.val)
if t1.left or t2.left:
SUM.left = Tsum(SUM,t1.left,t2.left)
if t1.right or t2.right:
SUM.right = Tsum(SUM,t1.right,t2.right)
return SUM
return Tsum(SUM,t1,t2)
83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
p = head
if p is None:
return head
while p.next is not None:
if p.val == p.next.val:
p.next = p.next.next
else:
p = p.next
return head
206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
My output is bellow.
class Solution:
def List2Array(self,head):
nums = []
while head:
nums.append(head.val)
head = head.next
print(nums)
return nums
def Array2List(self,nums):
root = ListNode(nums.pop())
runner = root
while nums:
runner.next = ListNode(nums.pop())
runner = runner.next
return root
def reverseList(self, head: ListNode) -> ListNode:
if not head:return
nums = self.List2Array(head)
return self.Array2List(nums)
#44ms
252. Meeting Rooms
Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: true
my approach is bellow
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort()
for i in range(len(intervals)-1):
if intervals[i][1] > intervals[i+1][0]:
return False
return True
#80ms
283. Move Zeroes
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
My approach is bellow.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if max(nums) == 0:return nums
cnt = 0
while 0 in nums:
nums.remove(0)
cnt += 1
if cnt > 0:
for _ in range(cnt):
nums.append(0)
#116ms
2020/12/03 comment
Looking over the whole, it seems that the for statement nests can break through basic(easy) problems. As you know, the problem can be solved smoothly by programming after imagining the approach. To make imagining easy, it is effective to study the algorithm well and practice creating an image.
I also want to absorb more things.
Let's work hard together.
2020/12/17 comment
This is the first time challenge on Tree problem of leetcode.
I am very glad to solve it by myself,even if it is easy problem.
The point is I made the configuration of recursive in my head during putting a child to sleep.
Good point of software is everyone can do it anywhere.
2020 12/18 comment
I guess this is full search on Tree.
so it is easy to solve it by re-use full search sample program.
Best regards,
AKpirion