分类： Python技术

71. 简化路径（JS实现）

1 题目
以 Unix 风格给出一个文件的*对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的*对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。*后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示*对路径的*短字符串。
示例 1：
输入：”/home/”
输出：”/home”
解释：注意，*后一个目录名后面没有斜杠。
示例 2：
输入：”/…/”
输出：”/”
解释：从根目录向上一级是不可行的，因为根是你可以到达的*高级。
示例 3：
输入：”/home//foo/”
输出：”/home/foo”
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入：”/a/./b/…/…/c/”
输出：”/c”
示例 5：
输入：”/a/…/…/b/…/c//.//”
输出：”/c”
示例 6：
输入：”/a//bc/d//././/…”
输出：”/a/b/c”

2 思路
当看标签是考察栈时，这道题也就成功了一大半了，主要思路是遇到单词就推入栈中，遇到..就弹出栈的顶部元素

3代码
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function(path) {
const arr = path.split(‘/’);
const stack = [];
const len = arr.length;

for (let i=0; i<len; i++) {
if (arr[i] === “” || arr[i] === “.”) {
continue;
} else if (arr[i] === “..”) {
stack.pop();
} else {
stack.push(arr[i]);
}
}

return ‘/’ + stack.join(‘/’);
};

73. 矩阵置零（JS实现）

1 题目
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是*好的解决方案。
你能想出一个常数空间的解决方案吗？

2 思路
这道题的思路主要是用两个数组，分别用来存储值等于0的元素行列号，然后再遍历这两个数组将对应的行和列置0，题解中还有一种方法，把原数组的*行和*列当作行列数组来进行标记，这样就没有使用额外m + n的空间

3代码
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const rows = [];
const cols = [];
const m = matrix.length;
const n = matrix[0].length;

for (let i=0; i<m; i++) {
if (cols.length === n) { //当所有列都要置为0时，就没有再遍历行的必要了
rows.push(i);
continue;
}
for (let j=0; j<n; j++) {
if (matrix[i][j] === 0) {
rows.push(i);
if (cols.includes(j)) continue;
cols.push(j);
}
}
}

for (let i=0; i<rows.length; i++) {
for (j=0; j<n; j++) {
matrix[rows[i]][j] = 0;
}
}

for (let i=0; i<cols.length; i++) {
for (let j=0; j<m; j++) {
matrix[j][cols[i]] = 0;
}
}
};

74. 搜索二维矩阵（JS实现）

1 题目
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的*个整数大于前一行的*后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false

2 思路
这道题就是用二分查找先找到在哪一行，然后在这一行内继续二分查找

3 代码
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
let m = matrix.length;
if (m === 0) return false;
let n = matrix[0].length;

let low = 0;
let high = m – 1;
let mid;
let row = -1;

while(low <= high) {
mid = Math.floor((low + high) / 2);

if (matrix[mid][0] > target) {
high = mid – 1;
} else if (matrix[mid][n – 1] < target) {
low = mid + 1;
} else {
row = mid;
break;
}
}

if (row < 0) return false;

low = 0;
high = n – 1;

while(low <= high) {
mid = Math.floor((low + high) / 2);

if (matrix[row][mid] > target) {
high = mid – 1;
} else if (matrix[row][mid] < target) {
low = mid + 1;
} else {
return true;
}
}

return false;
};

77. 组合（JS实现）

1 题目
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

2 思路
这道题的思路主要深度优先构造一棵树，由于生成的组合无关顺序，因此每层循环的初始值都是父节点的值+1

3代码
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function(n, k) {
if (k === 0) return [];

const result = [];

for (let i = 1; i <= n; i++) {
d([i], k – 1, i);
}

function d(arr, depth, begin) {
if (depth === 0) {
result.push(arr);
return;
}

for (let i = begin + 1; i <= n; i++) {
let temp = arr.slice();
temp.push(i);
d(temp, depth – 1, i);
}
}

return result;
};

9. 单词搜索（JS实现）

1 题目
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
示例:
board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]
给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false
提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

2 思路
这道题的思路主要还是考察深度优先遍历 + 回溯， 主要思路就是遍历二维数组每个元素，当发现元素和目标单词的首字母相同时，就进入递归，沿该元素的四个方向进行依次查找，用一个散列表标记已经访问过的位置，在递归过程中，若找到则返回true，若未找到，则递归回来时，要重置散列表状态

3代码
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {

let m = board.length;
let n = board[0].length;

if (m * n < word.length) return false;

let map = {};

for (let i=0; i<m; i++) {
for (let j=0; j<n; j++) {
if (board[i][j] === word[0]) {
if (search(i,j,0)) return true;
}
}
}

return false;

function search(i, j, nextIndex) {
//单词已遍历完，则表明已经找到了
if (nextIndex === word.length) {
return true;
};

let key = `${i}-${j}`;
//数组越界、已经访问过、对应字母不相等时直接返回false
if (i < 0 || j < 0 || i >= m || j >=n || map[key] || board[i][j] !== word[nextIndex]) {
return false;
}

map[key] = true;

let success = search(i+1, j, nextIndex + 1) //沿4个方向寻找
|| search(i-1, j, nextIndex + 1)
|| search(i, j+1, nextIndex + 1)
|| search(i, j-1, nextIndex + 1);

map[key] = success; //失败时要重置位置状态

return success;
}
};

81. 搜索旋转排序数组 II（JS实现）

1 题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

2 思路
这道题思路还是主要判断mid和nums[0]的大小，来确定数组的哪部分是有序数组，再判断target是在有序数组内，还是外部，进行范围的逐步缩小，值得注意的是，若有重复元素，例如[1,3,1,1,1]，此时mid=2时，其与num[0]大小相等，无法直接判断mid在左边的有序数组还是右边的有序数组，此时就需要遍历mid后面的数，若发现有任何与nums[0]不相等的数，那么mid就在左边

3代码
/**
* @param {number[]} nums
* @param {number} target
* @return {boolean}
*/
var search = function(nums, target) {
if (nums.length === 0) return false;
if (nums[0] === target || nums[nums.length – 1] === target) return true;

let low = 0;
let high = nums.length – 1;

while (low <= high) {
let mid = Math.floor((low + high) / 2);

if (nums[mid] === target) {
return true;
}

if (nums[mid] > nums[0]) {
if (target < nums[mid] && target > nums[0]) {
high = mid – 1;
} else {
low = mid + 1;
}
} else if (nums[mid] < nums[0]) {
if (target > nums[mid] && target < nums[0]) {
low = mid + 1;
} else {
high = mid – 1;
}
} else { //当无法直接判断mid位置时，遍历mid后面的数
let tempIndex = mid + 1;
let isLeft = false;
while (tempIndex < nums.length) {
if (nums[tempIndex++] !== nums[0]) { //发现不等于nums[0]的数，则mid一定在左边
isLeft = true;
}
}

if (isLeft) {
low = mid + 1;
} else {
high = mid – 1;
}
}
}

return false;
};

82. 删除排序链表中的重复元素 II（JS实现）

1 题目
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3

2 思路
这道题的思路主要思路还是双指针，prev指针上一个元素，head指针遍历每个元素，当prev和head指向的元素值不同时，两者同时向后移动，当prev和head指向的元素值相同时，此时说明出现重复元素，那么prev指针不动，head指针继续向后搜索直到找到不同的元素，然后修改指针指向，将重复元素段移除。

3代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
if (!head || !head.next) return head;

let linkHead = head;
let prev = head;
head.prev = null;
let flag = false;

while (head.next) {
head.next.prev = head;
head = head.next;
if (head.val === prev.val) {
if (!flag) {
flag = true; //打开开关，开始寻找下一个值不同的元素
};
} else {
if (flag) { //找到不同值的元素，修改指针
if (!prev.prev) { //如果重复的是列表头元素
linkHead = head;
head.prev = null;
} else { //如果重复的元素位于列表中间
prev.prev.next = head;
head.prev = prev.prev;
}
flag = false; //关闭开关，继续寻找相同的元素
}
prev = head;
}
}

if (flag) { //如果重复元素段在链表尾部
if (!prev.prev) {
linkHead = null;
} else {
prev.prev.next = null;
}
}

return linkHead;
};

88. 合并两个有序数组（JS实现）

1 题目
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

2 思路
这道题思路主要是考察如何用O(1)的存储空间完成替换，我的代码是O(n)的，看了题解，才知道，我们可以从尾部向前逐渐填充，从大到小进行填充

3代码
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
if (n === 0) return nums1;
const result = [];
let i=0, j=0;
while (j < n || i < m) {
if (i < m && nums1[i] <= nums2[j] || j >= n) {
result.push(nums1[i]);
i++;
} else {
result.push(nums2[j]);
j++
}
}

let len = m + n;

for (let i=0; i<len;i++) {
nums1[i] = result[i];
}
};

86. 分隔链表（JS实现）

1 题目
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

2 思路
这道题思路主要是新建两个列表，将大于或等于目标的元素、以及小于目标的元素分开，然后再将两个列表连接起来

3代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function(head, x) {
if (!head || !head.next) return head;

let smallLink; //小于target的元素列表头
let bigLink; //比大于或等于target的元素列表头
let bigHead;
let prev;

while(head) {
if (head.val >= x) {
if (!bigLink) {
bigLink = head;
} else {
bigHead.next = head;
}
bigHead = head;
} else {
if (prev) {
prev.next = head;
} else {
smallLink = head;
}
prev = head;
}
head = head.next;
}

if (!prev) return bigLink; //全部元素都大于或相等target
if (!bigLink) return smallLink; //全部元素都小于target
prev.next = bigLink; //将大于列表接在小于列表后面
bigHead.next = null;
return smallLink;
};

91. 解码方法（JS实现）

1 题目
一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:
输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

2 思路
这道题思路主要是考察动态规划，设d[i]为以索引号i为结尾的字符串所解码的总数，总体可以分为三种情况：1.当前位为0时。2. 当前位和前一位无法形成有效数字。3.当前位和前一位可以形成有效数字

3代码
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function(s) {
if (s.length === 0 || s[0] === ‘0’) return 0;
if (s.length === 1) return 1;

const d = [1];

for (let i=1; i<s.length; i++) {
if (s[i] === ‘0’) { // 当前位为0
if (s[i-1] !== ‘1’ && s[i-1] !== ‘2’) { //无法连接前一位形成有效数字，返回0
return 0;
} else { //d[i-2]
d[i] = i > 1 ? d[i-2] : 1;
}
} else if (s[i-1] === ‘0’ || parseInt(s[i-1])*10 + parseInt(s[i]) > 26) { //前一位为0或当前位无法连接前一位
d[i] = d[i – 1];
} else { //当前位可以连接前一位
d[i] = d[i – 1] + (i > 1 ? d[i – 2] : 1);
}
}

return d[s.length – 1];
};