dmitry.labutin
BAN USERInterval tree problem
package main
import "fmt"
type Interval struct {
Start int
End int
}
type IntervalTree struct {
Val Interval
Max int
Left *IntervalTree
Right *IntervalTree
}
func Insert(root *IntervalTree, val Interval) *IntervalTree {
if root == nil {
return &IntervalTree{
Val: val,
Max: val.End,
}
}
if val.Start < root.Val.Start {
root.Left = Insert(root.Left, val)
} else {
root.Right = Insert(root.Right, val)
}
if root.Max < val.End {
root.Max = val.End
}
return root
}
func CountIntervals(root *IntervalTree, search int) int {
if root == nil || root.Max < search {
return 0
}
res := 0
if root.Val.Start <= search && root.Val.End >= search {
res = 1
}
res += CountIntervals(root.Left, search)
res += CountIntervals(root.Right, search)
return res
}
func BuildTree(intervals []Interval) *IntervalTree {
var root *IntervalTree
for _, interval := range intervals {
root = Insert(root, interval)
}
return root
}
func main() {
root := BuildTree([]Interval{
Interval{1, 1234},
Interval{2, 1234},
})
fmt.Println(CountIntervals(root, 2))
fmt.Println(CountIntervals(root, 1))
fmt.Println(CountIntervals(root, 1235))
root = BuildTree([]Interval{
Interval{15, 20},
Interval{10, 30},
Interval{5, 20},
Interval{12, 15},
Interval{17, 19},
Interval{30, 40},
})
fmt.Println(CountIntervals(root, 18))
fmt.Println(CountIntervals(root, 30))
fmt.Println(CountIntervals(root, 14))
fmt.Println(CountIntervals(root, 4))
fmt.Println(CountIntervals(root, 44))
}
package main
import (
"fmt"
)
type Tree struct {
val int
left *Tree
right *Tree
}
func findSequence(root *Tree) []int {
lTry := findSequenceHelper(root.left)
rTry := findSequenceHelper(root.right)
var res []int
if len(lTry) > len(rTry) {
res = lTry
} else {
res = rTry
}
cTry := findSequenceHelper(root)
if len(cTry) > len(res) {
res = cTry
}
return res
}
func findSequenceHelper(root *Tree) []int {
res1 := lessSequence(root.left, root.val)
res1 = append(res1, root.val)
res1 = append(res1, graterSequence(root.right, root.val)...)
res2 := graterSequence(root.left, root.val)
res2 = append([]int{root.val}, res2...)
res2 = append(res2, lessSequence(root.right, root.val)...)
if len(res1) > len(res2) {
return res1
} else {
return res2
}
}
func lessSequence(root *Tree, max int) []int {
if root == nil || root.val != max-1 {
return []int{}
}
lTry := lessSequence(root.left, root.val)
rTry := lessSequence(root.right, root.val)
if len(lTry) > len(rTry) {
return append(lTry, root.val)
} else {
return append(rTry, root.val)
}
}
func graterSequence(root *Tree, min int) []int {
if root == nil || root.val != min+1 {
return []int{}
}
lTry := graterSequence(root.left, root.val)
rTry := graterSequence(root.right, root.val)
res := []int{root.val}
if len(lTry) > len(rTry) {
return append(res, lTry...)
} else {
return append(res, rTry...)
}
}
func main() {
root := &Tree{
val: 2,
left: &Tree{
val: 1,
left: &Tree{
val: 0,
left: &Tree{
val: 10,
},
right: &Tree{
val: -1,
},
},
},
right: &Tree{
val: 3,
left: &Tree{
val: 4,
right: &Tree{
val: 5,
left: &Tree{
val: 6,
},
},
},
right: &Tree{
val: 7,
},
},
}
fmt.Println(findSequence(root))
}
viv, try to execute your solution with 10 elements.
- dmitry.labutin February 26, 2018package main
import (
"fmt"
"math"
)
type LList struct {
val int
next *LList
}
type Tree struct {
val int
left *Tree
right *Tree
}
func convert(head *LList) *Tree {
tmp := head
count := 0
for tmp != nil {
count++
tmp = tmp.next
}
if count == 0 {
return nil
}
return convertHelper(head, count)
}
func convertHelper(head *LList, count int) *Tree {
if count == 0 {
return nil
}
if count == 1 {
return &Tree{val: head.val}
}
levels := uint(math.Log2(float64(count)))
full := 1<<levels - 1
lastLevel := count - full
if lastLevel > (full+1)/2 {
lastLevel = (full + 1) / 2
}
middle := (full-1)/2 + lastLevel
middleOrig := middle
tmp := head
for middle > 0 {
tmp = tmp.next
middle--
}
root := &Tree{val: tmp.val}
root.left = convertHelper(head, middleOrig)
root.right = convertHelper(tmp.next, count-1-middleOrig)
return root
}
func main() {
head := fillList(13)
printList(head)
fmt.Println()
printLevelTree(convert(head))
}
func height(root *Tree) int {
if root == nil {
return 0
}
lh := height(root.left)
rh := height(root.right)
if lh < rh {
return rh + 1
} else {
return lh + 1
}
}
func printLevelTree(root *Tree) {
h := height(root)
for i := 1; i <= h; i++ {
printGivenLevel(root, i)
fmt.Println()
}
}
func printGivenLevel(root *Tree, level int) {
if root == nil {
return
}
if level == 1 {
fmt.Print(root.val, " ")
return
}
printGivenLevel(root.left, level-1)
printGivenLevel(root.right, level-1)
}
func fillList(count int) *LList {
var head *LList
for i := count; i > 0; i-- {
newNode := &LList{val: i, next: head}
head = newNode
}
return head
}
func printList(root *LList) {
for root != nil {
fmt.Print(root.val, " ")
root = root.next
}
}
package main
import "fmt"
type Node struct {
Value int
Children []*Node
}
func PrintTree(root *Node) {
fmt.Print(root.Value, " -> {")
for _, node := range root.Children {
fmt.Print(node.Value, " ")
}
fmt.Println("}")
for _, node := range root.Children {
PrintTree(node)
}
}
func MakeTree(matrix [][]bool) *Node {
nodes := make([]*Node, len(matrix))
hasParent := make([]bool, len(matrix))
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix); j++ {
if matrix[i][j] {
if nodes[i] == nil {
nodes[i] = &Node{i, []*Node{}}
}
if nodes[j] == nil {
nodes[j] = &Node{j, []*Node{}}
}
nodes[i].Children = append(nodes[i].Children, nodes[j])
hasParent[j] = true
}
}
}
for i := 0; i < len(hasParent); i++ {
if !hasParent[i] {
return nodes[i]
}
}
return nil
}
func main() {
matrix := make([][]bool, 6)
matrix[0] = []bool{false, true, true, true, false, false}
matrix[1] = []bool{false, false, false, false, false, false}
matrix[2] = []bool{false, false, false, false, true, true}
matrix[3] = []bool{false, false, false, false, false, false}
matrix[4] = []bool{false, false, false, false, false, false}
matrix[5] = []bool{false, false, false, false, false, false}
PrintTree(MakeTree(matrix))
}
Marcello Ghali,
How about if H will have child B and E will not have any children?
package main
import "fmt"
type LList struct {
Value int
Next *LList
}
func Print(head *LList) {
for head != nil {
fmt.Printf("%d ", head.Value)
head = head.Next
}
fmt.Println()
}
func Revers(head *LList, K int) *LList {
oldHead := head
newHead := head
var next, nextNext *LList
if head != nil {
next = head.Next
}
if next != nil {
nextNext = next.Next
}
head.Next = nil
for next != nil {
next.Next = head
if nextNext != nil {
head, next, nextNext = next, nextNext, nextNext.Next
} else {
head, next, nextNext = next, nextNext, nil
}
K--
if K > 0 {
newHead = head
}
if K == 0 {
head.Next = nil
}
}
if K > 0 {
return head
}
oldHead.Next = head
return newHead
}
func main() {
head := &LList{Value: 1}
n2 := &LList{Value: 2}
n3 := &LList{Value: 3}
n4 := &LList{Value: 4}
n5 := &LList{Value: 5}
head.Next = n2
n2.Next = n3
n3.Next = n4
n4.Next = n5
Print(head)
Print(Revers(head, 3))
}
package main
import "fmt"
type Node struct {
V string
Child []*Node
}
func FindCircle(root *Node, visited []*Node) (string, bool) {
for i := 0; i < len(visited); i++ {
if visited[i] == root {
path := visited[i].V
for j := i + 1; j < len(visited); j++ {
path += "->" + visited[j].V
}
path += "->" + root.V
return path, true
}
}
visited = append(visited, root)
for _, n := range root.Child {
p, ok := FindCircle(n, visited)
if ok {
return p, ok
}
}
visited = visited[0 : len(visited)-1]
return "", false
}
func main() {
root := &Node{V: "A"}
B := &Node{V: "B"}
C := &Node{V: "C"}
D := &Node{V: "D"}
E := &Node{V: "E"}
F := &Node{V: "F"}
H := &Node{V: "H"}
root.Child = []*Node{B, C}
B.Child = []*Node{D, E, F}
C.Child = []*Node{E, H}
E.Child = []*Node{B}
fmt.Println(FindCircle(root, []*Node{}))
}
package main
import (
"fmt"
"math/rand"
"time"
)
func getRandom(min, max int) int {
a := 1
b := 1
nums := []int{}
for b <= max {
if b >= min {
nums = append(nums, b)
}
a, b = b, a+b
}
r := rand.New(rand.NewSource(time.Now().UnixNano()))
return nums[r.Intn(len(nums))]
}
func main() {
fmt.Println(getRandom(2, 21))
}
For example, if target will be equal 2*Max + 1 (Max - is a maximum element in the array) we have to print all possible subsets N * (N + 1) / 2
So, solution can't be faster than O(N*N) ?
package main
import (
"fmt"
"strings"
)
type PatternPart struct {
l string
count int
}
func FindMinNum(pattern string) string {
letters := strings.Split(pattern, "")
P := []PatternPart{{letters[0], 1}}
i := 0
for j := 1; j < len(letters); j++ {
if letters[j] == P[i].l {
P[i].count++
} else {
P = append(P, PatternPart{letters[j], 1})
i++
}
}
digits := []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
res := ""
for pos, p := range P {
if p.l == "D" {
if pos == 0 {
res += digits[p.count]
digits = append(digits[:p.count], digits[p.count+1:]...)
}
for j := p.count - 1; j >= 0; j-- {
res += digits[j]
}
digits = digits[p.count:]
} else {
if pos == 0 {
res = "1"
digits = digits[1:]
}
if pos == len(P)-1 {
for j := 0; j < p.count; j++ {
res += digits[j]
}
digits = digits[p.count:]
} else {
for j := 0; j < p.count-1; j++ {
res += digits[j]
}
digits = digits[p.count-1:]
res += digits[P[pos+1].count]
digits = append(digits[:P[pos+1].count], digits[P[pos+1].count+1:]...)
}
}
}
return res
}
func main() {
fmt.Println(FindMinNum("D")) // 21
fmt.Println(FindMinNum("I")) // 12
fmt.Println(FindMinNum("DD")) // 321
fmt.Println(FindMinNum("II")) // 123
fmt.Println(FindMinNum("DIDI")) // 21435
fmt.Println(FindMinNum("IIDDD")) // 126543
fmt.Println(FindMinNum("DDIDDIID")) // 321654798
}
package main
import "fmt"
type TreeNode struct {
v string
l, r *TreeNode
}
type Step struct {
pos int
v string
}
func AllPath(root *TreeNode, offset int) [][]Step {
if root == nil {
return [][]Step{}
}
lP := AllPath(root.l, offset-1)
rP := AllPath(root.r, offset+1)
res := [][]Step{}
if len(lP) == 0 && len(rP) == 0 {
res = append(res, []Step{Step{pos: offset, v: root.v}})
} else {
for _, path := range lP {
res = append(res, append(path, Step{pos: offset, v: root.v}))
}
for _, path := range rP {
res = append(res, append(path, Step{pos: offset, v: root.v}))
}
}
return res
}
func FindMin(path []Step) int {
min := path[0].pos
for i := 1; i < len(path); i++ {
if min > path[i].pos {
min = path[i].pos
}
}
return min
}
func PrintPaths(paths [][]Step) {
for _, path := range paths {
min := FindMin(path)
for s := len(path) - 1; s >= 0; s-- {
step := path[s]
for i := min; i < step.pos; i++ {
fmt.Print("_ ")
}
fmt.Println(step.v)
}
fmt.Println()
}
}
func main() {
root := &TreeNode{"A", nil, nil}
root.l = &TreeNode{"B", nil, nil}
root.r = &TreeNode{"C", nil, nil}
root.l.l = &TreeNode{"D", nil, nil}
root.l.r = &TreeNode{"E", nil, nil}
root.r.l = &TreeNode{"F", nil, nil}
root.r.r = &TreeNode{"G", nil, nil}
root.r.r.r = &TreeNode{"H", nil, nil}
PrintPaths(AllPath(root, 0))
}
package main
import "fmt"
func Sum(a, b int) int {
res := a ^ b
y := a & b << 1
for y > 0 {
a = res
res = res ^ y
y = a & y << 1
}
return res
}
func main() {
fmt.Println(Sum(10, 20)) // Output: 30
}
How about to check m_refCount > 0 before decrement?
Release () {
m.lock();
if (m_refCount > 0) {
m_refCount--;
if (m_refCount == 0) {
free(this);
}
}
m.unlock();
return m_refCount;
}
#include <stdio.h>
int main()
{
int i, j;
int * p, * q;
int ** x;
int *** newVar;
i = 100;
j = 200;
p = &i;
q = &j;
x = &p;
newVar = &x;
*p = *p + *q;
*q = **x / 2;
**x = *p + j;
printf(" i = %d\n", i);
printf("&i = %p\n", &i);
printf(" j = %d\n", j);
printf("&j = %p\n", &j);
printf(" p = %p\n", p);
printf("&p = %p\n", &p);
printf("*p = %d\n", *p);
printf(" q = %p\n", q);
printf("&q = %p\n", &q);
printf("*q = %d\n", *q);
printf(" x = %p\n", x);
printf("&x = %p\n", &x);
printf("*x = %p\n", *x);
printf("**x= %d\n", **x);
***newVar = 999;
printf(" updated i = %d\n", i);
return 0;
}
How can robot leave starting position if it can turn to left and right only? This robot will alway stay on starting position :(
- dmitry.labutin March 03, 2017package main
import "fmt"
func sum(n, C int64) int64 {
res := int64(1)
add := int64(1)
count := int64(1)
last := int64(1)
for i := int64(2); i <= n; i++ {
add = add * i
if count == C {
add = add / last
last++
} else {
count++
}
res += add
}
return res
}
func main() {
fmt.Println(sum(5, 2)) // Output: 41
}
package main
import (
"fmt"
"log"
"strconv"
"strings"
)
func Solver(s string) int {
ds := strings.Split(s, "")
digits := []int{}
for _, d := range ds {
di, err := strconv.Atoi(d)
if err != nil {
log.Fatalln(err)
}
digits = append(digits, di)
}
return len(_count(digits))
}
func _count(digits []int) map[int]bool {
if len(digits) == 0 {
return map[int]bool{0: true}
}
num := 0
result := map[int]bool{}
for i := 0; i < len(digits); i++ {
num = num*10 + digits[i]
res := _count(digits[i+1:])
for r := range res {
result[num+r] = true
result[-num+r] = true
}
}
return result
}
func main() {
fmt.Println(Solver("123")) // Output: 17
}
package main
import "fmt"
type Point struct {
x, y int
}
func Abs(a int) int {
if a < 0 {
return -a
}
return a
}
func FindSquares(p []Point) [][]Point {
m := map[int]map[int]int{}
for i, point := range p {
if _, ok := m[point.x]; !ok {
m[point.x] = map[int]int{}
}
m[point.x][point.y] = i
}
res := [][]Point{}
for i := 0; i < len(p)-1; i++ {
for j := i + 1; j < len(p); j++ {
if Abs(p[i].x-p[j].x) == Abs(p[i].y-p[j].y) {
_, ok1 := m[p[i].x][p[j].y]
_, ok2 := m[p[j].x][p[i].y]
if ok1 && ok2 {
found := []Point{
p[i],
p[j],
p[m[p[i].x][p[j].y]],
p[m[p[j].x][p[i].y]],
}
res = append(res, found)
}
}
}
delete(m[p[i].x], p[i].y)
}
return res
}
func main() {
input := []Point{
Point{1, 1},
Point{3, 1},
Point{4, 2},
Point{3, 3},
Point{1, 4},
Point{1, 3},
Point{4, 1},
Point{3, 2},
}
fmt.Println(FindSquares(input))
}
Dijkstra's algorithm
But I don't understand what we need to minimize?
Sum of costs (5th value) or sum of distances abs(x1-x2)+abs(y1-y2) ?
package main
import (
"fmt"
)
type TreeNode struct {
value int
left, right *TreeNode
}
type PathWSum struct {
path []*TreeNode
sum int
}
func allPath(root *TreeNode) []PathWSum {
if root == nil {
return []PathWSum{}
}
result := []PathWSum{{path: []*TreeNode{root}, sum: root.value}}
tmp := append(allPath(root.left), allPath(root.right)...)
for _, path := range tmp {
newPath := PathWSum{path: append(path.path, root), sum: path.sum + root.value}
result = append(result, newPath)
}
return result
}
func reversPath(path []*TreeNode) []*TreeNode {
for i := 0; i < len(path)/2; i++ {
path[i], path[len(path)-1-i] = path[len(path)-1-i], path[i]
}
return path
}
func allPathFromRoot(root *TreeNode, sum int) [][]*TreeNode {
result := [][]*TreeNode{}
if root == nil {
return result
}
if root.value == sum {
result = append(result, []*TreeNode{root})
}
tmp := allPath(root.left)
for _, path := range tmp {
rPaths := allPath(root.right)
for _, rPath := range rPaths {
if path.sum+root.value+rPath.sum == sum {
result = append(result, append(append(path.path, root), reversPath(rPath.path)...))
}
}
}
result = append(result, allPathFromRoot(root.left, sum)...)
result = append(result, allPathFromRoot(root.right, sum)...)
return result
}
func printPaths(paths [][]*TreeNode) {
for _, path := range paths {
for _, node := range path {
fmt.Print(node.value)
fmt.Print(" ")
}
fmt.Println()
}
}
func main() {
n31 := &TreeNode{value: 3}
n32 := &TreeNode{value: 3}
n1 := &TreeNode{value: 1}
n_1 := &TreeNode{value: -1}
n_2 := &TreeNode{value: -2}
n6 := &TreeNode{value: 6}
n4 := &TreeNode{value: 4}
n5 := &TreeNode{value: 5}
n2 := &TreeNode{value: 2}
n_1.left = n31
n_2.left = n32
n4.left = n1
n4.right = n_1
n5.left = n_2
n5.right = n6
n2.left = n4
n2.right = n5
// 2
// 4 5
// 1 -1 -2 6
// 3 3
printPaths(allPathFromRoot(n2, 13))
// 1 4 2 5 -2 3
// 3 -1 4 2 5
}
Union-Find Algorithm
package main
import "fmt"
var sea [3][3]string
var isles [3][3]int
var count int
func initData() {
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
sea[i][j] = "o"
}
}
}
func getRoot(x, y int) (int, int) {
for true {
nx := isles[x][y] / 3
ny := isles[x][y] % 3
if nx == x && ny == y {
return x, y
}
x = nx
y = ny
}
return 0, 0
}
func mergeIsles(x1, y1, x2, y2 int) {
rootX1, rootY1 := getRoot(x1, y1)
rootX2, rootY2 := getRoot(x2, y2)
if rootX1 != rootX2 || rootY1 != rootY2 {
count--
isles[rootX1][rootY1] = isles[rootX2][rootY2]
}
}
func place(x, y int) int {
if sea[x][y] == "x" {
return count
}
sea[x][y] = "x"
count++
isles[x][y] = x*3 + y
if x > 0 {
if sea[x-1][y] == "x" {
mergeIsles(x-1, y, x, y)
}
}
if x < 2 {
if sea[x+1][y] == "x" {
mergeIsles(x+1, y, x, y)
}
}
if y > 0 {
if sea[x][y-1] == "x" {
mergeIsles(x, y-1, x, y)
}
}
if y < 2 {
if sea[x][y+1] == "x" {
mergeIsles(x, y+1, x, y)
}
}
return count
}
func main() {
initData()
fmt.Println(place(1, 2)) // 1
fmt.Println(place(2, 1)) // 2
fmt.Println(place(1, 1)) // 1
fmt.Println(place(0, 0)) // 2
fmt.Println(place(0, 1)) // 1
}
SELECT city.name, COUNT(*) as count FROM orders LEFT JOIN city ON orders.city=city.id GROUP BY orders.city ORDER BY count DESC LIMIT N
package main
import "fmt"
type ListNode struct {
value string
next *ListNode
}
func getMin(lists []*ListNode) int {
var min *ListNode
min = nil
ind := -1
for i, node := range lists {
if node != nil {
if min == nil {
min = node
ind = i
} else {
if min.value > node.value {
min = node
ind = i
}
}
}
}
return ind
}
func merge(lists []*ListNode) *ListNode {
var root, end *ListNode
present := map[string]map[int]bool{}
for i := 0; i < len(lists); i++ {
root := lists[i]
for root != nil {
if _, ok := present[root.value]; !ok {
present[root.value] = map[int]bool{}
}
present[root.value][i] = true
root = root.next
}
}
for true {
minNode := getMin(lists)
if minNode == -1 {
break
}
add := true
if len(present[lists[minNode].value]) > 1 {
add = false
}
if add {
newNode := &ListNode{value: lists[minNode].value}
if root == nil {
root = newNode
end = newNode
} else {
end.next = newNode
end = newNode
}
}
lists[minNode] = lists[minNode].next
}
return root
}
func printList(root *ListNode) {
for root != nil {
fmt.Print(root.value + " ")
root = root.next
}
}
func addToList(root *ListNode, add string) *ListNode {
newNode := &ListNode{value: add, next: root}
return newNode
}
func main() {
lists := []*ListNode{}
var root *ListNode
root = addToList(root, "xyxz")
root = addToList(root, "ddd")
root = addToList(root, "bbb")
root = addToList(root, "aaa")
lists = append(lists, root)
root = nil
root = addToList(root, "hkp")
root = addToList(root, "ccc")
root = addToList(root, "ccc")
root = addToList(root, "bbb")
lists = append(lists, root)
root = nil
root = addToList(root, "lmn")
root = addToList(root, "glk")
root = addToList(root, "ffff")
root = addToList(root, "eee")
root = addToList(root, "ddd")
lists = append(lists, root)
root = merge(lists)
printList(root)
}
package main
import "fmt"
func Add(res chan int, i, j int) {
res <- i + j
}
func Calc(a, b, c, d int) int {
res := make(chan int)
go Add(res, a, b)
go Add(res, c, d)
res1 := <-res
res2 := <-res
return res1 * res2
}
func main() {
fmt.Println(Calc(1, 2, 3, 4))
}
O(N^2) solution
package main
import "fmt"
func CountZero(m []int, sum int) int {
res := 0
for i := 0; i < len(m)-1; i++ {
sum := 0
for j := i + 1; j < len(m); j++ {
sum += m[j]
if sum == -m[i] {
res++
}
}
}
return res
}
func main() {
fmt.Println(CountZero([]int{-1, 1, -1, 1}, 0)) // 4
fmt.Println(CountZero([]int{-1, -1, 1, 1}, 0)) // 2
fmt.Println(CountZero([]int{-1, 1}, 0)) // 1
}
package main
import (
"fmt"
"strings"
)
func isNext(a, b string) bool {
ma := strings.Split(a, "")
mb := strings.Split(b, "")
diff := 0
for i, la := range ma {
if la != mb[i] {
diff++
}
if diff > 1 {
return false
}
}
return true
}
func copyMap(g map[int][]int, ei int) map[int][]int {
res := map[int][]int{}
for i := range g {
if i == ei {
continue
}
res[i] = []int{}
for j := 0; j < len(g[i]); j++ {
if ei != g[i][j] {
res[i] = append(res[i], g[i][j])
}
}
}
return res
}
func _longestPath(g map[int][]int, start int) int {
max := 1
if len(g) == 0 {
return 0
}
for _, next := range g[start] {
copyG := copyMap(g, start)
tmp := _longestPath(copyG, next)
if tmp+1 > max {
max = tmp + 1
}
}
return max
}
func LongestPath(g map[int][]int) int {
max := -1
for start := range g {
tmp := _longestPath(g, start)
if tmp > max {
max = tmp
}
}
return max
}
func Solve(m []string) bool {
g := map[int][]int{}
for i := 0; i < len(m); i++ {
g[i] = []int{}
}
for i := 0; i < len(m)-1; i++ {
for j := i + 1; j < len(m); j++ {
if isNext(m[i], m[j]) {
g[i] = append(g[i], j)
g[j] = append(g[j], i)
}
}
}
if LongestPath(g) == len(m) {
return true
} else {
return false
}
}
func main() {
fmt.Println(Solve([]string{"abc", "aba", "bba", "tbb", "cbb"})) // false
fmt.Println(Solve([]string{"abc", "aba", "bba", "tbb", "cbb", "cba"})) // true
fmt.Println(Solve([]string{"abc", "bba", "bbt", "aba"})) // true
}
package main
import (
"fmt"
"strings"
)
func KthLongestDistinctSubString(s string, k int) []string {
letters := strings.Split(s, "")
start := 0
i := 1
j := k
for j > 0 {
if len(letters) == i {
j--
i++
break
}
if letters[i-1] != letters[i] {
j--
}
i++
}
if j != 0 {
return []string{}
}
max := i - start - 1
result := []string{s[0 : i-1]}
for i < len(letters) {
for letters[start] == letters[start+1] {
start++
}
start++
for i < len(letters) && letters[i-1] == letters[i] {
i++
}
i++
if max == i-start-1 {
result = append(result, s[start:i-1])
}
if max < i-start-1 {
max = i - start - 1
result = []string{s[start : i-1]}
}
}
return result
}
func main() {
fmt.Println(KthLongestDistinctSubString("aaaabbbb", 2))
fmt.Println(KthLongestDistinctSubString("asdfrttt", 3))
fmt.Println(KthLongestDistinctSubString("aassdfrttt", 3))
}
package main
import "fmt"
func isPossible(seats []int, count int) bool {
possible := 0
freeCount := 0
if len(seats) == 0 {
return false
}
if seats[0] == 0 {
freeCount = 1
}
for i := 0; i < len(seats); i++ {
if seats[i] == 0 {
freeCount++
} else {
possible += (freeCount - 1) / 2
if possible >= count {
return true
}
freeCount = 0
}
}
possible += freeCount / 2
if possible >= count {
return true
}
return false
}
func main() {
seats := []int{1, 0, 0, 0, 0, 0, 1, 0, 0}
fmt.Println(isPossible(seats, 3))
fmt.Println(isPossible(seats, 4))
seats = []int{1, 0, 0, 1, 0, 0, 1, 0, 0}
fmt.Println(isPossible(seats, 1))
fmt.Println(isPossible(seats, 2))
seats = []int{0}
fmt.Println(isPossible(seats, 1))
fmt.Println(isPossible(seats, 2))
}
package main
import "fmt"
// _GetAllSums variants of summ
func _GetAllSums(A, N int) []map[int]int {
if N == 0 || A == 0 {
return []map[int]int{{}}
}
if A > N {
return _GetAllSums(N, N)
}
if A == 1 {
return []map[int]int{{1: N}}
}
result := _GetAllSums(A-1, N)
t := N - A
countA := 1
for t >= 0 {
tmp := _GetAllSums(A-1, t)
for _, v := range tmp {
v[A] = countA
result = append(result, v)
}
t -= A
countA++
}
return result
}
func Factorial(N int) int64 {
if N < 0 {
N = -N
}
result := int64(1)
for i := N; i > 1; i-- {
result = result * int64(i)
}
return result
}
func CountSums(A, N int) int64 {
r := _GetAllSums(A, N)
result := int64(0)
// Calculate result with permutations with repeating elements
for _, variant := range r {
length := 0
denominator := int64(1)
for _, nums := range variant {
length += nums
denominator *= Factorial(nums)
}
if length > 0 {
result += Factorial(length) / denominator
}
}
return result
}
func main() {
fmt.Println(CountSums(3, 4)) // Output: 7
}
func Merge(A, B []int) []int {
C := make([]int, len(A)+len(B))
ia := 0
ib := 0
ic := 0
for ia < len(A) || ib < len(B) {
if ia == len(A) {
C[ic] = B[ib]
ib++
ic++
continue
}
if ib == len(B) {
C[ic] = A[ia]
ia++
ic++
continue
}
if A[ia] < B[ib] {
C[ic] = A[ia]
ia++
} else {
C[ic] = B[ib]
ib++
}
ic++
}
return C
}
func main() {
A := []int{3, 6, 6, 7}
B := []int{3, 3, 8, 10}
fmt.Println(Merge(A, B))
}
package main
import "fmt"
func checkSumK(m []int, K int) bool {
if len(m) < 2 {
return false
}
elms := map[int]bool{}
for _, el := range m {
tmp := K - el
_, ok := elms[tmp]
if ok {
return true
}
elms[el] = true
}
return false
}
func main() {
fmt.Println(checkSumK([]int{1, 4, 5, 5, 7}, 12))
}
How about several CEOs ?
package main
import (
"fmt"
"log"
)
func inArray(s string, m []string) bool {
for _, e := range m {
if e == s {
return true
}
}
return false
}
func findCEOs(s map[string][]string) []string {
notCEO := []string{}
CEOs := []string{}
for e := range s {
for _, empl := range s[e] {
notCEO = append(notCEO, empl)
}
}
for e := range s {
if !inArray(e, notCEO) {
CEOs = append(CEOs, e)
}
}
return CEOs
}
func _printStruct(s map[string][]string, CEO string, space string) {
fmt.Println(space + "-" + CEO)
_, ok := s[CEO]
if ok {
for _, e := range s[CEO] {
_printStruct(s, e, space + " ")
}
}
}
func printStruct(s map[string][]string) {
CEOs := findCEOs(s)
if len(CEOs) == 0 {
log.Fatalln("Not CEOs")
}
for _, CEO := range CEOs {
_printStruct(s, CEO, "")
}
}
func main() {
empl := make(map[string][]string)
empl["AAA"] = []string{"BBB", "CCC", "DDD"}
empl["CCC"] = []string{"EEE"}
empl["RRR"] = []string{"FFF"}
printStruct(empl)
}
func PrintByLevel(root *TreeNode) {
data := [][]int{}
_ByLevel(root, 0, &data)
for i:= len(data) - 1; i >= 0; i-- {
for _, v := range data[i] {
fmt.Print(v)
}
}
}
func _ByLevel(root *TreeNode, level int, data *[][]int) {
if root == nil {
return
}
if len(*data) <= level {
*data = append(*data, []int{})
}
(*data)[level] = append((*data)[level], root.val)
_ByLevel(root.left, level + 1, data)
_ByLevel(root.right, level + 1, data)
}
func first_non_repeat(str string) string {
charsCount := map[rune]int{}
charsSingle := map[rune]bool{}
charsPos := map[rune]int{}
pos := 0
for _, r := range str {
charsCount[r]++
if charsCount[r] == 1 {
charsSingle[r] = true
charsPos[r] = pos
} else {
delete(charsSingle, r)
}
pos++
}
minPos := math.MaxInt64
for r, _ := range charsSingle {
if charsPos[r] < minPos {
minPos = charsPos[r]
}
}
return str[minPos:minPos+1]
}
package main
import (
"fmt"
)
func nextJumbled(n int) int {
if n < 10 {
return n + 1
}
last := n % 10
prev := (n / 10) % 10
if last < 8 && prev > last {
return n + 2
}
prefix := nextJumbled(n / 10)
last = prefix % 10
if last == 0 {
return prefix*10 + 1
}
return prefix*10 + last - 1
}
func main() {
max := 1000
cur := 10
for cur <= max {
fmt.Printf("%d ", cur)
cur = nextJumbled(cur)
}
}
- dmitry.labutin March 30, 2018