I had a day filled with coding. I did eight leetcoding challenges for the May challenge (which I didn’t know existed until today), and started on the binary search card. Every single one of these is ranked Easy.
This is pretty basic stuff. I chose the recursive solution for binary search over the iterative solution.
func search(nums []int, target int) int {
return searchRecursive(nums, target, 0, len(nums))
}
func searchRecursive(nums []int, target, begin, end int) int {
if begin == end {
return -1
}
midpoint := (begin + end) / 2
if target > nums[midpoint] {
return searchRecursive(nums, target, midpoint+1, end)
} else if target < nums[midpoint] {
return searchRecursive(nums, target, begin, midpoint)
}
return midpoint
}As for the challenges, they’re all pretty easy and self-explanatory. One I thought was really interesting was the “bit shifting” problem.
This one I thought was really interesting because it says you can’t brute force it, but it let me brute force it. This is why I decided to do the Binary Search card. Apparently, the challenge is supposed to fail you for brute forcing, and only approve binary searches - but I’m guessing Go is fast enough to where it couldn’t detect that I just brute forced it :)
/**
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/
func firstBadVersion(n int) int {
for i := 0; i <= n; i++ {
if isBadVersion(i) {
return i
}
}
return -1
}This is a classic. I’ve probably solved this 3 or 4 times before. Probably the easiest programming challenge known to man.
func numJewelsInStones(J string, S string) int {
count := 0
for _,i := range S {
for _,j := range J {
if i == j {
count++
}
}
}
return count
}There’s a bit of a gotcha if you don’t use built-ins (which I tried not to, IE “contains” method), but this is still a 5 minute problem tops.
func canConstruct(ransomNote string, magazine string) bool {
for _,v := range ransomNote {
replaced := false
for _,r := range magazine {
if r == v {
magazine = strings.Replace(magazine, string(r), "", 1)
replaced = true
break
}
}
if !replaced {
return false
}
}
return true
}From all the binary work I’ve done in college, I would have figured this would be simple. You’re just shifting the bits, how hard could it be? Well, it’s not extremely challenging, but it took some research into the bits package. Note: This can also be done without the bits package, but it’s not as clean.
func findComplement(num int) int {
return num ^ ((1 << bits.Len(uint(num))) - 1)
}Again, not a hard problem so I decided to operate entirely on bytes and not use any built-ins. Turned out to be an extremely performant solution, faster than 90% of other submissions.
func firstUniqChar(s string) int {
if len(s) == 1 {
return 0
}
for i := 0; i < len(s); i++ {
repeated := false
current := s[i]
for j := 0; j < len(s); j++ {
if j == i {
continue
}
if current == s[j] {
repeated = true
break
}
}
if !repeated {
return i
}
}
return -1
}Another straightforward problem. The intuitive solution uses a map and is O(n).
func majorityElement(nums []int) int {
intmap := make(map[int]int)
for i := range nums {
intmap[nums[i]]++
}
max := 0
key := 0
for i,v := range intmap {
if v > max {
max = v
key = i
}
}
return key
}I absolutely lost it during this problem. This really should not be difficult, but Go refused to provide a float from integer division unless I casted literally every single element into a float64. I find this is one of the things that irritates me about using Go as compared to Java. I could really write an entire blog post at this point about things in Go that I’ve found that infuriate me. Among this would be lack of generics and the interface implementation.
func checkStraightLine(coordinates [][]int) bool {
var slope float64 = float64(coordinates[1][1] - coordinates[0][1]) / float64(coordinates[1][0] - coordinates[0][0])
for i := 1; i < len(coordinates) - 1; i++ {
tmpSlope := float64(coordinates[i+1][1] - coordinates[i][1]) / float64(coordinates[i+1][0] - coordinates[i][0])
if tmpSlope != slope {
return false
}
}
return true