Leetcode 046 permutations

Posted on 2017-11-08 Edited on 2020-01-06 In leetcode

题目要求：

输入一组不重复的数字，输出全部可能的排列方式。例如，输入 [1,2,3] 输出
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。

思路：

可以采用深度优先搜索（DFS）的方式。如果输入数组长度为1，则直接返回该数组，否则，遍历数组，取出一个元素作为当前排列的第一位元素，然后对余下元素求全部排列，并附加到当前元素之后，可以用递归的方式简化程序。

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) <= 1:
            return [nums]
        solns = []
        for i, num in enumerate(nums):
            for tail in self.permute(nums[:i] + nums[i+1:]):
                solns.append([num] + tail)
        return solns

Leetcode 269 Alien Dictionary

Posted on 2017-10-31 Edited on 2020-01-06 In leetcode

题目要求：

一门外语由拉丁字母组成，但是他们的顺序和英语不一样。现有一个非空的单词列表，其中的单词已经根据该门外语的字母顺序排好序，尝试根据该列表推测字母顺序，输出字符串。当顺序中存在循环时输出空字符串，无法判明顺序的可以自由排列。

例如：

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

可以得到字母顺序："wertf"

思路：

可以采取拓扑排序，把整个字母顺序想象成一张有向图，字母是顶点，先后顺序是边（箭头）。先找到所有入度的顶点——即顺序最靠前的字母——放入栈，每次弹出一个字母放入字母顺序表。再找出排在他们之后的字母，将他们的入度减1，如果入度变为0了就将该字母也入栈，如此循环直至队列为空。

此时如果图中仍有边，则图中存在循环，无法拓扑排序，否则排序完成，得到字母顺序表。

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        if words is None or words == []:
            return ""
        chars = set().union(*map(set, words))
        outs = {c : set() for c in chars}
        indegrees = {c : 0 for c in chars}
        for i in range(len(words) - 1):
            before, after = words[i], words[i + 1]
            for j in range(min(len(before), len(after))):
                if before[j] != after[j]:
                    if after[j] not in outs[before[j]]:
                        indegrees[after[j]] += 1
                        outs[before[j]].add(after[j])
                    break

        q = [k for k, v in indegrees.items() if v == 0]
        soln = []
        while q:
            curr_char = q.pop()
            soln.append(curr_char)
            for next_char in outs[curr_char]:
                indegrees[next_char] -= 1
                if indegrees[next_char] == 0:
                    q.append(next_char)

        if max(indegrees.values()) > 0:
            return ""
        else:
            return "".join(soln)

Leetcode 681 Next Closest Time

Posted on 2017-10-29 Edited on 2020-01-06 In leetcode

题目要求：

输入为 HH:MM 格式表示的时间a，要求返回用组成时间a的数字组成的，a之后第一个时间b，可以重复使用数字，比a小的b被认为是第二天的时间。

思路：

利用 python 的 set 结构，获得组成时间的全部数字，并且不断对时间进行 +1 操作，直到遇到第一个组成数字是时间a的组成数字子集的时间b。一天只有 24 * 60 分钟因此程序运行时间可以保证。

class Solution(object):
    def nextClosestTime(self, time):
        """
        :type time: str
        :rtype: str
        """
        digits = set(time)
        while True:
            time = self.nextMinute(time)
            if set(time) <= digits:
                return time

    def nextMinute(self, time):
        h, m = map(int, time.split(':'))
        carry, m = divmod(m + 1, 60)
        h = (h + carry) % 24
        return "{:02d}:{:02d}".format(h, m)

Leetcode 008 String to Integer (atoi)

Posted on 2017-09-25 Edited on 2020-01-06 In leetcode

题目要求：

实现 atoi 函数，注意考虑各种可能情况。

思路：

可以直接采用正则表达式。先去掉首尾空格，行首可以有正负号也可以没有，之后接着一个或多个数字。匹配完成后，如果超过32位整数限制，则变成32位有符号整数的最大/最小值。

import re
class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        match = re.findall('^([+-]?\d+).*$', str)
        if match == []:
            num = 0
        else:
            num = int(match[0])
        if num >= 2 ** 31:
            num = (2 ** 31) - 1
        elif num <- 2 ** 31:
            num =- 2 ** 31
        return num

Leetcode 007 Reverse Integer

Posted on 2017-09-24 Edited on 2020-01-06 In leetcode

题目要求：

输入 x 为32位有符号整数，求按位反转的整数，如遇溢出则返回0

思路：

判断是0直接结束并返回0
判断是负数则 neg = True 并令 x = -x
因为64位 Python 不用担心32位整形溢出，可以初始化答案为0并不断加上 x 模10后乘10，直到 x == 0 为止，之后再判断是否超过32位整数最大值

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return x
        if x < 0:
            neg = True
            x = -x
        else:
            neg = False
        revx = 0
        while x > 0:
            revx = revx * 10 + x % 10
            x //= 10
        if len(bin(revx)[2:]) >= 32:
            return 0
        else:
            return -revx if neg else revx

Leetcode 006 ZigZag Conversion

Posted on 2017-09-23 Edited on 2020-01-06 In leetcode

题目要求：

输入字符串 s 和行数 numRows ，将字符串按照给定行数进行之字形重新纵向排列后再横向重新组织成字符串。以 s = "PAYPALISHIRING"， numRows = 3 为例，之字形排列后得到
P A H N
A P L S I I G
Y I R
重新排列后得到 "PAHNAPLSIIGYIR"。

思路：

个人认为这道题比较简单，首先判断当 numRows == 1 or numRows>=len(s) 时，无需处理，直接输出原始字符串即可。否则，遍历每一个字符，根据字符位置确定行号。确定方法为：

字符位置对 numRows * 2 - 1 取模 m，因为一个最小的 “ZigZag” 单元元素数实际上是行数两倍，少了两端的两行
当m小于行数时，表示当前 ZigZag 正处在下降阶段，直接在第 m 行尾附上当前字符即可
当 m 大于等于行数时，说明 ZigZag 正处在上升阶段，应在 -(m - numRows + 2) 即倒数 (m - numRows + 2) 行附加当前字符
将各行合并即得到最终输出

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1 or numRows > len(s):
            return s
        soln = [[] for i in range(numRows)]
        for i in range(len(s)):
            loc = i % (numRows * 2 - 2)
            if loc < numRows:
                soln[loc].append(s[i])
            else:
                soln[-(loc - numRows + 2)].append(s[i])
        return "".join(["".join(soln[i]) for i in range(numRows)])

Leetcode 005 Longest Palindromic Substring

Posted on 2017-09-20 Edited on 2020-01-06 In leetcode

题目要求

输入字符串 s 要求返回其中包含的长度最长的回文子字符串

思路：

朴素解法亦暴力解法即遍历所有子字符串，找到最长的回文字符串，效率低，不可取

优化：

验证回文字符串时不需要检验整个字符串，只需从两边向中间，发现不一样的字母即可判断不是回文；
因为只需返回最长的回文字符串，因此比当前最长回文字符串短的字符串均不需检验；
需要考虑长度为奇数/偶数的回文检验。

程序总体思路为：从左至右循环，每次检验到第 i 个字符为止的比当前最长回文字符串长度多 1 和 2 的字符串，如果是回文就更新当前最长回文及其长度，最后返回结果。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s is None or s == "":
            return ""
        if len(s) < 2:
            return s

        currLen = 0
        currStr = ""
        for i in range(len(s)):
            if self.isPalindrome(s, i - currLen - 1, i):
                currStr = s[i - currLen - 1 : i + 1]
                currLen += 2
            elif self.isPalindrome(s, i - currLen, i):
                currStr = s[i - currLen : i + 1]
                currLen += 1
                
        return currStr

    def isPalindrome(self, s, begin, end):
        if begin < 0:
            return False

        while begin < end:
            if s[begin] != s[end]:
                return False
            else:
                begin, end = begin + 1, end - 1

        return True

Leetcode 003 Longest Substring Without Repeating Characters

Posted on 2017-09-13 Edited on 2020-01-06 In leetcode

题目要求：

输入字符串 s 要求返回输入中不含重复字符的最长子字符串

思路：

朴素解法亦暴力解法即遍历所有子字符串，找到最长的无重复字符串，一共需要考察 O(n^2) 个字符串，效率较低。

优化：

采取动态规划策略。遍历一次字符串并且维护一个字典，记录每个遇到的字母最后一次出现的位置；以及两个变量，分别记录当前无重复字符串的开始位置和当前最长无重复字符串的位置。因为要求字符串无重复、无间断，因此遇到出现过的字母时，当前字符串的起始位置要变到上一次出现的位置之后。并且每遍历一个字母都更新一次当前、最大无重复字符串的长度。最后返回最大字符串长度。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        l = len(s)
        if l < 2:
            return l
        lastCharPos = {}
        maxStrLen = 0
        currStrStart = 0
        for i, ch in enumerate(s):
            if ch in lastCharPos and lastCharPos[ch] >= currStrStart:
                currStrStart = lastCharPos[ch] + 1
            lastCharPos[ch] = i
            maxStrLen = max(maxStrLen, i - currStrStart + 1)
        return maxStrLen

Leetcode 002 Add Two Numbers

Posted on 2017-09-13 Edited on 2020-01-06 In leetcode

题目要求：

输入为两个用单向链表表示的非负整数 l1 和 l2，整数在链表上由低位至高位进行储存，要求输出两个整数的和，同样以低位至高位的单向链表表示。

思路：

此题直接用手算加法的方式即可解决。输入的两个整数是由低位到高位储存的符合手算的顺序，题目中保证了输入非空也给我们提供了方便，不需要考察边界条件，计算时需维护一个“进位”的变量，并且要注意最后。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        solnHead = ListNode(None)
        carry = 0
        p = solnHead
        while l1 or l2 or carry:
            p.next = ListNode(carry)
            if l1:
                p.next.val += l1.val
                l1 = l1.next
            if l2:
                p.next.val += l2.val
                l2 = l2.next
            carry, p.next.val = divmod(p.next.val, 10)
            p = p.next
        return solnHead.next

Leetcode 001 Two Sums

Posted on 2017-09-10 Edited on 2020-01-06 In leetcode

题目要求：

输入为一个整数数组 nums 和一个整数 target ，要求返回 nums 中相加得到 target 的两个数的位置。可以假定输入数据存在唯一解。

思路：

朴素解法就是双重 for 循环，复杂度 O(n^2) 。

优化：

对于 nums 建立索引，key 是数值，value 是位置
对于 nums 中每个数求与 target 的差，如果差存在于索引中就可获得答案
要排除位置相同的数，如输入 [2, 1, 3], 4 则不应返回 [0, 0] 而应返回 [1, 2]
Python 中的 dict 按 key 查询是 O(1) 操作，因此整个算法复杂度为 O(N)

代码如下：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        index = {}
        for i, j in enumerate(nums):
            index[j] = i
        
        for i, j in enumerate(nums):
            if target - j in index and index[target - j] != i:
                return sorted([i, index[target - j]])