数组

力扣 27题 移除数组元素 给你一个数组 nums 和一个值 val，你须要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要应用额定的数组空间，你必须仅应用 O(1) 额定空间并 原地 批改输出数组。元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素。 阐明:为什么返回数值是整数，但输入的答案是数组呢?请留神，输出数组是以「援用」形式传递的，这意味着在函数里批改输出数组对于调用者是可见的。你能够设想外部操作如下:// nums 是以“援用”形式传递的。也就是说，不对实参作任何拷贝int len = removeElement(nums, val);// 在函数里批改输出数组对于调用者是可见的。// 依据你的函数返回的长度, 它会打印出数组中 该长度范畴内 的所有元素。for (int i = 0; i < len; i++) {    print(nums[i]);} 示例 1：输出：nums = [3,2,2,3], val = 3输入：2, nums = [2,2]解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不须要思考数组中超出新长度前面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。示例 2：输出：nums = [0,1,2,2,3,0,4,2], val = 2输入：5, nums = [0,1,4,0,3]解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。留神这五个元素可为任意程序。你不须要思考数组中超出新长度前面的元素。起源：力扣（LeetCode）链接：https://leetcode.cn/problems/remove-element著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。解决方案，双指针法工夫复杂度 O(n)空间复杂度 O(1) ...

这个问题其实就是一个十分根底的面试题，个别面试官想理解你基础知识方面的把握时，根本都会问这个问题，尤其是一些，计算机学子毕业之后，如果还是想要从事计算机技术相干的行业时，那么在面试的时候就须要做好短缺的筹备，因为联合本身思考，大部分刚毕业的计算机专业的同学并没有相干的我的项目教训。 所以依据个别公司的面试环节，面试官会从：本身基础知识储备、我的项目教训、工作态度、集体能力等几个大方面动手，那么针对以上这几点，如果投递简历时，公司在审核简历时针对刚毕业的大学生简历，都会提前跟面试官沟通好，这个时候面试官就会间接跳过我的项目问题，简略间接的次要针对基础知识问题，会问的很多，所以，从事计算机行业，如果不想被淘汰，你就须要每天一直学习减少常识储备量。那么做好心理建设的敌人咱们就持续来理解这个java根底知识点吧，从这一刻开始，每天储备一点基础知识，滴水也可汇成汪洋，毕竟千里之行;始于足下嘛！ 那么针对数组和汇合的区别，咱们就先来简略的唠唠区别吧！首先咱们须要明确：什么是数组？ 数组（Array）：用来有序排列同类数据元素的汇合被称为数组（数组是一个能够存储一组或一系列相干数据的容器），数组中的每个元素都具备雷同的数据类型，在计算机语言中，数组是十分重要的汇合类型，数组的三个基本特征体现在：一致性（像数组它只能保留雷同数据数据类型的元素，能够是任何雷同的数据类型）、有序性（数组中的元素都是有序的，次要通过下标进行拜访）、不可变性（数组一旦开始初始化，则数组的长度是不可变的）。数组有两种创立形式：动静初始化（指定长度），动态初始化（指定内容）。 总体来说数组次要的特点就是： 1.长度是确定的，数组一旦被创立，它的大小就是不可变的 2.数组中的元素类型必须是雷同类型，不容许呈现混合类型 3.数组既能够存储根本数据类型，又能够存储援用数据类型（根本数据类型存储的是值， 援用数据类型存储的是地址值） 4.数组变量属于援用类型，数组也是对象，数组中的元素相当于对象的属性 5.数组由索引（索引的作用是不便查找元素，索引从0开始到数组的长度-1完结）和数组元素组成 6.通常应用for循环来实现对数组的遍历好嘞！敌人们，以上就是针对于数组的大抵简说，接下来咱们要来说说汇合了，理解完数组，再理解完，想必大家就能够对数组和汇合的区别做出论断啦！请问什么是汇合呢？ 上次曾经给大家做过对于汇合问题的答复了，大家也能够参考参考哦！那么既然曾经具体解说了，上面我就只做简述喽！其实在学习java的过程中亦或者是工作中，咱们始终都是在跟数据打交道，比方怎么把这个数据传输上来，又怎么接管这个数据呢，这个数据如何保留呢？这些都是大家在解决数据时最根底的问题了，特地像咱们切菜的时候，咱们要找碟子或者碗将切好的菜寄存起来，而在日常生活中，像这类用作贮存的容器特地多，像碗啊、碟子啊、食品包装袋啊、纸箱子等。 甚至咱们寓居的房子也是一个大号的容器啊，他们都有一个对立的特点，那就是“能装”，不同的就是他们的包容量不同，他们有各式各样的样子，随着生存的一直进步，这些容器的样子也是越来越难看，这些容器不仅让咱们的生存东倒西歪起来，也进步了咱们的生存品质。同样的，在java中也存在各种各样的“容器”，咱们把java中所有“容器”的总称，称为汇合。 就像图片中显示的就是汇合中的容器，它们存储数据的模式也是各不相同的，简略来说，汇合就是一个放数据容器，它次要包含Collection和Map汇合，汇合只能寄存对象，Java汇合类寄存于java.util包中，Java中每一种根本数据类型都有对应的援用类型。例如在汇合中存储一个int型数据时，要先主动转换成Integer类后再存入。 那么针对单列汇合Conllection和双列汇合Map它们各自又有什么不同的特点呢？大家能够参考之前的答复（比拟具体），这里给大家简略总结，大家简略看看： 综合以上对汇合的理解大家当初也能总结进去数组和汇合到底有什么区别了吧！ 1.数组是动态的，有固定大小，且创立之后无奈扭转；而汇合是能够动静扩容的，能够依据须要动静扭转大小。如果要存储根本数据类型，并且也有固定的个数，如果元素个数是固定的，举荐用数组如果元素个数不是固定的， 举荐用汇合，因为数组的长度是固定的（数组是动态的，一个数组实例具备固定大小，一旦创立，无奈扭转），汇合长度是能够扭转的（依据须要动静扭转大小，而且汇合提供了更多的成员办法，能够满足更多的需要），简略来说，元素个数固定，举荐应用数组，若元素个数不固定，举荐应用汇合。 2.数组既能够存储根本数据类型，又能够存储援用数据类型（根本数据类型存储的是值， 援用数据类型存储的是地址值）；汇合只能存储援用数据类型（也就是对象）， 汇合中也能够存储根本数据类型，然而在存储的时候会主动装箱（JDK1.5新个性）变成对象。 3.数组和汇合都是java中的容器，然而数组申明了它包容的元素类型，而汇合不申明。 4.数组是java语言内置的数据类型，是线性排列的数组，所以能够快速访问元素，正因为数组有这样的长处，大家能够看到很多汇合的底层构造就是数组。 5.应用场景不同，数组个别应用在数据长度固定的状况，并且次要进行的是数据的查找操作。而汇合个别是用在须要同时存储具备一对一关系的数据，也就是保留键值对数据的状况下，都是应用汇合，并且在解决数据反复问题的时候就能够间接应用Set汇合解决这个问题（Set汇合的特点是元素惟一，且不可反复）。 6.咱们在定义数组的时候必须指定数组元素的类型，然而汇合如果不定义的话就默认所有的元素都是Object（Object类是所有类的父类）。 7.咱们无奈间接获取数组中理论存储的元素个数，应用length（）也只能获取数组的长度，然而汇合能够间接用size（）间接获取汇合中理论存储的元素个数。 8.汇合有多种实现形式和不同的实用场合，比方：List、Set、Map等，然而数组只采纳调配间断的空间形式。 而且汇合以接口和类的模式存在，具备封装、继承、多态等对于类的特点，所以通过办法和属性的调用就能够实现一些各种简单的操作，这样能够无效的进步软件的开发效率。 好啦，以上就是针对这个问题的一些介绍，离开做了介绍，也给大家做了总结，大家能够参考利用哦，也祝各位筹备面试的宝子们，年后面试顺利！

数组中反复的值如[1,3,4,1,3,5,2,6,3,7,4,2,1,1,1,1,1]数组中不容许反复 第一步：创立一个空数组第二步： for遍历拿到a的所有值控制台你一眼就明确线路是一个一个往里接 var a = [1, 3, 4, 3, 5, 2, 6, 3, 7, 4, 8]var result = []for (var i = 0; i < a.length; i++) { result.push(a[i]) console.log(result)} 第三步：判断是否反复咱们抉择了indexof，判断有没有雷同的，如果他找不到肯定返回-1每次他找到雷同！就用continue，而且他是最初增加！如果反复会被他干掉。push也进不去 var a = [1, 3, 4, 1, 3, 5, 2, 6, 3, 7, 4, 2,1,1,1,1,1] var result = [] for(var i=0; i<a.length; i++) { if(result.indexOf(a[i]) >=0){ continue } result.push(a[i]) } console.log(result)最初一步为了更加完满，最初来个排序 var a = [1, 3, 4, 3, 5, 2, 6, 3, 7, 4, 8,1,1,1,1,1,1]var result = []for(var i=0; i<a.length; i++){ if(result.indexOf(a[i])>=0){ continue } result.push(a[i]) console.log(result)}console.log(result)console.log(result.sort())//或者localeCompare避免汉子无奈排序result.sort((a,b)=>{ return a.localeCompare(b)})

在理论开发中，有很多场景须要咱们将数组元素依照从大到小（或者从小到大）的顺序排列，这样在查阅数据时会更加直观，例如：一个保留了班级学号的数组，排序后更容易分区好学生和坏学生；一个保留了商品单价的数组，排序后更容易看出它们的性价比。 对数组元素进行排序的办法有很多种，比方冒泡排序、归并排序、抉择排序、插入排序、疾速排序等，其中最经典最须要把握的是「冒泡排序」。 以从小到大排序为例，冒泡排序的整体思维是这样的：从数组头部开始，一直比拟相邻的两个元素的大小，让较大的元素逐步往后挪动（替换两个元素的值），直到数组的开端。通过第一轮的比拟，就能够找到最大的元素，并将它挪动到最初一个地位。第一轮完结后，持续第二轮。依然从数组头部开始比拟，让较大的元素逐步往后挪动，直到数组的倒数第二个元素为止。通过第二轮的比拟，就能够找到次大的元素，并将它放到倒数第二个地位。以此类推，进行 n-1（n 为数组长度）轮“冒泡”后，就能够将所有的元素都排列好。 整个排序过程就如同气泡一直从水里冒出来，最大的先进去，次大的第二进去，最小的最初进去，所以将这种排序形式称为冒泡排序（Bubble Sort）。 上面咱们以“3 2 4 1”为例对冒泡排序进行阐明。 第一轮 排序过程3 2 4 1 （最后）2 3 4 1 （比拟3和2，替换）2 3 4 1 （比拟3和4，不替换）2 3 1 4 （比拟4和1，替换）第一轮完结，最大的数字 4 曾经在最初面，因而第二轮排序只须要对后面三个数进行比拟。 第二轮 排序过程2 3 1 4 （第一轮排序后果）2 3 1 4 （比拟2和3，不替换）2 1 3 4 （比拟3和1，替换）第二轮完结，次大的数字 3 曾经排在倒数第二个地位，所以第三轮只须要比拟前两个元素。 第三轮 排序过程2 1 3 4 （第二轮排序后果）1 2 3 4 （比拟2和1，替换） 至此，排序完结。算法总结及实现对领有 n 个元素的数组 R[n] 进行 n-1 轮比拟。 第一轮，一一比拟 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-1], R[N])，最大的元素被挪动到 R[n] 上。 ...

数组双指针双指针是一种罕用的解题思路，能够应用两个相同方向或雷同方向的指针扫描数组从而达到解题目标。值得注意的是，本书在不同的章节都提到了双指针。本书中的“指针”并不专指C语言中的指针，而是一个绝对宽泛的概念，是能定位数据容器中某个数据的伎俩。在数组中它实际上是数字的下标。 相同指针面试题6：排序数组中的两个数字之和 题目：输出一个递增排序的数组和一个值k，请问如何在数组中找出两个和为k的数字并返回它们的下标？假如数组中存在且只存在一对符合条件的数字，同时一个数字不能应用两次。例如，输出数组[1，2，4，6，10]，k的值为8，数组中的数字2与6的和为8，它们的下标别离为1与3。 /** * @param {number[]} numbers * @param {number} target * @return {number[]} */var twoSum = function(numbers, target) { let l = 0 let r = numbers.length - 1 while(l < r) { if(numbers[l] +numbers[r]===target) { return [l,r] } else if(numbers[l] +numbers[r]>target) { r-- } else { l++ } }};没啥好说的，相同指针的经典题目：2数之和，显著特色有序数组。 面试题7：数组中和为0的3个数字 题目：输出一个数组，如何找出数组中所有和为0的3个数字的三元组？须要留神的是，返回值中不得蕴含反复的三元组。例如，在数组[-1，0，1，2，-1，-4]中有两个三元组的和为0，它们别离是[-1，0，1]和[-1，-1，2]。 /** * @param {number[]} nums * @return {number[][]} */var threeSum = function(nums) { nums.sort((a, b) => a-b); let res = [] for(let i = 0; i < nums.length-2;i++) { // 去重 if (i > 0 && nums[i] == nums[i - 1]) continue let l = i+1; let r = nums.length-1 while(l < r) { // 怎么去重 if(nums[l]+nums[r]+nums[i]===0) { res.push([nums[i], nums[l], nums[r]]) while(l<r&&nums[l] === nums[++l]); while(l<r&&nums[r] === nums[--r]); } else if(nums[l]+nums[r]+nums[i]>0) { r-- } else { l++ } } } return res};首先是排序，难的是解决去重。 ...

给定一个 n × n 的二维矩阵 matrix 示意一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你须要间接批改输出的二维矩阵。请不要 应用另一个矩阵来旋转图像。 链接: 力扣LeetBook—高级算法—数组—旋转图像. 示例 1： 输出：matrix = [[1,2,3],[4,5,6],[7,8,9]]输入：[[7,4,1],[8,5,2],[9,6,3]]示例 2： 输出：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]输入：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]示例 3： 输出：matrix = [[1]]输入：[[1]]示例 4： 输出：matrix = [[1,2],[3,4]]输入：[[3,1],[4,2]]标签：数组、数学、矩阵 解题思路：先替换高低的值，再替换对角的值，便能解决该题的需要 拿示例1来说， n=3 ，先把原数组进行高低替换，如下：1   2   3       7   8   94   5   6 => 4   5   6 7   8   9       1   2   3 再进行对角替换，如下： 7   8   9       7   4   1 4   5   6 => 8   5   2 1   2   3       9   6   3 其中i==j的地位替换后也不会扭转 次要Go代码如下： func rotate(matrix [][]int) { n := len(matrix) for i := 0; i < n/2; i++ { matrix[i], matrix[n-1-i] = matrix[n-1-i], matrix[i] } for i := 0; i < n; i++ { for j := 0; j < i; j++ { matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] } }}提交截图： ...

原文地址：Array的练习Introduction实现Array相干练习。 RequirementDO NOT use vectors to process data in your function algorithms.This project can be a bit challenging as it involves working on and submitting three individual array processing-related programs (one for each scenario). For each program (a) carefully read the specification and the expected outcome (b) identify function types used, key types of parameters needed (value and reference) and the interface in main to test the function algorithms (c) write the algorithms with proper function setup (with function prototype and definitions - no inline function definitions) used to implement and meet the program specifications (d) test, debug algorithms written to ensure accurate output similar to the sample result provided and (e) finally set aside time to revisit the three completed programs to ensure proper program format, style, naming conventions and make sure to add function related documentation prior to submitting your project (no need to loose points for poor or none existent program documentation). ...

办法一 ：for循环 let arr = ['zhang','xu','liu'];//for循环for( i = 0; i < arr.length; i++){ console.log(arr[i]); // zhang // xu // liu}办法二 ：for...in... let arr = ['zhang','xu','liu'];//for...in...for(var index in arr){ console.log(arr[index]); // zhang // xu // liu}办法三 ： 利用map()办法遍历数组 let arr = ['zhang','xu','liu'];// 利用map()办法遍历数组let result = arr.map(function(item) { return item})console.log(result); //[ 'zhang', 'xu', 'liu' ]办法四 ： 利用forEach()遍历数组 let arr = ['zhang','xu','liu'];//利用forEach()遍历数组let res = arr.forEach(function(item,index,arr) { console.log(item,index);//数组元素 数组元素索引下标 数组 // zhang 0 // xu 1 // liu 2})办法五 ： 应用filter()遍历数组 ...

pop()pop() 办法用于删除数组的最初一个元素并返回删除的元素。 //myPop()// 还得思考当数组为空的状况Array.prototype.myPop = function ( ) { // 当传入的数组为空时 if(this.length == ''){ return undefined; }else{ var result = this[this.length - 1]; this.length--; return result; }}// 当数组为空时var arr = []// var arr = [2,4,4,5,6]; //6 返回最初一个元素6// console.log(arr);var result = arr.myPop();console.log(result); //undefined push()push() 办法可向数组的开端增加一个或多个元素，并返回新的长度。 //myPush()Array.prototype.myPush = function (params) { for(var i = 0; i < arguments.length;i++){ //把新增元素放到数组的最初地位 this[this.length] = arguments[i]; } return this.length;}var arr = [1,4,2,9];console.log(arr);var result = arr.myPush(1,3,4);console.log(arr);console.log(result); //[1, 4, 2, 9, 1, 3, 4]shift()shift() 办法用于把数组的第一个元素从其中删除，并返回第一个元素的值。 ...

解析List汇合子类ArrayList、Vector、LinkedList底层及扩容机制ArrayList特点高效率不平安有序 扩容机制1.应用无参结构器初始化时，会创立一个elementData的空数组，没有初始容量.2.当调用汇合第一次进行add操作时，会进行以后数组elementData是否是空判断，如果为空，则造成一个最小所需容量为10的最小长度，随后则进行扩容，如果依据所需容量计算的后果小于0，则进行新容量的反赋值操作，随后则调用Arrays.copyOf办法进行数组的赋值，并且实现赋值。3.当所需容量大于10的时候，则依照现有容量的1.5倍进行扩容，并实现赋值。4.应用有参结构时则应用有参结构初始化elementData数组，当容量不够时，同上3 private void grow(int minCapacity) { // overflow-conscious code // 以后数组的长度 int oldCapacity = elementData.length; // 计算扩容 int newCapacity = oldCapacity + (oldCapacity >> 1); // 当所需容量大于新容量的时候，则应用所需容量进行扩容 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }Vector汇合特点低效率平安有序 扩容机制1.应用无参结构初始化时，默认容量为10. /** * Constructs an empty vector so that its internal data array * has size {@code 10} and its standard capacity increment is * zero. */ public Vector() { this(10); }2.当所需容量小于现有容量时，会依照现有容量的2倍进行扩容 ...

// 第一种形式 removalRepeat (arr, uniqueKey) { let map = new Map() for (let i of arr) { if (!map.has(i[uniqueKey])) { map.set(i[uniqueKey], i) } } arr = [...map.values()] return arr}// 调用 this.removalRepeat(res.result.list,'id') // 第二种 let obj = {} // 去重 第一层 newList = newList.reduce((preVal, curVal) => { // provinceId就是数组中的provinceId字段 obj[curVal.provinceId] ? '' : (obj[curVal.provinceId] = true && preVal.push(curVal)) return preVal }, [])

简介： 咱们在开发中后盾利用或者中间件的时候，会存储一些数据在内存中以放慢访问速度。随着数据量的减少，除了能够搁置于堆外，还能够通过实时压缩来缓解。明天就给大家介绍一种压缩整形数组的形式。 作者 | 玄胤起源 | 阿里技术公众号 咱们在开发中后盾利用或者中间件的时候，会存储一些数据在内存中以放慢访问速度。随着数据量的减少，除了能够搁置于堆外，还能够通过实时压缩来缓解。明天就给大家介绍一种压缩整形数组的形式。 一 数据压缩数组指 long[] 或者 int[] 类型，在 Java 中利用很广。当数据量很大时，其内存占用的问题便突显进去，起因是一个 long 类型是占 8 个字节，而 int 也是占用 4 个字节，当有千万级别的数据时，其占用的空间便是上百 MB 级别的了。 1 去冗余首先想到的就是缩减每个数字占用的空间。因为咱们都晓得就负数而言，int 3 个字节以上即可示意 2^24 = 16M 即 1600 百万个数，而再往后，即应用第 4 个字节，绝大多数咱们是用不到的，但也不能砍掉，万一还会用到的；所以能够将高位去掉，是一种可行的思路，但必须动静去掉，该用的时候还是得用，这就须要存储用到多少个字节了（见图：数字压缩基本原理）。 数字压缩基本原理 示意数据占用字节数有两种形式：一是借用原数据的几位来示意，就拿 long 来说，咱们只须要借用 3 位就能够笼罩用到的字节数了（因为 23 = 8），因为 2^60 当前曾经是十分大的数了，简直用不到，所以咱们借用也根本不会产生负面成果；另一种就是利用字节最高位示意还有残余数据（见图2），Facebook 在 Thrift 中就是应用此办法来压缩传输数据的。总之，咱们就是要把 long 或者 int 数组压缩成 byte 数组，在应用时再根据 byte 数组中存储的信息将对应的数字还原。 解压时辨认数据大小办法 以上压缩思路在传输场景下能够很好的解决存取问题，因为都是后退先出的思路，然而如果咱们须要压缩后的构造依然具备数组的下标拜访能力怎么办？ 这里的难点是：之前每个数字都是固定长度，咱们能够通过 “[单个数字占用的字节数]*[第几个]” 很快地找到对应的内存地址，然而压缩过后每个数字占用的空间不是一样的，这种形式就生效了，咱们无奈得悉第 N 个数所处的内存地位。要取下标为 200 的值，难道只能线性查找 200 次吗？显然这样的效率是相当低的，其工夫复杂度就由 O(1) 降落为了 O(n)。有没有更好的方法呢？当然是有的。咱们能够建设索引（如下图），即： ...

这是JS 原生办法原理探索系列的第六篇文章，这次咱们来实现数组的 30 个 API。在开始之前，能够先看一下本文的思维导图： 文章分为四个局部，别离介绍在数组原生 API 中，会批改原数组的办法、不会批改原数组的办法、用于遍历的办法以及静态方法，共计 30 个。在讲每个办法的具体实现之前，会简要介绍它们的用法（更具体的查阅 MDN 即可），之后给出实现的思路和具体的代码。代码来源于本人思考以及对 polyfill 的参考，实测能够通过大部分测试用例，但不排除有更好的思路以及值得优化的中央，若发现任何谬误或者值得改良之处，欢送评论区留言斧正。 这是一些实现时须要留神的中央： 原型办法挂载在数组原型上。因为办法是通过数组实例调用的，所以咱们能够在办法外部通过 this 拿到调用者，也就是数组（如果怕批改到原数组，能够把这个 this 浅拷贝一份）大部分办法在遍历数组的时候，会跳过 empty 元素（空位），而有的办法却不会。因而，在遍历数组的过程中，要留神判断元素是不是 empty 元素 —— 能够用 in 判断，比方索引 1 的元素不是 empty，那么 1 in arr 是会返回 true 的。此外，也能够抉择用 for…in 遍历数组，它只会遍历出那些非 empty 元素的索引（留神：for...of 能够遍历出 empty 元素，遍历出的后果是 undefined）上面注释开始。 会扭转数组的办法pop用法pop 办法能够弹出数组最初一个元素，并将其作为返回值 const arr = [1,2,3]arr.pop() // 返回移除的元素 5，数组变成 [1,2,3,4] 实现Array.prototype.myPop = function(){ let arr = this let returnValue = arr[arr.length - 1] arr.length-- return returnValue}push用法push 办法能够往数组开端增加任意多个元素，并将数组长度作为返回值： ...

// 上移upData(text, record, index, column) { if (index === 0) { return; } else { // sort是排序 后端要的 this.tableData[index - 1].sort = Number(this.tableData[index - 1].sort) + 1; record.sort = Number(record.sort) - 1; } // 在上一项插入该项 this.tableData.splice(index - 1, 0, this.tableData[index]); // 删除后一项 this.tableData.splice(index + 1, 1); this.$message.success("上移胜利");}// 下移downData(text, record, index, column) { if (index === this.tableData.length - 1) { return; } else { // sort是排序 后端要的 this.tableData[index + 1].sort = Number(this.tableData[index + 1].sort) - 1; record.sort = Number(record.sort) + 1; } // 在下一项插入该项 this.tableData.splice(index + 2, 0, this.tableData[index]); // 删除前一项 this.tableData.splice(index, 1); this.$message.success("下移胜利");}// 删除this.tableData.splice(index, 1);

前言在开始学习之前，咱们想要告诉您的是，本文章是对 JavaScript 语言常识中 数组 局部的总结，如果您已把握上面常识事项，则可跳过此环节间接进入题目练习 数组简介定义数组数组赋值和应用数组的罕用办法数组的遍历如果您对某些局部有些忘记， 曾经为您筹备好了！ 数组简介数组（Array） 是 ECMAScript 中十分罕用的类型。ECMAScript 数组跟其余编程语言的数组有很大区别。跟其余语言中的数组一样，ECMAScript 数组也是一组有序的数据，但跟其余语言不同的是，数组中每个槽位能够存储任意类型的数据。这意味着能够创立一个数组，它的第一个元素是字符串，第二个元素是数值，第三个是对象。ECMAScript 数组也是动静大小的，会随着数据增加而主动增长。 定义数组有几种根本的形式能够创立数组。一种是应用 Array 构造函数，比方： let colors = new Array()如果晓得数组中元素的数量，那么能够给构造函数传入一个数值，而后 length 属性就会被主动创立并设置为这个值。比方，上面的代码会创立一个初始 length 为 20 的数组： let colors = new Array(20)也能够给 Array 构造函数传入要保留的元素。比方，上面的代码会创立一个蕴含 3 个字符串值的数组： let colors = new Array('red', 'blue', 'green')创立数组时能够给构造函数传一个值。这时候就有点问题了，因为如果这个值是数值，则会创立一个长度为指定数值的数组；而如果这个值是其余类型的，则会创立一个只蕴含该特定值的数组。上面看一个例子： let colors = new Array(3) // 创立一个蕴含 3 个元素的数组let names = new Array('Greg') // 创立一个只蕴含一个元素，即字符串"Greg"的数组在应用 Array 构造函数时，也能够省略 new 操作符。后果是一样的，比方： let colors = Array(3) // 创立一个蕴含 3 个元素的数组let names = Array('Greg') // 创立一个只蕴含一个元素，即字符串"Greg"的数组另一种创立数组的形式是应用数组字面量（array literal）表示法。数组字面量是在中括号中蕴含以逗号分隔的元素列表，如上面的例子所示： ...

稠密数组当一个数组中大部分元素为0，或者为同一个值的数组时，能够应用稠密数组来保留该数组。 稠密数组解决办法： 记录数组一共有几行几列，有多少不同的值把具备不同值的元素的行列及值记录在一个小规模的数组中，从而放大程序的规模6（row） 7(col) 0（默认值）

明天的知识点 (2020.12.12) —— 第606天 (我也要出题)[html] 如何给table中的某一列设置固定宽度[css] Scss和Sass有什么区别？[js] 说说你对稠密数组的了解[软技能] 在前端开发中，你有应用过二进制方面的常识吗？在哪些场景会用到？《论语》，曾子曰：“吾日三省吾身”（我每天屡次检查本人）。前端面试每日3+1题，以面试题来驱动学习，每天提高一点！让致力成为一种习惯，让奋斗成为一种享受！置信 保持 的力量！！！欢送在 Issues 和敌人们一起探讨学习！ 我的项目地址：前端面试每日3+1【举荐】欢送跟 jsliang 一起折腾前端，零碎整顿前端常识，目前正在折腾 LeetCode，打算买通算法与数据结构的任督二脉。GitHub 地址 微信公众号欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个Star, 同时欢送微信扫码关注 前端剑解 公众号，并退出 “前端学习每日3+1” 微信群互相交换（点击公众号的菜单：交换）。 学习不打烊，充电加油只为遇到更好的本人，365天无节假日，每天早上5点纯手工公布面试题（死磕本人，愉悦大家）。心愿大家在这虚夸的前端圈里，放弃沉着，保持每天花20分钟来学习与思考。在这变幻无穷，类库层出不穷的前端，倡议大家不要等到找工作时，才狂刷题，提倡每日学习！（不忘初心，html、css、javascript才是基石！）欢送大家到Issues交换，激励PR，感激Star，大家有啥好的倡议能够加我微信一起交换探讨！心愿大家每日去学习与思考，这才达到来这里的目标！！！（不要为了谁而来，要为本人而来！）交换探讨欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个[Star]

明天的知识点 (2020.12.07) —— 第601天 (我也要出题)[html] 说说你对H5媒体捕捉的了解，它有什么用处？[css] css变量有哪些浏览器反对？[js] js最大反对多少长度的数组？为什么？[软技能] 你平时喜爱看书吗？电子书还是实体书？为什么？《论语》，曾子曰：“吾日三省吾身”（我每天屡次检查本人）。前端面试每日3+1题，以面试题来驱动学习，每天提高一点！让致力成为一种习惯，让奋斗成为一种享受！置信 保持 的力量！！！欢送在 Issues 和敌人们一起探讨学习！ 我的项目地址：前端面试每日3+1【举荐】欢送跟 jsliang 一起折腾前端，零碎整顿前端常识，目前正在折腾 LeetCode，打算买通算法与数据结构的任督二脉。GitHub 地址 微信公众号欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个Star, 同时欢送微信扫码关注 前端剑解 公众号，并退出 “前端学习每日3+1” 微信群互相交换（点击公众号的菜单：交换）。 学习不打烊，充电加油只为遇到更好的本人，365天无节假日，每天早上5点纯手工公布面试题（死磕本人，愉悦大家）。心愿大家在这虚夸的前端圈里，放弃沉着，保持每天花20分钟来学习与思考。在这变幻无穷，类库层出不穷的前端，倡议大家不要等到找工作时，才狂刷题，提倡每日学习！（不忘初心，html、css、javascript才是基石！）欢送大家到Issues交换，激励PR，感激Star，大家有啥好的倡议能够加我微信一起交换探讨！心愿大家每日去学习与思考，这才达到来这里的目标！！！（不要为了谁而来，要为本人而来！）交换探讨欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个[Star]

摘要：在这篇文章里，将从各个角度介绍下std::array的用法，心愿能带来一些启发。td::array是在C++11规范中减少的STL容器，它的设计目标是提供与原生数组相似的性能与性能。也正因而，使得std::array有很多与其余容器不同的非凡之处，比方：std::array的元素是间接寄存在实例外部，而不是在堆上调配空间；std::array的大小必须在编译期确定；std::array的构造函数、析构函数和赋值操作符都是编译器隐式申明的……这让很多用惯了std::vector这类容器的程序员不习惯，感觉std::array不好用。但实际上，std::array的威力很可能被低估了。在这篇文章里，我会从各个角度介绍下std::array的用法，心愿能带来一些启发。 本文的代码都在C++17环境下编译运行。以后支流的g++版本曾经能反对C++17规范，然而很多版本（如gcc 7.3）的C++17个性不是默认关上的，须要手工增加编译选项-std=c++17。 主动推导数组大小很多我的项目中都会有相似这样的全局数组作为配置参数： uint32_t g_cfgPara[] = {1, 2, 5, 6, 7, 9, 3, 4}; 当程序员想要应用std::array替换原生数组时，麻烦来了： array<uint32_t, 8> g_cfgPara = {1, 2, 5, 6, 7, 9, 3, 4}; // 留神模板参数“8” 程序员不得不手工写出数组的大小，因为它是std::array的模板参数之一。如果这个数组很长，或者常常增删成员，对数组大小的保护工作恐怕不是那么欢快的。有人要埋怨了：std::array的申明用起来还没有原生数组不便，选它干啥？然而，这个埋怨只该限于C++17之前，C++17带来了类模板参数推导个性，你不再须要手工指定类模板的参数： array g_cfgPara = {1, 2, 5, 6, 7, 9, 3, 4}; // 数组大小与成员类型主动推导 看起来很美妙，但很快就会有人发现不对头：数组元素的类型是什么？还是std::uint32_t吗？有人开始尝试只提供元素类型参数，让编译器主动推导长度，遗憾的是，它不会见效。 array<uint32_t> g_cfgPara = {1, 2, 5, 6, 7, 9, 3, 4}; // 编译谬误 好吧，临时看起来std::array是不能像原生数组那样申明。上面咱们来解决这个问题。 用函数返回std::array问题的解决思路是用函数模板来代替类模板——因为C++容许函数模板的局部参数主动推导——咱们能够联想到std::make_pair、std::make_tuple这类辅助函数。巧的是，C++规范真的在TS v2试验版本中推出过std::make_array，然而因为类模板参数推导的问世，这个工具函数起初被删掉了。但显然，用户的需要还是存在的。于是在C++20中，又新增了一个辅助函数std::to_array。别被C++20给吓到了，这个函数的代码其实很简略，咱们能够把它拿过去定义在本人的C++17代码中[1]。 template<typename R, typename P, size_t N, size_t... I> constexpr array<R, N> to_array_impl(P (&a)[N], std::index_sequence<I...>) noexcept{ return { {a[I]...} };} ...

????叮~李老师小课堂上线了???? 分享主题:《 数组下标为什么从0开始? 》http://note.youdao.com/s/SIQl9QDv 前言：大家有没有感觉这个和咱们平时生存中从1开始编号的习惯相比显得很反人类？ 总结三大起因： 物理内存地址是从0开始的；缩小CPU指令运算；历史起因。

明天的知识点 (2020.10.05) —— 第538天 (我也要出题)[html] 实现中国五星红旗国旗的布局[css] 应用css3制作一个鼠标通过文本时，显示出边框的动画特效[js] 什么时候在JS中应用Float32Array而不是Array？[软技能] 开发多个零碎时如何共享组件化？有哪些计划？《论语》，曾子曰：“吾日三省吾身”（我每天屡次检查本人）。前端面试每日3+1题，以面试题来驱动学习，每天提高一点！让致力成为一种习惯，让奋斗成为一种享受！置信 保持 的力量！！！欢送在 Issues 和敌人们一起探讨学习！ 我的项目地址：前端面试每日3+1【举荐】欢送跟 jsliang 一起折腾前端，零碎整顿前端常识，目前正在折腾 LeetCode，打算买通算法与数据结构的任督二脉。GitHub 地址 微信公众号欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个Star, 同时欢送微信扫码关注 前端剑解 公众号，并退出 “前端学习每日3+1” 微信群互相交换（点击公众号的菜单：交换）。 学习不打烊，充电加油只为遇到更好的本人，365天无节假日，每天早上5点纯手工公布面试题（死磕本人，愉悦大家）。心愿大家在这虚夸的前端圈里，放弃沉着，保持每天花20分钟来学习与思考。在这变幻无穷，类库层出不穷的前端，倡议大家不要等到找工作时，才狂刷题，提倡每日学习！（不忘初心，html、css、javascript才是基石！）欢送大家到Issues交换，激励PR，感激Star，大家有啥好的倡议能够加我微信一起交换探讨！心愿大家每日去学习与思考，这才达到来这里的目标！！！（不要为了谁而来，要为本人而来！）交换探讨欢送大家前来探讨，如果感觉对你的学习有肯定的帮忙，欢送点个[Star]

一、数组定义： var 数组名 [数组大小]数组类型var a [5]int // 定义完数组各个元素就有默认值 数组的地址能够通过数组名来获取&arr数组的第一个元素的地址，就是数组的首地址数组的各个元素的地址距离是根据数组类型决定的，如int64->8arr[0]的地址加8个字节就是arr[1] 的地址 四种初始化形式： func main() { var arr [3]int = [3]int{1, 2, 3} var arr2 = [3]int{1, 2, 3} var arr3 = [...]int{1, 2, 3} var arr3 = [...]string{0: "xxx", 1: "zzz"}}for range 遍历数组： func main() {// 第一个返回值index是数组的下标// 第二个返回值value是下标对应的值// 他们都是仅在for循环外部可见的变量 var arr3 = [...]string{0: "xxx", 2: "zzz"} for index,value := range arr3 { fmt.Printf("索引：%v, 值：%vn", index, value) }}一、切片切片是数组的援用 func main() { var intArr [5]int = [...]int {1, 2, 33, 44, 56} // 援用数组下标为1，最初的下标为3（但不包含3） 22, 33 slice := intArr[1:3] fmt.Println("数组：", intArr) fmt.Println("切片：", slice) fmt.Println("切片个数：", len(slice)) fmt.Println("切片容量：", cap(slice)) // 切片的容量能够动态变化}切片内存存储切片不存储任何元素， 只是对现有数组的援用，对切片的任何批改，都反映在底层数组中。 ...

背景最近准备一个教程，案例的过程中准备了如下代码碎片，演示解析http scheme #include <stdio.h>#include <stdlib.h>#include <string.h>char *parse_scheme(const char *url){ char *p = strstr(url,"://"); return strndup(url,p-url);}int main(){ const char *url = "http://static.mengkang.net/upload/image/2019/0907/1567834464450406.png"; char *scheme = parse_scheme(url); printf("%s\n",scheme); free(scheme); return 0;}上面是通过strndup的方式，背后也依托了malloc，所以最后也需要free。有人在微信群私信parse_scheme能用char []来做返回值吗？我们知道栈上的数组也能用来存储字符串，那我们可以改写成下面这样吗？ char *parse_scheme(const char *url){ char *p = strstr(url,"://"); long l = p - url + 1; char scheme[l]; strncpy(scheme, url, l-1); return scheme;}大多数人都知道不能这样写，因为返回的是栈上的地址，当从该函数返回之后，那段栈空间的操作权也释放了，当再次使用该地址的时候，值就是不确定的了。 那我们今天就一起探讨下出现这样情况的背后的真正原理。 基础预备每个函数运行的时候因为需要内存来存放函数参数以及局部变量等，需要给每个函数分配一段连续的内存，这段内存就叫做函数的栈帧（Stack Frame）。因为是一块连续的内存地址，所以叫帧；为什么叫要加一个栈呢？想必大家都熟悉了函数调用栈，为什么叫函数调用栈呢？比如下面的表达式 array_values(explode(",",file_get_contents(...)));函数的执行顺序是最内层的函数最先执行，然后依次返回执行外层的函数。所以函数的执行就是利用了栈的数据结构，所以就叫栈帧。 x86_64 cpu上的 rbp 寄存器存函数栈底地址，rsp 寄存器存函数栈顶地址。 实验#include <stdio.h>void foo(void){ int i; printf("%d\n", i); i = 666;}int main(void){ foo(); foo(); return 0;}$gcc -g 2.c$./a.out0666为什么第二次调用foo函数输出的结果都是上次函数调用的赋值呢？先看下反汇编之后的代码 ...

提出问题：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。 解决思路：判断众数实则是判断重复元素的个数。遇到重复元素首先考虑字典。字典key值存放数组元素，value存放元素出现次数，如果次数超过n/2，则为答案。 代码如下(￣▽￣)： class Solution: def majorityElement(self, nums: List[int]) -> int: d = {} for i in nums: if i in d: d[i]+=1 else: d[i]=1 for key,value in d.items(): if d[key] > len(nums)/2: return key return 0时间与空间复杂度： 题目来源：https://leetcode-cn.com/probl...

提出问题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 解题思路：使用异或运算解决。异或运算规则：1.相同数字进行异或运算结果为0。2. 0与任何数进行异或运算结果为该数字。比如[4,1,1] 4与1异或为5，5与1异或为4，最终输出4为正确答案。所以算法先设定最终输出值为0，让输出值与数组中所有元素进行一次异或操作，即可得出最终答案。 代码如下(￣▽￣)： class Solution: def singleNumber(self, nums: List[int]) -> int: num = 0 for i in range(len(nums)): num = num^nums[i] return num时间与空间复杂度： 题目链接：https://leetcode-cn.com/probl...

Nginx 作为优秀的开源软件，凭借其高性能高并发等特点，常常作为web和反向代理服务部署在生产环境中。但是当 Nginx 的规模较大时， Nginx 的运维成本也是不断上升。本文介绍如何通过confd+ACM来管理 Nginx 配置，通过集中式的配置管理方式解决 Nginx 的大规模运维问题，运维和开发人员不用登陆到 Nginx 机器上，只需要配置好confd，然后在ACM上操作就可以动态修改 Nginx 的配置参数。 准备工作在操作本文的示例之前需要配置好开通ACM和对confd的使用有基本概念，ACM的开通及其基本使用可以参考：这里confd的基本使用可以参考：这里 Nginx 在日常开发中使用得比较多的功能是负载均衡、限流、缓存等， Nginx 的使用和安装可以在网上查阅相关资料。本文结合负载均衡和限流功能讲解如何使用confd+ACM实现 Nginx 的大规模运维操作。 创建confd配置文件创建confd所需的toml格式配置文件 vim /etc/confd/conf.d/myapp.tomlcheck_cmd用于检验 Nginx 配置的正确性，当src配置错误则不会覆盖 Nginx 配置reload_cmd用于reload Nginx 配置 [template]src = " Nginx .conf.tmpl"dest = "/usr/local/ Nginx /conf/ Nginx .conf"keys = ["/myapp/ Nginx /conf",]check_cmd = "/usr/local/ Nginx /sbin/ Nginx -t -c {{.src}}"reload_cmd = "/usr/local/ Nginx /sbin/ Nginx -s reload"创建模版文件vim /etc/confd/templates/ Nginx .conf.tmplgetv从ACM中获取对应dataId的配置，/myapp/ Nginx /conf对应的dataId为myapp. Nginx .conf，配置格式为json格式，模版文件包含了 Nginx 的upstream、限流、黑白名单配置内容，通过json指令解析配置文件。upstream后端ip通过从ACM的配置的backends数组中获取，同样地，白名单和黑名单ip分别存储在whiteList和blackList的数组中，限流的速率和并发数通过rateLimit和connectionLimit设置 ...

本文承接上一篇：乐字节Java发射之二：实例化对象、接口与父类、修饰符和属性 继续讲述Java反射之三：方法、数组、类加载器 一、方法获取所有方法(包括父类或接口)，使用Method即可。 public static void test() throws Exception { Class<?> clz = Class.forName("com.shsxt.ref.simple.User "); //获取属性System.out.println("===============本类方法==============="); // 取得全部公共方法 Method[] methods =clz.getMethods(); for(Method m:methods){ //1、权限 int mod=m.getModifiers(); System.out.print(Modifier.toString(mod)+" "); //2、返回类型 Class<?> returnType=m.getReturnType(); System.out.print(returnType.getName()+" "); //3、名字 String name =m.getName(); System.out.print(name +"("); //4、参数 Class<?>[] para=m.getParameterTypes(); for(int i=0;i<para.length;i++){ Class<?> p =para[i]; System.out.print(p.getName() +" arg"+i); if(i!=para.length-1){ System.out.print(","); } } //异常 Class<?>[] exce=m.getExceptionTypes(); if(exce.length>0){ System.out.print(") throws "); for(int k=0;k<exce.length;++k){ System.out.print(exce[k].getName()+" "); if(k<exce.length-1){ System.out.print(","); } } }else{ System.out.print(")"); } System.out.println(); } }二、 数组操作数组需要借助Array类。 ...

概述ArraysList可以动态分配数组 ArrayList<...> list = new ArrayList(); <>内是泛型。泛型：集合中的所有元素都是统一的类型。泛型只能是引用类型，不能是基本类型。原因是集合里保存的是地址值，基本类型中没有地址值 ArrayList<int> list = new ArrayList();//错误ArrayList<String> list = new ArrayList();//正确ArrayList<Employee> list = new ArrayList();//正确List<Employee> list = new ArrayList();//多态，正确如果希望向集合ArrayList当中存储基本类型数据，必须使用基本类型对应的“包装类” ArrayList<Integer> list = new ArrayList();//正确ArrayList常用方法：add：添加元素到数组中。可以带索引ensureCapacity：array.ensureCapacity(100)将分配一个包含100个对象的内部数组，然后调用100次add。也可以ArrayList<Integer> array = new ArrayList<>(100)，两者作用相同。size：返回数组列表中包含的实际元素数量trimToSize：当确定数组列表的大小不再发生变化，该方法将存储区域的大小调整为当前元素数量所需要的存储空间数目。垃圾回收器将回收多余的存储空间get和set：实现访问和改变数组元素的操作。set只能设置已存在的元素 remove：删除一个元素

JavaScript 实现数组更多的高阶函数场景虽说人人平等，但有些人更加平等。为什么有了 Lodash 这种通用函数工具库，吾辈要写这篇文章呢？吾辈在 SegmentFault 上经常看到关于 JavaScript 数组的相关疑问，甚至于，相同类型的问题，只是数据变化了一些，就直接提出了一个新的问题（实际上，对自身并无帮助）。简单搜索了一下 Array，居然有 2360+ 条的结果，足可见这类问题的频率之高。若是有一篇适合 JavaScript 萌新阅读的自己实现数组更多操作的文章，情况是否会发生变化呢？ 下面吾辈便来实现以下几种常见的操作 uniqueBy: 去重sortBy: 排序filterItems: 过滤掉一些元素diffBy: 差异groupBy: 分组递归操作前言:你至少需要了解 ES6 的一些特性你才能愉快的阅读uniqueBy: 去重相关问题 javascript 怎么实现多种数据类型的数组去重？JS 有没有比较高效的数组去重的方法？/** * js 的数组去重方法 * @param arr 要进行去重的数组 * @param kFn 唯一标识元素的方法，默认使用 {@link returnItself} * @returns 进行去重操作之后得到的新的数组 (原数组并未改变) */function uniqueBy(arr, kFn = val => val) { const set = new Set() return arr.filter((v, ...args) => { const k = kFn(v, ...args) if (set.has(k)) { return false } set.add(k) return true })}使用 ...

题目要求Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.Find all the elements that appear twice in this array.Could you do it without extra space and in O(n) runtime?Example:Input:[4,3,2,7,8,2,3,1]Output:[2,3]存在一个整数数组，其中的所有元素都位于1~n之间，其中n是数组的长度。有的元素出现了一次，而有的元素出现了两次。找到数组中所有出现两次的数字。 思路一：交换为了在O(N)的时间内找到所有的出现两次的数字，其核心要求在于用现有的数组记录已经访问过的元素，同时不会丢失尚未访问过的元素。思路一采用交换的核心思想，即每次都将当前下标上的值和以该值为下标的位置上的值进行交换，如果该值下标位置上的值和其相等，则说明该数字已经被遍历过一遍了。 代码如下： public List<Integer> findDuplicates(int[] nums) { int index = 0; List<Integer> result = new ArrayList<Integer>(); while(index < nums.length) { int num = nums[index]; if(num == 0){ index++; }else if (nums[num-1] == num) { if(index != num-1){ result.add(num); nums[index] = 0; } index++; }else{ swap(index, num-1, nums); } } return result; } public void swap(int i, int j, int[] nums) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }思路二：取反有没有一种办法在既保留当前位置上的值nums[i]的同时，又能够用某种方式记录i+1是否已经被访问过了？可以通过取反的方法来记录是否被访问过这个情况。如果访问到下标为i的位置上的值，则去判断nums[nums[i]-1]位置上的值是否为负数，如果是，则说明num[i]出现了两次，否则将nums[nums[i]-1]位置上的值取反保留。 ...

JavaScript 数组的高阶函数使用异步操作吾辈的博客原文: https://blog.rxliuli.com/p/5e...场景吾辈是一只在飞向太阳的萤火虫JavaScript 中的数组是一个相当泛用性的数据结构，能当数组，元组，队列，栈进行操作，更好的是 JavaScript 提供了很多原生的高阶函数，便于我们对数组整体操作。然而，JavaScript 中的高阶函数仍有缺陷 -- 异步！当你把它们放在一起使用时，就会感觉到这种问题的所在。 例如现在，有一组 id，我们要根据 id 获取到远端服务器 id 对应的值，然后将之打印出来。那么，我们要怎么做呢？ const wait = ms => new Promise(resolve => setTimeout(resolve, ms))async function get(id) { // 这里只是为了模拟每个请求的时间可能是不定的 await wait(Math.random() * id * 100) return '内容: ' + id.toString()}const ids = [1, 2, 3, 4]你或许会下意识地写出下面的代码 ids.forEach(async id => console.log(await get(id)))事实上，控制台输出是无序的，而并非想象中的 1, 2, 3, 4 依次输出 内容: 2 内容: 3 内容: 1 内容: 4这是为什么呢？原因便是 JavaScript 中数组的高阶函数并不会等待异步函数的返回！当你在网络上搜索时，会发现很多人会说可以使用 for-of, for-in 解决这个问题。 ...

作者：Bolaji Ayodeji翻译：疯狂的技术宅 原文：https://www.freecodecamp.org/... 未经允许严禁转载 JavaScript 中的数组是什么？在开始之前，你需要先了解数组的真正含义。 在 JavaScript 中，数组是一个用于存储不同数据类型的变量。它将不同的元素存储在一个盒子中，供以后使用。声明一个数组： let myBox = []; // JS中的初始化数组声明数组中可以包含多种数据类型 let myBox = ['hello', 1, 2, 3, true, 'hi'];可以用被称为方法的多个操作来操作数组。这些方法允许我们对数组进行添加、删除、修改挤执行更多操作。 我会在本文中向你展示一其中的一部分，让我们继续： 注意：本文中使用了箭头功能，如果你不知道这意味着什么，你应该在这里阅读。箭头功能是ES6的功能。toString()toString() 方法能够将数组转换为以逗号分隔的字符串。 let colors = ['green', 'yellow', 'blue'];console.log(colors.toString()); // green,yellow,bluejoin()The JavaScript join() method combines all array elements into a string.JavaScript 的 join() 方法将所有数组元素组合成一个字符串。 它类似于 toString() 方法，但在这里你可以指定分隔符而不是默认的逗号。 let colors = ['green', 'yellow', 'blue'];console.log(colors.join('-')); // green-yellow-blueconcat此方法可以将两个数组组合在一起，或者向数组中添加更多的元素项，然后返回一个新数组。 let firstNumbers = [1, 2, 3];let secondNumbers = [4, 5, 6];let merged = firstNumbers.concat(secondNumbers);console.log(merged); // [1, 2, 3, 4, 5, 6]push()此方法将元素项添加到数组的末尾，并修改原始数组。 ...

splice() 和 slice()唯一的共同点是都是对数组的操作，还有就是长的很像，有时候容易搞混。 这两个最的区别：splice()会改变原来的数组，返回的是被改变的内容，比如说通过splice删掉了某一项，那么返回的是删掉的这一项，当然还是会以数组的形式返回。举个栗子 let animals = ['ant', 'bison','camel','duck','elephant'] console.log(animals.splice(2,1)) //['camel']被删掉的是索引未为2的一项，返回的也只有这一项所以如果想删掉某一项，并不需要得到一个新的数组，只需要 animals.splice(2,1) console.log(animasl)//['ant', 'bison','duck','elephant']// 用某个元素替换掉数组里的某个元素 直接修改原来的数组Array.prototype.replaceAryItem = function(index,val) { this.splice(index,1,val)}slice不会对原数组进行改变，会返回一个新的数组。利用slice同样也可以实现根据索引删除某一项 // 删除数组里的某一项 返回一个新的数组 不直接修改数组Array.prototype.removeAryItemByIndex = function(index) { return this.slice(0,index).concat(this.slice(index+1))}

一、前言之前写了一篇文章：JavaScript 系列--JavaScript一些奇淫技巧的实现方法（一）简短的sleep函数，获取时间戳 https://www.mwcxs.top/page/74... 介绍了sleep函数和获取时间戳的方法。接下来我们来介绍数字格式化1234567890 --> 1,234,567,890 二、数字格式化 1234567890 --> 1,234,567,8901、普通版// 数字格式化 1234567890 --> 1,234,567,890function formatNumber(str){ var arr = []; var count = str.length; while(count>=3){ arr.unshift(str.slice(count - 3, count)); count -= 3; } // 如果是不是3的倍数就另外追加到上去 str.length % 3 && arr.unshift(str.slice(0, str.length % 3)); return arr.toString();}formatNumber('1234567890')优点：自我感觉比网上写的一堆 for循环 还有 if-else 判断的逻辑更加清晰直白。缺点：太普通 2、进阶版// 2、进阶版function formatNumber(str){ return str.split("").reverse().reduce((prev,next,index) => { return ((index%3)? next: (next+',')) + prev; })}formatNumber("1234567890");优点：把 JS 的 API 玩的了如指掌缺点：不好理解 ...

源码问题排序arr.sort(fun)arr.sort(()=>1) 与 arr.sort(()=>-1) 是否会按照从大到小或从小到大排序？

在javascript中，数组是最重要的数据结构，没有之一，因为所有的数据结构都可以使用数组模拟和表达。可以说掌握了数组，就掌握了js与数据操作的大部分核心功能。 ES6给数组添加了一些新特性，而这些新特性到目前为止完全可以运用到自己的业务层。 但是，开发者初次接触ES6，很多东西都看得云里来雾里，无从下手。在这一节中将总结有关于ES6给数组提供一些新特性的使用方法，让用户能够听得懂，用的起来。 1、新增数组创建方法 1.1 Array.from Array.from的设计目的是快速便捷把一个类似数组的可迭代对象创建成一个新的数组实例。 通俗的讲，只要一个对象有length，Array.from就能把它变成一个数组，返回新的数组，而不改变原对象。 let likeArr = { '0': 'a', '1': 'b', '2': 'c', length: 3};// ES5的写法var arr1 = [].slice.call(likeArr); // ['a', 'b', 'c']// ES6的写法let arr2 = Array.from(likeArr); // ['a', 'b', 'c']常见的类似数组的对象还有 DOM 操作返回的 NodeList 集合，以及函数内部的 arguments 对象。Array.from都可以将它们转为真正的数组。 // NodeList对象let div = document.querySelectorAll('div');console.log(div); // NodeList(8) [div#cst, div, div.gb_3, …]console.log(Array.from(div)); //(8) [div#cst, div, div.gb_3, …]// arguments对象function foo() { var args = Array.from(arguments); console.log(args);}foo(1,2,34,666,333,663); // [1, 2, 34, 666, 333, 663]Array.from 对 String，Set，Map 等拥有迭代器的对象也可以进行转换。 ...

题目要求Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.Find all the elements of [1, n] inclusive that do not appear in this array.Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.Example:Input:[4,3,2,7,8,2,3,1]Output:[5,6]假设一个长度为n的整数数组，数组中的元素的值位于[1,n]区间中。问，该数组中有哪些[1,n]区间中的整数没有出现？ 思路和代码首先可以想到用另一个临时数组来记录每个元素出现的次数，则出现次数为零次的元素在数组中没有出现。代码如下： public List<Integer> findDisappearedNumbers(int[] nums) { int[] temp = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { temp[nums[i]]++; } List<Integer> result = new ArrayList<>(); for (int i = 1; i < temp.length; i++) { if (temp[i] == 0) { result.add(i); } } return result; }但是这个实现违背了O(1)的空间复杂度（这里结果集不视为额外空间）。因此如何才能避免使用临时数组呢？其实我们可以利用原数组中元素相互调换的方式，将其转化为一个新的有序的数组。即从最左边开始，每遇到一个元素，就将其防止到元素的目标位置上，如在第0位上遇到元素i，则将位置i-1上的元素和位置0上的元素进行交换，并在此判断新的元素是否需要交换。如果当前元素无需进行交换，则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。 ...

905. Sort Array By Parity（easy）题目理解：一个数组中全是非负数，现在要我们把偶数放在前面，奇数放在偶数之后 首先想到的做法：声明一个新的vector，扫描A两遍，第一遍插入偶数，第二遍插入奇数，返回新的vector可能优化方向： 扫描一遍不分配新空间于是想到了新的做法：用两个指针标记位置，两个指针分别从前往后和从后往前扫描比较两个指针所指的数据有4种情况： 情况对应操作前奇后偶交换位置，i向后移，j向前移前偶后奇不用交换，i往后移，j往前移前后全是偶数不用交换，i往后移前后全是奇数不用交换，j往前移其实这种做法的本质就是利用两个指针在O(N)时间里达到了和之前扫描两次同样的效果，并且维护了原数组，就不用再分配新的空间了，这也是一种比较常用的做法。在实际代码里我对i，j移动的时机做了一些改动，结果是一样的，但是看起来可能更简单，也可以分成四种情况逐一用if...else if来写。accept代码 class Solution {public: vector<int> sortArrayByParity(vector<int>& A) { int i = 0, j = A.size() - 1; int n = A.size(); while (i < j) { if (A[i] % 2 != 0 && A[j] % 2 != 1) swap(A[i++], A[j--]); if (A[i] % 2 == 0) i++; if (A[j] % 2 == 1) j--; } return A; }}; ...

了解和学习一种知识的最好方法是带着相关的问题去探索，当我们把一些常见的问题全部解答了，我们也就能对这种事物有一些初步的了解了。试着回答下面的几个问题，让我们对数据结构和算法有一个基本的认识吧。 什么是数据结构？为什么要了解数据结构？作为一个前端，日常工作当中，我们接触的数据结构有哪几种？数据结构和算法是什么关系？如何判断一个算法是否是最优？什么是数据结构？从字面意思来理解就是一种数据的多种表现方法，什么是结构——由组成整体的各部分的搭配和安排（百度百科）。我的理解是：数据的排列，不同的数据结构就是数据的多种排列形式，然后根据排列的情况我们通常用一个学名来表示它，比如说：数组，集合，树，图等。 为什么要了解数据结构？当我们了解了数据结构之后，在实际的编程过程当中，我们遇到某一类的数据的时候，我们就能够找到一种最合适的数据结构来表示他们了。这样再处理跟数据相关问题的时候就会变得高效，因为确定了数据结构，我们也就确定了针对该结构的数据，使用那些方法来对数据进行相关的操作了。比如说，我们需要一种数据结构来记录每天的天气情况，当我们说到某一天的时候，就能立刻知道当天的天气是怎么样的时候我们可以用一个数组来表现。又如，我们要描述一个家族的族谱的时候，用树型结构比较合适；描述一个人的年龄，身高，体重，民族，学历这种用集合比较合适；描述排队的情况用队列。 作为前端，通常我们接触到的数据结构有哪几种？最常用的应该有两种了：数组，对象。到了ES6又增加了两种新的数据结构Set和Map，其实Set和Map应该算是数组和对象的一种变种，但总的来说它们又是另外两种类型的数据结构； Set类数组结构——成员唯一，没有重复的值Map类对象结构——不同Object，键值通常是字符串，Map的键值可以是任何类型。数据结构和算法的关系数据结构只不过是我们描述数据的一种手段，但我们最终的目的通常是对这些数据进行相关的操作，比如：添加，删除，查找，排序等。所谓的算法就是如何去实现这种操作的一种计算方式。但算法往往不止一种，有道是条条道路通罗马，通常要达到某种目的，我们可能会有很多种的算法。比如一个数组我们要给他进行去重，就有很多种方法。你可以循环遍历，把每个值跟其他的值比较一遍，也可以把数组转成Set结构的数据。 如何判断一个算法是否最优？上面说到实现某种操作的方法有很多种，但是哪一种是最好的，我们要如何判断呢。我们可以通过算法的执行时间对吧，那种算法执行的速度越快，当然那种算法就最好。但计算机当中，还要考虑到算法的空间复杂度，也就是算法执行过程当中，可能占用的内存空间，一个算法执行的速度非常块，但执行的时候，需要1T的内存空间，这就不行。所以好的算法往往有两个条件: 运算的速度快占用的内存（存储空间） 小我还有个第三点，那就是代码便于理解，但这部分优秀的算法，往往涉及到很多数学相关的问题，如果没有这部分相关的概念，理解起来是非常不容易的。 其它涉及到前端数据结构和算法的一些学习笔记，我放到了github上面，内容还在更新，尽量一周分享一个，欢迎大家一起来讨论并参与分享，github地址如下: https://github.com/mmcai/Stru...

声明数组declare -a array_name 数组初始赋值array_name[xx]=value 其中xx表示下标，为大于等于0的整数数字array_name=([xx]=value1 [yy]=value2 ...)其中xx表示下标，为大于等于0的整数数字array_name=(value1 value2 value3 ...)或declare -a array_name=(value1 value2 value3 ...)数组追加元素array=( "${array[@]}" "new element" )或array[${#array[*]}]="new element" 复制数组array2=( "${array1[@]}" )或array2="${array1[@]}" 获取单个、全部或连续的部分数组元素${array_name[xx]}获取下标为xx的单个元素${array_name[@]}或${array_name[*]}获取所有元素。在有引号括起的情况下，"${array_name[@]}"表示单独的数组元素，"${array_name[*]}"表示数组元素整体，没有引号括起的情况下都表示单独的数组元素，类似$*和$@的区别${array_name[@]:index:length}获取连续的部分数组元素，其中:length可省略。 arrayZ=( one two three four five )# 提取所有元素echo ${arrayZ[@]:0} # one two three four five# 提取下标从1开始(包含)的所有元素echo ${arrayZ[@]:1} # two three four five# 提取下标从1开始(包含)的2个元素echo ${arrayZ[@]:1:2} # two three获取数组元素个数${#array_name[*]}或${#array_name[@]} 获取数组某个元素的字符串长度${#array_name[xx]} 提取数组中某个元素的部分字符串${array_name[xx]:index:length}, 其中:length可省略 删除数组或数组元素unset array_name[xx]删除下标为xx的数组元素，等同于array_name[xx]=unset array_name删除整个数组数组元素的字符串替换/删除操作通常情况下，形如${name...}表示法的字符串操作都可以应用在数组上，使用${name[@]...}或${name[*]...}的方式。 子字符串移除 arrayZ=( one two three four five five )# 从每个元素的最左侧进行最短匹配，并删除匹配的字符串echo ${arrayZ[@]#fiv} # one two three four e eecho ${arrayZ[@]#t*e} # one two e four five five# 从每个元素的最左侧进行最长匹配，并删除匹配的字符串echo ${arrayZ[@]##t*e} # one two four five five# 从每个元素的最右侧进行最短匹配，并删除匹配的字符串echo ${arrayZ[@]%h*e} # one two t four five five# 从每个元素的最右侧进行最长匹配，并删除匹配的字符串echo ${arrayZ[@]%%t*e} # one two four five five子字符串替换 ...

遍历方法小结常用的遍历方法for 遍历forEach（对数组的每个元素执行一次提供的函数）map（创建一个新数组，其结果是该数组中的每个元素都调用一个提供的函数后返回的结果）for 遍历大家都熟悉，所以重点讲一下forEach 与 map 的区别相同点：回调函数参数相同，都自带三个属性：item / index / array均不会修改原数组第二参数this的指向均指向window（可是使用箭头函数进行修改）只能遍历数组都不能使用循环跳出语句 break & continue不同点：forEach返回值为undefinedmap返回值为一个新的数组可以链式调用 // 链式调用 var str = ‘abcde’; // 使用call在字符类型中使用map方法 Array.prototype.map.call(str, function(x) { return x; }).reverse().join(’’); // edcba其他遍历方法filter (创建一个新数组, 其包含通过所提供函数实现的测试的所有元素)find (返回数组中满足提供的测试函数的第一个元素的值。否则返回 undefined)every (测试数组的所有元素是否都通过了指定函数的测试)some (测试是否至少有一个元素通过由提供的函数实现的测试)【Attention】 filter 将遍历所有的元素 find & some & every 属于「条件中断」遍历（即当元素满足某一条件是返回boolean） 四个方法都不会对原数组进行修改ES5 中的for…in 遍历常用于对象key值的遍历ES6 引入的遍历方法for…of 遍历[ 前置知识：for…of 可对具有iterator接口的数据结构进行遍历 ]原生具有iterator接口的数据结构如下：ArraySetMapStringTypedArrayNodeList 对象函数的arguments 对象keys( ) / values( ) / entries( )常用来遍历对象、数组、set、map结构【番外】改变原数组的方法pop、push、reverse、shift、sort、splice、unshift不会改变原数组的方法concat、join、slice、toString、toLocaleString、indexOf、lastIndexOf

数组简述数组是一种效率最高的存储和随机访问对象引用的一个简单的线性序列，虽然访问快速，但为之付出的代价是数组的大小固定，并且在其生命周期中不可改变。数组与其他容器之间的区别在于：效率、类型和保存基本类型的能力。但随着自动包装机制的出现，容器已经可以与数组几乎一样方便，而数组仅存的优点就是效率。应该 “优先选择容器而不是数组”，只有在已经证明性能称为问题（并且切换到数组对性能提高有所帮助）时，你才应该将程序重构为使用数组数组标识符就是一个引用，用以保存指向其他对象的引用，数组的一个单元指向在堆中创建的一个真实对象。对像数组与基本类型数组的区别在于，对象保存的是引用，基本类型数组保存的是基本类型的值。数组的 length属性，表示数组的大小，而不是实际保存的元素个数。新生成的对象数组，会被默认的初始化为 null，基本类型数组则会初始化为对应基本类型的默认值，对于对象数组，可以检测其中的引用是否为 null，进而确定某个位置是否存在对象。当数组不被需要时，垃圾回收器会负责清理数组，否则将一直存在。实用数组方法System.arraycopy()：复制一个数组比用 for 循环复制要快得多，且该方法对所有类型做了重载。当复制对象数组时，只是复制对象的引用（属浅拷贝）。Arrays.asList(T… a)：将多个元素转换成 List 列表，底层表示的还是数组，当尝试进行 add()、delete()操作时将在运行时报错。Arrays.sort(T[] a, Comparator<? super T> c)：按照给定的比较器对指定的数组进行排序。Arrays.binarySearch(T[] a,T key, Comparator<? super T> c)：对一个有序的数组采用二分查找获取对象下标，如果数组存在重复元素，可能返回的不精确。<span color=“red”>注：如果使用了Comparator排序了一个对象数组，则调用此方法时传入的Comparator必须是同一个。</span>Comparator比较器comparator用于指定元素的排列顺序，在常见的数据类型中已经被默认实现，对于需要按照某种规则进行排序的时候，提供Comparator或者实现 java.lang.Comparable接口。class DemoComparator implements Comparator<Demo> { @Override public int compare(Demo o1, Demo o2) { if (o1.value == o2.value) { return 0; } return o1.value < o2.value ? 1 : -1; } }容器Collection一个独立元素的序列，这些元素都服从一条或多条规则，提供了存放一组对象的方式。List必须按照插入的顺序保存元素，而Set不能有重复元素。Queue按照队列排队规则来确定对象产生的顺序。PriorityQueue：优先级队列，声明下一个弹出最需要的元素（具有最高的优先级），通过默认排序或提供 Comparator。当调用 peek()、poll()、remove()方法时，获取的元素是队列中优先级最高的。List类描述ArrayList常用于随机访问元素，但是在 List的中间插入和删除元素时较慢。LinkedList对中间插入和删除元素的操作中提供了优化的顺序列表，在随机访问方面相对比较慢，但是它的特性集较 ArrayList更大。ListIterator：Iterator的子类，只用于对各种 List 类的访问，可以实现双向移动。hasNext() / next()、hasPrevious() / previous()对于随机访问的 get/set操作，背后有数组支持的 List 比 ArrayList 稍快一点，但是对于 LinkedList，将会变得很慢，因为它不是针对随机访问操作而设计的。最佳的做法是将 ArrayList 作为默认首选，当因为经常插入和删除操作而性能下降时，才去选择 LinkedList。如果使用的是固定数量的元素，既可以选择List，也可以选择数组。Set类描述Set (interface)存入Set的每一个元素都必须要唯一，因为Set不允许重复元素。加入Set的元素必须定义 equals()方法以确保对象的唯一性。Set 和 Collection 有完全一样的接口。 Set 接口不保证维护元素的次序。HashSet为快速查找而设计的Set。存入 HashSet的元素必须定义 hashCode()。TreeSet保持次序的 Set，底层为数据结构。使用它可以从 Set中提取有序的序列。元素必须实现 Comparator接口。LinkedHashSet具有 HashSet的查询速度，且内部使用链表维护元素的顺序（插入的次序）。于是在使用迭代遍历 Set时，结果会按元素插入的次序显示。元素必须定义 hashCode()方法。HashSet以某种顺序保存元素，LinkedHashSet按照元素插入的顺序保存元素，而 TressSet按照排序维护元素。HashSet的性能基本上总是比 TreeSet好，特别在添加和查询元素时。 TreeSet存在的唯一原因是它维持元素的排序顺序，因此迭代的时候，TreeSet通常比用HashSet要快。MapMap的各个实现类的行为特性的不同在于，效率、键值对的保存及呈现次序、对象的保存周期、映射表如何在多线程程序中工作和判定 ”键“等价的策略等方面。类描述HashMapMap基于散列表的实现（取代HashTable）。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量和负载因子，以调整容器的性能。LinkedHashMap类似于HashMap，但是迭代遍历它时，取得 “键值对” 的顺序就是其插入次序，或者是最近最少使用（LRU）的次序。只比HashMap慢一点；而在迭代访问时反而快，因为它使用链表维护内部次序。TreeMap基于红黑树的实现。查看 “键” 或“键值对”时，它们会被排序。TreeMap的特点在于，所得到的的结果是经过排序的。TreeSet是唯一一个带有 subMap()方法的Map，它可以返回一个子树。WeekHashMap弱键映射，允许释放映射所指向的对象，这是为解决某类特殊问题而设计的。如果映射 之外没有引用指向某个“键”，则此“键”可以被垃圾收集器回收。ConcurrentHashMap一种线程安全的Map，它不涉及同步加锁。IdentityHashMap使用 ==代替equals()对“键”进行比较的散列映射。专为解决特殊问题而设计的使用Map时，首选HashMap，TreeMap维护着散列数据结构的同时还要维护链表，在迭代的时候速度快，其余方面比HashMap要慢。插入操作随着Map尺寸的变大，速度会明显变慢（除了 IdentityHashMap），但是查找所耗费的代价比插入小很多。对于插入操作，由于维护链表所带来的的开销，导致LinkedHashSet 比 HashSet的代价高很多。HashMap的性能因子：容量：表中的桶位数。初始容量：表在创建时所拥有的桶位数。尺寸：表中当前存储的项数。负载因子：尺寸/容量。 空表的负载因子为 0，半满表为 0.5。负载越轻的表产生的冲突性越小，HashMap默认负载因子为 0.75，达到默认值时，将进行散列。散列与散列码散列码是一个无符号的十六进制数，散列的目的在于使用一个对象来查找另一个对象；散列的价值在于能够快速进行查询。在Map上的实现：通过键对象生成一个数字，这个数字就是散列码。将散列码作为数组的下标，该数组的一个单元指向一个链表，链表上的一个节点就是一个 Entry 对象。数组的容量是固定的，不同的键可以产生相同的下标，这将导致 “冲突”。Example：参考Java编程思想 P493static final int SIZE = 1024;LinkedList<Entry<K, V>>[] buckets = new LinkedList[SIZE]; public V put(K key, V value) { V oldValue = null; // 对散列值取余获取数组下标 int index = Math.abs(key.hashCode()) % SIZE; if (buckets[index] == null) { buckets[index] = new LinkedList<Entry<K,V>>(); } // 获取下标所指向的链表 LinkedList<Entry<K, V>> bucket = buckets[index]; Entry<K, V> pair = new Entry<>(); boolean found = false; // 获取迭代器进行迭代，判断是否存在，存在则覆盖 ListIterator<Entry<K, V>> it = bucket.listIterator(); while (it.hasNext()) { Entry<K, V> iPair = it.next(); if (iPair.getKey().equals(key)) { oldValue = iPair.getValue(); it.set(pair); found = true; break; } } // 没有找到就添加 if (!found) { buckets[index].add(pair); } return oldValue;}equals()自反性。对称性。传递性。一致性。对任何不是 null的 x， x.equals(null) 一定返回 false。hashcode()对同一个对象调用hashcode() 都应该生成同样的值。基于对象的内容生成散列码，让其富有意义。散列码不必独一无二，应关注生成速度。通过 hashCode()和equals()，必须能够完全确定对象的身份。好的 hashCode()应该产生分布均匀的散列码。赋予一个非零常量值。public int hashCode() { int result = 19; return result * field.hashCode();} ...

题目给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）例如：给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：[ [15,7], [9,20], [3]]题解利用层次遍历,层次遍历的时候进入下一层的时候记录一下当前队列中有几个元素。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> levelVal = new LinkedList<>(); while (size > 0) { TreeNode current = queue.poll(); if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } levelVal.add(current.val); size–; } res.add(0, levelVal); } return res; }}用递归去做。用递归去做的关键在于需要把层数也带上。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } helper(root, res, 0); return res; } public void helper(TreeNode root, List<List<Integer>> res, int depth) { if (root == null) { return; } if (depth == res.size()) { res.add(0, new LinkedList<>()); } List<Integer> current = res.get(res.size() - depth - 1); helper(root.left, res, depth + 1); helper(root.right, res, depth + 1); current.add(root.val); }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树手撕代码QQ群：805423079， 群密码：1024 ...

在Java中，集合和数组是我们经常会用到的数据结构，需要经常对他们做增、删、改、查、聚合、统计、过滤等操作。相比之下，关系型数据库中也同样有这些操作，但是在Java 8之前，集合和数组的处理并不是很便捷。不过，这一问题在Java 8中得到了改善，Java 8 API添加了一个新的抽象称为流Stream，可以让你以一种声明的方式处理数据。本文就来介绍下如何使用Stream。特别说明一下，关于Stream的性能及原理不是本文的重点，如果大家感兴趣后面会出文章单独介绍。Stream介绍Stream 使用一种类似用 SQL 语句从数据库查询数据的直观方式来提供一种对 Java 集合运算和表达的高阶抽象。Stream API可以极大提高Java程序员的生产力，让程序员写出高效率、干净、简洁的代码。这种风格将要处理的元素集合看作一种流，流在管道中传输，并且可以在管道的节点上进行处理，比如筛选，排序，聚合等。Stream有以下特性及优点：无存储。Stream不是一种数据结构，它只是某种数据源的一个视图，数据源可以是一个数组，Java容器或I/O channel等。为函数式编程而生。对Stream的任何修改都不会修改背后的数据源，比如对Stream执行过滤操作并不会删除被过滤的元素，而是会产生一个不包含被过滤元素的新Stream。惰式执行。Stream上的操作并不会立即执行，只有等到用户真正需要结果的时候才会执行。可消费性。Stream只能被“消费”一次，一旦遍历过就会失效，就像容器的迭代器那样，想要再次遍历必须重新生成。我们举一个例子，来看一下到底Stream可以做什么事情：上面的例子中，获取一些带颜色塑料球作为数据源，首先过滤掉红色的、把它们融化成随机的三角形。再过滤器并删除小的三角形。最后计算出剩余图形的周长。如上图，对于流的处理，主要有三种关键性操作：分别是流的创建、中间操作（intermediate operation）以及最终操作(terminal operation)。Stream的创建在Java 8中，可以有多种方法来创建流。1、通过已有的集合来创建流在Java 8中，除了增加了很多Stream相关的类以外，还对集合类自身做了增强，在其中增加了stream方法，可以将一个集合类转换成流。List<String> strings = Arrays.asList(“Hollis”, “HollisChuang”, “hollis”, “Hello”, “HelloWorld”, “Hollis”);Stream<String> stream = strings.stream();以上，通过一个已有的List创建一个流。除此以外，还有一个parallelStream方法，可以为集合创建一个并行流。这种通过集合创建出一个Stream的方式也是比较常用的一种方式。2、通过Stream创建流可以使用Stream类提供的方法，直接返回一个由指定元素组成的流。Stream<String> stream = Stream.of(“Hollis”, “HollisChuang”, “hollis”, “Hello”, “HelloWorld”, “Hollis”);如以上代码，直接通过of方法，创建并返回一个Stream。Stream中间操作Stream有很多中间操作，多个中间操作可以连接起来形成一个流水线，每一个中间操作就像流水线上的一个工人，每人工人都可以对流进行加工，加工后得到的结果还是一个流。以下是常用的中间操作列表:filterfilter 方法用于通过设置的条件过滤出元素。以下代码片段使用 filter 方法过滤掉空字符串：List<String> strings = Arrays.asList(“Hollis”, “”, “HollisChuang”, “H”, “hollis”);strings.stream().filter(string -> !string.isEmpty()).forEach(System.out::println);//Hollis, , HollisChuang, H, hollismapmap 方法用于映射每个元素到对应的结果，以下代码片段使用 map 输出了元素对应的平方数：List<Integer> numbers = Arrays.asList(3, 2, 2, 3, 7, 3, 5);numbers.stream().map( i -> i*i).forEach(System.out::println);//9,4,4,9,49,9,25limit/skiplimit 返回 Stream 的前面 n 个元素；skip 则是扔掉前 n 个元素。以下代码片段使用 limit 方法保理4个元素：List<Integer> numbers = Arrays.asList(3, 2, 2, 3, 7, 3, 5);numbers.stream().limit(4).forEach(System.out::println);//3,2,2,3sortedsorted 方法用于对流进行排序。以下代码片段使用 sorted 方法进行排序：List<Integer> numbers = Arrays.asList(3, 2, 2, 3, 7, 3, 5);numbers.stream().sorted().forEach(System.out::println);//2,2,3,3,3,5,7distinctdistinct主要用来去重，以下代码片段使用 distinct 对元素进行去重：List<Integer> numbers = Arrays.asList(3, 2, 2, 3, 7, 3, 5);numbers.stream().distinct().forEach(System.out::println);//3,2,7,5接下来我们通过一个例子和一张图，来演示下，当一个Stream先后通过filter、map、sort、limit以及distinct处理后会发生什么。代码如下：List<String> strings = Arrays.asList(“Hollis”, “HollisChuang”, “hollis”, “Hello”, “HelloWorld”, “Hollis”);Stream s = strings.stream().filter(string -> string.length()<= 6).map(String::length).sorted().limit(3) .distinct();过程及每一步得到的结果如下图：Stream最终操作Stream的中间操作得到的结果还是一个Stream，那么如何把一个Stream转换成我们需要的类型呢？比如计算出流中元素的个数、将流装换成集合等。这就需要最终操作（terminal operation）最终操作会消耗流，产生一个最终结果。也就是说，在最终操作之后，不能再次使用流，也不能在使用任何中间操作，否则将抛出异常：java.lang.IllegalStateException: stream has already been operated upon or closed俗话说，“你永远不会两次踏入同一条河”也正是这个意思。常用的最终操作如下图：forEachStream 提供了方法 ‘forEach’ 来迭代流中的每个数据。以下代码片段使用 forEach 输出了10个随机数：Random random = new Random();random.ints().limit(10).forEach(System.out::println);countcount用来统计流中的元素个数。List<String> strings = Arrays.asList(“Hollis”, “HollisChuang”, “hollis”,“Hollis666”, “Hello”, “HelloWorld”, “Hollis”);System.out.println(strings.stream().count());//7collectcollect就是一个归约操作，可以接受各种做法作为参数，将流中的元素累积成一个汇总结果：List<String> strings = Arrays.asList(“Hollis”, “HollisChuang”, “hollis”,“Hollis666”, “Hello”, “HelloWorld”, “Hollis”);strings = strings.stream().filter(string -> string.startsWith(“Hollis”)).collect(Collectors.toList());System.out.println(strings);//Hollis, HollisChuang, Hollis666, Hollis接下来，我们还是使用一张图，来演示下，前文的例子中，当一个Stream先后通过filter、map、sort、limit以及distinct处理后会，在分别使用不同的最终操作可以得到怎样的结果：下图，展示了文中介绍的所有操作的位置、输入、输出以及使用一个案例展示了其结果。 总结本文介绍了Java 8中的Stream 的用途，优点等。还接受了Stream的几种用法，分别是Stream创建、中间操作和最终操作。Stream的创建有两种方式，分别是通过集合类的stream方法、通过Stream的of方法。Stream的中间操作可以用来处理Stream，中间操作的输入和输出都是Stream，中间操作可以是过滤、转换、排序等。Stream的最终操作可以将Stream转成其他形式，如计算出流中元素的个数、将流装换成集合、以及元素的遍历等。本文作者：hollischuang阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...

前言上一篇文章「前端面试题系列8」数组去重(10 种浓缩版) 中提到了不少数组的常用操作。今天，会更具体地将数组的常用操作进行归纳和汇总，以便备不时之需。每组方法都会配以示例说明，有时我也会忘了某个方法是否会返回一个新的数组，如果你也有类似的困惑，那么看这篇就够了。希望能帮到有需要的同学。ES5 中 Array 操作1、forEachArray 方法中最基本的一个，就是遍历，循环。基本用法：[].forEach(function(item, index, array) {});const array = [1, 2, 3];const result = [];array.forEach(function(item) { result.push(item);});console.log(result); // [1, 2, 3]2、mapmap 方法的作用不难理解，“映射”嘛，也就是原数组被 “映射” 成对应的新数组。基本用法跟 forEach 方法类似：[].map(function(item, index, array) {}); 下面这个例子是数值项求平方：const data = [1, 2, 3, 4];const arrayOfSquares = data.map(function (item) { return item * item;});alert(arrayOfSquares); // 1, 4, 9, 163、filterfilter 为 “过滤”、“筛选” 之意。指数组 filter 后，返回过滤后的新数组。用法跟 map 极为相似：[].filter(function(item, index, array) {});filter 的 callback 函数，需要返回布尔值 true 或 false。返回值只要 弱等于 Boolean 就行，看下面这个例子：const data = [0, 1, 2, 3];const arrayFilter = data.filter(function(item) { return item;});console.log(arrayFilter); // [1, 2, 3]4、some 和 everysome 意指“某些”，指是否 “某些项” 合乎条件。也就是 只要有1值个让 callback 返回 true 就行了。基本用法：[].som(function(item, index, array) {});const scores = [5, 8, 3, 10];const current = 7;function higherThanCurrent(score) { return score > current;}if (scores.some(higherThanCurrent)) { alert(“one more”);}every 跟 some 是一对好基友，同样是返回 Boolean 值。但必须满足每 1 个值都要让 callback 返回 true 才行。改动一下上面 some 的例子：if (scores.every(higherThanCurrent)) { console.log(“every is ok!”);} else { console.log(“oh no!”); }5、concatconcat() 方法用于连接两个或多个数组。该方法不会改变现有的数组，仅会返回被连接数组的一个副本。const arr1 = [1,2,3];const arr2 = [4,5];const arr3 = arr1.concat(arr2);console.log(arr1); // [1, 2, 3]console.log(arr3); // [1, 2, 3, 4, 5]6、indexOf 和 lastIndexOfindexOf 方法在字符串中自古就有，string.indexOf(searchString, position)。数组这里的 indexOf 方法与之类似。返回整数索引值，如果没有匹配（严格匹配），返回-1.fromIndex可选，表示从这个位置开始搜索，若缺省或格式不合要求，使用默认值0。const data = [2, 5, 7, 3, 5];console.log(data.indexOf(5, “x”)); // 1 (“x"被忽略)console.log(data.indexOf(5, “3”)); // 4 (从3号位开始搜索)console.log(data.indexOf(4)); // -1 (未找到)console.log(data.indexOf(“5”)); // -1 (未找到，因为5 !== “5”)lastIndexOf 则是从后往前找。const numbers = [2, 5, 9, 2];numbers.lastIndexOf(2); // 3numbers.lastIndexOf(7); // -1numbers.lastIndexOf(2, 3); // 3numbers.lastIndexOf(2, 2); // 0numbers.lastIndexOf(2, -2); // 0numbers.lastIndexOf(2, -1); // 37、reduce 和 reduceRightreduce 是JavaScript 1.8 中才引入的，中文意思为“归约”。基本用法：reduce(callback[, initialValue])callback 函数接受4个参数：之前值(previousValue)、当前值(currentValue)、索引值(currentIndex)以及数组本身(array)。可选的初始值(initialValue)，作为第一次调用回调函数时传给previousValue的值。也就是，为累加等操作传入起始值（额外的加值）。var sum = [1, 2, 3, 4].reduce(function (previous, current, index, array) { return previous + current;});console.log(sum); // 10解析：因为initialValue不存在，因此一开始的previous值等于数组的第一个元素从而 current 值在第一次调用的时候就是2最后两个参数为索引值 index 以及数组本身 array以下为循环执行过程：// 初始设置previous = initialValue = 1, current = 2// 第一次迭代previous = (1 + 2) = 3, current = 3// 第二次迭代previous = (3 + 3) = 6, current = 4// 第三次迭代previous = (6 + 4) = 10, current = undefined (退出)有了reduce，我们可以轻松实现二维数组的扁平化：var matrix = [ [1, 2], [3, 4], [5, 6]];// 二维数组扁平化var flatten = matrix.reduce(function (previous, current) { return previous.concat(current);});console.log(flatten); // [1, 2, 3, 4, 5, 6]reduceRight 跟 reduce 相比，用法类似。实现上差异在于reduceRight是从数组的末尾开始实现。const data = [1, 2, 3, 4];const specialDiff = data.reduceRight(function (previous, current, index) { if (index == 0) { return previous + current; } return previous - current;});console.log(specialDiff); // 08、push 和 poppush() 方法可向数组的末尾添加一个或多个元素，返回的是新的数组长度，会改变原数组。const a = [2,3,4];const b = a.push(5);console.log(a); // [2,3,4,5]console.log(b); // 4// push方法可以一次添加多个元素push(data1, data2….)pop() 方法用于删除并返回数组的最后一个元素。返回的是最后一个元素，会改变原数组。const arr = [2,3,4];console.log(arr.pop()); // 4console.log(arr); // [2,3]9、shift 和 unshiftshift() 方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。返回第一个元素，改变原数组。const arr = [2,3,4];console.log(arr.shift()); // 2console.log(arr); // [3,4]unshift() 方法可向数组的开头添加一个或更多元素，并返回新的长度。返回新长度，改变原数组。const arr = [2,3,4,5];console.log(arr.unshift(3,6)); // 6console.log(arr); // [3, 6, 2, 3, 4, 5]// tip:该方法可以不传参数,不传参数就是不增加元素。10、slice 和 spliceslice() 返回一个新的数组，包含从 start 到 end （不包括该元素）的 arrayObject 中的元素。返回选定的元素，该方法不会修改原数组。const arr = [2,3,4,5];console.log(arr.slice(1,3)); // [3,4]console.log(arr); // [2,3,4,5]splice() 可删除从 index 处开始的零个或多个元素，并且用参数列表中声明的一个或多个值来替换那些被删除的元素。如果从 arrayObject 中删除了元素，则返回的是含有被删除的元素的数组。splice() 方法会直接对数组进行修改。const a = [5,6,7,8];console.log(a.splice(1,0,9)); //[]console.log(a); // [5, 9, 6, 7, 8]const b = [5,6,7,8];console.log(b.splice(1,2,3)); //v[6, 7]console.log(b); // [5, 3, 8]11、sort 和 reversesort() 按照 Unicode code 位置排序，默认升序。const fruit = [‘cherries’, ‘apples’, ‘bananas’];fruit.sort(); // [‘apples’, ‘bananas’, ‘cherries’]const scores = [1, 10, 21, 2];scores.sort(); // [1, 10, 2, 21]reverse() 方法用于颠倒数组中元素的顺序。返回的是颠倒后的数组，会改变原数组。const arr = [2,3,4];console.log(arr.reverse()); // [4, 3, 2]console.log(arr); // [4, 3, 2]12、joinjoin() 方法用于把数组中的所有元素放入一个字符串。元素是通过指定的分隔符进行分隔的，默认使用’,‘号分割，不改变原数组。const arr = [2,3,4];console.log(arr.join()); // 2,3,4console.log(arr); // [2, 3, 4]13、isArrayArray.isArray() 用于确定传递的值是否是一个 Array。一个比较冷门的知识点：其实 Array.prototype 也是一个数组。Array.isArray([]); // trueArray.isArray(Array.prototype); // trueArray.isArray(null); // falseArray.isArray(undefined); // falseArray.isArray(18); // falseArray.isArray(‘Array’); // falseArray.isArray(true); // falseArray.isArray({ proto: Array.prototype });在公用库中，一般会这么做 isArray 的判断：Object.prototype.toString.call(arg) === ‘[object Array]’;ES6 新增的 Array 操作1、find 和 findIndexfind() 传入一个回调函数，找到数组中符合当前搜索规则的第一个元素，返回这个元素，并且终止搜索。const arr = [1, “2”, 3, 3, “2”]console.log(arr.find(n => typeof n === “number”)) // 1findIndex() 与 find() 类似，只是返回的是，找到的这个元素的下标。const arr = [1, “2”, 3, 3, “2”]console.log(arr.findIndex(n => typeof n === “number”)) // 02、fill用指定的元素填充数组，其实就是用默认内容初始化数组。基本用法：[].fill(value, start, end)该函数有三个参数：填充值(value)，填充起始位置(start，可以省略)，填充结束位置(end，可以省略，实际结束位置是end-1)。// 采用一个默认值，填充数组const arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];arr1.fill(7);console.log(arr1); // [7,7,7,7,7,7,7,7,7,7,7]// 制定开始和结束位置填充，实际填充结束位置是前一位。const arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];arr2.fill(7, 2, 5);console.log(arr2); // [1,2,7,7,7,6,7,8,9,10,11]// 结束位置省略，从起始位置到最后。const arr3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];arr3.fill(7, 2);console.log(arr3); // [1,2,7,7,7,7,7,7,7,7,7]3、from将类似数组的对象（array-like object）和可遍历（iterable）的对象转为真正的数组。const set = new Set(1, 2, 3, 3, 4);Array.from(set) // [1,2,3,4]Array.from(‘foo’); // [“f”, “o”, “o”]4、ofArray.of() 方法创建一个具有可变数量参数的新数组实例，而不考虑参数的数量或类型。Array.of() 和 Array 构造函数之间的区别在于处理整数参数：Array.of(7) 创建一个具有单个元素 7 的数组，而 Array(7) 创建一个长度为7的空数组（注意：这是指一个有7个空位的数组，而不是由7个undefined组成的数组）。Array.of(7); // [7] Array.of(1, 2, 3); // [1, 2, 3]Array(7); // [ , , , , , , ]Array(1, 2, 3); // [1, 2, 3]5、copyWithin选择数组的某个下标，从该位置开始复制数组元素，默认从0开始复制。也可以指定要复制的元素范围。基本用法：[].copyWithin(target, start, end)const arr = [1, 2, 3, 4, 5];console.log(arr.copyWithin(3)); // [1,2,3,1,2] 从下标为3的元素开始，复制数组，所以4, 5被替换成1, 2const arr1 = [1, 2, 3, 4, 5];console.log(arr1.copyWithin(3, 1)); // [1,2,3,2,3] 从下标为3的元素开始，复制数组，指定复制的第一个元素下标为1，所以4, 5被替换成2, 3const arr2 = [1, 2, 3, 4, 5];console.log(arr2.copyWithin(3, 1, 2));// [1,2,3,2,5] 从下标为3的元素开始，复制数组，指定复制的第一个元素下标为1，结束位置为2，所以4被替换成26、includes判断数组中是否存在该元素，参数：查找的值、起始位置，可以替换 ES5 时代的 indexOf 判断方式。const arr = [1, 2, 3];arr.includes(2); // truearr.includes(4); // false另外，它还可以用于优化 || 的判断写法。if (method === ‘post’ || method === ‘put’ || method === ‘delete’) { …}// 用 includes 优化 || 的写法if ([‘post’, ‘put’, ‘delete’].includes(method)) { …}7、entries、values 和 keysentries() 返回迭代器：返回键值对//数组const arr = [‘a’, ‘b’, ‘c’];for(let v of arr.entries()) { console.log(v)}// [0, ‘a’] [1, ‘b’] [2, ‘c’]//Setconst arr = new Set([‘a’, ‘b’, ‘c’]);for(let v of arr.entries()) { console.log(v)}// [‘a’, ‘a’] [‘b’, ‘b’] [‘c’, ‘c’]//Mapconst arr = new Map();arr.set(‘a’, ‘a’);arr.set(‘b’, ‘b’);for(let v of arr.entries()) { console.log(v)}// [‘a’, ‘a’] [‘b’, ‘b’]values() 返回迭代器：返回键值对的 value//数组const arr = [‘a’, ‘b’, ‘c’];for(let v of arr.values()) { console.log(v)}//‘a’ ‘b’ ‘c’//Setconst arr = new Set([‘a’, ‘b’, ‘c’]);for(let v of arr.values()) { console.log(v)}// ‘a’ ‘b’ ‘c’//Mapconst arr = new Map();arr.set(‘a’, ‘a’);arr.set(‘b’, ‘b’);for(let v of arr.values()) { console.log(v)}// ‘a’ ‘b’keys() 返回迭代器：返回键值对的 key//数组const arr = [‘a’, ‘b’, ‘c’];for(let v of arr.keys()) { console.log(v)}// 0 1 2//Setconst arr = new Set([‘a’, ‘b’, ‘c’]);for(let v of arr.keys()) { console.log(v)}// ‘a’ ‘b’ ‘c’//Mapconst arr = new Map();arr.set(‘a’, ‘a’);arr.set(‘b’, ‘b’);for(let v of arr.keys()) { console.log(v)}// ‘a’ ‘b’总结操作 Array 的数据结构，在日常工作中会经常遇到。ES6 在 Array 的操作上，也提供了更为简便实用的方法，比如 includes、find、from 等等。过去，我会习惯于用 lodash 的 _.find 方法，现在就可以选择拥抱原生了。PS：欢迎关注我的公众号 “超哥前端小栈”，交流更多的想法与技术。 ...

本系列翻译自开源项目 30-seconds-of-code这是一个非常优秀的系列，文章总结了大量的使用es6语法实现的代码模块不是说真的三十秒就能理解，也需要你认真的思考，其中有一些点非常精妙，很值得一读。本文在我的github同步更新，你可以看到当前翻译的全部系列。如果您对本期有不同或者更好的见解，请在下方评论告，喜欢请点个赞，谢谢阅读。ary创建一个可以接收n个参数的函数, 忽略其他额外的参数。调用提供的函数fn,参数最多为n个, 使用 Array.prototype.slice(0,n) 和展开操作符 (…)。const ary = (fn, n) => (…args) => fn(…args.slice(0, n));示例const firstTwoMax = ary(Math.max, 2);[[2, 6, ‘a’], [8, 4, 6], [10]].map(x => firstTwoMax(…x)); // [6, 8, 10]call给定一个key和一组参数，给定一个上下文时调用它们。主要用于合并。使用闭包调用上下文中key对应的值，即带有存储参数的函数。const call = (key, …args) => context => contextkey;示例Promise.resolve([1, 2, 3]) .then(call(‘map’, x => 2 * x)) .then(console.log); // [ 2, 4, 6 ]const map = call.bind(null, ‘map’);Promise.resolve([1, 2, 3]) .then(map(x => 2 * x)) .then(console.log); // [ 2, 4, 6 ]collectInto将一个接收数组参数的函数改变为可变参数的函数。给定一个函数，返回一个闭包，该闭包将所有输入收集到一个数组接受函数中。const collectInto = fn => (…args) => fn(args);示例const Pall = collectInto(Promise.all.bind(Promise));let p1 = Promise.resolve(1);let p2 = Promise.resolve(2);let p3 = new Promise(resolve => setTimeout(resolve, 2000, 3));Pall(p1, p2, p3).then(console.log); // [1, 2, 3] (after about 2 seconds)flipFlip以一个函数作为参数，然后把第一个参数作为最后一个参数。返回一个可变参数的闭包，在应用其他参数前，先把第一个以外的其他参数作为第一个参数。const flip = fn => (first, …rest) => fn(…rest, first);示例let a = { name: ‘John Smith’ };let b = {};const mergeFrom = flip(Object.assign);let mergePerson = mergeFrom.bind(null, a);mergePerson(b); // == bb = {};Object.assign(b, a); // == bover创建一个函数，这个函数可以调用每一个被传入的并且才有参数的函数，然后返回结果。使用 Array.prototype.map() 和 Function.prototype.apply()将每个函数应用给定的参数。const over = (…fns) => (…args) => fns.map(fn => fn.apply(null, args));示例const minMax = over(Math.min, Math.max);minMax(1, 2, 3, 4, 5); // [1,5]overArgs创建一个函数，它可以调用提供的被转换参数的函数。使用Array.prototype.map()将transforms应用于args，并结合扩展运算符(…)将转换后的参数传递给fn。const overArgs = (fn, transforms) => (…args) => fn(…args.map((val, i) => transformsi));示例const square = n => n * n;const double = n => n * 2;const fn = overArgs((x, y) => [x, y], [square, double]);fn(9, 3); // [81, 6]pipeAsyncFunctions为异步函数执行从左到右的函数组合。在扩展操作符(…)中使用Array.prototype.reduce() 来使用Promise.then()执行从左到右的函数组合。这些函数可以返回简单值、Promise的组合，也可以定义为通过await返回的async值。所有函数必须是一元的。const pipeAsyncFunctions = (…fns) => arg => fns.reduce((p, f) => p.then(f), Promise.resolve(arg));示例const sum = pipeAsyncFunctions( x => x + 1, x => new Promise(resolve => setTimeout(() => resolve(x + 2), 1000)), x => x + 3, async x => (await x) + 4);(async() => { console.log(await sum(5)); // 15 (after one second)})();pipeFunctions执行从左到右的函数组合。在展开操作符(…)中使用Array.prototype.reduce()来执行从左到右的函数组合。第一个(最左边的)函数可以接受一个或多个参数; 其余的函数必须是一元的。const pipeFunctions = (…fns) => fns.reduce((f, g) => (…args) => g(f(…args)));示例const add5 = x => x + 5;const multiply = (x, y) => x * y;const multiplyAndAdd5 = pipeFunctions(multiply, add5);multiplyAndAdd5(5, 2); // 15promisify把一个异步函数转换成返回promise的。使用局部套用返回一个函数，该函数返回一个调用原始函数的Promise。使用的…操作符来传入所有参数。const promisify = func => (…args) => new Promise((resolve, reject) => func(…args, (err, result) => (err ? reject(err) : resolve(result))) );示例const delay = promisify((d, cb) => setTimeout(cb, d));delay(2000).then(() => console.log(‘Hi!’)); // Promise resolves after 2srearg创建一个调用提供的函数的函数，该函数的参数按照指定的索引排列。利用 Array.prototype.map() 根据 indexes 和展开操作符 (…) 对参数进行重新排序，将转换后的参数传递给 fn.const rearg = (fn, indexes) => (…args) => fn(…indexes.map(i => args[i]));示例var rearged = rearg( function(a, b, c) { return [a, b, c]; }, [2, 0, 1]);rearged(‘b’, ‘c’, ‘a’); // [‘a’, ‘b’, ‘c’]spreadOver接受一个可变参数函数并返回一个闭包，该闭包接受一个参数数组以映射到函数的输入。使用闭包和扩展操作符(…)将参数数组映射到函数的输入。const spreadOver = fn => argsArr => fn(…argsArr);示例const arrayMax = spreadOver(Math.max);arrayMax([1, 2, 3]); // 3unary创建一个最多接受一个参数的函数，忽略任何其他参数。只把第一个参数传递给要调用的函数fn。const unary = fn => val => fn(val);示例[‘6’, ‘8’, ‘10’].map(unary(parseInt)); // [6, 8, 10]推荐阅读【React深入】setState的执行机制【React深入】React事件机制 ...

最近的MySQL8.0.14版本增加了其第一个并行查询特性，可以支持在聚集索引上做SELECT COUNT()和check table操作。本文简单的介绍下这个特性。用法增加了一个session级别参数: innodb_parallel_read_threads要执行并行查询，需要满足如下条件(ref: row_scan_index_for_mysql)无锁查询聚集索引不是Insert…select需要参数设置为>1相关代码入口函数:row_scan_index_for_mysql parallel_select_count_star // for select count() parallel_check_table // for check tableInnoDB里实现了两种查询方式，一种是基于key的(key reader)， 根据叶子节点上的值做分区，需要判断可见性；另外一种是基于page的(physical read)，根据page no来做分区，无需判断可见性。目前支持的两种查询都是key reader的方式。使用如下代码创建一个reader，并调用接口函数，read()函数里的回调函数包含了如何对获取到的行数据进行处理:Key_reader reader(prebuilt->table, trx, index, prebuilt, n_threads);reader.read(func), 其中func是回调函数，用于告诉线程怎么处理得到的每一行分区并计算线程数分区入口：template <typename T, typename R>typename Reader<T, R>::Ranges Reader<T, R>::partition()流程：搜集btree的最左节点page no从root page开始向下，尝试构建子树：如果该level的page个数不足线程数，继续往下走否则，使用该level, 搜集该level的每个page的最左记录向下直到叶子节点的最左链表如上搜集到的是多条代表自上而下的page no数组，需要根据这些数组创建分区range，这里有两种创建方式：Key_reader::Ranges Key_reader::create_ranges: 基于键值创建分区找到每个链表的叶子节点的第一条记录，存储其cursor作为当前range的起点和上一个range的终点Phy_reader::Ranges Phy_reader::create_ranges：基于物理页创建分区找到每个链表的叶子节点，相邻链表的叶子节点组成一个range线程数取分区数和配置线程数的最小值启动线程启动线程各自扫描: start_parallel_load为每个分区创建context(class Reader::Ctx)，加入到队列中实现了一个Lock-free的队列模型，多线程可以并发的从队列中取context: 实现细节在文件include/ut0mpmcbq.h中，对应类 class mpmc_bq, 实现思路见链接线程函数：dberr_t Reader<T, R>::worker(size_t id, Queue &ctxq, Function &f)每取一个分区，调用处理函数去遍历分区：Key_reader::traverse对于获得的每条记录，判断其可见性（共享事务对象trx_t），调用回调函数处理记录（在Key_reader::read()作为参数传递）,对于select count(), 就是累加记录的计数器Phy_reader::traverse读取每条非标记删除的记录并调用回调函数处理，无需判断可见性对于异常情况，只返回最后一个context的错误码。该特性只是MySQL在并行查询的第一步，甚至定义了一些接口还没有使用，例如接口函数pread_adapter_scan_get_num_threads, 估计是给未来server层做并行查询使用的。代码里对应两个适配类：Parallel_reader_adapterParallel_partition_reader_adapter另外一个可以用到的地方是创建二级索引，我们知道InnoDB创建二级索引，是先从聚集索引读取记录，生成多个merge file，然后再做归并排序，但无论是生成merge file，还是排序，都可以做到并行化。官方也提到这是未来的一个优化点，相信不久的将来，我们就能看到MySQL更为强大的并行查询功能。ReferenceWL#11720: InnoDB: Parallel read of indexMySQL 8.0.14: A Road to Parallel Query Execution is Wide Open!本文作者：zhaiwx_yinfeng.阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...

翻译：疯狂的技术宅原文： http://2ality.com/2018/12/cre…本文首发微信公众号：jingchengyideng欢迎关注，每天都给你推送新鲜的前端技术文章创建数组的最佳方法是通过字面方式：const arr = [0,0,0];不过这并不是长久之计，比如当我们需要创建大型数组时。这篇博文探讨了在这种情况下应该怎么做。没有空洞的数组往往表现得更好在大多数编程语言中，数组是连续的值序列。在 JavaScript 中，Array 是一个将索引映射到元素的字典。它可以存在空洞（holes） —— 零和数组长度之间的索引没有映射到元素（“缺失索引”）。例如，下面的 Array 在索引 1 处有一个空洞：> Object.keys([‘a’,, ‘c’])[ ‘0’, ‘2’ ]没有空洞的数组也称为 dense 或 packed。密集数组往往表现更好，因为它们可以连续存储（内部）。一旦出现了空洞，内部表示就必须改变。我们有两种选择：字典。查找时会消耗更多时间，而且存储开销更大。连续的数据结构，对空洞进行标记。然后检查对应的值是否是一个空洞，这也需要额外的时间。不管是哪种情况，如果引擎遇到一个空洞，它不能只返回 undefined，它必须遍历原型链并搜索一个名称为“空洞索引”的属性，这需要花费更多时间。在某些引擎中，例如V8，如果切换到性能较低的数据结构，这种改变将会是永久性的。即使所有空洞都被填补，它们也不会再切换回来了。关于 V8 是如何表示数组的，请参阅Mathias Bynens的文章“V8中的元素类型”。创建数组Array 构造函数如果要创建具有给定长度的 Array，常用的方法是使用 Array 构造函数 ：const LEN = 3;const arr = new Array(LEN);assert.equal(arr.length, LEN);// arr only has holes in itassert.deepEqual(Object.keys(arr), []);这种方法很方便，但是有两个缺点：即便你稍后再用值把数组完全填满，这种空洞也会使这个 Array 略微变慢。空洞的默认值一般不会是元素的初始“值”。常见的默认值是零。在 Array 构造函数后面加上 .fill() 方法.fill()方法会更改当前的 Array 并使用指定的值去填充它。这有助于在用 new Array() 创建数组后对其进行初始化：const LEN = 3;const arr = new Array(LEN).fill(0);assert.deepEqual(arr, [0, 0, 0]);警告：如果你用对象作为参数去 .fill() 一个数组，所有元素都会引用同一个实例（也就是这个对象没有被克隆多份）：const LEN = 3;const obj = {};const arr = new Array(LEN).fill(obj);assert.deepEqual(arr, [{}, {}, {}]);obj.prop = true;assert.deepEqual(arr, [ {prop:true}, {prop:true}, {prop:true} ]);稍后我们会遇到的一种填充方法（ Array.from() ）则没有这个问题。.push() 方法const LEN = 3;const arr = [];for (let i=0; i < LEN; i++) { arr.push(0);}assert.deepEqual(arr, [0, 0, 0]);这一次，我们创建并填充了一个数组，同时里面没有出现漏洞。所以操作这个数组时应该比用构造函数创建的更快。不过 创建 数组的速度比较慢，因为引擎可能需要随着数组的增长多次重新分配连续的内存。使用 undefined 填充数组Array.from() 将 iterables 和类似数组的值转换为 Arrays ，它将空洞视为 undefined 元素。这样可以用它将每个空洞都转换为 undefined：> Array.from({length: 3})[ undefined, undefined, undefined ]参数 {length：3} 是一个长度为 3 的类似 Array 的对象，其中只包含空洞。也可以使用 new Array(3)，但这样一般会创建更大的对象。下面这种方式仅适用于可迭代的值，并且与 Array.from()具有类似的效果：> […new Array(3)][ undefined, undefined, undefined ]不过 Array.from()通过 new Array() 创建它的结果，所以你得到的仍然是一个稀疏数组。使用 Array.from() 进行映射如果提供映射函数作为其第二个参数，则可以使用 Array.from() 进行映射。用值填充数组使用小整数创建数组：> Array.from({length: 3}, () => 0)[ 0, 0, 0 ]使用唯一（非共享的）对象创建数组：> Array.from({length: 3}, () => ({}))[ {}, {}, {} ]按照数值范围进行创建用升序整数数列创建数组：> Array.from({length: 3}, (x, i) => i)[ 0, 1, 2 ]用任意范围的整数进行创建：> const START=2, END=5;> Array.from({length: END-START}, (x, i) => i+START)[ 2, 3, 4 ]另一种创建升序整数数组的方法是用 .keys()，它也将空洞看作是 undefined 元素：> […new Array(3).keys()][ 0, 1, 2 ].keys()返回一个可迭代的序列。我们将其展开并转换为数组。备忘速查：创建数组用空洞或 undefined填充：new Array(3)→ [ , , ,]Array.from({length: 2})→ [undefined, undefined][…new Array(2)]→ [undefined, undefined]填充任意值：const a=[]; for (let i=0; i<3; i++) a.push(0);→ [0, 0, 0]new Array(3).fill(0)→ [0, 0, 0]Array.from({length: 3}, () => ({}))→ [{}, {}, {}] （唯一对象）用整数范围填充：Array.from({length: 3}, (x, i) => i)→ [0, 1, 2]const START=2, END=5; Array.from({length: END-START}, (x, i) => i+START)→ [2, 3, 4][…new Array(3).keys()]→ [0, 1, 2]推荐的模式我更喜欢下面的方法。我的侧重点是可读性，而不是性能。你是否需要创建一个空的数组，以后将会完全填充？new Array(LEN)你需要创建一个用原始值初始化的数组吗？new Array(LEN).fill(0)你需要创建一个用对象初始化的数组吗？Array.from({length: LEN}, () => ({}))你需要创建一系列整数吗？Array.from({length: END-START}, (x, i) => i+START)如果你正在处理整数或浮点数的数组，请考虑Typed Arrays —— 它就是为这个目的而设计的。它们不能存在空洞，并且总是用零进行初始化。提示：一般来说数组的性能无关紧要对于大多数情况，我不会过分担心性能。即使是带空洞的数组也很快。使代码易于理解更有意义。另外引擎优化的方式和位置也会发生变化。今天最快的方案可能明天就不是了。致谢感谢 Mathias Bynens 和 Benedikt Meurer 帮我了解 V8 的详细信息。扩展阅读Chapter “Typed Arrays” in “Exploring ES6”Sect. “ES6 and holes in Arrays” in “Exploring ES6”本文首发微信公众号：jingchengyideng欢迎扫描二维码关注公众号，每天都给你推送新鲜的前端技术文章欢迎继续阅读本专栏其它高赞文章：12个令人惊叹的CSS实验项目世界顶级公司的前端面试都问些什么CSS Flexbox 可视化手册过节很无聊？还是用 JavaScript 写一个脑力小游戏吧！从设计者的角度看 ReactCSS粘性定位是怎样工作的一步步教你用HTML5 SVG实现动画效果程序员30岁前月薪达不到30K，该何去何从第三方CSS安全吗？谈谈super(props) 的重要性 ...

一 历史在c99标准出来之前。如果要在某个结构体中使用字符串变时，为了使字符串变量存储地址能与结构体整体连在一起，需要这样实现#include <stdio.h>#include <malloc.h>#include <string.h>typedef struct pen{ int len; char data;//字符串变量}pen;int main(int argc, char argv){ char str[] = “this is a string”;//需要填入的字符串 / 动态申请一个pen类型结构体变量， 它的大小为，pen类型的本身长度， 再加上str（需要填入字符串的长度）,再加1， / struct pen p = (struct pen)malloc(sizeof(pen) + strlen(str) + 1); p->data= NULL; //设置p的长度为目标字符串的长度 p->len = strlen(str); / 将目标字符串拷贝到结构体对应的位置 此处为什么p+1之后指向的是pen结构体存储空间后的位置，而不是只加一呢？ 因为此处的p+1偏移的是p指向类型大小的偏移量，什么意思呢？p指向的类型为pen类型的结构体， 而pen类型的结构体大小为 len（4字节）加上 data（8个字节），由于此处有内存对齐的情况， 所以实际上pen大小为 4 + 8 + 4（这个4为内存对齐的多余空间，如果再增加一个int类型的变量， pen的大小还是为16）=16字节 所以此处p+1向后偏移了16字节，通过下方地址打印可以详细看出 / strcpy((char)(p + 1), str); //int所占字节数，不同机器不同。一般64位为4字节 printf(“sizeof(int): %ld\n”, sizeof(int)); //上文已说明，16字节 printf(“sizeof(pen): %ld\n”, sizeof(pen)); //起始地址 printf(“start: %p\n\n”, (char)p); //上文已说明，偏移后的地址 printf("(p+1) : %p\n", (char)(p+1)); //偏移后，对应的字符串 printf("(char*)(p+1): %s\n\n", (char*)(p+1)); //结构体变量data的地址 printf("&(p->data): %p\n", &(p->data)); //数据，null，此处为空，故此变量已经被浪费。访问对应字符串数据需要(char *)(p+1) printf(“p->data: %s\n\n”, p->data);}二 柔性数组通过上文我们可以看到，data字段是一个被浪费的指针（8个字节）。并且我们想取到结构体下的字符串变量时需要(char *)(p+1)写这么一串东西，既不好看，也容易出错，那有没有可以直接用p->data取到字符串并且内存是连续的，而且又不浪费data字段呢， 柔性数组 就是用来干这个的。#include <stdio.h>#include <malloc.h>#include <string.h>typedef struct pen{ int len; char data[];//柔性数组}pen;int main(int argc, char **argv){ char str[] = “this is a new string”;//需要填入的字符串 struct pen p = (struct pen)malloc(sizeof(pen) + strlen(str) + 1); p->data= NULL; p->len = strlen(str); strcpy((char *)(p+1), str); printf(“pen->data: %s\n”, p->data);}C99使用不完整类型实现柔性数组成员，在C99 中，结构中的最后一个元素允许是未知大小的数组，这就叫做柔性数组(flexible array)成员(也叫伸缩性数组成员)，但结构中的柔性数组成员前面必须至少一个其他成员。柔性数组成员允许结构中包含一个大小可变的数组。柔性数组成员只作为一个符号地址存在，而且必须是结构体的最后一个成员，sizeof 返回的这种结构大小不包括柔性数组的内存 （此段话摘自:https://blog.csdn.net/ce123_z…） ...

题目要求Design a data structure that supports all following operations in average O(1) time.Note: Duplicate elements are allowed.insert(val): Inserts an item val to the collection.remove(val): Removes an item val from the collection if present.getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.Example:// Init an empty collection.RandomizedCollection collection = new RandomizedCollection();// Inserts 1 to the collection. Returns true as the collection did not contain 1.collection.insert(1);// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].collection.insert(1);// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].collection.insert(2);// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.collection.getRandom();// Removes 1 from the collection, returns true. Collection now contains [1,2].collection.remove(1);// getRandom should return 1 and 2 both equally likely.collection.getRandom();设计一个数据结构，支持能够在O(1)的时间内完成对数字的插入，删除和获取随机数的操作，允许插入重复的数字，同时要求每个数字被随机获取的概率和该数字当前在数据结构中的个数成正比。强烈建议先看一下这个问题的基础版本，传送门在这里。思路和代码遵循之前基础版本的思路，当解决这种问题的时候我们会用数组和hashmap来做位置的存储，从而更新的时候无需检索。但是在这题的情境下，存在一个问题，举个例子：假如现在插入1,2,3,3,4,3,3此时的map中应当是如下：1:[0] 2:[1] 3:[2,3,5,6] 4:[4]我们先执行删除1，按照之前的规则，我们会删除数组中最后一个元素，并将其值移动到这个位置上map应当被更新为2:[1] 3:[2,3,5,0] 4:[4]接着我们再删除2，此时虽然最后一个元素还是3，但是这个3在位置数组中的位置却是需要O(n)的时间来查询的，这就违反了O(1)的删除时间复杂度。网上有一些java实现采用OrderSet来解决，这是不合理的。因为有序堆本质上底层是一个最大堆或最小堆，它的插入和删除操作都需要O(lgn)的时间复杂度来完成这里我们采用的方式是继续冗余，即我们在插入每一个元素的时候，同时记录该元素在下标数组中的位置，举个例子：先插入1，则map的值为[1:[0]]，list的值为[[1,0]] 此处的0代表1这个值在下标数组[0]中位于第0个位置上。在插入2，则map的值为[1:[0], 2:[1]], list的值为[[1,0],[2,0]]再插入1，此时map=[1:[0, 2], 2:[1], list的值为[[1,0],[2,0],[1,1]]此时删除2，同理，我们还是会将数组中最后一个元素的值替换在删除掉元素的位置，此处我们从map中得出2最后一次在数组中出现的下标为1，我们需要将最后位置上的1替换掉当前2的值，之后我们还能从数组中得知，1这个数字它对应的位置下标的索引为2，因此我们再将map[1]中map[1][2]的值替换为2所在的新的位置，即1。此时的map=[1:[0, 1], 2:[] list=[[1,0], [1,1]]代码如下：public class InsertDeleteGetRandomDuplicatesallowed_381 { private List<Pair> list; private Map<Integer, List<Integer>> index; /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. / public InsertDeleteGetRandomDuplicatesallowed_381() { list = new ArrayList<>(); index = new HashMap<>(); } public boolean insert(int val) { boolean contains = true; if(!index.containsKey(val) || index.get(val).isEmpty()) { contains = false; } List<Integer> tmp = index.getOrDefault(val, new ArrayList<>()); tmp.add(list.size()); index.put(val, tmp); list.add(new Pair(val, tmp.size()-1)); return !contains; } /* Removes a value from the collection. Returns true if the collection contained the specified element. / public boolean remove(int val) { if(!index.containsKey(val) || index.get(val).isEmpty()) { return false; } List<Integer> tmp = index.get(val); int position = tmp.remove(tmp.size()-1); if(position != list.size()-1) { Pair lastPair = list.get(list.size()-1); int lastValue = lastPair.value; List<Integer> lastValuePositions = index.get(lastValue); lastValuePositions.set(lastPair.position, position); list.set(position, lastPair); } list.remove(list.size()-1); return true; } /* Get a random element from the collection. */ public int getRandom() { int position = (int)Math.floor((Math.random() * list.size())); return list.get(position).value; } public static class Pair{ int value; int position; public Pair(int value, int position) { this.value = value; this.position = position; } } } ...

题目要求Design a data structure that supports all following operations in average O(1) time.insert(val): Inserts an item val to the set if not already present.remove(val): Removes an item val from the set if present.getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.Example:// Init an empty set.RandomizedSet randomSet = new RandomizedSet();// Inserts 1 to the set. Returns true as 1 was inserted successfully.randomSet.insert(1);// Returns false as 2 does not exist in the set.randomSet.remove(2);// Inserts 2 to the set, returns true. Set now contains [1,2].randomSet.insert(2);// getRandom should return either 1 or 2 randomly.randomSet.getRandom();// Removes 1 from the set, returns true. Set now contains [2].randomSet.remove(1);// 2 was already in the set, so return false.randomSet.insert(2);// Since 2 is the only number in the set, getRandom always return 2.randomSet.getRandom();设计一个数据结构，使得能够在O(1)的时间复杂度中插入数字，删除数字，以及随机获取一个数字。要求所有的数字都能够被等概率的随机出来。思路和代码其实有几个思路入手：如何实现O(1)的插入这里数字的插入还需要能够去重，即需要首先判断该数字是否已经存在，已经存在的话就不执行任何插入操作。如果底层是一个一般的数组，我们知道查询的时间复杂度为O(n)，明显不满足题目的意思。一个有序的数组能够将查询的时间复杂度下降到O(lgn），但是这依然不满足条件1，而且也无法做到所有的元素被等概率的查询出来，因为每插入一个元素都将改动之前元素的位置。而唯一能够做到O(1)时间查询的只有一个数据结构，即hash。因此，使用hash来查询时不可避免的。如何实现O(1)的删除这个其实是一个很经典的问题了，只要能够利用hash在O(1)的时间内找到这个数字的位置，就有两种方法来实现O(1)的删除，一个是利用伪删除，即每一个位置都对应一个状态为，将状态位社会为已经删除即可，还有一种就更有意思，就是将被删除位替换为数组最后一位的值，然后只需要删除最后一位就行。这种删除就无需将删除位右侧的元素全部左移造成O(n)的时间复杂度。这里我们采用的是第二种方法。如何实现O(1)的随机查询这个其实就是强调一点，我们需要维持原有的插入顺序，从而保证各个元素等概率被随机。综上所述，我们底层需要两种数据结构，一个hashmap来支持O(1)的查询，以及一个list来支持随机数的获取。代码实现如下：public class InsertDeleteGetRandom_380 { private List<Integer> list; private Map<Integer, Integer> hash; public InsertDeleteGetRandom_380() { list = new ArrayList<Integer>(); hash = new HashMap<Integer, Integer>(); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. / public boolean insert(int val) { if(hash.containsKey(val)) { return false; } list.add(val); hash.put(val, list.size()-1); return true; } /* Removes a value from the set. Returns true if the set contained the specified element. / public boolean remove(int val) { if(!hash.containsKey(val)){ return false; } int position = hash.get(val); if(position != list.size()-1) { int last = list.get(list.size()-1); list.set(position, last); hash.put(last, position); } list.remove(list.size()-1); hash.remove(val); return true; } /* Get a random element from the set. */ public int getRandom() { int position = (int)Math.floor((Math.random() * list.size())); return list.get(position); }} ...

一、数组元素为 1100 内的整数，长度为 N，且数字不重复，如何查找缺失的数字题目：给定一数组如 [1, 2, 3, 5]，如何查找出缺失的数字 4.解题思路：数字有规律，1100 内的连续数字，只缺失一个数字，只要求和相减即可 (Sum1 - Sum2)。其中， Sum1 代表的是完整不缺数字的期待总和，等于 1+2+3+4+5=5*(5+1)/2=15，其演变表达式为 N(N+1)/2; Sum2 代表是的数组元素的总和，等于 1+2+3+5=11。所以缺失的数字为 4=15-11.Javascript 实现：function getMissingNum(arr){ var n = arr.length + 1; // N + 1, 最大项 var expectedSum = n * (n + 1) / 2; // Sum1 var sum = 0; // Sum2 arr.map(item=>sum+=item); return expectedSum - sum;}

本文来自GitHub开源项目点我跳转30秒的PHP代码片段精选的有用PHP片段集合，您可以在30秒或更短的时间内理解这些片段。排列all如果所提供的函数返回 true 的数量等于数组中成员数量的总和，则函数返回 true，否则返回 false。function all($items, $func){ return count(array_filter($items, $func)) === count($items);}Examplesall([2, 3, 4, 5], function ($item) { return $item > 1;}); // trueany如果提供的函数对数组中的至少一个元素返回true，则返回true，否则返回false。function any($items, $func){ return count(array_filter($items, $func)) > 0;}Examplesany([1, 2, 3, 4], function ($item) { return $item < 2;}); // truedeepFlatten(深度平铺数组)将多维数组转为一维数组function deepFlatten($items){ $result = []; foreach ($items as $item) { if (!is_array($item)) { $result[] = $item; } else { $result = array_merge($result, deepFlatten($item)); } } return $result;}ExamplesdeepFlatten([1, [2], [[3], 4], 5]); // [1, 2, 3, 4, 5]drop返回一个新数组，并从左侧弹出n个元素。function drop($items, $n = 1){ return array_slice($items, $n);}Examplesdrop([1, 2, 3]); // [2,3]drop([1, 2, 3], 2); // [3]findLast返回所提供的函数为其返回的有效值（即过滤后的值）的最后一个元素的键值（value）。function findLast($items, $func){ $filteredItems = array_filter($items, $func); return array_pop($filteredItems);}ExamplesfindLast([1, 2, 3, 4], function ($n) { return ($n % 2) === 1;});// 3findLastIndex返回所提供的函数为其返回的有效值（即过滤后的值）的最后一个元素的键名（key）。function findLastIndex($items, $func){ $keys = array_keys(array_filter($items, $func)); return array_pop($keys);}ExamplesfindLastIndex([1, 2, 3, 4], function ($n) { return ($n % 2) === 1;});// 2flatten(平铺数组)将数组降为一维数组function flatten($items){ $result = []; foreach ($items as $item) { if (!is_array($item)) { $result[] = $item; } else { $result = array_merge($result, array_values($item)); } } return $result;}Examplesflatten([1, [2], 3, 4]); // [1, 2, 3, 4]groupBy根据给定的函数对数组的元素进行分组。function groupBy($items, $func){ $group = []; foreach ($items as $item) { if ((!is_string($func) && is_callable($func)) || function_exists($func)) { $key = call_user_func($func, $item); $group[$key][] = $item; } elseif (is_object($item)) { $group[$item->{$func}][] = $item; } elseif (isset($item[$func])) { $group[$item[$func]][] = $item; } } return $group;}ExamplesgroupBy([‘one’, ’two’, ’three’], ‘strlen’); // [3 => [‘one’, ’two’], 5 => [’three’]]hasDuplicates(查重)检查数组中的重复值。如果存在重复值，则返回true；如果所有值都是唯一的，则返回false。function hasDuplicates($items){ return count($items) > count(array_unique($items));}ExampleshasDuplicates([1, 2, 3, 4, 5, 5]); // truehead返回数组中的第一个元素。function head($items){ return reset($items);}Exampleshead([1, 2, 3]); // 1last返回数组中的最后一个元素。function head($items){ return reset($items);}Exampleslast([1, 2, 3]); // 3pluck检索给定键名的所有键值function pluck($items, $key){ return array_map( function($item) use ($key) { return is_object($item) ? $item->$key : $item[$key]; }, $items);}Examplespluck([ [‘product_id’ => ‘prod-100’, ’name’ => ‘Desk’], [‘product_id’ => ‘prod-200’, ’name’ => ‘Chair’],], ’name’);// [‘Desk’, ‘Chair’]pull修改原始数组以过滤掉指定的值。function pull(&$items, …$params){ $items = array_values(array_diff($items, $params)); return $items;}Examples$items = [‘a’, ‘b’, ‘c’, ‘a’, ‘b’, ‘c’];pull($items, ‘a’, ‘c’); // $items will be [‘b’, ‘b’]reject使用给定的回调筛选数组。function reject($items, $func){ return array_values(array_diff($items, array_filter($items, $func)));}Examplesreject([‘Apple’, ‘Pear’, ‘Kiwi’, ‘Banana’], function ($item) { return strlen($item) > 4;}); // [‘Pear’, ‘Kiwi’]remove从给定函数返回false的数组中删除元素。function remove($items, $func){ $filtered = array_filter($items, $func); return array_diff_key($items, $filtered);}Examplesremove([1, 2, 3, 4], function ($n) { return ($n % 2) === 0;});// [0 => 1, 2 => 3]tail返回数组中的所有元素，第一个元素除外。function tail($items){ return count($items) > 1 ? array_slice($items, 1) : $items;}Examplestail([1, 2, 3]); // [2, 3]take返回一个数组，其中从开头删除了n个元素。function take($items, $n = 1){ return array_slice($items, 0, $n);}Examplestake([1, 2, 3], 5); // [1, 2, 3]take([1, 2, 3, 4, 5], 2); // [1, 2]without筛选出给定值之外的数组元素。function without($items, …$params){ return array_values(array_diff($items, $params));}Exampleswithout([2, 1, 2, 3, 5, 8], 1, 2, 8); // [3, 5]orderBy按键名对数组或对象的集合进行排序。function orderBy($items, $attr, $order){ $sortedItems = []; foreach ($items as $item) { $key = is_object($item) ? $item->{$attr} : $item[$attr]; $sortedItems[$key] = $item; } if ($order === ‘desc’) { krsort($sortedItems); } else { ksort($sortedItems); } return array_values($sortedItems);}ExamplesorderBy( [ [‘id’ => 2, ’name’ => ‘Joy’], [‘id’ => 3, ’name’ => ‘Khaja’], [‘id’ => 1, ’name’ => ‘Raja’] ], ‘id’, ‘desc’); // [[‘id’ => 3, ’name’ => ‘Khaja’], [‘id’ => 2, ’name’ => ‘Joy’], [‘id’ => 1, ’name’ => ‘Raja’]] ...

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。示例 1:输入: [3,0,1]输出: 2示例 2:输入: [9,6,4,2,3,5,7,0,1]输出: 8下面我用两种方法，一块了解一下。求合法 // 开始之前我先说一下我的思路 //0-n个有序数字累加和，数学里边是有公式的，我们重温一下推导过程。 // 0, 1 n为1 个数为2， 累加和为1 // 0, 1, 2 n为2 个数为3，累加和为3 // 0, 1, 2, 3 n为3 个数为4，累加和为6 // 0, 1, 2, 3 ,4 n为4 个数为5， 累加和为10 // 思考一下，n已知所以我们从n上找规律 //以上我们推出 (n*个数)/2 = 累加和,是不是这个理？ // n知道 累加和知道，少那个我们不就知道了吗？ // 完整的n序列和-缺失数字的累加和=缺失数字 // 翻译成代码 var arr = [0, 1, 3] function findNum(nums) { let len = nums.length let n = len * (len + 1) / 2 let n1 = nums.reduce((num, item) => { return num + item }, 0) console.log(n, n1) return n - n1 }; console.log(findNum(arr))//2索引查找法//先解析思路,0-n序列，数组的索引和0-n序列正好能一一对应，不过因为有可能是乱序，所以不能直接挨个匹配索引对比，我们需要换个思路。//因为是序列，虽然乱序，只是和遍历n的索引值缺一个，这就简单了，我们通过遍历n来查找对应的剩余数组，找不到的就是我们要找的缺失数字，怎么找对应数字呢？你猜对了我们用indexOf() function findNum1(nums) { let len = nums.length + 1 for (let i = 0; i < len; i++) { if (nums.indexOf(i) === -1) { return i } } }; findNum1(arr)完美，只不过没有第一种的效率高！毕竟每一次indexOf也是一次遍历过程。 ...

属性 lengthlength 属性可获得数组的长度，即数组中值的个数。数组的长度是比数组最大索引值多一的数。let arr = [1, 2, 3, 4]arr.length // 4;如果给 length 属性赋值，指定的数组长度小于原数组长度，会缩短数组。let arr = [1, 2, 3, 4]arr.length = 3;arr // [1, 2, 3]length 设为 0，可以清空数组。let arr = [1, 2, 3, 4]arr.length = 0;arr // []方法静态方法1. Array.isArray()Array.isArray() 方法返回一个布尔值，表示参数是否为数组。它可以弥补 typeof 运算符的不足。let arr = [1, 2, 3];typeof arr // “object"Array.isArray(arr) // true2. Array.from()Array.from() 方法用于将两类对象转为真正的数组：类数组对象和可遍历（iterable）的对象（包括 ES6 新增的数据结构 Set 和 Map）。返回值是新数组。let arrayLike = { ‘0’: ‘a’, ‘1’: ‘b’, ‘2’: ‘c’, length: 3 };// ES5的写法var arr1 = [].slice.call(arrayLike); // [‘a’, ‘b’, ‘c’]// ES6的写法let arr2 = Array.from(arrayLike); // [‘a’, ‘b’, ‘c’]只要是部署了 Iterator 接口的数据结构，Array.from 都能将其转为数组。Array.from(‘hello’) // [‘h’, ’e’, ’l’, ’l’, ‘o’]let namesSet = new Set([‘a’, ‘b’])Array.from(namesSet) // [‘a’, ‘b’]任何有 length 属性的对象，即类数组对象，都可以通过 Array.from() 方法转为数组。Array.from({ length: 3 }); // [ undefined, undefined, undefined ]Array.from() 还可以接受第二个参数，作用类似于数组的 map 方法，用来对每个元素进行处理，将处理后的值放入返回的数组。Array.from(arrayLike, x => x * x);// 等同于Array.from(arrayLike).map(x => x * x);Array.from([1, 2, 3], (x) => x * x) // [1, 4, 9]Array.from() 的第三个参数，用来绑定 this。应用取出一组 DOM 节点的文本内容。let spans = document.querySelectorAll(‘span.name’);// map()let names1 = Array.prototype.map.call(spans, s => s.textContent);// Array.from()let names2 = Array.from(spans, s => s.textContent)将数组中布尔值为 false 的成员转为 0。Array.from([1, , 2, , 3], (n) => n || 0) // [1, 0, 2, 0, 3]返回各种数据的类型。function typesOf () { return Array.from(arguments, value => typeof value)}typesOf(null, [], NaN) // [‘object’, ‘object’, ’number’]将字符串转为数组，然后返回字符串的长度。因为它能正确处理各种 Unicode 字符，可以避免 JS 将大于 \uFFFF 的 Unicode 字符，算作两个字符的 bug。function countSymbols(string) { return Array.from(string).length;}3. Array.of()Array.of() 方法用于将一组值，转换为数组。Array.of(3, 11, 8) // [3,11,8]Array.of(3) // [3]Array.of(3).length // 1Array.of() 总是返回参数值组成的数组。如果没有参数，就返回一个空数组。Array.of() // []Array.of(undefined) // [undefined]Array.of(1) // [1]Array.of() 方法可以用下面的代码模拟实现。function ArrayOf(){ return [].slice.call(arguments);}实例方法1. valueOf()，toString()valueOf() 方法是一个所有对象都拥有的方法，表示对该对象求值，不同对象的valueOf() 方法不尽一致。数组的 valueOf 方法是 Array 构造函数的原型上的方法，覆盖了 Object 的 valueOf() 方法，返回数组本身。let arr = [1, 2, 3];arr.valueOf() // [1, 2, 3]toString() 方法也是对象的通用方法。数组的 toString 方法是 Array 构造函数的原型上的方法，覆盖了 Object 的 toString() 方法，返回数组的字符串形式。相当于调用 join() 方法，将数组转换为字符串，用逗号连接。let arr = [1, 2, 3];arr.toString() // “1,2,3"let arr = [1, 2, 3, [4, 5, 6]];arr.toString() // “1,2,3,4,5,6"2. push()，pop()push() 方法用于在数组的末端添加一个或多个元素，并返回添加新元素后的数组长度。该方法会直接改变原数组。let arr = [];arr.push(1) // 1arr.push(‘a’) // 2arr.push(true, {}) // 4arr // [1, ‘a’, true, {}]pop() 方法用于删除数组的最后一个元素，一次只能删一项。并返回被删除的该元素。该方法会直接改变原数组。let arr = [‘a’, ‘b’, ‘c’];arr.pop() // ‘c’arr // [‘a’, ‘b’]对空数组使用 pop() 方法，不会报错，而是返回 undefined。[].pop() // undefinedpush() 和 pop() 结合使用，就构成了“后进先出”的栈结构（stack）。let arr = [];arr.push(1, 2);arr.push(3);arr.pop(); // 3 是最后进入数组的，但是最早离开数组。arr // [1, 2]3. shift()，unshift()shift() 方法用于删除数组的第一个元素，一次只能删一项。并返回被删除的该元素。该方法会直接改变原数组。let arr = [‘a’, ‘b’, ‘c’];arr.shift() // ‘a’arr // [‘b’, ‘c’]push() 和 shift() 结合使用，就构成了“先进先出”的队列结构（queue）。let arr = [];arr.push(1, 2);arr.push(3);arr.shift(); // 1 是最先进入数组的，也最早离开数组。arr // [2, 3]unshift() 方法用于在数组的第一个位置添加一个或多个元素，并返回添加新元素后的数组长度。该方法会直接改变原数组。let arr = [‘a’, ‘b’, ‘c’];arr.unshift(‘x’); // 4arr.unshift(‘y’, ‘z’) // 6arr // [“y”, “z”, “x”, “a”, “b”, “c”]4. join()join() 方法以指定参数作为分隔符，将所有数组成员连接为一个字符串返回。如果不提供参数，默认用逗号分隔。该方法不改变原数组。let arr = [1, 2, 3, 4];arr.join(’ ‘) // ‘1 2 3 4’arr.join(’ | ‘) // “1 | 2 | 3 | 4"arr.join(’’) // ‘1234’arr.join() // “1,2,3,4"如果数组成员是 undefined 或 null 或 空位 ，会被转成空字符串。[undefined, null].join(’#’) // ‘#’[‘a’,, ‘b’].join(’-’) // ‘a–b’通过 call 方法，这个方法也可以用于字符串或类数组对象。Array.prototype.join.call(‘hello’, ‘-’) // “h-e-l-l-o"let obj = { 0: ‘a’, 1: ‘b’, length: 2 };Array.prototype.join.call(obj, ‘-’) // ‘a-b'5. concat()concat() 方法用于多个数组的合并。它将新数组的成员，添加到原数组成员的后面，然后返回一个新数组。参数设置非常灵活，可以是数组变量，也可以是字符串或数组字面量。该方法不改变原数组。[‘hello’].concat([‘world’], [’!’]) // [“hello”, “world”, “!”][].concat({a: 1}, {b: 2}) // [{ a: 1 }, { b: 2 }][1, 2, 3].concat(4, 5, 6) // [1, 2, 3, 4, 5, 6]let arr = [2,3];[1].concat(arr) // [1, 2, 3]concat() 方法是“浅拷贝”，拷贝的是对象的引用。let obj = { a: 1 };let newArray = [].concat(obj);newArray[0].a // 1obj.a = 2 // 2newArray[0].a // 26. reverse()reverse() 方法用于颠倒排列数组元素，返回改变后的数组。该方法会直接改变原数组。let arr = [‘a’, ‘b’, ‘c’];arr.reverse() // [“c”, “b”, “a”]arr // [“c”, “b”, “a”]7. slice()slice(start, end) 方法用于提取目标数组中选中的部分作为一个新的数组返回。该方法不改变原数组。参数a. slice(start, end)，从下标 start 开始截取到下标 end 的元素，包含 start 不包含 end。let arr = [‘a’, ‘b’, ‘c’];arr.slice(1, 2) // [“b”]arr.slice(2, 6) // [“c”]b. slice(start)，只有 start 一个参数表示从包含 start 的下标开始截取后面所有的元素。let arr = [‘a’, ‘b’, ‘c’];arr.slice(1) // [“b”, “c”]c. slice()，没有参数，则相当于从下标 0 开始截取后面所有的元素，实际上等于返回一个原数组的拷贝。let arr = [‘a’, ‘b’, ‘c’];arr.slice(0) // [“a”, “b”, “c”]arr.slice() // [“a”, “b”, “c”]d. slice(-start, -end)，参数可以用负数。表示倒数计算的位置。-1 表示倒数计算的第一个位置，依次向前类推。let arr = [‘a’, ‘b’, ‘c’];arr.slice(-2) // [“b”, “c”]arr.slice(-2, -1) // [“b”]e. 如果第一个参数大于等于数组长度，或者第二个参数小于第一个参数，则返回空数组。let arr = [‘a’, ‘b’, ‘c’];arr.slice(4) // []arr.slice(2, 1) // []slice() 方法的一个重要应用，是通过 call 方法，将类数组对象转为真正的数组。Array.prototype.slice.call({ 0: ‘a’, 1: ‘b’, length: 2 }) // [‘a’, ‘b’]Array.prototype.slice.call(document.querySelectorAll(“div”));Array.prototype.slice.call(arguments);8. splice()splice() 方法是一个多功能方法，根据参数的不同可以插入、删除、替换元素，返回值是被删除的元素组成的数组。该方法会直接改变原数组。arr.splice(start, count, addElement1, addElement2, …);参数a. arr.splice(start) 1个参数是拆分，等同于将原数组在指定位置拆分成两个数组。删除下标之后的全部值。包含 start 。let arr = [‘a’, ‘b’, ‘c’, ’d’, ’e’, ‘f’];arr.splice(3) // [’d’, ’e’, ‘f’]arr // [‘a’, ‘b’, ‘c’]b. arr.splice(start, count) 2个参数是删除，第二个参数是删除的个数，相当于从 start 开始，删除第二个参数指定的元素个数。let arr = [‘a’, ‘b’, ‘c’, ’d’, ’e’, ‘f’];arr.splice(4, 2) // [“e”, “f”] 下标 4 开始删除 2 项arr // [“a”, “b”, “c”, “d”]c. arr.splice(start, count, …) 更多参数是替换，表示从 start 开始，删除 count 项，然后将后面的参数作为新元素插入原数组中，返回值是被删除的元素。let arr = [‘a’, ‘b’, ‘c’, ’d’, ’e’, ‘f’];arr.splice(4, 2, 1, 2) // [“e”, “f”]arr // [“a”, “b”, “c”, “d”, 1, 2]d. arr.splice(start, 0, …) 第二个参数为0时，表示插入，从 start 开始，删除 0 项，并在 start 之前添加新元素。返回空数组。let arr = [‘a’, ‘b’, ‘c’, ’d’];arr.splice(2, 0, 1, 2) // []arr // [“a”, “b”, 1, 2, “c”, “d”]e. arr.splice(-start, …) 起始位置 start 如果是负数，就表示从倒数位置开始进行相关操作。let arr = [‘a’, ‘b’, ‘c’, ’d’];arr.splice(-2, 2) // [“c”, “d”]9. sort()sort() 方法对数组成员进行排序，默认按照字符顺序排序，会将数字隐式转换为字符串排序。直接返回改变后的原数组。该方法会直接改变原数组。let arr = [’d’, ‘c’, ‘b’, ‘a’];arr.sort() // [“a”, “b”, “c”, “d”]arr // [“a”, “b”, “c”, “d”]会将数字隐式转换为字符串排序。let arr=[2,3,45,12,78,67,155]arr.sort() // [12, 155, 2, 3, 45, 67, 78]自定义排序，可以传入一个函数作为参数。let arr=[2,3,45,12,78,67,155]arr.sort(function(a,b){ return a-b }) // [2, 3, 12, 45, 67, 78, 155]sort 的参数函数本身接受两个参数 a 和 b，表示进行比较的两个数组成员。如果该函数的返回值 >0，那么 b 排在 a 的前面；=0，位置不变；<0， a 排到 b 的前面。[{ name: “张三”, age: 30 }, { name: “李四”, age: 24 }, { name: “王五”, age: 28 }].sort(function (o1, o2) { return o1.age - o2.age;})// [// { name: “李四”, age: 24 },// { name: “王五”, age: 28 },// { name: “张三”, age: 30 }// ]10. map()map() 方法将数组的所有成员依次传入参数函数，然后把每一次的执行结果组成一个新数组返回。该方法不改变原数组。let numbers = [1, 2, 3];numbers.map(function (n) { return n + 1;}); // [2, 3, 4]numbers // [1, 2, 3]map() 方法接受一个函数作为参数。该函数调用时，map方法向它传入三个参数：第一个为当前进入函数的数组元素，第二个为当前元素的下标，第三个为原始数组。只有第一个是必须的。[1, 2, 3].map(function(elem, index, arr) { return elem * index;}); // [0, 2, 6]如果数组有空位，map() 方法的回调函数在这个位置不会执行，会跳过数组的空位。但不会跳过 undefined 和 null。let f = function (n) { return ‘a’ };[1, undefined, 2].map(f) // [“a”, “a”, “a”][1, null, 2].map(f) // [“a”, “a”, “a”][1, , 2].map(f) // [“a”, , “a”]map() 方法还可以接受第二个参数，用来绑定回调函数内部的 this 变量let arr = [‘a’, ‘b’, ‘c’];[1, 2].map(function (e) { return this[e];}, arr) // [‘b’, ‘c’]11. forEach()forEach() 方法与 map() 方法很相似，也是对数组的所有成员依次执行参数函数。但是，forEach() 方法不返回值，只用来操作数据。这就是说，如果数组遍历的目的是为了得到返回值，那么使用 map() 方法，否则使用 forEach() 方法。forEach() 的用法与 map() 方法一致，参数是一个函数，该函数同样接受三个参数：当前元素、当前下标、整个数组。同样也会跳过数组的空位。但不会跳过 undefined 和 null。var log = function (n) { console.log(n + 1); };[1, undefined, 2].forEach(log) // 2 // NaN // 3[1, null, 2].forEach(log) // 2 // 1 // 3[1, , 2].forEach(log) // 2 // 3forEach() 方法也可以接受第二个参数，绑定参数函数的 this 变量。let out = [];[1, 2, 3].forEach(function(elem) { this.push(elem * elem);}, out);out // [1, 4, 9]注意，forEach() 方法无法中断执行，总是会将所有成员遍历完。如果希望符合某种条件时，就中断遍历，要使用 for 循环。let arr = [1, 2, 3];for (let i = 0; i < arr.length; i++) { if (arr[i] === 2) break; console.log(arr[i]);}// 112. filter()filter() 方法用于过滤数组成员，满足条件的成员组成一个新数组返回。它的参数是一个函数，所有数组成员依次执行该函数，返回结果为 true 的成员组成一个新数组返回。该方法不改变原数组。[1, 2, 3, 4, 5].filter(function (elem) { return (elem > 3);}) // [4, 5]let arr = [0, 1, ‘a’, false];arr.filter(Boolean) // [1, “a”]filter() 方法的参数函数可以接受三个参数：当前元素、当前下标、整个数组。[1, 2, 3, 4, 5].filter(function (elem, index, arr) { return index % 2 === 0;}); // [1, 3, 5]filter() 方法还可以接受第二个参数，用来绑定参数函数内部的 this 变量。let obj = { MAX: 3 };let myFilter = function (item) { if (item > this.MAX) return true;};let arr = [2, 8, 3, 4, 1, 3, 2, 9];arr.filter(myFilter, obj) // [8, 4, 9]13. some()，every()这两个方法类似“断言”（assert），返回一个布尔值，表示判断数组成员是否符合某种条件。它们接受一个函数作为参数，所有数组成员依次执行该函数。该函数接受三个参数：当前元素、当前下标和整个数组。然后返回一个布尔值。some() 方法是只要一个成员的返回值是 true，则整个 some() 方法的返回值就是 true，否则返回 false。let arr = [1, 2, 3, 4, 5];arr.some(function (elem, index, arr) { return elem >= 3;}); // trueevery() 方法是所有成员的返回值都是 true，整个every() 方法才返回 true，否则返回 false。let arr = [1, 2, 3, 4, 5];arr.every(function (elem, index, arr) { return elem >= 3;}); // false注意，对于空数组，some() 方法返回 false，every() 方法返回 true，回调函数都不会执行。function isEven(x) { return x % 2 === 0 }[].some(isEven) // false[].every(isEven) // truesome() 和 every() 方法还可以接受第二个参数，用来绑定参数函数内部的 this 变量。14. reduce()，reduceRight()reduce() 方法和 reduceRight() 方法依次处理数组的每个成员，最终累计为一个值。它们的差别是，reduce 是从左到右处理（从第一个元素到最后一个元素），reduceRight 则是从右到左（从最后一个元素到第一个元素），其他完全一样。[1, 2, 3, 4, 5].reduce(function (a, b) { console.log(a, b); return a + b;}) // 15// 1 2// 3 3// 6 4// 10 5reduce() 方法和 reduceRight() 方法的第一个参数都是一个函数。该函数接受以下四个参数。前两个是必须的，后两个是可选的。累积变量，依次为上一轮的返回值，初始值默认为数组的第一个元素，可通过参数传入指定的初始变量。当前变量，默认为数组的第二个元素，当累积变量有指定初始值时，当前变量为第一个元素。当前变量的下标，默认为 1，当累积变量有指定初始值时，下标为 0。原数组reduce() 方法和 reduceRight() 方法的第二个参数是对累积变量指定初值。[1, 2, 3, 4, 5].reduce(function (a, b) { return a + b;}, 10); // 25指定累积变量相当于设定了默认值，对于处理空数组尤其有用。function add(prev, cur) { return prev + cur; }[].reduce(add) // 报错[].reduce(add, 1) // 1 永远返回初始值，不会执行函数reduceRight() 是从右到左依次执行函数。 function subtract(prev, cur) { return prev - cur; } [3, 2, 1].reduce(subtract) // 0 [3, 2, 1].reduceRight(subtract) // -4应用 由于这两个方法会遍历数组，所以实际上还可以用来做一些遍历相关的操作。找出字符长度最长的数组成员。function findLongest(entries) { return entries.reduce(function (longest, entry) { return entry.length > longest.length ? entry : longest; }, ‘’);}findLongest([‘aaa’, ‘bb’, ‘c’]) // “aaa"将二维数组转化为一维[[0, 1], [2, 3], [4, 5]].reduce(function(a, b) { return a.concat(b);},[]) // [0, 1, 2, 3, 4, 5]数组去重let arr = [1,2,1,2,3,5,4,5,3,4,4,4,4];let result = arr.sort().reduce((init, current)=>{ if(init.length===0 || init[init.length-1]!==current){ init.push(current); } return init;}, []) //[1,2,3,4,5]按属性对object分类let people = [ { name: ‘Alice’, age: 21 }, { name: ‘Max’, age: 20 }, { name: ‘Jane’, age: 20 }];function groupBy(objectArray, property) { return objectArray.reduce(function (acc, obj) { let key = obj[property]; if (!acc[key]) { acc[key] = []; } acc[key].push(obj); return acc; }, {});}groupBy(people, ‘age’);// { // 20: [// { name: ‘Max’, age: 20 }, // { name: ‘Jane’, age: 20 }// ], // 21: [{ name: ‘Alice’, age: 21 }] // }参考链接：Array.prototype.reduce()15. indexOf()，lastIndexOf()indexOf() 方法返回参数在数组中第一次出现的位置，如果没有出现则返回-1。let arr = [‘a’, ‘b’, ‘c’];arr.indexOf(‘b’) // 1arr.indexOf(‘y’) // -1indexOf() 方法还可以接受第二个参数，表示搜索的开始位置。[‘a’, ‘b’, ‘c’].indexOf(‘a’, 1) // -1lastIndexOf() 方法返回参数在数组中最后一次出现的位置，如果没有出现则返回-1。let arr = [2, 5, 9, 2];arr.lastIndexOf(2) // 3arr.lastIndexOf(7) // -1注意，这两个方法不能用来搜索 NaN 的位置，即它们无法确定数组成员是否包含 NaN。这是因为这两个方法内部，使用严格相等运算符（===）进行比较，而 NaN 是唯一一个不等于自身的值。[NaN].indexOf(NaN) // -1[NaN].lastIndexOf(NaN) // -116. copyWithin()copyWithin() 方法，在当前数组内部，将指定位置的成员复制到其他位置（会覆盖原有成员），然后返回当前数组。包含 start 不包含 end。该方法会直接改变原数组。Array.prototype.copyWithin(target, start, end)接受三个参数：target（必需）：从该位置开始替换数据。如果为负值，表示倒数。start（可选）：从该位置开始读取数据，默认为 0。如果为负值，表示倒数。end（可选）：到该位置前停止读取数据，默认等于数组长度。如果为负值，表示倒数。[1, 2, 3, 4, 5].copyWithin(0, 3) // [4, 5, 3, 4, 5]上面代码表示将从下标 3 到数组结束的元素（4 和 5），复制到从下标 0 开始的位置，结果覆盖了原来的 1 和 2。[1, 2, 3, 4, 5].copyWithin(0, 3, 4) // [4, 2, 3, 4, 5][1, 2, 3, 4, 5].copyWithin(0, -2, -1) // [4, 2, 3, 4, 5][].copyWithin.call({length: 5, 3: 1}, 0, 3) // {0: 1, 3: 1, length: 5}17. find()，findIndex()find() 方法用于找出第一个符合条件的数组元素。它的参数是一个回调函数，所有数组元素依次执行该回调函数，直到找出第一个返回值为 true 的元素，然后返回该元素。如果没有符合条件的元素，则返回 undefined。[1, 4, -5, 10].find((n) => n < 0) // -5find() 方法的回调函数可以接受三个参数，依次为当前元素、当前下标和原数组。[1, 5, 10, 15].find(function(value, index, arr) { return value > 9;}) // 10findIndex() 方法的用法与 find() 方法非常类似，返回第一个符合条件的数组元素的位置，如果所有元素都不符合条件，则返回 -1。[1, 5, 10, 15].findIndex(function(value, index, arr) { return value > 9;}) // 2这两个方法都可以接受第二个参数，用来绑定回调函数的 this 对象。function f(v){ return v > this.age; }let person = {name: ‘John’, age: 20};[10, 12, 26, 15].find(f, person); // 26另外，这两个方法都可以可以借助 Object.is() 方法识别数组的 NaN，弥补了 indexOf() 方法的不足。[NaN].indexOf(NaN) // -1[NaN].findIndex(y => Object.is(NaN, y)) // 018. fill()fill() 方法使用给定值，填充一个数组。[‘a’, ‘b’, ‘c’].fill(7) // [7, 7, 7]new Array(3).fill(7) // [7, 7, 7]fill() 方法还可以接受第二个和第三个参数，用于指定填充的起始位置和结束位置。[‘a’, ‘b’, ‘c’].fill(7, 1, 2) // [‘a’, 7, ‘c’]注意，如果填充的类型为对象，那么被赋值的是同一个内存地址的对象，而不是深拷贝对象。let arr = new Array(3).fill({name: “Mike”});arr[0].name = “Ben”;arr // [{name: “Ben”}, {name: “Ben”}, {name: “Ben”}]let arr = new Array(3).fill([]);arr[0].push(5);arr // [[5], [5], [5]]19. includes()includes() 方法返回一个布尔值，表示某个数组是否包含给定的值，与字符串的includes() 方法类似。[1, 2, 3].includes(2) // true[1, 2, 3].includes(4) // false[1, 2, NaN].includes(NaN) // true该方法的第二个参数表示搜索的起始位置，默认为0。如果第二个参数为负数，则表示倒数的位置，如果这时它大于数组长度（比如第二个参数为-4，但数组长度为3），则会重置为从0开始。[1, 2, 3].includes(3, 3); // false[1, 2, 3].includes(3, -1); // true没有该方法之前，我们通常使用数组的 indexOf() 方法，检查是否包含某个值。if (arr.indexOf(el) !== -1) { // …}indexOf() 方法内部使用严格相等运算符（===）进行判断，这会导致对 NaN 的误判。includes() 使用的是不一样的判断算法，就没有这个问题。[NaN].indexOf(NaN) // -1[NaN].includes(NaN) // true20. flat()，flatMap()flat() 用于将多维数组变成一维数组。返回一个新数组。该方法不改变原数组。[1, 2, [3, 4]].flat() // [1, 2, 3, 4]flat() 默认只会“拉平”一层，如果想要“拉平”多层的嵌套数组，可以将 flat() 方法的参数写成一个整数，表示想要拉平的层数，默认为 1。[1, 2, [3, [4, 5]]].flat() // [1, 2, 3, [4, 5]][1, 2, [3, [4, 5]]].flat(2) // [1, 2, 3, 4, 5]如果不管有多少层嵌套，都要转成一维数组，可以用 Infinity 关键字作为参数。[1, [2, [3]]].flat(Infinity) // [1, 2, 3]如果原数组有空位，flat() 方法会跳过空位。[1, 2, , 4, 5].flat() // [1, 2, 4, 5]flatMap() 方法对原数组的每个元素执行一个函数（相当于执行Array.prototype.map()），然后对返回值组成的数组执行 flat() 方法。返回新数组。该方法不改变原数组。[2, 3, 4].flatMap((x) => [x, x * 2]) // [2, 4, 3, 6, 4, 8]// 相当于 [[2, 4], [3, 6], [4, 8]].flat()flatMap() 只能展开一层数组。[1, 2, 3, 4].flatMap(x => [[x * 2]]) // [[2], [4], [6], [8]]// 相当于 [[[2]], [[4]], [[6]], [[8]]].flat()flatMap() 方法的参数是一个遍历函数，该函数可以接受三个参数，分别是当前数组元素、当前数组元素的下标（从零开始）、原数组。flatMap() 方法还可以有第二个参数，用来绑定遍历函数里面的 this。arr.flatMap(function callback(currentValue[, index[, array]]) { // …}[, thisArg])链式使用上面这些数组方法之中，有不少返回的还是数组，所以可以链式使用。var users = [ {name: ’tom’, email: ’tom@example.com’}, {name: ‘peter’, email: ‘peter@example.com’}];users.map(function (user) { return user.email;}).filter(function (email) { return /^t/.test(email);}).forEach(function (email) { console.log(email);});// “tom@example.com"参考链接：Array对象数组的扩展 ...

今天聊一下clone这个前端面试高频问题，由此引出typeof、instanceof、Object.prototype.toString这些javascript Api。下面我们先详细的聊一下，完了解决下面试官的问题。typeoftypeof能获取一个变量或表达式的类型。原始类型BooleanNullUndefinedStringSymbolNumberSymbol和 引用类型 Object，Function下面看一些栗子 //基础类型也可以说非引用类型 let str = ‘hello word!’ console.log(typeof str) //string let num = 12 console.log(typeof num) //number let udf = undefined console.log(typeof udf) //undefined let bl = true console.log(typeof bl) //boolean let nl = null console.log(nl) //null let sl = Symbol() console.log(typeof sl) //symbol //复合类型也可以说是引用类型， let obj = { a: 1 } console.log(typeof obj) //object let arr = [1, 2, 3] console.log(typeof arr) //object //函数也属于引用类型，不过typeof却能准确的返回类型 function fn() {} console.log(typeof fn) //function从以上的执行结果可以看出，typeof不能够准确分返回所有类型instenceof我们从instenceof的实现来了解下instenceof是干什么的 // 模拟instenceof实现 // 1、instenceof接收两个参数 // 2、返回true或false function myInstenceof(X, Y) { let L = X.proto let R = Y.prototype if (L !== R) { return false } return true } // test function Fn() { } let newFn = new Fn() console.log(newFn) console.log(new Fn()) console.log(myInstenceof(newFn, new Fn())) //true console.log(myInstenceof([], new Array())) //true console.log(myInstenceof([], new Object())) //true以上demo我们就能看出，instenceof也不够靠谱，模拟实现就是判断X的原型知否在Y的原型链上。数组之所以instenceof Object为true是因为 [].prototype->new Array->new Object->null上边说了typeof和instenceof其实就是想说这两个对于深度clone的实现来说不够严谨要不就是多层判断。Object.prototype.toString.call()接下里我们说个靠谱的 Object.prototype.toString.call(’’); // [object String] Object.prototype.toString.call(1); // [object Number] Object.prototype.toString.call(true); // [object Boolean] Object.prototype.toString.call(undefined); // [object Undefined] Object.prototype.toString.call(null); // [object Null] Object.prototype.toString.call(new Function()); // [object Function] Object.prototype.toString.call(new Date()); // [object Date] Object.prototype.toString.call([]); // [object Array] Object.prototype.toString.call(new RegExp()); // [object RegExp] Object.prototype.toString.call(new Error()); // [object Error] Object.prototype.toString.call(document); // [object HTMLDocument] Object.prototype.toString.call(window); //[object Window]靠谱！接下来我们就用Object.prototype.toString.call()来解答一下面试题 function clone(obj, o) { //Object.prototype.toString.call(obj)返回类似[Object Array] 利用slice来截取我们需要的字符串 let type = Object.prototype.toString.call(obj).slice(8, -1) // 如果是Object if (type === ‘Object’) { o = {} for (let k in obj) { o[k] = clone(obj[k]); } // 如果是对象 } else if (type === ‘Array’) { o = [] for (let i = 0; i < obj.length; i++) { o.push(clone(obj[i])); } } else { // 非引用类型 o = obj } return o } let obj1 = { a: [1, 2, 3, 4, 5, 6], b: { c: 2 }, d: 1, f: function() { return 1 } } let obj2 = clone(obj1) obj2.f = function() { return 2 } obj2.a = 1 console.log(obj1) console.log(obj2)测试打印结果，obj2的改变不会影响到obj1。欢迎吐槽！ ...

一、前言本次分享我们来共同探讨JUC包中一些有意思的类，包含AtomicLong & LongAdder,ThreadLocalRandom原理。二、AtomicLong & LongAdder2.1 AtomicLong 类AtomicLong是JUC包提供的原子性操作类，其内部通过CAS保证了对计数的原子性更新操作。大家可以翻看源码发现内部是通过UnSafe(rt.jar)这个类的CAs操作来保证对内部的计数器变量 long value进行原子性更新的，比如JDK8中： public final long incrementAndGet() { return unsafe.getAndAddLong(this, valueOffset, 1L) + 1L; }其中unsafe.getAndAddLong的代码如下： public final long getAndAddLong(Object paramObject, long paramLong1, long paramLong2) { long l; do { l = getLongVolatile(paramObject, paramLong1);//(1) } while (!compareAndSwapLong(paramObject, paramLong1, l, l + paramLong2));//(2) return l; }可知最终调用的是native 方法compareAndSwapLong原子性操作。当多个线程调用同一个AtomicLong实例的incrementAndGet方法后，多个线程都会执行到unsafe.getAndAddLong方法，然后多个线程都会执行到代码（1）处获取计数器的值，然后都会去执行代码（2），如果多个线程同时执行了代码（2），由于CAS具有原子性，所以只有一个线程会更新成功，然后返回true从而退出循环，整个更新操作就OK了。其他线程则CAS失败返回false，则循环一次在次从（1）处获取当前计数器的值，然后在尝试执行（2），这叫做CAS的自旋操作，本质是使用Cpu 资源换取使用锁带来的上下文切换等开销。2.2 LongAdder类AtomicLong类为开发人员使用线程安全的计数器提供了方便，但是AtomicLong在高并发下存在一些问题，如上所述，当大量线程调用同一个AtomicLong的实例的方法时候，同时只有一个线程会CAS计数器的值成功，失败的线程则会原地占用cpu进行自旋转重试，这回造成大量线程白白浪费cpu原地自旋转。在JDK8中新增了一个LongAdder类，其采用分而治之的策略来减少同一个变量的并发竞争度,LongAdder的核心思想是把一个原子变量分解为多个变量，让同样多的线程去竞争多个资源，这样竞争每个资源的线程数就被分担了下来，下面通过图形来理解下两者设计的不同之处：如上图AtomicLong是多个线程同时竞争同一个原子变量。如上图LongAdder内部维护多个Cell变量，在同等并发量的情况下，争夺单个变量更新操作的线程量会减少，这是变相的减少了争夺共享资源的并发量。下面我们首先看下Cell的结构： @sun.misc.Contended static final class Cell { volatile long value; Cell(long x) { value = x; } final boolean cas(long cmp, long val) { return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val); } // Unsafe 机制 private static final sun.misc.Unsafe UNSAFE; private static final long valueOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); Class<?> ak = Cell.class; valueOffset = UNSAFE.objectFieldOffset (ak.getDeclaredField(“value”)); } catch (Exception e) { throw new Error(e); } } }LongAdder维护了一个延迟初始化的原子性更新数组（默认情况下Cell数组是null）和一个基值变量base，由于Cells占用内存是相对比较大的，所以一开始并不创建，而是在需要时候在创建，也就是惰性 创建。当一开始判断cell数组是null并且并发线程较少时候所有的累加操作都是对base变量进行的，这时候就退化为了AtomicLong。cell数组的大小保持是2的N次方大小，初始化时候Cell数组的中Cell的元素个数为2，数组里面的变量实体是Cell类型。当多个线程在争夺同一个Cell原子变量时候如果失败并不是在当前cell变量上一直自旋CAS重试，而是会尝试在其它Cell的变量上进行CAS尝试，这个改变增加了当前线程重试时候CAS成功的可能性。最后获取LongAdder当前值的时候是把所有Cell变量的value值累加后在加上base返回的，如下代码： public long sum() { Cell[] as = cells; Cell a; long sum = base; if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; }如上代码可知首先把base的值赋值给sum变量，然后通过循环把每个cell元素的value值累加到sum变量上，最后返回sum.其实这是一种分而治之的策略，先把并发量分担到多个原子变量上，让多个线程并发的对不同的原子变量进行操作，然后获取计数时候在把所有原子变量的计数和累加。思考问题：何时初始化cell数组当前线程如何选择cell中的元素进行访问如果保证cell中元素更新的线程安全cell数组何时进行扩容，cell元素个数可以无限扩张?性能对比，这里有一个文章 http://blog.palominolabs.com/2014/02/10/java-8-performance-improvements-longadder-vs-atomiclong/三、 Random & ThreadLocalRandom3.1 Random类原理及其局限性在JDK7之前包括现在java.util.Random应该是使用比较广泛的随机数生成工具类,下面先通过简单的代码看看java.util.Random是如何使用的：public class RandomTest { public static void main(String[] args) { //(1)创建一个默认种子的随机数生成器 Random random = new Random(); //(2)输出10个在0-5（包含0，不包含5）之间的随机数 for (int i = 0; i < 10; ++i) { System.out.println(random.nextInt(5)); } }}代码（1）创建一个默认随机数生成器，使用默认的种子。代码（2）输出输出10个在0-5（包含0，不包含5）之间的随机数。 public int nextInt(int bound) { //(3)参数检查 if (bound <= 0) throw new IllegalArgumentException(BadBound); //(4)根据老的种子生成新的种子 int r = next(31); //(5)根据新的种子计算随机数 … return r; } 如上代码可知新的随机数的生成需要两个步骤首先需要根据老的种子计算生成新的种子。然后根据新的种子和bound变量通过一定的算法来计算新的随机数。下面看下next()代码： protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { //(6)获取当前原子变量种子的值 oldseed = seed.get(); //(7)根据当前种子值计算新的种子 nextseed = (oldseed * multiplier + addend) & mask; //(8)使用新种子替换老的种子 } while (!seed.compareAndSet(oldseed, nextseed)); //(9) return (int)(nextseed >>> (48 - bits)); }代码（6）使用原子变量的get方法获取当前原子变量种子的值代码（7）根据具体的算法使用当前种子值计算新的种子代码（8）使用CAS操作，使用新的种子去更新老的种子，多线程下可能多个线程都同时执行到了代码（6）那么可能多个线程都拿到的当前种子的值是同一个，然后执行步骤（7）计算的新种子也都是一样的，但是步骤（8）的CAS操作会保证只有一个线程可以更新老的种子为新的，失败的线程会通过循环从新获取更新后的种子作为当前种子去计算老的种子,这就保证了随机数的随机性。代码（9）则使用固定算法根据新的种子计算随机数，并返回。3.2 ThreadLocalRandomRandom类生成随机数原理以及不足：每个Random实例里面有一个原子性的种子变量用来记录当前的种子的值，当要生成新的随机数时候要根据当前种子计算新的种子并更新回原子变量。多线程下使用单个Random实例生成随机数时候，多个线程同时计算随机数计算新的种子时候多个线程会竞争同一个原子变量的更新操作，由于原子变量的更新是CAS操作，同时只有一个线程会成功，那么CAS操作失败的大量线程进行自旋重试，而大量线程的自旋重试是会降低并发性能和消耗CPU资源的，为了解决这个问题，ThreadLocalRandom类应运而生。public class RandomTest { public static void main(String[] args) { //(10)获取一个随机数生成器 ThreadLocalRandom random = ThreadLocalRandom.current(); //(11)输出10个在0-5（包含0，不包含5）之间的随机数 for (int i = 0; i < 10; ++i) { System.out.println(random.nextInt(5)); } }}如上代码（10）调用ThreadLocalRandom.current()来获取当前线程的随机数生成器。下面来分析下ThreadLocalRandom的实现原理。从名字看会让我们联想到ThreadLocal类。ThreadLocal通过让每一个线程拷贝一份变量，每个线程对变量进行操作时候实际是操作自己本地内存里面的拷贝，从而避免了对共享变量进行同步。实际上ThreadLocalRandom的实现也是这个原理。Random的缺点是多个线程会使用原子性种子变量，会导致对原子变量更新的竞争，这个原理可以通过下面图来表达：那么如果每个线程维护自己的一个种子变量，每个线程生成随机数时候根据自己本地内存中的老的种子计算新的种子，并使用新种子更新老的种子，然后根据新种子计算随机数，就不会存在竞争问题，这会大大提高并发性能，如下图ThreadLocalRandom原理可以使用下图表达：Thread类里面有几个变量： /** The current seed for a ThreadLocalRandom / @sun.misc.Contended(“tlr”) long threadLocalRandomSeed; /* Probe hash value; nonzero if threadLocalRandomSeed initialized */ @sun.misc.Contended(“tlr”) int threadLocalRandomProbe;思考问题：每个线程的初始种子怎么生成的如果保障多个线程产生的种子不一样四、总结本文是对拙作 java并发编程之美 一书中有关章节的提炼。本次分享首先讲解了AtomicLong的内部实现，以及存在的缺点，然后讲解了 LongAdder采用分而治之的策略通过使用多个原子变量减小单个原子变量竞争的并发度。然后简单介绍了Random，和其缺点，最后介绍了ThreadLocalRandom借用ThreadLocal的思想解决了多线程对同一个原子变量竞争锁带来的性能损耗。其实JUC包中还有其他一些经典的组件，比如fork-join框架等。本文作者：加多阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...

ProblemGiven an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.Find all the elements that appear twice in this array.Could you do it without extra space and in O(n) runtime?Example:Input:[4,3,2,7,8,2,3,1]Output:[2,3]Solutionclass Solution { public List<Integer> findDuplicates(int[] nums) { //use index to record visited: times -1 List<Integer> res = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { int index = nums[i] > 0 ? nums[i]-1 : -nums[i]-1; if (nums[index] < 0) res.add(index+1); nums[index] *= -1; } return res; }} ...

ProblemGiven an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.Find all the elements of [1, n] inclusive that do not appear in this array.Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.Example:Input:[4,3,2,7,8,2,3,1]Output:[5,6]Solutionclass Solution { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> res = new ArrayList<>(); if (nums == null || nums.length == 0) return res; for (int i = 0; i < nums.length; i++) { int index = nums[i] > 0 ? nums[i]-1 : -nums[i]-1; if (nums[index] < 0) continue; nums[index] *= -1; } for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) res.add(i+1); } return res; }} ...

ProblemGiven n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area = 10 unit.Solutionclass Solution { public int largestRectangleArea(int[] height) { if (height == null || height.length == 0) return 0; int n = height.length; int[] left = new int[n]; int[] right = new int[n]; right[n-1] = n; left[0] = -1; for (int i = 1; i < n; i++) { int index = i-1; while (index >= 0 && height[index] >= height[i]) index = left[index]; left[i] = index; } for (int i = n-2; i >= 0; i–) { int index = i+1; while (index < n && height[index] >= height[i]) index = right[index]; right[i] = index; } int max = 0; for (int i = 0; i < n; i++) max = Math.max(max, height[i]*(right[i]-left[i]-1)); return max; }} ...

array 和 slice 看似相似，却有着极大的不同，但他们之间还有着千次万缕的联系 slice 是引用类型、是 array 的引用，相当于动态数组，这些都是 slice 的特性，但是 slice 底层如何表现，内存中是如何分配的，特别是在程序中大量使用 slice 的情况下，怎样可以高效使用 slice？今天借助 Go 的 unsafe 包来探索 array 和 slice 的各种奥妙。数组slice 是在 array 的基础上实现的，需要先详细了解一下数组。 维基上如此介绍数组：在计算机科学中，数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储，利用元素的索引（index）可以计算出该元素对应的存储地址。 数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先请求空间。这使得数组有以下特性：请求空间以后大小固定，不能再改变（数据溢出问题）；在内存中有空间连续性的表现，中间不会存在其他程序需要调用的数据，为此数组的专用内存空间；在旧式编程语言中（如有中阶语言之称的C），程序不会对数组的操作做下界判断，也就有潜在的越界操作的风险（比如会把数据写在运行中程序需要调用的核心部分的内存上）。根据维基的介绍，了解到数组是存储在一段连续的内存中，每个元素的类型相同，即是每个元素的宽度相同，可以根据元素的宽度计算元素存储的位置。通过这段介绍总结一下数组有一下特性：分配在连续的内存地址上元素类型一致，元素存储宽度一致空间大小固定，不能修改可以通过索引计算出元素对应存储的位置（只需要知道数组内存的起始位置和数据元素宽度即可）会出现数据溢出的问题（下标越界）Go 中的数组如何实现的呢，恰恰就是这么实现的，实际上几乎所有计算机语言，数组的实现都是相似的，也拥有上面总结的特性。Go 语言的数组不同于 C 语言或者其他语言的数组，C 语言的数组变量是指向数组第一个元素的指针；而 Go 语言的数组是一个值，Go 语言中的数组是值类型，一个数组变量就表示着整个数组，意味着 Go 语言的数组在传递的时候，传递的是原数组的拷贝。在程序中数组的初始化有两种方法 arr := [10]int{} 或 var arr [10]int，但是不能使用 make 来创建，数组这节结束时再探讨一下这个问题。使用 unsafe来看一下在内存中都是如何存储的吧：package mainimport ( “fmt” “unsafe”)func main() { var arr = [3]int{1, 2, 3} fmt.Println(unsafe.Sizeof(arr)) size := unsafe.Sizeof(arr[0]) // 获取数组指定索引元素的值 fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&arr[0])) + 1size))) // 设置数组指定索引元素的值 (int)(unsafe.Pointer(uintptr(unsafe.Pointer(&arr[0])) + 1size)) = 10 fmt.Println(arr[1])}这段代码的输出如下 (Go Playground)：12210首先说 12 是 fmt.Println(unsafe.Sizeof(arr)) 输出的，unsafe.Sizeof 用来计算当前变量的值在内存中的大小，12 这个代表一个 int 有4个字节，3 * 4 就是 12。这是在32位平台上运行得出的结果， 如果在64位平台上运行数组的大小是 24。从这里可以看出 [3]int 在内存中由3个连续的 int 类型组成，且有 12 个字节那么长，这就说明了数组在内存中没有存储多余的数据，只存储元素本身。size := unsafe.Sizeof(arr[0]) 用来计算单个元素的宽度，int在32位平台上就是4个字节，uintptr(unsafe.Pointer(&arr[0])) 用来计算数组起始位置的指针，1size 用来获取索引为1的元素相对数组起始位置的偏移，unsafe.Pointer(uintptr(unsafe.Pointer(&arr[0])) + 1size)) 获取索引为1的元素指针，(int) 用来转换指针位置的数据类型， 因为 int 是4个字节，所以只会读取4个字节的数据，由元素类型限制数据宽度，来确定元素的结束位置，因此得到的结果是 2。上一个步骤获取元素的值，其中先获取了元素的指针，赋值的时候只需要对这个指针位置设置值就可以了， (int)(unsafe.Pointer(uintptr(unsafe.Pointer(&arr[0])) + 1size)) = 10 就是用来给指定下标元素赋值。package mainimport ( “fmt” “unsafe”)func main() { n:= 10 var arr = [n]int{} fmt.Println(arr)}如上代码，动态的给数组设定长度，会导致编译错误 non-constant array bound n， 由此推导数组的所有操作都是编译时完成的，会转成对应的指令，通过这个特性知道数组的长度是数组类型不可或缺的一部分，并且必须在编写程序时确定。可以通过 GOOS=linux GOARCH=amd64 go tool compile -S array.go 来获取对应的汇编代码，在 array.go 中做一些数组相关的操作，查看转换对应的指令。之前的疑问，为什么数组不能用 make 创建？ 上面分析了解到数组操作是在编译时转换成对应指令的，而 make 是在运行时处理（特殊状态下会做编译器优化，make可以被优化，下面 slice 分析时来讲）。slice因为数组是固定长度且是值传递，很不灵活，所以在 Go 程序中很少看到数组的影子。然而 slice 无处不在，slice 以数组为基础，提供强大的功能和遍历性。slice 的类型规范是[]T，slice T元素的类型。与数组类型不同，slice 类型没有指定的长度。 slice 申明的几种方法：s := []int{1, 2, 3} 简短的赋值语句var s []int var 申明make([]int, 3, 8) 或 make([]int, 3) make 内置方法创建s := ss[:5] 从切片或者数组创建 slice 有两个内置函数来获取其属性：len 获取 slice 的长度cap 获取 slice 的容量slice 的属性，这东西是什么，还需借助 unsafe 来探究一下。package mainimport ( “fmt” “unsafe”)func main() { s := make([]int, 10, 20) s[2] = 100 s[9] = 200 size := unsafe.Sizeof(0) fmt.Printf("%x\n", (uintptr)(unsafe.Pointer(&s))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size2))) fmt.Println(([20]int)(unsafe.Pointer((uintptr)(unsafe.Pointer(&s)))))}这段代码的输出如下 (Go Playground)：c00007ce901020[0 0 100 0 0 0 0 0 0 200 0 0 0 0 0 0 0 0 0 0]这段输出除了第一个，剩余三个好像都能看出点什么， 10 不是创建 slice 的长度吗，20 不就是指定的容量吗， 最后这个看起来有点像 slice 里面的数据，但是数量貌似有点多，从第三个元素和第十个元素来看，正好是给 slice 索引 2 和 10 指定的值，但是切片不是长度是 10 个吗，难道这个是容量，容量刚好是 20个。 第二和第三个输出很好弄明白，就是 slice 的长度和容量， 最后一个其实是 slice 引用底层数组的数据，因为创建容量为 20，所以底层数组的长度就是 20，从这里了解到切片是引用底层数组上的一段数据，底层数组的长度就是 slice 的容量，由于数组长度不可变的特性，当 slice 的长度达到容量大小之后就需要考虑扩容，不是说数组长度不能变吗，那 slice 怎么实现扩容呢， 其实就是在内存上分配一个更大的数组，把当前数组上的内容拷贝到新的数组上， slice 来引用新的数组，这样就实现扩容了。说了这么多，还是没有看出来 slice 是如何引用数组的，额…… 之前的程序还有一个输出没有搞懂是什么，难道这个就是底层数组的引用。package mainimport ( “fmt” “unsafe”)func main() { arr := [10]int{1, 2, 3} arr[7] = 100 arr[9] = 200 fmt.Println(arr) s1 := arr[:] s2 := arr[2:8] size := unsafe.Sizeof(0) fmt.Println("———-s1———") fmt.Printf("%x\n", (uintptr)(unsafe.Pointer(&s1))) fmt.Printf("%x\n", uintptr(unsafe.Pointer(&arr[0]))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size2))) fmt.Println(s1) fmt.Println(([10]int)(unsafe.Pointer((uintptr)(unsafe.Pointer(&s1))))) fmt.Println("———-s2———") fmt.Printf("%x\n", (uintptr)(unsafe.Pointer(&s2))) fmt.Printf("%x\n", uintptr(unsafe.Pointer(&arr[0]))+size2) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s2)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s2)) + size2))) fmt.Println(s2) fmt.Println(([8]int)(unsafe.Pointer((*uintptr)(unsafe.Pointer(&s2)))))}以上代码输出如下(Go Playground)：[1 2 3 0 0 0 0 100 0 200] ———-s1——— c00001c0a0 c00001c0a0 10 10 [1 2 3 0 0 0 0 100 0 200] [1 2 3 0 0 0 0 100 0 200] ———-s2——— c00001c0b0 c00001c0b0 6 8 [3 0 0 0 0 100][3 0 0 0 0 100 0 200]这段输出看起来有点小复杂，第一行输出就不用说了吧，这个是打印整个数组的数据。先分析一下 s1 变量的下面的输出吧，s1 := arr[:] 引用了整个数组，所以在第5、6行输出都是10，因为数组长度为10，所有 s1 的长度和容量都为10，那第3、4行输出是什么呢，他们怎么都一样呢，之前分析数组的时候 通过 uintptr(unsafe.Pointer(&arr[0])) 来获取数组起始位置的指针的，那么第4行打印的就是数组的指针，这么就了解了第三行输出的是上面了吧，就是数组起始位置的指针，所以 (uintptr)(unsafe.Pointer(&s1)) 获取的就是引用数组的指针，但是这个并不是数组起始位置的指针，而是 slice 引用数组元素的指针，为什么这么说呢？接着看 s2 变量下面的输出吧，s2 := arr[2:8] 引用数组第3~8的元素，那么 s2 的长度就是 6。 根据经验可以知道 s2 变量输出下面第3行就是 slice 的长度，但是为啥第4行是 8 呢，slice 应用数组的指定索引起始位置到数组结尾就是 slice 的容量， 所以 所以从第3个位置到末尾，就是8个容量。在看第1行和第2行的输出，之前分析数组的时候通过 uintptr(unsafe.Pointer(&arr[0]))+size2 来获取数组指定索引位置的指针，那么这段第2行就是数组索引为2的元素指针，(*uintptr)(unsafe.Pointer(&s2)) 是获取切片的指针，第1行和第2行输出一致，所以 slice 实际是引用数组元素位置的指针，并不是数组起始位置的指针。 总结：slice 是的起始位置是引用数组元素位置的指针。slice 的长度是引用数组元素起始位置到结束位置的长度。slice 的容量是引用数组元素起始位置到数组末尾的长度。经过上面一轮分析了解到 slice 有三个属性，引用数组元素位置指针、长度和容量。实际上 slice 的结构像下图一样：slice 增长slice 是如何增长的，用 unsafe 分析一下看看：package mainimport ( “fmt” “unsafe”)func main() { s := make([]int, 9, 10) // 引用底层的数组地址 fmt.Printf("%x\n", *(*uintptr)(unsafe.Pointer(&s))) s = append(s, 1) // 引用底层的数组地址 fmt.Printf("%x\n", *(*uintptr)(unsafe.Pointer(&s))) s = append(s, 1) // 引用底层的数组地址 fmt.Printf("%x\n", *(*uintptr)(unsafe.Pointer(&s)))}以上代码的输出(Go Playground):c000082e90 9 10 c000082e90 10 10 c00009a00011 20从结果上看前两次地址是一样的，初始化一个长度为9，容量为10的 slice，当第一次 append 的时候容量是足够的，所以底层引用数组地址未发生变化，此时 slice 的长度和容量都为10，之后再次 append 的时候发现底层数组的地址不一样了，因为 slice 的长度超过了容量，但是新的 slice 容量并不是11而是20，这要说 slice 的机制了，因为数组长度不可变，想扩容 slice就必须分配一个更大的数组，并把之前的数据拷贝到新数组，如果一次只增加1个长度，那就会那发生大量的内存分配和数据拷贝，这个成本是很大的，所以 slice 是有一个增长策略的。Go 标准库 runtime/slice.go 当中有详细的 slice 增长策略的逻辑：func growslice(et *_type, old slice, cap int) slice { ….. // 计算新的容量，核心算法用来决定slice容量增长 newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if old.len < 1024 { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } // 根据et.size调整新的容量 var overflow bool var lenmem, newlenmem, capmem uintptr switch { case et.size == 1: lenmem = uintptr(old.len) newlenmem = uintptr(cap) capmem = roundupsize(uintptr(newcap)) overflow = uintptr(newcap) > maxAlloc newcap = int(capmem) case et.size == sys.PtrSize: lenmem = uintptr(old.len) * sys.PtrSize newlenmem = uintptr(cap) * sys.PtrSize capmem = roundupsize(uintptr(newcap) * sys.PtrSize) overflow = uintptr(newcap) > maxAlloc/sys.PtrSize newcap = int(capmem / sys.PtrSize) case isPowerOfTwo(et.size): var shift uintptr if sys.PtrSize == 8 { // Mask shift for better code generation. shift = uintptr(sys.Ctz64(uint64(et.size))) & 63 } else { shift = uintptr(sys.Ctz32(uint32(et.size))) & 31 } lenmem = uintptr(old.len) << shift newlenmem = uintptr(cap) << shift capmem = roundupsize(uintptr(newcap) << shift) overflow = uintptr(newcap) > (maxAlloc >> shift) newcap = int(capmem >> shift) default: lenmem = uintptr(old.len) * et.size newlenmem = uintptr(cap) * et.size capmem = roundupsize(uintptr(newcap) * et.size) overflow = uintptr(newcap) > maxSliceCap(et.size) newcap = int(capmem / et.size) } …… var p unsafe.Pointer if et.kind&kindNoPointers != 0 { p = mallocgc(capmem, nil, false) // 分配新的内存 memmove(p, old.array, lenmem) // 拷贝数据 memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { p = mallocgc(capmem, et, true) // 分配新的内存 if !writeBarrier.enabled { memmove(p, old.array, lenmem) } else { for i := uintptr(0); i < lenmem; i += et.size { typedmemmove(et, add(p, i), add(old.array, i)) // 拷贝数据 } } } return slice{p, old.len, newcap} // 新slice引用新的数组，长度为旧数组的长度，容量为新数组的容量}基本呢就三个步骤，计算新的容量、分配新的数组、拷贝数据到新数组，社区很多人分享 slice 的增长方法，实际都不是很精确，因为大家只分析了计算 newcap 的那一段，也就是上面注释的第一部分，下面的 switch 根据 et.size 来调整 newcap 一段被直接忽略，社区的结论是：“如果 selic 的容量小于1024个元素，那么扩容的时候 slice 的 cap 就翻番，乘以2；一旦元素个数超过1024个元素，增长因子就变成1.25，即每次增加原来容量的四分之一” 大多数情况也确实如此，但是根据 newcap 的计算规则，如果新的容量超过旧的容量2倍时会直接按新的容量分配，真的是这样吗?package mainimport ( “fmt”)func main() { s := make([]int, 10, 10) fmt.Println(len(s), cap(s)) s2 := make([]int, 40) s = append(s, s2…) fmt.Println(len(s), cap(s))}以上代码的输出(Go Playground):10 1050 52这个结果有点出人意料， 如果是2倍增长应该是 10 * 2 * 2 * 2 结果应该是80， 如果说新的容量高于旧容量的两倍但结果也不是50，实际上 newcap 的结果就是50，那段逻辑很好理解，但是switch 根据 et.size 来调整 newcap 后就是52了，这段逻辑走到了 case et.size == sys.PtrSize 这段，详细的以后做源码分析再说。 总结 当 slice 的长度超过其容量，会分配新的数组，并把旧数组上的值拷贝到新的数组逐个元素添加到 slice 并操过其容量， 如果 selic 的容量小于1024个元素，那么扩容的时候 slice 的 cap 就翻番，乘以2；一旦元素个数超过1024个元素，增长因子就变成1.25，即每次增加原来容量的四分之一。批量添加元素，当新的容量高于旧容量的两倍，就会分配比新容量稍大一些，并不会按上面第二条的规则扩容。当 slice 发生扩容，引用新数组后，slice 操作不会再影响旧的数组，而是新的数组（社区经常讨论的传递 slice 容量超出后，修改数据不会作用到旧的数据上），所以往往设计函数如果会对长度调整都会返回新的 slice，例如 append 方法。slice 是引用类型？slice 不发生扩容，所有的修改都会作用在原数组上，那如果把 slice 传递给一个函数或者赋值给另一个变量会发生什么呢，slice 是引用类型，会有新的内存被分配吗。package mainimport ( “fmt” “strings” “unsafe”)func main() { s := make([]int, 10, 20) size := unsafe.Sizeof(0) fmt.Printf("%p\n", &s) fmt.Printf("%x\n", *(uintptr)(unsafe.Pointer(&s))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size2))) slice(s) s1 := s fmt.Printf("%p\n", &s1) fmt.Printf("%x\n", *(uintptr)(unsafe.Pointer(&s1))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size2))) fmt.Println(strings.Repeat("-", 50)) *(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size)) = 20 fmt.Printf("%x\n", *(uintptr)(unsafe.Pointer(&s))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size2))) fmt.Printf("%x\n", *(uintptr)(unsafe.Pointer(&s1))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s1)) + size2))) fmt.Println(s) fmt.Println(s1) fmt.Println(strings.Repeat("-", 50)) s2 := s s2 = append(s2, 1) fmt.Println(len(s), cap(s), s) fmt.Println(len(s1), cap(s1), s1) fmt.Println(len(s2), cap(s2), s2)}func slice(s []int) { size := unsafe.Sizeof(0) fmt.Printf("%p\n", &s) fmt.Printf("%x\n", *(uintptr)(unsafe.Pointer(&s))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size))) fmt.Println((int)(unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + size2)))}这个例子(Go Playground)比较长就不逐一分析了，在这个例子里面调用函数传递 slice 其变量的地址发生了变化， 但是引用数组的地址，slice 的长度和容量都没有变化， 这说明是对 slice 的浅拷贝，拷贝 slice 的三个属性创建一个新的变量，虽然引用底层数组还是一个，但是变量并不是一个。第二个创建 s1 变量，使用 s 为其赋值，发现 s1 和函数调用一样也是 s 的浅拷贝，之后修改 s1 的长度发现 s1 的长度发生变化，但是 s 的长度保持不变， 这也说明 s1 就是 s 的浅拷贝。这样设计有什么优势呢，第三步创建 s2 变量， 并且 append 一个元素， 发现 s2 的长度发生变化了， s 并没有，虽然这个数据就在底层数组上，但是用常规的方法 s 是看不到第11个位置上的数据的， s1 因为长度覆盖到第11个元素，所有能够看到这个数据的变化。这里能看到采用浅拷贝的方式可以使得切片的属性各自独立，而不会相互影响，这样可以有一定的隔离性，缺点也很明显，如果两个变量都引用同一个数组，同时 append， 在不发生扩容的情况下，总是最后一个 append 的结果被保留，可能引起一些编程上疑惑。 总结 slice 是引用类型，但是和 C 传引用是有区别的， C 里面的传引用是在编译器对原变量数据引用， 并不会发生内存分配，而 Go 里面的引用类型传递和赋值会进行浅拷贝，在32位平台上有12个字节的内存分配， 在64位上有24字节的内存分配。 传引用和引用类型是有区别的， slice 是引用类型。slice 的三种状态slice 有三种状态：零切片、空切片、nil切片。零切片所有的类型都有零值，如果 slice 所引用数组元素都没有赋值，就是所有元素都是类型零值，那这就是零切片。package mainimport “fmt"func main() { var s = make([]int, 10) fmt.Println(s) var s1 = make([]int, 10) fmt.Println(s1) var s2 = make([]string, 10) fmt.Println(s2)}以上代码输出(Go Playground):[0 0 0 0 0 0 0 0 0 0] [<nil> <nil> <nil> <nil> <nil> <nil> <nil> <nil> <nil> <nil>][ ]零切片很好理解，数组元素都为类型零值即为零切片，这种状态下的 slice 和正常的 slice 操作没有任何区别。空切片空切片可以理解就是切片的长度为0，就是说 slice 没有元素。 社区大多数解释空切片为引用底层数组为 zerobase 这个特殊的指针。但是从操作上看空切片所有的表现就是切片长度为0，如果容量也为零底层数组就会指向 zerobase ，这样就不会发生内存分配， 如果容量不会零就会指向底层数据，会有内存分配。package mainimport ( “fmt” “reflect” “strings” “unsafe”)func main() { var s []int s1 := make([]int, 0) s2 := make([]int, 0, 0) s3 := make([]int, 0, 100) arr := [10]int{} s4 := arr[:0] fmt.Println(strings.Repeat(”–s–", 10)) fmt.Println((reflect.SliceHeader)(unsafe.Pointer(&s))) fmt.Println(s) fmt.Println(s == nil) fmt.Println(strings.Repeat("–s1–", 10)) fmt.Println((reflect.SliceHeader)(unsafe.Pointer(&s1))) fmt.Println(s1) fmt.Println(s1 == nil) fmt.Println(strings.Repeat("–s2–", 10)) fmt.Println((reflect.SliceHeader)(unsafe.Pointer(&s2))) fmt.Println(s2) fmt.Println(s2 == nil) fmt.Println(strings.Repeat("–s3–", 10)) fmt.Println((reflect.SliceHeader)(unsafe.Pointer(&s3))) fmt.Println(s3) fmt.Println(s3 == nil) fmt.Println(strings.Repeat("–s4–", 10)) fmt.Println((*reflect.SliceHeader)(unsafe.Pointer(&s4))) fmt.Println(s4) fmt.Println(s4 == nil)}以上代码输出(Go Playground):–s—-s—-s—-s—-s—-s—-s—-s—-s—-s– {0 0 0} [] –s1—-s1—-s1—-s1—-s1—-s1—-s1—-s1—-s1—-s1– {18349960 0 0} [] –s2—-s2—-s2—-s2—-s2—-s2—-s2—-s2—-s2—-s2– {18349960 0 0} [] –s3—-s3—-s3—-s3—-s3—-s3—-s3—-s3—-s3—-s3– {824634269696 0 100} [] –s4—-s4—-s4—-s4—-s4—-s4—-s4—-s4—-s4—-s4– {824633835680 0 10}[]以上示例中除了 s 其它的 slice 都是空切片，打印出来全部都是 []，s 是nil切片下一小节说。要注意 s1 和 s2 的长度和容量都为0，且引用数组指针都是 18349960， 这点太重要了，因为他们都指向 zerobase 这个特殊的指针，是没有内存分配的。nil切片什么是nil切片，这个名字说明nil切片没有引用任何底层数组，底层数组的地址为nil就是nil切片。上一小节中的 s 就是一个nil切片，它的底层数组指针为0，代表是一个 nil 指针。总结零切片就是其元素值都是元素类型的零值的切片。空切片就是数组指针不为nil，且 slice 的长度为0。nil切片就是引用底层数组指针为 nil 的 slice。操作上零切片、空切片和正常的切片都没有任何区别，但是nil切片会多两个特性，一个nil切片等于 nil 值，且进行 json 序列化时其值为 null，nil切片还可以通过赋值为 nil 获得。数组与 slice 大比拼对数组和 slice 做了性能测试，源码在 GitHub。对不同容量和数组和切片做性能测试，代码如下，分为：100、1000、10000、100000、1000000、10000000func BenchmarkSlice100(b *testing.B) { for i := 0; i < b.N; i++ { s := make([]int, 100) for i, v := range s { s[i] = 1 + i _ = v } }}func BenchmarkArray100(b *testing.B) { for i := 0; i < b.N; i++ { a := [100]int{} for i, v := range a { a[i] = 1 + i _ = v } }}测试结果如下：goos: darwin goarch: amd64 pkg: github.com/thinkeridea/example/array_slice/test BenchmarkSlice100-8 20000000 69.8 ns/op 0 B/op 0 allocs/op BenchmarkArray100-8 20000000 69.0 ns/op 0 B/op 0 allocs/op BenchmarkSlice1000-8 5000000 318 ns/op 0 B/op 0 allocs/op BenchmarkArray1000-8 5000000 316 ns/op 0 B/op 0 allocs/op BenchmarkSlice10000-8 200000 9024 ns/op 81920 B/op 1 allocs/op BenchmarkArray10000-8 500000 3143 ns/op 0 B/op 0 allocs/op BenchmarkSlice100000-8 10000 114398 ns/op 802816 B/op 1 allocs/op BenchmarkArray100000-8 20000 61856 ns/op 0 B/op 0 allocs/op BenchmarkSlice1000000-8 2000 927946 ns/op 8003584 B/op 1 allocs/op BenchmarkArray1000000-8 5000 342442 ns/op 0 B/op 0 allocs/op BenchmarkSlice10000000-8 100 10555770 ns/op 80003072 B/op 1 allocs/op BenchmarkArray10000000-8 50 22918998 ns/op 80003072 B/op 1 allocs/op PASSok github.com/thinkeridea/example/array_slice/test 23.333s从上面的结果可以发现数组和 slice 在1000以内的容量上时性能机会一致，而且都没有内存分配，这应该是编译器对 slice 的特殊优化。从100001000000容量时数组的效率就比slice好了一倍有余，主要原因是数组在没有内存分配做了编译优化，而 slice 有内存分配。但是10000000容量往后数组性能大幅度下降，slice 是数组性能的两倍，两个都在运行时做了内存分配，其实这么大的数组还真是不常见，也没有比较做编译器优化了。slice 与数组的应用场景总结slice 和数组有些差别，特别是应用层上，特性差别很大，那什么时间使用数组，什么时间使用切片呢。之前做了性能测试，在1000以内性能几乎一致，只有100001000000时才会出现数组性能好于 slice，由于数组在编译时确定长度，也就是再编写程序时必须确认长度，所有往常不会用到更大的数组，大多数都在1000以内的长度。我认为如果在编写程序是就已经确定数据长度，建议用数组，而且竟可能是局部使用的位置建议用数组（避免传递产生值拷贝），比如一天24小时，一小时60分钟，ip是4个 byte这种情况是可以用时数组的。为什么推荐用数组，只要能在编写程序是确定数据长度我都会用数组，因为其类型会帮助阅读理解程序，dayHour := [24]Data 一眼就知道是按小时切分数据存储的，如要传递数组时可以考虑传递数组的指针，当然会带来一些操作不方便，往常我使用数组都是不需要传递给其它函数的，可能会在 struct 里面保存数组，然后传递 struct 的指针，或者用 unsafe 来反解析数组指针到新的数组，也不会产生数据拷贝，并且只增加一句转换语句。slice 会比数组多存储三个 int 的属性，而且指针引用会增加 GC 扫描的成本，每次传递都会对这三个属性进行拷贝，如果可以也可以考虑传递 slice 的指针，指针只有一个 int 的大小。 对于不确定大小的数据只能用 slice，否则就要自己做扩容很麻烦， 对于确定大小的集合建议使用数组。转载：本文作者： 戚银（thinkeridea）本文链接： https://blog.thinkeridea.com/…版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！ ...

数组，对于每一个前端人员来说是非常常见且重要的数据结构之一，也是面试常常出现的题目，掌握数组的方法能帮助我们更高效地处理问题。不过在数组的学习中，我们常常会混淆数组本身的方法和Javascript提供的数组的方法，在这里只简单归纳一下。常用的数组方法1、pop()删除数组的最后一个元素，返回被删除的元素，原数组长度减1。原数组发生了变化，但没有创建新的数组。2、shift()删除数组的第一个元素，返回被删除的元素，原数组长度减1。原数组发生了变化，但没有创建新的数组.3、unshift()添加元素到数组的第一位，返回添加后的数组的长度，可见，原数组长度加1。原数组发生了变化，但没有创建新的数组。4、push()添加元素到数组的最后，返回添加后的数组的长度，可见，原数组长度加1。原数组发生了变化，但没有创建新的数组。5、sort()将指定数组进行排序，返回排好序的数组。改变了数组。6、reverse()颠倒数组元素的顺序，返回逆序后的数组。改变了数组。7、join(separator)返回字符串值，不影响原数组。8、toString()将数组转为字符串，与join()的默认效果一致9、splice(start, end)返回被删除的元素，从start开始删，删end个（包含start）。splice(start, end, item)：返回被删除的元素，并插入新的元素item（从被删的位置插入）10、concat()拼接两个或多个数组，返回新数组，对原数组没有影响11、slice(start, end)返回截取的新数组，从start开始截取，截end个，但截取的元素不包含第end个的元素，即截取end-1个。 slice(0)：复制旧数组，生成新数组。ES5新增的方法1、indexOf()返回查找项第一次在数组中出现的位置，第一个参数为查找项，第二个参数可选，为查找开始的位置。如果查找不到，则返回 -1。这常常应用在数组去重的案例中。2、lastindexOf()从后往前找，查找方向与 indexOf 相反。3、every(callback, [this.Arg])当数组的所有元素都满足条件时，返回 true，否则返回false。条件是item>3，只有4,5,6,7大于3，返回false4、some(callback, [this.Arg])只要数组有一项元素满足条件，就返回 true，否则返回false。条件是item>3，4,5,6,7大于3，返回true5、filter(callback, [this.Arg])满足条件的元素组成新的数组条件是item>3，4, 5, 6, 7大于3，返回[4, 5, 6, 7]6、map(callback, [this.Arg])每次调用函数处理后的值组成新的数组var arr = [{“name”: “Amy”, age: 20}, {“name”: “Sheldon”}, age: 22];var result = map(function(item, index, array){ return item.age //返回[20, 22]})7、forEach()循环遍历，与for循环差不多，适用于循环次数未知，缺点是不能中断循环

题目Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.Example 1:Input: 5Output: TrueExplanation:The binary representation of 5 is: 101Example 2:Input: 7Output: FalseExplanation:The binary representation of 7 is: 111.Example 3:Input: 11Output: FalseExplanation:The binary representation of 11 is: 1011.Example 4:Input: 10Output: TrueExplanation:The binary representation of 10 is: 1010.题目地址讲解这一题的意思是判断一个整数的二进制形式，是否是0和1互相间隔排列的。题目挺简单的，但我想做的是空间O(1)。所以我用两个变量来存储遍历过程中需要保存的前一位和后一位，然后设置一个首次访问flag。遍历一遍二进制，结果就出来了。java代码class Solution { public boolean hasAlternatingBits(int n) { if(n<=2){ return true; } int temp = n; int now = 0; int previous = 0; boolean flag = true; while(temp>0){ if(flag){ now = temp%2; temp >>= 1; flag = false; }else{ previous = now; now = temp%2; if(previous==now){ return false; } temp >>= 1; } } return true; }} ...

题目在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。基本思路二维数组是有序的，比如下面的数据：1 2 34 5 67 8 9可以直接利用左下角数字开始查找：大于：比较上移小于：比较右移代码思路将二维数组看作平面坐标系从左下角（0,arr.length-1）开始比较：目标值大于坐标值—x坐标+1目标值小于坐标值—y坐标-1注意：二维数组arri中j代表x坐标i代表y坐标代码 function Find(target, array) { let i = array.length - 1; // y坐标 let j = 0; // x坐标 return compare(target, array, i, j); } function compare(target, array, i, j) { if (array[i] === undefined || array[i][j] === undefined) { return false; } const temp = array[i][j]; if (target === temp) { return true; } else if (target > temp) { return compare(target, array, i, j+1); } else if (target < temp) { return compare(target, array, i-1, j); } }拓展：二分查找二分查找的条件是必须有序。和线性表的中点值进行比较，如果小就继续在小的序列中查找，如此递归直到找到相同的值。 function binarySearch(data, arr, start, end) { if (start > end) { return -1; } var mid = Math.floor((end + start) / 2); if (data == arr[mid]) { return mid; } else if (data < arr[mid]) { return binarySearch(data, arr, start, mid - 1); } else { return binarySearch(data, arr, mid + 1, end); } } ...

题目You have an array of logs. Each log is a space delimited string of words.For each log, the first word in each log is an alphanumeric identifier. Then, either:Each word after the identifier will consist only of lowercase letters, or;Each word after the identifier will consist only of digits.We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.Return the final order of the logs.Example 1:Input: [“a1 9 2 3 1”,“g1 act car”,“zo4 4 7”,“ab1 off key dog”,“a8 act zoo”]Output: [“g1 act car”,“a8 act zoo”,“ab1 off key dog”,“a1 9 2 3 1”,“zo4 4 7”]Note:0 <= logs.length <= 1003 <= logs[i].length <= 100logs[i] is guaranteed to have an identifier, and a word after the identifier.题目地址讲解这道题我看过后立马联想到了另一个题目：953. Verifying an Alien Dictionary。那个题目是判断是否有序，而现在这个题目是要排序。感觉这一题更难。实际做下来确实还是比较难的，主要是字符串的比较，要自己写比较规则。然后在调用系统的sort函数。如果要自己写快排那又要多花不少时间了。有个小窍门，题目要求数字的logs保持原样，而且要放在数组尾部，所以我这里是从后往前遍历数组。Java代码class Solution { public String[] reorderLogFiles(String[] logs) { String[] result = new String[logs.length]; int indexBegin = 0; int indexEnd = logs.length-1; for(int i=logs.length-1;i>=0;i–){ int firstSpaceIndex = logs[i].indexOf(’ ‘); if(logs[i].charAt(firstSpaceIndex+1)>=‘0’ && logs[i].charAt(firstSpaceIndex+1)<=‘9’){ result[indexEnd–] = logs[i]; }else{ result[indexBegin++] = logs[i]; } } // for(int i=0;i<logs.length;i++){ // System.out.println(result[i]); // } StringComparator comparator = new StringComparator(); Arrays.sort(result, 0, indexBegin, comparator); return result; } class StringComparator implements Comparator<String>{ @Override public int compare(String o1, String o2) { int o1IndexOfFirstSpace = o1.indexOf(’ ‘); o1 = o1.substring(o1IndexOfFirstSpace); int o2IndexOfFirstSpace = o2.indexOf(’ ‘); o2 = o2.substring(o2IndexOfFirstSpace); int minLength = o1.length(); boolean o1ShortThano2 = true; if(o1.length()>o2.length()){ minLength = o2.length(); o1ShortThano2 = false; } boolean o1LittleThano2 = true; boolean o1Equalso2 = true; for(int i=0;i<minLength;i++){ if(o1.charAt(i)<o2.charAt(i)) { o1Equalso2 = false; break; }else if(o1.charAt(i)>o2.charAt(i)){ o1LittleThano2 = false; o1Equalso2 = false; break; } } if(o1Equalso2){ if(o1ShortThano2){ return -1; }else{ return 1; } }else{ if(o1LittleThano2){ return -1; }else{ return 1; } } } }} ...

题目Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].题目地址讲解这道题挺简单的，往后找比当前温度大的就行了。Java代码class Solution { public int[] dailyTemperatures(int[] T) { int[] result = new int[T.length]; for(int i=0;i<T.length;i++){ int index = i+1; while(index<T.length && T[index]<=T[i]){ index++; } if(index==T.length){ result[i] = 0; }else{ result[i] = index-i; } } return result; }} ...

题目You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.Example 1:Input: nums1 = [4,1,2], nums2 = [1,3,4,2].Output: [-1,3,-1]Explanation: For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1. For number 1 in the first array, the next greater number for it in the second array is 3. For number 2 in the first array, there is no next greater number for it in the second array, so output -1.Example 2:Input: nums1 = [2,4], nums2 = [1,2,3,4].Output: [3,-1]Explanation: For number 2 in the first array, the next greater number for it in the second array is 3. For number 4 in the first array, there is no next greater number for it in the second array, so output -1.Note:All elements in nums1 and nums2 are unique.The length of both nums1 and nums2 would not exceed 1000.题目地址讲解这道题主要就是考察立flag的能力（首次进入）。java代码class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] result = new int[nums1.length]; for(int i=0;i<result.length;i++){ result[i]=-1; } for(int i=0;i<nums1.length;i++){ boolean flag = false; for(int j=0;j<nums2.length;j++){ if(nums2[j]==nums1[i]){ flag = true; } if(flag && nums2[j]>nums1[i]){ result[i] = nums2[j]; break; } } } return result; }} ...

题目Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.Example 1:Input: candies = [1,1,2,2,3,3]Output: 3Explanation:There are three different kinds of candies (1, 2 and 3), and two candies for each kind.Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. The sister has three different kinds of candies. Example 2:Input: candies = [1,1,2,3]Output: 2Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1]. The sister has two different kinds of candies, the brother has only one kind of candies. Note:The length of the given array is in range [2, 10,000], and will be even.The number in given array is in range [-100,000, 100,000].题目地址讲解要让妹妹的蜡烛种类尽量多，很简单，尝试把每种不同的蜡烛都塞给妹妹，但她最多只能拿一半。java代码class Solution { public int distributeCandies(int[] candies) { Set<Integer> set = new HashSet<>(); for(int x:candies){ set.add(x); } int result=0; if(set.size()>candies.length/2){ result = candies.length/2; }else{ result = set.size(); } return result; }} ...

题目Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.If there aren’t two consecutive 1’s, return 0.Example 1:Input: 22Output: 2Explanation: 22 in binary is 0b10110.In the binary representation of 22, there are three ones, and two consecutive pairs of 1’s.The first consecutive pair of 1’s have distance 2.The second consecutive pair of 1’s have distance 1.The answer is the largest of these two distances, which is 2.Example 2:Input: 5Output: 2Explanation: 5 in binary is 0b101.Example 3:Input: 6Output: 1Explanation: 6 in binary is 0b110.Example 4:Input: 8Output: 0Explanation: 8 in binary is 0b1000.There aren’t any consecutive pairs of 1’s in the binary representation of 8, so we return 0.Note:1 <= N <= 10^9题目地址讲解首先一定要理解题目的意思，题目的意思是两个连续1之间的最大距离，比如11，最大距离是1，10001最大距离是4.然后简单的做法是，记录每个1的坐标，然后算最大的差值。但这样要额外扫描一遍坐标数组。我的代码做到了只扫描一遍N，需要三个值进行记录，index记录是否扫描到1，count记录每一段1的距离，max记录最大距离。Java代码class Solution { public int binaryGap(int N) { int index=0; int count=0; int max=0; int temp = N; while(temp>0){ if(temp%2==1){ if(index==1){ count++; max = max<count?count:max; count=0; }else{ index = 1; } }else{ if(index==1){ count++; max = max<count?count:max; } } temp >>= 1; } return max; }} ...

题目You’re now a baseball game point recorder.Given a list of strings, each string can be one of the 4 following types:Integer(one round’s score): Directly represents the number of points you get in this round."+" (one round’s score): Represents that the points you get in this round are the sum of the last two valid round’s points.“D” (one round’s score): Represents that the points you get in this round are the doubled data of the last valid round’s points.“C” (an operation, which isn’t a round’s score): Represents the last valid round’s points you get were invalid and should be removed.Each round’s operation is permanent and could have an impact on the round before and the round after.You need to return the sum of the points you could get in all the rounds.Example 1:Input: [“5”,“2”,“C”,“D”,"+"]Output: 30Explanation: Round 1: You could get 5 points. The sum is: 5.Round 2: You could get 2 points. The sum is: 7.Operation 1: The round 2’s data was invalid. The sum is: 5. Round 3: You could get 10 points (the round 2’s data has been removed). The sum is: 15.Round 4: You could get 5 + 10 = 15 points. The sum is: 30.Example 2:Input: [“5”,"-2",“4”,“C”,“D”,“9”,"+","+"]Output: 27Explanation: Round 1: You could get 5 points. The sum is: 5.Round 2: You could get -2 points. The sum is: 3.Round 3: You could get 4 points. The sum is: 7.Operation 1: The round 3’s data is invalid. The sum is: 3. Round 4: You could get -4 points (the round 3’s data has been removed). The sum is: -1.Round 5: You could get 9 points. The sum is: 8.Round 6: You could get -4 + 9 = 5 points. The sum is 13.Round 7: You could get 9 + 5 = 14 points. The sum is 27.Note:The size of the input list will be between 1 and 1000.Every integer represented in the list will be between -30000 and 30000.题目地址讲解我采取了一个数组来存放真实的分数。然后全部加起来。Java代码class Solution { public int calPoints(String[] ops) { List<Integer> result = new ArrayList<>(); for(String s:ops){ switch(s){ case “+”: result.add(result.get(result.size()-1)+result.get(result.size()-2)); break; case “D”: result.add(result.get(result.size()-1)*2); break; case “C”: result.remove(result.size()-1); break; default: result.add(Integer.parseInt(s)); } } int sum = 0; for(int i=0;i<result.size();i++){ sum += result.get(i); } return sum; }} ...

ProblemSuppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.Example 1:Input: flowerbed = [1,0,0,0,1], n = 1Output: TrueExample 2:Input: flowerbed = [1,0,0,0,1], n = 2Output: FalseNote:The input array won’t violate no-adjacent-flowers rule.The input array size is in the range of [1, 20000].n is a non-negative integer which won’t exceed the input array size.Solutionclass Solution { public boolean canPlaceFlowers(int[] bed, int n) { if (bed == null || bed.length == 0) return n == 0; if (n > (bed.length+1)/2) return false; if (bed.length == 1) return !(bed[0] == 1 && n >= 1); int i = 0, k = n; while (i < bed.length && k > 0) { if (bed[i] == 1) i+=2; else { if (i > 0 && i < bed.length-1) { if (bed[i-1] == 0 && bed[i+1] == 0) { bed[i] = 1; k–; } } else if (i == 0) { if (bed[i+1] != 1) { bed[i] = 1; k–; } } else { if (bed[i-1] != 1) { bed[i] = 1; k–; } } i++; } } return k <= 0; }} ...

ProblemWinter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.Note:Numbers of houses and heaters you are given are non-negative and will not exceed 25000.Positions of houses and heaters you are given are non-negative and will not exceed 10^9.As long as a house is in the heaters’ warm radius range, it can be warmed.All the heaters follow your radius standard and the warm radius will the same.Example 1:Input: [1,2,3],[2]Output: 1Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.Example 2:Input: [1,2,3,4],[1,4]Output: 1Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.Solutionclass Solution { public int findRadius(int[] houses, int[] heaters) { Arrays.sort(houses); Arrays.sort(heaters); int i = 0, res = 0; for (int house: houses) { while (i < heaters.length-1 && house-heaters[i] >= heaters[i+1]-house) i++; res = Math.max(res, Math.abs(heaters[i]-house)); } return res; }} ...

ProblemGiven a matrix A, return the transpose of A.The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.Example 1:Input: [[1,2,3],[4,5,6],[7,8,9]]Output: [[1,4,7],[2,5,8],[3,6,9]]Example 2:Input: [[1,2,3],[4,5,6]]Output: [[1,4],[2,5],[3,6]]Note:1 <= A.length <= 10001 <= A[0].length <= 1000Solutionclass Solution { public int[][] transpose(int[][] A) { int m = A.length, n = A[0].length; int[][] B = new int[n][m]; for (int j = 0; j < n; j++) { for (int i = 0; i < m; i++) { B[j][i] = A[i][j]; } } return B; }} ...

ProblemGiven an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.You may return any answer array that satisfies this condition.Example 1:Input: [3,1,2,4]Output: [2,4,3,1]The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.Note:1 <= A.length <= 50000 <= A[i] <= 5000Solutionclass Solution { public int[] sortArrayByParity(int[] A) { if (A == null || A.length < 2) return A; int i = 0, j = 0; while (j < A.length) { while (i < j && A[i]%2 == 0) i++; if (A[j]%2 == 0) { int temp = A[i]; A[i] = A[j]; A[j] = temp; i++; } j++; } return A; }} ...

ProblemThe n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.Example:Input: 4Output: [ [".Q..", // Solution 1 “…Q”, “Q…”, “..Q.”], ["..Q.", // Solution 2 “Q…”, “…Q”, “.Q..”]]Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.Solutionclass Solution { public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(board[i], ‘.’); } List<List<String>> res = new ArrayList<>(); dfs(board, 0, res); return res; } private void dfs(char[][] board, int col, List<List<String>> res) { if (col == board.length) { res.add(construct(board)); return; } for (int row = 0; row < board.length; row++) { if (validate(board, row, col)) { board[row][col] = ‘Q’; dfs(board, col+1, res); board[row][col] = ‘.’; } } } private boolean validate(char[][] board, int row, int col) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == ‘Q’ && ( i+j == row+col || row+j == col+i || row == i )) return false; } } return true; } private List<String> construct(char[][] board) { List<String> res = new ArrayList<>(); for (int i = 0; i < board.length; i++) { String str = new String(board[i]); res.add(str); } return res; }} ...

题目You are given an array A of strings.Two strings S and T are special-equivalent if after any number of moves, S == T.A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.Return the number of groups of special-equivalent strings from A.Example 1:Input: [“a”,“b”,“c”,“a”,“c”,“c”]Output: 3Explanation: 3 groups [“a”,“a”], [“b”], [“c”,“c”,“c”]Example 2:Input: [“aa”,“bb”,“ab”,“ba”]Output: 4Explanation: 4 groups [“aa”], [“bb”], [“ab”], [“ba”]Example 3:Input: [“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]Output: 3Explanation: 3 groups [“abc”,“cba”], [“acb”,“bca”], [“bac”,“cab”]Example 4:Input: [“abcd”,“cdab”,“adcb”,“cbad”]Output: 1Explanation: 1 group [“abcd”,“cdab”,“adcb”,“cbad”]Note:1 <= A.length <= 10001 <= A[i].length <= 20All A[i] have the same length.All A[i] consist of only lowercase letters.讲解这道题我刚开始又没看懂，我以为是数组是一个字符串，对这个数组进行奇偶位的swap。后来终于懂了，是对数组中的每个字符串进行奇偶位的swap。Java代码class Solution { public int numSpecialEquivGroups(String[] A) { Set<List> set = new HashSet<>(); for(String s:A){ char[] c = s.toCharArray(); List<Character> temp1 = new ArrayList<>(); if(c.length>2){ List<Character> temp2 = new ArrayList<>(); for(int i=0;i<c.length;i+=2){ temp1.add(c[i]); } Collections.sort(temp1); for(int i=1;i<c.length;i+=2){ temp2.add(c[i]); } Collections.sort(temp2); temp1.addAll(temp2); }else{ for(int i=0;i<c.length;i++){ temp1.add(c[i]); } } set.add(temp1); } return set.size(); }} ...

题目Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.Example 1:Input: S = “loveleetcode”, C = ’e’Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]Note:S string length is in [1, 10000].C is a single character, and guaranteed to be in string S.All letters in S and C are lowercase.题目地址讲解这个简单题还花了我不少时间，主要是思绪有点混乱。这道题给我的收获是，开始和终止条件要最先检查，分支条件的顺序是非常重要的，是逻辑的一部分。这道题我先遍历一遍数组，扫描出结点的位置，存入一个结点数组。然后再遍历一遍数组，计算出结果集，同时使用一个指针记录结点数组的读取进度。Java代码class Solution { public int[] shortestToChar(String S, char C) { char[] cc = S.toCharArray(); int[] result = new int[cc.length]; List<Integer> index = new ArrayList<>(); for(int i=0;i<cc.length;i++){ if(cc[i]==C){ index.add(i); System.out.print(i); } } int count=0; for(int i=0;i<cc.length;i++){ if(i==index.get(count)){ if(count<index.size()-1){ count++; } result[i] = 0; }else if(count==0 && i<index.get(count)){ result[i] = index.get(count)-i; }else if(count==index.size()-1 && i>index.get(count)){ result[i] = i - index.get(count); }else if(count>0){ if(i-index.get(count-1) < index.get(count)-i){ result[i] = i-index.get(count-1); }else{ result[i] = index.get(count)-i; } } } return result; }} ...

题目We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.Example :Input: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]S = “abcdefghijklmnopqrstuvwxyz"Output: [3, 60]Explanation: All letters have the same length of 10. To write all 26 letters,we need two full lines and one line with 60 units.Example :Input: widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]S = “bbbcccdddaaa"Output: [2, 4]Explanation: All letters except ‘a’ have the same length of 10, and “bbbcccdddaa” will cover 9 * 10 + 2 * 4 = 98 units.For the last ‘a’, it is written on the second line becausethere is only 2 units left in the first line.So the answer is 2 lines, plus 4 units in the second line.Note:The length of S will be in the range [1, 1000].S will only contain lowercase letters.widths is an array of length 26.widths[i] will be in the range of [2, 10].题目地址讲解这道题有点写缓冲区的意思，很考验逻辑性。如果缓冲区还没满，就塞一个试试如果大于缓冲区的长度，就换一行，并让新的缓冲区重新接收；如果缓冲区恰好满了，也是换一行，缓冲区长度置0.Java代码class Solution { public int[] numberOfLines(int[] widths, String S) { if(S==null){ return new int[]{0, 0}; } char[] c = S.toCharArray(); int count=1; int len = 0; for(int i=0;i<c.length;i++){ if(len<100){ len += widths[c[i]-‘a’]; } if(len>100){ len = widths[c[i]-‘a’]; count++; }else if(len==100){ len = 0; count++; } } return new int[]{count, len}; }} ...

filter()简单讲filter就是一个数组过滤器，参数接收一个函数，数组的每一项经过函数过滤，返回一个符合过滤条件的新数组函数接收三个参数：item （当前遍历的数组项）i （当前项索引）arr （调用filter数组本身） // 需求找到数组内偶数 let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] let newArr = arr.filter((item, i, arr) => { //函数本身返回布尔值，只有当返回值为true时，当前项存入新数组。 return item % 2 == 0 }) console.log(newArr)再来一个应用，巧妙地用filter结合indexof实现去重let arr1 = [1, 2, 3, 4, 5, 6, 7, 8, 2, 3, 4, 5, 6, 7] let newArr = arr1.filter(function(item, i, self) { let a = self.indexOf(item) console.log(item----${item},self.indexOf(item)---${a},i----${i}) return self.indexOf(item) === i; }); console.log(newArr) //[1, 2, 3, 4, 5, 6, 7, 8]**利用filter的过滤功能和indexof返回数组项所在的索引，相同项返回第一个的索引这个特性。您的点赞是我继续写下去的动力！欢迎吐槽！ 谢谢！ ...

题目Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add x to A[i].After this process, we have some array B.Return the smallest possible difference between the maximum value of B and the minimum value of B.Example 1:Input: A = [1], K = 0Output: 0Explanation: B = [1]Example 2:Input: A = [0,10], K = 2Output: 6Explanation: B = [2,8]Example 3:Input: A = [1,3,6], K = 3Output: 0Explanation: B = [3,3,3] or B = [4,4,4]Note:1 <= A.length <= 100000 <= A[i] <= 100000 <= K <= 10000题目地址讲解这道题刚开始一直没看懂题，但是看懂了之后就会发现非常非常简单。题目的意思是对一个数组A中的每一个数，都加一个x，x的取值范围是-K <= x <= K，然后得到结果数组B，取B中的最大值和最小值，让这两者的差最小（最小是0），求这个最小值。这里有个误区是所有数加的x都相同，但你仔细看题目给的例子，x并不是要相同的。看完例子我们发现，只要A的最大和最小值之差小于2倍K，我们就能让B中的元素全部相等。这就是解题思路。Java代码class Solution { public int smallestRangeI(int[] A, int K) { int max=A[0]; int min=A[0]; for(int i=0;i<A.length;i++){ if(max<A[i]){ max = A[i]; } if(min>A[i]){ min=A[i]; } } if(2K>max-min){ return 0; }else{ return max-min-2K; } }} ...

题目On a N * N grid, we place some 1 * 1 * 1 cubes that are axis-aligned with the x, y, and z axes.Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).Now we view the projection of these cubes onto the xy, yz, and zx planes.A projection is like a shadow, that maps our 3 dimensional figure to a 2 dimensional plane. Here, we are viewing the “shadow” when looking at the cubes from the top, the front, and the side.Return the total area of all three projections.Example 1:Input: [[2]]Output: 5Example 2:Input: [[1,2],[3,4]]Output: 17Explanation:Here are the three projections (“shadows”) of the shape made with each axis-aligned plane.Example 3:Input: [[1,0],[0,2]]Output: 8Example 4:Input: [[1,1,1],[1,0,1],[1,1,1]]Output: 14Example 5:Input: [[2,2,2],[2,1,2],[2,2,2]]Output: 21Note:1 <= grid.length = grid[0].length <= 500 <= grid[i][j] <= 50题目地址讲解这题其实很简单，就是考察对数组的横纵操作。Java代码class Solution { public int projectionArea(int[][] grid) { return countRow(grid)+countColumn(grid)+countPlan(grid); } private int countRow(int[][] grid){ int result = 0; for(int i=0;i<grid.length;i++){ int max = grid[i][0]; for(int j=0;j<grid[i].length;j++){ if(max<grid[i][j]){ max = grid[i][j]; } } result+=max; } return result; } private int countColumn(int[][] grid){ int result = 0; for(int i=0;i<grid[0].length;i++){ int max = grid[0][i]; for(int j=0;j<grid.length;j++){ if(max<grid[j][i]){ max=grid[j][i]; } } result+=max; } return result; } private int countPlan(int[][] grid){ int result = 0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[i].length;j++){ if(grid[i][j]>0){ result++; } } } return result; }} ...

题目In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.Return the element repeated N times.Example 1:Input: [1,2,3,3]Output: 3Example 2:Input: [2,1,2,5,3,2]Output: 2Example 3:Input: [5,1,5,2,5,3,5,4]Output: 5Note:4 <= A.length <= 100000 <= A[i] < 10000A.length is even题目地址讲解这个题目很简单，只要扫描一遍数组，遇到一个数出现两次，就找到了这个数。Java代码class Solution { public int repeatedNTimes(int[] A) { Map<Integer, Integer> map = new HashMap<>(); for(int x:A){ Integer count = map.get(x); if(count==null){ map.put(x, 1); }else{ return x; } } return 0; }} ...

题目Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.You may return any answer array that satisfies this condition.Example 1:Input: [4,2,5,7]Output: [4,5,2,7]Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.Note:2 <= A.length <= 20000A.length % 2 == 00 <= A[i] <= 1000题目地址讲解这道题需要新开一个等大的空间，还需要两个指针来分别记录偶数和奇数的位置。Java代码class Solution { public int[] sortArrayByParityII(int[] A) { int[] result = new int[A.length]; int indexOfEven = 0; int indexOfOdd = 1; for(int i=0;i<A.length;i++){ if(A[i]%2==0){ result[indexOfEven] = A[i]; indexOfEven += 2; }else{ result[indexOfOdd] = A[i]; indexOfOdd += 2; } } return result; }} ...

题目A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.Example 1:Input: S = “ababcbacadefegdehijhklij"Output: [9,7,8]Explanation:The partition is “ababcbaca”, “defegde”, “hijhklij”.This is a partition so that each letter appears in at most one part.A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.Note:S will have length in range [1, 500].S will consist of lowercase letters (‘a’ to ‘z’) only.题目地址讲解这道题我居然一遍过，以前做题或多或少有些小错误。这道题我一上手就发现应该尽量阻止对数据的多次遍历，所以如果能遍历一遍得到一些有用的信息就好了。我用的解法是，建立一个map存储每个字母的首尾位置（当然实际操作中我用的是两个map分别存储字母第一次出现的位置和最后一次出现的位置）。然后如果这一段之间出现了一个字母，它的尾部位置比框住它的这个字母更大，就更新尾部位置，直到尾部位置无法再扩大为止。Java代码class Solution { public List<Integer> partitionLabels(String S) { List<Integer> result = new ArrayList<>(); char[] c = S.toCharArray(); Map<Character, Integer> mapStart = new HashMap<>(); Map<Character, Integer> mapEnd = new HashMap<>(); for(int i=0;i<c.length;i++){ if(mapStart.get(c[i])==null){ mapStart.put(c[i], i); mapEnd.put(c[i], i); }else{ mapEnd.put(c[i], i); } } int beginIndex=0; while(beginIndex<c.length){ int endIndex=mapEnd.get(c[beginIndex]); for(int i=beginIndex;i<endIndex;i++){ if(mapEnd.get(c[i])>endIndex){ endIndex = mapEnd.get(c[i]); } } result.add(endIndex-beginIndex+1); beginIndex = endIndex+1; } return result; }} ...

题目Given an array of 2n integers, your task is to group these integers into n pairs of integer, say $(a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n)$ which makes sum of $min(a_i, b_i)$ for all i from 1 to n as large as possible.Example 1:Input: [1,4,3,2]Output: 4Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).Note:n is a positive integer, which is in the range of [1, 10000].All the integers in the array will be in the range of [-10000, 10000].题目地址讲解这道题对我来说难点在于看懂题，哈哈哈。题目的意思是2n个数，两两一组，求$$\sum_{i=0}^{n} min(a_i, b_i)$$我们对数组排序，让小的两个组成一对，这样就能得到最大结果了。Java代码class Solution { public int arrayPairSum(int[] nums) { Arrays.sort(nums); int result=0; for(int i=0;i<nums.length;i+=2){ result+=nums[i]; } return result; }} ...

前言 在 JS 中我们数组用的是比较多的了，它自带了很多方法可以用，省去了我们时间，特别是 ES6 当中对数组的扩展让数组具有了更强大的功能，为了以后使用数组的时候能够充分发挥数组的特性，在这里对数组的方法进行一次汇总吧。说明 标题后的标识 * 是说明该方法会改变原数组对数组元素的操作push() & pop() *push() 向数组的末尾添加一个或更多元素（就是传进去的参数），并返回新的长度。pop() 删除并返回数组的最后一个元素。具体效果看代码let arr = [1,2,3];let res1 = arr.push(5);console.log(res1); // 4 arr的长度console.log(arr); // [1,2,3,5] let res2 = arr.pop();console.log(res2); // 5 移除的数组项console.log(arr); // [1,2,3] shift() & unshift() *shift() 删除并返回数组的第一个元素unshift() 向数组的头部添加一个或者多个元素（传入的参数），并返回新的长度。具体效果看代码let arr = [1,2,3];let res1 = arr.shift();console.log(res1); // 1 移除的数组项console.log(arr); // [2,3] let res2 = arr.unshift(5,7);console.log(res2); // 4 数组新长度console.log(arr); // [5,7,2,3]slice()这个方法是从某个已有的数组返回选定的元素。一般带两参数 par1 和 par2，方法返回原数组 [par1, par2) 区间内的值组成的新数组。如果只有一个参数 par1 的话，就返回原数组 [par1，数组尾] 区间内的值组成的新数组。具体看代码let arr = [1,2,3];console.log(arr.slice(1,2)); // [2]console.log(arr.slice(1)); // [2,3]console.log(arr); // [1,2,3]splice() *这个方法有点复杂了，他是从原数组中删除/添加项目,并返回删除的项目。具体是删除还是添加，看参数决定，它至少需要两个参数 index，deleteCount，分别指代要开始删除/添加项目的下标 index 和要删除的项目的个数 deleteCount，后面如果其他参数通通就是要加入 index 位置后面的项目了。看代码就知道一切了。let arr = [0,1,2,3,4];// 删除操做console.log(arr.splice(0,2)); // [0,1] 从 下标 0 的位置开始删除两个元素，并返回。 console.log(arr); // [2,3,4] 删除后就剩它仨了// 添加操作console.log(arr.splice(1, 0, 5, 6, 7)); // [] 第二个参数 0 ，那就没有删除啥元素咯，然后在下标 1 的位置开始插入console.log(arr); // [2, 5, 6, 7, 3, 4] // 替换操作console.log(arr.splice(1,1,2)); // [5]console.log(arr); // [2, 2, 6, 7, 3, 4 ]这个方法是很强大的，可以用它来实现数组元素的删除，替换，添加的操作，看上面代码就知道啦。整个数组的大操作(转换&拼接&排序&倒置)join()这个方法是将数组转换为字符串，数组元素间用传进去的参数（ 没有参数就用,） 分隔let arr = [1,2,3,4,5];console.log(arr.join(’|’)); // 1|2|3|4|5console.log(arr.join()); // 1,2,3,4,5concat()这个方法用于拼接两个数组并返回一个新的数组。let arr = [1,2,3,4,5];console.log(arr.concat([6,7,8])); // [ 1, 2, 3, 4, 5, 6, 7, 8 ]sort() *这个就不用讲了吧，排序，不过默认的排序方法是把数字当成字符串来排序的，所以就会有了下面代码中的问题，也有了我们关于排序的重写。let arr = [1,22,13,4,5];arr.sort();console.log(arr) // [ 1, 13, 22, 4, 5 ] 因为 22 的第一个字符是 2 比 4 小，所以 22 比 4 小。。。 arr.sort(function(val1,val2){ return val1-val2;})console.log(arr); // [ 1, 13, 22, 4, 5 ]reverse() *如其名，倒置数组的元素。let arr = [1,22,13,4,5];arr.reverse();console.log(arr) // [ 5, 4, 13, 22, 1 ]toString() & toLocaleString() & valueOf()这三个方法，是个对象就会有，数组对象也不例外，也顺便写出来看看吧，具体啥效果，看代码吧。let arr = [1,22,13,4,5];console.log(arr.toString()); // 1,22,13,4,5console.log(arr.toLocaleString()); // 1,22,13,4,5console.log(arr.valueOf()); // [ 1, 22, 13, 4, 5 ]数组位置方法indexOf() & lastIndexOf()这个用于查找数组中的元素，找到后返回元素的下标，找不到的话就返回 -1。两个方法都是一样的，只不过一个从头到尾找，一个从尾到头找let arr = [1,22,13,4,5];console.log(arr.indexOf(13)); // 2console.log(arr.lastIndexOf(22)); // 1console.log(arr.indexOf(44)); // -1迭代方法every() & some()every() 对数组每一项运行一个函数，如果该函数对每一项都返回 true，则整体返回 truesome() 这个和上面一样啦，不过这个只要有一项是 true，整体就返回 true具体看代码啦let arr = [1, 2, 3, 4, 5];console.log( arr.every(function (item, index, array) { return (item > 2) })); // falseconsole.log( arr.some(function (item, index, array) { return (item > 2) })); // trueforEach()这个是对数组中的每一项运行给定函数，没有返回值。看代码吧let arr = [1,2,3,4,5]// 打印整个数组arr.forEach(function(item){ console.log(item);});map()这个方法是对数组的每一项运行给定函数，返回每一项返回结果组成的数组。let arr = [1,2,3,4,5]let newArr = arr.map(function(item){ return item+1});console.log(newArr); // [ 2, 3, 4, 5, 6 ]filter()这个方法是对数组的每一项运行给定函数，返回该函数会返回为 true 的数组项组成的新数组。let arr = [1,2,3,4,5]let newArr = arr.filter(function(item){ return item > 2});console.log(newArr); // [ 3, 4, 5 ]ES6 扩展的数组方法Array.from() 对象转为数组这个方法用于将两类对象转为真正的数组，分别是类数组对象和可遍历对象（包括 ES6 新增的数据结构 Set 和 Map）用法就看代码吧let arrLike = { ‘0’:‘1’, ‘1’:‘2’, ‘2’:‘2’, length:‘3’} let arr = Array.from( arrLike);console.log(arr); // [ ‘1’, ‘2’, ‘2’ ]在实际应用中，DOM 操作返回的 NodeList 集合就是一个类数组对象。Array.of() 值转为数组这个是用来替代 Array() 或 new Array()的，为啥要替换，来段代码感受下就知道了console.log(Array()); // []console.log(Array(3)); // [, , ,]console.log(Array(1, 2, 3)); // [ 1, 2, 3 ]console.log(Array.of()); // []console.log(Array.of(undefined)); // [undefined]console.log(Array.of(3)); // [3]console.log(Array.of(1, 2, 3)); // [ 1, 2, 3 ]看出门道了吧，Array() 会因为参数不同会有不同的效果，而 Array.of() 就不会存在这种问题啦。copyWithin() 数组内成员复制 *这个方法有点迷，暂时不知道是用来干啥的，但是也记一下它能干啥，没准以后就用上了。它的话是在当前数组内部将指定位置的成员复制到其他位置（覆盖掉原有成员），然后返回该数组。他有下面三个参数target（必选）：从该位置开始替换数据start（可选）：从该位置读取数据，默认 0。如果为负值，表示倒数。end（可选）：到该位置前停止读取数据，默认是数组长度，如果为负值，表示倒数。具体有啥效果就看代码吧let arr = [1, 2, 3, 6, 5];// 从下标 0 开始换 下标 1（也就是 2）开始的数据，一直替换到 下标 4 前（也就是到 arr[3] 结束）// 人话说就是 arr[0] 到 arr[4-2] 的值被 arr[1] 到 arr[4-1] 的值替换掉console.log(arr.copyWithin(0, 1, 4)); // [ 2, 3, 6, 6, 5 ]arr2 = [0, 1, 2, 3, 4, 5, 6];console.log(arr2.copyWithin(1, 3, 6)); // [ 0, 3, 4, 5, 4, 5, 6 ]find() & findIndex() 查找数组元素find() 用于查找符合第一个符合条件的数组成员，并将其返回。如果没有的话，就返回 undefined。findIndex() 和上面一样，不过他返回的是那个符合条件的数组的下标。啥效果就看代码吧let arr = [0, 1, 2, 3, 5, 5, 6];arr.find(function (value, index, arr) { return value > 4;}) // 返回数值 5 arr.findIndex(function (value, index, arr) { return value > 4;}) // 返回下标 4### fill() 数组填充 这个方法是用给定值填充一个数组。初始化数组的时候可以用到。它有三个参数： value 填充数组的值 start 填充的起始位置 end 填充的结束位置[1, 2, 3].fill(‘a’) // [ ‘a’, ‘a’, ‘a’ ][1, 2, 3, 4, 5].fill(‘a’, 2, 4) // [ 1, 2, ‘a’, ‘a’, 5 ]entries() & key() & values() 遍历数组这三个都会返回一个迭代器对象，可以用 for…of 循环遍历，区别是，entries() 遍历键值对，keys() 遍历键名，values() 遍历键值，啥效果看代码。let arr = [1, 2];for (let [index, ele] of arr.entries()) { console.log(index, ele);} // 0 1 1 2for (let index of arr.keys()) { console.log(index);} // 0 1for (let ele of arr.values()) { console.log(ele);} // 1 2includes() 判断数组是否有某值这个方法如其名，用于判断数组内是否有某个值，如果有，返回 true，没有，返回 false。他如果有第二个参数的话，那么第二个参数表示开始搜索的位置。let arr=[1,2,3,4,5,6,7];arr.includes(1) // truearr.includes(1,5) // false 从下标 5 开始搜没有 1关于数组的的方法，就总结道这边了，如果还有遗漏或者错误的地方的话，就麻烦下下面评论修正啦。 ...

Peak Index in a Mountain ArrayLet’s call an array A a mountain if the following properties hold:A.length >= 3There exists some 0 < i < A.length - 1 such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]Given an array that is definitely a mountain, return any i such that A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1].Example 1:Input: [0,1,0]Output: 1Example 2:Input: [0,2,1,0]Output: 1Note:3 <= A.length <= 100000 <= A[i] <= 10^6A is a mountain, as defined above.这题非常简单，就是求数组中的最大值java代码class Solution { public int peakIndexInMountainArray(int[] A) { int max = A[0]; for(int i=1;i<A.length;i++){ if(max>A[i]){ return i-1; }else{ max=A[i]; } } return 0; }}

前言 这几天面试被问到了数组的方法有哪些，回答得简直一塌糊涂，面试官说reduce的功能很强大，于是想对这个方法进行总结，在红宝书中对这个方法的描述并不算多，我也是参考了其他文章才进行总结的，下面就开始吧reduce的原理简介 在红宝书中，将这个方法定义为数组的归并方法，这个方法和迭代方法（map,forEach,filter…）一样，都会对数组进行遍历，reduce与他们不同的是函数的第一个参数得到的是迭代计算后的效果（看不懂没关系，继续往下看就会懂了）语法 这个方法接收两个参数：要执行的函数，要执行的函数中也可传入参数，分别为prev：上次调用函数的返回值cur：当前元素index：当前元素索引arr：被遍历的数组函数迭代的初始值举例没有设置函数的初始迭代值let arr = [1, 2, 3, 4];let sum = arr.reduce(function(prev, cur, index, arr) { console.log(prev, cur, index); return prev + cur;})console.log(arr, sum);运行结果：分析： 我们可以看到，在这里reduce的作用就是对这个数组进行求和，迭代了3次，函数迭代的初始值是1，也就是默认值（数组的第一项），prev的值是每次计算后的值，现在理解了吧！设置初始迭代值let arr = [1, 2, 3, 4];let sum = arr.reduce(function(prev, cur, index, arr) { console.log(prev, cur, index); return prev + cur;},5)console.log(arr, sum);运行结果：分析： 这里我们添加了一个初始的迭代值，也就是让prev从5开始计算，可以看到，这里迭代了4次，结果也加上了初始值。reduce的应用初级应用 最常见的应用一般就是求和以及求乘积了，比如说下面的例子：let arr = [1,2,3,4,5]console.log(arr.reduce((a,b) => a + b))//15console.log(arr.reduce((a,b) => a * b))//120高级应用计算数组中每个元素出现的次数let arr = [’name’,‘age’,’long’,‘short’,’long’,’name’,’name’] let arrResult = arr.reduce((pre,cur) =>{ console.log(pre,cur) if(cur in pre){ pre[cur]++ }else{ pre[cur] = 1 } return pre},{})console.log(arrResult)//结果：{name: 3, age: 1, long: 2, short: 1}运行结果：（第一个console.log）分析： 大概的解释一下，运行过程是这样的：由于设置了迭代初始值，pre的第一个值是一个空对象，此时cur为name，然后进行判断，发现在pre中没有name属性，所以就将name对应的属性值赋为1；后面没有重复的是一样的道理，如果碰到重复值，就会将该属性值加1，这样就能计算元素重复的次数了。（有没有觉得很神奇呀）去除数组中重复的元素let arrResult = arr.reduce((pre,cur) =>{ if(!pre.includes(cur)){ pre.push(cur) } return pre;},[])console.log(arrResult)//结果：[“name”, “age”, “long”, “short”]分析： 这里主要是借助迭代功能实现数组的扩展，判断当前元素是否已经添加到数组中，如果不存在就从尾部添加，这个方法在去重方法中应该算比较简单高效的。对对象的属性求和let person = [ { name: ‘xiaoming’, age: 18 },{ name: ‘xiaohong’, age: 17 },{ name: ‘xiaogang’, age: 19 }]let result = person.reduce((a,b) =>{ a = a + b.age; return a;},0)console.log(result)//结果：54分析： 这里主要就是利用reduce第一个参数是迭代，可以通过初始化这个参数的数据类型，达到想实现的效果。总结 使用reduce操作数组时，最重要的就是理解第一个参数是怎么迭代的，可以好好利用初始化这个参数的数据类型来减少很多不必要的代码。上面举的三个高级应用的例子都是利用了这个优点，当然，reduce还有更多的应用，后面碰到还会进行补充的。 如果觉得有用就给个赞吧~ ...

题目题解import java.util.Stack;public class Solution { Stack<Integer> stack = new Stack(); Stack<Integer> helpStack = new Stack(); public void push(int node) { int helpStackTop = node; if (!helpStack.isEmpty()) { helpStackTop = Math.min(helpStack.peek(), helpStackTop); } stack.push(node); helpStack.push(helpStackTop); } public void pop() { if (stack.isEmpty()) { return; } stack.pop(); helpStack.pop(); } public int top() { return stack.peek(); } public int min() { return helpStack.peek(); }}

ProblemGiven an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]….Example:Input: nums = [3,5,2,1,6,4]Output: One possible answer is [3,5,1,6,2,4]Solutionclass Solution { public void wiggleSort(int[] nums) { for (int i = 0; i < nums.length; i++) { if (i%2 == 1) { if (nums[i] < nums[i-1]) swap(nums, i, i-1); } else { if (i != 0 && nums[i] > nums[i-1]) swap(nums, i, i-1); } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }} ...

ProblemGiven an integer array sorted in ascending order, write a function to search target in nums. If target exists, then return its index, otherwise return -1. However, the array size is unknown to you. You may only access the array using an ArrayReader interface, where ArrayReader.get(k) returns the element of the array at index k (0-indexed).You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.Example 1:Input: array = [-1,0,3,5,9,12], target = 9Output: 4Explanation: 9 exists in nums and its index is 4Example 2:Input: array = [-1,0,3,5,9,12], target = 2Output: -1Explanation: 2 does not exist in nums so return -1Note:You may assume that all elements in the array are unique.The value of each element in the array will be in the range [-9999, 9999].Solutionclass Solution { public int search(ArrayReader reader, int target) { //find higher bound int r = 1; while (reader.get(r) < target) r *= 2; //then you know lower bound int l = r/2; while (l <= r) { int m = l+(r-l)/2; if (reader.get(m) == target) return m; else if (reader.get(m) < target) l = m+1; else r = m-1; } return -1; }} ...

ProblemGiven a list of words and two words word1 and word2, return the shortest distance between these two words in the list.Example:Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].Input: word1 = “coding”, word2 = “practice”Output: 3Input: word1 = “makes”, word2 = “coding"Output: 1Note:You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.Solutionclass Solution { public int shortestDistance(String[] words, String word1, String word2) { if (word1.equals(word2)) return 0; int m = -1, n = -1; int min = words.length; for (int i = 0; i < words.length; i++) { if (words[i].equals(word1)) { m = i; if (n != -1) min = Math.min(min, m-n); } else if (words[i].equals(word2)) { n = i; if (m != -1) min = Math.min(min, n-m); } } if (m == -1 || n == -1) return -1; return min; }} ...

ProblemGiven a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.Example 1:Input: [1,0,1,1,0]Output: 4Explanation: Flip the first zero will get the the maximum number of consecutive 1s.After flipping, the maximum number of consecutive 1s is 4.Note:The input array will only contain 0 and 1.The length of input array is a positive integer and will not exceed 10,000Follow up:What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?Solutionclass Solution { public int findMaxConsecutiveOnes(int[] nums) { int max = 0, lastZeroIndex = -1; int l = 0, r = 0; while (r < nums.length) { if (nums[r] == 0) { l = lastZeroIndex+1; lastZeroIndex = r; } max = Math.max(max, r-l+1); r++; } return max; }} ...

题目要求Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.Example 1:Input: nums = [1,3], n = 6Output: 1 Explanation:Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].So we only need 1 patch.Example 2:Input: nums = [1,5,10], n = 20Output: 2Explanation: The two patches can be [2, 4].Example 3:Input: nums = [1,2,2], n = 5Output: 0假设有一个有序的正整数数组nums和一个整数n，最少添加几个元素到这个数组中，使得从1-n的所有整数都可以由这个数组中的值的或是几个值的和构成。思路和代码这里的核心思路在于如何找到一个规律，使得我们可以在前一个规律的基础上添加一个数达到下一个范围。假设当前的数组可以组成从[1…k]的所有整数，那么我们下一步如果往数组中添加x，则数组就可以组成从[1…k+x]的所有整数。因此，为了只打最少的补丁，我们会希望每一次往数组中添加的元素所能够到达的范围越远越好，因此我们会patch一个k+1上去从而使得数组最远扩展到[1…2k+1]。如果当前数组中存在一个数组m位于[k+1, 2k+1]这个范围中，则我们的数组可以再次扩展到[1…2k+m+1]。 public int minPatches(int[] nums, int n) { int count = 0; long max = 0; int index = 0; while(max < n) { if(index<nums.length && max + 1 >= nums[index]) { max += nums[index++]; } else { count++; max += max + 1; } } return count; }这里需要注意的细节是数组的溢出。这里用long型避免数组值的溢出。 ...

摘要： 这些python库真“冷”，但真的很强大！Python是一种神奇的语言。事实上,它是近几年世界上发展最快的编程语言之一，它一次又一次证明了它在开发工作和数据科学立场各行业的实用性。整个Python系统和库是对于世界各地的用户(无论是初学者或者高级)都是一个恰当的选择。其成功和受欢迎的原因之一是它强大的库，这些库使其具有动态性和快速性。在本文中,我们将看到一些除了常用的像pandas、scikit-learn、 matplotlib之外的数据科学任务的Python库。虽然一看见像pandas,scikit-learn这些库就让人脑子浮现出机器学习任务,但了解并学习这个领域的其他python库总归是有益的。1、Wget从网页提取数据是数据科学家的重要任务之一。Wget是一个免费的非交互性的从网上下载文件的实用工具。它支持HTTP、HTTPS和FTP协议,以及通过HTTP代理检索。因为它是非交互性的,所以即使用户没有登录，也可以在后台工作。所以下次你想下载一个网站或页面的图片,wget可以帮助你。安装：$ pip install wget例子：import wget url = ‘http://www.futurecrew.com/skaven/song_files/mp3/razorback.mp3' filename = wget.download(url) 100% […………………………………………] 3841532 / 3841532 filename ‘razorback.mp3'2、Pendulum对于那些在python中使用日期时间感到沮丧的，可以使用Pendulum。它是一个python包，可以缓解日期时间操作，是一个python的原生类替代。如果想深入了解请参考该文档。安装：$ pip install pendulum例子：import pendulum dt_toronto = pendulum.datetime(2012, 1, 1, tz=‘America/Toronto’) dt_vancouver = pendulum.datetime(2012, 1, 1, tz=‘America/Vancouver’) print(dt_vancouver.diff(dt_toronto).in_hours()) 33、imbalanced-learn我看到过大多数分类算法效果,每个类的样本数量几乎是相同的，如balanced。但是现实生活情况下大部分是不平衡数据集，它会影响学习阶段和随后的机器学习算法的预测。幸运的是,创建了这个imbalanced库来解决这个问题。它兼容了scikit-learn并且是scikit-learn-contrib项目的一部分。当下次遇到不平衡数据集，可以尝试使用这个库。安装：pip install -U imbalanced-learn #or conda install -c conda-forge imbalanced-learn例子：用法和例子请参考文档。4、FlashTextNLP任务中清理文本数据常常需要在句子中换关键字或从句子中提取关键字。通常，这些操作可以用正则表达式来完成，但如果搜索方面遇到了数以千计的数量，可能会成为麻烦。Python的FlashText模块,该模块基于FlashText算法提供了恰当的替代等情况。FlashText最好的部分是运行时间与搜索词的数量无关，你可以在这里了解更多。安装：$ pip install flashtext例子：提取关键字from flashtext import KeywordProcessor keyword_processor = KeywordProcessor() # keyword_processor.add_keyword(<unclean name>, <standardised name>) keyword_processor.add_keyword(‘Big Apple’, ‘New York’) keyword_processor.add_keyword(‘Bay Area’) keywords_found = keyword_processor.extract_keywords(‘I love Big Apple and Bay Area.’) keywords_found [‘New York’, ‘Bay Area’]替代关键字keyword_processor.add_keyword(‘New Delhi’, ‘NCR region’) new_sentence = keyword_processor.replace_keywords(‘I love Big Apple and new delhi.’) new_sentence ‘I love New York and NCR region.‘5、Fuzzywuzzy这个名字听起来确实很奇怪,但在处理字符串匹配时，fuzzywuzzy是一个非常有用的库，可以轻松实现操作,比如字符串比较比率,令牌比率等。它也方便匹配保存在不同数据库的记录。安装：$ pip install fuzzywuzzy例子：from fuzzywuzzy import fuzz from fuzzywuzzy import process # Simple Ratio fuzz.ratio(“this is a test”, “this is a test!”) 97 # Partial Ratio fuzz.partial_ratio(“this is a test”, “this is a test!”) 100可以在GitHub repo找到更多有趣的例子。6、PyFlux时间序列分析是机器学习领域最常见的问题之一。PyFlux是一个在Python中为了时间序列问题而建立的开源库。该库有一个良好的现代时间序列模型包括但不限于ARIMA、GARCH和VAR模型。简而言之,PyFlux针对时间序列建模提供了一种概率方法，值得一试。安装：pip install pyflux例子：用法例子请参考相关文档。7、Ipyvolume结果可视化是数据科学的一个重要方面。能够可视化结果具有很大的优势。 IPyvolume是一个Python库，只需最少的配置和精力就可以在Jupyter notebook中可视化3d体积和字形（例如3d散点图）。但是，它目前处于1.0之前的阶段。一个很好的比喻是这样的：IPyvolume的volshow是3d数组而matplotlib的imshow是2d数组。你可以在这里读更多关于它的内容。安装：Using pip $ pip install ipyvolume Conda/Anaconda $ conda install -c conda-forge ipyvolume例子：动画立体渲染8、DashDash是一个用于构建Web应用程序的高效Python框架。它写在Flask，Plotly.js和React.js之上，并将现有的UI元素（如下拉列表，滑块和图形）与你的分析Python代码联系起来，而无需使用javascript。Dash非常适合构建数据可视化应用程序，然后可以在Web浏览器中呈现这些应用程序。用户指南可在此处访问。安装pip install dash==0.29.0 # The core dash backend pip install dash-html-components==0.13.2 # HTML components pip install dash-core-components==0.36.0 # Supercharged components pip install dash-table==3.1.3 # Interactive DataTable component (new!)例子下面的示例显示了下拉表的高度交互式图形。当用户在下拉列表中选择一个值时，应用程序代码会将Google财经中的数据动态导出到Pandas DataFram中。源代码9、GymOpenAI的Gym是一个用于开发和比较强化学习算法的工具包。它与任何数值计算库兼容，如TensorFlow或Theano。Gym库是测试问题的必要集合，也称为环境 – 你可以使用它来训练强化学习算法。这些环境具有共享接口，允许编写通用算法。安装pip install gym例子以下是运行环境CartPole-v0中1000个步骤的实例的例子，在每个步骤渲染环境。你可以在这里了解更多的环境。结论这些是我选的对于数据科学有用的python库，而不是常见的如numpy，pandas等。如果你知道可以添加到列表中的其他库，请在下面的评论中提及。别忘了尝试一下。本文作者：【方向】阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...

前言这两天在家中帮朋友做项目，项目中使用了数组的indexOf 方法，找到了一篇文章，感觉非常不错，顺便整理下以防链接丢失。相信说到 indexOf 大家并不陌生，判断字符串是否包涵子字符串时特别常用，正则不熟练同学的利器。这篇文章就最近遇到的一个问题，用实例再说说说indexOf方法。本文是小知识点积累，不作为深入讨论的话题，因此这里没有解释indexOf()的第二个参数，相信大家都知道第二个参数的作用。String 类型的使用温习一下大家熟知的字符串用法，举个例子let str = ‘orange’; str.indexOf(‘o’); //0str.indexOf(’n’); //3str.indexOf(‘c’); //-1这里 0 和 3 分别是 o 和 n 在字符串中出现的位置。起始下标是 0。而 -1 代表未匹配。曾经有人问我为什么偏偏是 -1 不是 null 或者 undefined。你去问制定规则的人啊！一脸无奈。大家看到这里感觉没什么亮点啊，别急接着再来一个例子let numStr = ‘2016’; numStr.indexOf(‘2’); //0numStr.indexOf(2); //0看到这里有个小点就是 indexOf 会做简单的类型转换，把数字转换成字符串 ‘2’ 然后再执行。Number 类型的使用大家可能会想 number 类型有没有 indexOf 方法因为会做隐式转换嘛！明确告诉大家没有，上例子let num = 2016; num.indexOf(2); //Uncaught TypeError: num.indexOf is not a function非要对 number 类型使用 indexOf 方法嘞？那就转换成字符串咯，接着上例来写//二逼青年的写法num = ‘2016’;num.indexOf(2); //0 //普通青年的写法num.toString().indexOf(2); //0 //文艺青年的写法(’’ + num).indexOf(2); //0第一种写法简单直接，对于已知的较短的数字也不是不可行。但是 num 变量针对不同数据是变化的时候，怎么办呢？第二种写法最为常用,但对比第三种写法长了一点。哈哈，其实都可以，代码洁癖的人喜欢第三种 √ 。array 类型的使用大家提起精神，大boss来了。数组方法大家再熟悉不过了，却忽略了数组有 indexOf 这个方法（我个人感觉）。干说不练瞎扯淡，遇到了什么问题，注意要点又在哪里？let arr = [‘orange’, ‘2016’, ‘2016’]; arr.indexOf(‘orange’); //0arr.indexOf(‘o’); //-1 arr.indexOf(‘2016’); //1arr.indexOf(2016); //-1这里没把例子拆的那么细，四个用例足以说明问题。arr.indexOf(‘orange') 输出 0 因为 ‘orange’ 是数组的第 0 个元素，匹配到并返回下标。arr.indexOf(‘o') 输出 -1 因为此方法不会在每一个元素的基础上再次执行 indexOf 匹配。arr.indexOf(‘2016') 输出 1 因为此方法从头匹配直到匹配到时返回第一个数组元素的下表，而不是返回全部匹配的下标。arr.indexOf(2016) 输出 -1 注意：这里不会做隐式类型转换。既然坑已经发现我们不妨刨根问底。去MDN官网一看究竟。对此话题感兴趣的朋友可以直接跳转到Array.prototype.indexOf()。只想了解的朋友下面给大家官方的 Description。indexOf() compares searchElement to elements of the Array using strict equality (the same method used by the === or triple-equals operator).一目了然，这里用的是严格等于（===）。大家做类似判断的时候多留意。不要误认为数字会转成字符串，同理字符串也不会转换成数字。总结以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。String：indexOf 会将’0’做类型转换，转换为0。Number：没有indexOf 方法。需要将数字类型转换为字符串。方法有三种。直接字符串、字符串toString、字符串拼接。Array：数组同样有indexOf 方法，只不过做类型判断时，使用的严格相等(strict equality)，也就是 === 。 ...

博客文章链接：数组大概知多少判断一个变量是否为数组？可靠地检测数组方法1.利用Object的toString方法var list = [1, 2, 3];Object.prototype.toString.call(list);//[object Array]2.利用ES6的Array.isArray()方法var list = [1, 2, 3];Array.isArray(list);//true数组的原生方法有哪些？会改变自身的方法：copyWithin、fill、pop、push、reverse、shift、sort、splice、unshift不会改变自身的方法：concat、includes、join、slice、toSource、toString、indexOf、lastIndexOf遍历方法：forEach、entries、every、some、filter、find、findIndexkeys、map、reduce、reduceRight、values如何将类数组的变量转化为数组？如果是ES6，可以用Array.from()方法。通常用Array.prototype.slice.call()的方法，将类似数组转换为数组。如何将类数组的变量转化为数组？如果是ES6，可以用Array.from()方法。通常用Array.prototype.slice.call()的方法，将类似数组转换为数组。