65. Valid Number

Version #1 Go library

10.61 % 

import (
    "strconv"
    "strings"
)
func isNumber(s string) bool {
    _, err := strconv.ParseFloat(strings.TrimSpace(s), 64)
    return err == nil || strings.Contains(err.Error(), "value out of range")
}

[Go]Notes

Defer

A defer statement defers the execution of a function until the surrounding function returns.

The deferred call's arguments are evaluated immediately, but the function call is not executed until the surrounding function returns.

Closures

https://www.calhoun.io/5-useful-ways-to-use-closures-in-go/

[Go]Exercise: Loops and Functions

package main

import (
"fmt"
"math"
)

const Delta = 1e-10
func Sqrt(x float64) float64 {
i := 0
z := float64(1)
prev := z
for i < 10 {
z -= (z * z - x) / (2 * z)
fmt.Println(z)
if math.Abs(z - prev) < Delta {
break;
}
prev = z
i++
}
return z
}

func main() {
fmt.Println(Sqrt(2))
}

[Go]Methods are functions

Methods
A method is a function with a special receiver argument.

package main

import (
"fmt"
"math"
)

type Vertex struct {
X, Y float64
}

func (v Vertex) Abs() float64 {
return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

func main() {
v := Vertex{3, 4}
fmt.Println(v.Abs())
}

------------------------------------------------------------------
Regular Function
package main

import (
"fmt"
"math"
)

type Vertex struct {
X, Y float64
}

func Abs(v Vertex) float64 {
return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

func main() {
v := Vertex{3, 4}
fmt.Println(Abs(v))
}

[Go]Fibonacci closure

Version #2 "Go" Version

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
prev := -1
curr := 1
return func() int {
prev, curr = curr, prev + curr
return curr
}
}

func main() {
f := fibonacci()
for i := 0; i < 10; i++ {
fmt.Println(f())
}
}

Version #1 "Java" Version
package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
prev := 0
curr := 1
return func() int {
next := prev + curr
prev = curr
curr = next
return prev
}
}

func main() {
f := fibonacci()
for i := 0; i < 10; i++ {
fmt.Println(f())
}
}

659. Split Array into Consecutive Subsequences

Greedily append the element to previous sequences
Always try to append
Only create a single sequence if we are not able to append

class Solution {
    public boolean isPossible(int[] nums) {
        // For every distinct number, we keep track of then consective sequence end with num
        // whose length are 1 2 3
        int prev = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;
        for (int i = 0; i < nums.length; i++) {
            int curr = nums[i];
            int c1 = 0, c2 = 0, c3 = 0;
            int count = 1;
            // accumulate numbers with same value as curr
            while (i < nums.length - 1 && nums[i + 1] == curr) {
                count++;
                i++;
            }
           
            // cannot append to previous number
            if (curr != prev + 1) {
                if (p1 != 0 || p2 != 0) return false;
                c1 = count;
            } else { // append to p1 first
                if (count < p1 + p2) return false;
                c2 = p1;
                c3 = p2 + Math.min(p3, count - (p1 + p2));
                c1 = Math.max(0, count - (p1 + p2 + p3));
            }
            prev = curr;
            p1 = c1;
            p2 = c2;
            p3 = c3;
        }
        return p1 == 0 && p2 == 0;
    }
}

499. The Maze III

Version #1 Dijastra

几个需要注意的点
首先visited是必须要有的，否则impossible就是infinite loop
但是不应该是个boolean而应该是一个int，因为一个点可以通过不同的path被到达，只要后来的dist <= visited[ny][nx]都可以
因为hole不一定是球可以停住的状态，所以第一次经过不一定是最佳答案
需要存起来然后每次经过的话都去更新

 73.91 %
class Solution {
    class Point implements Comparable<Point> {
        int x, y, dist;
        String path;
        public Point(int y, int x, int dist, String path) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.path = path;
        }
        @Override
        public int compareTo(Point p) {
            if (this.dist != p.dist) {
                return this.dist - p.dist;
            } else {
                return this.path.compareTo(p.path);
            }
        }
    }
    private int rows, cols;
    private int[] dx = new int[]{1, 0, -1, 0};
    private int[] dy = new int[]{0, -1, 0, 1};
    private char[] direction = new char[]{'r', 'u', 'l', 'd'};
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        // priorityQueue of int[] poisition + int dist so far
        // when we pop one element out, we have four choices
        // 1.minHeap ordered by dist
        // 2.original point into minHeap
        // polling from minHeap, try 4 directions and walk
        // if we can walk to that direction (move more than 0 step, destination not visited)
        // if we see hole while rolling, return the final steps directly
        // offer into minHeap with destination position and new distance
       
        if (maze == null || maze.length == 0 || maze[0] == null || maze[0].length == 0) {
            return "impossible";
        }
        PriorityQueue<Point> minHeap = new PriorityQueue<>();
        rows = maze.length;
        cols = maze[0].length;
        int[][] visited = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        minHeap.offer(new Point(ball[0], ball[1], 0, ""));
        visited[ball[0]][ball[1]] = 0;
        Point minResult = null;
        while (!minHeap.isEmpty()) {
            Point curr = minHeap.poll();
            int x = curr.x;
            int y = curr.y;
            int dist = curr.dist;
            if (minResult != null && dist > minResult.dist) break;
            String path = curr.path;
            for (int i = 0; i < 4; i++) {
                // try to roll to direction
                int step = 0;
                int nx = x, ny = y;
                while (isValid(ny + dy[i], nx + dx[i]) && maze[ny + dy[i]][nx + dx[i]] == 0) {
                    ny += dy[i];
                    nx += dx[i];
                    step++;
                    if (ny == hole[0] && nx == hole[1]) {
                        Point temp = new Point(ny, nx, dist + step, path + direction[i]);
                        if (minResult == null || temp.compareTo(minResult) < 0) {
                            minResult = temp;
                        }
                    }
                }
                if (step > 0 && dist + step <= visited[ny][nx]) {
                    visited[ny][nx] = dist + step;
                    minHeap.offer(new Point(ny, nx, dist + step, path + direction[i]));
                }
               
            }
        }
        return minResult == null ? "impossible" : minResult.path;
    }
   
    private boolean isValid(int y, int x) {
        return x >= 0 && x < cols && y >= 0 && y < rows;
    }
}