LeetCode day31

发布时间:2023年12月27日

LeetCode day31


被创新实践的机器学习大作业和数据库作业折磨力,临近期末,各种大作业以及ddl,搞的咱只能偶尔刷刷力扣,但是csdn就挺难去发布了,大家期末也好好复习过个好年啦,O(∩_∩)O


409. 最长回文串

给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串

在构造过程中,请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
输出:1

示例 3:

输入:s = "aaaaaccc"
输出:7

class Solution {
    public int longestPalindrome(String s) {
        int[]temp=new int[128];
        if(s.length()==1){
            return 1;
        }
   
        for(int i=0;i<s.length();i++){
            temp[s.charAt(i)]++;
        }
        int ans=0;
        for(int x: temp){
            if(x%2!=0){
                x-=1;
            }
            if(x%2==0){
                ans+=x;
            }
        }
        if(ans!=s.length()){
            return ans+1;
        }
        return ans;
    }
}

嘛,虽然但是第一时间有想过哈希表,但是忘记得开多少空间了,对Ascall码有点忘记了


111. 二叉树的最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明:**叶子节点是指没有子节点的节点。

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:2

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int min=0;
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
    LinkedList<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        min++;
        int size=queue.size();
        while(size>0){
       TreeNode p = queue.poll();
       if(p.left!=null){
           queue.offer(p.left);
       }
       if(p.right!=null){
           queue.offer(p.right);
       }
       if(p.right==null&&p.left==null){
           return min;
       }
       size--;
    }
    }
    return min;
}
}

嘛,递归的时候发现瘸腿树直接出问题了。就直接用队列了。


100. 相同的树

给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

img

输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

img

输入:p = [1,2], q = [1,null,2]
输出:false

示例 3:

img

输入:p = [1,2,1], q = [1,1,2]
输出:false
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
    if(p==null&&q==null){
        return true;
    }
    if(p==null||q==null){
        return false;
    }
    if(p.val!=q.val){
        return false;
    }
    return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

麻了,递归感觉有点麻
主要是这个题也没想到递归去做,结果可想而知,发现层序遍历和深度遍历的时候null不好处理,只能无脑if语句
文章来源:https://blog.csdn.net/m0_74345527/article/details/135233792
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。