[leetcode]第四部分

12-Integer to Roman

问题描述

一般使用7个不同的符号表示罗马数字:I,V,X,L,C,D,M,对应关系如下:

符号
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如,2使用罗马数字表示为“II,为21放在一起;12写作XII,为X+II27写作XXVII,为XX+V+II`。

罗马数字一般从左到右为从大到小的顺序。但是,4的数学表示不是IIII,而是IV,因为5前面的1表示减法。相同的原则也适用于数字9,表示为IX。下面有6中情形会使用到减法:

  • I可以放在V5)和X(10)前面得到49
  • X可以放在L50)和C(100)前面得到4090
  • C可以放在D500)和M(1000)前面得到400900

给定一个整数,将其转化为罗马数字,输入限定在03999的范围内。

示例1

Input: 3
Output: "III"

示例2

Input: 4
Output: "IV"

示例3

Input: 9
Output: "IX"

示例4

Input: 58
Output: "LVIII"

解析: C = 100, L = 50, XXX = 30 and III = 3.
示例5

Input: 1994
Output: "MCMXCIV"

解析: M = 1000, CM = 900, XC = 90 and IV = 4.

解题思路

最简单的想法:将对应的6种特殊情况也进行编码:

符号
IV 4
IX 9
XL 40
XC 90
CD 400
CM 900

把这些对应关系按照值的大小进行降序排列,然后用整数一个一个去除以该值,可以得到一个组成关系。

例如,示例 5中,1994的处理过程如下:
1994/1000=1 -> M -> 994
994/1000=0
994/900=1 -> CM -> 94
94/900=0 94/500=0 94/400=0 ...
94/90=1 -> XC -> 4
...
4/4 = 1 -> IV ->0

组合以下:MCMXCIV,问题解决。

代码

class Solution(object):
    symbolList = [{1000: "M"}, {900:"CM"}, {500:"D"}, {400:"CD"},{100:"C"}, {90:"XC"}, {50:"L"}, {40:"XL"},{10:"X"}, {9:"IX"}, {5:"V"}, {4:"IV"}, {1:"I"}]

    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        romanStr = ""
        for i in range(len(self.symbolList)):
            base, symbol = self.symbolList[i].items()[0]
            cnt = num / base
            for j in range(cnt):
                romanStr += symbol
            num = num % base
            if num == 0:
                break
        return romanStr

13-Roman to Integer

题干说明同上。

给定一个罗马数字,将其转化为一个整数。输入限定在13999的范围内。

示例1

Input: "III"
Output: 3

示例2

Input: "IV"
Output: 4

示例3

Input: "IX"
Output: 9

示例4

Input: "LVIII"
Output: 58

解析: C = 100, L = 50, XXX = 30 and III = 3.
示例5

Input: "MCMXCIV"
Output: 1994

解析: M = 1000, CM = 900, XC = 90 and IV = 4.

解题思路

同上一题,一共有13种不同的符号,因此可以从左往右遍历,先取两个字符,如果该字符串在符号集合里面,直接相加,并且向前移动2位;否则取一个字符,取出其对应值,加起来,向前移动1位。

例如,示例5中,对于MCMXCIV
MC -- M - 1000
CM - 900
XC - 90
IV - 4

全部相加,得到1994,问题解决。

代码

class Solution(object):

    symbolDict = {"M": 1000, "CM": 900, "D": 500, "CD":400, "C":100, "XC": 90, "L":50, "XL": 40, "X": 10, "IX":9, "V": 5, "IV": 4, "I": 1}

    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        idx = 0
        res = 0
        while idx < len(s):
            symbol = s[idx]
            if idx < len(s) - 1:
                if s[idx:idx+2] in self.symbolDict:
                    symbol = s[idx: idx+2]
                    idx += 1
            res += self.symbolDict[symbol]
            idx += 1
        return res

14-Longest Common Prefix

问题描述

写一个函数,找到字符串数组中最长的共同字符串前缀。

如果没有共同前缀,返回空字符串""

示例1

Input: ["flower","flow","flight"]
Output: "fl"

示例2

Input: ["dog","racecar","car"]
Output: ""

解析:在输入字符串中没有共同前缀。

注意:所有给定的输入都是小写的字符a-z

解题思路

分析下问题,找到字符串数组中最长的共同字符串前缀,其实可以简化为:找两个字符串的最长共同字符串前缀,后面再进行遍历;直到共同字符串前缀为空,或者到数组末端为止。

刚刚仔细看了下题目,发现这里计算的是公共前缀,所以很简单,针对两个字符串,只要从前往后遍历,碰到第一个不相同的字符就停止即可。

算法复杂度为:O(N*L),两个字符串比较的复杂度为O(L),其中L表示两个字符串中较短的字符串长度,而N表示数组的长度。

代码

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""
        preStr = strs[0]
        for i in range(1, len(strs)):
            nowStr = strs[i]
            if preStr == "":
                break
            preStr = self.longestCommonPrefixTwo(preStr, nowStr)
        return preStr



    def longestCommonPrefixTwo(self, str1, str2):
        """
        :type str1: str1 
        :type str2: str2
        :rtype: str
        """
        i = 0
        while i < len(str1) and i < len(str2):
            if str1[i] == str2[i]:
                i += 1
            else:
                break
        i -= 1
        if i >= 0:
            return str1[:i+1]
        else:
            return ""

15-3Sum

问题描述

给定一个n个整数的数组nums,找到在nums数组中是否有三个元素a,b,c,使得a+b+c=0。找到数组中所有的唯一三元组使得和为0

注意:返回值中不要包含重复的三元组。

示例

给定数组nums= [-1, 0, 1, 2, -1, -4]
返回结果如下:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

刚拿到这一题的时候立马想到之前有做过的2Sum,使用一个额外的字典来存储数字和下标的对应关系。其实这个题目也可以使用类似的解法。

先遍历一遍数组,使用一个字典记录数值和对应下标的关系;然后使用两个指针,分别指向前两个数(a,b),判断0-a-b是否在字典中,如果在的话,取出其下标,如果下标大于前两个数的下标,则找到一组满足条件的三元组。

注意:题干中还特地说明了不能出现重复的三元组,因此,这里我们需要去个重。因此,只需要新建一个重复字典来进行存储。

在这里,我想到了最笨的一种方法:如果三元组中两个数字重复,那么三元组必定会重复;因此针对每个已经存储的三元组对,我们将其对应的数字中的一个存储起来;如果下次再遇到该数字,判断下其对应的集合中是否已经有相同的其它数字即可,

代码

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        retList = list()
        idxDict = dict()
        dupDict = dict()
        for i in range(len(nums)):
            idxDict[nums[i]] = i
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                target = 0 - (nums[i] + nums[j])
                if target in idxDict:
                    targetIdx = idxDict[target]
                    if targetIdx > j :
                        if target in dupDict:
                            numSet = dupDict[target]
                            if nums[i] not in numSet and nums[j] not in numSet:
                                #print target, nums[i], nums[j], num
                                retList.append([nums[i], nums[j], nums[targetIdx]]) 
                                nowSet = set()
                                if nums[i] in dupDict:
                                    nowSet = dupDict[nums[i]]
                                nowSet.add(target)
                                dupDict[nums[i]] = nowSet
                                nowSet = set()
                                if nums[j] in dupDict:
                                    nowSet = dupDict[nums[j]]
                                nowSet.add(target)
                                dupDict[nums[j]] =  nowSet
                                nowSet = set()
                                if target in dupDict:
                                    nowSet = dupDict[target]
                                nowSet.add(nums[i])
                                dupDict[target] = nowSet
                        else:
                            #print nums[i],nums[j], target
                            retList.append([nums[i], nums[j], nums[targetIdx]])
                            nowSet = set()
                            if nums[i] in dupDict:
                                nowSet = dupDict[nums[i]]
                            nowSet.add(target)
                            dupDict[nums[i]] = nowSet
                            nowSet = set()
                            if nums[j] in dupDict:
                                nowSet = dupDict[nums[j]]
                            nowSet.add(target)
                            dupDict[nums[j]] =  nowSet
                            nowSet = set()
                            if target in dupDict:
                                nowSet = dupDict[target]
                            nowSet.add(nums[i])
                            dupDict[target] = nowSet
        return retList

16-3Sum Closet

问题描述

给定一个长度为n的数组nums和一个目标整数target,找到nums中的三个整数,使得他们的和最接近于target,返回这三个整数的和。可以假设每个输入只有一种解决方法。

示例

Input: nums = [-1, 2, 1, -4], target = 1
Output: 2

解题思路

直观想法是:使用三个指针,从前到后进行遍历,取得三个数的和与target的距离最小的那个即可,很明显,这样的方法,算法复杂度是O(N^3)

抱着试一试的心态提交,居然AC了…

代码

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) < 3:
            return None
        closet = target - (nums[0] + nums[1] + nums[2])
        if closet == 0:
            return target
        for i in range(len(nums)-2):
            for j in range(i+1, len(nums)-1):
                for k in range(j+1, len(nums)):
                    now = target - (nums[i] + nums[j] + nums[k])
                    if now == 0:
                        return target
                    if closet * closet > now * now:
                        closet = now
        return target - closet

17-Letter Combinations of a Phone Number

问题描述

给定一个包含从2-9数字的字符串,返回所有可能这些数组可能表达的数字组合。数字到字母的映射关系如下图所示(类似于手机按键)。注意:1不映射到任何字母。


示例

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

注意:虽然上面的答案是词典顺序,我们的答案可以是任何顺序,例如da

解题思路

拿到题目,第一感觉这是一道比较简单的题目,只要把数字和字母的映射关系存储起来,然后遍历给定的字符串就可以求解了。但是具体开始做的时候,却发现这种思路无法解决问题。

上面那种做法只适合做两两组合的问题,那么可以把这个题目进行分解,每次都计算一个数字和之前字母的组合。此时,算法复杂度为:O(N*4^N*4)

特别注意:当输入为空字符串的时候,返回空数组。

代码

class Solution(object):
    digitMap = {"2": ["a", "b", "c"],
                "3": ["d", "e", "f"],
                "4": ["g", "h", "i"],
                "5": ["j", "k", "l"],
                "6": ["m", "n", "o"],
                "7": ["p", "q", "r", "s"],
                "8": ["t", "u", "v"],
                "9": ["w", "x", "y", "z"]}

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits) == 0:
            return []
        letterList = [""]
        for i in range(len(digits)):
            digit = digits[i]
            letterList = self.aLetterCombination(digit, letterList)
        return letterList


    def aLetterCombination(self, digit, letterList):
        if digit in self.digitMap:
            retList = []
            nowLetterList = self.digitMap[digit]
            for i in range(len(nowLetterList)):
                for j in range(len(letterList)):
                    retList.append( letterList[j]+nowLetterList[i])
            return retList
        else:
            return letterList

18-4Sum

问题描述

给定一个包含n个数字的数组nums和一个整数target,在nums中是否四个元素a,b,c,d使得a+b+c+d=target?找到数组中所有和为target的单一四元组。

注意:返回的集合中必须不能包含重复的四元组。

示例

Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题思路

这种类型的题目其实可以转化为:给定三个数,找剩下的数中是否有等于target-a-b-c的即可。

这样的做法会出现有重复数组的情况,那么我们需要怎么去重呢?我们需要注意到:4Sum的时候有且仅有3个数字完全一样的情况才会全部数字都相同。

在这里,我们初步获得所有满足条件的数组后,再进行一遍过滤即可。但是此时算法复杂度很高,为O(N^3)

代码

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(nums) < 4:
            return []
        # init dict
        numberDict = dict()
        for i in range(len(nums)):
            numberDict[nums[i]] = i
        tmpList = list()
        for i in range(len(nums)-3):
            for j in range(i+1, len(nums)-2):
                for k in range(j+1, len(nums)-1):
                    sum = nums[i] + nums[j] + nums[k]
                    targetNum = target - sum
                    if targetNum in numberDict:
                        idx = numberDict[targetNum]
                        if idx > k:
                            tmpList.append([nums[i], nums[j], nums[k], targetNum])
        print tmpList
        retList = self.filter(tmpList)
        return retList

    def filter(self, tmpList):
        resList =  list()
        if len(tmpList) == 0:
            return tmpList
        resList.append(tmpList[0])
        for i in range(1, len(tmpList)):
            tmpData = tmpList[i]
            tmpData.sort()
            isSame = False
            for j in range(len(resList)):
                resData = resList[j]
                resData.sort()
                if resData == tmpData:
                    isSame = True
                    break

            if not isSame:
               resList.append(tmpData)
        return resList
打赏

mickey

记录生活,写给几十年后的自己。