0%

Posted on Edited on

题目要求：

输入链表的起始节点和整数n，需要去掉从链表结尾起第n个节点，然后返回新链表的起始节点。

思路：

用双指针方法确定位置，第一个指针先从头至尾移动n个节点，第二个指针开始移动，两个指针同步移动直至第一个指针到达链表尾部，第二个指针就到达了距离尾部距离n的节点，删除即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        placeHolder = ListNode(0)
        placeHolder.next = head
        p = q = placeHolder
        for i in range(n):
            p = p.next
        while p.next:
            p, q = p.next, q.next
        q.next = q.next.next
        return placeHolder.next

Posted on Edited on

题目要求：

输入整数数组和目标整数，求能使得和恰好为目标整数的所有四元组。

思路：

遍历两次全部二元组，第一次先创建一个所有二元组及其和的倒排索引，再第二次遍历，利用倒排索引查找相加之和等于当前二元组之和与目标之差的所有二元组，如果没有重复元素，则找到一个符合规则的四元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if nums is None:
            return []
        length = len(nums)
        solns = set()
        if length < 4:
            return []
        nums.sort()
        twoSums = {}
        for i in range(length):
            for j in range(i + 1, length):
                twoSum = nums[i] + nums[j]
                if twoSum in twoSums:
                    twoSums[twoSum].append([i, j])
                else:
                    twoSums[twoSum] = [[i, j]]
        for k in range(length):
            for l in range(k + 1, length):
                diff = target - nums[k] - nums[l]
                if diff in twoSums:
                    for ij in twoSums[diff]:
                        if ij[0] > l:
                            solns.add(tuple([nums[k], nums[l]] + 
                                            [nums[ij[0]], nums[ij[1]]]))
        return [list(soln) for soln in solns]

Posted on Edited on

题目要求：

给定电话号码键盘上输入的一组数字字符串，求对应按键上所有可能的字母组合。

思路：

采用迭代方法，当数字长度为1时，返回所有字母，否则对从第二个数字开始的字符串继续应用函数，把返回的字符串分别附加到第一个数字对应的字母后，组成字符串，加到答案中并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    letters = {'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 digits is None or digits == '':
            return []
        if len(digits) == 1:
            return self.letters.get(digits[0], [])
        solns = []
        if digits[0] in self.letters:
            for soln in self.letterCombinations(digits[1:]):
                for ch in self.letters[digits[0]]:
                    solns.append(ch + soln)
        else:
            for soln in self.letterCombinations(digits[1:]):
                solns.append(soln)
        return solns

Posted on Edited on

题目要求：

输入一个数组和一个目标整数，求一个数组中元素组成的三元组，使得三元组之和与目标整数最接近，返回该整数。

思路：

采用与015类似的方法，先对数组排序，i, j, k 为三元组所在位置， i 从左至右移动， j, k 在之后从两边向中间移动，同时记录和目标的差距，保留最优值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        MAXINT = 2 ** 31 - 1
        if nums is None:
            return MAXINT
        l = len(nums)
        if l < 3:
            return MAXINT
        nums.sort()
        minDiff = MAXINT
        minDiffSum = MAXINT
        for i in range(l - 2):
            if i and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, l - 1
            while j < k:
                test = nums[i] + nums[j] + nums[k]
                if test == target:
                    return target
                elif test < target:
                    j += 1
                else:
                    k -= 1
                if abs(target - test) < minDiff:
                    minDiff = abs(target - test)
                    minDiffSum = test
        return minDiffSum

Posted on Edited on

题目要求：

输入数组和，求出数组中所有不重复的三元组，使得三元组只和为0。

思路：

先对全部数组排序，假设三元组的对应的位置是 i, j, k ，令 i 从左至右循环，j, k 从 i 右侧的两边向中间循环。遇到和为0的三个元素则记录下并将 j, k继续向中间循环直至遇到不重复的元素，如和小于零则向右移动 j，否则向左移动 k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def threeSum(self, nums):
        if nums is None or nums == []:
            return []
        if len(nums) < 3:
            return []
        nums.sort()
        solns = []
        l = len(nums)
        for i in range(0, l - 2):
            if i and nums[i] == nums[i - 1]:
                continue
            j, k= i + 1, l - 1
            while j < k:
                test = nums[i] + nums[j] + nums[k]
                if test == 0:
                    soln = [nums[i], nums[j], nums[k]]
                    solns.append(soln)
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
                elif test > 0:
                    k -= 1
                else:
                    j += 1
        return solns

Posted on Edited on

题目要求：

从给定的一组字符串中，确定最长的公共前缀（LCP）。

思路：

先找出最短的字符串，然后从头开始测试每个字符，如果出现了最短字符串中的字符在其他字符串中相应位置没有出现的情况，该字符之前就是 LCP ，否则该最短字符串就是 LCP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    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

Posted on Edited on

题目要求：

输入大于0小于3999的罗马数字，输出相对应的整数。

思路：

结果初始化为0，从左至右每一位罗马数依次转换为整数，加至待输出的整数。除第一位以外，当前一位小于当前位时，再从结果中减去两倍的前一位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    romans = {'I' : 1,
              'V' : 5,
              'X' : 10,
              'L' : 50,
              'C' : 100,
              'D' : 500,
              'M' : 1000}
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        rlen = len(s)
        if rlen == 0:
            return 0
        intlst = []
        for i in range(rlen):
            intlst.append(self.romans[s[i]])
        if rlen == 1:
            return intlst[0]
        num = 0
        for i in range(rlen):
            if i == 0:
                num += intlst[0]
                continue
            if intlst[i] <= intlst[i-1]:
                num += intlst[i]
            else:
                num += intlst[i] - 2 * intlst[i - 1]
        return num

Posted on Edited on

题目要求：

输入大于0小于3999的整数，输出相对应的罗马数字。

罗马数字的拼写规则：

  • 重复数次：一个罗马数字重复几次，就表示这个数的几倍
  • 右加左减：
    • 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字
    • 在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字
    • 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
    • 但是，左减时不可跨越一个位值。比如，99不可以用IC表示，而是用XCIX表示。（等同于阿拉伯数字每位数字分别表示。）
    • 左减数字必须为一位，比如8写成VIII，而非IIX
    • 右加数字不可连续超过三位，比如14写成XIV，而非XIIII（见下方“数码限制”一项）
  • 数码限制：
    • 同一数码最多只能连续出现三次，如40不可表示为XXXX，而要表示为XL
    • 例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替IV

思路：

因为数字有上限3999，因此可以按1000、100、10、1为单位逐步转换，注意4和9的特殊情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num is None or num == 0:
            return ""
        integers = [1000, 100, 10, 1]
        romans = [['M'], ['C', 'D'], ['X', 'L'], ['I', 'V']]
        roman = []
        for i, j in enumerate(integers):
            if num < j:
                continue
            digit = num // j
            if digit < 4:
                for k in range(digit):
                    roman.append(romans[i][0])
            elif digit == 4:
                roman.append(romans[i][0])
                roman.append(romans[i][1])
            elif digit < 9:
                roman.append(romans[i][1])
                for k in range(digit - 5):
                    roman.append(romans[i][0])
            else:
                roman.append(romans[i][0])
                roman.append(romans[i - 1][0])
            num %= j
        return ''.join(roman)

Posted on Edited on

题目要求：

输入一个整数数组 height ，每个元素相当于一堵墙的高度，两堵墙之间距离为1，要求输出这些墙壁中能存住最多水的两堵墙

思路：

使用贪心法，从左右两端开始，计算最外侧两堵墙所能存住的水体积，并且每次放弃较矮的那堵墙，选择这一侧更靠近中心的下一堵墙继续尝试，直到两堵墙相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if height is None or len(height) < 2:
            return 0
        maxVol = 0
        left, right = 0, len(height) - 1
        while left < right:
            maxVol = max(maxVol, (right - left) * min(height[left], height[right]))
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return maxVol

Posted on Edited on

题目要求：

输入整数x，确定该整数是否为回文数。注：负数不算回文数。

思路：

翻转该整数，比较翻转后整数与x是否相等。可以在翻转前排出一些简单情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        elif x < 10:
            return True
        elif x % 10 == 0:
            return False
        else:
            resx = x
            revx = 0
            while resx:
                revx = revx * 10 + resx % 10
                resx //= 10
            return revx == x