博客主页 🏗️
wy的leetcode刷题记录_Day62——二叉树结束
wy的leetcode刷题记录_Day62——二叉树结束

Author:

wy-1226

©

Wordage:

共计 3202 字

needs:

约 2 分钟

Popular:

199 ℃

Created:

目 录

wy的leetcode刷题记录_Day62

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间:2022-12-27

前言

@TOC

1750. 删除字符串两端相同字符后的最短长度

今天的每日一题是:1750. 删除字符串两端相同字符后的最短长度

题目介绍

给你一个只包含字符 'a','b' 和 'c' 的字符串 s ,你可以执行下面这个操作(5 个步骤)任意次:

  1. 选择字符串 s 一个 非空 的前缀,这个前缀的所有字符都相同。
  2. 选择字符串 s 一个 非空 的后缀,这个后缀的所有字符都相同。
  3. 前缀和后缀在字符串中任意位置都不能有交集。
  4. 前缀和后缀包含的所有字符都要相同。
  5. 同时删除前缀和后缀。

请你返回对字符串 s 执行上面操作任意次以后(可能 0 次),能得到的 最短长度 。

示例 1:
输入:s = "ca"
输出:2
解释:你没法删除任何一个字符,所以字符串长度仍然保持不变。

示例 2:
输入:s = "cabaabac"
输出:0
解释:最优操作序列为:

  • 选择前缀 "c" 和后缀 "c" 并删除它们,得到 s = "abaaba" 。
  • 选择前缀 "a" 和后缀 "a" 并删除它们,得到 s = "baab" 。
  • 选择前缀 "b" 和后缀 "b" 并删除它们,得到 s = "aa" 。
  • 选择前缀 "a" 和后缀 "a" 并删除它们,得到 s = "" 。

思路

简单模拟法:采用双指针,分别从字符串的头部和尾部开始遍历,对于每一次迭代我们的目标就是消除当前迭代的前缀和后缀,于是每一个迭代我们执行:

  1. 从当前头部指针i寻找需要判别的字符
  2. 判断头指针和尾指针字符是否相等,若相等继续,否则直接返回当前长度
  3. 寻找前后缀及长度
  4. 在寻找后缀时需要判断是否前后缀有重复的字符

最后当我们的头指针或者尾指针不相等亦或者字符串遍历完比时,我们返回原字符串长度-执行操作的字符串长度即为答案。

代码

class Solution {
public:
    int minimumLength(string s) {
        int n=s.size();
        int i=0;
        int j=n-1;
        int ans=0;
        while(i<j)
        {
            if(s[i]!=s[j])
                break;
            char Compare=s[i];
            //找前缀
            while(Compare==s[i])
            {
                // if(i<j)
                //     break;
                i++;
                ans++;
            }
            
            //找后缀
            while(Compare==s[j])
            {
                if(i>=j)
                    break;
                j--;
                ans++;
            }
            
        }
        return n-ans;
    }
};

收获

简单的模拟题

108. 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树

题目介绍

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:
在这里插入图片描述

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:
在这里插入图片描述

示例 2:

在这里插入图片描述
输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

思路

很正常的将有序数组的中间作为当前迭代的根节点左区间为左子树,右区间为右子树。

代码

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) 
            return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid - 1);
        root->right = traversal(nums, mid + 1, right);
        return root;
    }
    public:
        TreeNode* sortedArrayToBST(vector<int>& nums) {
            TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

收获

二叉树刷的时间段有点长中间忘了很多期待二刷

文章二维码
wy的leetcode刷题记录_Day62——二叉树结束
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 14 小时 9 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视