953. Verifying an Alien Dictionary

 二刷 07/2022

Version #2 HashMap

Time O(MN)

Space O(26) ~ O(1)

Runtime: 2 ms, faster than 36.78% of Java online submissions for Verifying an Alien Dictionary.

Memory Usage: 43.1 MB, less than 9.85% of Java online submissions for Verifying an Alien Dictionary.

class Solution {

    public boolean isAlienSorted(String[] words, String order) {

        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < order.length(); i++) {

            map.put(order.charAt(i), i);

        }

        for (int i = 1; i < words.length; i++) {

            if (!smaller(words[i - 1], words[i], map)) {

                return false;

            }

        }

        return true;

    }

    

    private boolean smaller(String a, String b, Map<Character, Integer> map) {

        int pa = 0, pb = 0;

        while (pa < a.length() && pb < b.length()) {

            char ca = a.charAt(pa);

            char cb = b.charAt(pb);

            if (ca == cb) {

                pa++;

                pb++;

                continue;

            }

            if (map.get(ca) < map.get(cb)) {

                return true;

            } else {

                return false;

            }

        }

        return a.length() <= b.length();

    }

}

一刷

Version #1 Array as HashMap

Runtime: 0 ms, faster than 100.00% of Java online submissions for Verifying an Alien Dictionary.

Memory Usage: 37.3 MB, less than 94.58% of Java online submissions for Verifying an Alien Dictionary. 

一开始想复杂了

其实只要比较相邻的word就可以了, 因为smaller than是transitive的

if a < b && b < c we can infer that a < c

Time O(word count * avg word length)

Space O(1) 

class Solution {

    public boolean isAlienSorted(String[] words, String order) {

        char[] map = new char[26];

        for (int i = 0; i < order.length(); i++) {

            map[order.charAt(i) - 'a'] = (char)('a' + i); 

        }

        String prev = null;

        for (String word : words) {

            if (prev != null && !smaller(prev, word, map)) {

                return false;

            }

            prev = word;

        }

        return true;

    }

    

    private boolean smaller(String a, String b, char[] map) {

        int i = 0;

        for (i = 0; i < a.length() && i < b.length(); i++) {

            char ca = map[a.charAt(i) - 'a'];

            char cb = map[b.charAt(i) - 'a'];

            if (ca != cb) {

               return ca < cb;

            }

            // continue comparing if ca == cb

        }

        // apple

        // app

        if (i < a.length()) {

            return false;

        }

       // Can be optimized to: return a.length() <= b.length()

        return true;

    }

}

621. Task Scheduler

Version #1 

好久没写java了，自己磕磕绊绊写了一版

用到了hashmap，没有利用tasks[i] is upper-case English letter这个条件

Time O(n)

Space O(1)

class Solution {

    public int leastInterval(char[] tasks, int n) {

        // A -> x -> x -> A -> x -> x -> A

        // (count(max chars) - 1) * (n + 1) + #chars that have max count

        if (n == 0) {

            return tasks.length;

        }

        int maxCount = 0;

        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < tasks.length; i++) {

            int cnt = map.getOrDefault(tasks[i], 0) + 1;

            maxCount = Math.max(maxCount, cnt);

            map.put(tasks[i], cnt);

        }

        int maxTasks = 0;

        for (Integer cnt : map.values()) {

            if (maxCount == cnt) {

                maxTasks++;

            }

        }

        return Math.max((maxCount - 1) * (n + 1) + maxTasks, tasks.length);

    }

}

Version #2 Optimized solution

Time O(n)

Space O(1)

这个testcase两次都错了

["A","A","A","B","B","B", "C","C","C", "D", "D", "E"]

2

class Solution {

    public int leastInterval(char[] tasks, int n) {

        // calculate the characters with max count

        int[] counts = new int[26];

        int maxCount = 0;

        int maxCountCharNum = 0;

        for (char task : tasks) {

            int i = task - 'A';

            counts[i]++;

            if (counts[i] > maxCount) {

                maxCountCharNum = 1;

                maxCount = counts[i];

            } else if (counts[i] == maxCount) {

                maxCountCharNum++;

            }

        }

        // n = 2

        // maxCountCharNum

        // (A B C) _divider_ (A B C) _ (A B C)

        // maxChars need (maxCount - 1) dividers to be seaparated

        // divider length = n - maxCountCharNum + 1

        // e.g. n = 2, maxCountCharNum = 1

        // A _ _ A _ _  divider = 2-1+1=2

        // if divider length <= 0 it means we don't need idle

        // e.g. n = 1, maxCountCharNum = 2

        // A B A B

        // so divider length = Math.max(0, n - maxCountCharNum + 1)

        // left chars = total chars - maxCountCharNum * maxCount

        // white spaces = divider length * (maxCount - 1) - left chars

        int idleCount = Math.max(0, n - maxCountCharNum + 1) * (maxCount - 1) - (tasks.length - maxCountCharNum * maxCount);

        return tasks.length + Math.max(0, idleCount);

    }

}

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())
}
}