1.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
var merge = function(intervals) {
let x = -1,ans = [];
intervals.sort((a,b) => {
return a[0] - b[0];
})
for(let i = 0; i < intervals.length;i++) {
ans.push([]);
}
for(let interval of intervals) {
if(x == -1
interval[0] > ans[x][1]) {
ans[++x] = interval;
} else {
ans[x][1] = Math.max(ans[x][1],interval[1]);
}
}
return ans.slice(0,x + 1);
};
2.不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
var uniquePaths = function(m, n) {
let arr = new Array(m).fill(0).map(() => new Array(n).fill(0));
for(let i = 0; i < m;i++) {
arr[i][0] = 1;
}
for(let i = 0; i < n;i++) {
arr[0][i] = 1;
}
for(let i = 1; i < m;i++) {
for(let j = 1; j < n; j++) {
arr[i][j] = arr[i][j - 1] + arr[i - 1][j];
}
}
return arr[m - 1][n - 1];
};
2. 电话号码的字母组合给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = “23”输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
输入：digits = “” 输出：[]
输入：digits = “2”输出：[“a”,“b”,“c”]
队列解法var letterCombinations = function(digits) {
if(digits.length == 0) {
return []
}
let map = new Map([
['2', 'abc'],
['3', 'def'],
['4', 'ghi'],
['5', 'jkl'],
['6', 'mno'],
['7', 'pqrs'],
['8', 'tuv'],
['9', 'wxyz']
]);
let queue = [];
queue.push("")
for(let i = 0; i < digits.length;i++) {
let ans = map.get(digits.charAt(i));
let qulen = queue.length;
for(let j = 0; j < qulen;j++) {
let tmp = queue.shift();
for(let z = 0; z < ans.length; z++) {
queue.push(tmp + ans.charAt(z));
}
}
}
return queue;
};
回溯解法var letterCombinations = function(digits) {
// 回溯
let res = [],path = [];
if(digits.length == 0) {
return []
}
var back = function(digits,index) {
if(index == digits.length) {
res.push(path.join(""))
return;
}
let map = new Map([
['2', 'abc'],
['3', 'def'],
['4', 'ghi'],
['5', 'jkl'],
['6', 'mno'],
['7', 'pqrs'],
['8', 'tuv'],
['9', 'wxyz']
]);
let str = map.get(digits[index]);
for(let i = 0; i < str.length; i++) {
path.push(str[i]);
back(digits,index + 1);
path.pop();
}
}
back(digits,0);
return res;
}
3.删除链表的倒数第 N 个结点给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]
输入：head = [1], n = 1 输出：[]
输入：head = [1,2], n = 1 输出：[1]
计算链表长度var removeNthFromEnd = function(head, n) {
var len = getheadlen(head),dummp = new ListNode(0,head),cur = dummp;
for(let i = 1; i < len - n + 1;i++){
cur = cur.next;
}
cur.next = cur.next.next;
return dummp.next;
}
var getheadlen = function(head) {
var len = 0;
while(head) {
len++;
head = head.next;
}
return len;
}
快慢指针var removeNthFromEnd = function(head, n) {
let dummp = new ListNode(0,head),slow = dummp,fast = head;
for(let i = 0; i < n; i++) {
fast = fast.next;
}
while(fast !== null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummp.next;
}
4.将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = [] 输出：[]
var mergeTwoLists = function(l1, l2) {
let prehead = new ListNode(0),pre = prehead;
while(l1 !== null && l2 !== null) {
if(l1.val < l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
pre.next = l1 == null ? l2 : l1;
return prehead;
}
以上题型来源于力扣}