数组(一)
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道同时记录在博客，再次大家做个见证，感兴趣的也能够退出我 的队伍中，咱们一起后退！！加油！！