目录
读算法导论(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;
};
- 两数相加
var addTwoNumbers = function (l1, l2) {
let head = null;
let temp = head;
let diff = 0;
while (l1 || l2) {
let plus = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + diff;
let newVal = plus % 10;
diff = ~~(plus / 10);
let node = new ListNode(newVal, null);
if (!head) {
head = node;
}
if (temp) {
temp.next = node;
}
temp = node;
l1 = l1 ? l1.next : null;
l2 = l2 ? l2.next : null;
}
if (diff > 0) {
let node = new ListNode(diff, null);
if (temp) {
temp.next = node;
}
}
return head;
};
var addTwoNumbers = function (l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
let carry = 0;
while (l1 || l2 || carry) {
const v1 = l1 ? l1.val : 0;
const v2 = l2 ? l2.val : 0;
const sum = v1 + v2 + carry;
carry = Math.floor(sum / 10);
current.next = new ListNode(sum % 10);
current = current.next;
if (l1) l1 = l1.next;
if (l2) l2 = l2.next;
}
return dummy.next;
};
3.最长无重复子串长度
var lengthOfLongestSubstring = function (s) {
let max = 0;
let left = 0;
const len = s.length;
const map = new Array(128).fill(-1);
for (let right = 0; right < len; right++) {
const charCode = s[right].charCodeAt(0);
if (map[charCode] >= left) {
left = map[charCode] + 1;
}
map[charCode] = right;
const currentLength = right - left + 1;
if (currentLength > max) {
max = currentLength;
}
}
return max;
};
优化代码
var lengthOfLongestSubstring = function (s) {
const len = s.length;
if (len <= 1) return len;
let max = 0;
let left = 0;
const map = new Int32Array(128).fill(-1); // 使用 Int32Array 替代普通数组
let charCode;
for (let right = 0; right < len; right++) {
// 提前终止：剩余可能的最大窗口不超过当前 max
if (len - left <= max) break;
charCode = s[right].charCodeAt(0);
// 如果字符在窗口内出现过，移动左指针
if (map[charCode] >= left) {
left = map[charCode] + 1;
}
// 更新字符的最新位置
map[charCode] = right;
// 计算当前窗口长度并更新最大值
const currentLength = right - left + 1;
if (currentLength > max) {
max = currentLength;
}
}
return max;
};
简化后
var lengthOfLongestSubstring = function (s) {
const n = s.length;
if (n <= 1) return n;
let max = 0,
l = 0,
map = new Int32Array(128).fill(-1);
for (let r = 0; r < n && n - l > max; r++) {
const c = s[r].charCodeAt(0);
if (map[c] >= l) l = map[c] + 1;
map[c] = r;
max = Math.max(max, r - l + 1);
}
return max;
};
5.最长回文子串
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时：
相对速度可能与环长形成特殊关系
导致某些位置永远无法到达
增加了不相遇的可能性