代码编织梦想

wy的leetcode刷题记录_Day62

声明

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

前言

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;
    }
};

收获

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

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_54015435/article/details/128474205

wy的leetcode刷题记录_day33_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day33 时间:2022-11-4 目录 wy的leetcode刷题记录_Day33754. 到达终点数字题目介绍思路代码收获 199. 二叉树的右视图题目介绍思路代码收获

wy的leetcode刷题记录_day32_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day32 时间:2022-11-3 目录 wy的leetcode刷题记录_Day321668. 最大重复子字符串题目介绍思路代码收获 637. 二叉树的层平均值题目介绍思路代

wy的leetcode刷题记录_day34_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day34 时间:2022-11-5 目录 wy的leetcode刷题记录_Day341106. 解析布尔表达式题目介绍思路代码收获 429. N 叉树的层序遍历题目介绍思路代

wy的leetcode刷题记录_day36_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day36 时间: 目录 wy的leetcode刷题记录_Day36816. 模糊坐标题目介绍思路代码收获 226. 翻转二叉树题目介绍思路代码收获 816.

wy的leetcode刷题记录_day39_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day39 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉 目录 wy的leetcode刷题记录_Day39声明1704. 判断字符串的两半是否相似题目介绍

wy的leetcode刷题记录_day40_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day40 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉 目录 wy的leetcode刷题记录_Day40声明790. 多米诺和托米诺平铺题目介绍思路代码

wy的leetcode刷题记录_day41_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day41 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉 目录 wy的leetcode刷题记录_Day41声明791. 自定义字符串排序题目介绍思路代码收

wy的leetcode刷题记录_day42_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day42 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉 目录 wy的leetcode刷题记录_Day42声明805. 数组的均值分割题目介绍思路代码收获

wy的leetcode刷题记录_day47_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day47 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-20 前言 补 目录 wy的leetcode刷题记录_Day47声

wy的leetcode刷题记录_day46_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day46 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-19 前言 补 目录 wy的leetcode刷题记录_Day46声

wy的leetcode刷题记录_day56_wy-1226的博客-爱代码爱编程

wy的leetcode刷题记录_Day56 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-30 前言 目录 wy的leetcode刷题记录_Day56声明前

wy的leetcode刷题记录_day1-爱代码爱编程

wy的leetcode刷题记录_Day1 目录 wy的leetcode刷题记录_Day1698. 划分为k个相等的子集题目介绍思路代码收获 63. 不同路径 II题目介绍思路代码收获

wy的leetcode刷题记录_day37_wy37.net最新-爱代码爱编程

wy的leetcode刷题记录_Day37 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉 目录 wy的leetcode刷题记录_Day37声明1684. 统计一致字符串的数目题目介

wy的leetcode刷题记录_day48-爱代码爱编程

wy的leetcode刷题记录_Day48 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-21 前言 补前几天的blog 目录 wy的leetcode

wy的leetcode刷题记录_day51-爱代码爱编程

wy的leetcode刷题记录_Day51 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-24 前言 目录 wy的leetcode刷题记录_Day51

wy的leetcode刷题记录_day52-爱代码爱编程

wy的leetcode刷题记录_Day52 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-25 前言 补 目录 wy的leetcode刷题记录_Day

wy的leetcode刷题记录_day53-爱代码爱编程

wy的leetcode刷题记录_Day53 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-27 前言 补 目录 wy的leetcode刷题记录_Day

wy的leetcode刷题记录_day50-爱代码爱编程

wy的leetcode刷题记录_Day50 声明 本文章的所有题目信息都来源于leetcode 如有侵权请联系我删掉! 时间:2022-11-23 前言 补 目录 wy的leetcode刷题记录_Day