leetcode 1-20 easy

1、Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].


思路：
关键词：一遍迭代map
建立map，迭代一遍数组，第一个迭代开始检查numToFind是否存在于map中。存在就返回两者的index；
不存在就把当前的数组nums[i]插入到map。重复迭代下去。

C++:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> hash_map;
        for(int i=0;i<nums.size();i++)
        {
            int numToFind=target-nums[i];
            if(hash_map.find(numToFind)!=hash_map.end())
            {
                res.push_back(i);
                res.push_back(hash_map[numToFind]);
                return res;
            }
            else
                hash_map[nums[i]]=i;
        }
        return res;
    }
};

python:

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        maps={}
        for i in range(len(nums)):
            if target-nums[i] in maps:
                return i,maps[target-nums[i]]
            else:
                maps[nums[i]]=i
        return -1,-1

7、Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

C++：

class Solution {
public:
    int reverse(int x) {
        long long res = 0;
        while(x) {
            res = res*10 + x%10;
            x /= 10;
        }
        return (res<INT_MIN || res>INT_MAX) ? 0 : res;
    }
};

python：

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        
        if x < 0:
            result = (0 - int(str(0-x)[::-1]))
            if result <= 2147483647 and result >= -2147483648:
                return result
            else:
                return 0
        else:
            result = int(str(x)[::-1])
            if result <= 2147483647 and result >= -2147483648:
                return result
            else:
                return 0

9、Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:

Coud you solve it without converting the integer to a string?

C++

//思路：反转后一样

class Solution {
public:
bool isPalindrome(int x) {
if(x<0|| (x!=0 &&x%10==0)) return false;
int sum=0;
int x1=x;
while(x)
{
sum = sum*10+x%10;
x = x/10;
}

return (x1==sum);
}
};

python

def isPalindrome(self, x):
    if x < 0:
        return False
    p, res = x, 0
    while p:
        res = res * 10 + p % 10
        p /= 10
    return res == x

14、Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.

C++

First one: check from strs[0][0] to strs[i][0]. If matches, check strs[0][1] to strs[i][1].
思路：ans由0开始添加前缀
Code:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
        return "";
        string ans="";
        int max=INT_MAX;
        for(auto& s:strs)
        {
            max=(max>s.length())?s.length():max;
        }
        for(int i=0;i<max;i++)
        {
            bool flag=true;
            char x=strs[0][i];
            for(auto& s:strs)
            {
                if(s[i]!=x)
                {
                    flag=false;
                    break;
                }
            }
            if(flag==false)
            return ans;
            ans+=x;
        }
        return ans;
    }
};

//////////////////////////////////////////////////

Second one: assume the prefix is strs[0]. Compair with strs[i], and cut the letters which don’t match.
ans由最小的串开始不断减少前缀
Code:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
        return "";
        string ans=strs[0];
        int max=INT_MAX;
        for(auto& s:strs)
        {
            if(s.length()==0)
            return "";
            int i=0;
            for(i=0;i<ans.length()&&i<s.length();i++)
            {
                if(s[i]!=ans[i])
                break;  //跳出整个循环
            }
            ans=ans.substr(0,i);
        }

        return ans;
    }
};

////////////////////////////////////

Third one: use a Trie data structure to save the strs. Search the trie, and stops when a TrieNode has more than one son.
数据结构trie
Code:

class TrieNode{
public:
    bool val;
    TrieNode* next[52];
    int sons;
    TrieNode() :val(false), sons(0)
    {
        for (int i = 0; i < 52; i++)
            next[i] = nullptr;
    }
};


class Trie{
private:
    TrieNode* putst(string& s, TrieNode * node, int loc, TrieNode *father)
    {
        if (s.length() == 0)
        {
            node->val = true;
            node->sons++;
            return node;
        }
        if (node == nullptr)
        {
            node = new TrieNode();
            if (father != nullptr)
                father->sons++;
        }
        if (loc == s.length())
        {
            node->val = true;
            return node;
        }
        if (s[loc] >= 'a')
            node->next[s[loc] - 'a'] = putst(s, node->next[s[loc] - 'a'], loc + 1, node);
        else
            node->next[s[loc] - 'A' + 26] = putst(s, node->next[s[loc] - 'A' + 26], loc + 1, node);
        return node;
    }
  
public:
    TrieNode *root;
    void insert(string & str){ putst(str, root, 0, nullptr); }
    Trie(){ root = new TrieNode(); }
};


class Solution {
private:
    string findPre(TrieNode * node)
    {
        if (node == nullptr || (node != nullptr&&node->sons > 1))
            return string("");
        int i = 0;
        for (i = 0; i < 52; i++)
        {
            if (node->next[i] != nullptr)
                break;
        }
        if (i == 52)
            return string("");
        char temp1 = ((i>25) ? ('A' + i) : ('a' + i));
        string temp;
        temp.insert(temp.begin(), temp1);
        if (node->val)
        {
            return string("");
        }
        else
        {
            return temp + findPre(node->next[i]);
        }
    }
  
public:
    string longestCommonPrefix(vector<string>& strs) {
        Trie a;
        for (auto& str : strs)
            a.insert(str);
        return findPre(a.root);
    }
};

python：good trick

def longestCommonPrefix(strs):
        if not strs:
            return ""
            
        for i, letter_group in enumerate(zip(*strs)): #返回所有字符串各自第一个元素组成的第一组元祖，例如（"a","a"）
            if len(set(letter_group)) > 1:
                return strs[0][:i]
        else:   #如果长度不一样，for在最短的字符串结束并跳到else
            return min(strs)

strs=["abcd","adef"]
print(longestCommonPrefix(strs))

同c++的第二种方法

 def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        shortest = min(strs,key=len)
        for i, ch in enumerate(shortest):
            for other in strs:
                if other[i] != ch:
                    return shortest[:i]
        return shortest

20、Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char& c : s) {
            switch (c) {
                case '(': paren.push(c); break;
                case '{': paren.push(c); break;
                case '[': paren.push(c); break;
                case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
                case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
                case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }
};

python

class Solution:
    def isValid(self, s):
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return stack == []