两数之和:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
count = {}
n = len(nums)
for i in range(n):
if target - nums[i] not in count:
count[nums[i]] = i
else:
return [i, count[target - nums[i]]]
return None
go 声明 map
// 1. make 声明
m := make(map[int]int)
// 2. 仅声明, 不可直接写入
var m map[int]int
两数之和(链表):
# 万能转换数组
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
if not l1:
return l2
if not l2:
return l1
num1 = ''
num2 = ''
while l1:
num1 += str(l1.val)
l1 = l1.next
while l2:
num2 += str(l2.val)
l2 = l2.next
# 原数字是逆序
num1 = int(num1[::-1])
num2 = int(num2[::-1])
res = num1 + num2
head = ListNode(res % 10)
ans = head
res //= 10
while res > 0:
node = ListNode(res % 10)
head.next = node
head = head.next
res //= 10
return ans
# 模拟
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head = ListNode()
cur = head
car = False
while l1 or l2 or car:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
cnt = val1 + val2 + 1 if car else val1 + val2
car = cnt >= 10
cur.next = ListNode(cnt % 10)
cur = cur.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return head.next
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{0, nil}
cur := head
car := false
for l1 != nil || l2 != nil || car {
v1, v2, sum := 0, 0, 0
if l1 != nil {v1, l1 = l1.Val, l1.Next}
if l2 != nil {v2, l2 = l2.Val, l2.Next}
if car {sum = v1 + v2 + 1}else{sum = v1 + v2}
car = sum >= 10
cur.Next = &ListNode{sum % 10, nil}
cur = cur.Next
}
return head.Next
}
在go里面, 声明一个结构体字面量有一个语法糖, 可以快速得到一个结构体的指针
p := &ListNode{Val: 3}
Q: 如果没有 &, 直接得到值不行吗?
A:不行, 结构体里面明确了 Next字段是一个指针, 所以必须使用指针才能连起来一个链表
无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l, r, n = 0, 1, len(s)
res = 1
max_res = 1
if n <= 1:
return n
count = set(s[l])
while r < n:
while s[r] in count:
count.remove(s[l])
l += 1
res -= 1
else:
count.add(s[r])
res += 1
max_res = max(max_res, res)
r += 1
return max_res
# 优化版
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l, n, res = 0, len(s), 1
if n <= 1:
return n
count = set()
for r, val in enumerate(s):
while val in count:
count.remove(s[l])
l += 1
count.add(val)
res = max(res, r - l + 1)
return res
# 跳左指针, 记录字符的最后一个出现位置
def lengthOfLongestSubstring(s: str) -> int:
last = {}
l = 0
best = 0
for r, ch in enumerate(s):
if ch in last and last[ch] >= l:
l = last[ch] + 1
last[ch] = r
best = max(best, r - l + 1)
return best
// 定位跳指针法
func lengthOfLongestSubstring(s string) int {
l, res := 0, 0
count := make(map[rune]int)
for r, val := range s {
index, ok := count[val]
if ok && index >= l{
l = index + 1
}
count[val] = r
res = max(res, r - l + 1)
}
return res
}
乘最多水的容器
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l, r = 0, len(height) - 1
res = 0
while l < r:
cur = (r - l) * min(height[l], height[r])
res = max(res, cur)
if height[l] > height[r]:
r -= 1
else:
l += 1
return res
func maxArea(height []int) int {
n := len(height)
l, r := 0, n - 1
res := 0
for l < r{
cur := min(height[l], height[r]) * (r - l)
res = max(res, cur)
if height[l] < height[r]{
l ++
}else{
r --
}
}
return res
}
罗马数字转整数
class Solution:
def romanToInt(self, s: str) -> int:
dic = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
s = s[::-1]
ans = dic[s[0]]
for i in range(1, len(s)):
if dic[s[i]] < dic[s[i - 1]]:
ans -= dic[s[i]]
else:
ans += dic[s[i]]
return ans
func romanToInt(s string) int {
dic := map[byte]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
n := len(s)
ans := dic[s[n - 1]]
for i := n - 2; i >= 0; i--{
if dic[s[i]] < dic[s[i + 1]] {
ans -= dic[s[i]]
}else {
ans += dic[s[i]]
}
}
return ans
}
最长公共前缀
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
min_len = len(strs[0])
min_ans = strs[0]
for i in strs:
if len(i) < min_len:
min_len = len(i)
min_ans = i
for i in range(min_len):
for j in range(len(strs)):
cur = strs[0][i]
if strs[j][i] != cur:
return strs[j][:i]
return min_ans
func longestCommonPrefix(strs []string) string {
minLen := len(strs[0])
minAns := strs[0]
for _, v := range strs{
if len(v) < minLen{
minLen = len(v)
minAns = v
}
}
for i := 0; i < minLen; i++{
for j := 0; j < len(strs); j++{
cur := strs[0][i]
if strs[j][i] != cur{
return strs[j][:i]
}
}
}
return minAns
}
大小为 k 且平均值大于分股阈值的子数组数目
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
n, tar = len(arr), k * threshold
if k > n:
return 0
cur = sum(arr[:k])
ans = 1 if cur >= tar else 0
for r in range(k, len(arr)):
l = r - k
cur -= arr[l]
cur += arr[r]
if cur >= tar:
ans += 1
return ans
# 优化版
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
n, tar = len(arr), k * threshold
cur = sum(arr[:k])
ans = int(cur >= tar)
for r in range(k, n):
l = r - k
cur += arr[r] - arr[l]
ans += int(cur >= tar)
return ans
字母异位词分组
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = {}
for i in strs:
list_i = list(i)
list_i.sort()
cur = "".join(list_i)
if cur not in ans:
ans[cur] = [i]
else:
ans[cur].append(i)
return list(ans.values())
# 优化版, defaultdict 在访问一个不存在的 key 时，会自动创建一个默认值，而不会报错。
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = defaultdict(list) # 入参为键不存在的时候的默认值
for i in strs:
cur = "".join(sorted(i))
ans[cur].append(i)
return list(ans.values())
经验
- 快读代替scan
reader := bufio.NewReader(os.Stdin)
line, err := reader.Readstrings(‘\n’)
// 注意go不能像py一样动态改变变量类型
fields := strings.Fields(line)
