golang实现lintcode部分算法

落日映苍穹つ 2023-02-17 05:14 14阅读 0赞

1.[https://www.lintcode.com/problem/digit-counts/description][https_www.lintcode.com_problem_digit-counts_description]

### Description ###

中文English

Count the number of *k*'s between *0* and *n*. *k* can be *0* - *9*.

**Example**

Input:
    k = 1, n = 12
    Output:
    5
    Explanation:
    In [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we found that one appeared five times (1, 10, 11, 12)(Note that there are two 1 in 11).

**Code**

/**
    Input:
    k = 1, n = 1
    Output:
    1
    Explanation:
    In [0, 1], we found that 1 appeared once (1).
    */
    func CountNumber(k int ,n int) int  {
    	count := 0
    	var kStr = strconv.Itoa(k)
    	for i :=0 ; i <= n ; i++ {
    		tempStr := strconv.Itoa(i)
    		if tempStr == kStr && len(tempStr) == 1{
    			count ++
    		}else {
    			for j :=0 ; j < len(tempStr); j++ {
    				if kStr == string(tempStr[j]){
    					count ++
    				}
    			}
    		}
    	}
    	return count
    }

测试：

package main
    
    import (
    	"fmt"
    	"src/lintcode"
    )
    
    func main()  {
    	// 测试出现频率
    	k := 1
    	n := 12
    	fmt.Println("输入",k,n)
    	number := lintcode.CountNumber(k, n)
    	fmt.Println("输出",number)
    }

输出：

![20200612171521178.png][]

2. [https://www.lintcode.com/problem/ugly-number-ii/description][https_www.lintcode.com_problem_ugly-number-ii_description]

### Description ###

Ugly number is a number that only have prime factors `2`, `3` and `5`.

Design an algorithm to find the *n*th ugly number. The first 10 ugly numbers are `1, 2, 3, 4, 5, 6, 8, 9, 10, 12...`

// 寻找丑陋数

/**
    寻找丑陋数
     */
    func FindUgly(endFlag int) int  {
    	if endFlag < 1 {
    		return -1
    	}
    	target := 1
    	flag := 1
    	for {
    		temp := target
    		for ;target % 2 == 0;  {
    			target = target / 2
    		}
    		for ;target % 3 == 0;  {
    			target = target / 3
    		}
    		for ;target % 5 == 0;  {
    			target = target / 5
    		}
    		if flag >= endFlag && target == 1{
    			return temp
    		}
    
    		if target == 1{
    			flag ++
    		}
    		target = temp + 1
    	}
    }

func main()  {
    	// 测试丑数
    	input := 9
    	output := lintcode.FindUgly(input)
    	fmt.Println(input, output)
    }

输出：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hlbGxvV29ybGRZYW5nU29uZw_size_16_color_FFFFFF_t_70][]

3. [https://www.lintcode.com/problem/kth-largest-element/description][https_www.lintcode.com_problem_kth-largest-element_description]

### Description ###

中文English

在数组中找到第 k 大的元素。

你可以交换数组中的元素的位置

### Example ###

**样例 1：**

输入：
    n = 1, nums = [1,3,4,2]
    输出：
    4

**样例 2：**

输入：
    n = 3, nums = [9,3,2,4,8]
    输出：
    4

### Challenge ###

要求时间复杂度为O(n)，空间复杂度为O(1)。

// 代码

持续更新中

[https_www.lintcode.com_problem_digit-counts_description]: https://www.lintcode.com/problem/digit-counts/description
[20200612171521178.png]: https://img-blog.csdnimg.cn/20200612171521178.png
[https_www.lintcode.com_problem_ugly-number-ii_description]: https://www.lintcode.com/problem/ugly-number-ii/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hlbGxvV29ybGRZYW5nU29uZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615101846388.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hlbGxvV29ybGRZYW5nU29uZw==,size_16,color_FFFFFF,t_70
[https_www.lintcode.com_problem_kth-largest-element_description]: https://www.lintcode.com/problem/kth-largest-element/description