数组(一)
LeetCode 是个很好的刷题网站,然而咱们应该怎么刷呢?自觉的刷题不仅效率不高,笼罩的知识面也十分无限,所以从明天开始我会陆续分享本人做题的路线,心愿此时在看我博客的你能有所方向,咱们一起加油!多说无益,撸起袖子开始干!
内容用 Java 语言编写
数组 (一) 系列题型如下
数组的遍历(485)
485 题:最大间断 1 的个数
给定一个二进制数组,计算其中最大间断 1 的个数
示例:
输出:[1,1,0,1,1,1]
输入:3
解释:结尾的两位和最初的三位都是间断 1,所以最大间断 1 的个数是 3.
提醒 :
输出的数组只蕴含 0 和 1。输出数组的长度是正整数,且不超过 10,000。
暴力解法(MyCode)
看到这类数组的遍历问题,我想到的第一个解法就是暴力解决
比拟大小能够用此 Math 函数 max = Math.max(mid, max);
或者应用三目运算 max=mid>max?mid:max;
/**
* max 返回间断 1 的最大数量
* mid 两头比拟大小的介质
*/
class Solution {public int findMaxConsecutiveOnes(int[] nums) {
int max=0,mid=0;
for(int i=0;i<nums.length;i++){if(nums[i]==1)
mid++;
else {if(mid>max){max=mid;}
mid=0;
}
}
if(mid>max)
max=mid;
return max;
}
}
执行用时:2 ms, 在所有 Java 提交中击败了 89.40% 的用户
内存耗费:40.4 MB, 在所有 Java 提交中击败了 5.03% 的用户 '
双指针(Other’s Code)
先献上我对这个代码的思路和想法,我感觉双指针算法思路挺不错!
class Solution {public int findMaxConsecutiveOnes(int[] nums) {
int n = nums.length;
int ans = 0;
for (int i = 0, j = 0; i < n; j = i) {if (nums[i] == 1) {while (j + 1 < n && nums[j + 1] == 1) j++;
ans = Math.max(ans, j - i + 1);
i = j + 1;
} else {i++;}
}
return ans;
}
}
统计数组中的元素(697)(442)
697 题:数组的度
给定一个非空且只蕴含非正数的整数数组 nums,数组的度的定义是指数组里任一元素呈现频数的最大值。
你的工作是在 nums 中找到与 nums 领有雷同大小的度的最短间断子数组,返回其长度。
示例 1:
输出:[1, 2, 2, 3, 1]
输入:2
解释:输出数组的度是 2,因为元素 1 和 2 的呈现频数最大,均为 2.
间断子数组外面领有雷同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短间断子数组 [2, 2] 的长度为 2,所以返回 2.
示例 2:
输出:[1,2,2,3,1,4,2] 输入:6
提醒:
nums.length 在 1 到 50,000 区间范畴内。
nums[i] 是一个在 0 到 49,999 范畴内的整数。
哈希表(MyCode)
先介绍一下哈希表的基础知识
HashMap 是一个散列表,它存储的内容是键值对 (key-value) 映射。HashMap 实现了 Map
接口,依据键的 HashCode 值存储数据,具备很快的访问速度,最多容许一条记录的键为 null,不反对线程同步。HashMap
是无序的,即不会记录插入的程序。HashMap 继承于 AbstractMap,实现了
Map、Cloneable、java.io.Serializable 接口。艰深的讲就是通过哈希表生成 key-value 一一对应的关系
HashMap<Integer, int[]> map = newHashMap<Integer, int[]>();
生成 key 为 integer 类型的值对应 int 类型的数组(value)
应用数组的目标就是想达到一对多的作用相似函数的映射关系
/**
* 我谈谈看到这道题的感触,首先这道题特地不好了解,实现的难度也很大,我一开始是想用链表去实现更加不便,然而
* 我的能力很无限,最初我决定由 HashMap 解决
* 首先我想到的是就是要将度,首索引和尾索引存到 HashMap 中的 value, 便想到使用数组。* 我遇到了一个问题当初还是不能明确如下
* map.get(nums[i])[0]=1;
* map.get(nums[i])[1]=i;
* map.get(nums[i])[2]=i;
* 以上三条语句和底下这一条有什么区别吗?* map.put(nums[i], new int[]{1, i, i});
* 谬误提醒:java.lang.NullPointerException
* 通过我的查找:* NullPointerException 即空指针异样,俗称 NPE。如果一个对象为 null,调用其办法或拜访其字段就会产生这个异样
* 问题出在给数组初始化的问题,呈现数组援用对象为 null
* 遍历解法有点暴力解决的做法,而后我开始搜寻他人的代码,多去学习学习!!*/
class Solution {public int findShortestSubArray(int[] nums) {HashMap<Integer, int[]> map = new HashMap<Integer, int[]>();
// 将度,首索引和尾索引填入到 HashMap
for(int i=0;i<nums.length;i++){
//
if(map.containsKey(nums[i])){map.get(nums[i])[0]++;
map.get(nums[i])[2]=i;
}else{map.put(nums[i], new int[]{1, i, i});
}
}
// 遍历 HashMap
int maxdegree=0,minlen=0;
int[] len = new int[50000];
for(int i=0;i<nums.length;i++){len[nums[i]]=map.get(nums[i])[2]-map.get(nums[i])[1]+1;
if(map.containsKey(nums[i])){if(maxdegree<map.get(nums[i])[0]){maxdegree=map.get(nums[i])[0];
minlen=len[nums[i]];
}else if(maxdegree==map.get(nums[i])[0]){if(len[nums[i]]<minlen){minlen=len[nums[i]];
}
}
}
}
return minlen;
}
}
执行用时:28 ms, 在所有 Java 提交中击败了 28.91% 的用户
内存耗费:43 MB, 在所有 Java 提交中击败了 41.46% 的用户
数组法(Other’s Code)
不出名大佬的 2ms 模板,超过了百分百, 多看一些大佬的代码,的确很棒!感觉很受用!必须赞!!!
/**
* 看到代码的第一眼就发现了这两条代码比拟好奇,我抵赖我还是第一次看到
* int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
* 解释如下:* 在 JDK 中,整形类型是有范畴的,最大值为 Integer.MAX_VALUE,即 2147483647,* 最小值为 Integer.MIN_VALUE -2147483648。对整形最大值加 1,2147483648(越界了)* 那么此时值为多少呢?后果是 -2147483648,即是 Integer.MIN_VALUE。*
*/
class Solution {public int findShortestSubArray(int[] nums) {
int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
// 数组遍历 foreach
for (int i : nums) {
// 失去数组的最大值和最小值的边界
max = Math.max(i, max);
min = Math.min(i, min);
}
// 用于记录数组对应的度
int[] counts = new int[max - min + 1];
int countMax = 0;
for (int i : nums) {//++counts[i - min] 先自增 1,而后将 counts[i - min]代入运算
countMax = Math.max(countMax, ++counts[i - min]);
}
if (countMax == 1) return 1;
// 遍历统计数组
int minLength = nums.length;
for (int i = 0; i < counts.length; i++) {if (counts[i] == countMax) {
int tmp = min + i;
// 通过 start 和 end 别离从前后找到对应数的数组长度
int start = 0, end = nums.length - 1;
while (start < end && nums[start] != tmp) {start++;}
while (start < end && nums[end] != tmp) {end--;}
minLength = Math.min(minLength, end - start + 1);
}
}
return minLength;
}
442 题:数组中反复的数据
给定一个整数数组 a,其中 1 ≤ a[i] ≤ n(n 为数组长度), 其中有些元素呈现两次而其余元素呈现一次。
找到所有呈现两次的元素。
你能够不必到任何额定空间并在 O(n)工夫复杂度内解决这个问题吗?
示例:
输出: [4,3,2,7,8,2,3,1]
输入: [2,3]
反复标记法(Other’s Code)
看到这道题,外表上看起来很简略,然而当真正去满去“你能够不必到任何额定空间并在 O(n)工夫复杂度内解决这个问题吗?”这个条件的时候,发现有点机灵和蛊惑,想了很久还是无果,可能思维定势了!
/*
* 首先讲一下这个语句,我对这个去决定值示意异议,因为 1 ≤ a[i] ≤ n,那这个取绝对值不是
* 多此一举,然而当去掉绝对值的时候,报错起因就是有正数输出; 而后为啥是减去 1 呢?这个就要
* 思考数组下标越界的问题 0~num[n]-1
* int numFlag = Math.abs(nums[i]) - 1;
* 接下来就是辨别是否反复呈现,通过取反就能够标记呈现过一次,然而这个时候我又有纳闷了,* 题中提到的不是呈现 2 次吗?这只能判断呈现屡次呀!所以纠结的中央还挺多!!* (如果有大佬帮我一下,我不甚感谢!!)
* nums[numFlag] = -nums[numFlag];
* 最初就是多提一句就是 add() 办法将元素插入到指定地位的动静数组中。* countTwo.add(numFlag + 1);
*/
class Solution {public List<Integer> findDuplicates(int[] nums) {List<Integer> countTwo = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {int numFlag = Math.abs(nums[i]) - 1;
if (nums[numFlag] > 0) {nums[numFlag] = -nums[numFlag];
} else {countTwo.add(numFlag + 1);
}
}
return countTwo;
}
}
执行用时:7 ms, 在所有 Java 提交中击败了 76.21% 的用户
内存耗费:47.1 MB, 在所有 Java 提交中击败了 82.68% 的用户
计数排序(MyCode)
惟一有余的是违反了题意,然而发明靠近 100% 执行效率以及没有我上面对问题
/*
* 这里我就不多说了,应该特地好了解吧!*/
class Solution {public List<Integer> findDuplicates(int[] nums) {List<Integer> list = new ArrayList<>();
int[] countTwo = new int[nums.length + 1];
for(int i = 0; i<nums.length;i++){countTwo[nums[i]]++;
}
for (int i = 1; i <= nums.length; i++) {if (countTwo[i] == 2)
list.add(i);
}
return list;
}
}
执行用时:4 ms, 在所有 Java 提交中击败了 99.95% 的用户
内存耗费:47.4 MB, 在所有 Java 提交中击败了 44.70% 的用户
数组的扭转和挪动(665)
665 题:非递加数列
给你一个长度为 n 的整数数组,请你判断在 最多 扭转 1 个元素的状况下,该数组是否变成一个非递加数列。
咱们是这样定义一个非递加数列的:对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]
示例 1:
输出: nums = [4,2,3] 输入: true 解释: 你能够通过把第一个 4 变成 1 来使得它成为一个非递加数列。
示例 2:
输出: nums = [4,2,1] 输入: false 解释: 你不能在只扭转一个元素的状况下将其变为非递加数列。
提醒:
1 <= n <= 10 ^ 4
- 10 ^ 5 <= nums[i] <= 10 ^ 5
比较法(MyCode)
看到这类题型,得了解非递增数列,就是相邻的数组元素之间都是递增或者不增的数列,看起来简略然而思考起来还是磕磕碰碰!!
// 重点了解这句
if (i > 0 && nums[i + 1] < nums[i - 1]) {nums[i + 1] = nums[i];
}
class Solution {public boolean checkPossibility(int[] nums) {
int turn = 0;
for (int i = 0; i < nums.length - 1; ++i) {if (nums[i] > nums[i + 1]) {
turn++;
if (turn > 1) {return false;}
if (i > 0 && nums[i + 1] < nums[i - 1]) {nums[i + 1] = nums[i];
}
}
}
return true;
}
}
执行用时:1 ms, 在所有 Java 提交中击败了 99.98% 的用户
内存耗费:39.5 MB, 在所有 Java 提交中击败了 97.22% 的用户
贪婪法(Other’s Code)
大佬的想法很清晰,就是抓住两头过程的 ” 降落 ” 相似四边形的顶点 则返回 False
如果存在 i,使的 nums[i+1]<nums[i],咱们就说呈现了一次“降落”
分 3 种状况:
1、不存在降落的状况,即降落次数为 0,返回 true。
2、只呈现了 1 次降落,将降落后的元素记为 nums[x]
此时,能够尝试将 nums[x-1]变小,或者将 nums[x]变大,以达到“非递加”的目标。如果 x = 1 或者 x =n-1, 只须要将 nums 中第一个元素减小(最差到 Integer.MIN_VALUE),或者最初一个元素增大总能满足要求;如果 1 <x<n-1,若将 nums[x]变大必须要求 nums[x-1]<=nums[x+1]
亦即,x 前后的两个元素不能再“捣鬼”。若将 nums[x-1]变小,须要求 nums[x-2]<=nums[x]
亦即,x- 1 前后的两个元素不能再“捣鬼”。
3、呈现超过 1 次的降落,必定不同只通过调整一个元素实现要求,返回 false。
class Solution {public boolean checkPossibility(int[] nums) {
int n = nums.length;
if (n <= 1) return true;
int down = 0;
for (int i = 1; i < n; i++) {if (nums[i] < nums[i - 1]) {
down++;
if (down > 1) {return false;}
if (i > 1 && i < n - 1 && nums[i - 1] > nums[i + 1] && nums[i - 2] > nums[i]) {return false;}
}
}
return true;
}
}
二维数组及滚动数组(119)
119 题:杨辉三角 II
给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
输出: 3
输入: [1,3,3,1]
进阶:你能够优化你的算法到 O(k) 空间复杂度吗?
递归算法(MyCode)
因为超出运算工夫的限度,我也不晓得我的代码有没有问题,然而我还是想要分享进去,大家一起看一看,可能有不同的思维碰撞,每个人都不应该悭吝本人的思维,能力发明出更好的算法!!
class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> listHead = new ArrayList<>();
List<Integer> listTail = new ArrayList<>();
if(rowIndex == 0){listTail.add(1);
}if(rowIndex == 1){listTail.add(1);
listTail.add(1);
}else {listHead = getRow(rowIndex-1);
listTail.add(1);
for(int i = 1;i<rowIndex;i++){int sum = listHead.get(i-1)+listHead.get(i);
listTail.add(sum);
}
listTail.add(1);
}
return listTail;
}
}
线性递推(Other’s Code)
这个是官网的解题思路,我感觉我的境界还差的太远他用了一条外围代码诠释了什么是大神!!— row.add((int) ((long) row.get(i – 1) * (rowIndex – i + 1) / i));
class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> row = new ArrayList<Integer>();
row.add(1);
for (int i = 1; i <= rowIndex; ++i) {row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i));
}
return row;
}
}
执行用时:0 ms, 在所有 Java 提交中击败了 100.00% 的用户
内存耗费:35.9 MB, 在所有 Java 提交中击败了 96.97% 的用户
集体总结
回想当初,刚进大学,糊涂无知,想着怎么多把课程问题学到最好以及退出学生会的想法,我感觉真正学到的货色太少了,当初作为大二的我开始刷题,我感觉也为时不晚,所以我开始我的 LeetCode 的刷题之路,我想的是每周做 5 道同时记录在博客,再次大家做个见证,感兴趣的也能够退出我 的队伍中,咱们一起后退!!加油!!