Leetcode_go_python

Go and Python solutions for Leetcode. (😁Updating)

Array

Title	Solution	Difficulty	Time	Space	Like	Mark
1. Two Sum	Go	Easy	O(N)	O(N)
11. Contaniner with most water	Go	Medium	O(N)	O(1)		Two pointers (move small)
15. 3 Sum	Go	Medium	O(N^2)	O(N)
16. 3 Sum Closest	Go	Medium	O(N^2)	O(1)
33. Search in Rotated Sorted Array	Go	Medium	O(lg(N))	O(1)		Binary compare lo
39. Combination Sum	Go	Medium	O(2^N)	O(N)
40. Combination Sum II	Go	Medium	O(2^N)	O(N)
53. Maximum Subarray	Go	Medium	O(N)	O(1)		DP or Divide
84. Largest Rectangle in Histogram	Go	Hard	O(N)	O(N)	🌹	Monotonous stack
122. Best Time to Buy and Sell Stock II	Go	Easy	O(N)	O(1)
136. Single number	Go	Easy	O(N)	O(1)	🌹	Bit manipulation
283. Move zeros	Go	Easy	O(N)	O(1)
311. Sparse Matrix Multiplication	Go	Medium	O(N*M)	O(N*M)
525. Contiguous Array	Go	Medium	O(N)	O(N)		diff = 0

String

Title	Solution	Difficulty	Time	Space	Like	Mark
49. Group Anagrams	Go	Medium	O(Nk)	O(Nk)		sort/count
67. Add Binary	Go	Easy	O(Max(N)	O(Max(N))
273. Integer to English Words	Python	Hard	O(len(digits))	O(1)		Devide and Conquer
438. Find All Anagrams in a String	Go	Medium	O(N) 26	O(M)
844. Backspace String Compare	Go	Medium	O(N)	O(1)		pointer(end -> start)
953. Verifying an Alien Dictionary	Python	Easy	O(K*N)	O(1)

Permutation

Title	Solution	Difficulty	Time	Space	Like	Mark
60. Permutation Sequence	Python	Medium	O(N^2)	O(N)		right to left, (n-1)!
31. Next Permutation	Go	Medium	O(N)	O(1)

Parentheses

Title	Solution	Difficulty	Time	Space	Like	Mark
301. Remove Invalid Parentheses	Go	Hard	O(N * 2^N)	O(2^N)		bt, memo, pruning
678. Valid Parenthesis String	Go	Medium	O(N)	O(1)	🌹
1249. Minimum Remove to Make Valid Parentheses	Go	Medium	O(N)	O(N)		check open and close

Graph

Title	Solution	Difficulty	Time	Space	Like	Mark

Tree

Title	Solution	Difficulty	Time	Space	Like	Mark
95. Unique Binary Search Trees II	Go	Medium	O(N * Gn)	O(N*Gn)		(lo, hi), DFS, Memo
96. Unique Binary Search Trees	Go	Medium	O(N^2)	O(N)		Catalan number
124. Binary Tree Maximum Path Sum	Go	Hard	O(N))	O(h)
199. Binary Tree Right Side View	Go Python	Medium	O(N))	O(h)		BFS/DFS
222. Count Complete Tree Nodes	Python	Medium	O(d^2))	O(1)	🌹	bs + bs
543. Diameter of Binary Tree	Go	Easy	O(N)	O(N)
1008. Construct Binary Search Tree from Preorder Traversal	Go	Medium	O(N)	O(N)

Dynamic Programing

Title	Solution	Difficulty	Time	Space	Like	Mark
64. Minimum Path Sum	Go	Medium	O(MN)	O(1)		see 174
174. Dungeon Game	Go	Hard	O(MN)	O(1)	🌹	bottom-right to top-left
887. Super Egg Drop	Go	Hard	O(N^1/2)	O(KM)	🌹

DFS/Memo

Title	Solution	Difficulty	Time	Space	Like	Mark

Linked List

Title	Solution	Difficulty	Time	Space	Like	Mark
202. Happy Number	Go	Easy	O(log(N))	O(1)	🌹	Hare and tortoise
206. Reverse Linked List	Go	Easy	O(N)	O(1)
30-day First Unique Number	Go solution	Easy	O(1)	O(1)		Double-Linked-List

Fundamental

1. Bit manipulation

(1). MIN and MAX

//Int32Max Max int 0111 1111 1111 11..
const Int32Max int = int(^uint(0) >> 1)

//Int32Min Min int 1000 0000 0000 00..
const Int32Min int = ^Int32Max

(2). Add Binary

//a = 1111
//b = 0010
//Sum without carry: a ^ b = 1101
//Carry a & b = 0010 --> (a & b) << 1 = 0100
//Loop until carry become 0
//cannot handle the situation that the number of bits is over 64...
func addBinary2(a string, b string) string {
	binA, _ := strconv.ParseInt(a, 2, 64)
	binB, _ := strconv.ParseInt(b, 2, 64)
	var answer int64
	var carry int64
	for binB != 0 {
		answer = binA ^ binB        //The sum results without carray
		carry = (binA & binB) << 1  //The carry
		binA, binB = answer, carry
	}
	return strconv.FormatInt(binA, 2)

}

(3). Single Number

//Only one is single and others appear twice.
func SingleNumber(nums []int) int {
	// Bit Mapulation
	// a ^ 0 = a
    // a ^ a = 0
    // a ^ b ^ b = a ^ 0 = a
    var res int
    for _, num := range nums {
        res ^= num
    }
	return res

2. Go Fundamental

Slice

var s1 []int            // == nil 
s2 := *new([]int)       // == nil

var s3 = []int{}        // empty slice != nil
var s4 = make([]int, 0) // empty slice != nil
//All can use s1 = append(s1, a)

res = append(res, s)
*res = append(*res, s)

*res = append(*res, s) means that a pointer points to this slice, and the slice is a struct which has three fileds: cap, len, array. When append function is used, the base array address may be changed because a new array with big capacity is allocated. Therefore, when we pass a slice into a function as a result set, try to pass the pointer of the slice instead of the slice struct itself.

Map

This variable m is a map of string keys to int values:

var m map[string]int

Map types are reference types, like pointers or slices, and so the value of m above is nil; it doesn't point to an initialized map. A nil map behaves like an empty map when reading, but attempts to write to a nil map will cause a runtime panic; don't do that. To initialize a map, use the built in make function:

m = make(map[string]int)

The same syntax may be used to initialize an empty map, which is functionally identical to using the make function:

m = map[string]int{}

No set in Go, so a map can be used. map[T]struct{} is better than map[T]bool because struct{} doesn't occupy memory:

set := make(map[int]struct{})
set[v] = struct{}{}s

How to compare two maps?

if reflect.DeepEqual(slide, memo) {
			res = append(res, i-len(p)+1)
		}

String

//https://gobyexample.com/string-functions
package main

import (
    "fmt"
    "strings"
)

var p = fmt.Println

func main() {

    p("Contains:  ", strings.Contains("test", "es"))          //true
    p("Count:     ", strings.Count("test", "t"))              //2
    p("HasPrefix: ", strings.HasPrefix("test", "te"))         //true
    p("HasSuffix: ", strings.HasSuffix("test", "st"))         //true
    p("Index:     ", strings.Index("test", "e"))              //1
    p("Join:      ", strings.Join([]string{"a", "b"}, "-"))   //a-b
    p("Repeat:    ", strings.Repeat("a", 5))                  //aaaaa
    p("Replace:   ", strings.Replace("foooo", "o", "0", -1))  //f0000
    p("Replace:   ", strings.Replace("foooo", "o", "0", 1))   //f0ooo
    p("Split:     ", strings.Split("a-b-c-d", "-"))           //["a","b","c","d"]
    p("ToLower:   ", strings.ToLower("TEST"))
    p("ToUpper:   ", strings.ToUpper("test"))
    p()

    p("Len: ", len("hello"))              //5
    p("Char:", "hello"[1])                //e


    str := []rune("abcd")                //[a, b, c, d]
    str2 := []rune("你好")                //[你,好]
    p(len("你好"))                        //6
    p(len(str2))                         //2
    p(str)
}