|
__数组、链表__
====
__1.【删除数组重复元素】
题目描述：给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。<br>__
```javascript
//JS版本
var removeDuplicates = function(nums) {
? ? let p,q;
? ? p=0;
? ? q=1;
? ? while(q!=nums.length){
? ? ? ? if(nums[p]!=nums[q]){
? ? ? ? ? ? if(q-p>1)
? ? ? ? ? ? ? ? nums[p+1]=nums[q];
? ? ? ? ? ? p++;
? ? ? ? }
? ? ? ? q++;
? ? }
? ? return p+1;
};
```
__题解：<br>
核心思想——双指针，删除重复元素；设定两个指针p、q记录元素下标，p指向第1个元素（即nums[0]），q指向第二个元素（即nums[1]）。
比较p和q指向的元素，若相等，则q++往后移，寻找与p不同的第一个元素；若不相等，nums[p+1]记下q所指元素（即nums[q]），p++，q++；
此时我们已经完成基本要求。<br>
优化点:<br>
不是每次p、q不相等都需要用p+1记录q，只有当p和q不相邻时才有必要，故加判定条件q-p>1时才进行操作。__
****
__2.【旋转数组】
题目描述：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。<br>__
```javascript
//JS版本
var rotate = function(nums, k) {
? ? const newNums=new Array(nums.length);
? ? for(let i=0;i<nums.length;i++){
? ? ? ? newNums[(i+k)%nums.length]=nums[i];
? ? }
? ? for(let i=0;i<nums.length;i++){
? ? ? ? nums[i]=newNums[i];
? ? }
};
```
__题解：<br>
核心思想—辅助数组存储反转后的结果；由于旋转数组的本质是将数组元素形成一个循环，故需注意当下标越界时的处理，即（i+k）%nums.length处理得到旋转后的对应下标。<br>__
****
__3.【合并两个有序链表】
题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 <br>__
```javascript
//JS版本
var mergeTwoLists = function(l1, l2) {
? ? if (l1 === null) {
? ? ? ? return l2;
? ? } else if (l2 === null) {
? ? ? ? return l1;
? ? } else if (l1.val < l2.val) {
? ? ? ? l1.next = mergeTwoLists(l1.next, l2);
? ? ? ? return l1;
? ? } else {
? ? ? ? l2.next = mergeTwoLists(l1, l2.next);
? ? ? ? return l2;
? ? }
};
```
__题解：<br>
核心思想—递归；终止条件：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果（调用递归）。当两个链表都为空时，表示我们对链表已合并完成。<br>__
****
__4.【合并两个有序数组】
题目描述：给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 <br>__
```javascript
//JS版本
var merge = function(nums1, m, nums2, n) {
? ? let len1 = m - 1;
? ? let len2 = n - 1;
? ? let len = m + n - 1;
? ? while(len1 >= 0 && len2 >= 0) {
? ? ? ? nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
? ? }
? ? function arrayCopy(src, srcIndex, dest, destIndex, length) {
? ? ? ? dest.splice(destIndex, length, ...src.slice(srcIndex, srcIndex + length));
? ? }
? ? arrayCopy(nums2, 0, nums1, 0, len2 + 1);
};
```
__题解：<br>
核心思想—标签：从后向前数组遍历
因为 nums1 的空间都集中在后面，所以从后向前处理排序的数据会更好，节省空间，一边遍历一边将值填充进去；
设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部，从尾部值开始比较遍历，同时设置指针 len 指向 nums1 的最末尾，每次遍历比较值大小之后，则进行填充；
当 len1<0 时遍历结束，此时 nums2 中海油数据未拷贝完全，将其直接拷贝到 nums1 的前面，最后得到结果数组。
<br>__
****
|