leetcode-235-二叉树搜索的最近公共祖先

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
 

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

思路：
解法一：

迭代
find_q_or_p, 在每一个子树中查找p或q，如果都存在，那么子树的父节点即最短祖先，若不存在任何一个则返回nil，不用在递归了

解法二：

根据二叉搜索树的特性， 左节点都小于父节点，右节点都大于父节点，故可以根据p.val q.val 和root.val 来逐渐缩小范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14

code: 
```ruby
#ruby
def lowest_common_ancestor(root, p, q)
     return root if root == nil || root == p || root == q
    if p.val > root.val && q.val > root.val
       lowest_common_ancestor(root.right, p ,q)
    elsif p.val < root.val && q.val < root.val
       lowest_common_ancestor(root.left, p, q)
    else
       return root
    end
end
1
2
3
4
5
6
7
8
9
10
11
12
#python3
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val >q.val:
            p,q =q,p
        while True:
            if root.val>q.val:
                root = root.left
            elif root.val < p.val:
                root = root.right
            else:
                return root

展开全文 >>

leetcode-215-数组中第K大的元素-堆

题目：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度

思路：

  1. 直接排序，取第k大的元素即可， 时间复杂度 O（nlogn）（快排的情况）
  2. 使用优先队列，维护一个K大的小顶堆 时间复杂度 O(logn)

code：

1
2
3
4
5
#ruby  ..没找到ruby里面的优先队列。。。
def find_kth_largest(nums, k)
    temp_arr = nums.sort
    temp_arr[-k]
end
1
2
3
4
5
6
7
8
9
10
11
#python3
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums[:k]:
            heapq.heappush(heap, num)
        for num in nums[k:]:
            if num > heap[0]:
                heapq.heappop(heap)
                heapq.heappush(heap, num)
        return heap[0]

展开全文 >>

leetcode-98-有效的二叉搜索树

题目：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
示例 1:

输入:

    2
   / \
  1   3

输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

思路：

关键： 二叉搜索树的左节点都小于父节点，右节点都大于父节点
解法一： 中序遍历
解法二： 迭代，每次获取右子树的最小值min和左子树的最大值max,与根节点做比较，若min> root && max < root ,则继续迭代，反之则不为有效二叉搜索树

code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#ruby
解法一：
### ruby
def is_valid_bst(root)
    sort_arr = inorder(root)
    sort_arr == sort_arr.sort.uniq      # 一定要去重！防止[1,1]的情况
end

def inorder(root)
    return [] if root.nil?
    return inorder(root.left) + [root.val] + inorder(root.right)
end

###python3
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        order_arr = self.inorder(root)
        return order_arr == list(sorted(set(order_arr)))
        
        
    def inorder(self, root):
        if root is None:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
解法二： 
### python3   官方题解
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
            
        stack = [(root, float('-inf'), float('inf')), ] 
        while stack:
            root, lower, upper = stack.pop()
            if not root:
                continue
            val = root.val
            if val <= lower or val >= upper:
                return False
            stack.append((root.right, val, upper))
            stack.append((root.left, lower, val))
        return True

展开全文 >>

leetcode-141-环形链表

题目：
给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

思路：
解法一： 哈希表
每走一个节点检测之前是否经历过

解法二： 双指针
快，慢指针, 快指针走两布，慢指针走一步，若快指针== 慢指针，则有环

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#python3
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow: return True
        return False

展开全文 >>

leetcode-20-有效的括号

题目：
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

思路：

  1. 使用栈可以保证时间复杂度为O（n）
  2. 将左括号加入栈
  3. 检测右括号，如果栈顶元素能匹配，则将栈顶元素pop，不能匹配则直接返回false
  4. 最后检测栈是否为空，为空即有效

code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ruby
def is_valid(s)
 hash = {')': '(', '}': '{', ']': '['}
    stack = []
    for i in 0...s.size
        if hash.values.include? s[i]
            stack << s[i]
        elsif (hash.keys.include? s[i].to_sym) && (stack[-1] == hash[s[i].to_sym])
            stack.pop
        else
            return false
        end
    end
    stack.empty?
end
1
2
3
4
5
6
7
8
9
10
#python3
class Solution:
    def isValid(self, s: str) -> bool:
        hash = {'{': '}',  '[': ']', '(': ')'}
        stack = []
        for c in s:
            if not stack or c in hash: stack.append(c)
            elif stack[-1] in hash and hash[stack[-1]] == c: stack.pop()
            else: return False  
        return not stack

展开全文 >>

leetcode-24-两两交换链表中的节点

题目：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3

思路：

  1. 生成一个链表 tmp, tmp.next 指向head
  2. 需要三个指针 分别记录head.next, head.next.next, 和head的前一个指针
  3. 将这三个指针翻转\

code：

1
2
3
4
5
6
7
8
9
10
11
12
#ruby
def swap_pairs(head)
    pre, pre.next = ListNode.new(0), head
    tmp = pre
    while pre.next && pre.next.next
      a = pre.next
      b = a.next
      pre.next, b.next, a.next = b, a, b.next
      pre = a
    end
    tmp.next
end
1
2
3
4
5
6
7
8
9
10
11
#python3
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        pre, pre.next = self, head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, b.next, a.next = b, a, b.next
            pre = a
        
        return self.next

展开全文 >>

leetcode-236-二叉树的最近公共祖先

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
 

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

思路：

迭代
find_q_or_p, 在每一个子树中查找p或q，如果都存在，那么子树的父节点即最短祖先，若不存在任何一个则返回nil，不用在递归了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

code: 
```ruby
#ruby
def lowest_common_ancestor(root, p, q)
    return root if root == nil || root == p || root == q
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p ,q)
    if left == nil
        return right
    elsif right == nil
        return left
    else
        return root
    end
    
end
1
2
3
4
5
6
7
8
9
10
11
12
13
#python3
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.res = None
        self.dfs(root, p, q)
        return self.res
    def dfs(self, root, p, q):
        if not root: return 0
        left = self.dfs(root.left, p, q)
        right = self.dfs(root.right,p ,q)
        mid = root == p or root == q
        if left + right + mid > 1: self.res = root
        return left or right or mid

展开全文 >>

leetcode-50-Pow(x, n)

题目：

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1]

思路：

  1. 直接调用内置函数
  2. 暴力解法，直接循环N次
  3. 递归，分治，将n次幂转化为n/2 次幂，依次迭代

Code：

1
2
3
4
5
6
7
8
9
#ruby
def my_pow(x, n)
    return 1 if n == 0
    return 1 / my_pow(x, -n) if n < 0
    if n % 2 == 1
        return x * my_pow(x, n-1)
    end
    my_pow(x * x, n/2 )
end
1
2
3
4
5
6
7
8
9
10
#python3
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if not n:
            return 1
        if n < 0:
            return 1/self.myPow(x, -n)
        if n%2:
            return x * self.myPow(x, n-1)
        return self.myPow(x * x, n/2)

展开全文 >>

leetcode-206-反转链表

题目：
反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路：
这题是链表中的基础题也是一道经典题
单链表每一个节点中保存着下一个节点的指针，只需要将指针指向上一个节点就可以实现反转链表\

  1. 我们需要两个指针， 一个指向当前节点，一个指向前面的节点

    cur, pre = head, nil

  2. 将当前节点的指针指向前面的节点

    cur.next = pre

  3. 将pre移到当前节点

    pre = cur

  4. 将cur 移到cur.next

    cur = cur.next

  5. 循环直到cur为nil
  6. 此时pre已经移到最后一个节点，返回\

code:

1
2
3
4
5
6
7
def reverse_list(head)
  cur, pre = head, nil
  while cur
    cur.next, pre, cur = pre, cur, cur.next
  end
  pre
end

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家