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;

}