贝壳校招春招已开

1.无重复字符的最长字串        此题定义一个map存储nums中对应索引值，用双指针进行遍历。初始化l=0和res。用r进行遍历，如果遇到重复的就重置l，也就是l=重复值的索引+1，重新开一个区间。r固定往右走，并将r，也就是索引值存储到map里。r-l+1就是区间大小，比较它和res的大小。最终return一个res。2.LRU缓存        要创建两个结构体，一个是LRUCache，规定了当前cache的存量和容量，以及一个map[int]*Node，规定头节点和尾节点。一个是Node，规定了key和val以及prev和next。规定初始化Node函数和构建LRUCache函数。        重点在于Get和Put函数。        Get函数尝试从map中取值，取不到返回-1，else就返回val值，并把当前kv挪到链表head的下一个，也就是moveToHead（）函数，这个函数首先要移除他自身节点，也就是removeNode（node），此函数将节点上一个连到下一个，下一个连到上一个。再执行addToHead(node)函数，将node连到头节点下一个。也要将node的上一个连到头节点。        Put函数尝试检查map中是否有已存在的key，如果有将val替换，并将此节点moveToHead。没有的话，用initNode()创建一个节点，并使用addToHead()插入头节点，记得把cache的cnt++，并检查是否大于容量cap。如果大于cap，用removeTail（）函数移除尾节点，包括cnt--，此函数将取出尾节点执行removeNode（node）。还要记得用delete（）函数删除缓存队列中的键值对。3.反转链表        定义一个cur和一个pre，for cur！=nil开始，存储cur.next，cur.next指向pre，并pre=cur，cur=next。直到cur=nil的时候停了，返回pre。4.数组中第K个最大元素        使用快排或堆排。快排用到递归思想，定义一个qsort函数，输入待排数组和区间l，r，以及k值，返回的是第k个元素。首先是终止递归条件，也就是l==r。将nums[0]作为标准值进行比对。并从左右开始定义i=l+1，j=r-1，nums[l]要是比标准值小就停，（此处判断条件是大于partition才能i++）。也就是把小的放到右边，实现降序排序。r则相反，交换numsi和numsj，规定好顺序。然后将已经排好的区间，用j和k作比较，如果j比k大，说明已经覆盖到了，对左边进行排序就好了。如果j比k小，就对右边进行排序，也就是j+1到r。        堆排的话，首先要对数组进行堆化。用buildMaxHeap来进行，对于i=heapSize/2-1的值，要执行Heapify函数进行堆化。Heapify函数要创建左儿子和右儿子的索引值，也就是2*i+1和2*i+2以及largest=i，判断左儿子和右儿子是否大于父节点，并对largest进行相应赋值，并交换儿子节点和父节点。并对交换的节点进行堆化，保证儿子节点都符合堆的定义。构建完堆后，开始对根节点堆化。for一个i=n-1，做k-1次，也就是i>n-1-(k-1)。交换nums[0]和nums[I]，将heapSize--，并对0执行Heapify。此处保证0处永远是最大的，减小HeapSize是为了将大的放到后面就不动了，依次排完，nums就编程升序。如果执行n-1次的话，此时数组按升序排序，n-1就是第1大的，n-2就是第2大的。返回n-k获得第k个大的值。5.K个一组反转链表        对于链表，要使用dummy，返回的是dummy.Next。创建一个pre指针，开始for head！=nil。首先要反转的链表节点数是否大于k，不大于k直接返回dummy.Next。然后对大于k的部分进行翻转。要注意，这里需要翻转的链表，head指向下个部分的头，而tail指向上个部分的尾。也就是head,tail= func reverse（head，tail）(tail,head){}(………………)（）。6.三数之和#牛客AI配图神器#        此题通过双指针方法来进行。首先先进行sort.Ints（nums）进行升序排序，其次确定i，l，r的值。i从0开始，l从i+1开始，r从len-1开始依次遍历。这里要注意去重，条件是nums[i]==nums[i-1]&&i>0，开头要规定条件，否则会报错。        再开一个for循环遍历此i情况下的l和r，条件是l<r。如果三树之和大于0，说明和太大，把r-1使得和变小。反之亦然，进入下轮遍历。二者都不满足加入结果集，并进行去重，注意此时去重的条件为nums[l]==nums[l+1]，r也是一样。因为先加入了结果集，所以去重条件要直接判断下一个，注意记得判断尾部，并上一个l<r。7.最大子数组和        此题首先遍历数组的每个值，要注意遍历的判断条件，也就是要满足当前值大于0，并且和小于0的时候，再将sum归零。此后继续将值与sum相加，比较maxSum和sum的大小，最后return maxSum8.合并两个有序链表        注意点：此题需要创建一个新的头节点，指向头结点。以及虚拟节点cur1，cur2指向两个链表头节点，通过比较cur1和cur2的值大小，往cur中插入节点。最后返回的是dummy.Next。