给定一个整数数组nums包含4个整数的数组nums,其数字都在1到3之间(包括1？

来源：蜘蛛抓取(WebSpider) 时间：2022-10-30 08:10 标签： 给定一个整数数组nums

本文参考自《剑指offer》一书，代码采用Java语言。

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。

从哈希表的思路拓展，重排数组：把扫描的每个数字(如数字m)放到其对应下标(m下标)的位置上，若同一位置有重复，则说明该数字重复。

(在动手写代码前应该先想好测试用例)

JFileChooser文件选择器是Swing中经常用到的一个控件.它的使用主要包含以下几个参数: 1.当前路径.也就是它第一次打开时所在的路径,许多软件喜欢设置为桌面. 2.文件过滤器.通过设置文件 ...

距离上一次开发SpringMVC项目已经过去了大半年,有些细节已经开始遗忘,今天复习一下 先从标签说起: 和struts有各种配置文件不同,spring用标签开发. 1.@Controller在Spr ...

给定一个正数数组arr，其中每个值代表砖块长度。所有砖块等高等宽，只有长度有区别，每一层可以用1块或者2块砖来摆。要求每一层的长度一样
要求必须使用所有的砖块，请问最多摆几层

首先我们可以将数组arr排个序。然后了本题使用双指针的方法就能够搞定，就只有两种可能性。首先我们就要想了砖块长度最大的砖块，它就只有两种选择第一种选择自己单独作为一层，第二种选择就只能和砖块长度最小的砖块作为一层，可能就有老铁问了为什么只能和长度最小的砖块作为一层，这是因为题目要求砖块必须都用，并且每一层的宽度要一样。此时如果宽度最长的和其它的砖块结合了，那么长度最小的和谁配了？所以长度最长的只能和长度最短的配。就只有这两种可能性将这两种可能性的答案累加起来就是答案。

给定一个字符串形式的数，比如"3421"或者"-8731"，如果这个数不在 - 范围上，那么返回"NODATA"。如果这个数在 - 范围上，那么这个数就没有超过16个二进制位所能表达的范围，返回这个数的2进制形式的字符串和16进制形式的字符串，用逗号分割。

本题的解题思路很简单直接干就是了。首先我们可以将这个字符串转换问为一个int类型的整数。在这之前我们可以判断一下这个字符串的长度是否超过6位如果超过了直接返回“NODATA"即可。因为-长度最长也就只有6位，所以如果超过了6位我们返回即可。将其转换为整型之后，我们把低16位的数据提取出来即可。如何提取了我们只需要使用0xffff和转换的这个数字按位与即可。这样一来16个比特位的信息我们都有了，二进制形式直接遍历即可是1就填1是0就填0.现在我们只要把16进制搞定了这道题就做完了
而十六进制我们只需要每次提取4位根据他的值进行判断即可。具体我们看看代码吧

本题其实是最长递增子序列的变形题。这题也有点这个希尔排序分支的意思。按照题目的意思我们可以将没k 个数取一个元素，分为若干组，例如当 k=3时
下面我们看一张图就更清楚了
将这个数组分成k组之后，我们分别求每一组里面最长不严格递增子序列的长度，在用这一组的个数减去最长不严格递增子序列的长度就是需要修改的次数。在这里需要注意的是每一组的元素个数可能不相同，假设数组的长度为N，那么最多只有（N+k-1）/k也就是N/K向上取整个元素。每一组我们都这么干，将每一组需要修改的次数累加上来最终就是我们想要的答案。

思考？如果从非递减改成严格递增此时又该怎么做?

把每个数减去其下标，然后对所有正整数求最长非降子序列。

举个例子，现在每 k 个数选一个数，假设选出来的数组是 [3,2,4,5,5,6,6]。

对这个数组中的正整数求最长非降子序列，那就是 [1,1,1]了，对应原始数组的 [,2,,,5,6,]，这三个数字保留，其余数字修改完成后就是 [1,2,3,4,5,6,7]，符合严格递增且均为正整数的要求。

注：上述减去下标的技巧，主要是为了能让保留的数字之间可以容纳严格递增的数字。否则，若直接按照最长严格递增子序列的求法，会得到例如 [,2,4,5,,6,*] 这样的错误结果。

小美有一个长度为n的数组，为了使得这个数组的和尽量大，她向会魔法的小团进行求助。小团可以选择数组中至多两个不相交的子数组，并将区间里的数全都变为原来的10倍，小团想知道他的魔法最多可以帮助小美将数组的和变大到多少?

本题难度很大个人认为？首先我们说一下暴力方法。首先我们求一个数组的累加和数组，从[0…N-1)范围内枚举划分点。假设划分点为split,那么对应这个划分点我们可以求[0…split]范围内最多有一个魔法子数组的情况下最大累加和是多少，[split…N-1]范围内最多有一个魔法子数组的情况下最大累加和是多少。把这两个区间的累加和加起来就是当前划分点所能获得的最大累加和，然后我们在尝试下一个划分点，更新答案。每个划分点我们都这样搞那么答案一定就在其中。那么如何求一个范围内最多有一个魔法子数组的最大累加和了？
第一种情况就是这个范围不使用魔法，那么就是原始数组的累加。
第二种情况需要使用魔法，此时我们可以枚举这个范围内所有的子数组对这个子数组使用魔法其它子数组加上原始累加和即可。

但是获取每个范围内最大累加和我们是使用暴力枚举的方式进行的。如果我们能够省掉这个枚举那么这个时间复杂度就变为了线性时间。下面我们来介绍一下dp的方法是如何来实现的。下面我们解释一下dp[i]的含义
dp[i]的含义代表arr[0…i]最多有一个魔法子数组的最大累加和，如果我们能够求出来，那么我们在反着求一遍.即dp1[i]代表这个arr[i…N-1]范围内最多有一个魔法子数组的情况下最大累加和是多少。如果我们能够求出来那么我们只需要将其拼接起来就可以了。下面我们我们来分析一下可能性

  • 可能性1：arr[0…i]不使用魔法也就是没有这个魔法子数组，那么最大累加和就是原始数组[0…i]范围内的累加和。
  • 可能性2：arr[0…i]范围内存在魔法子数组那么此时就又有两种小情况了。

下面我们一个一个来分析这两种小情况的可能性
可能性1：arr[i]不在10倍区域里面，那么此时答案就是arr[i]+dp[i-1]也就是当前位置的值+arr[0…i-1]范围内最多只有一个魔法数组的最大累加和
可能性2：arr[i]在10倍区域里面，此时我们有要分情况了
2.arr[i]决定往左边扩但是此时干了我们不知道他要扩多远。

对于这种情况我们该如何解决了此时我们需要知道arr[0…i-1]范围内i-1位置必须在10倍区域里面的情况下最大累加和是多少。因此我们需要在定义一个动态规划magic[i]，他的含义是arr[i]必须在10倍区域里面最大累加和是多少。这个动态规划求起来很简单。第一种情况就是arr[i]位置单独，第二种情况就是往左扩那么不就是arr[i]*10+magic[i-1]吗？然后我们在反着求一遍。这个问题就解决了

我要回帖

更多关于 给定一个整数数组nums 的文章

 

随机推荐