算法刷题300问
2019-09-11
小傻瓜，哪来的300问😂
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution:
var twoSum = function(nums, target) {
let len = nums.length,
result = [];
for(let i = 0; i < len; i++) {
for(let j = i + 1; j < len; j++) {
let curI = nums[i],
curJ = nums[j];
if(curI + curJ === target) {
result.push(i);
result.push(j);
}
}
}
return result;
};
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807
Solution:
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
let add = 0, // 每一项的加数
result = null, // 结果返回的首项
curNode = null; // 当前的节点
// 只要l1或者l2中还有值就继续循环
while(l1 || l2 ) {
// 若l1或l2中不存在节点了，则值为0
let a = l1? l1.val : 0,
b = l2? l2.val : 0;
// 当前的值为 两个节点中的值以及加数的和
let sum = a + b + add;
// ~ => -(x + 1) ~~ => -(-(x + 1) + 1) ~~ 即 parseInt()
add = ~~(sum / 10);
// 去除加数后的当前节点的值 即若大于10则取个位数
let node = new ListNode(sum % 10);
// 构造返回链表的节点
if(!result) {
result = curNode = node;
} else {
curNode.next = node;
curNode = node;
}
// 移动l1的节点
if(l1){
l1 = l1.next;
}
// 移动l2的节点
if(l2) {
l2 = l2.next;
}
}
// 如果最后的节点还有加数，则创建新的节点，保存加数
if(add) {
let node = new ListNode(add);
curNode.next = node;
}
return result;
};
知识引申：按位操作符
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring,
"pwke" is a subsequence and not a substring.
Solution:
var lengthOfLongestSubstring = function(s) {
let result = 0,
temp = 0,
ind = 0,
subStr = s.substr(),
subObj = {};
while(ind < subStr.length) {
let chart = subStr[ind];
if(subObj[chart] !== undefined) {
// 将当前子字符串的长度与之前最大子字符串的长度进行比较取较大的值
if(temp > result) result = temp;
// 将下标移动回重复的字符后一位
ind = subStr.indexOf(chart) + 1;
// 截取判断过的子字符串
subStr = subStr.substr(ind);
// 将子字符对象与记长变量清空
subObj = {};
temp = 0;
ind = 0;
} else {
// 将子字符录入对象中
subObj[chart] = 1;
// 将当前子字符串的长度加1
temp++;
// 访问下一个字符
ind++;
}
}
// 将最后一个子字符串的长度与之前保留的最大子字符串长度进行比较取较大值
if(temp > result) result = temp;
return result;
};
5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
Solution:
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let left = right = 0,
len = s.length;
for(let i = 0; i < len; i++) {
// 奇数个数对称
let l = r = i;
// 判断是否相等
while(l >= 0 && r < len && s[l] == s[r]) {
l -= 1;
r += 1;
}
// r - 1 - (l + 1) 将之前循环多加和多减的1抹去，然后同right - left的值做比较
if(r - l - 2 > right - left) {
left = l + 1;
right = r - 1;
}
// 偶数个数对称
l = i;
r = i + 1;
while(l >= 0 && r < len && s[l] == s[r]) {
l -= 1;
r += 1;
}
if(r - l - 2 > right - left) {
left = l + 1;
right = r - 1;
}
}
return s.substring(left, right + 1);
};
6. ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Solution:
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
// 若分行为1，则直接返回原字符串
if(numRows <= 1) {
return s;
}
let len = s.length,
// 链表数组
linkList = [],
// 保存最后结果
ans = '',
// Z形移动的下标
linkIndex = 0,
// 标识下标当前该如何移动的标志， true为增 false为减
signal = false;
for(let i = 0; i < len; i++) {
// 链表节点
let node = new Node(s[i]);
// 到达Z两端，需要转折
if(i % (numRows - 1) == 0) {
signal = !signal;
}
if(signal) {
// 增
linkIndex = i % (numRows - 1);
} else {
// 减
linkIndex = (numRows - 1) - (i % (numRows - 1));
}
// 第一个节点
if(linkList[linkIndex] == undefined) {
linkList[linkIndex] = node;
} else {
let head = linkList[linkIndex];
// 找到最后一个节点
while(!!head.next) head = head.next;
// 将节点挂到当前行的最后一个
head.next = node;
}
}
// 将链表中的字符取出来
linkList.map((head) => {
while(head) {
ans += head.val;
head = head.next;
}
});
return ans;
};
// 链表节点
function Node(val) {
this.val = val;
this.next = null;
}
7. Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Solution:
/**
* @param {number} x
* @return {number}
*/
var reverse = function(x) {
// 标识数字正负
let signal = true,
x_arr = `${x}`.split(''), // 将数字拆分为数组
ans = 0;
if(x < 0) {
// 输入数字为负
signal = false;
// 将负号退出数组
x_arr.shift();
}
// 将数字逆序
x_arr.reverse();
// 将数组转为数字
ans = +x_arr.join('');
// 为ans加入符号
if(!signal) {
ans = -ans;
}
// 判断逆序的数字是否超出32位有符号整数的范围
if(ans > (Math.pow(2, 31) - 1) || ans < -Math.pow(2, 31)) {
ans = 0;
}
return ans;
};
9. Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121.
From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Coud you solve it without converting the integer to a string?
Solution:
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
// 如果为负数，直接返回
if(x < 0) {
return false;
}
// 保存各个位数上的数字
let num_list = [],
num = x;
// 将input的数字拆解为数字数组
while(num) {
let tmp = num % 10;
num_list.push(tmp);
num = ~~(num / 10);
}
// 计算数字数组的位数
let len = num_list.length,
index = r_num = 0; // index指示当前位数 r_num为逆序之后的数字
// 遍历拆解之后的数字数组
while(index < len) {
// 将各个下标中的数字，转化为对应位数上的数字
r_num += num_list[index] * Math.pow(10, len - 1 - index);
index++;
}
// 如果逆序之后与input数字相等，则返回true，否则返回false
if(r_num == x) {
return true;
} else {
return false;
}
};