ninehills / blog Goto Github PK
View Code? Open in Web Editor NEWHome Page: https://ninehills.tech
Home Page: https://ninehills.tech
童年阴影
进度:
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/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)
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)
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/
目前看了提示后,采用下面的思路:
2n -1
个,n为字符串的长度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')
背景:Docker on Mac 长时间运行后,Docker.qcow2就会变得很大,需要压缩
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/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"))
}
https://www.amazon.com/_/dp/1491917628
in calibre
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]))
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://en.wikipedia.org/wiki/The_Expanse_(TV_series)
中文名:《苍穹浩瀚》《无垠的太空》《太空无垠》
最喜欢的硬科幻电视剧,想起了惨遭腰斩的《Firefly》
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.
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))
}
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))
}
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"
.
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://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))
}
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].
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]
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.
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]
]
参考: 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])
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
两种思路,一种是递归,一种是动态规划
[ ')' * open ]
['('+x for x in generateParenthesis(n-1, 1)]
,就是对所有『n-1个闭合括号对&1个右括号』的组合,都在最左侧加一个左括号[')'+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 个右括号』加一个最左侧的左括号()
'(' + parenthesis(0) + ')' + parenthesis(n-1)
'(' + parenthesis(1) + ')' + parenthesis(n-2)
''
'(' + 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/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://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/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]
]
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/problemset/all/
参考:https://github.com/kamyu104/LeetCode
先列在这里,对自己没什么信心。
天 | 题目 |
---|---|
20170713 | #5 LeetCode-1. Two Sum |
20170714 | #6 LeetCode-2. Add Two Numbers |
20170715 | #7 LeetCode-3. Longest Substring Without Repeating Characters |
20170716 | #9 LeetCode-5. Longest Palindromic Substring |
20170717 | #13 LeetCode-6. ZigZag Conversion |
20170718 | #14 LeetCode-7. Reverse Integer |
20170719 | #15 LeetCode-8. String to Integer (atoi) |
20170720 | #16 LeetCode-9. Palindrome Number |
20170721 | #19 LeetCode-12. Integer to Roman |
20170722 | #20 LeetCode-13. Roman to Integer |
20170723 | #21 LeetCode-14. Longest Common Prefix |
20170724 | LeetCode-15. 3Sum #24 |
20170725 | LeetCode-16. 3Sum Closest #25 |
20170726 | LeetCode-17. Letter Combinations of a Phone Number #26 |
20170728 | LeetCode-19. Remove Nth Node From End of List #28 |
20170729 | LeetCode-20. Valid Parentheses #29 |
20170731 | LeetCode-22. Generate Parentheses #35 |
20170801 | LeetCode-24. Swap Nodes in Pairs #40 |
20170803 | LeetCode-26. Remove Duplicates from Sorted Array #42 |
20170804 | LeetCode-27. Remove Element #43 |
20170808 | LeetCode-35. Search Insert Position #51 |
20170818 | LeetCode-33. Search in Rotated Sorted Array #49 |
20170828 | LeetCode-357. Count Numbers with Unique Digits #53 |
https://en.wikipedia.org/wiki/The_Brink
中文名:《政局边缘》
起初是因为马亲王的安利才看的这部剧,一看就喜欢上了。
整部剧充斥着黑色幽默,可惜播出十集后惨遭腰斩,第二季也被取消续订,又一个萤火虫!-_-
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"))
}
工作流引擎
最近发现 GitHub 上有一个 repo: system-design-primer
最近几年工作也颇有几分心得,但是并没有一个系统性的整理。所以决定安排一个学习任务,看看自己和别人的思路是否有差距。
学习过程主要以看为主,利用碎片时间进行。学习进度,同步到这个Issue上。
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
Symbol | I | V | X | L | C | D | M |
---|---|---|---|---|---|---|---|
-- | 1 | 5 | 10 | 50 | 100 | 500 | 1,000 |
罗马计数法看起来复杂,其实可以和十进制有个一一对应关系
分位-数字 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
个位 | "" | I | II | III | IV | V | VI | VII | VIII | IX |
十位 | "" | X | XX | XXX | XL | L | LX | LXX | LXXX | XC |
百位 | "" | C | CC | CCC | CD | D | DC | DCC | DCCC | CM |
千位 | "" | M | MM | MMM |
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))
}
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.
字符串子串搜索,两种思路:
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/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/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.
双指针:
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)
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
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]))
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("[{}[{{{{({{}}((((({{}}))))))}}}}]]]")
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://book.douban.com/subject/27025492/
购于Amazon Kindle,¥14.99 特价
26% - 20170721
传统教育有一个非常扼杀思考能力的地方,就是直接给结论,陷入死记硬背的泥潭。而前辈们如何在信息如此不完全的情况下,依靠惊人的理性以及直觉,从混沌的未知中找到规律,这个过程被完全忽略了。
本书试图将我们拉回到那个达尔文、孟德尔的的伟大时代,让我们体会到在蛮荒之地开拓的感觉,让我们再一次为科学史上那些惊人壮举所惊讶。
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.
本题刚开始没有想到有效的思路,只好看了下别人的实现,思路是『滑动窗口』:
顺序遍历字符串
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")
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")
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/merge-k-sorted-lists/description/
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
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
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))
}
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
今天登录 RMS 系统,意外的看到自己的五周年纪念日提示:
时光荏苒,五年就这么过去了,回想过去五年,有付出也有收获,由欣慰也有遗憾,有拼搏也有懈怠,有成长也有落后。乃至于连个人性格,都发生了剧烈的变化,虽然不能说有多成熟,但也足够在这个复杂世界立足。
人生没有多少五年,上一个五年我们有诸多的未了心愿,下一个五年能够顺心如意呢?
当勉之!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.