LeetCode简单题目(#225 #226 #231 #232 #234)-5道（栈、队列、树、数字）

心已赠人 2023-06-17 11:52 19阅读 0赞

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

### 文章目录 ###

*  225 用队列实现栈
 *   *  描述
     *  代码
 *  226 翻转二叉树
 *   *  描述
     *  代码
     *  java版本
 *  231 2的幂
 *   *  描述
     *  代码
 *  232 用栈实现队列
 *   *  描述
     *  代码
     *  大神代码
 *  234 回文链表
 *   *  描述
     *  代码
     *  大神代码-java

# 225 用队列实现栈 #

## 描述 ##

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈  
pop() – 移除栈顶元素  
top() – 获取栈顶元素  
empty() – 返回栈是否为空  
注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。  
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。  
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

## 代码 ##

# https://leetcode-cn.com/u/qqqun902025048/
    class MyStack:
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.q = collections.deque()
            
    
        def push(self, x: int) -> None:
            """
            Push element x onto stack.
            """
            # push 的时候把 x 放入队尾，然后遍历一遍原始队列元素，每次弹出之后加入队尾
            self.q.append(x)
            for _ in range(len(self.q) - 1): self.q.append(self.q.popleft())
            
    
        def pop(self) -> int:
            """
            Removes the element on top of the stack and returns that element.
            """
            return self.q.popleft()
            
    
        def top(self) -> int:
            """
            Get the top element.
            """
            return self.q[0]
            
    
        def empty(self) -> bool:
            """
            Returns whether the stack is empty.
            """
            return not len(self.q)
            
    
    
    # Your MyStack object will be instantiated and called as such:
    # obj = MyStack()
    # obj.push(x)
    # param_2 = obj.pop()
    # param_3 = obj.top()
    # param_4 = obj.empty()

# 226 翻转二叉树 #

## 描述 ##

翻转一棵二叉树。  
示例：  
输入：

/ \\  
2 7  
/ \\ / \\  
1 3 6 9  
输出：

/ \\  
7 2  
/ \\ / \\  
9 6 3 1  
备注:  
这个问题是受到 Max Howell 的 原问题 启发的 ：  
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

## 代码 ##

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    # https://leetcode-cn.com/u/a51067433/
    class Solution:
        def invertTree(self, root: TreeNode) -> TreeNode:
            if not root:
                return None
            root.left,root.right=self.invertTree(root.right),self.invertTree(root.left)
            return root

## java版本 ##

> https://leetcode-cn.com/problems/invert-binary-tree/solution/fan-zhuan-er-cha-shu-by-leetcode/

# 231 2的幂 #

## 描述 ##

给定一个整数，编写一个函数来判断它是否是 2 的幂次方。  
示例 1:

输入: 1  
输出: true  
解释: 20 = 1  
示例 2:  
输入: 16  
输出: true  
解释: 24 = 16  
示例 3:  
输入: 218  
输出: false

## 代码 ##

# 232 用栈实现队列 #

## 描述 ##

## 代码 ##

class Solution:
        def isPowerOfTwo(self, n: int) -> bool:
            # while n and not n%2:
            #     n //= 2
            # if n == 1:
            #     return True
            # if n%2:
            #     return False
            if n <= 0:
                return False
            one_count = bin(n)[2:].count('1')
            if one_count == 1:
                return True
            else:
                return False

## 大神代码 ##

> 作者：jyd  
> 链接：https://leetcode-cn.com/problems/power-of-two/solution/power-of-two-er-jin-zhi-ji-jian-by-jyd/

class Solution:
        def isPowerOfTwo(self, n: int) -> bool:
            return n > 0 and n & (n - 1) == 0

# 234 回文链表 #

## 描述 ##

请判断一个链表是否为回文链表。  
示例 1:

输入: 1->2  
输出: false  
示例 2:

输入: 1->2->2->1  
输出: true  
进阶：  
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

## 代码 ##

class Solution:
        def isPalindrome(self, head: ListNode) -> bool:
            node_list = []
            while head:
                node_list.append(head.val)
                head = head.next
            
            return node_list[:length//2] == node_list[(length-length//2):][::-1]
            # return node_list == node_list[::-1]

## 大神代码-java ##

> 作者：nuan  
> 链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/wo-de-kuai-man-zhi-zhen-du-cong-tou-kai-shi-gan-ju/

public boolean isPalindrome(ListNode head) {
        
            if(head == null || head.next == null) {
        
                return true;
            }
            ListNode slow = head, fast = head;
            ListNode pre = head, prepre = null;
            while(fast != null && fast.next != null) {
        
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
                pre.next = prepre;
                prepre = pre;
            }
            if(fast != null) {
        
                slow = slow.next;
            }
            while(pre != null && slow != null) {
        
                if(pre.val != slow.val) {
        
                    return false;
                }
                pre = pre.next;
                slow = slow.next;
            }
            return true;
        }