力扣1-100题解
2023-12-13 05:50:40
本篇博客是用Go语言编写的详尽简洁代码，这里没有写算法思路，若要看具体思路，请移步力扣官网查看相关高赞题解。本篇博客的特点是代码简洁明了，包含多种写法，适合读者后期复盘巩固，加深理解。前一百题是面试高频题，建议读者认真阅读，背诵记忆。欢迎点赞+收藏+关注~~
LC1 两数之和
func twoSum(nums []int, target int) []int {
mp := map[int]int{}
for i, x := range nums {
y := target - x
if _, ok := mp[y]; ok {
return []int{mp[y], i}
}
mp[nums[i]] = i
}
return []int{}
}
LC2 两数相加
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{-1, nil}
cur := dummy
t := 0
for l1 != nil || l2 != nil || t != 0 {
if l1 != nil {
t += l1.Val
l1 = l1.Next
}
if l2 != nil {
t += l2.Val
l2 = l2.Next
}
cur.Next = &ListNode{t % 10, nil}
cur = cur.Next
t /= 10
}
return dummy.Next
}
LC3 无重复字符的最长子串
func lengthOfLongestSubstring(s string) int {
mp := map[byte]int{}
ans := 0
for l, r := 0, 0; r < len(s); r ++ {
mp[s[r]] ++
for mp[s[r]] > 1 {
mp[s[l]] --
l ++
}
ans = max(ans, r - l + 1)
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
LC4 寻找两个正序数组的中位数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
n, m := len(nums1), len(nums2)
tot := n + m
if tot & 1 != 0 {
return float64(getKth(nums1, 0, n - 1, nums2, 0, m - 1, tot / 2 + 1))
} else {
a := float64(getKth(nums1, 0, n - 1, nums2, 0, m - 1, tot / 2))
b := float64(getKth(nums1, 0, n - 1, nums2, 0, m - 1, tot / 2 + 1))
return (a + b) / 2.0
}
}
func getKth(nums1 []int, s1, e1 int, nums2 []int, s2, e2, k int) int {
l1, l2 := e1 - s1 + 1, e2 - s2 + 1
if l1 > l2 {
return getKth(nums2, s2, e2, nums1, s1, e1, k)
}
if l1 == 0 {
return nums2[s2 + k - 1]
}
if k == 1 {
return min(nums1[s1], nums2[s2])
}
i, j := s1 + min(k / 2, l1) - 1, s2 + min(k / 2, l2) - 1
if nums1[i] > nums2[j] {
return getKth(nums1, s1, e1, nums2, j + 1, e2, k - (j - s2 + 1))
} else {
return getKth(nums1, i + 1, e1, nums2, s2, e2, k - (i - s1 + 1))
}
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
LC5 最长回文子串
func longestPalindrome(s string) string {
n := len(s)
if n < 2 {
return s
}
ans := ""
for i := 0; i < n; i ++ {
l, r := i, i + 1
for l >= 0 && r < n && s[l] == s[r] {
l --
r ++
}
if r - l - 1 > len(ans) {
ans = s[l + 1 : r]
}
l, r = i - 1, i + 1
for l >= 0 && r < n && s[l] == s[r] {
l --
r ++
}
if r - l - 1 > len(ans) {
ans = s[l + 1 : r]
}
}
return ans
}
LC6 N字形变换
func convert(s string, n int) string {
if n < 2 {
return s
}
t := make([]string, n)
i, flag := 0, -1
for _, c := range s {
t[i] += string(c)
if i == 0 || i == n - 1 {
flag = -flag
}
i += flag
}
ans := ""
for _, v := range t {
ans += v
}
return ans
}
LC7 整数反转
func reverse(x int) int {
ans := 0
for x != 0 {
t := x % 10
if ans > 214748364 || (ans == 214748364 && t > 7) {
return 0
}
if ans < -214748364 || (ans == -214748364 && t < -8) {
return 0
}
ans = ans * 10 + t
x /= 10
}
return ans
}
LC8 字符串转换整数（atoi）
func myAtoi(s string) int {
k, ans, sign, n := 0, 0, 1, len(s)
for k < n && s[k] == ' ' {
k ++
}
if k == n {
return 0
}
if s[k] == '+' {
k ++
} else if s[k] == '-' {
sign = -1
k ++
}
for k < n && s[k] >= '0' && s[k] <= '9' {
t := int(s[k] - '0')
if sign == 1 && (ans > 214748364 || ans == 214748364 && t > 7) {
return math.MaxInt32
}
if sign == -1 && (-ans < -214748364 || -ans == -214748364 && t > 7) {
return math.MinInt32
}
ans = ans * 10 + t
t /= 10
k ++
}
return sign * ans
}
LC9 回文数
func isPalindrome(x int) bool {
if x < 0 || (x % 10 == 0 && x != 0) {
return false
}
y := 0
for x > y {
y = y * 10 + x % 10
x /= 10
}
return x == y || x == y / 10
}
LC10 正则表达式匹配
func isMatch(s string, p string) bool {
n, m := len(s), len(p)
s = " " + s
p = " " + p
f := make([][]bool, n + 1)
for i := 0; i <= n; i ++ {
f[i] = make([]bool, m + 1)
}
f[0][0] = true
for i := 0; i <= n; i ++ {
for j := 1; j <= m; j ++ {
if p[j] != '*' {
f[i][j] = i > 0 && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.')
} else {
f[i][j] = (j >= 2 && f[i][j - 2]) || (i > 0 && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'))
}
}
}
return f[n][m]
}
LC11 盛最多水的容器
func maxArea(h []int) int {
l, r, ans := 0, len(h) - 1, 0
for l < r {
ans = max(ans, min(h[l], h[r]) * (r - l))
if h[l] < h[r] {
l ++
} else {
r --
}
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
LC12 整数转罗马数字
type PIS struct {
Value int
Roman string
}
func intToRoman(num int) string {
mp := []PIS{
{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
{100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
{10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"},
}
ans := ""
for _, p := range mp {
for num >= p.Value {
num -= p.Value
ans += p.Roman
}
if num == 0 {
break
}
}
return ans
}
LC13 罗马数字转整数
func romanToInt(s string) int {
mp := map[byte]int{
'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000,
}
ans, n := 0, len(s)
for i := 0; i < n; {
if i + 1 < n && mp[s[i]] < mp[s[i + 1]] {
ans += mp[s[i + 1]] - mp[s[i]]
i += 2
} else {
ans += mp[s[i]]
i ++
}
}
return ans
}
LC14 最长公共前缀
func longestCommonPrefix(strs []string) string {
base, ans := strs[0], ""
for i := 0; i < len(base); i ++ {
for _, s := range strs {
if i >= len(s) || s[i] != base[i] {
return ans
}
}
ans += string(base[i])
}
return ans
}
LC15 三数之和
func threeSum(nums []int) [][]int {
n := len (nums)
ans := [][]int{}
if n == 0 || n < 3 {
return ans
}
sort.Ints(nums)
for i := 0; i < n - 2; i ++ {
if nums[i] > 0 {
break
}
if i > 0 && nums[i] == nums[i - 1] {
continue
}
if nums[i] + nums[i + 1] + nums[i + 2] > 0 {
break
}
if nums[i] + nums[n -1] + nums[n - 2] < 0 {
continue
}
l, r := i + 1, n - 1
for l < r {
s := nums[i] + nums[l] + nums[r]
if s < 0 {
l ++
} else if s > 0 {
r --
} else {
ans = append(ans, []int{nums[i], nums[l], nums[r]})
l ++
for l < r && nums[l] == nums[l - 1] {
l ++
}
r --
for l < r && nums[r] == nums[r + 1] {
r --
}
}
}
}
return ans
}
LC16 最接近的三数之和
func threeSumClosest(nums []int, target int) int {
n := len(nums)
sort.Ints(nums)
ans := nums[0] + nums[1] + nums[2]
for i := 0; i < n; i ++ {
l, r := i + 1, n - 1
for l < r {
s := nums[i] + nums[l] + nums[r]
if abs(s - target) < abs(ans - target) {
ans = s
}
if s < target {
l ++
} else if s > target {
r --
} else {
return ans
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
LC17 电话号码的字母组合
var (
s []string
ans []string
)
func dfs(digits string, u int, path string) {
if u == len(digits) {
ans = append(ans, path)
return
}
for _, c := range s[digits[u] - '0'] {
dfs(digits, u + 1, path + string(c))
}
}
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
s = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
ans = []string{}
dfs(digits, 0, "")
return ans
}
LC18 四数之和
func fourSum(nums []int, target int) [][]int {
n := len(nums)
ans := [][]int{}
if n == 0 || n < 4 {
return ans
}
sort.Ints(nums)
for i := 0; i < n - 3; i ++ {
if i > 0 && nums[i] == nums[i - 1] {
continue
}
for j := i + 1; j < n - 2; j ++ {
if j > i + 1 && nums[j] == nums[j - 1] {
continue
}
l, r := j + 1, n - 1
for l < r {
s := nums[i] + nums[j] + nums[l] + nums[r]
if s < target {
l ++
} else if s > target {
r --
} else {
ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
l ++
for l < r && nums[l] == nums[l - 1] {
l ++
}
r --
for l < r && nums[r] == nums[r + 1] {
r --
}
}
}
}
}
return ans
}
LC19 删除链表的倒数第N个结点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{-1, head}
slow, fast := dummy, dummy
for i := 0; i <= n; i ++ {
fast = fast.Next
}
for fast != nil {
slow = slow.Next
fast = fast.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
LC20 有效的括号
func isValid(s string) bool {
stk := []byte{}
for _, c := range s {
if c == '(' || c == '[' || c == '{' {
stk = append(stk, byte(c))
} else {
if len(stk) == 0 {
return false
}
x := stk[len(stk) - 1]
stk = stk[ : len(stk) - 1]
if c == ')' && x != '(' {
return false
}
if c == ']' && x != '[' {
return false
}
if c == '}' && x != '{' {
return false
}
}
}
return len(stk) == 0
}
LC21 合并两个有序链表
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{-1, nil}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
cur.Next =l1
cur = cur.Next
l1 = l1.Next
} else {
cur.Next = l2
cur = cur.Next
l2 = l2.Next
}
}
if l1 != nil {
cur.Next = l1
}
if l2 != nil {
cur.Next = l2
}
return dummy.Next
}
LC22 括号生成
var (
n, m int
ans []string
)
func dfs(u, lc int, seq string) {
if u == m {
ans = append(ans, seq)
return
}
if lc < n {
dfs(u + 1, lc + 1, seq + "(")
}
if u - lc < lc {
dfs(u + 1, lc, seq + ")")
}
}
func generateParenthesis(_n int) []string {
n, m = _n, 2*_n
ans = []string{}
dfs(0, 0, "")
return ans
}
LC23 合并K个升序链表
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
auto cmp = [](auto a, auto b) {
return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q;
for (int i = 0; i < lists.size(); ++ i)
if (lists[i])
q.push(lists[i]);
auto dummy = new ListNode(-1), cur = dummy;
while (q.size()) {
auto t = q.top(); q.pop();
cur = cur->next = t;
if (t->next) q.push(t->next);
}
return dummy->next;
}
};
LC24 两两交换链表中的节点
func swapPairs(head *ListNode) *ListNode {
n, k := 0, 2
for p := head; p != nil; p = p.Next {
n ++
}
dummy := &ListNode{-1, head}
p0 := dummy
var pre *ListNode
pre = nil
cur := head
for n >= k {
for i := 0; i < k; i ++ {
nxt := cur.Next
cur.Next = pre
pre = cur
cur = nxt
}
tmp := p0.Next
p0.Next.Next = cur
p0.Next = pre
p0 = tmp
n -= k
}
return dummy.Next
}
LC25 K个一组翻转链表
func reverseKGroup(head *ListNode, k int) *ListNode {
n := 0
for p := head; p != nil; p = p.Next {
n ++
}
dummy := &ListNode{-1, head}
p0 := dummy
var pre *ListNode
pre = nil
cur := head
for n >= k {
for i := 0; i < k; i ++ {
nxt := cur.Next
cur.Next = pre
pre = cur
cur = nxt
}
tmp := p0.Next
p0.Next.Next = cur
p0.Next = pre
p0 = tmp
n -= k
}
return dummy.Next
}
LC26 删除有序数组中的重复项
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
k := 0
for i := 0; i < len(nums); i ++ {
if i == 0 || nums[i] != nums[i - 1] {
nums[k] = nums[i]
k ++
}
}
return k
}
LC27 移除元素
func removeElement(nums []int, val int) int {
k := 0
for _, x := range nums {
if x != val {
nums[k] = x
k ++
}
}
return k
}
LC28 找出字符串中第一个匹配项的下标
func strStr(s string, p string) int {
if len(p) == 0 {
return 0
}
n, m := len(s), len(p)
s = " " + s
p = " " + p
ne := make([]int, m + 1)
ne[0] = 0
ne[1] = 0
for i, j := 2, 0; i <= m; i ++ {
for j > 0 && p[i] != p[j + 1] {
j = ne[j]
}
if p[i] == p[j + 1] {
j ++
}
ne[i] = j
}
for i, j := 1, 0; i <= n; i ++ {
for j > 0 && s[i] != p[j + 1] {
j = ne[j]
}
if s[i] == p[j + 1] {
j ++
}
if j == m {
return i - m
}
}
return -1
}
func strStr(s string, p string) int {
if len(p) == 0 {
return 0
}
n, m := len(s), len(p)
s = " " + s
p = " " + p
p += string(make([]byte, n + 1))
p = p[ : m + 1] + "#" + p[m + 2 : ]
ne := make([]int, n + m + 2)
for i := 1; i <= n; i ++ {
p = p[ : m + 1 + i] + string(s[i]) + p[m + 1 + i + 1 : ]
}
ne[0], ne[1] = 0, 0
for i, j := 2, 0; i <= n + m + 1; i ++ {
for j > 0 && p[i] != p[j + 1] {
j = ne[j]
}
if p[i] == p[j + 1] {
j ++
}
ne[i] = j
}
for i := m + 2; i <= n + m + 1; i ++ {
if ne[i] == m {
return i - 2 * m - 1
}
}
return -1
}
LC29 两数相除
func divide(a int, b int) int {
if a == 0 {
return 0
}
if a == math.MinInt32 && b == -1 {
return math.MaxInt32
}
if b == math.MinInt32 {
if a == b {
return 1
}
return 0
}
ans := 0
sign := ((a ^ b) < 0)
if a == math.MinInt32 {
a -= -abs(b)
ans ++
}
x, y := abs(a), abs(b)
for i := 31; i >= 0; i -- {
if x >> i >= y {
x -= y << i
if ans > math.MaxInt32 - (1 << i) {
return math.MinInt32
}
ans += 1 << i
}
}
if sign {
return -ans
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
LC30 串联所有单词的子串
func findSubstring(s string, words []string) []int {
ans := []int{}
if len(s) == 0 {
return ans
}
n, m, d := len(s), len(words), len(words[0])
mp := map[string]int{}
for _, x := range words {
mp[x] ++
}
for i := 0; i < d; i ++ {
wd := map[string]int{}
cnt := 0
for l, r := i, i; r < n - d + 1; r += d {
x := s[r : r + d]
wd[x] ++
cnt ++
for wd[x] > mp[x] {
y := s[l : l + d]
wd[y] --
cnt --
l += d
}
if cnt == m {
ans = append(ans, l)
}
}
}
return ans
}
LC31 下一个排列
func nextPermutation(nums []int) {
n, k := len(nums), len(nums) - 2
for k >= 0 && nums[k] >= nums[k + 1] {
k --
}
if k == -1 {
reverse(nums, 0, n - 1)
} else {
l, r := k + 1, n - 1
for l < r {
mid := (l + r + 1) >> 1
if nums[mid] > nums[k] {
l = mid
} else {
r = mid - 1
}
}
nums[k], nums[l] = nums[l], nums[k]
reverse(nums, k + 1, n - 1)
}
}
func reverse(nums []int, l, r int) {
for l < r {
nums[l], nums[r] = nums[r], nums[l]
l ++
r --
}
}
LC32 最长有效括号
func longestValidParentheses(s string) int {
n := len(s)
if n == 0 {
return 0
}
f := make([]int, n)
ans := 0
for i := 1; i < n; i ++ {
if s[i] == ')' {
if s[i] == '(' {
if i >= 2 {
f[i] = f[i - 2] + 2
} else {
f[i] = 2
}
} else {
if i - f[i - 1] - 1 >= 0 && s[i - f[i - 1] - 1] == '(' {
if i - f[i - 1] - 2 >= 0 {
f[i] = f[i - 1] + 2 + f[i - f[i - 1] - 2]
} else {
f[i] = f[i - 1] + 2
}
}
}
if f[i] > ans {
ans = f[i]
}
}
}
return ans
}
LC33 搜索旋转排序数组
func search(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
n, l, r := len(nums), 0, len(nums) - 1
for l < r {
mid := (l + r + 1) >> 1
if nums[mid] >= nums[0] {
l = mid
} else {
r = mid - 1
}
}
if target >= nums[0] {
l = 0
} else {
l, r = r + 1, n - 1
}
for l < r {
mid := (l + r) >> 1
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
if nums[r] == target {
return r
}
return -1
}
LC34 在排序数组中查找元素的第一个和最后一个位置
func searchRange(nums []int, target int) []int {
if len(nums) == 0 {
return []int{-1, -1}
}
n, l, r := len(nums), 0, len(nums) - 1
for l < r {
mid := (l + r) >> 1
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
if nums[l] != target {
return []int{-1, -1}
}
left := l
l, r = 0, n - 1
for l < r {
mid := (l + r + 1) >> 1
if nums[mid] <= target {
l = mid
} else {
r = mid - 1
}
}
return []int{left, r}
}
LC35 搜索插入位置
func searchInsert(nums []int, target int) int {
l, r := 0, len(nums)
for l < r {
mid := (l + r) >> 1
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
return l
}
LC36 有效的数独
func isValidSudoku(g [][]byte) bool {
var row, col, sub [9]int
for i := 0; i < len(g); i++ {
for j := 0; j < len(g[0]); j++ {
if g[i][j] != '.' {
k := int(g[i][j] - '0')
idx := (i / 3) * 3 + j / 3
if (row[i] & (1 << k)) != 0 ||
(col[j] & (1 << k)) != 0 ||
(sub[idx] & (1 << k)) != 0 {
return false
}
row[i] |= 1 << k
col[j] |= 1 << k
sub[idx] |= 1 << k
}
}
}
return true
}
LC37 解数独
var (
row, col, cell []int
)
func dfs(x, y int, g [][]byte) bool {
if y == 9 {
x ++
y = 0
}
if x == 9 {
return true
}
if g[x][y] == '.' {
for i := 1; i <= 9; i ++ {
idx := (x / 3) * 3 + y / 3
if row[x] & (1 << i) == 0 && col[y] & (1 << i) == 0 && cell[idx] & (1 << i) == 0 {
row[x] |= 1 << i
col[y] |= 1 << i
cell[idx] |= 1 << i
g[x][y] = byte(i) + '0'
if dfs(x, y + 1, g) {
return true
}
row[x] ^= 1 << i
col[y] ^= 1 << i
cell[idx] ^= 1 << i
g[x][y] = '.'
}
}
} else if dfs(x, y + 1, g) {
return true
}
return false
}
func solveSudoku(board [][]byte) {
row, col, cell = make([]int, 9), make([]int, 9), make([]int, 9)
for i := 0; i < 9; i ++ {
for j := 0; j < 9; j ++ {
if board[i][j] != '.' {
k := int(board[i][j] - '0')
row[i] |= 1 << k
col[j] |= 1 << k
cell[(i / 3) * 3 + j / 3] |= 1 << k
}
}
}
dfs(0, 0, board)
}
LC38 外观数列
func countAndSay(n int) string {
ans := "1"
for i := 0; i < n - 1; i ++ {
var t string
for j, k := 0, 1; j < len(ans); j = k {
for k < len(ans) && ans[k] == ans[j] {
k ++
}
t += strconv.Itoa(k - j) + string(ans[j])
}
ans = t
}
return ans
}
LC39 组合总和
var (
c, path []int
ans [][]int
)
func dfs(start, sum, target int) {
if sum == target {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
return
}
for i := start; i < len(c) && sum + c[i] <= target; i ++ {
sum += c[i]
path = append(path, c[i])
dfs(i, sum, target)
sum -= c[i]
path = path[ : len(path) - 1]
}
}
func combinationSum(candidates []int, target int) [][]int {
c = candidates
ans, path = make([][]int, 0), make([]int, 0, len(c))
sort.Ints(c)
dfs(0, 0, target)
return ans
}
LC40 组合总和II
var (
c, path []int
ans [][]int
)
func dfs(start, sum, target int) {
if sum == target {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
return
}
for i := start; i < len(c) && sum + c[i] <= target; i ++ {
if i > start && c[i] == c[i - 1] {
continue
}
sum += c[i]
path = append(path, c[i])
dfs(i + 1, sum, target)
sum -= c[i]
path = path[ : len(path) - 1]
}
}
func combinationSum2(candidates []int, target int) [][]int {
c = candidates
ans, path = make([][]int, 0), make([]int, 0, len(c))
sort.Ints(c)
dfs(0, 0, target)
return ans
}
LC41 缺失的第一个正数
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i ++ {
for nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1] {
nums[i], nums[nums[i] -1] = nums[nums[i] - 1], nums[i]
}
}
for i := 0; i < n; i ++ {
if nums[i] != i + 1 {
return i + 1
}
}
return n + 1
}
LC42 接雨水
func trap(h []int) int {
l, r, lm, rm, ans := 0, len(h) -1, 0, 0, 0
for l < r {
lm = max(lm, h[l])
rm = max(rm, h[r])
if lm < rm {
ans += lm - h[l]
l ++
} else {
ans += rm - h[r]
r --
}
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func trap(h []int) int {
stk := []int {}
ans := 0
for i := 0; i < len(h); i ++ {
for len(stk) > 0 && h[stk[len(stk) - 1]] < h[i] {
mid := stk[len(stk) - 1]
stk = stk[ : len(stk) - 1]
if len(stk) == 0 {
break
}
height := min(h[stk[len(stk) - 1]], h[i]) - h[mid]
width := i - stk[len(stk) - 1] - 1
ans += height * width
}
stk = append(stk, i)
}
return ans
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
LC43 字符串相乘
func multiply(num1 string, num2 string) string {
A, B := []int{}, []int{}
n, m := len(num1), len(num2)
for i := n - 1; i >= 0; i -- {
A = append(A, int(num1[i] - '0'))
}
for i := m - 1; i >= 0; i -- {
B = append(B, int(num2[i] - '0'))
}
C := make([]int, n + m)
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
C[i + j] += A[i] * B[j]
}
}
for i, t := 0, 0; i < len(C); i ++ {
t += C[i]
C[i] = t % 10
t /= 10
}
k := len(C) - 1
for k > 0 && C[k] == 0 {
k --
}
ans := ""
for k >= 0 {
ans += string(C[k] + '0')
k --
}
return ans
}
LC44 通配符匹配
func isMatch(s string, p string) bool {
n, m := len(s), len(p)
s = " " + s
p = " " + p
f := make([][]bool, n + 1)
for i := 0; i <= n; i ++ {
f[i] = make([]bool, m + 1)
}
f[0][0] = true
for i := 0; i <= n; i ++ {
for j := 1; j <= m; j ++ {
if p[j] == '*' {
f[i][j] = f[i][j - 1] || (i > 0 && f[i - 1][j])
} else {
f[i][j] = i > 0 && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?')
}
}
}
return f[n][m]
}
LC45 跳跃游戏II
func jump(nums []int) int {
n := len(nums)
f := make([]int, n)
f[0] = 0
for i, j := 1, 0; i < n; i ++ {
for j < n && j + nums[j] < i {
j ++
}
f[i] = f[j] + 1
}
return f[n - 1]
}
LC46 全排列
var (
st []bool
ans [][]int
a, path []int
)
func dfs(u int) {
if u == len(a) {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
return
}
for i := 0; i < len(a); i ++ {
if !st[i] {
path = append(path, a[i])
st[i] = true
dfs(u + 1)
st[i] = false
path = path[ : len(path) - 1]
}
}
}
func permute(nums []int) [][]int {
a = nums
n := len(nums)
st = make([]bool, n)
ans, path = make([][]int, 0), make([]int, 0, n)
dfs(0)
return ans
}
LC47 全排列II
var (
st []bool
a, path []int
ans [][]int
)
func dfs(u int) {
if u == len(a) {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
return
}
for i := 0; i < len(a); i ++ {
if i > 0 && a[i] == a[i - 1] && !st[i - 1] {
continue
}
if !st[i] {
path = append(path, a[i])
st[i] = true
dfs(u + 1)
st[i] = false
path = path[ : len(path) - 1]
}
}
}
func permuteUnique(nums []int) [][]int {
a = nums
n := len(nums)
st = make([]bool, n)
ans, path = make([][]int, 0), make([]int, 0, n)
sort.Ints(nums)
dfs(0)
return ans
}
LC48 旋转图像
func rotate(g [][]int) {
n := len(g)
for i := 0; i < n / 2; i ++ {
for j := 0; j < n; j ++ {
g[i][j], g[n - i - 1][j] = g[n - i - 1][j], g[i][j]
}
}
for i := 0; i < n; i ++ {
for j := 0; j < i; j ++ {
g[i][j], g[j][i] = g[j][i], g[i][j]
}
}
}
LC49 字母异位词分组
func groupAnagrams(strs []string) [][]string {
mp := map[string][]string{}
for _, str := range strs {
s := []byte(str)
sort.Slice(s, func(i, j int) bool {
return s[i] < s[j]
})
t := string(s)
mp[t] = append(mp[t], str)
}
ans := [][]string{}
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
LC50 Pow(x, n)
func qmi(a float64, b int) float64 {
ans := 1.0
if b < 0 {
b = -b
}
for b > 0 {
if b & 1 > 0 {
ans *= a
}
a *= a
b >>= 1
}
return ans
}
func myPow(x float64, n int) float64 {
sign := n < 0
ans := qmi(x, n)
if sign {
return 1 / ans
}
return ans
}
LC51 N皇后
var (
n int
path []string
ans [][]string
col, dg, udg []bool
)
func dfs(u int) {
if u == n {
tmp := make([]string, n)
copy(tmp, path)
ans = append(ans, tmp)
return
}
for i := 0; i < n; i ++ {
if !col[i] && !dg[u + i] && !udg[u - i + n] {
path[u] = path[u][ : i] + "Q" + path[u][i + 1 : ]
col[i], dg[u + i], udg[u - i + n] = true, true, true
dfs(u + 1)
col[i], dg[u + i], udg[u - i + n] = false, false, false
path[u] = path[u][ : i] + "." + path[u][i + 1 : ]
}
}
}
func solveNQueens(_n int) [][]string {
n = _n
path = make([]string, n)
ans = [][]string{}
col, dg, udg = make([]bool, 2 * n), make([]bool, 2 * n), make([]bool, 2 * n)
for i := range path {
path[i] = string(make([]byte, n))
for j := 0; j < n; j ++ {
path[i] = path[i][ : j] + "." + path[i][j + 1 : ]
}
}
dfs(0)
return ans
}
LC52 N皇后II
var (
n, ans int
path []string
col, dg, udg []bool
)
func dfs(u int) {
if u == n {
ans ++
return
}
for i := 0; i < n; i ++ {
if !col[i] && !dg[u + i] && !udg[u - i + n] {
path[u] = path[u][ : i] + "Q" + path[u][i + 1 : ]
col[i], dg[u + i], udg[u - i + n] = true, true, true
dfs(u + 1)
col[i], dg[u + i], udg[u - i + n] = false, false, false
path[u] = path[u][ : i] + "." + path[u][i + 1 : ]
}
}
}
func totalNQueens(_n int) int {
n, ans = _n, 0
path = make([]string, n)
col, dg, udg = make([]bool, 2 * n), make([]bool, 2 * n), make([]bool, 2 * n)
for i := range path {
path[i] = string(make([]byte, n))
for j := 0; j < n; j ++ {
path[i] = path[i][ : j] + "." + path[i][j + 1 : ]
}
}
dfs(0)
return ans
}
LC53 最大子数组和
func maxSubArray(nums []int) int {
s, ans := 0, math.MinInt
for i := 0; i < len(nums); i ++ {
if s > 0 {
s += nums[i]
} else {
s = nums[i]
}
if s > ans {
ans = s
}
}
return ans
}
LC54 螺旋矩阵
func spiralOrder(g [][]int) []int {
dx := []int{0, 1, 0, -1}
dy := []int{1, 0, -1, 0}
n, m := len(g), len(g[0])
st := make([][]bool, n)
for i := 0; i < n; i ++ {
st[i] = make([]bool, m)
}
ans := []int{}
x, y, d := 0, 0, 0
for i := 0; i < n * m; i ++ {
ans = append(ans, g[x][y])
st[x][y] = true
a, b := x + dx[d], y + dy[d]
if a < 0 || a >= n || b < 0 || b >= m || st[a][b] {
d = (d + 1) % 4
a, b = x + dx[d], y + dy[d]
}
x, y = a , b
}
return ans
}
LC55 跳跃游戏
func canJump(nums []int) bool {
for i, j := 1, 0; i < len(nums); i ++ {
for j < i && j + nums[j] < i {
j ++
}
if j == i {
return false
}
}
return true
}
LC56 合并区间
func merge(a [][]int) [][]int {
ans := [][]int{}
sort.Slice(a, func(i, j int) bool {
if a[i][0] != a[j][0] {
return a[i][0] < a[j][0]
}
return a[i][1] < a[j][1]
})
lastL, lastR := a[0][0], a[0][1]
for i := 1; i < len(a); i ++ {
if a[i][0] > lastR {
ans = append(ans, []int{lastL, lastR})
lastL, lastR = a[i][0], a[i][1]
} else {
lastR = max(lastR, a[i][1])
}
}
ans = append(ans, []int{lastL, lastR})
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
lC57 插入区间
func insert(a [][]int, b []int) [][]int {
ans := [][]int{}
n, k := len(a), 0
for k < n && b[0] > a[k][1] {
ans = append(ans, a[k])
k ++
}
if k < n {
b[0] = min(b[0], a[k][0])
for k < n && a[k][0] <= b[1] {
b[1] = max(b[1], a[k][1])
k ++
}
}
ans = append(ans, b)
for k < n {
ans = append(ans, a[k])
k ++
}
return ans
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
LC58 最后一个单词的长度
func lengthOfLastWord(s string) int {
i, ans := len(s) - 1, 0
for s[i] == ' ' {
i --
}
for i >= 0 && s[i] != ' ' {
ans ++
i --
}
return ans
}
LC59 螺旋矩阵II
func generateMatrix(n int) [][]int {
dx, dy := []int{0, 1, 0, -1}, []int{1, 0, -1, 0}
g := make([][]int, n)
for i := 0; i < n; i ++ {
g[i] = make([]int, n)
}
x, y, d, num := 0, 0, 0, 0
for i := 0; i < n * n; i ++ {
num ++
g[x][y] = num
a, b := x + dx[d], y + dy[d]
if a < 0 || a >= n || b < 0 || b >= n || g[a][b] != 0 {
d = (d + 1) % 4
a, b = x + dx[d], y + dy[d]
}
x, y = a, b
}
return g
}
LC60 排列序列
func getPermutation(n int, k int) string {
v := ""
for i := 1; i <= n; i ++ {
v += strconv.Itoa(i)
}
fact := make([]int, n + 1)
fact[0] = 1
for i := 1; i <= n; i ++ {
fact[i] = fact[i - 1] * i
}
k --
ans := ""
for i := n; i > 0; i -- {
t := k / fact[i - 1]
r := k % fact[i - 1]
k = r
ans += string(v[t])
v = v[ : t] + v[t + 1 :]
}
return ans
}
LC61旋转链表
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
n := 0
p := head
for p != nil {
p = p.Next
n ++
}
k %= n
if k == 0 {
return head
}
slow, fast := head, head
for k > 0 && fast != nil {
fast = fast.Next
k --
}
for fast.Next != nil {
slow = slow.Next
fast = fast.Next
}
fast.Next = head
head = slow.Next
slow.Next = nil
return head
}
LC62 不同路径
func uniquePaths(m int, n int) int {
f := make([][]int, m)
for i := 0; i < m; i ++ {
f[i] = make([]int, n)
}
for i := 0; i < m; i ++ {
for j := 0; j < n; j ++ {
if i == 0 || j == 0 {
f[i][j] = 1
} else {
f[i][j] = f[i - 1][j] + f[i][j - 1]
}
}
}
return f[m - 1][n - 1]
}
func uniquePaths(m int, n int) int {
f := make([][]int, m)
for i := 0; i < m; i ++ {
f[i] = make([]int, n)
}
for i := 0; i < m; i ++ {
for j := 0; j < n; j ++ {
if i == 0 && j == 0 {
f[i][j] = 1
} else {
if i > 0 {
f[i][j] += f[i - 1][j]
}
if j > 0 {
f[i][j] += f[i][ j - 1]
}
}
}
}
return f[m - 1][n - 1]
}
func uniquePaths(m int, n int) int {
f := make([]int, n)
f[0] = 1
for i := 0; i < m; i ++ {
for j := 1; j < n; j ++ {
f[j] += f[j - 1]
}
}
return f[n - 1]
}
LC63 不同路径II
func uniquePathsWithObstacles(g [][]int) int {
m, n := len(g), len(g[0])
f := make([][]int, m)
for i := 0; i < m; i ++ {
f[i] = make([]int, n)
}
for i := 0; i < m; i ++ {
for j := 0; j < n; j ++ {
if g[i][j] == 1 {
continue
}
if i == 0 && j == 0 {
f[i][j] = 1
} else {
if i > 0 {
f[i][j] += f[i - 1][j]
}
if j > 0 {
f[i][j] += f[i][j - 1]
}
}
}
}
return f[m - 1][n - 1]
}
func uniquePathsWithObstacles(g [][]int) int {
m, n := len(g), len(g[0])
f := make([][]int, m)
for i := 0; i < m; i ++ {
f[i] = make([]int, n)
}
for i := 0; i < m && g[i][0] == 0; i ++ {
f[i][0] = 1
}
for j := 0; j < n && g[0][j] == 0; j ++ {
f[0][j] = 1
}
for i := 1; i < m; i ++ {
for j := 1; j < n; j ++ {
if g[i][j] == 0 {
f[i][j] = f[i - 1][j] + f[i][j - 1]
}
}
}
return f[m - 1][n - 1]
}
func uniquePathsWithObstacles(g [][]int) int {
m, n := len(g), len(g[0])
f := make([]int, n)
if g[0][0] == 0 {
f[0] = 1
} else {
f[0] = 0
}
for i := 0; i < m; i ++ {
for j := 0; j < n; j ++ {
if g[i][j] == 1 {
f[j] = 0
continue
}
if j > 0 && g[i][j - 1] == 0 {
f[j] += f[j - 1]
}
}
}
return f[n - 1]
}
LC64 最小路径和
func minPathSum(g [][]int) int {
m, n := len(g), len(g[0])
f := make([][]int, m)
for i := 0; i < m; i ++ {
f[i] = make([]int, n)
for j := 0; j < n; j++ {
f[i][j] = math.MaxInt32
}
}
for i := 0; i < m; i ++ {
for j := 0; j < n; j ++ {
if i == 0 && j == 0 {
f[i][j] = g[i][j]
} else {
if i > 0 {
f[i][j] = min(f[i][j], f[i - 1][j] + g[i][j])
}
if j > 0 {
f[i][j] = min(f[i][j], f[i][j - 1] + g[i][j])
}
}
}
}
return f[m - 1][n - 1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func minPathSum(g [][]int) int {
m, n := len(g), len(g[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
for i := 0; i < m; i ++ {
for j := 0; j < n; j ++ {
if i == 0 && j == 0 {
f[i][j] = g[i][j]
} else if i == 0 {
f[i][j] = f[i][j - 1] + g[i][j]
} else if j == 0 {
f[i][j] = f[i - 1][j] + g[i][j]
} else {
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i][j]
}
}
}
return f[m - 1][n - 1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func minPathSum(g [][]int) int {
m, n := len(g), len(g[0])
f := make([][]int, m)
for i := 0; i < m; i ++ {
f[i] = make([]int, n)
}
f[0][0] = g[0][0]
for i := 1; i < m; i ++ {
f[i][0] = f[i - 1][0] + g[i][0]
}
for j := 1; j < n; j ++ {
f[0][j] = f[0][j - 1] + g[0][j]
}
for i := 1; i < m; i ++ {
for j := 1; j < n; j ++ {
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i][j]
}
}
return f[m - 1][n - 1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func minPathSum(g [][]int) int {
m, n := len(g), len(g[0])
f := make([][]int, m + 1)
for i := 0; i <= m; i ++ {
f[i] = make([]int, n + 1)
for j := 0; j <= n; j ++ {
f[i][j] = math.MaxInt32
}
}
f[1][1] = g[0][0]
for i := 1; i <= m; i ++ {
for j := 1; j <= n; j ++ {
if i == 1 && j == 1 {
continue
}
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i - 1][j - 1]
}
}
return f[m][n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
LC65 有效数字
func check(s string, l, r int, mustInt bool) bool {
if l < len(s) && (s[l] == '+' || s[l] == '-') {
l ++
}
point, digit := false, false
for i := l; i <= r && i < len(s); i++ {
if s[i] == '.' {
if point || mustInt {
return false
}
point = true
} else if s[i] >= '0' && s[i] <= '9' {
digit = true
} else {
return false
}
}
return digit
}
func isNumber(s string) bool {
idx, n := -1, len(s)
for i := 0; i < n; i++ {
if s[i] == 'e' || s[i] == 'E' {
if idx == -1 {
idx = i
} else {
return false
}
}
}
if idx == -1 {
return check(s, 0, n-1, false)
}
if idx >= n {
return false
}
return check(s, 0, idx-1, false) && check(s, idx+1, n-1, true)
}
LC66 加一
func plusOne(digits []int) []int {
t := 1
for i := len(digits) - 1; i >= 0; i -- {
t += digits[i]
digits[i] = t % 10
t /= 10
}
if t > 0 {
digits = append([]int{t}, digits...)
}
return digits
}
LC67 二进制求和
func reverse(str string) string {
s := []byte(str)
for i, j := 0, len(s) - 1; i < j; i, j = i + 1, j - 1 {
s[i], s[j] = s[j], s[i]
}
return string(s)
}
func addBinary(a string, b string) string {
n, m := len(a), len(b)
a, b = reverse(a), reverse(b)
var ans strings.Builder
for i, t := 0, 0; i < n || i < m || t > 0; i ++ {
if i < n {
t += int(a[i] - '0')
}
if i < m {
t += int(b[i] - '0')
}
ans.WriteString(strconv.Itoa(t % 2))
t /= 2
}
return reverse(ans.String())
}
LC68 文本左右对齐
func fullJustify(words []string, maxWidth int) []string {
n := len(words)
ans := []string{}
for i := 0; i < n; {
lineLen := len(words[i])
j := i + 1
for j < n && lineLen + 1 + len(words[j]) <= maxWidth {
lineLen += 1 + len(words[j])
j ++
}
var line strings.Builder
if j == n || j - i == 1 {
line.WriteString(words[i])
for k := i + 1; k < j; k ++ {
line.WriteByte(' ')
line.WriteString(words[k])
}
line.WriteString(strings.Repeat(" ", maxWidth - line.Len()))
} else {
gap := j - i - 1
if gap > 0 {
space := maxWidth - lineLen + gap
line.WriteString(words[i])
for k := 0; k < space % gap; k ++ {
line.WriteString(strings.Repeat(" ", space / gap + 1))
line.WriteString(words[i + k + 1])
}
for k := space % gap; k < gap; k ++ {
line.WriteString(strings.Repeat(" ", space / gap))
line.WriteString(words[i + k + 1])
}
}
}
ans = append(ans, line.String())
i = j
}
return ans
}
LC69 x的平方根
func mySqrt(x int) int {
l, r := 0, x
for l < r {
mid := (l + r + 1) >> 1
if mid * mid <= x {
l = mid
} else {
r = mid - 1
}
}
return l
}
LC70 爬楼梯
func climbStairs(n int) int {
f := make([]int, n + 1)
f[0], f[1] = 1, 1
for i := 2; i <= n; i ++ {
f[i] = f[i - 1] + f[i - 2]
}
return f[n]
}
LC71简化路径
func simplifyPath(path string) string {
ans, name := "", ""
if path[len(path) - 1] != '/' {
path += "/"
}
for i := 0; i < len(path); i ++ {
if (path[i] != '/' ) {
name += string(path[i])
} else {
if name == ".." {
for len(ans) > 0 && ans[len(ans) - 1] != '/' {
ans = ans[: len(ans) - 1]
}
if len(ans) > 0 {
ans = ans[: len(ans) - 1]
}
} else if (name != "." && name != "") {
ans += "/" + name
}
name = ""
}
}
if len(ans) == 0 {
ans = "/"
}
return ans
}
LC72 编辑距离
func minDistance(a string, b string) int {
n, m := len(a), len(b)
a, b = " " + a, " " + b
f := make([][]int, n + 1)
for i := 0; i <= n; i ++ {
f[i] = make([]int, m + 1)
}
for i := 0; i <= n; i ++ {
f[i][0] = i
}
for j := 0; j <= m; j ++ {
f[0][j] = j
}
for i := 1; i <= n; i ++ {
for j := 1; j <= m; j ++ {
if a[i] == b[j] {
f[i][j] = f[i - 1][j - 1]
} else {
f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1
}
}
}
return f[n][m]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
LC73 矩阵置零
func setZeroes(g [][]int) {
n, m := len(g), len(g[0])
r0, c0 := false, false
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
if g[i][j] == 0 {
if i == 0 {
r0 = true
}
if j == 0 {
c0 = true
}
g[i][0], g[0][j] = 0, 0
}
}
}
for i := 1; i < n; i ++ {
if g[i][0] == 0 {
for j := 1; j < m; j ++ {
g[i][j] = 0
}
}
}
for j := 1; j < m; j ++ {
if g[0][j] == 0 {
for i := 1; i < n; i ++ {
g[i][j] = 0
}
}
}
if r0 {
for j := 0; j < m; j ++ {
g[0][j] = 0
}
}
if c0 {
for i := 0; i < n; i ++ {
g[i][0] = 0
}
}
}
LC74 搜索二维矩阵
func searchMatrix(g [][]int, target int) bool {
n, m := len(g), len(g[0])
if n == 0 || m == 0 {
return false
}
x, y := 0, m - 1
for x < n && y >= 0 {
if g[x][y] < target {
x ++
} else if g[x][y] > target {
y --
} else {
return true
}
}
return false
}
LC75 颜色分类
func sortColors(nums []int) {
p0, p2 := 0, len(nums) - 1
for i := 0; i <= p2; {
if nums[i] == 0 {
nums[i], nums[p0] = nums[p0], nums[i]
i ++
p0 ++
} else if nums[i] == 1 {
i ++
} else {
nums[i], nums[p2] = nums[p2], nums[i]
p2 --
}
}
}
LC76 最小覆盖子串
func minWindow(s string, t string) string {
if len(s) < len(t) {
return ""
}
mp := map[byte]int{}
for _, c := range t {
mp[byte(c)] ++
}
start, need, length := 0, len(mp), math.MaxInt32
for l, r := 0, 0; r < len(s); r ++ {
mp[s[r]] --
if mp[s[r]] == 0 {
need --
}
for need == 0 {
if r - l + 1 < length {
start = l
length = r - l + 1
}
mp[s[l]] ++
if mp[s[l]] > 0 {
need ++
}
l ++
}
}
if length == math.MaxInt32 {
return ""
}
return s[start : start + length]
}
LC77 组合
var (
n, k int
path []int
ans [][]int
)
func dfs(start int) {
if len(path) + (n - start + 1) < k {
return
}
if k == len(path) {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
return
}
for i := start; i <= n; i ++ {
path = append(path, i)
dfs(i + 1)
path = path[ : len(path) - 1]
}
}
func combine(_n int, _k int) [][]int {
n, k = _n, _k
path, ans = make([]int, 0, k), make([][]int, 0)
dfs(1)
return ans
}
LC78 子集
var (
a, path []int
ans [][]int
)
func dfs(start int) {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
for i := start; i < len(a); i ++ {
path = append(path, a[i])
dfs(i + 1)
path = path[ : len(path) - 1]
}
}
func subsets(nums []int) [][]int {
a = nums
path, ans = make([]int, 0, len(a)), make([][]int, 0)
dfs(0)
return ans
}
var (
a, path []int
ans [][]int
)
func dfs(u int) {
if u >= len(a) {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
return
}
dfs(u + 1)
path = append(path, a[u])
dfs(u + 1)
path = path[ : len(path) - 1]
}
func subsets(nums []int) [][]int {
a = nums
path, ans = make([]int, 0, len(a)), make([][]int, 0)
dfs(0)
return ans
}
func subsets(nums []int) [][]int {
ans := [][]int{}
n := len(nums)
for i := 0; i < (1 << n); i ++ {
tmp := []int{}
for j := 0; j < n; j ++ {
if (i >> j & 1) != 0 {
tmp = append(tmp, nums[j])
}
}
ans = append(ans, tmp)
}
return ans
}
LC79 单词搜索
var (
n, m int
dx = [4]int{0, 1, 0, -1}
dy = [4]int{-1, 0, 1, 0}
)
func dfs(board [][]byte, word string, u, x, y int) bool {
if board[x][y] != word[u] {
return false
}
if u >= len(word) - 1 {
return true
}
t := board[x][y]
board[x][y] = '#'
for i := 0; i < 4; i ++ {
a, b := x + dx[i], y + dy[i]
if a < 0 || a >= n || b < 0 || b >= m || board[a][b] == '#' {
continue
}
if dfs(board, word, u + 1, a, b) {
return true
}
}
board[x][y] = t
return false
}
func exist(board [][]byte, word string) bool {
n, m = len(board), len(board[0])
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
if dfs(board, word, 0, i, j) {
return true
}
}
}
return false
}
LC80 删除有序数组中的重复项II
func solve(nums []int, k int) int {
i := 0
for _, x := range nums {
if i < k || nums[i - k] != x {
nums[i] = x
i ++
}
}
return i
}
func removeDuplicates(nums []int) int {
return solve(nums, 2)
}
LC81 搜索旋转排序数组II
func search(nums []int, target int) bool {
n := len(nums) - 1
for n >= 0 && nums[n] == nums[0] {
n --
}
if n < 0 {
return nums[0] == target
}
l, r := 0, n
for l < r {
mid := (l + r + 1) >> 1
if nums[mid] >= nums[0] {
l = mid
} else {
r = mid - 1
}
}
if target >= nums[0] {
l = 0
} else {
l, r = r + 1, n
}
for l < r {
mid := (l + r) >> 1
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
return nums[r] == target
}
LC82 删除排序链表中的重复元素II
func deleteDuplicates(head *ListNode) *ListNode {
dummy := &ListNode{}
dummy.Next = head
p := dummy
for p.Next != nil {
q := p.Next
for q != nil && q.Val == p.Next.Val {
q = q.Next
}
if p.Next.Next == q {
p = p.Next
} else {
p.Next = q
}
}
return dummy.Next
}
LC83 删除排序链表中的重复元素
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return head
}
p := head
for p.Next != nil {
if p.Val == p.Next.Val {
p.Next = p.Next.Next
} else {
p = p.Next
}
}
return head
}
LC84 柱状图中的最大矩形
func largestRectangleArea(h []int) int {
n := len(h)
l, r := make([]int, n + 2), make([]int, n + 2)
stk := []int{}
h = append([]int{-1}, h...)
stk = append(stk, 0)
for i := 1; i <= n; i ++ {
for h[stk[len(stk) - 1]] >= h[i] {
stk = stk[ : len(stk) - 1]
}
l[i] = stk[len(stk) - 1]
stk = append(stk, i)
}
stk = []int{}
h = append(h, -1)
stk = append(stk, n + 1)
for i := n; i > 0; i -- {
for h[stk[len(stk) - 1]] >= h[i] {
stk = stk[ : len(stk) - 1]
}
r[i] = stk[len(stk) - 1]
stk = append(stk, i)
}
ans := 0
for i := 1; i <= n; i ++ {
if ans < (h[i] * (r[i] - l[i] - 1)) {
ans = h[i] * (r[i] - l[i] - 1)
}
}
return ans
}
func largestRectangleArea(h []int) int {
n := len(h)
h = append([]int{-1}, h...)
h = append(h, -1)
stk := []int{}
stk = append(stk, 0)
ans := 0
for i := 1; i <= n + 1; i ++ {
for h[i] < h[stk[len(stk) - 1]] {
mid := stk[len(stk) - 1]
stk = stk[: len(stk) - 1]
width := i - stk[len(stk) - 1] - 1
height := h[mid]
if width * height > ans {
ans = width * height
}
}
stk = append(stk, i)
}
return ans
}
LC85 最大矩形
func solve(h []int) int {
n := len(h)
l, r := make([]int, n), make([]int ,n)
stk := []int{}
for i := 0; i < n; i ++ {
for len(stk) > 0 && h[stk[len(stk) - 1]] >= h[i] {
stk = stk[: len(stk) - 1]
}
if len(stk) == 0 {
l[i] = -1
} else {
l[i] = stk[len(stk) - 1]
}
stk = append(stk, i)
}
stk = []int{}
for i := n - 1; i >= 0; i -- {
for len(stk) > 0 && h[stk[len(stk) - 1]] >= h[i] {
stk = stk[: len(stk) - 1]
}
if len(stk) == 0 {
r[i] = n
} else {
r[i] = stk[len(stk) - 1]
}
stk = append(stk, i)
}
ans := 0
for i := 0; i < n; i ++ {
ans = max(ans, h[i] * (r[i] - l[i] - 1))
}
return ans
}
func maximalRectangle(g [][]byte) int {
n, m := len(g), len(g[0])
if n == 0 || m == 0 {
return 0
}
s := make([][]int, n)
for i := 0; i < n; i ++ {
s[i] = make([]int, m)
}
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
if g[i][j] == '1' {
if i > 0 {
s[i][j] = s[i - 1][j] + 1
} else {
s[i][j] = 1
}
}
}
}
ans := 0
for i := 0; i < n; i ++ {
ans = max(ans, solve(s[i]))
}
return ans
}
func max(x, y int )int {
if x > y {
return x
}
return y
}
func solve(h []int) int {
n := len(h)
ans := 0
h = append([]int{-1}, h...)
h = append(h, -1)
stk := []int{}
for i := 0; i < n + 2; i ++ {
for len(stk) > 0 && h[stk[len(stk) - 1]] > h[i] {
mid := stk[len(stk) - 1]
stk = stk[ : len(stk) - 1]
ans = max(ans, h[mid] * (i - stk[len(stk) - 1] - 1))
}
stk = append(stk, i)
}
return ans
}
func maximalRectangle(g [][]byte) int {
n, m := len(g), len(g[0])
if n == 0 || m == 0 {
return 0
}
s := make([][]int, n)
for i := 0; i < n; i ++ {
s[i] = make([]int, m)
}
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
if g[i][j] == '1' {
if i > 0 {
s[i][j] = s[i - 1][j] + 1
} else {
s[i][j] = 1
}
}
}
}
ans := 0
for i := 0; i < n; i ++ {
ans = max(ans, solve(s[i]))
}
return ans
}
func max(x, y int )int {
if x > y {
return x
}
return y
}
LC86 分隔链表
func partition(head *ListNode, x int) *ListNode {
small, big := &ListNode{}, &ListNode{}
ps, pb := small, big
for p := head; p != nil; p = p.Next {
if p.Val < x {
ps.Next = p
ps = ps.Next
} else {
pb.Next = p
pb = pb.Next
}
}
ps.Next = big.Next
pb.Next = nil
return small.Next
}
LC87 扰乱字符串
func isScramble(s1 string, s2 string) bool {
n, m := len(s1), len(s2)
if n != m {
return false
}
f := make([][][]bool, n)
for i := 0; i < n; i ++ {
f[i] = make([][]bool, n)
for j := 0; j < n; j ++ {
f[i][j] = make([]bool, n + 1)
}
}
for len := 1; len <= n; len ++ {
for i := 0; i + len - 1 < n; i ++ {
for j := 0; j + len - 1 < n; j ++ {
if len == 1 {
f[i][j][len] = (s1[i] == s2[j])
} else {
for k := 1; k < len; k ++ {
if (f[i][j][k] && f[i + k][j + k][len - k]) || (f[i][j + len - k][k] && f[i + k][j][len - k]) {
f[i][j][len] = true
break
}
}
}
}
}
}
return f[0][0][n]
}
LC88 合并两个有序数组
func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m - 1, n - 1, m + n - 1
for i >= 0 && j >= 0 {
if nums1[i] >= nums2[j] {
nums1[k] = nums1[i]
k --
i --
} else {
nums1[k] = nums2[j]
k --
j --
}
}
for j >= 0 {
nums1[k] = nums2[j]
k --
j --
}
}
LC89 格雷编码
func grayCode(n int) []int {
ans := make([]int, 1)
head := 1
for n != 0 {
for i := len(ans) - 1; i >= 0; i -- {
ans = append(ans, head + ans[i])
}
head <<= 1
n --
}
return ans
}
LC90 子集II
var (
ans [][]int
a, path []int
)
func dfs(start int) {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
for i := start; i < len(a); i ++ {
if i > start && a[i] == a[i - 1] {
continue
}
path = append(path, a[i])
dfs(i + 1)
path = path[: len(path) - 1]
}
}
func subsetsWithDup(nums []int) [][]int {
a, path, ans = nums, make([]int, 0, len(a)), make([][]int, 0)
sort.Ints(a)
dfs(0)
return ans
}
var (
ans [][]int
a, path []int
st []bool
)
func dfs(start int) {
tmp := make([]int, len(path))
copy(tmp, path)
ans = append(ans, tmp)
for i := start; i < len(a); i ++ {
if i > 0 && a[i] == a[i - 1] && !st[i - 1]{
continue
}
path = append(path, a[i])
st[i] = true
dfs(i + 1)
path = path[: len(path) - 1]
st[i] = false
}
}
func subsetsWithDup(nums []int) [][]int {
a, path, ans = nums, make([]int, 0, len(a)), make([][]int, 0)
st = make([]bool, len(a))
sort.Ints(a)
dfs(0)
return ans
}
LC91 解码方法
func numDecodings(s string) int {
n := len(s)
s = " " + s
f := make([]int, n + 1)
f[0] = 1
for i := 1; i <= n; i ++ {
if s[i] != '0' {
f[i] += f[i - 1]
}
if i >= 2 {
t := (int(s[i - 1] - '0')) * 10 + int(s[i] - '0')
if t >= 10 && t <= 26 {
f[i] += f[i - 2]
}
}
}
return f[n]
}
LC92 反转链表II
func reverseBetween(head *ListNode, left int, right int) *ListNode {
dummy := &ListNode{-1, head}
p0 := dummy
for i := 0; i < left - 1; i ++ {
p0 = p0.Next
}
var pre, cur *ListNode = nil, p0.Next
for i := 0; i < right - left + 1; i ++ {
nxt := cur.Next
cur.Next = pre
pre = cur
cur = nxt
}
p0.Next.Next = cur
p0.Next = pre
return dummy.Next
}
LC93 复原IP地址
var ans []string
func dfs(s string, u, k int, path string) {
if u == len(s) {
if k >= 4 {
path = path[: len(path) - 1]
ans = append(ans, path)
return
}
}
if k >= 4 {
return
}
for i, t := u, 0; i < len(s); i ++ {
if i > u && s[u] == '0' {
break
}
t = t * 10 + int(s[i] - '0')
if t <= 255 {
dfs(s, i + 1, k + 1, path + strconv.Itoa(t) + ".")
} else {
break
}
}
}
func restoreIpAddresses(s string) []string {
ans = []string{}
dfs(s, 0, 0, "")
return ans
}
LC94 二叉树的中序遍历
var ans []int
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
ans = append(ans, root.Val)
dfs(root.Right)
}
func inorderTraversal(root *TreeNode) []int {
ans = []int{}
if root == nil {
return ans
}
dfs(root)
return ans
}
func inorderTraversal(root *TreeNode) []int {
ans, stk := []int{}, []*TreeNode{}
if root == nil {
return ans
}
for len(stk) > 0 || root != nil {
for root != nil {
stk = append(stk, root)
root = root.Left
}
root = stk[len(stk) - 1]
stk = stk[: len(stk) - 1]
ans = append(ans, root.Val)
root = root.Right
}
return ans
}
func inorderTraversal(root *TreeNode) []int {
ans := []int{}
for root != nil {
if root.Left == nil {
ans = append(ans, root.Val)
root = root.Right
} else {
p := root.Left
for p.Right != nil && p.Right != root {
p = p.Right
}
if p.Right == nil {
p.Right = root
root = root.Left
} else {
ans = append(ans, root.Val)
p.Right = nil
root = root.Right
}
}
}
return ans
}
LC95 不同的二叉搜索树II
func dfs(l, r int) []*TreeNode {
if l > r {
return []*TreeNode{nil}
}
ans := []*TreeNode{}
for i := l; i <= r; i ++ {
left, right := dfs(l, i - 1), dfs(i + 1, r)
for _, lc := range left {
for _, rc := range right {
root := &TreeNode{i, nil, nil}
root.Left, root.Right = lc, rc
ans = append(ans, root)
}
}
}
return ans
}
func generateTrees(n int) []*TreeNode {
if n == 0 {
return nil
}
return dfs(1, n)
}
LC96 不同的二叉搜索树
func numTrees(n int) int {
f := make([]int, n + 1)
f[0] = 1
for i := 1; i <= n; i ++ {
for j := 1; j <= i; j ++ {
f[i] += f[j - 1] * f[i - j]
}
}
return f[n]
}
LC97 交错字符串
func isInterleave(s1 string, s2 string, s3 string) bool {
n, m := len(s1), len(s2)
if n + m != len(s3) {
return false
}
f := make([][]bool, n + 1)
for i := 0; i < n + 1; i ++ {
f[i] = make([]bool, m + 1)
}
s1, s2, s3 = " " + s1, " " + s2, " " + s3
for i := 0; i <= n; i ++ {
for j := 0; j <= m; j ++ {
if i == 0 && j == 0 {
f[i][j] = true
} else {
if i > 0 && s1[i] == s3[i + j] {
f[i][j] = f[i - 1][j]
}
if j > 0 && s2[j] == s3[i + j] {
f[i][j] = f[i][j] || f[i][j - 1]
}
}
}
}
return f[n][m]
}
LC98 验证二叉搜索树
var (
ans bool
pre *TreeNode
)
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if pre != nil && pre.Val >= root.Val {
ans = false
return
}
pre = root
dfs(root.Right)
}
func isValidBST(root *TreeNode) bool {
ans, pre = true, nil
dfs(root)
return ans
}
func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}
stk := []*TreeNode{}
pre := math.MinInt64
for len(stk) > 0 || root != nil {
for root != nil {
stk = append(stk, root)
root = root.Left
}
root = stk[len(stk) - 1]
stk = stk[: len(stk) - 1]
if root.Val <= pre {
return false
}
pre = root.Val
root = root.Right
}
return true
}
LC99 恢复二叉搜索树
var (
x, y, pre *TreeNode
)
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if pre != nil && pre.Val > root.Val {
if x == nil {
x = pre
}
y = root
}
pre = root
dfs(root.Right)
}
func recoverTree(root *TreeNode) {
x, y, pre = nil, nil, nil
dfs(root)
x.Val, y.Val = y.Val, x.Val
}
var (
x, y , pre *TreeNode
)
func recoverTree(root *TreeNode) {
x, y, pre = nil, nil, nil
for root != nil {
if root.Left == nil {
if pre != nil && pre.Val > root.Val {
if x == nil {
x = pre
}
y = root
}
pre = root
root = root.Right
} else {
p := root.Left
for p.Right != nil && p.Right != root {
p = p.Right
}
if p.Right == nil {
p.Right = root
root = root.Left
} else {
p.Right = nil
if pre != nil && pre.Val > root.Val {
if x == nil {
x = pre
}
y = root
}
pre = root
root = root.Right
}
}
}
x.Val, y.Val = y.Val, x.Val
}
LC100 相同的树
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil || p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
欢迎点赞+收藏+关注呀~~~
文章来源:https://blog.csdn.net/qq_45832461/article/details/134881140
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！