目录
读算法导论(todo)
2.1 插入排序
leetcode(js)
插入排序
INSERTION-SORT(A)
for j = 2 to A.length
key = A[j]
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i-1
A[i+1] = key
function insertionSort(arr) {
for (let j = 1; j < arr.length; j++) {
let key = arr[j];
let i = j - 1;
while (i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i];
i = i - 1;
}
arr[i + 1] = key;
}
return arr;
}
简单记录
- 两数之和
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
const res = [];
for (let i = 0; i < nums.length; i++) {
let newArr = JSON.parse(JSON.stringify(nums));
newArr.splice(i, 1);
if (newArr.includes(target - nums[i])) {
res.push(i);
break;
}
}
if (res.length > 0) {
for (let j = 0; j < nums.length; j++) {
if (nums[j] === target - nums[res[0]] && j !== res[0]) {
res.push(j);
break;
}
}
}
return res;
};
704.二分查找
var search = function (nums, target) {
let res = -1;
let i = 0,
j = nums.length - 1;
//这一步经常出错
while (i <= j) {
let k = Math.floor((i + j) / 2);
if (target < nums[k]) {
j = k - 1;
} else if (target > nums[k]) {
i = k + 1;
} else {
res = k;
return res;
}
}
return res;
};
https://www.hello-algo.com/
快慢指针判断链表有环 快指针走3步，一定会相遇吗
数学原理分析
基本设定
慢指针每次走1步
快指针每次走k步（k > 1）
环的长度为n
相对速度分析
每一轮快指针相对慢指针前进了(k-1)步
这个相对运动可以看作是以(k-1)的速度在环中移动
相遇条件
设从进入环后经过t次移动
要相遇必须满足：(k-1)t ≡ 0 (mod n)
即：(k-1)t必须是环长n的整数倍
具体分析k=3的情况
当k=3时：
(k-1)t ≡ 0 (mod n)
2t ≡ 0 (mod n)
这意味着： 如果n是奇数，则t必须是n的倍数 如果n是偶数，则t必须是n/2的倍数
如果快指针每次走3步，慢指针每次走1步，在有环链表中不一定会相遇。这与传统的快指针走2步的情况不同。
让我解释原因： 快指针走2步的情况（一定相遇）： 假设慢指针走了k步，快指针就走了2k步 两者的距离差每次增加1步 在环中，这个差值会以环的长度为周期循环 终会出现差值等于环的长度的情况，即相遇 快指针走3步的情况（不一定相遇）： 假设环的长度为n 每一轮，快指针比慢指针多走2步 如果n能被2整除，那么可能永远错过相遇点 举个具体例子：
环长度为4的情况：
位置编号：0,1,2,3（然后回到0）
第0次移动：慢=0，快=0
第1次移动：慢=1，快=3
第2次移动：慢=2，快=2
第3次移动：慢=3，快=1
第4次移动：慢=0，快=0（回到初始状态）
在这种情况下，快慢指针会相遇。 但如果环长度为5：
环长度为5的情况：
位置编号：0,1,2,3,4（然后回到0）
第0次移动：慢=0，快=0
第1次移动：慢=1，快=3
第2次移动：慢=2，快=1
第3次移动：慢=3，快=4
第4次移动：慢=4，快=2
第5次移动：慢=0，快=0（回到初始状态）
这形成了一个周期性模式：
相对位置差依次为：0→2→4→1→3→0
这个序列会不断重复
但永远不会出现相对位置差为0的情况（除了回到初始状态）
数学证明
对于k=3的情况：
1.每次移动后的相对距离：d = (3t - t) mod n = 2t mod n
2.要相遇，必须有：2t ≡ 0 (mod n)
3.当n为奇数时，这个方程只在t是n的倍数时成立
4.这意味着指针必须完整地走完n个周期才能相遇
结论
k=2是最优的选择，因为：
相对速度为1，保证能遍历环中每个位置
不会跳过可能的相遇点
k>2时：
相对速度可能与环长形成特殊关系
导致某些位置永远无法到达
增加了不相遇的可能性