求中位數中回文數之和C語言,JS算法題之leetcode(1~10)

JS算法題之leetcode(1~10)

前言

一直以來，前端開發的知識儲備在資料結構以及算法層面是有所暫缺的，可能歸根于我們的前端開發的業務性質，但是我認為任何的程式設計崗位都離不開資料結構以及算法。

是以，我作為一名前端菜雞，打算做一個專欄，就是關于用JavaScript來解答算法題，會持續跟新，希望大家督促。同時，本人才疏學淺，文章内容可能有錯誤的地方，希望各位大神指出，謝謝。

no more bb, show me the code!

兩數之和

題目描述

給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那 兩個 整數，并傳回他們的數組下标。

示例

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

是以傳回 [0, 1]

解答

這題不難，周遊nums，用targer減去目前元素，得到的元素如果在數組中，那就完事了。不過要注意統一進制素不能用兩次

var twoSum = function(nums, target) {

let idx1, idx2;

nums.forEach((ele, index) => {

let tempIdx = nums.indexOf(target - ele);

if(tempIdx !== -1 && tempIdx !== index){

idx1 = index;

idx2 = tempIdx;

}

});

return [idx1, idx2]

};

兩數相加

題目描述

給出兩個 非空 的連結清單用來表示兩個非負的整數。其中，它們各自的位數是按照 逆序 的方式存儲的，并且它們的每個節點隻能存儲 一位 數字。

如果，我們将這兩個數相加起來，則會傳回一個新的連結清單來表示它們的和。

您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

解答

這題不難，不過稍微有點複雜，涉及到了連結清單，同時考擦了js大數的運算情況。

先周遊兩個連結清單獲得對應的數字，然後相加，最後反推算出結果對應的連結清單即可。

function ListNode(val) {

this.val = val;

this.next = null;

return {

val: this.val,

next: null

}

}

function addBigNumber(a, b) {

var res = '',

temp = 0;

a = a.split('');

b = b.split('');

while (a.length || b.length || temp) {

temp += ~~a.pop() + ~~b.pop();

res = (temp % 10) + res;

temp = temp > 9;

}

return res.replace(/^0+/, '');

}

var addTwoNumbers = function(l1, l2) {

let num1 = '', num2 = '', cur;

cur = l1;

while(cur){

num1 += cur.val.toString();

cur = cur.next;

}

cur = l2;

while(cur){

num2 += cur.val.toString();

cur = cur.next;

}

num1 = num1.split('').reverse().join('');

num2 = num2.split('').reverse().join('');

let total;

if(num1.length > 21 || num2.length > 21){

total = addBigNumber(num1, num2)

}

else{

total = Number(num1) + Number(num2)

}

total = total.toLocaleString().toString().split('').reverse().join('').replace(/,/g, '')

console.log(num1, num2, total)

let l3 = ListNode(total[0]);

cur = l3;

for(let i = 1; i < total.length; i++){

let node = ListNode(total[i]);

cur.next = node;

cur = node;

}

return l3;

};

無重複字元的最長子串

題目描述

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

示例

輸入: "abcabcbb"

輸出: 3

解釋: 因為無重複字元的最長子串是 "abc"，是以其長度為 3。

輸入: "bbbbb"

輸出: 1

解釋: 因為無重複字元的最長子串是 "b"，是以其長度為 1。

輸入: "pwwkew"

輸出: 3

解釋: 因為無重複字元的最長子串是 "wke"，是以其長度為 3。

請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

解答

維護一個數組用于存放無重複子串，周遊輸入的字元串，若目前字元不在無重複數組中，則添加，否則，無重複數組清空，并push目前字元。

同時要維護另外一個最長無重複子串的數組。

var lengthOfLongestSubstring = function(s) {

let max = 0, maxArr = [], oldArr= [];

s.split('').forEach((ele, index) => {

if(maxArr.indexOf(ele) === -1){

maxArr.push(ele)

if(maxArr.length > max){

max = maxArr.length;

}

}

else{

maxArr = [ele]

let tempItem = oldArr.pop();

while(tempItem != ele){

maxArr.unshift(tempItem)

tempItem = oldArr.pop();

}

}

oldArr = [...maxArr]

})

return max;

};

尋找兩個有序數組的中位數

題目描述

給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。

請你找出這兩個有序數組的中位數，并且要求算法的時間複雜度為 O(log(m + n))。

你可以假設 nums1 和 nums2 不會同時為空。

示例

nums1 = [1, 3]

nums2 = [2]

則中位數是 2.0

nums1 = [1, 2]

nums2 = [3, 4]

則中位數是 (2 + 3)/2 = 2.5

解答

将兩個數組合并然後排序，之後擷取中位數即可。問題在于限定時間複雜度為 O(log(m + n))的情況下，如何排序呢？

我們這裡直接使用sort()方法，該方法底層原理是将多個排序集于一體，根據數組的長度不同選擇不同的排序方法，加上V8引擎的優化，綜合來說時間複雜度是能滿足的。

好像有點偷雞摸狗的感覺。。。

sort方法的源碼：Array API源碼，從710行開始看吧

var findMedianSortedArrays = function(nums1, nums2) {

let num = nums1.concat(nums2);

num = num.sort((a, b) => a - b);

let mid = Math.floor(num.length / 2);

if (num.length % 2 === 0) {

return (num[mid-1] + num[mid])/2

} else {

return num[mid]

}

};

最長回文子串

題目描述

給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

示例

輸入: "babad"

輸出: "bab"

注意: "aba" 也是一個有效答案。

輸入: "cbbd"

輸出: "bb"

解答

這題要用動态規劃來做，先是判斷出所有長度為1,2,3的子串是否回文。

長度為1，必定回文。

長度為2或者3，取決于首位字元是否相同。

長度大于3，取決于該子串去掉首位字元之後是否回文，并且首位字元是否相同。

核心在于 dp[i][j] == dp[i+1][j-1] && s[i] === s[j]

var longestPalindrome = function(s) {

let dp = [];

for(let i = 0; i < s.length; i++){

dp[i] = [];

}

let max = -1, str = '';

for(let k = 0; k < s.length; k++){

// k為所周遊的子串長度 - 1，即左下标到右下标的距離

for(let i = 0; i + k < s.length; i++){

let j = i + k;

// i為子串開始的左下标，j為子串開始的右下标

if(k == 0){

// 當子串長度為1時，必定是回文

dp[i][j] = true;

}

else if(k <= 2){

// 當子串長度為2時，兩字元相同則符合回文，長度為3，首位字元相同則符合回文

if(s[i] == s[j]){

dp[i][j] = true;

}

else{

dp[i][j] = false;

}

}

else{

// 當子串長度超過3，取決于去掉頭尾之後的子串是否回文并且首位字元是否相同

if(dp[i+1][j-1] && (s[i] == s[j])){

dp[i][j] = true;

}

else{

dp[i][j] = false;

}

}

if(dp[i][j] && k > max){

max = k;

str = s.substring(i, j + 1)

}

}

}

return str;

};

Z 字形變換

題目描述

将一個給定字元串根據給定的行數，以從上往下、從左到右進行 Z 字形排列。

比如輸入字元串為 "LEETCODEISHIRING" 行數為 3 時，排列如下：

L C I R

E T O E S I I G

E D H N

之後，你的輸出需要從左往右逐行讀取，産生出一個新的字元串，比如："LCIRETOESIIGEDHN"。

請你實作這個将字元串進行指定行數變換的函數：

string convert(string s, int numRows);

示例

輸入: s = "LEETCODEISHIRING", numRows = 3

輸出: "LCIRETOESIIGEDHN"

輸入: s = "LEETCODEISHIRING", numRows = 4

輸出: "LDREOEIIECIHNTSG"

解釋:

L D R

E O E I I

E C I H N

T S G

解答

這題目的結構有點怪，但也是有規律可循的，我們發現這個”Z“的字元順序是這樣子的：垂直向下，斜向上，然後再垂直向下。

那其實我們可以直接将該結構簡化為一個二維數組，去掉中間的空格，再一行一行地周遊就能擷取到答案了。

如：

L D R

E O E I I

E C I H N

T S G

可以變成

L D R

E O E I I

E C I H N

T S G

接着再一行一行讀，拼成字元串，便可。

var convert = function(s, numRows) {

if(numRows == 1){

return s;

}

let arr = [], direction = 'down', line = 0, str = '';

for(let i = 0; i < numRows; i++){

arr[i] = [];

}

for(let i = 0; i < s.length; i++){

arr[line].push(s[i]);

if(line == 0){

line++;

direction = 'down'

}

else if(line == numRows - 1){

line--;

direction = 'up'

}

else{

if(direction == 'down'){

line++;

}

else if(direction = 'up'){

line--;

}

}

}

for(let i = 0; i < numRows; i++){

str += arr[i].join("");

}

return str;

};

整數反轉

題目描述

給出一個 32 位的有符号整數，你需要将這個整數中每位上的數字進行反轉。

注意:

假設我們的環境隻能存儲得下 32 位的有符号整數，則其數值範圍為 [−231,  231 − 1]。請根據這個假設，如果反轉後整數溢出那麼就傳回 0。

示例

輸入: 123

輸出: 321

輸入: -123

輸出: -321

輸入: 120

輸出: 21

解答

這題就很簡單了，不過要考慮好邊緣溢出情況即可。

var MAX = Math.pow(2, 31) - 1

var MIN = -1 * Math.pow(2, 31)

var reverse = function(x) {

let str = x.toString().split(''), symbolFlag = false;

if(str[0] == '-'){

symbolFlag = true;

str.shift();

}

str = str.reverse();

if(symbolFlag){

str.unshift('-');

}

let num = Number(str.join(''))

if(num < MIN || num > MAX){

return 0

}

else{

return num

}

};

字元串轉換整數 (atoi)

題目描述

請你來實作一個 atoi 函數，使其能将字元串轉換成整數。

首先，該函數會根據需要丢棄無用的開頭空格字元，直到尋找到第一個非空格的字元為止。

當我們尋找到的第一個非空字元為正或者負号時，則将該符号與之後面盡可能多的連續數字組合起來，作為該整數的正負号；假如第一個非空字元是數字，則直接将其與之後連續的數字字元組合起來，形成整數。

該字元串除了有效的整數部分之後也可能會存在多餘的字元，這些字元可以被忽略，它們對于函數不應該造成影響。

注意：假如該字元串中的第一個非空格字元不是一個有效整數字元、字元串為空或字元串僅包含空白字元時，則你的函數不需要進行轉換。

在任何情況下，若函數不能進行有效的轉換時，請傳回 0。

說明：

假設我們的環境隻能存儲 32 位大小的有符号整數，那麼其數值範圍為 [−231,  231 − 1]。如果數值超過這個範圍，qing傳回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例

題目很長是吧，沒關系，我們直接看示例。

輸入: "42"

輸出: 42

輸入: " -42"

輸出: -42

解釋: 第一個非空白字元為 '-', 它是一個負号。

我們盡可能将負号與後面所有連續出現的數字組合起來，最後得到 -42 。

輸入: "4193 with words"

輸出: 4193

解釋: 轉換截止于數字 '3' ，因為它的下一個字元不為數字。

輸入: "words and 987"

輸出: 0

解釋: 第一個非空字元是 'w', 但它不是數字或正、負号。

是以無法執行有效的轉換。

輸入: "-91283472332"

輸出: -2147483648

解釋: 數字 "-91283472332" 超過 32 位有符号整數範圍。

是以傳回 INT_MIN (−231) 。

解答

這題不難，但是有很多坑。首先我們采取ASCII編碼的方式來判斷字元為數字還是英文還是别的。

先去空白，去掉空白之後取第一個字元，判斷正負符号，若是英文直接傳回0，若數字則不取。

從第二個字元開始周遊，若不是數字則退出循環。

最後還要考慮溢出情況。

const MIN = -1 * Math.pow(2, 31);

const MAX = Math.pow(2, 31) - 1;

var myAtoi = function(str) {

str = str.trim();

let result = '', symbol = '';

let idx = 0;

if(str.charCodeAt(0) === 45){

idx++;

symbol = '-';

}

else if(str.charCodeAt(0) === 43){

idx++;

}

else if(str.charCodeAt(0) < 48 || str.charCodeAt(0) > 57){

return 0;

}

for(let i = idx; i < str.length; i++){

if(str.charCodeAt(i) === 46){

break;

}

else if(str.charCodeAt(i) >= 48 && str.charCodeAt(i) <= 57){

result += str[i];

}

else{

break

}

}

result = symbol.toString() + result.toString();

if(Number(result) !== Number(result)){

return 0;

}

else if(Number(result) < MIN){

return MIN;

}

else if(Number(result) > MAX){

return MAX;

}

else{

return Number(result)

}

};

回文數

題目描述

判斷一個整數是否是回文數。回文數是指正序(從左向右)和倒序(從右向左)讀都是一樣的整數。

示例

輸入: 121

輸出: true

輸入: -121

輸出: false

解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。是以它不是一個回文數。

輸入: 10

輸出: false

解釋: 從右向左讀, 為 01 。是以它不是一個回文數

解答

這題比較簡單，反轉對比即可

var isPalindrome = function(x) {

let y = x.toString().split("").reverse().join("");

return x == y

};

正規表達式比對

題目描述

給你一個字元串 s 和一個字元規律 p，請你來實作一個支援 '.' 和 '*' 的正規表達式比對。

'.' 比對任意單個字元

'*' 比對零個或多個前面的那一個元素

所謂比對，是要涵蓋 整個 字元串 s的，而不是部分字元串。

說明:

s 可能為空，且隻包含從 a-z 的小寫字母。

p 可能為空，且隻包含從 a-z 的小寫字母，以及字元 . 和 *。

示例

輸入:

s = "aa"

p = "a"

輸出: false

解釋: "a" 無法比對 "aa" 整個字元串。

輸入:

s = "aa"

p = "a*"

輸出: true

解釋: 因為 '*' 代表可以比對零個或多個前面的那一個元素, 在這裡前面的元素就是 'a'。是以，字元串 "aa" 可被視為 'a' 重複了一次。

輸入:

s = "ab"

p = ".*"

輸出: true

解釋: "." 表示可比對零個或多個('')任意字元('.')。

輸入:

s = "aab"

p = "cab"

輸出: true

解釋: 因為 '*' 表示零個或多個，這裡 'c' 為 0 個, 'a' 被重複一次。是以可以比對字元串 "aab"。

輸入:

s = "mississippi"

p = "misisp*."

輸出: false

解答

這題稍微有點複雜，我們采用了遞歸方法将兩個字元串對比，每次隻對比一個字元。

将目前遞歸p的下一個字元是否為*進行分類比較：

①p的下一個字元是*

若s和p的目前字元相同或者p的目前字元為.，則結果就取決于：

isMatch(s.slice(1), p) || isMatch(s.slice(1), p.slice(2)) || isMatch(s, p.slice(2))

若p的最後兩個字元為.*就傳回true

若不符合上面兩種情況就将取決于

isMatch(s,p.slice(2))

②p的下一個字元不為*

這種情況就簡單了

若s和p的目前字元相同或者p的目前字元為.，傳回true

否則傳回false

var isMatch = function(s, p) {

if(s.length === 0 && p.length === 0){

return true;

}

if(s.length !== 0 && p.length === 0){

return false;

}

let str = s[0], pattern = p[0];

let isNextStart = p[1] === "*";

if(isNextStart){

if(str && (str === pattern || pattern === ".")){

return isMatch(s.slice(1), p) || isMatch(s.slice(1), p.slice(2)) || isMatch(s, p.slice(2))

}

else if(pattern === "." && p.slice(2).length === 0){

return true

}

else{

return isMatch(s,p.slice(2));

}

}

else{

if(str && (str === pattern || pattern === ".")){

return isMatch(s.slice(1), p.slice(1))

}

else{

return false;

}

}

};

總結

本文所有題目均來自樂扣(leetcode)，做法不唯一，甚至可能還有所錯誤，希望各位大神指出，弟弟虛心學習。