115 双周赛

这篇具有很好参考价值的文章主要介绍了115 双周赛。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2901. 最长相邻不相等子序列 II

给你一个整数 n 和一个下标从 0 开始的字符串数组 words ,和一个下标从 0 开始的数组 groups ,两个数组长度都是 n 。

两个长度相等字符串的 汉明距离 定义为对应位置字符 不同 的数目。

你需要从下标 [0, 1, …, n - 1] 中选出一个 最长子序列 ,将这个子序列记作长度为 k 的 [i0, i1, …, ik - 1] ,它需要满足以下条件:

相邻 下标对应的 groups 值 不同。即,对于所有满足 0 < j + 1 < k 的 j 都有 groups[ij] != groups[ij + 1] 。
对于所有 0 < j + 1 < k 的下标 j ,都满足 words[ij] 和 words[ij + 1] 的长度 相等 ,且两个字符串之间的 汉明距离 为 1 。
请你返回一个字符串数组,它是下标子序列 依次 对应 words 数组中的字符串连接形成的字符串数组。如果有多个答案,返回任意一个。

子序列 指的是从原数组中删掉一些(也可能一个也不删掉)元素,剩余元素不改变相对位置得到的新的数组。

注意:words 中的字符串长度可能 不相等 。

示例 1:

输入:n = 3, words = [“bab”,“dab”,“cab”], groups = [1,2,2]
输出:[“bab”,“cab”]

解题思路

动态规划,唯一路径文章来源地址https://www.toymoban.com/news/detail-718533.html

code
class Solution {
    public Boolean Hamming(String s1,String s2){
        if(s1.length()!=s2.length())
        return false;
        int x = 0;
        for(int i=0;i<s1.length();i++)
            if(s1.charAt(i)!=s2.charAt(i)&&++x>1)
            return false;
        return true;
        }
    public List<String> getWordsInLongestSubsequence(int n, String[] words, int[] groups) {
            int[] source = new int[n];
            int[] best_seq = new int[n];
            int max_seq = 0;
            for(int i=0;i<n;i++)
            {
                for(int j=i-1;j>=0;j--)
                    if(best_seq[j]>best_seq[i]&&groups[j]!=groups[i]&&Hamming(words[i],words[j]))
                    {
                        best_seq[i]=best_seq[j];
                        source[i] = j;
                    }
            
            best_seq[i]++;
            if(best_seq[i]>best_seq[max_seq])
            max_seq = i;
            }
         List<String> result = new ArrayList<>();
         int now = max_seq;
         for(int i=0;i<best_seq[max_seq];i++)
         {
             result.add(words[now]);
             now = source[now];
         }
         for(int i=0;i<result.size()/2;i++)
             Collections.swap(result, i, result.size()-1-i);
         return result;
    }
}

到了这里,关于115 双周赛的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode第124场双周赛

    给你一个整数数组  nums  ,如果  nums   至少  包含  2  个元素,你可以执行以下操作: 选择  nums  中的前两个元素并将它们删除。 一次操作的  分数  是被删除元素的和。 在确保  所有操作分数相同  的前提下,请你求出  最多  能进行多少次操作。 请你返回按照上述

    2024年02月19日
    浏览(37)
  • 第 107 场LeetCode双周赛

    A 最大字符串配对数目 显然各字符串对 间匹配的先后顺序不影响最大匹配数目, 可以从后往前遍历数组, 判断前面是否有和当前末尾构成匹配的. B 构造最长的新字符串 记忆化搜索: 定义状态 p a a , b b , a b , l a s t p_{aa,bb,ab,last} p aa , bb , ab , l a s t ​ 为剩余三种字符串分别为aa、

    2024年02月11日
    浏览(40)
  • leetcode 122双周赛 解题思路+代码

    本人水平有限,只做出3道,最后1道放弃。 给你一个长度为 n 的整数数组 nums 。 一个数组的 代价 是它的 第一个 元素。比方说,[1,2,3] 的代价是 1 ,[3,4,1] 的代价是 3 。 你需要将 nums 分成 3 个 连续且没有交集 的子数组。 请你返回这些子数组的 最小 代价 总和 。 示例 1: 输

    2024年02月20日
    浏览(41)
  • LeetCode---121双周赛---数位dp

    2996. 大于等于顺序前缀和的最小缺失整数 2997. 使数组异或和等于 K 的最少操作次数 2998. 使 X 和 Y 相等的最少操作次数 2999. 统计强大整数的数目 简单的模拟题,只要按照题目的要求去写代码即可,代码如下 这题考异或的性质---相同为0,相异为1,我们只要关心nums的异或和与

    2024年01月22日
    浏览(48)
  • 【力扣周赛】第 113 场双周赛(贪心&异或性质&换根DP)

    https://leetcode.cn/contest/biweekly-contest-113/ https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/ 提示: 1 = nums.length = 100 1 = nums[i] = 100 nums 中的整数互不相同。 因为数据范围很小,所以可以从小到大枚举可能的答案。 https://leetcode.cn/problems/minimum-array-length-after-pair-removals/ 提示: 1

    2024年02月07日
    浏览(32)
  • 第 122 场 LeetCode 双周赛题解

    A 将数组分成最小总代价的子数组 I 枚举:枚举后两个子数组的起始下标 B 判断一个数组是否可以变为有序 模拟:模拟冒泡排序的过程,若相邻元素大小关系需要交换位置,但其二进制下数位为 1 的数目不同,则返回false,若完成排序返回true C 通过操作使数组长度最小 脑筋急

    2024年01月22日
    浏览(40)
  • [LeetCode108双周赛&LeetCode353周赛] 学习用记忆化搜索解决 DP 问题

    参考灵神直播和代码 @cache 装饰器的作用:将传入不同参数得到的函数值存储到缓存,避免下次传递相同参数重复计算结果,可用于解决递归函数重复计算问题,比如递归求斐波那契问题。 https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/ 记忆化搜索 dfs(i) 表示以

    2024年02月13日
    浏览(35)
  • 1014蓝桥算法双周赛,学习算法技巧,助力蓝桥杯

    家人们,我来免费给大家送福利了!!! 【1014蓝桥算法双周赛 】 蓝桥杯全国软件和信息技术专业人才大赛是由工业和信息化部人才交流中心举办的全国性IT学科赛事。参赛高校超过1200余所,累计参赛人数超过40万人。该赛事连续两年被列入中国高等教育学会发布的“全国普

    2024年02月08日
    浏览(39)
  • LeetCode 双周赛 106(2023/06/10)两道思维题

    本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 加入知识星球提问。 往期回顾:LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗? T1. 判断一个数是否迷人(Easy) 标签:计数 T2. 找到最长的半重复子字符串(Medium) 标签:同向双指针 T3. 移动机器人(Medi

    2024年02月08日
    浏览(38)
  • 蓝桥杯双周赛算法心得——三带一(暴力枚举)

    大家好,我是晴天学长,枚举思想,需要的小伙伴可以关注支持一下哦!后续会继续更新的。 1) .三带一 2) .算法思路 1.通过Scanner读取输入的整数n,表示接下来有n个字符串需要处理。 2.使用循环遍历每个字符串: 3.将字符串转换为字符数组c。 4.对于每个字符c[j],统计在整个

    2024年02月07日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包