专栏首页算法修养LeetCode 1585 Check If String Is Transformable With Substring Sort Operations

LeetCode 1585 Check If String Is Transformable With Substring Sort Operations

题目

题意:一个只有0-9组成的字符串,每次选择任意一个子串,按照数字从小到大排序。问从源字符串能否经过若干次操作转换成目标字符串。

题解:首先题目只问了是否,而没有问多少次,所以可以判断出,我们不关心过程是怎么样的,只关心结果能否到达。所以不太可能是动态规划,搜索什么的。 既然是看结果,那估计是个找规律的题目。首先看目标字符串的第一个字符x,如果它是由源字符串的某个字符x经过排序之后,安排到了第一个位置,那么它一定满足,在源字符串中从起始位置到x的位置的子串中,x一定是最小的那个。否则x就无法移动到第一个位置。 一次内推,第二个字符x2, 由于第一个字符x已经确定了我们把x变成最大值,那么x2应该满足从源字符串起始位置到x2的位置的子串中,x2是最小的那个。

所以这道题目就变成了单点更新,求区间最值。 使用简单优雅的数据结构,树状数组,即可解决问题。 树状数组的区间最值,要比区间和复杂一点,且更新的时间效率是Log(n)*Log(n) 跟线段树比差一点。

class Solution {
public:
    int c[100005];
    int a[100005];
    vector<int> pos[10];
    int n;
    bool isTransformable(string s, string t) {
        
        for(int i = s.length()-1;i>=0;i--)
        {
            int num = s[i]-'0';
            pos[num].push_back(i+1);
        }
        
        n = s.length();
        for(int i=0;i<=n;i++)
        {
            c[i] = INT_MAX;
        }
        
        for(int i=0;i<s.length();i++)
        {
            add(i+1,s[i]-'0');
            a[i+1]=s[i]-'0';
        }
        
        for(int i=0;i<t.length();i++)
        {
            if(pos[t[i]-'0'].size()==0)
                return false;
            int p = pos[t[i]-'0'].back();
            pos[t[i]-'0'].pop_back();
            int m = get(1,p);
            if(m!=t[i]-'0')
                return false;
            
            add(p,INT_MAX);
        }
        
        return true;
        
    }
    
    int lowbit(int x)
    {
        return x&(-x);
    }
    
    void add(int index,int num)
    {
        a[index] = num;
        while(index<=n)
        {
            int l = index-lowbit(index)+1;
            int m = get(l, index-1);
            if(l==index)
            {
                c[index]=a[index];
            }
            else if(min(m, a[index])!=c[index])
            {
                c[index]=min(m, a[index]);
            }
            else
            {
                break;
            } 
            index+=lowbit(index);
        }
    }
    
    int get(int l, int r)
    {
        if(l>r)
            return INT_MAX;
        int ans = INT_MAX;
        while(r>=l)
        {
            if(r-lowbit(r) < l-1)
            {
                ans = min(ans, a[r]);
                r--;
            }
            else
            {
                ans = min(ans, c[r]);
                r-=lowbit(r);
            }
        }
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [002] 一文了解Python中的常用字符串操作

    Asthe co-founder of Microsoft says, I invite you to continue stretching your min...

    Sam Gor
  • lua Standard Libraries

    The standard Lua libraries provide useful functions that are implemented directl...

    晚晴幽草轩轩主
  • 2018-11-21

    This section comprises a glossary of all the keywords — grouped by category and ...

    Albert陈凯
  • java开发_org.apache.commons.lang.StringUtils工具类源码

    http://www.cnblogs.com/hongten/archive/2012/11/08/java_null.html

    Hongten
  • LeetCode Longest Substring Without Repeating Characters

    Given a string, find the length of the longest substring without repeating chara...

  • Knapsack problem algorithms for my real-life carry-on knapsack

    I'm a nomad and live out of one carry-on bag. This means that the total weight o...

    李海彬
  • LeetCode Weekly Contest 28解题思路

    好吧,不要被这道题的例子给骗了。要求输出的最大,意思就是求除第一个元素之外的其他division最小,而不断连除就是第二部分的最小值,所以有如下代码:

    用户1147447
  • Python基础篇 strings 03

    找出子字符串出现频次和出现的索引位置核查是否存在字符串并找出其索引位置查找所有字符的出现次数和索引

    披头
  • No.003 Longest Substring Without Repeating Characters

    Longest Substring Without Repeating Characters Total Accepted: 167158 Total Subm...

    mukekeheart
  • C++版- Leetcode 3. Longest Substring Without Repeating Characters解题报告

    Leetcode 3. Longest Substring Without Repeating Characters

    Enjoy233
  • 【Leet Code】3. Longest Substring Without Repeating Characters

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • Leetcode solution 1036: Escape a Large Maze

    New leetcode solution video on YouTube.com/baozitraining

    包子面试培训
  • LeetCode3.滑动窗口: 双指针法(Kotlin语言)-无重复字符的最长子串

    输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

    一个会写诗的程序员
  • 【玩转腾讯云】python help函数

    python 3.x版本虽然比2.x少了一些内置函数,但是 python 内置 函数没有60个,也有40个,那么多内置函数你记得过来吗?为了方便使用,pytho...

    猿说编程[Python和C]
  • 写给开发者的机器学习指南(八)

    Ranking emails based on their content(Recommendation system)

    哒呵呵
  • Leetcode 211: Add and Search Word - Data structure design

    https://blog.baozitraining.org/2019/03/leetcode-solution-211-add-and-search.html

    包子面试培训
  • [LeetCode]HashTable主题系列{第3题}

    1. 内容介绍 开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解...

    昊楠Hacking
  • Leetcode3——Longest Substring Without Repeating Characters

    Given a string, find the length of the longest substring without repeating chara...

    Tyan
  • Leetcode 算法 -3. Longest Substring Without Repeating Characters

    我们以ababcbb为例说明, 这里hash表的值-1是初始值, 这样在方便做+1操作. index 作为开始索引值, 起初index为0, 这是理所当然的。当...

    用户1416054

扫码关注云+社区

领取腾讯云代金券