ninehills / blog Goto Github PK

http://sreweekly.com/sre-weekly-issue-83/

问题

https://leetcode.com/problems/search-in-rotated-sorted-array/description/
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

思路

• 顺序查找就不说了，最优解应该是二分查找的一个变种，主要是考虑边界条件

解答

package main

import "fmt"

// ----------------------
func search(nums []int, target int) int {
	var l int = 0
	var r int = len(nums) - 1
	if r < 0 {
		return -1
	}
	for l < r {
		m := (l + r) / 2
		if nums[m] == target {
			return m
		}
		if nums[m] >= nums[l] {
			if target < nums[m] && target >= nums[l] {
				r = m - 1
			} else {
				l = m + 1
			}
		} else {
			if target > nums[m] && target <= nums[r]{
				l = m + 1
			} else {
				r = m - 1
			}
		}
	}
	if nums[l] == target {
		return l
	} else {
		return -1
	}
}

// ----------------------

func main() {
	fmt.Println(search([]int{1, 3}, 0))
	fmt.Println(search([]int{}, 5))
	fmt.Println(search([]int{4, 5, 6, 7, 0, 1, 2}, 1))
	fmt.Println(search([]int{4, 5, 6, 7, 8, 1, 2, 3}, 8))
}

• https://www.bilibili.com/video/av7896615/
• https://zh.wikipedia.org/zh-hans/%E5%B0%91%E5%B9%B4%E5%8C%85%E9%9D%92%E5%A4%A9

童年阴影

进度：

• 名扬天下
• 血祭坛
• 隐逸村之迷
• 殿前扬威
• 五鼠闹相国
• 魔法幻影
• 翻龙劫

最近发现 GitHub 上有一个 repo： system-design-primer

最近几年工作也颇有几分心得，但是并没有一个系统性的整理。所以决定安排一个学习任务，看看自己和别人的思路是否有差距。

学习过程主要以看为主，利用碎片时间进行。学习进度，同步到这个Issue上。

问题

https://leetcode.com/problems/divide-two-integers/description/

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

思路

解答

问题

https://leetcode.com/problems/merge-k-sorted-lists/description/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

20170713

题目

https://leetcode.com/problems/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].

思路

• O(n)的思路其实使用Hash表，只需要查看target - num 对应的数字是否已经遍历过即可
• 实现的时候反向思考了下，在dict中注册了(target -num, value)，代码更加简洁

解答

class Solution(object):
    def twoSum1(self, nums, target):
        """最简单的办法，时间复杂度 O(n^2)
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for k,v in enumerate(nums):
            for i,j in enumerate(nums[k+1:]):
                if v + j == target:
                    return [k, i+k+1]

    def twoSum2(self, nums, target):
        """时间复杂度为 O(n)的办法：Runtime: 76 ms
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for k,v in enumerate(nums):
            if v not in d:
                d[target - v] = k
            else:
                return [d[v], k]

20170714

题目

https://leetcode.com/problems/add-two-numbers/

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

注意点：列表给的就是反序的，是342+465 = 807

思路

• 链表遍历，另外进位只可能进1，不可能进更多的数
• 注意增加了一个RootNode，用它的next放第一个节点
• 需要添加辅助的函数和类定义用来测试和debug

解答

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
        
    def __str__(self):
        return "Node({0}->[{1}])".format(self.val, self.next)

           
def init_list(l):
    before = None
    for i in l[::-1]:
        n = ListNode(i)
        n.next = before
        before = n
    return n

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0
        root = before = ListNode(None)
        while l1 or l2 or carry:
            v1 = v2 = 0
            if l1:
                v1 = l1.val
                l1 = l1.next
            if l2:
                v2 = l2.val
                l2 = l2.next
            z = v1 + v2 + carry
            if z >= 10:
                x = z - 10
                carry = 1
            else:
                x = z
                carry = 0
            node = ListNode(x)
            before.next = node
            before = node
        return root.next

# [7,0,8]
print Solution().addTwoNumbers(init_list([2,4,3]), init_list([5,6,4]))

问题

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]
]

思路

• 最基本的思路是将array求出全部子集，然后找匹配的结果并消重。用Python很容易计算而出，但是这种方法很明显会超出时间限制
• O(n^2)方法1: sort array，然后对每个元素，找匹配的三个元素，因为排序，所以相当于只有两次遍历
• O(n^2)方法2: 前两个元素两次循环，使用hash表，看第三个元素是否在hash表中（hash表中的元素为 0 - a-b）

参考： https://en.wikipedia.org/wiki/3SUM

解答

#coding=utf8
class Solution(object):
    def threeSumHash(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        d = {j: i for i,j in enumerate(nums)}
        ret = set()
        for i,j in enumerate(nums):
            for k,v in enumerate(nums[i+1:]):
                x = 0-j-v
                #print i,j,k,v
                if x in d and d[x] != i and d[x] != i+k+1:
                    ret.add(tuple(sorted([j, v, 0-j-v])))
        return list(ret)

    def threeSum(self, nums):
        """Sort"""
        nums.sort()
        ret = set()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i-1] == nums[i]:
                # 如果和前一位相等，直接忽略，避免重复结果
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                s = nums[l] + nums[r] + nums[i]
                if s == 0:
                    ret.add((nums[i], nums[l], nums[r]))
                    l = l + 1
                    r = r - 1
                elif s > 0:
                    r = r - 1
                else:
                    l = l + 1
        return list(ret)



print Solution().threeSum([0,0])
print Solution().threeSum([-1,0,1,2,-1,-4])
print Solution().threeSum([-2,0,0,2,2])

http://www.oreilly.com/webops-perf/free/chaos-engineering.csp?download=true

https://github.com/dastergon/awesome-chaos-engineering

in calibre

问题

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

思路

解答

问题

https://leetcode.com/problems/swap-nodes-in-pairs/description/

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

思路

思路就是循环换next，主要是处理边界条件

解答

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return "Node({0}->[{1}])".format(self.val, self.next)


def init_list(l):
    before = None
    for i in l[::-1]:
        n = ListNode(i)
        n.next = before
        before = n
    return n

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        root = ListNode(None)
        root.next = head
        head = root
        while head.next != None and head.next.next != None:
            n = head.next
            nn = n.next
            nnn = nn.next
            head.next = nn
            nn.next = n
            n.next = nnn
            head = head.next.next
        return root.next


print Solution().swapPairs(init_list([1,2,3,4,5]))

问题

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.

思路

解答

问题

https://leetcode.com/problems/reverse-nodes-in-k-group/description/

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

思路

两种思路都会遍历 n/k*2k = 2n次，时间复杂度都是O(n)，但是第二种的空间复杂度是O(k)

1. 先往后遍历确定是否可以倒序（剩余元素数是否小于k），如果可以，就两两互换
2. 顺序将k个元素存入数组，然后倒序（应该不符合Only constant memory is allowed.规则）

解答

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return "Node({0}->[{1}])".format(self.val, self.next)


def init_list(l):
    before = None
    for i in l[::-1]:
        n = ListNode(i)
        n.next = before
        before = n
    return n

class Solution(object):
    # from: https://discuss.leetcode.com/topic/31618/succinct-iterative-python-o-n-time-o-1-space
    def reverseKGroup(self, head, k):
        root = jump = ListNode(None)
        root.next = l = r = head
        while True:
            count = 0
            while r and count < k:
                r = r.next
                count += 1
            if count == k:
                pre, cur = r, l
                for _ in range(k):
                    cur.next, cur, pre = pre, cur.next, cur  # standard reversing
                jump.next, jump, l = pre, l, r  # connect two k-groups
            else:
                return root.next

    def reverseKGroup2(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        root = ListNode(None)
        root.next = head
        head = root
        while True:
            p = head
            tmp = []
            for i in range(k):
                if p.next == None:
                    return root.next
                tmp.append(p.next)
                p = p.next
            for i in range(k):
                if i == 0:
                    tmp[i].next = p.next
                else:
                    tmp[i].next = tmp[i-1]
            head.next = tmp[i]
            head = tmp[0]
        return root.next


print Solution().reverseKGroup(init_list([1,2,3,4,5]), 2)
print Solution().reverseKGroup(init_list([1,2,3,4,5]), 3)

https://en.wikipedia.org/wiki/The_Brink

中文名：《政局边缘》

起初是因为马亲王的安利才看的这部剧，一看就喜欢上了。
整部剧充斥着黑色幽默，可惜播出十集后惨遭腰斩，第二季也被取消续订，又一个萤火虫！-_-

问题

https://leetcode.com/problems/integer-to-roman/#/description

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

https://en.wikipedia.org/wiki/Roman_numerals

思路

罗马计数法看起来复杂，其实可以和十进制有个一一对应关系

解决

package main

import "fmt"

// ----------------------
func intToRoman(num int) string {
	r1 := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
	r2 := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
	r3 := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
	r4 := []string{"", "M", "MM", "MMM"}
	return fmt.Sprintf("%v%v%v%v", r4[num/1000], r3[num%1000/100], r2[num%100/10], r1[num%10])
}

// ----------------------

func main() {
	fmt.Println(intToRoman(90))
	fmt.Println(intToRoman(131))
	fmt.Println(intToRoman(13))
}

背景：Docker on Mac 长时间运行后，Docker.qcow2就会变得很大，需要压缩

参考：docker/for-mac#371

Author: yankcrime
NB: You'll need to install qemu via Homebrew as this process requires qemu-img to recompress the qcow2 disk image.

$ cd ~/Library/Containers/com.docker.docker/Data/com.docker.driver.amd64-linux
$ mv Docker.qcow2 Docker.qcow2.original
$ du -hs Docker.qcow2.original
12G     Docker.qcow2.original
$ qemu-img convert -O qcow2 Docker.qcow2.original Docker.qcow2
$ rm Docker.qcow2.original
$ du -hs Docker.qcow2
772M    Docker.qcow2

除此之外，还有一个根本解决问题的方法，就是不要在虚拟机内保存任何数据，全部使用Volume，这样当文件过大时，删除文件，重启Docker后，重新创建容器即可。

问题

https://leetcode.com/problems/3sum-closest/#/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).

思路

思路同3sum

解答

#coding=utf8
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        closest = 0
        ret = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i-1] == nums[i]:
                # 如果和前一位相等，直接忽略，避免重复结果
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                s = nums[l] + nums[r] + nums[i] - target
                if closest == 0 or abs(s) < closest:
                    closest = abs(s)
                    ret = (nums[l], nums[r], nums[i])
                if s == 0:
                    return target
                elif s > 0:
                    r = r - 1
                else:
                    l = l + 1
        print ret
        return ret[0] + ret[1] + ret[2]



print Solution().threeSumClosest([-1, 2, 1, -4], 1)
print Solution().threeSumClosest([0, 0, 0], 1)
print Solution().threeSumClosest([0, 1, 2], 3)

问题

https://leetcode.com/problems/longest-common-prefix/#/description

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

思路

两两对比找出最长的prefix字符串，然后顺序对比下去

解答

package main

import "fmt"

// ----------------------
func longestCommonPrefix(strs []string) string {
	common_prefix := ""
	for index, str := range strs {
		if index == 0 {
			common_prefix = str
			continue
		}
		common_prefix = getCommonPrefix(common_prefix, str)
	}
	return common_prefix
}

func getCommonPrefix(a string, b string) string {
	//fmt.Println(a, b)
	b_length := len(b)
	for index, char := range a {
		if index < b_length {
			//fmt.Println(index, byte(char), b[index])
			if byte(char) == b[index] {
				continue
			} else {
				return a[:index]
			}
		} else {
			return b
		}
	}
	return a
}

// ----------------------

func main() {
	var strs = []string{"MMMCMLXXXIX", "MMMCsd", "MMIDFSDF"}
	fmt.Println(longestCommonPrefix(strs))
	strs = []string{"", "b"}
	fmt.Println(longestCommonPrefix(strs))
	strs = []string{"b", "b"}
	fmt.Println(longestCommonPrefix(strs))
}

https://www.amazon.com/_/dp/1491917628

in calibre

问题

https://leetcode.com/problems/implement-strstr/description/
Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

思路

字符串子串搜索，两种思路：

1. 暴力查找，时间复杂度O(N*M)，原理比较简单的，就是循环比对
2. KMP算法

解答

今天登录 RMS 系统，意外的看到自己的五周年纪念日提示：

时光荏苒，五年就这么过去了，回想过去五年，有付出也有收获，由欣慰也有遗憾，有拼搏也有懈怠，有成长也有落后。乃至于连个人性格，都发生了剧烈的变化，虽然不能说有多成熟，但也足够在这个复杂世界立足。

人生没有多少五年，上一个五年我们有诸多的未了心愿，下一个五年能够顺心如意呢？

当勉之！

问题

https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

思路

刚开始以为就是算出去除重复后的长度，但是报wrong answer，看评论才知道要求同时修改list，思路为双指针法

解答

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i+1

a = [1,1,2,2,3,4]
print Solution().removeDuplicates(a)
print a

https://en.wikipedia.org/wiki/The_Expanse_(TV_series)

中文名：《苍穹浩瀚》《无垠的太空》《太空无垠》

最喜欢的硬科幻电视剧，想起了惨遭腰斩的《Firefly》

参考资料

• https://github.com/dastergon/postmortem-templates

问题

https://leetcode.com/problems/longest-valid-parentheses/description/
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

问题

https://leetcode.com/problems/next-permutation/description/

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

20170715

题目

https://leetcode.com/problems/longest-substring-without-repeating-characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路

本题刚开始没有想到有效的思路，只好看了下别人的实现，思路是『滑动窗口』：

顺序遍历字符串

• 如果字符已经出现过并且substring的起点在重复字符（含）之前，更新substring的起点到重复字符的后一位
• 其他情况下，用当前substring的长度和保存的max长度取max

解答

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        used = {}
        start = max_length = 0
        for index,value in enumerate(s):
            if value in used and start <= used[value]:
                start = used[value] + 1
            else:
                max_length = max(max_length, index - start + 1)
            used[value] = index
        return max_length
# 3
print Solution().lengthOfLongestSubstring("pwwkew")

20170716

问题

https://leetcode.com/problems/longest-palindromic-substring/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
Example:

Input: "cbbd"

Output: "bb"

思路

有O(n)的算法，以后参考：http://articles.leetcode.com/longest-palindromic-substring-part-ii/
目前看了提示后，采用下面的思路：

• 回文字符串的中心点两种『aba』以及『bb』，故可能有的回文字符串共计 2n -1个，n为字符串的长度
• 遍历字符串，对每个中心点找到其回文字符串的长度，取最大值
• 时间复杂度是O(n^2)，空间复杂度为O(1)

解答

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        longest_str = ""
        len_s = len(s)
        for index in range(len_s):
            # 以index为中心的最长回文
            l = r = index
            while (l >= 0) and (r < len_s):
                if s[l] == s[r]:
                    l = l - 1
                    r = r + 1
                    continue
                else:
                    break
            s1 = s[l+1:r]
            if len(s1) > len(longest_str):
                longest_str = s1
                
            # 以index+0.5为中心的最长回文
            l = index
            r = index + 1
            while (l >= 0) and (r < len(s)):
                if s[l] == s[r]:
                    l = l - 1
                    r = r + 1
                    continue
                else:
                    break
            if l + 1 < r and r <= len(s):
                s2 = s[l+1:r]
                if len(s2) > len(longest_str):
                    longest_str = s2
        return longest_str

print Solution().longestPalindrome('abbc')

https://book.douban.com/subject/4836601/

古代鬼故事考证，算是学术著作

进度：10%

问题

https://leetcode.com/problems/search-for-a-range/description/

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

思路

题目简单，直接遍历即可

解答

package main

import "fmt"

// ----------------------
func searchRange(nums []int, target int) []int {
	var i int = 0
	var r = []int{-1, -1}
	for i = 0; i < len(nums); i++ {
		if target == nums[i] {
			if r[0] == -1 {
				r[0] = i
				r[1] = i
			} else {
				r[1] = i
			}
		}
	}
	return r
}

// ----------------------

func main() {
	fmt.Println(searchRange([]int{5, 7, 7, 8, 8, 10}, 8))
}

问题

https://leetcode.com/problems/remove-element/description/

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

思路

思路和 #42 比较相似，也是采用双指针的方法，一个指针去遍历nums，另外一个指针原地更新array

解答

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        if not nums:
            return 0
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i

a = [1,1,2,1,3,1]
print Solution().removeElement(a, 1)
print a

题目

https://leetcode.com/problems/median-of-two-sorted-arrays/

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

思路

实际业务中，如果是Python3，那么由median函数，可以简单的按照如下的代码

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums1 = sorted(nums1 + nums2)
        import statistics
        return statistics.median(nums1)

然而时间复杂度为排序的时间复杂度，不满足要求

解答

问题

https://leetcode.com/problems/merge-two-sorted-lists/tabs/description
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

思路

解答

问题

https://leetcode.com/problems/generate-parentheses/
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路

两种思路，一种是递归，一种是动态规划

• 递归思路
  • 从n=2，很难推导出n=3；此时应该换个思路，我们找的其实是generateParenthesis(n, open)，其中n是闭合的括号对数目，open是没有闭合的右括号的数目（其实这里open左右都无所谓，假设所有没有闭合的都只有右括号）；最终我们找的只是open = 0 的特殊情况
  • 如果 n 等于 0 ，返回 [ ')' * open ]
  • 如果 open 等于 0 ，返回 ['('+x for x in generateParenthesis(n-1, 1)]，就是对所有『n-1个闭合括号对&1个右括号』的组合，都在最左侧加一个左括号
  • 如果 open 不为 0，应该是两种情况的组合
    • [')'+x for x in self.generateParenthesis(n, open-1)]，『n个闭合括号+ n-1个右括号』加一个最左侧的右括号
    • ['('+x for x in self.generateParenthesis(n-1, open+1)]，『n-1个闭合括号 + n +1 个右括号』加一个最左侧的左括号
• 动态规划，要想得到n对括号，那么应该有这么几步
  • 首先产生一对括号()
  • 括号里放0对括号，括号后放n-1对括号：'(' + parenthesis(0) + ')' + parenthesis(n-1)
  • 括号里放1对，括号后放 n-2对：'(' + parenthesis(1) + ')' + parenthesis(n-2)
  • .....以此类推，注意parenthesis(0) 为''
  • 括号里放n-1对括号，括号后放 0对：'(' + parenthesis(n-1) + ')' + parenthesis(0)

解答

递归思路（直接复制别人的代码）

class Solution:
    def generateParenthesis(self, n, open=0):
        if n == 0: return [')'*open]
        if open == 0:
            return ['('+x for x in self.generateParenthesis(n-1, 1)]
        else:
            return [')'+x for x in self.generateParenthesis(n, open-1)] + ['('+x for x in self.generateParenthesis(n-1, open+1)]

动态规划（更容易理解，也是复制别人的代码）

# https://discuss.leetcode.com/topic/28374/clean-python-dp-solution
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        dp = [[] for i in range(n + 1)]
        dp[0].append('')
        for i in range(n + 1):
            for j in range(i):
                dp[i] += ['(' + x + ')' + y for x in dp[j] for y in dp[i - j - 1]]
        return dp[n]

问题

https://leetcode.com/problems/4sum/tabs/description
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

思路

解答

20170720

问题

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

click to show spoilers.

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.

思路

回文数类似于 12321，或者 123321。两种思路：

• 转换数字到字符串后，进行判断
• 把数字逆序后，看看是否相等，相等就为回文数

解答

package main

import "fmt"

// ----------------------

func isPalindrome(x int) bool {
	if x < 0 {
		return false
	}
	xx := x
	y := 0
	for x != 0 {
		y = x%10 + y*10
		x = x / 10
	}
	if y == xx {
		return true
	} else {
		return false
	}
}

// ----------------------

func main() {
	fmt.Println(isPalindrome(123123123123123))
	fmt.Println(isPalindrome(922337203))
	fmt.Println(isPalindrome(-123))
	fmt.Println(isPalindrome(12521))
	fmt.Println(isPalindrome(125521))
}

问题

https://leetcode.com/problems/valid-parentheses/tabs/description

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

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

思路

使用stack的**，碰到({[就压栈，碰到)}]就出栈，出栈时栈空或者遍历结束后栈不为空，则not valid

解答

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        m = {'[': ']', '{': '}', '(': ')'}
        for c in s:
            if c in m:
                stack.append(c)
            else:
                if not stack:
                    return False
                else:
                    k = stack.pop()
                    if c == m[k]:
                        continue
                    else:
                        return False
        if not stack:
            return True
        else:
            return False


print Solution().isValid("[[[{{{{(((((())))))}}}}]]]")
print Solution().isValid("[{}[{{{{({{}}((((({{}}))))))}}}}]]]")

工作流引擎

20170718

问题

https://leetcode.com/problems/reverse-integer/

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

思路

• 一种想法是转换为字符串后反序
• 还有一种办法就是每次将x除以十取模后，在乘起来
• 至于overflow的判断，可以定义x为64bit整数，然后判断即可

解答

class Solution():
    def reverse(self, x):
        """第一种想法直接用库函数
        :type x: int
        :rtype: int
        """
        if x >= 0:
            ret = int(str(x)[::-1])
        else:
            ret = -1 * int(str(x)[:0:-1])
        if ret >= -1*2**31 and ret <= 2**31 - 1:
            return ret
        else:
            return 0

# -321
print(Solution().reverse(-10))

由于Python的%的实现方式是 -1 % 10 = 9，而不是 -1 % 10 = -1，我们取一个golang的例子

package main

import "fmt"

// ----------------------

func reverse(x int) int {
        var r int64 = 0
        var xx int64 = int64(x)
        for xx != 0 {
                r = r*10 + xx%10
                xx = xx / 10
        }
        const MaxInt = int32(^uint32(0) >> 1)
        const MinInt = -MaxInt - 1
        if r > int64(MaxInt) || r < int64(MinInt) {
                return 0
        } else {
                return int(r)

        }
}

// ----------------------

func main() {
        fmt.Println(reverse(123))
        fmt.Println(reverse(-234))
}

20170717

问题

https://leetcode.com/problems/zigzag-conversion/

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

思路

1. 第一种思路是初始化一个矩阵，然后根据之字形去填充这个矩阵，最后转换为字符串输出。时间复杂度为O(n)
2. 改进措施是没必要填充这个矩阵，因为空的元素没有意义，仅仅是分行append即可

解答

class Solution(object):
    def convert(self, s, numRows):
        """方案1
        :type s: str
        :type numRows: int
        :rtype: str
        """
        matrix = []
        for i in range(numRows):
            matrix.append([])
        row = 0
        row_add = 1
        column = 0
        for i in s:
            #print 'row: {0}'.format(row)
            #print 'column: {0}'.format(column)
            if column >= len(matrix[row]):
                matrix[row] = matrix[row] + [None] * (column - len(matrix[row]) + 1)
            matrix[row][column] = i
            if numRows == 1:
                row_add = 0
            else:
                if row == 0:
                    row_add = 1
                if row == numRows - 1:
                    row_add = -1
            row = row + row_add
            if row_add == -1 or row_add == 0:
                column = column + 1
                
        
        ret = ""
        #print matrix
        for r in matrix:
            for i in r:
                if i != None:
                    ret += i
        return ret
    def convert2(self, s, numRows):
        """方案2，更加精妙，来自于讨论区"""
        step = (numRows == 1) - 1  # 0 or -1  
        rows, idx = [''] * numRows, 0
        for c in s:
            rows[idx] += c
            if idx == 0 or idx == numRows-1: 
                step = -step  #change direction  
            idx += step
        return ''.join(rows)

# "PAHNAPLSIIGYIR"       
print Solution().convert("PAYPALISHIRING", 3)
# "AB"       
print Solution().convert("AB", 1)
# "ABC"       
print Solution().convert("AB", 1)

信息

https://book.douban.com/subject/26905142/

进度

20170723 - P154

书评

问题

https://leetcode.com/problems/roman-to-integer/#/description

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

罗马数字的定义参见： #19

思路

整数转罗马数用的是各位数字查表，罗马数转数字的时候，也有两种办法

• 识别千百十个位的罗马数，然后查表
• 只用识别单位的罗马字符，然后根据先后顺序加减

后者显然更简洁

解答

package main

import "fmt"

// ----------------------
func romanToInt(s string) int {
	romanChar := map[byte]int{
		'I': 1,
		'V': 5,
		'X': 10,
		'L': 50,
		'C': 100,
		'D': 500,
		'M': 1000,
	}
	ret := romanChar[s[len(s)-1]]
	for i := len(s) - 2; i >= 0; i-- {
		char := s[i]
		if romanChar[char] < romanChar[s[i+1]] {
			ret = ret - romanChar[char]
		} else {
			ret = ret + romanChar[char]
		}
	}
	return ret
}

// ----------------------

func main() {
	fmt.Println(romanToInt("MMMCMLXXXIX"))
}

问题：

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(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        digit_map = {
            '1': [''],
            '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'],
            '0': [' ']
        }
        old = set([''])
        for i in digits:
            new = set()
            for z in digit_map[i]:
                for k in old:
                    new.add(k + z)
            old = new
        return list(new)


print Solution().letterCombinations("23024")

问题

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

思路

解答

问题

https://leetcode.com/problems/remove-nth-node-from-end-of-list/tabs/description

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

思路

双指针：

• 先用root指针放到head之前，后续返回链表用
• first指针 从root往后走n步
• first, second 指针同时往后走，直到first到达链表尾部（first.next == None)，此时second.next 就是要去掉的Node
• 去掉second.next，然后返回root.next

解答

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return "Node({0}->[{1}])".format(self.val, self.next)


def init_list(l):
    before = None
    for i in l[::-1]:
        n = ListNode(i)
        n.next = before
        before = n
    return n

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        root = ListNode(None)
        root.next = head

        first = root
        second = root
        for i in range(n):
            first = first.next
        while first.next != None:
            first = first.next
            second = second.next
        second.next = second.next.next
        return root.next

print Solution().removeNthFromEnd(init_list([1,2,3,4,5]), 2)

https://leetcode.com/problemset/all/
参考：https://github.com/kamyu104/LeetCode

先列在这里，对自己没什么信心。

跟进表

20170719

问题

https://leetcode.com/problems/string-to-integer-atoi/#/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.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert... click to show requirements for atoi.

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.

思路

难点是边界处理，转整数的逻辑就是循环乘以10即可

解答

package main

import "fmt"

// ----------------------

const MaxInt = int32(^uint32(0) >> 1)
const MinInt = -MaxInt - 1

func myAtoi(str string) int {
	var r int64 = 0
	var tmp_r int64 = 0
	var flag int64 = 1
	var head bool = true
	for _, char := range str {
		if head {
			if char == ' ' {
				continue
			}
			if char == '-' {
				flag = -1
				head = false
				continue
			}
			if char == '+' {
				flag = 1
				head = false
				continue
			}
		}
		if char >= '0' && char <= '9' {
			head = false
			r = r*10 + (int64(char) - int64('0'))
			tmp_r = r * flag
			if tmp_r > int64(MaxInt) {
				return int(MaxInt)
			}
			if tmp_r < int64(MinInt) {
				return int(MinInt)
			}
		} else if head == false {
			break
		} else {
			return 0
		}
	}
	return int(r)
}

// ----------------------

func main() {
	fmt.Println(myAtoi("123123123123123"))
	fmt.Println(myAtoi("9223372036854775809"))
	fmt.Println(myAtoi("-123"))
	fmt.Println(myAtoi("43521"))
	fmt.Println(myAtoi("    010"))
}

信息

作者：王立铭
https://book.douban.com/subject/27025492/

购于Amazon Kindle，￥14.99 特价

进度

26% - 20170721

随笔

传统教育有一个非常扼杀思考能力的地方，就是直接给结论，陷入死记硬背的泥潭。而前辈们如何在信息如此不完全的情况下，依靠惊人的理性以及直觉，从混沌的未知中找到规律，这个过程被完全忽略了。
本书试图将我们拉回到那个达尔文、孟德尔的的伟大时代，让我们体会到在蛮荒之地开拓的感觉，让我们再一次为科学史上那些惊人壮举所惊讶。

en: https://github.com/0xAX/linux-insides
chs: https://github.com/MintCN/linux-insides-zh