数组与链表
题目出自LeetCodehttps://leetcode-cn.com
反转链表
var reverseList = function(head){
var cur = head;
var pre = null;
while(cur != null){
var temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}两两交换链表的节点
var swapPairs = function(head) {
if(head == null || head.next ==null){
return head
}
let next = head.next
head.next = swapPairs(next.next)
next.next = head;
return next
};判断链表是否有环
var hasCycle = function(head) {
let slow=head,fast=head;
while(fast!==null&&fast.next!==null){
slow = slow.next
fast = fast.next.next
if(slow==fast){
return true
}
}
return false
};给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
先判断有环，设快慢针相遇在环的a点，则head与慢针一起走，相遇的地方就是环的入口
var detectCycle = function(head) {
let isCycle = false
let slow=head,fast=head;
while(fast!==null&&fast.next!==null){
slow = slow.next
fast = fast.next.next
if(slow==fast){
isCycle = true
break
}
}
if(isCycle){
let cur = head
while(1){
if(head==slow){
return head
}
head = head.next
slow = slow.next
}
}
return null
};K 个一组翻转链表
var reverseKGroup = function(head, k) {
var prev = null;
var curr = head;
var p1 = null;
var p2 = null;
while(curr !== null) {
for(var i = 0; i < k; i++) {
if(curr === null) {
return head;
}
curr = curr.next;
}
p1 = (prev)? prev.next: head;
p2 = p1.next;
for(var i = 0; i < k - 1; i++) {
var next = p2.next;
p2.next = p1;
p1 = p2;
p2 = next;
}
if(!prev) {
prev = head;
head.next = curr;
head = p1;
} else {
var tempPrev = prev.next;
prev.next.next = curr;
prev.next = p1;
prev = tempPrev;
}
}
return head;
};删除链表重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
var deleteDuplicates = function(head) {
let pHead = head
if(pHead == null){
return head
}
while(pHead.next !==null){
if(pHead.val == pHead.next.val){
pHead.next = pHead.next.next
}else{
pHead = pHead.next
}
}
return head
};删除链表的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
var deleteDuplicates = function(head) {
let saveHead = head
let pre = {}
pre.next = head
let phead = pre
while(pre.next){
let cur = pre.next
let flag =true
while(cur.next && cur.next.val == cur.val){
cur = cur.next
flag = false
}
if(!flag){
pre.next = cur.next
}else{
pre = pre.next
}
}
return phead.next
};从排序数组中删除重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
var removeDuplicates = function(nums) {
for(let i = 0;i<nums.length-1;i++){
if(nums[i]==nums[i+1]){
nums.splice(i,1)
i-- //移除之后下标i要回退一位
}
}
return nums.length
}; 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
var maxProfit = function(prices) {
var res = 0
for(let i = 0;i<prices.length-1;i++){
if(prices[i+1]>prices[i]){
res+=prices[i+1]-prices[i]
}
}
return res
}; 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
var rotate = function(nums, k) {
let count = k%nums.length
if(count == 0){
return
}else{
for(let i = 0;i<count;i++){
let item = nums.pop()
nums.unshift(item)
}
return
}
}; 顺（逆）时针旋转数组90度
function rotate90(arr) {
let newArr = []
let length = arr[0].length
for (let i = 0; i < length; i++) {
newArr[i] = []
}
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[0].length; j++) {
newArr[j][length - 1 - i] = arr[i][j] //顺时针旋转
// newArr[i][j] = arr[j][length-1-i]//逆时针旋转
}
}
console.log(newArr)
}
rotate90([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
])数组转置
function transposition(arr) {
let newArr = []
let length = arr[0].length
for (let i = 0; i < length; i++) {
newArr[i] = []
}
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[0].length; j++) {
newArr[i][j] = arr[j][i]
}
}
console.log(newArr)
}顺时针打印数组
//顺时针打印数组
function printArr(matrix) {
let output = []
output.push(matrix.shift())
while (matrix[0]) {
if (matrix[0].length) matrix = rotateMatrix(matrix);
output.push(matrix.shift());
}
console.log([...matrix])
}
const rotateMatrix = matrix => {
let newMatrix = [];
for (let j = matrix[0].length - 1; j >= 0; j--) {
let tempMatrix = [];
for (let i = 0; i < matrix.length; i++) {
tempMatrix.push(matrix[i][j])
}
newMatrix.push(tempMatrix)
}
return newMatrix
};
原地旋转数组
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function(matrix) {
let len = matrix.length
for (let i = 0; i < len / 2; i++) {
let start = i
let end = len - i - 1
for (let j = 0; j < end - start; j++) {
let temp = matrix[start][start + j];
matrix[start][start + j] = matrix[end - j][start];
matrix[end - j][start] = matrix[end][end - j];
matrix[end][end - j] = matrix[start + j][end];
matrix[start + j][end] = temp;
}
}
return matrix
};
传音控股公司福利 317人发布