Leetcode(17) Letter Combinations of a Phone Number

发表于 2018-03-19 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”

Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

解法：

迭代法解题，即依次读取字符串中的每位数字，然后把数字对应的字母依次加到当前的所有结果中，然后进入下一次迭代。代码如下：

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        d = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
        result = [];
        if(len(digits) == 0):
            return [];
        di = int(digits[0]);
        for j in range(len(d[di])):
            result.append(d[di][j]);
        i = 1;
        while(i< len(digits)):
            di = int(digits[i]);
            tmp = [];
            for x in result:
                for j in d[di]:
                    tmp.append(x + j);
            result = tmp;
            i+=1;
        return result;

Leetcode(16) 3Sum Closest

发表于 2018-03-19 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given an array _S_ of _n_ integers, find three integers in _S_ such that the sum is closest to a given number, target. Return the sum of the three integers.

You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解法：

同三数和的解法，用三个指针移动遍历各种可能性。代码如下：

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort();
        i = 0;
        dis = 233333333;
        while(i < len(nums) - 2):
            p = i + 1;
            q = len(nums) - 1;
            remain = target - nums[i];
            while(p<q):
                if(abs(remain - nums[p] - nums[q]) < dis):
                    dis = abs(remain - nums[p] - nums[q]);
                    result = nums[i] + nums[p] + nums[q];
                if(nums[p] + nums[q] == remain):
                    return target;
                elif(nums[p] + nums[q] < remain):
                    p+=1;
                else:
                    q-=1;
            i+=1;
        return result;

Leetcode(15) 3Sum

发表于 2018-03-08 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given an array _S_ of _n_ integers, are there elements _a_, _b_, _c_ in _S_ such that _a_ + _b_ + _c_ = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

解法：

参考：http://blog.csdn.net/u010656539/article/details/52204607

首先，两数和问题这样做。先对数组中的数进行排序，再设置两个指针，一个指向头，一个指向尾。判断两数和是否等于想要的数，如果是则在结果集添加这个数组；如果小了说明左边指针指向的数小了，因此左指针右移；反之如果大了则右指针左移。尝试把三数和问题转化为两数和问题：同样先对数组排序，设置三个指针p,q,r，p指针指向第一个数x，则q,r要指向数组中剩余数中的两个，并且指向的两数和为-x，从而转化为两数和问题。对p指向第一个数的情况分析完毕后，不可能再有满足题意且包含x的情况，于是p右移。这样一直分析到p指向数组中倒数第三个数的情况。注意跳过所有重复的情况。代码如下：

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort();
        res = [];
        i = 0;
        while(i<len(nums)-2):
            r = [];
            r.append(nums[i]);
            sum = 0 - nums[i];
            p = i + 1;
            q = len(nums) - 1;
            while(p<q):
                if(nums[p] + nums[q] == sum):
                    r.append(nums[p]);
                    r.append(nums[q]);
                    res.append(r);
                    r = [];
                    r.append(nums[i]);
                    p+=1;
                    q-=1;
                    while(p<q and nums[p] ==nums[p-1]):
                        p+=1;
                    while(p<q and nums[q] == nums[q+1]):
                        q-=1;
                elif(nums[p] + nums[q] < sum):
                    p+=1;
                else:
                    q-=1;
            while(i<len(nums)-2 and nums[i+1] == nums[i]):
                i+=1;
            i+=1;
        return res;

Leetcode(14) Longest Common Prefix

发表于 2018-03-06 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

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

解法：

暴力查找字符串集合中的相同前缀，将单词上下排好，相当于一个各行长度有可能不相等的二维数组，采用纵向逐列遍历，在遍历的过程中，如果某一行没有了，说明其为最短的单词，因为共同前缀的长度不能长于最短单词，所以此时返回已经找出的共同前缀。我们每次取出第一个字符串的某一个位置的单词，然后遍历其他所有字符串的对应位置看是否相等，如果有不满足的直接返回res，如果都相同，则将当前字符存入结果，继续检查下一个位置的字符，代码如下：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList();
        helper(root,output);
        return output;
    }
    void helper(TreeNode root,List<Integer> output){
        if(root == null){
            return;
        }
        helper(root.left,output);
        helper(root.right,output);
        output.add(root.val);
    }
}

Leetcode(13) Roman to Integer

发表于 2018-03-06 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

解法：

我们只要考虑两种情况即可：

第一，如果当前数字是最后一个数字，或者之后的数字比它小的话，则加上当前数字

第二，其他情况则减去这个数字

代码如下：

class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        d = {'I': 1 , 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D' : 500, 'M': 1000};
        res = 0;
        for i in range(len(s)):
            val = d[s[i]];
            if(i == len(s) - 1 or d[s[i]]>=d[s[i+1]]):
                res += val;
            else:
                res-=val;
        return res;

Leetcode(12) Integer to Roman

发表于 2018-03-06 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

解法：

参考：http://www.cnblogs.com/grandyang/p/4123374.html

转换法则如下：

基本字符	I	V	X	L	C	D	M
相应的阿拉伯数字表示为	1	5	10	50	100	500	1000

例如整数 1437 的罗马数字为 MCDXXXVII，我们不难发现，千位，百位，十位和个位上的数分别用罗马数字表示了。 1000 – M, 400 – CD, 30 – XXX, 7 – VII。

所以我们要做的就是用取商法分别提取各个位上的数字，然后分别表示出来：

100 – C

200 – CC

300 – CCC

400 – CD

500 – D

600 – DC

700 – DCC

800 – DCCC

900 – CM

我们可以分为四类，100到300一类，400一类，500到800一类，900最后一类。每一位上的情况都是类似的，代码如下：

class Solution:
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        roman = ['M', 'D', 'C', 'L', 'X', 'V', 'I'];
        value = [1000, 500, 100, 50, 10, 5, 1];
        i = 0;
        res = "";
        while(i<=6):
            x = int(num /value[i]);
            if(x < 4):
                for j in range(x):
                    res += roman[i];
            elif(x == 4):
                res += (roman[i] +roman[i-1]);
            elif( x > 4 and x < 9):
                res += roman[i - 1];
                for j in range(x - 5):
                    res += roman[i];
            else:
                res += roman[i] + roman[i-2];
            num %= value[i];
            i+=2;
        return res;

Leetcode(11) Container With Most Water

发表于 2018-03-06 | 更新于 2019-10-03 | 分类于 Leetcode刷题笔记

Description:

Given _n_ non-negative integers _a1_, _a2_, …, _an_, where each represents a point at coordinate (_i_, _ai_). _n_ vertical lines are drawn such that the two endpoints of line _i_ is at (_i_, _ai_) and (_i_, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and _n_ is at least 2.

解法：

参考：http://blog.csdn.net/a83610312/article/details/8548519

贪心法，证明过程如下：

1.首先假设我们找到能取最大容积的纵线为 i , j (假定i<j)，那么得到的最大容积 C = min( ai , aj ) * ( j- i) ；

2.下面我们看这么些性质：

①: 在 j 的右端没有一条线会比它高！假设存在 k |( j aj) ，那么由 ak> aj，所以 min( ai,aj, ak) =min(ai,aj) ，所以由i, k构成的容器的容积C’ = min(ai,aj ) * ( k-i) > C，与C是最值矛盾，所以得证j的后边不会有比它还高的线；

②:同理，在i的左边也不会有比它高的线；

这说明什么呢？如果我们目前得到的候选：设为 x, y两条线（x< y)，那么能够得到比它更大容积的新的两条边必然在 [x,y]区间内并且 ax’ > =ax , ay’>= ay;

③：所以我们从两头向中间靠拢，同时更新候选值；在收缩区间的时候优先从 x, y中较小的边开始收缩；

直观的解释是：容积即面积，它受长和高的影响，当长度减小时候，高必须增长才有可能提升面积，所以我们从长度最长时开始递减，然后寻找更高的线来更新候补；

代码如下：

class Solution {
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int res = 0;
        while(l<r){
            res = Math.max(res,Math.min(height[l],height[r])*(r-l));
            if(height[l]<height[r]){
                int k = l;
                while(height[k]<=height[l]&&k<r){
                    k++;
                }
                l = k;
            }
            else{
                int k = r;
                while(height[k]<=height[r]&&k>l){
                    k--;
                }
                r = k;
            }
        }
        return res;
    }
}

Leetcode(10) Regular Expression Matching

发表于 2018-03-04 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Implement regular expression matching with support for '.' and '*'. ‘.’ Matches any single character. ‘‘ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char \s, const char *p)
Some examples: isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true isMatch(“aaa”,”aa”) → false isMatch(“aa”, “a“) → true isMatch(“aa”, “.“) → true isMatch(“ab”, “.“) → true isMatch(“aab”, “c\a*b”) → true

解法：

此题的关键在于对‘’号的处理，因为不知道到底会匹配多少个字符，但是有一点，‘’不会单独出现，它一定是和前面一个字母或”.”配成一对。看成一对”X*”，它的性质就是：要不匹配0个，要不匹配连续的“X”，关键在于匹配正确个数的字符。

考虑一个特殊的问题：
情况1：
“aaaaaaaaaaaaaaaa”
“aaa”

情况2：
“aaaaaaaaaaaaaaaa”
“aab”

最长匹配？
显然不合适，这样后面的a就无法匹配上了

匹配到和后面长度一样的位置，比如情况1，就是留3个a不匹配，让后面3个字母尝试去匹配？
这样看似合适，但是遇到情况2就不行了。

回溯，每种匹配个数的情况，看哪种情况能成功，如果其中出现了问题，马上回溯，换下一种情况

因此，采用递归的方法解决该问题，用p去与s做匹配（即代码中判定以p为准），实际上也是深度优先搜索，对该问题的分解如下：

递归出口：

若p为空，对s而言：

若s也为空，返回true，反之返回false

若p的长度为1，对s而言：

若此时若s长度也为1，且s与p相同或是p为’.’，则返回true，反之返回false

递归体：

考虑该问题还未进行最小划分的情况，即此时p的长度大于1，对两串从左至右进行匹配。

情况1：若此时 p[1] !=’*’

1.1 如果s的长度为0，匹配失败，则返回false

1.2如果s[0] == p[0] 或 p[0] == ‘*’，匹配暂时成功，递归看看s与p的头指针向右移一位之后的串匹配是否成功

1.3否则匹配失败，返回false

情况2：此时的 p[1] == ‘*’

2.1当s的长度不为0且s[0] == p[0] 或 p[0] == ‘’时，暂时地匹配成功了，将s的头指针右移一位，进入下一次循环判断，值得注意的是，当匹配至p中’’后的串与此时遗留的s串相匹配时，不需要进行进一步的匹配了，两串完全匹配成功，返回true。

2.2剩下的情况即，s[0] != p[0] 且 p[0] ！= ‘’，则考虑此时X组合匹配0次，递归看看p中’*’后的串与此时遗留的s串是否匹配

我的代码：

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if(len(p) == 0):
            if(len(s) == 0):
                return True;
            return False;
        if(len(p) == 1):
            if(len(s) == 1):
                if(p[0] == '.' or s[0] == p[0]):
                    return True;
            return False;
        if(p[1] != '*'):
            if(len(s) == 0):
                return False;
            if(p[0] == s[0] or p[0] == '.'):
                return Solution.isMatch(Solution,s[1:],p[1:]);
            return False;
        #p[1] == '*'的情况
        while(len(s)!=0 and (s[0] == p[0] or p[0] == '.')):
            if(Solution.isMatch(Solution,s,p[2:])):
                return True;
            l = list(s[1:]);
            s = "".join(l);
        return Solution.isMatch(Solution,s,p[2:]);

Leetcode(9) Palindrome Number

发表于 2018-03-02 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1) If you are thinking of converting the integer to string, note the restriction of using extra space. You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case? There is a more generic way of solving this problem.

解法

主要掌握从一个数中取一部分的方法：求除数的方法

1 2	while(x/div>=10): div*=10;

取最右边的数

1	x = x % 10

取最左边的数

1	x = x/div;

取左部分

x = x /10

取右部分

1	x = x % div

我的代码

import math;
class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        div = 1;
        if(x<0):
            return False;
        while(x/div>=10):
            div*=10;
        while(x>0):
            right = x%10;
            left = x/div;
            left = math.floor(left);
            if(right != left):
                return False;
            x = (x%div)/10;
            x = math.floor(x);
            div/=100;
            div = math.floor(div);
        return True;

Leetcode(8) String to Integer (atoi)

发表于 2018-03-02 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

解法：

没啥好说的，输入为空格，+，- 或数字，出现 +，-后直接计数，如果已经非法则返回0.

字符串转数字的公式为：

1 2	x = int(str[i]); result = result * 10 + x;

我的代码：

class Solution:
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        i = 0;
        flag = 1;
        if(str == ""):
            return 0;
        while(str[i]==" "):
            i+=1;
            if(i == len(str)):
                return 0;
        result = 0;
        if(str[i]=="-" and i!=len(str)-1):
            if(str[i+1]!=" " and str[i+1] !="+" and str[i+1]!="-"):
                flag = -1;
                i+=1;
            else:
                return 0;
        if(str[i]=="+"and i!=len(str)-1):
            if(str[i+1]!=" " and str[i+1] !="+" and str[i+1]!="-"):
                flag = 1;
                i+=1;
            else:
                return 0;
        while(ord(str[i])>=48 and ord(str[i])<=57):
            x = int(str[i]);
            result = result * 10 + x;
            i+=1;
            if(i == len(str)):
                break;
        if(flag == -1):
            result = -result;
        if(result<-2147483648):
            return -2147483648;
        if(result >2147483647):
            return 2147483647
        return result;