LeetCode简单题目(#235 #237 #242 #257 #258)-5道（树、数字、字符串）

墨蓝 2023-06-19 15:28 22阅读 0赞

> leetcode题库中共有350道简单题目。  
> 本文记录已解决的题目和代码。  
> 本文中的序号是leetcode题目中的真实序号。

### 文章目录 ###

*  235 二叉搜索树的最近公共祖先
 *   *  描述
     *  代码
 *  237 删除链表中的节点
 *   *  描述
     *  代码
 *  242 有效的字母异位词
 *   *  描述
     *  代码
     *  大神代码
 *  257 二叉树的所有路径
 *   *  描述
     *  代码
 *  258 各位相加
 *   *  描述
     *  代码

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

## 描述 ##

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。  
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，  
满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”  
例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]  
6  
/ \\  
2 8  
/ \\ / \\  
0 4 7 9  
/ \\  
3 5

示例 1:

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

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

## 代码 ##

> 作者：LeetCode  
> 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian–2/

# 递归方法
    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
            # Value of current node or parent node.
            parent_val = root.val
    
            # Value of p
            p_val = p.val
    
            # Value of q
            q_val = q.val
    
            # If both p and q are greater than parent
            if p_val > parent_val and q_val > parent_val:    
                return self.lowestCommonAncestor(root.right, p, q)
            # If both p and q are lesser than parent
            elif p_val < parent_val and q_val < parent_val:    
                return self.lowestCommonAncestor(root.left, p, q)
            # We have found the split point, i.e. the LCA node.
            else:
                return root

# 迭代方法
    class Solution:
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
    
            # Value of p
            p_val = p.val
    
            # Value of q
            q_val = q.val
    
            # Start from the root node of the tree
            node = root
    
            # Traverse the tree
            while node:
    
                # Value of current node or parent node.
                parent_val = node.val
    
                if p_val > parent_val and q_val > parent_val:    
                    # If both p and q are greater than parent
                    node = node.right
                elif p_val < parent_val and q_val < parent_val:
                    # If both p and q are lesser than parent
                    node = node.left
                else:
                    # We have found the split point, i.e. the LCA node.
                    return node

# 237 删除链表中的节点 #

## 描述 ##

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。  
现有一个链表 – head = \[4,5,1,9\]，它可以表示为:

示例 1:

输入: head = \[4,5,1,9\], node = 5  
输出: \[4,1,9\]  
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.  
示例 2:

输入: head = \[4,5,1,9\], node = 1  
输出: \[4,5,9\]  
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:  
链表至少包含两个节点。  
链表中所有节点的值都是唯一的。  
给定的节点为非末尾节点并且一定是链表中的一个有效节点。  
不要从你的函数中返回任何结果。

## 代码 ##

> https://leetcode-cn.com/problems/delete-node-in-a-linked-list/solution/tu-jie-shan-chu-lian-biao-zhong-de-jie-dian-python/

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    # https://leetcode-cn.com/problems/delete-node-in-a-linked-list/solution/tu-jie-shan-chu-lian-biao-zhong-de-jie-dian-python/
    class Solution:
        def deleteNode(self, node):
            """
            :type node: ListNode
            :rtype: void Do not return anything, modify node in-place instead.
            """ 
            node.val = node.next.val
            node.next = node.next.next

# 242 有效的字母异位词 #

## 描述 ##

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。  
示例 1:

输入: s = “anagram”, t = “nagaram”  
输出: true  
示例 2:

输入: s = “rat”, t = “car”  
输出: false  
说明:  
你可以假设字符串只包含小写字母。  
进阶:  
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

## 代码 ##

class Solution:
        def isAnagram(self, s: str, t: str) -> bool:
            return sorted(s) == sorted(t)
            # return "".join((lambda x:(x.sort(),x)[1])(list(s))) == "".join((lambda x:(x.sort(),x)[1])(list(t)))

## 大神代码 ##

> 作者：guanpengchn  
> 链接：https://leetcode-cn.com/problems/valid-anagram/solution/hua-jie-suan-fa-242-you-xiao-de-zi-mu-yi-wei-ci-by/

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            if(s.length() != t.length())
                return false;
            int[] alpha = new int[26];
            for(int i = 0; i< s.length(); i++) {
        
                alpha[s.charAt(i) - 'a'] ++;
                alpha[t.charAt(i) - 'a'] --;
            }
            for(int i=0;i<26;i++)
                if(alpha[i] != 0)
                    return false;
            return true;
        }
    }

# 257 二叉树的所有路径 #

## 描述 ##

给定一个二叉树，返回所有从根节点到叶子节点的路径。  
说明: 叶子节点是指没有子节点的节点。

示例:  
输入:  
1  
/ \\  
2 3  
\\  
5

输出: \[“1->2->5”, “1->3”\]  
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

## 代码 ##

> 作者：LeetCode  
> 链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/er-cha-shu-de-suo-you-lu-jing-by-leetcode/

# 递归方法
    class Solution:
        def binaryTreePaths(self, root: TreeNode) -> List[str]:
            def construct_paths(root, path):
                if root:
                    path += str(root.val)
                    if not root.left and not root.right:  # 当前节点是叶子节点
                        paths.append(path)  # 把路径加入到答案中
                    else:
                        path += '->'  # 当前节点不是叶子节点，继续递归遍历
                        construct_paths(root.left, path)
                        construct_paths(root.right, path)
    
            paths = []
            construct_paths(root, '')
            return paths

# 迭代方法
    class Solution:
        def binaryTreePaths(self, root):
            """
            :type root: TreeNode
            :rtype: List[str]
            """
            if not root:
                return []
            
            paths = []
            stack = [(root, str(root.val))]
            while stack:
                node, path = stack.pop()
                if not node.left and not node.right:
                    paths.append(path)
                if node.left:
                    stack.append((node.left, path + '->' + str(node.left.val)))
                if node.right:
                    stack.append((node.right, path + '->' + str(node.right.val)))
            
            return paths

# 258 各位相加 #

## 描述 ##

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。  
示例:

输入: 38  
输出: 2  
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。  
进阶:  
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

## 代码 ##

> 原理  
> https://leetcode-cn.com/problems/add-digits/solution/python-hua-tu-jiang-ming-bai-o1zuo-fa-de-yuan-li-b/

class Solution:
        def addDigits(self, num: int) -> int:
            # while num > 9:
            #     num = sum([int(i) for i in str(num)])
            # return num
            if not num:
                return 0
            return (num-1)%9 + 1