热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

用Java编码时如何避免TLE?

用Java编码时如何避免TLE?原文:https://ww

用 Java 编码时如何避免 TLE?

原文:https://www . geeksforgeeks . org/如何避免在 java 中编码时出现小标题/

避免超过时间限制 (TLE)是我们在进行竞争性编码以及在技术 PI 期间回答 DSA 问题时需要注意的最重要的方面之一。在这种情况下,所有编码平台中一个常见的问题是排序或涉及排序的问题。下面的代码是我在练习数据结构时设计的,它对从 1 开始的最少交换次数的连续数字列表进行线性排序,并返回交换次数的值。

下面代码背后的概念是,考虑到数组索引从 0 开始,排序数组中数字的正确位置比数字本身小 1。这是因为数组仅由从 1 开始的连续数字组成。

图解:考虑下面的例子:给定的未排序数组是:4 3 1 2 5。

输入:下面是数组元素及其在数组中的当前位置的表格(由第一行中的索引指示)。

| Zero | one | Two | three | four |
| four | three | one | Two | five |

输出:排序后,数组将如下图所示。因此,元素的正确位置只不过是比数字本身小 1 的值的索引,因此我们所需要做的就是将各个元素放在它们的正确索引处,这些索引可以从元素值中确定。

T18
3
T22
4
T26
| 0 | 1 | T15】2 |
| T29】1 | T33】2
T37 | 【T39】3【T40 |

进场:


  1. 我们首先将给定的数组元素插入到 HashMap 中,其中键是元素,值是指示当前位置的索引。

  2. 然后我们运行一个 for 循环,从输入数组的初始索引值(即 0)开始,直到小于数组大小 1 的值。

  3. 在每次迭代中,我们检查 arr[i]处的值是否比“I”多一个。

  4. 如果是这样的话,这意味着该元素位于其正确的位置,否则它的位置需要与它实际所在位置的元素交换(该元素只不过是(i+1))。每次交换发生时,用于记录交换次数的变量都会增加 1。

  5. 然后数组中由于交换而产生的相应变化也会在 HashMap 中更新。

图示:最初,散列表如下

T33
| Element (key) | Current index (value) |
| --- | --- |
| 4 | 19【0】 |
| 3 | one |

第一次迭代后,HashMap 会是这样的

T14
2
T18T20
3
T24
1
T28T30
1
T31
| Element (Key) | Current index (Value) |
| 4 |

而阵中则变成了

T16
3
T19T25
| 0 | 1 | T13】2 | 4T 23 T21 |
| 【T27】1T29 | T313 | 【T35】4T37】 |

结论:因此,在每次交换之后,一个元素被放置在其正确的位置,并且对 hashmap 进行相应的更改,以确保交换的数量最小。

实施:

Java 语言(一种计算机语言,尤用于创建网站)


// Java Program to illustrate a Hack to Avoid TLE while
// coding
// Importing required libraries
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
// Main Class
class GFG {
    // Method 1
    // To find the minimum number of swaps required
    static int minimumSwaps(int[] arr)
    {
        // Declaring and initializing variables to 0
        // Swap and Index variable
        int swap = 0, index = 0;
        // Creating object of HashMap class for storing
        // array elements along with corresponding current
        // position in the input array
        // Declaring both the objects if Integer type
        HashMap<Integer, Integer> index_table
            = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            index_table.put(arr[i], i);
        }
        // Loop variable beginning from 0 so the element
        // that should be present at index i after sorting
        // is, i+1 Hence we check if arr[i] is equal to i+1
        // or not
        for (int i = 0; i < arr.length; i++) {
            // Condition check for figuring out correct
            // element
            if (arr[i] != (i + 1))
            {
                // If the above condition is not fulfilled
                // i.e, if arr[i]!=i+1 that means the
                // correct element needs to be swapped with
                // the current one.
                // Find the index of the element i+1 from
                // the hashmap
                index = index_table.get(i + 1);
                // Swapping the element
                arr[index] = arr[i];
                arr[i] = i + 1;
                // Variable keeping a count of the number of
                // swaps
                swap++;
                // Updating the hashmap
                index_table.put(arr[i], i);
                index_table.put(arr[index], index);
            }
        }
        // Returning the swap counts
        return swap;
    }
    // Scnnere Class object to take unput from user
    private static final Scanner scanner
        = new Scanner(System.in);
    // Method 2
    // Main driver method
    public static void main(String[] args)
        throws IOException
    {
        // Creating an object of BufferedWriter to read
        // input fro te use
        BufferedWriter bufferedWriter = new BufferedWriter(
            new FileWriter(System.getenv("OUTPUT_PATH")));
        // Storing the non-primitive datatype
        // Here, Integer value
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        // Creating arrays
        // Array 1
        // Creating an Integer array o size N
        int[] arr = new int[n];
        // Array 2
        // Creating an String array
        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }
        int res = minimumSwaps(arr);
        bufferedWriter.write(String.valueOf(res));
        // Getting to new line
        bufferedWriter.newLine();
        // No further input will be accepted
        // isong the close()  method
        bufferedWriter.close();
        // Closing the inputs
        scanner.close();
    }
}

输出:

输入:

4 3 1 2 5

输出:

3


推荐阅读
  • 本文介绍了Android开发中Intent的基本概念及其在不同Activity之间的数据传递方式,详细展示了如何通过Intent实现Activity间的跳转和数据传输。 ... [详细]
  • 本文介绍如何使用布局文件在Android应用中排列多行TextView和Button,使其占据屏幕的特定比例,并提供示例代码以帮助理解和实现。 ... [详细]
  • 在 Flutter 开发过程中,开发者经常会遇到 Widget 构造函数中的可选参数 Key。对于初学者来说,理解 Key 的作用和使用场景可能是一个挑战。本文将详细探讨 Key 的概念及其应用场景,并通过实例帮助你更好地掌握这一重要工具。 ... [详细]
  • 深入理解Redis的数据结构与对象系统
    本文详细探讨了Redis中的数据结构和对象系统的实现,包括字符串、列表、集合、哈希表和有序集合等五种核心对象类型,以及它们所使用的底层数据结构。通过分析源码和相关文献,帮助读者更好地理解Redis的设计原理。 ... [详细]
  • 本文将深入探讨如何在不依赖第三方库的情况下,使用 React 处理表单输入和验证。我们将介绍一种高效且灵活的方法,涵盖表单提交、输入验证及错误处理等关键功能。 ... [详细]
  • 在Java中,this是一个引用当前对象的关键字。如何通过this获取并显示其所指向的对象的属性和方法?本文详细解释了this的用法及其背后的原理。 ... [详细]
  • PostgreSQL 10 离线安装指南
    本文详细介绍了如何在无法联网的服务器上进行 PostgreSQL 10 的离线安装,并涵盖了从下载安装包到配置远程访问的完整步骤。 ... [详细]
  • Startup 类配置服务和应用的请求管道。Startup类ASP.NETCore应用使用 Startup 类,按照约定命名为 Startup。 Startup 类:可选择性地包括 ... [详细]
  • 自己用过的一些比较有用的css3新属性【HTML】
    web前端|html教程自己用过的一些比较用的css3新属性web前端-html教程css3刚推出不久,虽然大多数的css3属性在很多流行的浏览器中不支持,但我个人觉得还是要尽量开 ... [详细]
  • 本文详细探讨了 Django 的 ORM(对象关系映射)机制,重点介绍了其如何通过 Python 元类技术实现数据库表与 Python 类的映射。此外,文章还分析了 Django 中各种字段类型的继承结构及其与数据库数据类型的对应关系。 ... [详细]
  • 本文详细介绍了Java库中com.vividsolutions.jts.io.WKTWriter类的appendGeometryCollectionText()方法,并提供了实际代码示例,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 本文介绍了 Elasticsearch 中常见的字段数据类型,包括文本、数值、日期、布尔值、二进制、范围、复杂对象和地理位置等类型,并详细说明了它们的应用场景和特点。 ... [详细]
  • 探讨如何从数据库中按分组获取最大N条记录的方法,并分享新年祝福。本文提供多种解决方案,适用于不同数据库系统,如MySQL、Oracle等。 ... [详细]
  • 20100423:Fixes:更新批处理,以兼容WIN7。第一次系统地玩QT,于是诞生了此预备式:【QT版本4.6.0&#x ... [详细]
  • 开发笔记:2020 BJDCTF Re encode
    开发笔记:2020 BJDCTF Re encode ... [详细]
author-avatar
靠谱同学轻松1988
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有