grind75

package
v0.0.0-...-eb8a366 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 10, 2023 License: Unlicense Imports: 9 Imported by: 0

Documentation

Overview

Package grind75 is 75 questions on leetCode https://www.techinterviewhandbook.org/grind75 or see grind75.pdf with links to leetcode

Example (CanConstruct) 
fmt.Printf("%#v ", canConstruct("Hello", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct("HELLO", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct("abcdef", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct("Hello", "tere lolo"))
fmt.Printf("%#v ", canConstruct2("Hello", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct2("HELLO", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct2("abcdef", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct2("Hello", "tere lolo"))
fmt.Printf("%#v ", canConstruct3("Hello", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct3("HELLO", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct3("abcdef", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct3("Hello", "tere lolo"))
fmt.Printf("%#v ", canConstruct4("Hello", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct4("HELLO", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct4("abcdef", "Hi there lolo"))
fmt.Printf("%#v ", canConstruct4("Hello", "tere lolo"))

Output:

true true false false true true false false true true false false true true false false
Example (CanConstruct2) 
ransom := "Hello"
magazine := "Hi there lolo"
fmt.Printf("Value: %#v\n", canConstruct2(ransom, magazine))

Output:

Value: true

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func AddBinary 

func AddBinary(a string, b string) (res string)

AddBinary add too a string of binaries "11"+"1"="100". Arbitrary length

func ClimbStairs 

func ClimbStairs(n int) int

ClimbStairs 0070 in how many distinct ways can you climb to the top of n stairs? This a iterativel fast version.

The number of ways to climb the stairs is equal to the sum of the number of ways to climb the stairs from the previous step and the number of ways to climb the stairs from two steps ago.

In other words, if we let f(n) be the number of ways to climb the stairs starting from the nth step, then we have the recurrence: f(n) = f(n - 1) + f(n - 2)

We can start the recursion with the base cases: f(1) = 1 (there is only 1 way to climb 1 step) f(2) = 2 (there are 2 ways to climb 2 steps: 1+1 or 2)

Then, we can use the recurrence to compute the number of ways to climb the stairs for n steps:

f(n) = f(n - 1) + f(n - 2) = f(n - 2) + f(n - 3) + f(n - 2) = f(n - 3) + f(n - 4) + f(n - 2) + f(n - 2) = ...

This is known as the Fibonacci sequence, and it has the closed-form solution: f(n) = ((1 + sqrt(5))/2)^n - ((1 - sqrt(5))/2)^n where sqrt(5) is the square root of 5.

func ClimbStairsRecursive 

func ClimbStairsRecursive(n int) int

ClimbStairsRecursive This the slow recursive version! In how many distinct ways can you climb to the top of n stairs?

func CoinChange 

func CoinChange(coins []int, amount int) int

CoinChange return best coin denominations mix

func ContainDuplicate 

func ContainDuplicate(nums []int) (res bool)

ContainDuplicate true if array has duplicate values

func DiameterOfBinaryTree 

func DiameterOfBinaryTree(root *ds.TreeNode) int

DiameterOfBinaryTree return the length of the diameter of the tree.

func DistThreeSum 

func DistThreeSum(nums []int) [][]int

DistThreeSum return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

func DistansToZeroInMatrix 

func DistansToZeroInMatrix(mat [][]int) (res [][]int)

DistansToZeroInMatrix return distans of nearest o for each cell Exampel Input Result 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 2 1 2,1 has 2 because that how meen sideway or up that is need to get to 0

func EvalRPN 

func EvalRPN(tokens []string) (res int)

EvalRPN reverse polish notation like "2","1","+","3","*" to 6

func FloodFill 

func FloodFill(image [][]int, sr, sc, color int) [][]int

FloodFill 0733 fills the region starting at point (sr,sc) with color and returns the resulting grid. Iterative version using array of position.

Example 
grid2 := FloodFill(testGrid, 0, 0, 2)
printGrid(grid2)

Output:

222
220
201

func HasCycle 

func HasCycle(head *ds.ListNode) bool

HasCycle 0141 check for cycle in list returning true if cycle exist

Example 
// Create test TreeNode
l := &ds.ListNode{Val: 3}
l.Next = &ds.ListNode{Val: 2}
loop := l.Next
l = l.Next
l.Next = &ds.ListNode{Val: 0}
l = l.Next
l.Next = loop
fmt.Println(HasCycle(l))

// Create test TreeNode
l = &ds.ListNode{Val: 3}
l.Next = &ds.ListNode{Val: 2}
l = l.Next
l.Next = &ds.ListNode{Val: 0}
l = l.Next

fmt.Println(HasCycle(l))

Output:

true
false

func InsertInterval 

func InsertInterval(intervals [][]int, newInterval []int) (res [][]int)

InsertInterval add new interval to a array of non-overlapping intervals Example [][]int{{1,3},{6,9}} adding []int{2,5} only extend 1,3 to 1,5 an result in [][]int{{1,5},{6,9}} [][]int{{1,2},{3,5},{6,7},{8,10},{12,16}} adding {4,8} [][]int{{1,2},{3,10},{12,16}} Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

func InvertTree 

func InvertTree(root *t.TreeNode) *t.TreeNode

InvertTree 0226 Resurcive Input: root = [2,1,3] Output: [2,3,1]

Example 
// New binary t1
t1 := new(t.TreeNode)

t1.Val = 4
t1.Left = new(t.TreeNode)
t1.Right = new(t.TreeNode)
t1.Left.Val = 2
t1.Right.Val = 7

t1.Left.Left = new(t.TreeNode)
t1.Left.Right = new(t.TreeNode)
t1.Right.Left = new(t.TreeNode)
t1.Right.Right = new(t.TreeNode)

t1.Left.Left.Val = 1
t1.Left.Right.Val = 3
t1.Right.Left.Val = 6
t1.Right.Right.Val = 9

fmt.Println(t1.PrintBreadthFirst(t1))
t1 = InvertTree(t1)
fmt.Println(t1.PrintBreadthFirst(t1))

t2 := new(t.TreeNode)

t2.Val = 2
t2.Left = new(t.TreeNode)
t2.Right = new(t.TreeNode)
t2.Left.Val = 1
t2.Right.Val = 3

t2.PrintInOrder()
fmt.Println()
t2 = InvertTree(t2)
t2.PrintInOrder()
fmt.Println()

// TODO Bug in InsertLeft and InsertRight does not create nodes
t3 := t.NewTreeNode()
t3.Val = 4
t3.InsertLeft(2)
t3.InsertLeft(1)
t3.InsertLeft(6)
t3.InsertRight(7)
t3.InsertRight(3)
t3.InsertRight(9)

t3.PrintInOrder()
fmt.Println()
t3 = InvertTree(t3)
t3.PrintInOrder()
fmt.Println()

// Don't not remove part below INCLUDE empty line it part Example testing

// Disabled test with this comment

Output:

func InvertTreeIterative 

func InvertTreeIterative(root *t.TreeNode) *t.TreeNode

InvertTreeIterative Input: root = [2,1,3] Output: [2,3,1] Not realy need for this leetcode

func IsAnagram 

func IsAnagram(s, t string) bool

IsAnagram 0242 Two word have same letters but diffent order. "nagaram" is anagram of "anagram".

func IsBalanced 

func IsBalanced(root *ds.TreeNode) bool

IsBalanced 0110 test if a simple tree node is balanced

Example 
// Create test TreeNode
root := &ds.TreeNode{Val: 1}
root.Left = &ds.TreeNode{Val: 2}
root.Right = &ds.TreeNode{Val: 3}
root.Left.Left = &ds.TreeNode{Val: 4}
root.Left.Right = &ds.TreeNode{Val: 5}
fmt.Println(IsBalanced(root))
root.Left.Right.Right = &ds.TreeNode{Val: 10}
fmt.Println(IsBalanced(root))

Output:

true
false

func IsPalindrome 

func IsPalindrome(s string) bool

IsPalindrome 0125 check if the alfanumerics is palindrome in lowercase returning true if so

func IsValid 

func IsValid(s string) bool

IsValid 0020. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

func IsValidBST 

func IsValidBST(root *ds.TreeNode) bool

IsValidBST valid binary tree as binary search tree

func Kclosest 

func Kclosest(res [][]int, k int) [][]int

Kclosest sort input array after distant to zero (0,0) return k part of array Original array is intact BUT not it's order!

func Lca 

func Lca(root, p, q *t.TreeNode) *t.TreeNode

Lca 0235 Lowest Common Ancestor of a Binary Search Tree

func LevelOrder 

func LevelOrder(t *ds.TreeNode) (res [][]int)

LevelOrder return TreeNode as [][]int

func LongestPalindrome 

func LongestPalindrome(s string) (res int)

LongestPalindrome 0409 how many letter in palindrome char mix made by they letter, case senitive Support only rune until 256 skip char above

func MajorityElement 

func MajorityElement(nums []int) int

MajorityElement what number that is the moste in a list Example []int{2,2,1,1,1,2,2} hase four number of twos result in : 2

func ManhatDist 

func ManhatDist(mat [][]int, row, col int) (minDist int)

ManhatDist travers and return Manhattan distance helper for updateMatrix

func MaxDepth 

func MaxDepth(root *ds.TreeNode) int

MaxDepth return its maximum depth of the binary tree TreeNode

func MaxProfit 

func MaxProfit(prices []int) (maxprof int)

MaxProfit 0121 Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

func MaxSubArray 

func MaxSubArray(nums []int) int

MaxSubArray 0053 biggest sum of sub arrays in array Exampel: fmt.Println(MaxSubArray([-2,1,-3,4,-1,2,1,-5,4]) Prints out : 6

func MergeTwoSortedLists 

func MergeTwoSortedLists(l1 *ds.ListNode, l2 *ds.ListNode) *ds.ListNode

MergeTwoSortedLists 0021 Join two sorted list to one. l1+l2=l2 Warning corrupt l1 and changes l2 to two the new join list

func MiddleNode 

func MiddleNode(head *ds.ListNode) *ds.ListNode

MiddleNode return pointer to middle of list

func NumIslands 

func NumIslands(grid [][]byte) int

NumIslands number of islands of 1 in matrix with sea as 0 Source: https://ljun20160606.github.io/leetcode/algorithms/200/

func ProductExceptSelf 

func ProductExceptSelf(nums []int) (res []int)

ProductExceptSelf return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

func ReverseList 

func ReverseList(head *ds.ListNode) *ds.ListNode

ReverseList 0206 Reverse a linked list 1,2,3,4,5 -> 5,4,3,2,1 This leadves a empty head behind. You have to nil your pointer to Head after this it, look in example below Example : listOfNodesReversed := ReverseList(listOfNodes) listOfNodes = nil

Example 
l := ds.NewListNode(1)
l.Next = ds.NewListNode(2)
l.Next.Next = ds.NewListNode(3)

nl := ReverseList(l)
l = nil
if l != nil {
	log.Println(l.Val, l.Next)
}
fmt.Println(nl)

Output:

Node: 0 Value: 3
Node: 1 Value: 2
Node: 2 Value: 1

func Search(nums []int, target int) int

Search 0704 Given an array of integers nums which is sorted in ascending order, and an integer target, search target in nums. If target exists, then return its index. Otherwise, return -1.

func SearchRotatedSortedArray 

func SearchRotatedSortedArray(nums []int, target int) int

SearchRotatedSortedArray give the index of a target in a pivot sorted array

func SortString 

func SortString(w string) string

SortString Sort a string alphanumeric order

func SplitOnLetter 

func SplitOnLetter(s string) (res []string)

SplitOnLetter split a string on new letter "abccccdd" will result in [a b ccc dd] "abcabc" will split in "aa","bb","cc"

func TwoSum 

func TwoSum(nums []int, target int) []int

TwoSum 0001. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Types

type Node 

type Node struct {
	Val       int
	Neighbors []*Node
}

Node Test case graph. Using adjacency list is a collection of unordered lists used to represent a finite graph.

func CloneGraph 

func CloneGraph(node *Node) (res *Node)

CloneGraph return a deep copy (clone) of the graph.

Example 
// Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
// Output: [[2,4],[1,3],[2,4],[1,3]]

// Clonked declaration with out methods...
var n [8]Node

for i := range n {
	n[i].Val = i + 2
}

var m Node
m.Neighbors = []*Node{
	&n[0],
	&n[1],
	&n[2],
	&n[3],
	&n[4],
	&n[5],
	&n[6],
	&n[7],
}

// fmt.Println(m)
o := CloneGraph(&m)
for i := range o.Neighbors {
	fmt.Printf("%d ", o.Neighbors[i].Val)
}
fmt.Println()

Output:

2 3 4 5 6 7 8 9

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.