松花皮蛋的黑板報
  • 分享在京東工作的技術感悟,還有JAVA技術和業內最佳實踐,大部分都是務實的、能看懂的、可復現的

掃一掃
關注公眾號

數據結構和算法精選(C++版)

博客首頁文章列表 松花皮蛋me 2019-03-24 15:20

代碼見:https://github.com/liangsonghua/algorithm

1.1 確定字符互異


請實現一個算法,確定一個字符串的所有字符是否全都不同。這里我們要求不允許使用額外的存儲結構。
思路:基于快速排序的partition,可以邊排序邊找重復

1.2 原串翻轉


請實現一個算法,在不使用額外數據結構和儲存空間的情況下,翻轉一個給定的字符串(可以使用單個過程變量)。

1.3 確定兩串亂序同構


給定兩個字符串,請編寫程序,確定其中一個字符串的字符重新排列后,能否變成另一個字符串。這里規定大小寫為不同字符,且考慮字符串重點空格。
思路:使用一個計數的數組來做

1.4 空格替換


請編寫一個方法,將字符串中的空格全部替換為“%20”。假定該字符串有足夠的空間存放新增的字符,并且知道字符串的真實長度(小于等于1000),同時保證字符串由大小寫的英文字母組成。

1.5 基本字符串壓縮


利用字符重復出現的次數,編寫一個方法,實現基本的字符串壓縮功能。比如,字符串“aabcccccaaa”經壓縮會變成“a2b1c5a3”。若壓縮后的字符串沒有變短,則返回原先的字符串。
思路:定義一個字符串數組用來放存在的字符和相應字符的數量

1.6 像素翻轉


有一副由NxN矩陣表示的圖像,這里每個像素用一個int表示,請編寫一個算法,在不占用額外內存空間的情況下(即不使用緩存矩陣),將圖像順時針旋轉90度。
思路:
第一步:先將矩陣以次對角線互換 (如果是逆時針則為主對角線)
第二步:交換第i行到第n-i-1行

1.7 壓縮空格


要求時間復雜度O(N)空間復雜度O(1)
思路: 定義兩個游標,如果當前不是空格就把該處的值賦值給前面

1.8 清除行列


請編寫一個算法,若MxN矩陣中某個元素為0,則將其所在的行與列清零。
思路:首先找到需要變為0的行和列號,
記錄在矩陣row和col中,若需要變為0則記為1,反之記為0,最后清零

1.9 翻轉子串


假定我們都知道非常高效的算法來檢查一個單詞是否為其他字符串的子串。請將這個算法編寫成一個函數,給定兩個字符串s1和s2,請編寫代碼檢查s2是否為s1旋轉而成,要求只能調用一次檢查子串的函數。
思路:s1拼接自己一次當作s3,s2如果是s1旋轉來的就必定是s3的子串

2.0 求鏈表中倒數第k個數


輸入一個鏈表,輸出該鏈表中倒數第k個結點。
思路:第一次遍歷鏈表,第一次求鏈表的長度length,第二次求第length-k+1個結點

2.1 訪問單個節點的刪除


實現一個算法,刪除單向鏈表中間的某個結點,假定你只能訪問該結點。

2.2 鏈表分割

編寫代碼,以給定值x為基準將鏈表分割成兩部分,所有小于x的結點排在大于或等于x的結點之前
思路一:小數鏈表和大數鏈表,最后完成后將兩鏈表連接,注意頭結點也有值
思路二:將鏈表的節點存放在數組中,進行快速排序的調整

2.3 鏈式A加B


有兩個用鏈表表示的整數,每個結點包含一個數位。這些數位是反向存放的,也就是個位排在鏈表的首部。編寫函數對這兩個整數求和,并用鏈表形式返回結果
思路:這里對于不同長度的數字,我們通過將較短的數字補0來保證每一位都能相加

2.4 回文鏈表


思路一:申請一個棧,將節點全部壓入,遍歷節點和彈出的節點對比
思路二:申請一個棧,用快指針和慢指針同時遍歷,慢指針遍歷時,將節點壓入棧中,當快指針走完,慢指針在中間,整個調整過程實際上是把左邊的節點折過來和右邊的比較
思路三:找到中間節點,右邊逆序調整,然后兩頭開始判斷

2.4.2 環形鏈表插值


有一個整數val,如何在節點值有序的環形鏈表中插入一個節點值為val的節點,并且保證這個環形單鏈表依然有序。給定鏈表的信息,及元素的值A及對應的nxt指向的元素編號同時給定val,請構造出這個環形鏈表,并插入該值

思路:如果val大于頭節點的值則更新頭節點,如果是中間位置,則需要防止斷鏈

2.4.3 鏈表的k逆序


有一個單鏈表,請設計一個算法,使得每K個節點之間逆序,如果最后不夠K個節點一組,則不調整最后幾個節點。例如鏈表1->2->3->4->5->6->7->8->null,K=3這個例子。調整后為,3->2->1->6->5->4->7->8->null。因為K==3,所以每三個節點之間逆序,但其中的7,8不調整,因為只有兩個節點不夠一組。
思路一:可以使用棧存儲k個節點,然后依次彈出
思路二:不使用棧,但是需要前一次調整后的最后一個節點指針下一組需要調整的最后一個節點

2.4.4 復雜鏈表的復制


輸入一個復雜鏈表(每個節點中有節點值,以及兩個指針,一個指向下一個節點,另一個特殊指針指向任意一個節點)。
思路:每個節點分別拷貝一個在其后面,然后讓原來的和拷貝random指向相對應的節點,最后分離

2.4.5 鏈表判環


如何判斷一個單鏈表是否有環?有環的話返回進入環的第一個節點的值,無環的話返回-1。如果鏈表的長度為N,請做到時間復雜度O(N),額外空間復雜度O(1)。
思路:快指針一次跳兩個,如果為NULL,則沒有環
有環時,當快指針和慢指針相遇時,讓快指針等于頭節點,
一次遍歷一個,慢指針一次遍歷一個,在進入環的第一個節點再次相遇

2.4.6 無環單鏈表判相交


現在有兩個無環單鏈表,若兩個鏈表的長度分別為m和n,請設計一個時間復雜度為O(n + m),額外空間復雜度為O(1)的算法,判斷這兩個鏈表是否相交
思路 遍歷兩個鏈表得到長度,然后長鏈表先走差值,一樣長時,再同步走,會同時到達相遇節點。
擴展: 有環單鏈表相交判斷,單鏈表相交判斷(注意結構,再結合鏈表判環和此題方法解即可)

2.5 集合棧


請實現一種數據結構SetOfStacks,由多個棧組成,其中每個棧的大小為size,當前一個棧填滿時,新建一個棧。該數據結構應支持與普通棧相同的push和pop操作。

2.6 用兩個棧實現隊列


用兩個棧來實現一個隊列,完成隊列的Push和Pop操作。 隊列中的元素為int類型。
思路:進時,棧2是否為空,不為空,則棧2元素倒回到棧1,出時,將棧1元素全部彈到棧2中,直到棧1為空。

2.7 雙棧排序


請編寫一個程序,按升序對棧進行排序(即最大元素位于棧頂),要求最多只能使用一個額外的棧存放臨時數據,但不得將元素復制到別的數據結構中。
思路:把numbers中的一個個元素拿出比較,放入臨時棧help中,如果新的元素比help中的小,
便把help中大的取出放入numbers中,壓入小的進help,再把大的從numbers取出壓入help。
最后把help全部元素放入numbers,返回numbers。

2.8 貓狗收容所


有家動物收容所只收留貓和狗,但有特殊的收養規則,收養人有兩種收養方式,第一種為直接收養所有動物中最早進入收容所的,第二種為選擇收養的動物類型(貓或狗),并收養該種動物中最早進入收容所的。
思路:維護兩個隊列,一個隊列存放放入的狗,一個隊列存放放入的貓,每次把動物放入隊列的時候,同時將一個遞增的序號放入隊列,這個序號就是一個時間序列

2.9 位運算_交換


請編寫一個算法,不用任何額外變量交換兩個整數的值
思路 結合率和交換率

3.0 位運算_比較


對于兩個32位整數a和b,請設計一個算法返回a和b中較大的。但是不能用任何比較判斷。若兩數相同,返回任意一個。
給定兩個整數a和b,請返回較大的數
思路 我們可以得到a-b的符號,根據該符號決定返回a或b

3.1 位運算_尋找奇數出現


有一個整型數組A,其中只有一個數出現了奇數次,其他的數都出現了偶數次,請打印這個數。要求時間復雜度為O(N),額外空間復雜度為O(1)。給定整形數組A及它的大小n,請返回題目所求數字。
思路 異或運算

3.2位運算_尋找奇數出現2


給定一個整型數組arr,其中有兩個數出現了奇數次,其他的數都出現了偶數次,找到這兩個數。要求時間復雜度為O(N),額外空間復雜度為O(1)
思路
比如出現奇數次的a,b
定義eO=0遍歷arr依次異或,結果為eO=a^b
因為a、b互異,所有eO不等于0,設eO的第k位為1
定義變量eOhasOne = 0;與arr中第k位為1的值進行依次異或,結果eOhasOne = a或eOhasOne =b
通過eO^eOhasOne求得另外一個數

3.3位運算_二進制小數


有一個介于0和1之間的實數,類型為double,返回它的二進制表示。如果該數字無法精確地用32位以內的二進制表示,返回“Error”。
思路 乘二取整,順序排列

3.4 數學基礎_加法運算替代


請編寫一個方法,實現整數的乘法、減法和除法運算(這里的除指整除)。只允許使用加號。
給定兩個正整數int a,int b,同時給定一個int type代表運算的類型,1為求a * b,0為求a / b,-1為求a - b。請返回計算的結果,保證數據合法且結果一定在int范圍內
思路
1. a*b:將問題轉換成|b|個a相加,或者|a|個b相加,最后根據a、b的符號確定返回值的符號。
2. a-b:轉化成a+[-b]補,而[b]補與[-b]補之間的轉換關系:連同符號位一起按位取反,再加1

3.5 動態規劃_最大子段和問題


N個整數組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的連續子段和的最大值。當所給的整數均為負數時和為0。
例如:-2,11,-4,13,-5,-2,和最大的子段為:11,-4,13。和為20

3.6 動態規劃_矩陣取值問題


一個N*N矩陣中有不同的正整數,經過這個格子,就能獲得相應價值的獎勵,從左上走到右下,只能向下向右走,求能夠獲得的最大價值

3.7 動態規劃_最大和子矩陣


有一個正整數和負整數組成的NxN矩陣,請編寫代碼找出元素總和最大的子矩陣。請嘗試使用一個高效算法。
思路: 將從第i行到第j行的每一行中相同列的加起來,可以得到一個一維數組如下: (ai1+……+aj1, ai2+……+aj2, ……,ain+……+ajn)
由此我們可以看出最后所求的就是此一維數組的最大子段和問題

3.8 動態規劃_最長公共子序列


我們有兩個字符串m和n,如果它們的子串a和b內容相同,則稱a和b是m和n的公共子序列。子串中的字符不一定在原字符串中連續。
例如字符串“abcfbc”和“abfcab”,其中“abc”同時出現在兩個字符串中,因此“abc”是它們的公共子序列。此外,“ab”、“af”等都是它們的字串。。

3.9 動態規劃_最長遞增子序列


對于一個數字序列,請設計一個復雜度為O(nlogn)的算法,返回該序列的最長上升子序列的長度,這里的子序列定義為這樣一個序列U1,U2…,其中Ui < Ui+1,且A[Ui] < A[Ui+1]。

4.0 動態規劃_最小編輯代價


對于兩個字符串A和B,我們需要進行插入、刪除和修改操作將A串變為B串,定義c0,c1,c2分別為三種操作的代價,請設計一個高效算法,求出將A串變為B串所需要的最少代價

4.1 字符串_全排列

4.2 字符串_移位


對于一個字符串,請設計一個算法,將字符串的長度為len的前綴平移到字符串的最后。

4.3 棧_下一個較大元素


現在我們有一個int數組,請你找出數組中每個元素的下一個比它大的元素。
給定一個int數組A及數組的大小n,請返回一個int數組,代表每個元素比他大的下一個元素,若不存在則為-1。保證數組中元素均為正整數。
思路: 從后往前維護一個棧,如果當前棧為空則直接入棧,不為空則彈出top,如果top元素大于當前元素則為較大元素;如果top元素小于當前元素,則繼續彈出直到-1或者大于當前元素

4.4 動態規劃和遞歸_魔術索引


在數組A[0..n-1]中,有所謂的魔術索引,滿足條件A[i]=i。給定一個不下降序列,元素值可能相同,編寫一個方法,判斷在數組A中是否存在魔術索引。請思考一種復雜度優于o(n)的方法。
思路:事實上,看到A[5]=3時按照二分查找的做法,我們需要遞歸搜索右半部分。不過,如搜索左半部分, 我們可以跳過一些元素,值遞歸搜索A[0]到A[3]的元素。A[3]是第一個可能成為魔術索引的元素。
綜上:我們得到一種搜索模式,先比較midIndex和midValue是否相同。然后,若兩者不同,則按如下方式遞歸搜索左半部分和右半部分。
左半部分:搜索索引從start到min(midIndex-1,midValue)的元素。
右半部分:搜索索引從max(midIndex+1,minValue)到end的元素。

4.5 數組_循環有序數組最小值


對于一個有序循環數組arr,返回arr中的最小值。有序循環數組是指,有序數組左邊任意長度的部分放到右邊去,右邊的部分拿到左邊來
思路::如果子數組是普通升序數組,則A[left]<a[right]。對于循環升序數組,a[left]>A[right]</a[right]。對于循環升序數組,a[left]>

4.6 數組_第一個缺失的整數


給定一個數組,找到從1開始,第一個不在數組中的正整數,如3,5,1,2,-3,7,14,8輸出4
思路::將找到的元素放到正確的位置上,如果最終發現某個元素一直沒有找到,則該元素即為所求
若A[i]=i,i加1,繼續比較后面的元素;
若A[i]<i或a[i]>N或A[i]=A[A[i]]則丟棄A[i];
若A[i]>i,則將A[A[i]]和A[i]交換</i或a[i]>

4.7 數組_荷蘭國旗問題


設有一個僅由紅白藍三種顏色的條塊組成的條塊序列。求一種時間復雜度O(n)的算法,使得這些條塊按紅、白、藍的順序排好,即排成荷蘭國旗的圖案。
思路::快速排序的partition的過程

4.8 數組_最大子數組和


給定一個數組A[0,…,N-1],求A的連續子數組,使得該子數組的和的最大,如數組1,-2,3,10,-4,7,2,-5,最大子數組:3,10,-4,7,2
思路::動態規劃 最優子問題

4.9 數組_最大間隔


給定整數數組A,求這N個數排序后的最大間隔,如1,7,14,9,4,13的最大間隔為4
思路::桶排序/hash映射
將N個數用間距(max-min)/(N-1)分成N-1個區間,則落在同一區間內的數不可能有最大間距,統計后一區間的最小值與前一個區間的最大值的差即可

5.0 二叉樹_遍歷打印


遞歸和非遞歸實現

5.1 二叉樹_根據前序和中序求中后序


思路::根據前序中序,構造二叉樹,后序遍歷二叉樹;后序遍歷最后一個結點即為根結點

5.2 二叉樹_層次遍歷


給定二叉樹的根結點root,請返回打印結果,結果按照每一層一個數組進行儲存,所有數組的順序按照層數從上往下,且每一層的數組內元素按照從左往右排列
思路::借助隊列,何時換行?
定義兩個指針last表示當前行的最右,nLast表示下一行的最右,當nLast==last時準備換行

5.3 二叉樹_二叉查找樹判斷


給定整數數組,判斷該數組有無可能是一顆二叉查找樹后序遍歷的結果.假定數組中沒有重復元素
思路::由于后序遍歷的最后一個元素為根結點,
根據該結點將數組分成前后兩段,使得前半段都小于根結點,后半段反之

5.4 二叉樹_平衡二叉樹判斷

5.5 二叉樹_完全二叉樹判斷


**思路: **如果當前節點沒有左孩子但是有右孩子,則return false; 如果當前節點并不是左右孩子都有,則孩子必須為子葉節點,否則return false

5.6 二叉樹_樹上最遠距離


從二叉樹的節點A出發,可以向上或者向下走,但沿途的節點只能經過一次,當到達節點B時,路徑上的節點數叫作A到B的距離。對于給定的一棵二叉樹,求整棵樹上節點間的最大距離。
給定一個二叉樹的頭結點root,請返回最大距離。保證點數大于等于2小于等于500.
思路:
情況A: 路徑經過左子樹的最深節點,通過根節點,再到右子樹的最深節點。
情況B: 路徑不穿過根節點,而是左子樹或右子樹的最大距離路徑,取其大者。

5.7 二叉樹_尋找錯誤結點


一棵二叉樹原本是搜索二叉樹,但是其中有兩個節點調換了位置,使得這棵二叉樹不再是搜索二叉樹,請找到這兩個錯誤節點并返回他們的值。保證二叉樹中結點的值各不相同。
給定一棵樹的根結點,請返回兩個調換了位置的值,其中小的值在前。
思路:第一次降序的較大值 第二次降序的較小值

5.8 二叉樹_折紙問題


請把紙條豎著放在桌?上,然后從紙條的下邊向上?對折,壓出折痕后再展 開。此時有1條折痕,突起的?向指向紙條的背?,這條折痕叫做“下”折痕 ;突起的?向指向紙條正?的折痕叫做“上”折痕。如果每次都從下邊向上? 對折,對折N次。請從上到下計算出所有折痕的?向。
給定折的次數n,請返回從上到下的折痕的數組,若為下折痕則對應元素為”down”,若為上折痕則為”up”

5.9 二叉樹_二叉樹的鏡像


操作給定的二叉樹,將其變換為源二叉樹的鏡像。
思路:改寫中序遍歷

6.0 二叉樹_樹的子結構


輸入兩顆二叉樹A,B,判斷B是不是A的子結構。
思路:第一步 在樹A中找到與B的根結點的值一樣的結點R
第二步再判斷樹A中以R為根結點的子樹是不是包含樹B一樣的結構

6.1 二叉樹_二叉搜索樹與雙向鏈表


輸入一棵二叉搜索樹,將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點,只能調整樹中結點指針的指向。
思路:
1.核心是中序遍歷的非遞歸算法。
2.修改當前遍歷節點與前一遍歷節點的指針指向

6.2 二叉樹_二叉搜索樹的第k個結點


二叉搜索樹的第k個結點
思路:給定一顆二叉搜索樹,請找出其中的第k大的結點。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按結點數值大小順序第三個結點的值為4。

6.3 查找和排序_數組中的逆序對


有一組數,對于其中任意兩個數組,若前面一個大于后面一個數字,則這兩個數字組成一個逆序對。請設計一個高效的算法,計算給定數組中的逆序對個數。
思路:歸并排序的思想

6.4 查找和排序_查找和為定值的兩個數


思路:兩頭掃

6.5 查找和排序_最短子數組


對于一個數組,請設計一個高效算法計算需要排序的最短子數組的長度。

6.7 查找和排序_堆排序

6.8 查找和排序_計數排序

6.9 圖_單詞變換問題word-ladder


Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end,
原題連接:https://leetcode.com/problems/word-ladder/
思路::隱式圖 廣度優先搜索 不需要事先建立圖本身

7.0 棧的逆序

7.1 數組_求最長可整合子數組的長度


先給出可整合數組的定義: 如果一個數組arr在排序之后,從最小值到最大值的順序中,每相鄰兩個數之間差的絕對值都為1,則arr為可整合數組。 例如: arr = {5,3,4,6,2},再排序之后為:{2,3,4,5,6},排序后符合每相鄰兩個數之間差的絕對值都為1,所以arr是可整合數組。 給定一個整形數組arr,請返回其中長度最大的可整合子數組的長度。
[5,0,1,2,4,3,9],最長可整合子數組為
[5,0,1,2,4,3],所以返回6
[6,7,3,0,1,2,4,7],最長可整合子數組為
3,0,1,2,4],所以返回5
要求:如果數組長度為N,時間復雜度請達到O(N^2)
思路:
可整合子數組沒有重復(一旦出現就沒有必要往右繼續找了)
最大值-最小值+1 = 長度
不應該陷入題目中可整合子數組的定義中

7.2 數組_未排序數組中累加和為給定值的最長子數組


思路:sum[i]+k = sum[j],則j-(i+1)的長度即為所求,我們利用一個哈希表記錄累加和sum[i]最早出現的位置

7.3 數組_最大子方陣


有一個方陣,其中每個單元(像素)非黑即白(非0即1),請設計一個高效算法,找到四條邊顏色相同的最大子方陣。
給定一個01方陣mat,同時給定方陣的邊長n,請返回最大子方陣的邊長。保證方陣邊長小于等于100。
測試樣例:
[[1,1,1],[1,0,1],[1,1,1]],3
返回:3
思路:
任何一個點的下方(包括自己)1的個數存于數組bottom[i][j]
任何一個點的右邊(包括自己)1的個數存于數組right[i][j]
數組分別往上和往左填充
檢驗四條邊顏色是否相同為時,往右或往下跳k個判斷1個數是否為k或為0個

7.4 數組_奇數位上都是奇數或者偶數位上都是偶數


給定一個長度不小于2的數組arr。 寫一個函數調整arr,使arr中要么所有的偶數位上都是偶數,要么所有的奇數位上都是奇數上。 要求:如果數組長度為N,時間復雜度請達到O(N),額外空間復雜度請達到O(1),下標0,2,4,6…算作偶數位,下標1,3,5,7…算作奇數位,例如[1,2,3,4]調整為[2,1,4,3]即可
思路:
每次與最后一個元素比較,如果為奇數,則與奇數位上交換,下標+2,如果為偶數,同理
奇偶位上的數依次填入

7.5 字符串_正則表達式匹配


請實現一個函數用來匹配包括’.’和’*’的正則表達式。模式中的字符’.’表示任意一個字符,而’*’表示它前面的字符可以出現任意次(包含0次)。 在本題中,匹配是指字符串的所有字符匹配整個模式。例如,字符串”aaa”與模式”a.a”和”ab*ac*a”匹配,但是與”aa.a”和”ab*a”均不匹配
思路:

1.有效性檢查:str不能有(.); pattern模式中前面必須有一個字符
2.情況分析:定義變量s[i]和p[i]表示從i位置到結尾的字符串
– 1) s[i],p[i]不相等時,而且P[i+1]!=*或者,則return false;

如果P[i+1]=*則s[i]與p[i+2]繼續比較

-2) s[i],p[i]相等時,如果p[i+1]=,比如s=xxxxzzzz,p=xyyyy
如果p[i+1]不等于*時,則i++

7.6 字符串_最短摘要生成算法


請設計并實現一個高效的最短摘要生成算法,該算法能找出S中包含所有T中的字符的最短子字符串,即最短摘要,如:
S=”ADOBECODEBANC”
T=”ABC”
最短摘要結果為”BANC”

7.7 數組_數組中出現次數超過一半的數字


思路: 同時刪掉兩個不同的數,眾數不變。
于是我們隨便記錄一個數x,
來一個數 y, 和x不同的話就把x ,y都扔了,=
相當于扔掉兩個不同的數,和x相同的話,就把計數器加1

7.8 數組_天平不平衡找假幣問題


Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.
Happily, Sally has a friend who loans her a very accurate balance scale. The friend will permit Sally three weighings to find the counterfeit coin. For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true. Now if Sally weighs
one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.
By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.
思路: 設置兩個數組: real[12]-標志為真 lh[12]–標志被懷疑
每次稱球的時候,如果是”even”則把對應的設置為”真東西”,即置為1,
如果是”up”或”donw” 則把表示輕重的數組lh對應的 ++ 或者 –,直到最后。

然后把所有對應real中為1(即就是真東西啦)的lh置為0;那么操作之后,
lh中存在沒有辨認出真的,就是一系列的例如: -1,-2,1,2,3等數值,那么
假東西就是其中絕對值最大的那個!!——被懷疑次數最多,所以它為假

7.9 字符串_把一個數字看成字符串,判斷是否為回文數


大家對回文串不陌生吧?一個字符串從前看和從后看如果一樣的話,就是回文串。比如“上海自來水來自海上”就是一個回文串。現在我們的問題來了,把一個數字看成字符串,問它是不是一個回文數?這么簡單的題目對想要成為小米工程師的你來說肯定不是問題。不過提醒一下哦:時間復雜度和空間復雜度越低的算法,得分越高。
示例:
12321 -> true
3 -> true
133434-> false
思路:通過計算得到數字前后對應位的數字

8.0 Trapping Rain Wate

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

https://leetcode.com/problems/trapping-rain-water/
思路:
一般做法:
water[i] = (min(max(arr[0….i]),max(i+1,……n))-arr[i]);
更好的做法: 見代碼

黑龙江6+1开奖结果查询