数据结构和算法学习笔记--数据结构：将“昂贵”的时间复杂度转换成

程序优化的最核心的思路

1. 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
2. 第二步，无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
3. 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。

package main

import "fmt"

// 在 100 以内的正整数中，找到同时满足以下两个条件的最小数字: 1. 能被 3 整除； 2. 除 5 余 2。
// 时间复杂度 O(n)
func testMinValue1() {
    minValue := -1
    count := 0
    for i := 0; i < 100; i++ {
        count++
        if i/3 == 0 && i%5 == 2 {
            if minValue == -1 || i < minValue {
                minValue = i
            }
        }
    }
    fmt.Printf("min value: %d, cal count: %d \n", minValue, count)
}

// 在 100 以内的正整数中，找到同时满足以下两个条件的最小数字: 1. 能被 3 整除； 2. 除 5 余 2。
// 时间复杂度 小于O(n)
func testMinValue2() {
    minValue := -1
    count := 0
    for i := 0; i < 100; i++ {
        count++
        if i/3 == 0 && i%5 == 2 {
            minValue = i
            break
        }
    }
    fmt.Printf("min value: %d, cal count: %d \n", minValue, count)
}

// 假设有任意多张面额为 2 元、3 元、7 元的货币，现要用它们凑出 100 元，求总共有多少种可能性
// 时间复杂度 O( n³ )
func testMoney1() {
    result := 0
    count := 0
    for i := 0; i < 100/7; i++ {
        for j := 0; j < 100/3; j++ {
            for k := 0; k < 100/2 + 1; k++ {
                count++
                if i * 7 + j * 3 + k * 2 == 100 {
                    fmt.Printf("7元: %d, 3元: %d, 2元: %d \n", i, j, k)
                    result += 1
                }
            }
        }
    }
    fmt.Printf("result: %d, cal count: %d \n", result, count)
}

// 假设有任意多张面额为 2 元、3 元、7 元的货币，现要用它们凑出 100 元，求总共有多少种可能性
// 时间复杂度 O(n²)
func testMoney2() {
    result := 0
    count := 0
    for i := 0; i < 100/7; i++ {
        for j := 0; j < 100/3; j++ {
            count++
            k := 100 - i * 7 - j * 3
            if k >= 0 && k % 2 == 0 {
                fmt.Printf("7元: %d, 3元: %d, 2元: %d \n", i, j, k / 2)
                result += 1
            }
        }
    }
    fmt.Printf("result: %d, cal count: %d \n", result, count)
}

// 查找出现次数最多的那个数字
// 时间复杂度 O(n)
func testMaxCountValue2(a []int) {
    //a := []int{ 1, 3, 4, 3, 4, 1, 3 }

    countMap := make(map[int]int)
    for i := 0; i < len(a); i++ {
        if _, ok := countMap[a[i]]; ok {
            countMap[a[i]] += 1
        } else {
            countMap[a[i]] = 1
        }
    }

    maxCount := 0 // 数字出现的次数
    maxCountVal := 0 // 最大次数的数字
    for key, count := range countMap {
        if count > maxCount {
            maxCount = count
            maxCountVal = key
        }
    }

    fmt.Printf("max count value is %d \n", maxCountVal)
}

func main() {
    //testMinValue1()
    //testMinValue2()
    //
    //testMoney1()
    //testMoney2()

    a := []int{1,2,3,4,5,5,6}

    testMaxCountValue2(a)
}