Leetcode練習

Two Sum:

思路1：先看第一個元素和後面的元素有無和為所需整數，在看第二個元素和後面元素，一次類推，直到最後兩個元素

思路2：所需整數減去第一個元素後，在數組中find是否有相等的值，減去第二個元素後

Palindrome Number:

思路1：将 int 轉換為 string ,使用下标操作 string，依次判斷開頭和結尾的數字是否相同

思路2:将 int 翻轉過來，判斷和原始的是否相同

int 轉 string 為 string s =to_string(x)

Reverse Integer：

将一個32位的 int 型數字颠倒

思路1：将 int 翻轉過來，注意符号，可以先取絕對值，再翻轉，之後添加符号，注意翻轉後可能會出現超出範圍，是以翻轉後的中間值使用 long型

思路2：轉化為string，然後颠倒

32位 int 的範圍為 [ -pow(2,31) ,pow(2,31)-1]

Roman to Integer:

将一個羅馬數字變成阿拉伯數字

思路：周遊所有的羅馬數字加起來，然後判斷特定的幾種情況，減去 double 的1，10或者100

Longest Comman Prefix:

思路：設定一個中間變量，存儲最長字首，每次循環用這個中間變量和 string 元素做比較，不同就break，更新result，使得result等于中間變量

Valiad Parentheses:

有效括号

思路：将括号按順序 push 到 vector 中，碰到後括号判斷前一個是否比對，比對的話将 vector pop_back，注意判斷前括号多，後括号多或者第一個就是後括号的情況

string的每一個元素都是字元 char

Merge Two Sorted Lists

思路：按順序比較每一個節點，對每一個節點設定正确的 next 指針，将兩個連結清單連接配接成一個連結清單，最後傳回 頭節點

連結清單都是按節點操作

Remove Duplicates from Sorted Array

思路：判斷容器目前元素和下一個元素是否相同，不同的話就删除目前元素，注意容器使用 erase 函數會使容器的疊代器失效，在容器中删除或者添加元素都會使容器的疊代器失效。但是 erase 傳回下一個元素的疊代器是正常的，可以使用，疊代器失效會報錯，可能導緻記憶體洩漏

Remove Element

思路：類似于上面一題，判斷目前元素是否是等于需要删除的值，如果是，使用 erase 函數，注意疊代器就好

Implement strStr()

判斷字元串中是否有目标字元串

思路：先定位string 目前元素是否等于目标字元串的第一個值，如果相等，進入内循環，判斷目前元素之後的值，是否和目标字元串後面的相等，如果不等使用 break 跳出内循環

Climbing Stairs

遞歸方法

class Solution {
public:
    int climbStairs(int n) {
        int result=;
        if(n== ) return ;
        else if(n==) return ;
        else{
            result = climbStairs(n-)+climbStairs(n-);
        }
        return result;
    }
};
           

會産生很多分支，時間很慢

動态規矩填表法

class Solution {
public:
    int climbStairs(int n) {
        vector<int> result(n);
        result[]=;
        result[]=;
        for(int i=;i<n;i++){
            result[i]=result[i-]+result[i-];
        }
        return result[n-];
     }
};
           

或者隻定義兩個值，更新這兩個中間值

Longest Palindromic Substring

思路一：分兩種情況，第一種，周遊檢查aba 型的回文，再周遊檢查 abba型回文

思路二：遇到重複的值，跨過去，标記收尾，之後從重複的首尾，分别減加，判斷是否相同，周遊一遍就可以

String to Integer (atoi)

考慮多種情況

有空格的情況，符号的情況，數字越界的情況，無效輸入的情況

Container With Most Water

思路一：兩個循環周遊所有的元素，複雜度為O(N2)

思路二：左右兩邊同時逼近，移動高度小的那邊直到重合

證明：移動高的那邊，長度變小，高度變高，面積變小，高度變低，面積變小，隻有移動低的面積有可能會變大，是以每次移動低的

Integer to Roman

思路：根據羅馬數字的規律，從左到右排列，比如 MMM，代表3000，是以隻需要将[1000,900,500,400,100,90,50,40,10,9,5,4,1] 按順序排好，然後依次将目标值和清單中的值比較，實用貪心算法，每次選擇能表示的最大值，然後将字元連起來

貪心算法的步驟如下

Greedy(C) //C是問題的輸入集合即候選集合

{

S={ }; //初始解集合為空集

while (not solution(S)) //集合S沒有構成問題的一個解

{

x=select(C); //在候選集合C中做貪心選擇

if feasible(S, x) //推斷集合S中增加x後的解是否可行

S=S+{x};

C=C-{x};

}

return S;

}