不同整数的最少数目和单词直接最短距离

这篇具有很好参考价值的文章主要介绍了不同整数的最少数目和单词直接最短距离。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写是为了更好的思考,坚持写作,力争更好的思考。
今天分享两个关于“最小、最短”的算法题,废话少说,show me your code!

一、不同整数的最少数目

给你一个整数数组arr和一个整数k。现需要从数组中恰好移除k个元素,请找出移除后数组中不同整数的最少数目?
输入:
arr=[5,4,5],k=1
输出:1
解释:
移除1个4,数组中只剩下5一种整数
输入:
arr=[4,3,1,1,3,3,2],k=3
输出:2 解释:先移除4,2然后再移除两个1中任意1个1或者移除两个3中的任意1个3,最后剩余1和3两种整数类型

public static int getMinDifference(int[] arr, int k) {
        // key存放数组数字,value存放次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : arr) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        // 对次数按照自然顺序排序即由小到大
        List<Integer> countNumList = map.values().stream().sorted().collect(Collectors.toList());
        // 不同种类组成的list的长度
        int size = countNumList.size();
        for (Integer count : countNumList) {
            // 由于countNumList由小到大有序,则每次从左边开始剔除数字,使得最终种类最少
            // 遍历countNumList,如果k>=当前次数,则直接删除,种类减少1即size--
            if (k >= count) {
                k -= count;
                size--;
            } else {
                // 如果k<当前次数,则删除当前次数1次后,总的种类并无变化,所以直接终止for循环,
                // 不用再继续判断下一个数字了(因为countNumList有序)
                break;
            }
        }
        return size;
    }

二、单词直接最短距离

给定一个单词列表arr和word1,word2,求出这两个单词之间的最短距离word1,word2不相等且均在arr列表中文章来源地址https://www.toymoban.com/news/detail-800015.html

public static int getMinDistance(String[] arr, String word1, String word2) {
        // 在for循环外定义2个变量,用于存储word1,word2的索引下标,注意要用-1表示,否则会计算出错
        // 将两者索引下标之差的绝对值进行比较,取最小值(注意pos1和pos2均不为空)
        int pos1 = -1;
        int pos2 = -1;
        int minDistance = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (word1.equals(arr[i])) {
                pos1 = i;
            } else if (word2.equals(arr[i])) {
                pos2 = i;
            }
            if (pos1 >= 0 && pos2 >= 0) {
                minDistance = Math.min(minDistance, Math.abs(pos1 - pos2));
            }
        }
        return minDistance;
    }

到了这里,关于不同整数的最少数目和单词直接最短距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 力扣(leetcode)第821题字符的最短距离(Python)

    题目链接:821.字符的最短距离 给你一个字符串 s 和一个字符 c ,且 c 是 s 中出现过的字符。 返回一个整数数组 answer ,其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。 两个下标 i 和 j 之间的 距离 为 abs(i - j) ,其中 abs 是绝对值函数。 示

    2024年01月19日
    浏览(41)
  • GEE机器学习——利用最短距离方法进行土地分类和精度评定

    最短距离方法(Minimum Distance)是一种常用的模式识别算法,用于计算样本之间的相似度或距离。该方法通过计算样本之间的欧氏距离或其他距离度量,来确定样本之间的相似程度或差异程度。 最短距离方法的具体步骤如下: 1. 数据准备:收集并准备用于训练的数据集,确保

    2024年01月20日
    浏览(55)
  • 2023河南萌新联赛第(二)场:河南工业大学 F - 最短距离

    时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 给定一棵包含 n n n 个顶点的树 T T T ,以及 m m m 个查询请求。每个查询包含三个参数 : x 、 y :x、y : x 、 y 和 k k k 。其中 x x x 和 y y y 是树中的两个顶点, k k k 是一个整数。对于

    2024年02月15日
    浏览(44)
  • 最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

    目录 简介 核心思路 优缺点分析 算法过程          示例 Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德

    2024年02月05日
    浏览(43)
  • 汉明距离,两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

    题记: 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 给你两个整数 x 和 y,计算并返回它们之间的汉明距离。 示例 1: 输入 :x = 1, y = 4 输出 :2 解释 : 1 (0 0 0 1) 4 (0 1 0 0) ------↑— ↑ 上面的箭头指出了对应二进制位不同的位置。 示例 2:

    2024年02月15日
    浏览(47)
  • leetcode2719. 统计整数数目

    Problem: 2719. 统计整数数目 给你两个数字字符串 num1 和 num2 ,以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件,我们称它是一个好整数: num1 = x = num2 min_sum = digit_sum(x) = max_sum. 请你返回好整数的数目。答案可能很大,请返回答案对 109 + 7 取余后的结果。 注意,d

    2024年01月18日
    浏览(54)
  • 输入单词需要的最少按键次数 I

    输入单词需要的最少按键次数 I 1 = word.length = 26 word 仅由小写英文字母组成 word 中的所有字母互不相同 因为word 中的所有字母互不相同,可以以任意8个字符为一组,第一组每个字符需要按键一次,第二组需要按键两次,以此类推…根据字符串长度将每组字符的按键次数累加起

    2024年01月24日
    浏览(42)
  • 「数位dp」统计整数数目(力扣第2719题)

    本题为1月16日力扣每日一题 题目来源:力扣第2719题 题目tag: 数位dp 动态规划 给你两个数字字符串num1和num2,以及两个整数max_sum和min_sum。如果一个整数x满足以下条件,我们称它是一个好整数: (num1 leq x leq num2) (min_sum leq digit_sum(x) leq max_sum) 请你返回好整数的数目。答案

    2024年01月16日
    浏览(40)
  • 【图论】【分类讨论】LeetCode3017按距离统计房屋对数目

    图论 分类讨论 【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目 给你三个 正整数 n 、x 和 y 。 在城市中,存在编号从 1 到 n 的房屋,由 n 条街道相连。对所有 1 = i n ,都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编

    2024年04月13日
    浏览(32)
  • [leetcode~数位动态规划] 2719. 统计整数数目 hard

    给你两个数字字符串 num1 和 num2 ,以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件,我们称它是一个好整数: num1 = x = num2 min_sum = digit_sum(x) = max_sum. 请你返回好整数的数目。答案可能很大,请返回答案对 109 + 7 取余后的结果。 注意,digit_sum(x) 表示 x 各位数字之

    2024年01月18日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包