leetCode之?dāng)?shù)字操作

首頁(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è)條件:
  1. 字符的第一位正負(fù)號(hào)峰鄙,且字符長(zhǎng)度大于1浸间,字符串第二位必須是數(shù)字
  2. 字符串的第一位是數(shù)字
  3. 字符串的轉(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
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市若河,隨后出現(xiàn)的幾起案子能岩,更是在濱河造成了極大的恐慌,老刑警劉巖萧福,帶你破解...
    沈念sama閱讀 222,627評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拉鹃,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)膏燕,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,180評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門炭庙,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人煌寇,你說(shuō)我怎么就攤上這事∮庑郏” “怎么了阀溶?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,346評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)鸦泳。 經(jīng)常有香客問(wèn)我银锻,道長(zhǎng),這世上最難降的妖魔是什么做鹰? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,097評(píng)論 1 300
  • 正文 為了忘掉前任击纬,我火速辦了婚禮,結(jié)果婚禮上钾麸,老公的妹妹穿的比我還像新娘更振。我一直安慰自己,他們只是感情好饭尝,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,100評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布肯腕。 她就那樣靜靜地躺著,像睡著了一般钥平。 火紅的嫁衣襯著肌膚如雪实撒。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,696評(píng)論 1 312
  • 那天涉瘾,我揣著相機(jī)與錄音知态,去河邊找鬼。 笑死立叛,一個(gè)胖子當(dāng)著我的面吹牛负敏,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播囚巴,決...
    沈念sama閱讀 41,165評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼原在,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了彤叉?” 一聲冷哼從身側(cè)響起庶柿,我...
    開(kāi)封第一講書(shū)人閱讀 40,108評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎秽浇,沒(méi)想到半個(gè)月后浮庐,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,646評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,709評(píng)論 3 342
  • 正文 我和宋清朗相戀三年审残,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了梭域。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,861評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡搅轿,死狀恐怖病涨,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情璧坟,我是刑警寧澤既穆,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站雀鹃,受9級(jí)特大地震影響幻工,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜黎茎,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,196評(píng)論 3 336
  • 文/蒙蒙 一囊颅、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧傅瞻,春花似錦踢代、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,698評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至掸读,卻和暖如春串远,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背儿惫。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,804評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工澡罚, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人肾请。 一個(gè)月前我還...
    沈念sama閱讀 49,287評(píng)論 3 379
  • 正文 我出身青樓留搔,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親铛铁。 傳聞我的和親對(duì)象是個(gè)殘疾皇子隔显,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,860評(píng)論 2 361