Let's challenge LeetCode!! _1

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](https://leetcode.com/problems/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.

```two_sum.py
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](https://leetcode.com/problems/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.

```reverse.py
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](https://leetcode.com/problems/palindrome-number/)**
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

```reverse.py
class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]
```

**[Q20.VALID PARENTHESES](https://leetcode.com/problems/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.

```valid_parentheses.py
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](https://leetcode.com/problems/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.

```search_target.py
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](https://leetcode.com/problems/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.

```search_insert.py
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**](https://leetcode.com/problems/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.

```BinTree_MaxDepth.py
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**](https://leetcode.com/problems/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.

```PathSum.py
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**](https://leetcode.com/problems/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.

```MergeTree.py
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**](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)
Given a sorted linked list, delete all duplicates such that each element appear only once.

```RemoveDubble.py
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**](https://leetcode.com/problems/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.

```ReverseList.py
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**](https://leetcode.com/problems/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

```MR.py
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**](https://leetcode.com/problems/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.

```zero_trans.py
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