# LeetCode
## Solution
#### 1. Two Sum ๐ข
==`Array`== ==`hash Table`==
##### Solution 1
```
func twoSum(nums []int, target int) []int {
var result []int
end := len(nums)-1
for i:=0;i<end;i++ {
loop := end
for i < loop {
if (nums[loop] + nums[i] == target) {
result = append(result, loop, i)
break;
}
loop --
}
if (len(result) != 0 ) {
break;
}
}
return result
}
```
##### Solution 2
```
func twoSum(nums []int, target int) []int {
diffMap := map[int]int {}
for index, num := range nums {
diff := target - num
if pos, exist := diffMap[diff]; exist {
return []int{index, pos}
} else {
diffMap[num] = index
}
}
return []int {}
}
```
#### 3. Longest Substring Without Repeating Characters ๐
==`Hash table`== ==`String`==
##### Solution 1
```
func lengthOfLongestSubstring(s string) int {
var max, left, right int
for i:=0;i<len(s);i++ {
fmt.Println(left, right)
for j:=left;j<right;j++ {
if (s[i] == s[j]) {
max = maximum(max, (right-left))
left = j + 1
break;
}
}
right++
max = maximum(max, (right-left))
}
return max
}
func maximum(a int, b int) int {
if a > b {
return a
}
return b
}
```
##### Solution 2
```
func lengthOfLongestSubstring(s string) int {
left, right := 0, 0
hashMap := make([]int, 128)
maxLen := 0
duplicate := false
for left <= right {
if right >= len(s) {break;}
charNum := int(s[right])
if (hashMap[charNum] != 0) {
maxLen = maximum(maxLen, len(s[left:right]))
hashMap[(int(s[left]))] --
left += 1
duplicate = true
} else {
right ++
hashMap[charNum] ++
duplicate = false
}
}
if (!duplicate) {
maxLen = maximum(maxLen, len(s[left:right]))
}
return maxLen
}
func maximum(a int, b int) int {
if (a > b) {
return a
}
return b
}
```
#### 11. Container With Most Water ๐
```
func maxArea(height []int) int {
l, r := 0, len(height)-1
max := -1
for l<=r {
currentHeight := minimum(height[l], height[r])
max = maximum((r-l)*currentHeight, max)
if height[l] > height[r] {
r--
} else {
l++
}
}
return max
}
func minimum(a, b int) int {
if a > b {return b}
return a
}
func maximum(a, b int) int {
if a > b {return a}
return b
}
```
#### 17. Letter Combinations of a Phone Number ๐
==`Hash Table`== ==`String`== ==`Backtracking`==
```
func letterCombinations(digits string) []string {
var result []string
if len(digits) == 0 {
return result
}
hashMap := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
var dfs func(current string, digits string, hashMap []string, result *[]string)
dfs = func(current string, digits string, hashMap []string, result *[]string) {
if len(digits) == 0 {
*result = append(*result, current)
return
}
index := int(digits[0])-48
for i:=0;i<len(hashMap[index]);i++{
dfs(current + string(hashMap[index][i]), digits[1:], hashMap, result)
}
}
dfs("", digits, hashMap, &result)
return result
}
```
#### 19. Remove Nth Node From End of List ๐
==`Linked List`==
```
func removeNthFromEnd(head *ListNode, n int) *ListNode {
var result *ListNode
result = &ListNode{0, nil}
length := countLength(head)
pos := length-n
current := head
head = result
for current != nil {
if (pos ==0) {
if (current.Next != nil) {
result.Next = current.Next
} else {
result.Next = nil
}
} else {
fmt.Println(result, current)
if (result == nil) {
result = &ListNode{current.Val, nil}
} else {
result.Next = current
result = result.Next
}
}
pos--
current = current.Next
}
return head.Next
}
func countLength(head *ListNode) (length int) {
for head != nil {
length ++
head = head.Next
}
return length
}
```
#### 20. Valid Parentheses ๐ข
==`String`== ==`Stack`==
```
func isValid(s string) bool {
var stack []string
for i:=0;i<len(s);i++ {
left_match, _ := regexp.MatchString("[({[]", string(s[i]))
if left_match {
stack = append(stack, string(s[i]))
}
right_match, _ := regexp.MatchString("[)}\\]]", string(s[i]))
if right_match {
if (!validateRightParenthese(string(s[i]), &stack)) {
return false
}
}
}
if (len(stack) != 0) {
return false
}
return true
}
func validateRightParenthese(target string, stack *[]string) bool {
result := false
if (len(*stack) == 0) {
return false
}
left_parenthese := (*stack)[len(*stack)-1]
switch target {
case ")":
if (left_parenthese == "(") {
result = true
}
break;
case "]":
if (left_parenthese == "[") {
result = true
}
break;
case "}":
if (left_parenthese == "{") {
result = true
}
break;
}
if (result) {
*stack = (*stack)[:len(*stack)-1]
}
return result
}
```
#### 22. Generate Parentheses ๐
```
func generateParenthesis(n int) []string {
var result []string
left_p, right_p := n, n
var dfs func(current string, left_p int, right_p int, result *[]string)
dfs = func(current string, left_p int, right_p int, result *[]string) {
if (left_p == 0 && right_p == 0) {
*result = append(*result, current)
return
}
if left_p > 0 {
dfs(current + "(", left_p-1, right_p, result)
}
if right_p > left_p && right_p > 0 {
dfs(current + ")", left_p, right_p-1, result)
}
}
dfs("", left_p, right_p, &result)
return result
}
```
#### 23. Merge k Sorted Lists ๐ด
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
var result *ListNode
for i:=0;i<len(lists);i++ {
if result == nil {
result = lists[i]
continue
}
result = mergeTwoLists(result, lists[i])
}
return result
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
mergeList := &ListNode{0, nil}
current := mergeList
for list1 != nil || list2 != nil {
if list2 == nil {
tmp := &ListNode{list1.Val, nil}
current.Next = tmp
list1 = list1.Next
} else if list1 == nil {
tmp := &ListNode{list2.Val, nil}
current.Next = tmp
list2 = list2.Next
} else {
if list1.Val <= list2.Val {
tmp := &ListNode{list1.Val, nil}
current.Next = tmp
list1 = list1.Next
} else {
tmp := &ListNode{list2.Val, nil}
current.Next = tmp
list2 = list2.Next
}
}
current = current.Next
}
return mergeList.Next
}
```
#### 25. Reverse Nodes in k-Group ๐ด
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
var prev *ListNode
var reverse_list []*ListNode
var result *ListNode
var left *ListNode
current := head
i := k
for current != nil {
if prev == nil {
prev = &ListNode{current.Val, nil}
} else {
tmp := &ListNode{current.Val, nil}
tmp.Next = prev
prev = tmp
}
i --
if i == 0 {
reverse_list = append(reverse_list, prev)
prev = nil
i = k
left = current.Next
}
current = current.Next
}
var r_t *ListNode
for l:=0;l<len(reverse_list);l++ {
tmp_reverse := reverse_list[l]
for tmp_reverse != nil {
if result == nil {
result = &ListNode{tmp_reverse.Val, nil}
r_t = result
} else {
r_t.Next = &ListNode{tmp_reverse.Val, nil}
r_t = r_t.Next
}
tmp_reverse = tmp_reverse.Next
}
}
if left != nil {
r_t.Next = left
}
return result
}
```
#### 26. Remove Duplicates from Sorted Array ๐ข
```
func removeDuplicates(nums []int) int {
j := 0
for i:=1;i<len(nums);i++ {
if (nums[i] != nums[j]) {
j++
nums[j] = nums[i]
}
}
return j+1
}
```
#### 27. Remove Element ๐ข
```
func removeElement(nums []int, val int) int {
sort.Ints(nums)
if (len(nums) < 1) {
return len(nums)
}
r_start := -1
r_end := len(nums)
for i:=0;i<len(nums);i++ {
if (nums[i] == val && r_start == -1) {
r_start = i
}
if (nums[i] != val && r_start != -1) {
r_end = i
break;
}
}
if (r_start != -1) {
nums = append(nums[:r_start], nums[r_end:]...)
}
return len(nums)
}
```
#### 35. Search Insert Position ๐ข
```
func searchInsert(nums []int, target int) int {
l, r := 0, len(nums)-1
mid := -1
for l <= r {
mid = (r + l) /2
if (nums[mid] == target) {
return mid
} else if (nums[mid] > target) {
r = mid - 1
} else {
l = mid + 1
}
}
return l
}
```
#### 36. Valid Sudoku ๐
==`Array`== ==`Hash Table`== ==`Matrix`==
```
func isValidSudoku(board [][]byte) bool {
for y:=0;y<len(board);y++ {
for x:=0;x<len(board[y]);x++ {
if board[y][x] != '.' {
//-- validate column
validate := validateColumn(board[y][x+1:], board[y][x])
if (!validate) {return false}
//-- validate row
validate = validateRow(board, y+1, x, board[y][x])
if (!validate) {return false}
}
//-- validate sub matrix
validate := validateMatrix(board, y, x)
if (!validate) {return false}
}
}
return true
}
func validateMatrix(board [][]byte, y int, x int) bool {
row_edge, column_edge := 0, 0
if y <= 2 && x <= 2 {
row_edge = 2
column_edge = 2
} else if y <= 2 && x <= 5 {
row_edge = 2
column_edge = 5
} else if y <= 2 && x <= 8 {
row_edge = 2
column_edge = 8
} else if y <= 5 && x <= 2 {
row_edge = 5
column_edge = 2
} else if y <= 5 && x <= 5 {
row_edge = 5
column_edge = 5
} else if y <= 5 && x <= 8 {
row_edge = 5
column_edge = 8
} else if y <= 8 && x <= 2 {
row_edge = 8
column_edge = 2
} else if y <= 8 && x <= 5 {
row_edge = 8
column_edge = 5
} else if y <= 8 && x <= 8 {
row_edge = 8
column_edge = 8
}
start_y := row_edge - 2
start_x := column_edge -2
if y == start_y && x == start_x {
hashMap := make(map[int]bool)
for y1:=start_y;y1<=row_edge;y1++{
for x1:=start_x;x1<=column_edge;x1++ {
if board[y1][x1] == '.' {continue}
if _, ok := hashMap[int(board[y1][x1])-48]; !ok {
hashMap[int(board[y1][x1])-48] = true
} else {
return false
}
}
}
}
return true
}
func validateColumn(column []byte, target byte) bool {
for _, v := range(column) {
if v == target {
return false
}
}
return true
}
func validateRow(board [][]byte, y int, x int, target byte) bool {
for row:=y;row<len(board);row++ {
if board[row][x] == target {
return false
}
}
return true
}
```
#### 37. Sudoku Solver ๐ด
```
func solveSudoku(board [][]byte) {
var dfs func(y, x int, tmpBoard [][]byte, result *[][]byte)
dfs = func(y, x int, tmpBoard [][]byte, result *[][]byte) {
if y == len(tmpBoard) {
for i:=0;i<len(tmpBoard);i++ {
current := []byte{}
for j:=0;j<len(tmpBoard[i]);j++ {
current = append(current, tmpBoard[i][j])
}
(*result) = append((*result), current)
}
return
}
if x == len(tmpBoard[y]) {
dfs(y+1, 0, tmpBoard, result)
return
}
if tmpBoard[y][x] == '.' {
for n:=1;n<=9;n++ {
tmpBoard[y][x] = strconv.Itoa(n)[0]
if validate(y, x, tmpBoard) {
dfs(y, x+1, tmpBoard, result)
}
tmpBoard[y][x] = '.'
}
} else {
dfs(y,x+1,tmpBoard, result)
}
}
var result [][]byte
dfs(0,0,board, &result)
for y:=0;y<len(board);y++ {
for x:=0;x<len(board[y]);x++ {
if board[y][x] == '.' {
board[y][x] = result[y][x]
}
}
}
}
func validate(y, x int, board [][]byte) bool {
hashMap := make(map[int]bool)
// vertical
for vy:=0;vy<9;vy++ {
if board[vy][x] != '.' {
n := int(board[vy][x]) - 48
if _, ok := hashMap[n];ok {
return false
}
hashMap[n] = true
}
}
// horizontal
hashMap = make(map[int]bool)
for vx:=0;vx<9;vx++ {
if board[y][vx] != '.' {
n := int(board[y][vx]) - 48
if _, ok := hashMap[n];ok {
return false
}
hashMap[n] = true
}
}
// board
var by, bx int
hashMap = make(map[int]bool)
if (y>=0 && y<3) && (x>=0 && x<3) {
by, bx = 3, 3
} else if (y>=0 && y<3) && (x>=3 && x<6) {
by, bx = 3, 6
} else if (y>=0 && y<3) && (x>=6 && x<9) {
by, bx = 3, 9
} else if (y>=3 && y<6) && (x>=0 && x<3) { // layer 2
by, bx = 6, 3
} else if (y>=3 && y<6) && (x>=3 && x<6) {
by, bx = 6, 6
} else if (y>=3 && y<6) && (x>=6 && x<9) {
by, bx = 6, 9
} else if (y>=6 && y<9) && (x>=0 && x<3) { // layer 3
by, bx = 9, 3
} else if (y>=6 && y<9) && (x>=3 && x<6) {
by, bx = 9, 6
} else if (y>=6 && y<9) && (x>=6 && x<9) {
by, bx = 9, 9
}
for bby:=by-3;bby<by;bby++ {
for bbx:=bx-3;bbx<bx;bbx++ {
if board[bby][bbx] != '.' {
n := int(board[bby][bbx]) - 48
if _, ok := hashMap[n];ok {
return false
}
hashMap[n] = true
}
}
}
return true
}
```
#### 39. Combination Sum ๐
```
func combinationSum(candidates []int, target int) [][]int {
var result [][]int
var visited = make(map[string]bool)
var dfs func(current []int, target int, visited map[string]bool, candidates []int, result *[][]int)
dfs = func(current []int, target int, visited map[string]bool, candidates []int, result *[][]int) {
if target < 0 {
return
} else if target == 0 {
key := fmt.Sprintf("%v", current)
if !visited[key] {
visited[key] = true
tmp := make([]int, len(current))
copy(tmp, current)
*result = append(*result, tmp)
}
return
} else {
for i:=0;i<len(candidates);i++ {
dfs(append(current, candidates[i]), target-candidates[i], visited, candidates[i:], result)
}
}
}
dfs([]int{}, target, visited, candidates, &result)
return result
}
```
#### 42. Trapping Rain Water ๐ด
```
func trap(height []int) int {
left, right := 0, len(height)-1
sum, minHeight := 0, 0
for left < right {
minHeight = minimum(height[left], height[right])
fmt.Println(left, right, sum)
if height[left] == minHeight {
left +=1
for height[left] < minHeight {
sum += (minHeight - height[left])
left +=1
}
} else {
right -=1
for height[right] < minHeight {
sum += (minHeight - height[right])
right -=1
}
}
}
return sum
}
func minimum(a,b int) int {
if a > b {return b}
return a
}
```
#### 43. Multiply Strings ๐
```
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
result := ""
p2 := len(num2)
for i:=len(num1)-1;i>=0;i-- {
if num1[i] == '0' {
p2--
continue;
}
current_str := multiplySingle(num1[i], num2) + pow10(len(num2)-p2)
if len(result) == 0 {
result = current_str
} else {
rl := len(result)-1
cl := len(current_str)-1
c := 0
for rl >= 0 || cl >=0 {
temp := c
if rl >= 0 {
temp += (int(result[rl])-48)
}
if cl >= 0 {
temp += (int(current_str[cl])-48)
}
c = temp/10
temp %= 10
if rl >= 0 {
result = result[:rl] + strconv.Itoa(temp) + result[rl+1:]
} else {
result = strconv.Itoa(temp) + result
}
rl --
cl --
}
if c > 0 {
result = strconv.Itoa(c) + result
}
}
p2--
}
return result
}
func maximum(a, b int) int {
if a > b {return a}
return b
}
func multiplySingle(num byte, num2 string) string {
result := ""
i := len(num2)-1
c := 0
for i >= 0 {
current := (int(num)-48) * (int(num2[i])-48) + c
c = current/10
current %= 10
result = strconv.Itoa(current) + result
i--
}
if c > 0 {
return strconv.Itoa(c) + result
}
return result
}
func pow10(p int) string {
pow := ""
for i:=0;i<p;i++ {
pow += "0"
}
return pow
}
```
#### 48. Rotate Image ๐
```
func rotate(matrix [][]int) {
for i:=0;i<len(matrix);i++ {
for j:=i+1;j<len(matrix);j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
// reverse
for r:=0;r<len(matrix)/2;r++{
matrix[i][r], matrix[i][len(matrix)-1-r] = matrix[i][len(matrix)-1-r], matrix[i][r]
}
}
}
```
#### 50. Pow(x, n) ๐
==`Math`== ==`Recursion`==
```
func myPow(x float64, n int) float64 {
var helper func(tx float64, tn int) float64
helper = func(tx float64, tn int) float64 {
if tx == 0 {return 0}
if tn == 0 {return 1}
result := helper(tx, tn/2)
result *= result
if tn%2 != 0 {
result *= x
}
return result
}
if n < 0 {
return 1 / helper(x, n)
}
return helper(x, n)
}
```
#### 53. Maximum Subarray ๐
```
func maxSubArray(nums []int) int {
dp := make([]int, len(nums))
maxSum := nums[0]
dp[0] = nums[0]
for i:=1;i<len(nums);i++ {
dp[i] = maximum(dp[i-1]+nums[i], nums[i])
maxSum = maximum(dp[i], maxSum)
}
return maxSum
}
func maximum(a int, b int) int {
if (a > b) {return a}
return b
}
```
#### 56. Merge Intervals ๐
```
func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[j][0] > intervals[i][0]
})
i:=1
for i<len(intervals) {
if intervals[i][0] <= intervals[i-1][1] {
intervals[i-1][0] = minimum(intervals[i][0], intervals[i-1][0])
intervals[i-1][1] = maximum(intervals[i][1], intervals[i-1][1])
intervals = append(intervals[:i], intervals[i+1:]...)
} else {
i++
}
// fmt.Println(i, intervals)
}
return intervals
}
func maximum(a, b int) int {
if a > b {return a}
return b
}
func minimum(a, b int) int {
if a > b {return b}
return a
}
```
#### 61. Rotate List ๐
==`LinkedList`== ==`Tow Pointer`==
```
func rotateRight(head *ListNode, k int) *ListNode {
length := 0
count := head
for count != nil {
length ++
count = count.Next
}
if length == 0 {return head}
var sub1,result *ListNode
current := head
loop := 0
loopTarget := getLoopCount(length, k)
if loopTarget == 0 {return head}
for current != nil {
if loop >= loopTarget {
if result == nil {
result = &ListNode{current.Val, nil}
if current.Next == nil {
tmp := result
tmp.Next = sub1
result = tmp
}
} else {
tr := result
for tr.Next != nil {
tr = tr.Next
}
tr.Next = &ListNode{current.Val, nil}
if current.Next == nil {
tmp := tr.Next
tmp.Next = sub1
}
}
} else {
if sub1 == nil {
sub1 = &ListNode{current.Val, nil}
} else {
dump := sub1
for dump != nil {
if dump.Next == nil {
dump.Next = &ListNode{current.Val, nil}
break;
}
dump = dump.Next
}
}
}
current = current.Next
loop ++
}
return result
}
func getLoopCount(length, k int) int {
loop := 0
if length == k || k % length == 0 {return 0}
if length > k {
loop = length - k
} else {
if (k % length) > length-1 {
loop = length -1
} else {
loop = length - (k % length)
}
}
return loop
}
func minimum(a,b int) int {
if a > b {return b}
return a
}
```
#### 62. Unique Paths ๐
```
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for x:=0;x<m;x++ {
dp[x] = make([]int, n)
for y:=0;y<n;y++ {
if (x == 0 || y == 0) {
dp[x][y] = 1
} else {
dp[x][y] = dp[x-1][y] + dp[x][y-1]
}
}
}
return dp[m-1][n-1]
}
```
#### 63. Unique Paths II ๐
```
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
dp := make([][]int, len(obstacleGrid))
for i:=0;i<len(obstacleGrid);i++ {
dp[i] = make([]int, len(obstacleGrid[i]))
}
for y:=0;y<len(obstacleGrid);y++ {
for x:=0;x<len(obstacleGrid[y]);x++ {
if (obstacleGrid[y][x] == 1){
dp[y][x] = 0
} else {
if (y == 0 && x == 0) {
dp[y][x] = 1
}
if (y > 0) {
dp[y][x] += dp[y-1][x]
}
if (x > 0) {
dp[y][x] += dp[y][x-1]
}
}
}
}
return dp[len(obstacleGrid)-1][len(obstacleGrid[0])-1]
}
```
#### 64. Minimum Path Sum ๐
```
func minPathSum(grid [][]int) int {
dp := make([][]int, len(grid))
for y:=0;y<len(grid);y++ {
dp[y] = make([]int, len(grid[y]))
for x:=0;x<len(grid[y]);x++ {
dp[y][x] = grid[y][x]
if (y == 0 || x == 0) {
if (y == 0 && x != 0) {
dp[y][x] += dp[y][x-1]
}
if (x == 0 && y != 0) {
dp[y][x] += dp[y-1][x]
}
} else {
dp[y][x] += min(dp[y][x-1], dp[y-1][x])
}
}
}
return dp[len(grid)-1][len(grid[0])-1]
}
func min(a int, b int) int {
if (a > b) {
return b
}
return a
}
```
#### 66. Plus One ๐ข
==`Array`== ==`Math`==
```
func plusOne(digits []int) []int {
result := []int{}
c := 1
pos := len(digits)-1
for c > 0 && pos >= 0 {
if (c + digits[pos]) >= 10 {
c = 1
digits[pos] = 0
} else {
c = 0
digits[pos] += 1
}
pos --
}
if c == 1 {
result = append([]int{1}, digits...)
} else {
result = digits
}
return result
}
```
#### 67. Add Binary ๐ข
==`String`== ==`Math`==
```
func addBinary(a string, b string) string {
var result []string
a_pos, b_pos := len(a)-1, len(b)-1
c := 0
for a_pos >= 0 || b_pos >= 0 {
a_int := 0
if (a_pos < len(a) && a_pos >= 0) {
a_int, _ = strconv.Atoi(string(a[a_pos]))
}
b_int := 0
if (b_pos < len(b) && b_pos >= 0) {
b_int, _ = strconv.Atoi(string(b[b_pos]))
}
if (a_int + b_int + c) >= 2 {
pushNum := (a_int + b_int + c)-2
result = append([]string{strconv.Itoa(pushNum)}, result...)
c = 1
} else {
pushNum := (a_int + b_int + c)
result = append([]string{strconv.Itoa(pushNum)}, result...)
c = 0
}
a_pos --
b_pos --
}
if (c == 1) {
result = append([]string{"1"}, result...)
}
return strings.Join(result, "")
}
func max(a int, b int) int {
if (a > b) {
return a
}
return b
}
```
#### 70. Climbing Stairs ๐ข
==`Dynamic Programming`==
```
func climbStairs(n int) int {
dp := make([]int, n+1)
dp[0] = 1;
dp[1] = 1;
for i:=2;i<=n;i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
```
#### 71. Simplify Path ๐
==`Array`== ==`Stack`==
```
func simplifyPath(path string) string {
var path_stack []string
current_path := ""
for i:=1;i<len(path);i++ {
if (path[i] == '/') {
if (len(current_path) > 0) {
if (current_path != ".") {
path_stack = append(path_stack, current_path)
}
}
current_path = ""
} else {
current_path += string(path[i])
}
}
if (len(current_path) > 0) {
if (current_path != ".") {
path_stack = append(path_stack, current_path)
}
}
i := 0
for i < len(path_stack) {
if (path_stack[i] == "..") {
if (i > 0) {
path_stack = append(path_stack[:i-1], path_stack[i+1:]...)
i = i - 1
} else {
fmt.Println(i)
path_stack = path_stack[i+1:]
}
} else {
i++
}
}
if (len(path_stack) > 0) {
return "/" + strings.Join(path_stack, "/")
}
return "/"
}
```
#### 74. Search a 2D Matrix ๐
##### Solution 1
```
func searchMatrix(matrix [][]int, target int) bool {
var level_matrix []int
for y:=0;y<len(matrix);y++ {
for x:=0;x<len(matrix[y]);x++ {
level_matrix = append(level_matrix, matrix[y][x])
}
}
l, r := 0, len(level_matrix) -1
mid := (l+r)/2
for l <= r {
if level_matrix[mid] == target {
return true
} else if level_matrix[mid] > target {
r = mid - 1
} else {
l = mid + 1
}
mid = (l+r)/2
}
return false
}
```
##### Solution 2
```
func searchMatrix(matrix [][]int, target int) bool {
for _, level := range matrix {
result := binarySearch(level, target)
if (result) {return result}
}
return false
}
func binarySearch(matrix_level []int, target int) bool {
l, r := 0, len(matrix_level) -1
mid := (l+r)/2
for l<=r {
if matrix_level[mid] == target {
return true
} else if matrix_level[mid] > target {
r = mid - 1
} else {
l = mid + 1
}
mid = (l+r)/2
}
return false
}
```
#### 75. Sort Colors ๐
```
func sortColors(nums []int) {
left, right := 0, len(nums)-1
for left < right {
for i:=left+1;i<=right;i++ {
if (nums[left] > nums[i]) {
swap(left, i, nums)
}
}
left ++
}
}
func swap(a int, b int, nums []int) {
tmp := nums[a]
nums[a] = nums[b]
nums[b] = tmp
}
```
#### 77. Combinations ๐
```
func combine(n int, k int) [][]int {
var result [][]int
var numList []int
for i:=1;i<=n;i++ {
numList = append(numList, i)
}
var dfs func(k int, numList []int, current []int, result *[][]int)
dfs = func(k int, numList []int, current []int, result *[][]int) {
if len(current) == k {
tmp := make([]int, len(current))
reflect.Copy(reflect.ValueOf(tmp), reflect.ValueOf(current))
*result = append(*result, tmp)
} else if (len(numList) == 0) || (len(current) > k) {
return
}
for i:=0;i<len(numList);i++ {
current = append(current, numList[i])
dfs(k, numList[i+1:], current, result)
//--backtrack
current = current[:len(current)-1]
}
}
dfs(k, numList, []int{}, &result)
return result
}
```
#### 78. Subsets ๐
```
func subsets(nums []int) [][]int {
var result [][]int
result = append(result, []int{})
var dfs func(nums []int, pos int, current []int, result *[][]int)
dfs = func(nums []int, pos int, current []int, result *[][]int) {
if (len(nums) == 0) {
return
}
for i:=pos;i<len(nums);i++ {
current = append(current, nums[i])
tmp := make([]int, len(current))
reflect.Copy(reflect.ValueOf(tmp), reflect.ValueOf(current))
*result = append(*result, tmp)
dfs(nums, i+1, current, result)
current = current[:len(current)-1]
}
}
dfs(nums, 0, []int{}, &result)
return result
}
```
#### 82. Remove Duplicates from Sorted List II ๐
```
func deleteDuplicates(head *ListNode) *ListNode {
var result *ListNode
result = &ListNode{0, nil}
if head == nil {
return head
}
current := head
next := head.Next
duplicate := false
head = result
for next != nil {
if (current.Val != next.Val) {
if (!duplicate) {
result.Next = current
result = result.Next
}
duplicate = false
} else {
duplicate = true
}
current = next
next = next.Next
}
if (duplicate) {
result.Next = nil
} else {
result.Next = current
}
return head.Next
}
```
#### 83. Remove Duplicates from Sorted List ๐ข
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteDuplicates(head *ListNode) *ListNode {
current := head
for current != nil {
next := current.Next
if (next != nil && next.Val == current.Val) {
current.Next = next.Next
} else {
current = current.Next
}
}
return head
}
```
#### 92. Reverse Linked List II ๐
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
var prev *ListNode
var start *ListNode
current := head
i:=1
for current != nil {
if i < left {
if (start == nil) {
start = &ListNode{current.Val, nil}
} else {
tmp := start
for tmp.Next != nil {
tmp = tmp.Next
}
tmp.Next = &ListNode{current.Val, nil}
}
} else if i >= left && i <= right {
if (prev == nil) {
prev = &ListNode{current.Val, nil}
} else {
tmp := &ListNode{0, nil}
tmp.Val = current.Val
tmp.Next = prev
prev = tmp
}
} else if i > right {
tmp := prev
for tmp.Next != nil {
tmp = tmp.Next
}
tmp.Next = current
head = prev
break;
}
i++
current = current.Next
}
if (start != nil) {
tmp := start
for tmp.Next != nil {
tmp = tmp.Next
}
tmp.Next = prev
head = start
} else {
head = prev
}
return head
}
```
#### 94. Binary Tree Inorder Traversal ๐ข
```
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
res := []int{}
dfs(root, &res)
return res
}
func dfs(current *TreeNode, traversal_list *[]int) {
if (current == nil) {
return
}
if (current.Left != nil) {
dfs(current.Left, traversal_list)
}
*traversal_list = append(*traversal_list, current.Val)
if (current.Right != nil) {
dfs(current.Right, traversal_list)
}
}
```
#### 98. Validate Binary Search Tree ๐
```
func isValidBST(root *TreeNode) bool {
prev := math.MinInt
return isBST(root, &prev)
}
func isBST(root *TreeNode, prev *int) bool {
if root == nil {
return true
}
if isBST(root.Left, prev) == false {
return false
}
if root.Val <= *prev {
return false
}
*prev = root.Val
return isBST(root.Right, prev)
}
```
#### 99. Recover Binary Search Tree ๐
```
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func recoverTree(root *TreeNode) {
var orderList []int
var dfs func(root *TreeNode, orderList *[]int)
dfs = func(root *TreeNode, orderList *[]int) {
if root == nil {return}
dfs(root.Left, orderList)
*orderList = append(*orderList, root.Val)
dfs(root.Right, orderList)
}
dfs(root, &orderList)
//-- find diff num
var findSwapInt []int
tmpOrderList := make([]int, len(orderList))
copy(tmpOrderList, orderList)
sort.Ints(tmpOrderList)
for i:=0;i<len(orderList);i++ {
if orderList[i] != tmpOrderList[i] {
findSwapInt = []int{orderList[i], tmpOrderList[i]}
}
}
var swapSearch func(root *TreeNode, swapInt []int)
swapSearch = func(root *TreeNode, swapInt []int) {
if root == nil {return}
if root.Val == swapInt[0] {
root.Val = swapInt[1]
} else if root.Val == swapInt[1] {
root.Val = swapInt[0]
}
swapSearch(root.Left, swapInt)
swapSearch(root.Right, swapInt)
}
swapSearch(root, findSwapInt)
}
```
#### 100. Same Tree ๐ข
```
func isSameTree(p *TreeNode, q *TreeNode) bool {
if ((p == nil && q != nil) || (p != nil && q == nil)) {
return false
} else if (p == nil && q == nil) {
return true
}
same := false
if (p.Val == q.Val) {
same_l := isSameTree(p.Left, q.Left)
same_r := isSameTree(p.Right, q.Right)
same = (same_l && same_r)
}
return same
}
```
#### 101. Symmetric Tree ๐ข
```
func isSymmetric(root *TreeNode) bool {
if root == nil {return false}
res := verifySymmetric(root.Left, root.Right)
return res
}
func verifySymmetric(left *TreeNode, right *TreeNode) bool {
if (left != nil && right == nil) || (left == nil && right != nil) {
return false
} else if (left == nil && right == nil) {
return true
}
left_res := verifySymmetric(left.Left, right.Right)
right_res := verifySymmetric(left.Right, right.Left)
if (left_res && right_res) {
if (left.Val == right.Val) {return true}
}
return false
}
```
#### 102. Binary Tree Level Order Traversal ๐
```
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
layer_map := make(map[int][]int)
result := [][]int{}
if (root == nil) {
return [][]int{}
}
layer := 0
bfs(root, layer+1, &layer_map)
result = append(result, []int{root.Val})
for i:=1;i<=len(layer_map);i++ {
result = append(result, layer_map[i])
}
return result
}
func bfs(root *TreeNode, layer int, res *map[int][]int) []int {
layer_result := []int{}
if (root.Left != nil) {
left := bfs(root.Left, layer + 1, res)
layer_result = append(layer_result, left...)
}
if (root.Right != nil) {
right := bfs(root.Right, layer + 1, res)
layer_result = append(layer_result, right...)
}
if (len(layer_result) != 0) {
(*res)[layer] = append((*res)[layer], layer_result...)
}
return []int{root.Val}
}
```
#### 103. Binary Tree Zigzag Level Order Traversal ๐
```
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
result := [][]int{}
layer := 0
if (root == nil) {
return result
}
bfs(root, layer, &result)
return result
}
func bfs(root *TreeNode, layer int, res *[][]int) {
if (root.Left != nil) {
bfs(root.Left, layer + 1, res)
}
if (root.Right != nil) {
bfs(root.Right, layer + 1, res)
}
for len((*res)) < layer + 1 {
(*res) = append((*res), []int{})
}
if (layer %2 != 0) {
(*res)[layer] = append([]int{root.Val}, (*res)[layer]...)
} else {
(*res)[layer] = append((*res)[layer], root.Val)
}
return;
}
```
#### 104. Maximum Depth of Binary Tree ๐ข
```
func maxDepth(root *TreeNode) int {
var dfs func(root *TreeNode, depth int) int
dfs = func(root *TreeNode, depth int) int {
if root == nil {return depth}
left := dfs(root.Left, depth+1)
right := dfs(root.Right, depth+1)
if (left > right) {
return left
}
return right
}
deep := dfs(root, 0)
return deep
}
```
#### 107. Binary Tree Level Order Traversal II ๐ข
```
func levelOrderBottom(root *TreeNode) [][]int {
var result [][]int
if root == nil {return result}
var bfs func(root *TreeNode, layer int, result *[][]int)
bfs = func(root *TreeNode, layer int, result *[][]int) {
if root == nil {return}
current := []int{}
layer ++
if root.Left != nil {
bfs(root.Left, layer, result)
current = append(current, root.Left.Val)
}
if root.Right != nil {
bfs(root.Right, layer, result)
current = append(current, root.Right.Val)
}
if (len(current) != 0) {
if len(*result) < layer {
for layer-1 > len(*result) {
*result = append(*result, []int{})
}
*result = append(*result, current)
} else {
(*result)[layer-1] = append((*result)[layer-1], current...)
}
}
}
bfs(root, 0, &result)
swap := [][]int{}
for i:=len(result)-1;i>=0;i-- {
if (len(result[i]) != 0) {
swap = append(swap, result[i])
}
}
swap = append(swap, []int{root.Val})
return swap
}
```
#### 118. Pascal's Triangle ๐ข
```
func generate(numRows int) [][]int {
dp := make([][]int, numRows)
for i:=0;i<numRows;i++ {
dp[i] = make([]int, i+1)
for j:=0;j<len(dp[i]);j++ {
if (j == 0 || j == len(dp[i])-1) {
dp[i][j] = 1
} else {
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
}
}
}
return dp
}
```
#### 121. Best Time to Buy and Sell Stock ๐ข
==`Dynamic Programming`==
```
func maxProfit(prices []int) int {
dpMax := make([]int, len(prices))
dpMin := make([]int, len(prices))
dpMin[0] = prices[0]
for i:=1;i<len(prices);i++ {
dpMax[i] = max(max(dpMax[i-1], prices[i] - dpMin[i-1]), dpMax[i])
dpMin[i] = min(prices[i], dpMin[i-1])
}
// fmt.Println(dpMax)
// fmt.Println(dpMin)
return dpMax[len(prices)-1]
}
func max(a int, b int) int {
if (a < b) {
return b
}
return a
}
func min(a int, b int) int {
if (a > b) {
return b
}
return a
}
```
#### 136. Single Number ๐ข
```
func singleNumber(nums []int) int {
if (len(nums) == 1) {return nums[0]}
sort.Ints(nums)
for i:=0;i<len(nums)-1;i+=2{
if (nums[i] != nums[i+1]) {
return nums[i]
}
}
return nums[len(nums)-1]
}
```
#### 141. Linked List Cycle ๐ข
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
if (head == nil || head.Next == nil) {
return false
}
h1 := head.Next
h2 := head.Next.Next
for h1 != nil && h2 != nil {
if (h1 == h2) {
return true
}
h1 = h1.Next
if h2.Next == nil {
return false
}
h2 = h2.Next.Next
}
return false
}
```
#### 142. Linked List Cycle II ๐
==`Linked List`==
```
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
slow, fast := head.Next, head.Next.Next
for slow != nil && fast != nil {
if (slow == fast) {
for head != slow {
head, slow = head.Next, slow.Next
}
return head
}
slow = slow.Next
if (fast.Next == nil) {
return nil
}
fast = fast.Next.Next
}
return nil
}
```
#### 144. Binary Tree Preorder Traversal ๐ข
```
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
result := []int{}
dfs(root, &result)
return result
}
func dfs(root *TreeNode, res *[]int) {
if (root == nil) {
return
}
*res = append(*res, root.Val)
if (root.Left != nil) {
dfs(root.Left, res)
}
if (root.Right != nil) {
dfs(root.Right, res)
}
}
```
#### 145. Binary Tree Postorder Traversal ๐ข
```
func postorderTraversal(root *TreeNode) []int {
result := []int{}
dfs(root, &result)
return result
}
func dfs(root *TreeNode, res *[]int) {
if (root == nil) {
return
}
if (root.Left != nil) {
dfs(root.Left, res)
}
if (root.Right != nil) {
dfs(root.Right, res)
}
*res = append(*res, root.Val)
}
```
#### 147. Insertion Sort List ๐
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func insertionSortList(head *ListNode) *ListNode {
var result *ListNode
current := head
for current != nil {
if result == nil {
result = &ListNode{current.Val, nil}
} else {
var prev *ListNode
resultTmp := result
changeFlag := false
for resultTmp != nil {
if current.Val < resultTmp.Val {
changeFlag = true
if prev == nil {
tmp := &ListNode{current.Val, nil}
tmp.Next = result
result = tmp
} else {
tmp := &ListNode{current.Val, nil}
tmp.Next = resultTmp
prev.Next = tmp
}
break;
}
prev = resultTmp
resultTmp = resultTmp.Next
}
//-- no small than all result
if !changeFlag {
tmp := &ListNode{current.Val, nil}
prev.Next = tmp
}
}
current = current.Next
}
return result
}
```
#### 150. Evaluate Reverse Polish Notation ๐
```
func evalRPN(tokens []string) int {
var nums []int
for i:=0;i<len(tokens);i++ {
num, err := strconv.Atoi(tokens[i])
if (err == nil) {
nums = append(nums, num)
} else {
nums = handleOperator(tokens[i], nums)
}
}
return nums[0]
}
func handleOperator(operator string, nums []int) []int {
sum := 0
switch(operator) {
case "+":
sum = nums[len(nums)-2] + nums[len(nums)-1]
break;
case "-":
sum = nums[len(nums)-2] - nums[len(nums)-1]
break;
case "*":
sum = nums[len(nums)-2] * nums[len(nums)-1]
break;
case "/":
sum = nums[len(nums)-2] / nums[len(nums)-1]
break;
}
nums = append(nums[:len(nums)-2], sum)
return nums
}
```
#### 160. Intersection of Two Linked Lists ๐ข
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
var result *ListNode
lengthA := getListNodeLength(headA)
lengthB := getListNodeLength(headB)
if (lengthA > lengthB) {
length := lengthA - lengthB
for i:=0;i<length;i++ {
headA = headA.Next
}
} else {
length := lengthB - lengthA
for i:=0;i<length;i++ {
headB = headB.Next
}
}
fmt.Println(headA.Val, headB.Val)
for headA != nil && headB != nil {
if headA == headB && result == nil {
result = headA
}
headA = headA.Next
headB = headB.Next
}
return result
}
func getListNodeLength(head *ListNode) int {
length := 0
for head != nil {
length ++
head = head.Next
}
return length
}
```
#### 172. Factorial Trailing Zeroes ๐
```
func trailingZeroes(n int) int {
if n < 5 {return 0}
sum := 1
zeroCnt := 0
for i:=1;i<=n;i++ {
sum *= i
for sum % 5 == 0 {
zeroCnt ++
sum /= 5
}
sum %= 5
}
return zeroCnt
}
```
#### 174. Dungeon Game ๐ด
```
func calculateMinimumHP(dungeon [][]int) int {
dp := make([][]int, len(dungeon))
for i:=0;i<len(dungeon);i++{
dp[i] = make([]int, len(dungeon[i]))
}
y_bond := len(dungeon)-1
x_bond := len(dungeon[0])-1
for y:=y_bond;y>=0;y-- {
for x:=x_bond;x>=0;x-- {
if (y == y_bond && x == x_bond) {
dp[y][x] = maximum(1, (1-dungeon[y][x]))
} else if (y == y_bond) {
dp[y][x] = maximum(1, (dp[y][x+1] - dungeon[y][x]))
} else if (x == x_bond) {
dp[y][x] = maximum(1, (dp[y+1][x] - dungeon[y][x]))
} else {
dp[y][x] = maximum(1, minimum((dp[y][x+1] - dungeon[y][x]), maximum(1, (dp[y+1][x] - dungeon[y][x]))))
}
}
}
return dp[0][0]
}
func maximum(a,b int) int {
if a > b {return a}
return b
}
func minimum(a,b int) int {
if a > b {return b}
return a
}
```
#### 189. Rotate Array ๐
##### Solution 1
```
func rotate(nums []int, k int) {
step := k%len(nums)
tmp := make([]int, step)
copy(tmp, nums[len(nums)-step:])
for i:=len(nums)-1;i>=0;i-- {
if i >= step {
nums[i], nums[i-step] = nums[i-step], nums[i]
} else {
nums[i] = tmp[i]
}
}
}
```
##### Solution 2
```
func rotate(nums []int, k int) {
k %= len(nums)
tmp := make([]int, len(nums))
copy(tmp, nums)
if k != 0 {
tmp = append(tmp[len(tmp)-k:], tmp[:len(tmp)-k]...)
}
copy(nums, tmp)
}
```
#### 198. House Robber ๐
```
func rob(nums []int) int {
if len(nums) == 1 {
return nums[0]
} else if len(nums) == 2 {
return max(nums[0], nums[1])
}
dp := make([]int, len(nums))
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i:=2;i<len(nums);i++ {
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
}
return dp[len(dp)-1]
}
func max(a int, b int) int {
if (a > b) {return a}
return b
}
```
#### 200. Number of Islands ๐
```
func numIslands(grid [][]byte) int {
visited := make([][]bool, len(grid))
for i:=0;i<len(grid);i++ {
visited[i] = make([]bool, len(grid[i]))
}
var dfs func(x int, y int, grid [][]byte, visited *[][]bool)
dfs = func(x int, y int, grid [][]byte, visited *[][]bool) {
if (*visited)[y][x] == true || grid[y][x] == '0' {
return
}
(*visited)[y][x] = true
if x > 0 {
dfs(x-1, y, grid, visited)
}
if x < len(grid[0])-1 {
dfs(x+1, y, grid, visited)
}
if y > 0 {
dfs(x, y-1, grid, visited)
}
if y < len(grid)-1 {
dfs(x, y+1, grid, visited)
}
}
var islandCount int
for y:=0;y<len(grid);y++ {
for x:=0;x<len(grid[y]);x++ {
if !visited[y][x] && grid[y][x] == '1' {
islandCount ++
dfs(x, y, grid, &visited)
}
}
}
return islandCount
}
```
#### 203. Remove Linked List Elements ๐ข
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeElements(head *ListNode, val int) *ListNode {
var prev *ListNode
current := head
for current != nil {
if (current.Val == val) {
if (prev != nil) {
prev.Next = current.Next
} else {
head = current.Next
}
} else {
prev = current
}
current = current.Next
}
return head
}
```
#### 206. Reverse Linked List ๐ข
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
current := head
for current != nil {
fmt.Println(current.Val)
if (prev == nil) {
prev = &ListNode{current.Val, nil}
} else {
tmp := &ListNode{0, nil};
tmp.Val = current.Val
tmp.Next = prev
prev = tmp
}
current = current.Next
}
return prev
}
```
#### 217. Contains Duplicate ๐ข
```
func containsDuplicate(nums []int) bool {
sort.Ints(nums)
result := false
for i:=1;i<len(nums);i++ {
if (nums[i] == nums[i-1]) {
result = true
break;
}
}
return result
}
```
#### 221. Maximal Square ๐
```
func maximalSquare(matrix [][]byte) int {
dp := make([][]int, len(matrix))
for i:=0;i<len(matrix);i++ {
dp[i] = make([]int, len(matrix[0]))
}
max := 0
for y:=0;y<len(matrix);y++ {
for x:=0;x<len(matrix[y]);x++ {
if x != 0 && y != 0 && matrix[y][x] == '1' {
if matrix[y-1][x] == '1' && matrix[y][x-1] == '1' && matrix[y-1][x-1] == '1' {
dp[y][x] = minimum(minimum(dp[y-1][x], dp[y][x-1]), dp[y-1][x-1]) + 1
} else {
dp[y][x] = 1
}
} else if matrix[y][x] == '1' {
dp[y][x] = 1
}
max = maximum(max, dp[y][x])
}
}
return max*max
}
func maximum(a, b int) int {
if a > b {return a}
return b
}
func minimum(a, b int) int {
if a > b {return b}
return a
}
```
#### 225. Implement Stack using Queues ๐ข
```
type MyStack struct {
queue *list.List
}
func Constructor() MyStack {
return MyStack{queue: list.New()}
}
func (this *MyStack) Push(x int) {
this.queue.PushBack(x)
}
func (this *MyStack) Pop() int {
popItem := this.queue.Back()
this.queue.Remove(this.queue.Back())
return popItem.Value.(int)
}
func (this *MyStack) Top() int {
return this.queue.Back().Value.(int)
}
func (this *MyStack) Empty() bool {
return (this.queue.Len() == 0)
}
```
#### 232. Implement Queue using Stacks
```
type MyQueue struct {
queue []int
}
func Constructor() MyQueue {
return MyQueue{queue: []int{}}
}
func (this *MyQueue) Push(x int) {
this.queue = append(this.queue, x)
}
func (this *MyQueue) Pop() int {
popNum := this.queue[0]
this.queue = append([]int{}, this.queue[1:]...)
return popNum
}
func (this *MyQueue) Peek() int {
return this.queue[0]
}
func (this *MyQueue) Empty() bool {
return (len(this.queue) == 0)
}
```
#### 237. Delete Node in a Linked List ๐
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func deleteNode(node *ListNode) {
next := node.Next
node.Val = next.Val
node.Next = next.Next
}
```
#### 242. Valid Anagram ๐ข
```
func isAnagram(s string, t string) bool {
h_map := make(map[string]int)
res := true
for i:=0;i<len(s);i++ {
h_map[string(s[i])] ++
}
for i:=0;i<len(t);i++ {
h_map[string(t[i])] --
}
for _, val := range(h_map) {
if val != 0 {
res = false
}
}
return res
}
```
#### 263. Ugly Number ๐ข
==`Math`==
```
func isUgly(n int) bool {
for n >= 2 || n >= 3 || n >= 5 || n == 1 {
tmp := n
if (n%2 ==0) {
n /= 2
}
if (n%3 ==0) {
n /= 3
}
if (n%5 ==0) {
n /= 5
}
if (n == 1) {
return true
}
if (n == tmp) {
return false
}
}
return false
}
```
#### 283. Move Zeroes ๐ข
```
func moveZeroes(nums []int) {
for i:=0;i < len(nums);i++ {
if (nums[i] == 0) {
swap_pos := findNextUnZero(i, nums)
if (swap_pos == -1) {
return
} else {
swap(i, swap_pos, nums)
}
}
}
}
func findNextUnZero(start int, nums []int) int {
for i:=start;i<len(nums);i++ {
if (nums[i]!=0) {
return i
}
}
return -1
}
func swap(i1 int, i2 int, nums []int) {
tmp := nums[i1]
nums[i1] = nums[i2]
nums[i2] = tmp
}
```
#### 290. Word Pattern ๐ข
==`hash Table`==
```
func wordPattern(pattern string, s string) bool {
wordDirect := strings.Split(s, " ")
hashMap := make(map[string]string)
if len(wordDirect) != len(pattern) {
return false
}
for i:=0;i<len(pattern);i++ {
if hashMap[string(pattern[i])] != "" {
if (hashMap[string(pattern[i])] != wordDirect[i]) {
return false
}
} else {
if checkExist(wordDirect[i], hashMap) {
return false
}
hashMap[string(pattern[i])] = wordDirect[i]
}
}
return true
}
func checkExist(word string, s_map map[string]string) bool {
for _, v := range(s_map) {
if (word == v) {
return true
}
}
return false
}
```
#### 292. Nim Game ๐ข
==`Math`==
```
func canWinNim(n int) bool {
return (n%4 != 0)
}
```
#### 322. Coin Change ๐
```
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i:=1;i<=amount;i++ {
dp[i] = 99999
for c:=0;c<len(coins);c++ {
if i >= coins[c] {
dp[i] = minimum(dp[i], dp[i-coins[c]]+1)
}
}
}
if dp[amount] == 99999 {
return -1
}
return dp[amount]
}
func minimum(a,b int) int {
if a > b {return b}
return a
}
```
#### 349. Intersection of Two Arrays ๐ข
==`Array`== ==`Hashmap`==
```
func intersection(nums1 []int, nums2 []int) []int {
result := []int{}
sort.Ints(nums1)
sort.Ints(nums2)
for i:=0;i<len(nums2);i++ {
if (i != 0 && nums2[i] == nums2[i-1]) {
continue;
}
for j:=0;j<len(nums1);j++ {
if (nums2[i] == nums1[j]) {
result = append(result, nums2[i])
break;
}
}
}
return result
}
```
#### 378. Kth Smallest Element in a Sorted Matrix ๐
```
func kthSmallest(matrix [][]int, k int) int {
var res []int
for i:=0;i<len(matrix);i++ {
for j:=0;j<len(matrix[i]);j++ {
res = sortArray(res, matrix[i][j])
}
}
return res[k-1]
}
func sortArray(array []int, target int) []int {
if (len(array) == 0) {
return append(array, target)
}
i :=0
for i < len(array) && array[i] <= target {
i++
}
array = append(array[:i], array[i-1:]...)
array[i] = target
return array
}
------ binary search
func kthSmallest(matrix [][]int, k int) int {
r, c := len(matrix), len(matrix[0])
lower, upper := matrix[0][0], matrix[r-1][c-1]
for lower <= upper {
mid := (lower + upper) / 2
count := 0
j := c-1
max_val := lower
for i:=0;i<r;i++ {
for j >= 0 && mid < matrix[i][j] {
j --
}
if (j >= 0) {
count += j + 1
if (matrix[i][j] > max_val) {
max_val = matrix[i][j]
}
}
}
if (count == k) {
return max_val
} else if (count < k) {
lower = mid + 1
} else {
upper = mid -1
}
}
return lower
}
```
#### 383. Ransom Note ๐ข
```
func canConstruct(ransomNote string, magazine string) bool {
hashMap := make(map[string]int)
for i:=0;i<len(ransomNote);i++ {
hashMap[string(ransomNote[i])] ++
}
for i:=0;i<len(magazine);i++ {
hashMap[string(magazine[i])] --
}
for _, v := range(hashMap) {
if (v > 0) {
return false
}
}
return true
}
```
#### 387. First Unique Character in a String ๐ข
```
func firstUniqChar(s string) int {
hashMap := make([]int, 26)
for i:=0;i<len(hashMap);i++ {
hashMap[i] = -1
}
for i:=0;i<len(s);i++ {
char_pos := int(s[i])-97
if hashMap[char_pos] != -1 {
hashMap[char_pos] = 99999
} else {
hashMap[char_pos] = i
}
}
sort.Ints(hashMap)
for _, v := range(hashMap) {
if v != -1 && v != 99999 {
return v
}
}
return -1
}
```
#### 389. Find the Difference ๐ข
```
func findTheDifference(s string, t string) byte {
var diff byte
hashMap := make(map[string]int)
for i:=0;i<len(s);i++ {
hashMap[string(s[i])] ++
}
for i:=0;i<len(t);i++ {
hashMap[string(t[i])] --
}
for i, v := range(hashMap) {
if (v == -1) {
return i[0]
}
}
return diff
}
```
#### 394. Decode String ๐
==`String`== ==`Stack`==
##### Solution 1
```
func decodeString(s string) string {
r, _ := regexp.Compile(`\[`)
for r.MatchString(s) {
i:=0
left_b, right_b := 0, 0
for i<len(s) {
if s[i] == '[' {
left_b = i
} else if s[i] == ']' {
right_b = i
break;
}
i++
}
num_pos, current_decode := generateDecode(left_b, right_b, s)
s = s[:num_pos] + current_decode + s[right_b+1:]
}
return s
}
func generateDecode(left, right int, s string) (int, string) {
//-- get num
var result string
num_string := ""
n := left -1
for n >= 0 && int(s[n]) >= 48 && int(s[n]) <= 57 {
num_string = string(s[n]) + num_string
n--
}
num, _ := strconv.Atoi(num_string)
for i:=0;i<num;i++ {
result += s[left+1:right]
}
return n+1,result
}
```
##### Solution 2
```
func decodeString(s string) string {
left_parent_match, _ := regexp.MatchString("\\[", s)
for left_parent_match {
num_sli := 0
string_sli := ""
num_str := ""
decode_item := ""
num_pos := 0
for i:=0;i<len(s);i++ {
num_match, _ := regexp.MatchString("[0-9]+", string(s[i]))
if num_match {
num_str += string(s[i])
} else {
if (num_str != "") {
num, _ := strconv.Atoi(num_str)
num_sli = num
num_pos = i - len(num_str)
num_str = ""
}
}
if string(s[i]) == "[" {
decode_item = ""
} else {
char_match, _ := regexp.MatchString("[a-zA-Z]+", string(s[i]))
if char_match {
decode_item += string(s[i])
}
}
if string(s[i]) == "]" {
if (decode_item != "") {
string_sli = decode_item
decode_item = ""
break;
}
}
}
//-- decode
decode_str := ""
for i:=0;i<num_sli;i++ {
decode_str += string_sli
}
len_n := strconv.Itoa(num_sli)
end_pos := num_pos + len(len_n) + 2 + len(string_sli)
s = s[:num_pos] + decode_str + s[end_pos:]
num_sli = 0
string_sli = ""
left_parent_match, _ = regexp.MatchString("\\[", s)
}
return s
}
```
#### 414. Third Maximum Number ๐ข
```
func thirdMax(nums []int) int {
sort.Ints(nums)
result := 0
maxNum := 1
for i:=len(nums)-1;i>0;i-- {
if (nums[i] != nums[i-1]) {
maxNum ++
}
result = nums[i-1]
if (maxNum == 3) {
break
}
}
if (maxNum < 3) {
return nums[len(nums) - 1 ]
}
return result
}
```
#### 419. Battleships in a Board ๐
```
func countBattleships(board [][]byte) int {
visited := make([][]bool, len(board))
for i:=0;i<len(board);i++ {
visited[i] = make([]bool, len(board[i]))
}
count := 0
var dfs func(y, x int, visited_map *[][]bool, board [][]byte, ship_cnt *int)
dfs = func(y, x int, visited_map *[][]bool, board [][]byte, ship_cnt *int) {
if y < 0 || y >= len(board) || x < 0 || x >= len(board[0]) || (*visited_map)[y][x] {
return
}
if board[y][x] == 'X' {
(*visited_map)[y][x] = true
if y == 0 && x == 0 {
*ship_cnt ++
} else {
same_flag := false
if y > 0 && (*visited_map)[y-1][x] {
same_flag = true
}
if x > 0 && (*visited_map)[y][x-1] {
same_flag = true
}
if !same_flag {
*ship_cnt ++
}
}
dfs(y, x+1, visited_map, board, ship_cnt)
dfs(y+1, x, visited_map, board, ship_cnt)
}
}
for i:=0;i<len(board);i++ {
for j:=0;j<len(board[i]);j++ {
dfs(i, j, &visited, board, &count)
}
}
return count
}
```
#### 463. Island Perimeter ๐ข
```
func islandPerimeter(grid [][]int) int {
perimeter := 0
for y:=0;y<len(grid);y++ {
for x:=0;x<len(grid[0]);x++ {
base := 4
if grid[y][x] == 1 {
if y+1 < len(grid) && grid[y+1][x] == 1 {
base --
}
if x+1 < len(grid[0]) && grid[y][x+1] == 1 {
base --
}
if y > 0 {
if grid[y-1][x] == 1 {
base --
}
}
if x > 0 {
if grid[y][x-1] == 1 {
base --
}
}
perimeter += base
}
}
}
return perimeter
}
```
#### 485. Max Consecutive Ones ๐ข
```
func findMaxConsecutiveOnes(nums []int) int {
dp := make([]int, len(nums))
if (nums[0] == 1) {
dp[0] = 1
}
for i:=1;i<len(nums);i++ {
if (nums[i] == 1) {
dp[i] = dp[i-1] + 1
} else {
dp[i] = 0
}
}
sort.Ints(dp)
return dp[len(nums)-1]
}
```
#### 498. Diagonal Traverse ๐
==`Array`== ==`Matrix`== ==`Simulation`==
```
func findDiagonalOrder(mat [][]int) []int {
var result []int
layer := [][]int{}
for y:=0;y<len(mat);y++ {
x:=0
tmp := y
layer_t := []int{}
for x < len(mat[0]) && tmp >=0 {
layer_t = append(layer_t, mat[tmp][x])
x ++
tmp --
}
layer = append(layer, layer_t)
}
for x:=1;x<len(mat[0]);x++ {
y:=len(mat)-1
tmp := x
layer_t := []int{}
for y >= 0 && tmp < len(mat[0]) {
layer_t = append(layer_t, mat[y][tmp])
y --
tmp ++
}
layer = append(layer, layer_t)
}
verse := false
for _, v := range(layer) {
if (!verse) {
for i:=0;i<len(v);i++ {
result = append(result, v[i])
}
} else {
for i:=len(v)-1;i>=0;i-- {
result = append(result, v[i])
}
}
verse = !verse
}
return result
}
```
#### 509. Fibonacci Number ๐ข
==`Dynamic Programming`==
```
func fib(n int) int {
if (n == 1 || n == 0) {
return n
}
return fib(n-1) + fib(n-2)
}
```
#### 513. Find Bottom Left Tree Value ๐
```
func findBottomLeftValue(root *TreeNode) int {
var dfs func(root *TreeNode, layer int, result *[][]int)
dfs = func(root *TreeNode, layer int, result *[][]int) {
if root == nil {return}
dfs(root.Left, layer+1, result)
dfs(root.Right , layer+1, result)
if root.Left == nil && root.Right == nil {
for len(*result) <= layer {
(*result) = append(*result, []int{})
}
(*result)[layer] = append((*result)[layer], root.Val)
}
return
}
var result [][]int
dfs(root, 0, &result)
return result[len(result)-1][0]
}
```
#### 529. Minesweeper ๐
> ่งฃ้ก้่ผฏ: ้ๅฐ blank ๆชขๆฅๅจๅไนๅฎฎๆ ผ๏ผๆชขๆฅๅฐๆธๅญๅๅๆญข๏ผๆชขๆฅๅฐ็ฉบ็ฝๅฐฑ็นผ็บๆชขๆฅ
```
func updateBoard(board [][]byte, click []int) [][]byte {
cy, cx := click[0], click[1]
if board[cy][cx] == 'M' {
board[cy][cx] = 'X'
return board
}
var dfs func(y, x int, result *[][]byte)
dfs = func(y, x int, result *[][]byte) {
if y < 0 || y > len(*result)-1 || x < 0 || x > len((*result)[0])-1 {
return
}
if (*result)[y][x] != 'E' {
return
}
dir := [][]int{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}
mineCnt := 0
for i:=0;i<len(dir);i++ {
xi, yi := x+dir[i][0], y+dir[i][1]
if (xi >=0 && xi < len((*result)[0]) && yi >=0 && yi < len((*result))) {
fmt.Println(yi, xi, string((*result)[yi][xi]))
if (*result)[yi][xi] == 'M' {
mineCnt ++
}
}
}
if mineCnt > 0 {
(*result)[y][x] = strconv.Itoa(mineCnt)[0]
} else {
(*result)[y][x] = 'B'
for i:=0;i<len(dir);i++ {
xi, yi := x+dir[i][0], y+dir[i][1]
if (xi >=0 && xi < len((*result)[0]) && yi >=0 && yi < len((*result))) {
dfs(yi, xi, result)
}
}
}
return;
}
dfs(cy, cx, &board)
return board
}
```
#### 532. K-diff Pairs in an Array ๐
```
func findPairs(nums []int, k int) int {
var result [][]int
sort.Ints(nums)
left := 0
right := left +1
lastInsert := []int{}
for left <= right && right < len(nums) {
diff := (nums[right] - nums[left])
if (diff == k) {
if (left != right && !reflect.DeepEqual(lastInsert, []int{nums[left], nums[right]})) {
result = append(result, []int{nums[left], nums[right]})
lastInsert = []int{nums[left], nums[right]}
}
right ++
}
if (diff < k) {
right ++
continue;
}
if (diff > k) {
left ++
continue;
}
}
return len(result)
}
```
#### 622. Design Circular Queue ๐
```
type MyCircularQueue struct {
queue *list.List
len int
limit int
}
func Constructor(k int) MyCircularQueue {
return MyCircularQueue{queue: list.New(), len: 0, limit: k}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if (this.queue.Len() == this.limit) {
return false
}
this.len += 1
this.queue.PushBack(value)
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if (this.queue.Front() == nil) {
return false
}
fmt.Println("back", this.queue.Front().Value)
this.queue.Remove(this.queue.Front())
this.len -= 1
return true
}
func (this *MyCircularQueue) Front() int {
if (this.queue.Front() == nil) {
return -1
}
return this.queue.Front().Value.(int)
}
func (this *MyCircularQueue) Rear() int {
if (this.queue.Back() == nil) {
return -1
}
return this.queue.Back().Value.(int)
}
func (this *MyCircularQueue) IsEmpty() bool {
return (this.queue.Len() == 0)
}
func (this *MyCircularQueue) IsFull() bool {
return (this.limit == this.len)
}
```
#### 637. Average of Levels in Binary Tree ๐ข
```
func averageOfLevels(root *TreeNode) []float64 {
result := []float64{}
layer_result := [][]float64{}
if (root == nil) {
return result
}
bfs(root, 0, &layer_result)
for i:=0;i<len(layer_result);i++ {
l_sum := float64(0)
for j:=0;j<len(layer_result[i]);j++ {
l_sum += float64(layer_result[i][j])
}
result = append(result, l_sum/float64(len(layer_result[i])))
}
return result
}
func bfs(root *TreeNode, layer int, res *[][]float64) {
if (root.Left != nil) {
bfs(root.Left, layer + 1, res)
}
if (root.Right != nil) {
bfs(root.Right, layer + 1, res)
}
for len((*res)) < layer + 1 {
(*res) = append((*res), []float64{})
}
(*res)[layer] = append((*res)[layer], float64(root.Val))
return;
}
```
#### 695. Max Area of Island ๐
> ่งฃ้ก้่ผฏ๏ผ ๅ *200.ๅณถๅถผๆธ้* ๏ผๅปบ็ซไธๅ้ ่จช่กจ(visited)ไพ็ขบ่ชๆฏๅฆ่จชๅ้ๆญค้ป๏ผไธๅ็ๅฐๆน็บๅขๅ ไธๅ่จ็ฎ้ข็ฉ็่ฎๆธ(areaCount)๏ผ่จ็ฎๆญคๆฌก่จชๅ้็จไธญ็้ข็ฉ็บๅคๅฐ๏ผๅ้
ๅmaximum function ๅ้ข็ฉๆๅคงๅผ๏ผๅณ็บ่งฃ็ญ
```
func maxAreaOfIsland(grid [][]int) int {
var maxArea int
visited := make([][]bool, len(grid))
for i:=0;i<len(grid);i++{
visited[i] = make([]bool, len(grid[i]))
}
var dfs func(y, x int, areaCount *int, grid [][]int, visited *[][]bool)
dfs = func(y, x int, areaCount *int, grid [][]int, visited *[][]bool) {
if y < 0 || y >= len(grid) || x < 0 || x >= len(grid[0]) || (*visited)[y][x] == true || grid[y][x] == 0 {
return
}
(*visited)[y][x] = true
*areaCount ++
dfs(y-1, x, areaCount, grid, visited)
dfs(y+1, x, areaCount, grid, visited)
dfs(y, x-1, areaCount, grid, visited)
dfs(y, x+1, areaCount, grid, visited)
}
for y:=0;y<len(grid);y++ {
for x:=0;x<len(grid[y]);x++ {
areaCount := 0
if !visited[y][x] && grid[y][x] == 1 {
dfs(y,x,&areaCount,grid,&visited)
maxArea = maximum(maxArea, areaCount)
}
}
}
return maxArea
}
func maximum(a, b int) int {
if a > b {return a}
return b
}
```
#### 700. Search in a Binary Search Tree ๐ข
==`Binary Search Tree`== ==`Binary Tree`==
```
func searchBST(root *TreeNode, val int) *TreeNode {
var result *TreeNode
for root != nil {
fmt.Println(root.Val)
if root.Val == val {
return root
} else if root.Val > val {
root = root.Left
} else {
root = root.Right
}
}
return result
}
```
#### 704. Binary Search ๐ข
```
func search(nums []int, target int) int {
l, r := 0, len(nums)-1
mid := 0
pos := -1
for l <= r {
mid = ( l + r ) /2
if (nums[mid] == target) {
pos = mid
}
if (target > nums[mid]) {
l = mid + 1
} else {
r = mid - 1
}
}
return pos
}
```
#### 724. Find Pivot Index ๐ข
```
func pivotIndex(nums []int) int {
if (len(nums) == 0) {
return -1
}
left_sum := 0
right_sum := 0
pos := 0
for i:=0;i<len(nums);i++ {
right_sum += nums[i]
}
for pos < len(nums) {
if (pos != 0) {
left_sum += nums[pos-1]
}
right_sum -= nums[pos]
if (left_sum == right_sum) {
return pos
}
pos ++
}
return -1
}
```
#### 733. Flood Fill ๐ข
```
func floodFill(image [][]int, sr int, sc int, color int) [][]int {
if (image[sr][sc] == color) {
return image
}
var dfs func(image *[][]int, sr int, sc int, preColor int, color int)
dfs = func(image *[][]int, sr int, sc int, preColor int, color int) {
if (*image)[sr][sc] == color {
return
}
if (*image)[sr][sc] != preColor {
return
}
(*image)[sr][sc] = color
if sr > 0 {
dfs(image, sr-1, sc, preColor, color)
}
if sr < len((*image))-1 {
dfs(image, sr+1, sc, preColor, color)
}
if sc > 0 {
dfs(image, sr, sc-1, preColor, color)
}
if sc < len((*image)[0])-1 {
dfs(image, sr, sc+1, preColor, color)
}
}
dfs(&image, sr, sc, image[sr][sc], color)
return image
}
```
#### 735. Asteroid Collision ๐
```
func asteroidCollision(asteroids []int) []int {
var live_asteroids []int
for i:=0;i<len(asteroids);i++ {
if (asteroids[i] > 0) {
live_asteroids = append(live_asteroids, asteroids[i])
} else {
live_asteroids = collide(asteroids[i], live_asteroids)
}
}
return live_asteroids
}
func collide(collide_asteroid int, live_asteroids []int) []int {
for len(live_asteroids) > 0 && collide_asteroid < 0 {
end := len(live_asteroids)-1
if (live_asteroids[end] < 0) {break}
if (collide_asteroid*-1 > live_asteroids[end]) {
live_asteroids = live_asteroids[:end]
} else if (collide_asteroid*-1 == live_asteroids[end]) {
live_asteroids = live_asteroids[:end]
collide_asteroid = 0
} else {
collide_asteroid = 0
}
}
if collide_asteroid != 0 {
live_asteroids = append(live_asteroids, collide_asteroid)
}
return live_asteroids
}
```
#### 744. Find Smallest Letter Greater Than Target ๐
```
func nextGreatestLetter(letters []byte, target byte) byte {
targetNum := int(target)
l, r := 0, len(letters)-1
mid := (l + r) / 2
diff := 999999
pos := 0
for l <= r {
if int(letters[mid]) > targetNum {
if (diff > (int(letters[mid]) - targetNum)) {
pos = mid
diff = int(letters[mid]) - targetNum
}
r = mid - 1
} else {
l = mid + 1
}
mid = (l+r)/2
}
return letters[pos]
}
func minimum(a, b int) int {
if (a > b) {return b}
return a
}
```
#### 852. Peak Index in a Mountain Array ๐
```
func peakIndexInMountainArray(arr []int) int {
l, r := 0, len(arr)-1
for l <= r {
mid := (l + r) /2
if (arr[mid] < arr[mid-1]) {
r = mid
} else if (arr[mid] < arr[mid+1]) {
l = mid
} else {
return mid
}
}
return 10
}
```
#### 876. Middle of the Linked List ๐ข
```
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func middleNode(head *ListNode) *ListNode {
total := 0
h1 := head
for head != nil {
total++
head = head.Next
}
middle := (total/2) + 1
i := 0
for h1 != nil {
i++
if (i == middle) {
break;
}
h1 = h1.Next
}
return h1
}
```
#### 897. Increasing Order Search Tree ๐ข
==`Stack`== ==`Tree`== ==`Depth-First Search`== ==`Binary Tree`==
```
func increasingBST(root *TreeNode) *TreeNode {
result := &TreeNode{}
cur := result
var dfs func(root *TreeNode)
dfs = func(root *TreeNode) {
if root == nil {return}
if root.Left != nil {
dfs(root.Left)
}
cur.Right = &TreeNode{root.Val, nil, nil}
cur = cur.Right
if root.Right != nil {
dfs(root.Right)
}
}
dfs(root)
return result.Right
}
```
#### 933. Number of Recent Calls ๐ข
```
type RecentCounter struct {
Res []int
}
func Constructor() RecentCounter {
return RecentCounter{}
}
func (this *RecentCounter) Ping(t int) int {
r_start, r_end := t - 3000, t
this.Res = append(this.Res, t)
i := 0
for i < len(this.Res) {
if (r_end >= this.Res[i] && this.Res[i] >= r_start) {
i++
} else {
this.Res = append(this.Res[:i], this.Res[i+1:]...)
}
}
return len(this.Res)
}
/**
* Your RecentCounter object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Ping(t);
*/
```
#### 1175. Prime Arrangements ๐ข
```
func numPrimeArrangements(n int) int {
const M = 1e9 + 7
composite_cnt := 0
prime_cnt := 0
// var result int64
result := 1
flag := "p"
for i:=1;i<=n;i++ {
if isPrime(i) {
prime_cnt ++
flag = "p"
} else {
composite_cnt ++
flag = "c"
}
if prime_cnt >= 2 && flag == "p" {
result *= prime_cnt
result %= M
}
if composite_cnt >= 2 && flag == "c" {
result *= composite_cnt
result %= M
}
}
return result
}
func isPrime(num int) bool {
if num % 2 == 0 {
return num == 2
} else if num > 2 {
for i:=3;i<=int(math.Sqrt(float64(num)));i++ {
if num % i == 0 {
return false
}
}
return true
}
return false
}
```
#### 1184. Distance Between Bus Stops ๐ข
==`Array`==
```
//่งฃ้ก้่ผฏ: ้ๆ้็่ท้ข = ็ธฝ่ท้ข - ้ ๆ้็่ท้ข
func distanceBetweenBusStops(distance []int, start int, destination int) int {
total := 0
for i:=0;i<len(distance);i++ {
total += distance[i]
}
cw_val := 0
if (start > destination) {
start, destination = destination, start
}
for i:=start;i<destination;i++ {
cw_val += distance[i]
}
return minimum(total - cw_val, cw_val)
}
func minimum(a int, b int) int {
if (a > b) {
return b
}
return a
}
```
#### 1200. Minimum Absolute Difference ๐ข
==`Array`== ==`Sorting`==
```
func minimumAbsDifference(arr []int) [][]int {
result := [][]int{}
min := 99999
sort.Ints(arr)
for i:=0;i<len(arr)-1;i++ {
if (arr[i+1] > arr[i]) {
if (len(result) == 0) {
min = arr[i+1]-arr[i]
result = append(result, []int{arr[i], arr[i+1]})
} else {
if (min > (arr[i+1]-arr[i])) {
min = (arr[i+1]-arr[i])
result = checkList([]int{arr[i], arr[i+1]}, result)
} else if (min == (arr[i+1]-arr[i])) {
result = append(result, []int{arr[i], arr[i+1]})
}
}
}
}
return result
}
func checkList(target []int, list [][]int) [][]int {
i:=0
for i<len(list) {
if ((list[i][1] - list[i][0]) > (target[1] - target[0])) {
list = append(list[:i], list[i+1:]...)
} else {
i++
}
}
return append(list, target)
}
```
#### 1480. Running Sum of 1d Array ๐ข
==`Array`== ==`Prefix Sum`==
```
func runningSum(nums []int) []int {
sum := 0
for i:=0;i<len(nums);i++ {
nums[i] += sum
sum = nums[i]
}
return nums
}
```
#### 2336. Smallest Number in Infinite Set ๐
```
type SmallestInfiniteSet struct {
removeList map[int]bool
}
func Constructor() SmallestInfiniteSet {
return SmallestInfiniteSet{removeList: make(map[int]bool)}
}
func (this *SmallestInfiniteSet) PopSmallest() int {
for i:=1;i<=math.MaxInt;i++ {
if _, ok := this.removeList[i]; !ok {
this.removeList[i] = true
return i
}
}
return 0
}
func (this *SmallestInfiniteSet) AddBack(num int) {
delete(this.removeList, num)
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.PopSmallest();
* obj.AddBack(num);
*/
```
#### 2389. Longest Subsequence With Limited Sum ๐ข
```
func answerQueries(nums []int, queries []int) []int {
var result []int
sort.Ints(nums)
total := 0
for _, v := range nums {
total += v
}
for i:=0;i<len(queries);i++ {
tmp_total := total
for j:=len(nums)-1;j>=0;j-- {
if (tmp_total <= queries[i]) {
result = append(result, j+1)
break;
} else {
tmp_total -= nums[j]
}
}
if (len(result) != i+1) {
result = append(result, 0)
}
}
return result
}
```
Sign in with Wallet
Connect another wallet