首頁(yè)目錄 點(diǎn)擊查看
第一題
- 難度：簡(jiǎn)單
- 題目： 7. 整數(shù)反轉(zhuǎn)
給出一個(gè) 32 位的有符號(hào)整數(shù)鲸睛，你需要將這個(gè)整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)弛饭。
示例 1:
輸入: 123
輸出: 321
輸入: -123
輸出: -321
解題思路
- 翻轉(zhuǎn)我想的比較快捷的方法就是用數(shù)組的reverse方法，所以需要把字符串先轉(zhuǎn)為數(shù)組粒氧，反轉(zhuǎn)后在join成字符串珍语，但是也需要單獨(dú)處理負(fù)數(shù)的情況赐劣。
我的答案
- 簡(jiǎn)單粗暴的字符串轉(zhuǎn)換
var reverse = function (x) {
let num = parseInt((x + "").split('').reverse().join(''));
if (num < -(2 ** 31) || num > 2 ** 31 - 1) {
return 0;
}
return x < 0 ? -num : num
};
- 時(shí)間復(fù)雜度：O(N)
-
空間復(fù)雜度： O(N)
image.png
高分答案
取余法 321 = 123%10 12%10 1%10 ：這個(gè)方案我確實(shí)不知道筋帖，最后的結(jié)果也稍微略勝一籌，所以可以算比我優(yōu)的解吧绽诚。
var reverse = function(x) {
let ord = Math.abs(x);//去符號(hào)
let now = 0;
while(ord > 0){
now = now * 10 + ord % 10;
ord = Math.floor(ord / 10);
}
if(x < 0){
return now <= Math.pow(2,31) ? -now : 0;
}else{
return now < Math.pow(2,31) ? now : 0;
}
};
image.png
第二題
- 難度：中等
- 題目：8. 字符串轉(zhuǎn)換整數(shù) (atoi)
請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè) atoi 函數(shù)，使其能將字符串轉(zhuǎn)換成整數(shù)杭煎。
首先恩够，該函數(shù)會(huì)根據(jù)需要丟棄無(wú)用的開(kāi)頭空格字符，直到尋找到第一個(gè)非空格的字符為止羡铲。接下來(lái)的轉(zhuǎn)化規(guī)則如下：
如果第一個(gè)非空字符為正或者負(fù)號(hào)時(shí)蜂桶，則將該符號(hào)與之后面盡可能多的連續(xù)數(shù)字字符組合起來(lái)，形成一個(gè)有符號(hào)整數(shù)也切。
假如第一個(gè)非空字符是數(shù)字扑媚，則直接將其與之后連續(xù)的數(shù)字字符組合起來(lái)腰湾，形成一個(gè)整數(shù)。
該字符串在有效的整數(shù)部分之后也可能會(huì)存在多余的字符疆股，那么這些字符可以被忽略费坊，它們對(duì)函數(shù)不應(yīng)該造成影響。
注意：假如該字符串中的第一個(gè)非空格字符不是一個(gè)有效整數(shù)字符押桃、字符串為空或字符串僅包含空白字符時(shí)葵萎，則你的函數(shù)不需要進(jìn)行轉(zhuǎn)換，即無(wú)法進(jìn)行有效轉(zhuǎn)換唱凯。
在任何情況下羡忘，若函數(shù)不能進(jìn)行有效的轉(zhuǎn)換時(shí)，請(qǐng)返回 0 磕昼。 - 提示：
本題中的空白字符只包括空格字符 ' ' 卷雕。
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位大小的有符號(hào)整數(shù)，那么其數(shù)值范圍為 [?231, 231 ? 1]票从。如果數(shù)值超過(guò)這個(gè)范圍漫雕，請(qǐng)返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
解題思路
- 第一種方法是拆開(kāi)字符串處理：
這道題需要符合條件的需要滿足以下幾個(gè)條件：
- 字符的第一位正負(fù)號(hào)峰鄙，且字符長(zhǎng)度大于1浸间，字符串第二位必須是數(shù)字
- 字符串的第一位是數(shù)字
- 字符串的轉(zhuǎn)換的數(shù)字有大小范圍限制
- 第二種是利用parseInt處理
我的答案
- 拆分字符串
var myAtoi = function (str) {
let newStr = str.trim(), //先去掉前后空格
firstStr = newStr[0], //獲取到第一個(gè)字符
number = firstStr, //最后待輸出的number
//如果首字符不是數(shù)字 或者首字符是- +符號(hào)，但是字符整體長(zhǎng)度只有1個(gè)
if (!isNaN(firstStr) || ((firstStr === '-' || firstStr === '+') && newStr.length > 1)) {
for (let i = 1; i <= newStr.length - 1; i++) {
if (!isNaN(newStr[i]) && (newStr[i] !== ' ')) {
number += newStr[i]
} else {
break
}
}
if (number === "-" || number === "+") { //如果最后只有+- 就返回0
return 0
}
number = Number(number)
if (number < Math.pow(-2, 31) || number > Math.pow(2, 31) - 1) { //判斷范圍
return number < Math.pow(-2, 31) ? Math.pow(-2, 31) : Math.pow(2, 31) - 1;
}
return number
} else {
return 0
}
};
結(jié)果
- parseInt
let myAtoi = (str)=> {
let number = parseInt(str)
if (isNaN(number)) {
return 0
}
if (number < Math.pow(-2, 31) || number > Math.pow(2, 31) - 1) {
return number < Math.pow(-2, 31) ? Math.pow(-2, 31) : Math.pow(2, 31) - 1;
}
return number
};
image.png
兩者性能幾乎差不多吟榴，但是第二種的代碼量明顯更少魁蒜。
高分答案
我的代碼量稍微偏大，在leetCode看到一個(gè)答案只有4行吩翻，用正則處理的兜看，不怎么會(huì)正則，不過(guò)也算一個(gè)不錯(cuò)的解題方法狭瞎。貼給大家看看,性能是我這個(gè)更好一些
let myAtoi = (str)=> {
let res = str.trim().match(/^(\-|\+)?\d+/g)
return res ? Math.max(Math.min(Number(res[0]),2**31-1),-(2**31)) : 0
};
image.png
第三題
- 難度：簡(jiǎn)單
- 題目：9. 回文數(shù)
判斷一個(gè)整數(shù)是否是回文數(shù)细移。回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)熊锭。
示例：
輸入: 121
輸出: true
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 弧轧。因此它不是一個(gè)回文數(shù)。
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 碗殷。 從右向左讀, 為 121- 劣针。因此它不是一個(gè)回文數(shù)。
解題思路
- 第一種方案是把字符拆成前后兩部分亿扁，后面那部分轉(zhuǎn)換成數(shù)組后倒序，然后和前面部分比較鸟廓，如果相等則是回文
- 第二種方案是把數(shù)組分為前后兩部分从祝，角標(biāo)i的數(shù)要等于數(shù)組長(zhǎng)度-i襟己，如果兩者相等則為回文
我的答案
- 第一種：
var isPalindrome = function (x) {
x = x + ""
if (x.length === 1) {
return true
}
let isOdd = x.length % 2 === 0
let halfLen = isOdd ? x.length / 2 : Math.floor(x.length / 2)
if (x.slice(0, halfLen) === x.slice(isOdd ? halfLen : halfLen + 1).split("").reverse().join("")) {
return true
} else {
return false
}
};
console.log(isPalindrome("121"))
image.png
- 第二種
var isPalindrome = function (x) {
x = x + ""
if (x.length === 1) {
return true
}
let flag = true
for (let i = 0; i < Math.floor(x.length / 2); i++) {
if ((i < x.length - 1 - i) && x[i] !== x[x.length - 1 - i]) {
flag = false
}
}
return flag
};
console.log(isPalindrome("1221"))
image.png
高分答案
-
看了題解還有一種方案非常的好，不需要把數(shù)字轉(zhuǎn)為字符牍陌，用取余的方式擎浴。如果是負(fù)數(shù)直接返回false,如果最后一位是0，也直接返回false毒涧。
對(duì)于數(shù)字 1221贮预，如果執(zhí)行 1221 % 10，我們將得到最后一位數(shù)字 1契讲，要得到倒數(shù)第二位數(shù)字仿吞，我們可以先通過(guò)除以 10 把最后一位數(shù)字從 1221 中移除，1221 / 10 = 122捡偏，再求出上一步結(jié)果除以 10 的余數(shù)唤冈，122 % 10 = 2，就可以得到倒數(shù)第二位數(shù)字银伟。如果我們把最后一位數(shù)字乘以 10你虹，再加上倒數(shù)第二位數(shù)字，1 * 10 + 2 = 12彤避，就得到了我們想要的反轉(zhuǎn)后的數(shù)字傅物。如果繼續(xù)這個(gè)過(guò)程，我們將得到更多位數(shù)的反轉(zhuǎn)數(shù)字琉预。
現(xiàn)在的問(wèn)題是董饰，我們?nèi)绾沃婪崔D(zhuǎn)數(shù)字的位數(shù)已經(jīng)達(dá)到原始數(shù)字位數(shù)的一半？
由于整個(gè)過(guò)程我們不斷將原始數(shù)字除以 10模孩，然后給反轉(zhuǎn)后的數(shù)字乘上 10尖阔，所以，當(dāng)原始數(shù)字小于或等于反轉(zhuǎn)后的數(shù)字時(shí)榨咐，就意味著我們已經(jīng)處理了一半位數(shù)的數(shù)字了介却。
image.png
var isPalindrome = function (x) {
if (x < 0 || (x % 10 === 0 && x !== 0)) {
return false
}
let newNum = 0;
while (x > newNum) {
newNum = newNum * 10 + x % 10
x = Math.floor(x / 10)
}
return x === newNum || x === Math.floor(newNum / 10)
};
console.log(isPalindrome(123212))
這性能非常好啊，幾乎雙百了
image.png
第四題
- 難度：中等
- 題目：43. 字符串相乘
給定兩個(gè)以字符串形式表示的非負(fù)整數(shù) num1 和 num2块茁，返回 num1 和 num2 的乘積齿坷，它們的乘積也表示為字符串形式。
示例：
輸入: num1 = "2", num2 = "3"
輸出: "6"
輸入: num1 = "123", num2 = "456"
輸出: "56088"
說(shuō)明:
num1 和 num2 的長(zhǎng)度小于110数焊。
num1 和 num2 只包含數(shù)字 0-9永淌。
num1 和 num2 均不以零開(kāi)頭，除非是數(shù)字 0 本身佩耳。
不能使用任何標(biāo)準(zhǔn)庫(kù)的大數(shù)類型（比如 BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來(lái)處理遂蛀。
解題思路
- 這道題不能直接用數(shù)字相乘得最后的結(jié)論，因?yàn)榇髷?shù)會(huì)直接超出干厚，題目也不允許李滴，所以螃宙，這里只能用讀書(shū)學(xué)乘除法得方法依次做乘法，然后錯(cuò)位相加所坯。
我的答案
var multiply = function (num1, num2) {
if (num1 === "0" || num2 === "0") return "0"
let len1 = num1.length,
len2 = num2.length,
array = new Array(len1 + len2).fill(0)
for (let i = len1 - 1; i >= 0; i--) {
for (let j = len2 - 1; j >= 0; j--) {
const product = num1[i] * num2[j];
const sum = array[i + j + 1] + product;
array[i + j + 1] = sum % 10;
array[i + j] += sum / 10 | 0;
}
}
if (array[0] == 0) {
array.shift();
}
return array.join("")
};
console.log(multiply("999", '999'))
- 時(shí)間復(fù)雜度：O(N2)
-
空間復(fù)雜度： O(N)
image.png
第五題
- 難度：簡(jiǎn)單
- 題目：172. 階乘后的零
給定一個(gè)整數(shù) n谆扎，返回 n! 結(jié)果尾數(shù)中零的數(shù)量。
示例：
輸入: 3
輸出: 0
解釋: 3! = 6, 尾數(shù)中沒(méi)有零芹助。
輸入: 5
輸出: 1
解釋: 5! = 120, 尾數(shù)中有 1 個(gè)零.
說(shuō)明: 你算法的時(shí)間復(fù)雜度應(yīng)為 O(log n) 堂湖。
解題思路
- 這道題，本來(lái)打算用遞歸解決的状土，可是發(fā)現(xiàn)遞歸其實(shí)沒(méi)必要无蜂，也不是真正的需要求得最后的數(shù)值，看了大神的思路声诸，其實(shí)只要找出有多少個(gè)5就可以酱讶，一個(gè)5就有一個(gè)0
我的答案
var trailingZeroes = function (n) {
let num = 0;
while (n >= 5) {
n = parseInt(n / 5)
num += n
}
return num
};
第六題
- 難度：簡(jiǎn)單
- 題目：258. 各位相加
給定一個(gè)非負(fù)整數(shù) num，反復(fù)將各個(gè)位上的數(shù)字相加彼乌，直到結(jié)果為一位數(shù)泻肯。
示例：
輸入: 38
輸出: 2
解釋: 各位相加的過(guò)程為：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位數(shù)慰照，所以返回 2灶挟。
你可以不使用循環(huán)或者遞歸，且在 O(1) 時(shí)間復(fù)雜度內(nèi)解決這個(gè)問(wèn)題嗎毒租？
解題思路
- 這道題實(shí)際上很簡(jiǎn)單稚铣，但是主要是O(1)的時(shí)間復(fù)雜度，也就是說(shuō)不能用循環(huán)墅垮，直接處理輸出結(jié)果惕医，就需要找規(guī)律，比如'1111 = 1 * 1000 + 1 * 100 + 1 * 10 + 1'算色，現(xiàn)在換成'4= 1 + 1 + 1 + 1' 兩者之間差了'999 + 99 + 9',所以直接把這個(gè)數(shù)取9的余數(shù)抬伺，如果小于9直接輸出num,如果取余===0，則直接輸出9灾梦，其他情況峡钓，輸出余數(shù)
我的答案
var addDigits = function (num) {
if (num < 9) {
return num
} else {
if (num % 9 === 0) {
return 9
}
return num % 9
}
};
-
時(shí)間復(fù)雜度：O(1)image.png
