LintCode刷题

1910 · 数组中出现次数最多的值

1609 · 链表的中间结点

func MiddleNode(head *ListNode) *ListNode {
    // write your code here.
    if head == nil || head.Next == nil {
        return head
    }
    count := 0
    res := head
    for head != nil {
        count++
        if count%2 == 0 {
            res = res.Next
        }
        head = head.Next
    }
    return res
}

1535 · 转换成小写字母

BenchmarkToLowerCase-8 100000000 10.19 ns/op

func ToLowerCase(str string) string {
    // Write your code here
    s := []byte(str)
    for i := 0; i < len(s); i++ {
        if s[i] <= 'Z' && s[i] >= 'A' {
            s[i] += 32
        }
    }
    return string(s)
}

1343 · 两字符串和-1

BenchmarkSumofTwoStrings-8 15157620 81.52 ns/op

import (
    "strconv"
)
func SumofTwoStrings(a string, b string) string {
    // write your code here
    res := ""
    //从string尾部开始计算
    indexA, indexB := len(a)-1, len(b)-1
    for indexA >= 0 && indexB >= 0 {
        temp := a[indexA] - '0' + b[indexB] - '0'
        res = strconv.Itoa(int(temp)) + res
        indexA--
        indexB--
    }
    if indexA >= 0 {
        res = a[0:indexA+1] + res
    }
    if indexB >= 0 {
        res = b[0:indexB+1] + res
    }
    return res
}

1334 · 旋转数组-1

BenchmarkRotate-8 72459829 16.88 ns/op

func Rotate(nums []int, k int) []int {
    // Write your code here
    l := len(nums)
    if k%l==0 {
        return nums
    }
    k = k%l
    reverse(nums,0,l-k-1)
    reverse(nums,l-k,l-1)
    reverse(nums,0,l-1)
    return nums
}
func reverse(nums []int, left, right int) {
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

1331 · 英语软件

BenchmarkEnglishSoftware-8 27541000 44.32 ns/op

func EnglishSoftware(score []int, ask []int) []int {
    // write your code here
    sCount := len(score)
    r := make([]int, len(ask))
    for i, v := range ask {
        c := 0
        for _, s := range score {
            if s <= score[v-1] {
                c++
            }
        }
        r[i] = (c - 1) * 100 / sCount
    }
    return r
}

1300 · 巴什博弈

BenchmarkCanWinBash-8 1000000000 0.2862 ns/op

func CanWinBash(n int) bool {
    // Write your code here
    if n % 4 == 0{
        return false
    }
    return true
}

1141 · 月份天数

BenchmarkGetTheMonthDays-8 1000000000 0.2992 ns/op

func GetTheMonthDays(year int, month int) int {
    // write your code here
    if month == 2 {
        if IsLeapYear(year) {
            return 29
        }
        return 28
    }
    if month == 4 || month == 6 || month == 9 || month == 11 {
        return 30
    }
    return 31
}
func IsLeapYear(n int) bool {
    // write your code here
    if n%4 == 0 && n%100 != 0 || n%400 == 0 {
        return true
    }
    return false
}

1138 · 能否放置花-1

BenchmarkCanPlaceFlowers-8 375463814 3.448 ns/op

func CanPlaceFlowers(flowerbed []int, n int) bool {
    // Write your code here
    length := len(flowerbed)
    for i, v := range flowerbed {
        //首尾部 当前值为0,且首部下一个index==0,尾部上一个index==0。可进行放置
        //中部 当前值为0 其前面一个和后面一个index均为0 方可放置
        if v == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == length-1 || flowerbed[i+1] == 0) {
            n--
            //并将当前值置为1
            flowerbed[i] = 1
            if n <= 0 {
                return true
            }
        }
    }
    //n 为 0的情况
    return n == 0
}

936 · 首字母大写

822 · 相反的顺序存储

BenchmarkReverseStore-8 12835638 97.49 ns/op

func ReverseStore(head *ListNode) []int {
    // write your code here
    arr := []int{}
    for head != nil {
        arr = append(arr, head.Val)
        head = head.Next
    }
    //反转切片
    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
    return arr
}

807 · 回文数 II

BenchmarkIsPalindrome-8 27474980 43.69 ns/op

func IsPalindrome(n int) bool {
    // Write your code here
    if n <= 1 {
        return true
    }
    a := toBinary(n)
    for i := 0; i <= len(a)-i-1; i++ {
        if a[i] == a[len(a)-i-1] {
            continue
        } else {
            return false
        }
    }
    return true
}
func toBinary(n int) []int {
    a := make([]int, 0, 32)
    for {
        a = append(a, n%2)
        n = n / 2
        if n == 1 {
            a = append(a, 1)
            break
        }
    }
    return a
}

771 · 二阶阶乘

768 · 杨辉三角

BenchmarkCalcYangHuisTriangle-8 2757681 509.4 ns/op

func CalcYangHuisTriangle(n int) [][]int {
    // write your code here
    tmp := []int{1}
    res := [][]int{}
    for i := 0; i < n; i++ {
        res = append(res, tmp)
        //每行的元素个数与当前行号相等
        //下一行的第i个元素为上一行的第j-1个元素与第i个元素之和
        for j := 1; j < i; j++ {
            res[i] = append(res[i], res[i-1][j-1]+res[i-1][j])
        }
        //其他的元素赋初值
        if i > 0 {
            res[i] = append(res[i], 1)
        }
    }
    return res
}

BenchmarkCalcYangHuisTriangle-8 6527358 199.4 ns/op

func CalcYangHuisTriangle(n int) [][]int {
    triangle := make([][]int, n)
    for i, _ := range triangle {
        triangle[i] = make([]int, i+1)
        // 外层
        triangle[i][0] = 1
        triangle[i][i] = 1
        // 内层
        if i >= 2 {
            for j := 1; j < len(triangle[i])-1; j++ {
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
            }
        }
    }
    return triangle
}

767 · 翻转数组

BenchmarkReverseArray-8 1000000000 1.138 ns/op

func ReverseArray(nums []int)  {
    // write your code here
    n := len(nums) - 1
    for i := 0; i < len(nums)/2; i++ {
        nums[i], nums[n-i] = nums[n-i], nums[i]
    }
}

766 · 闰年

BenchmarkIsLeapYear-8 1000000000 0.2808 ns/op

func IsLeapYear(n int) bool {
    // write your code here
    if n%4 == 0 && n%100 != 0 || n%400 == 0 {
        return true
    }
    return false
}

764 · 计算圆周长和面积

BenchmarkCalculate-8 1000000000 0.2809 ns/op

func Calculate(r int) []float64 {
    // write your code here
    PI := 3.14
    return []float64{float64(r) * 2 * PI, float64(r*r) * PI}
}

594 · 字符串查找 II

BenchmarkStrStr-8 217115032 5.188 ns/op

import "strings"
func StrStr2(source string, target string) int {
    // write your code here
    return strings.Index(source, target)
}

521 · 去除重复元素

BenchmarkDeduplication-8 16732713 75.24 ns/op

func Deduplication(nums []int) int {
    if nums == nil || len(nums) == 0 {
        return 0
    }
    sort.Ints(nums)
    n := len(nums)
    i, j := 0, 1
    for ; i < n; i++ {
        for j < n && nums[j] == nums[i] {
            j++
        }
        if j >= n {
            break
        }
        nums[i+1] = nums[j]
    }
    return i + 1
}

495 · 实现栈

492 · 队列维护

491 · 回文数

485 · 生成给定大小的数组

BenchmarkGenerate-8 30572190 37.48 ns/op

func Generate(size int) []int {
    // write your code here
    slice := make([]int, size)
    for i := 0; i < size; i++ {
        slice[i] = i + 1
    }
    return slice
}

484 · 交换数组两个元素

BenchmarkSwapIntegers-8 940372543 1.382 ns/op

func SwapIntegers(a []int, index1 int, index2 int) {
    // write your code here
    a[index1], a[index2] = a[index2], a[index1]
}

483 · 链表转数组

BenchmarkToArrayList-8 13093617 89.47 ns/op

func ToArrayList(head *ListNode) []int {
    // write your code here
    arr := []int{}
    for head != nil {
        arr = append(arr, head.Val)
        head = head.Next
    }
    return arr
}

480 · 二叉树的所有路径

479 · 数组第二大数

BenchmarkSecondMax-8 21445152 55.92 ns/op

func SecondMax(nums []int) int {
    // write your code here
    sort.Ints(nums)
    return nums[len(nums)-2]
}

478 · 简单计算器

BenchmarkCalculate-8 1000000000 0.2865 ns/op

func Calculate(a int, op byte, b int) int {
    // write your code here
    res := 0
    switch op {
    case '+':
        res = a + b
    case '-':
        res = a - b
    case '*':
        res = a * b
    case '/':
        res = a / b
    }
    return res
}

466 · 链表节点计数

BenchmarkCountNodes-8 837966589 1.420 ns/op

func CountNodes(head *ListNode) int {
    // write your code here
    count := 0
    for head != nil {
        count ++
        head = head.Next
    }
    return count
}

463 · 整数排序

BenchmarkSortIntegers-8 22559443 54.14 ns/op

func SortIntegers(a []int) {
    // write your code here
    sort.Ints(a)
}

449 · 字符转整数

BenchmarkCharToInteger-8 1000000000 0.2935 ns/op

func CharToInteger(character byte) int {
    // write your code here
    return int(character)
}

423 · 有效的括号序列

422 · 最后一个单词的长度

406 · 和大于S的最小子数组

366 · 斐波纳契数列

BenchmarkFibonacci-8 1000000000 0.2877 ns/op

func Fibonacci(n int) int {
    // write your code here
    q, p := 0, 1
    if n <= 2 {
        return n - 1
    }
    for i := 2; i < n; i++ {
        sum := q + p
        q = p
        p = sum
    }
    return p
}

353 · 最大字母

298 · 寻找素数

BenchmarkPrime-8 472503 2371 ns/op

func Prime(n int) []int {
    // write your code here
    //var slice []int
    //这个不行 会返回null 我自己本地1.18.4测试的ok,估计lintcode版本低了...
    slice := []int{}
    for i := 2; i <= n; i++ {
        if isPrime(i) {
            slice = append(slice, i)
        }
    }
    return slice
}
func isPrime(n int) bool {
    if n < 2 {
        return false
    }
    for i := 2; i <= n/i; i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

297 · 寻找最大值

BenchmarkMaxNum-8 24588752 51.23 ns/op

func MaxNum(nums []int) int {
    // write your code here
    sort.Ints(nums)
    return nums[len(nums)-1]
}

283 · 三数之中的最大值

BenchmarkMaxOfThreeNumbers-8 1000000000 0.2795 ns/op

func MaxOfThreeNumbers(num1 int, num2 int, num3 int) int {
    // write your code here
    tmp := max(num1, num2)
    return max(tmp, num3)
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

263 · 小括号匹配

241 · 转换字符串到整数（容易版）

BenchmarkStringToInteger-8 245307522 4.713 ns/op

import "strconv"
func StringToInteger(target string) int {
    // write your code here
    v, _ := strconv.Atoi(target)
    return v
}

228 · 链表的中点

BenchmarkMiddleNode-8 397173186 2.987 ns/op

func MiddleNode(head *ListNode) *ListNode {
    if head == nil || head.Next == nil || head.Next.Next == nil {
        return head
    }
    pre := head
    cur := head.Next.Next
    for cur.Next != nil && cur.Next.Next != nil{
        pre = pre.Next
        cur = cur.Next.Next
    }
    return pre.Next
}

BenchmarkMiddleNode-8 169528088 6.928 ns/op

func MiddleNode(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    node := head
    count := 0
    for head.Next != nil {
        count++
        head = head.Next
        if count%2 == 0 {
            node = node.Next
        }
    }
    return node
}

BenchmarkMiddleNode-8 2439154 483.7 ns/op

func MiddleNode(head *ListNode) *ListNode {
    if head == nil || head.Next == nil || head.Next.Next == nil {
        return head
    }
    count := 0
    m := map[int]*ListNode{}
    for head != nil {
        count++
        m[count] = head
        head = head.Next
    }
    if count%2 == 0 {
        return m[count/2]
    } else {
        return m[count/2+1]
    }
}

225 · 在链表中找节点

BenchmarkFindNode-8 1000000000 1.055 ns/op

func FindNode(head *ListNode, val int) *ListNode {
    // write your code here
    for head != nil {
        if head.Val == val{
            return head
        }
        head = head.Next
    }
    return nil
}

220 · 冰雹猜想

BenchmarkGetAnswer-8 53053446 23.72 ns/op

func GetAnswer(num int) int {
    // write your code here.
    count := 0
    for num != 1 {
        if num%2 == 0 {
            num /= 2
        } else {
            num = 3*num + 1
        }
        count++
    }
    return count
}

219 · 在排序链表中插入一个节点

214 · 数组的最大值

BenchmarkMaxOfArray-8 707330299 1.713 ns/op

func MaxOfArray(a []float32) float32 {
    // write your code here
    max := a[0]
    for i := 1; i < len(a); i++ {
        if a[i] > max {
            max = a[i]
        }
    }
    return max
}

209 · 第一个只出现一次的字符

175 · 翻转二叉树

157 · 判断字符串是否没有重复字符

146 · 大小写转换 II

BenchmarkLowercaseToUppercase2-8 44616631 24.94 ns/op

func LowercaseToUppercase2(letters string) string {
    // write your code here
    return strings.ToUpper(letters)
}

BenchmarkLowercaseToUppercase2-8 94741827 12.33 ns/op

func LowercaseToUppercase2(letters string) string {
    // write your code here
    strBytes := []byte(letters)
    for i := range strBytes {
        if strBytes[i] >= 'a' && letters[i] <= 'z' {
            strBytes[i] -= 32
        }
    }
    return string(strBytes)
}

145 · 大小写转换

BenchmarkLowercaseToUppercase-8 1000000000 0.3236 ns/op

func LowercaseToUppercase(character byte) byte {
    // write your code here
    return character-32
}

133 · 最长单词

68 · 二叉树的后序遍历

67 · 二叉树的中序遍历

66 · 二叉树的前序遍历

60 · 搜索插入位置

56 · 两数之和

53 · 翻转字符串

50 · 数组剔除元素后的乘积

46 · 主元素

39 · 恢复旋转排序数组

BenchmarkName-8 100000000 11.25 ns/op

func RecoverRotatedSortedArray(nums []int) {
    //write your code here
    //1.先找到后面一个数比前面大的索引值
    index := 0
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] > nums[i+1] {
            index = i
            break
        }
    }
    //当index不发生改变的时候，说明传入的[]int是顺序的,无需修改。
    if index != 0{
        reverse(nums, 0, index)
        reverse(nums, index+1, len(nums)-1)
        reverse(nums, 0, len(nums)-1)
    }
}
func reverse(nums []int, left, right int) {
    for left < right {
        nums[left], nums[right] = nums[right], nums[left]
        left++
        right--
    }
}

37 · 反转一个三位整数

BenchmarkReverseInteger-8 1000000000 0.2873 ns/op

func ReverseInteger(number int) int {
    // write your code here
    return number%10*100 + number/10%10*10 + number/100
}

25 · 打印X

BenchmarkPrintX-8 1361227 881.5 ns/op

func PrintX(n int) []string {
    // write your code here
    //1.创建一个长度为 n 的 []string
    res := make([]string, n)
    //2.针对每一个[]里面,对其进行操作
    for i := 0; i < n; i++ {
        //3.每一个切片中,开辟大小为n的byte[]
        item := make([]byte, n)
        //4.每个[]byte中的item初始化为 ' '
        for j := range item {
            item[j] = ' '
        }
        //5.只需对当前的行切片[]byte的首尾两个index赋值为 'X' 即可
        item[i] = 'X'
        item[n-i-1] = 'X'
        //6.对 []string 赋相应的 []byte
        res[i] = string(item)
    }
    //7.返回结果
    return res
}

23 · 判断数字与字母字符

BenchmarkIsAlphanumeric-8 1000000000 0.2794 ns/op

func IsAlphanumeric(c byte) bool {
    // write your code here
    if c <= 'Z' && c >= 'A' || c <= 'z' && c >= 'a' || c <= '9' && c >= '0' {
        return true
    }
    return false
}

14 · 二分查找

13 · 字符串查找

BenchmarkStrStr-8 225371284 5.191 ns/op

func StrStr(source string, target string) int {
    // Write your code here
    return strings.Index(source, target)
}

9 · Fizz Buzz 问题

BenchmarkFizzBuzz-8 6569154 180.0 ns/op

func FizzBuzz(n int) []string {
    // write your code here
    if n == 0 {
        return []string{}
    }
    str := make([]string, n)
    for i := 1; i <= n; i++ {
        if i%15 == 0 {
            str[i-1] = "fizz buzz"
        } else if i%5 == 0 {
            str[i-1] = "buzz"
        } else if i%3 == 0 {
            str[i-1] = "fizz"
        } else {
            str[i-1] = strconv.Itoa(i)
        }
    }
    return str
}

8 · 旋转字符数组

3 · 统计数字-1

import (
    "strconv"
)
func DigitCounts(k int, n int) int {
    str := ""
    for i := 0; i <= n; i++ {
        str += strconv.Itoa(i)
    }
    count := 0
    for _, v := range str {
        //string 的本质是 []byte,取出来的是byte值
        //而k是int值,byte转为int值则是相应的ascii值。
        if k == int(v-'0'){
            count++
        }
    }
    return count
}

import (
    "fmt"
    "strings"
)
func DigitCounts(k int, n int) int {
    count := 0
    strK := fmt.Sprintf("%d", k)//转成string
    for i := 0; i <= n; i++ {
        //利用Split包切分出k的string,并计数。
        count += len(strings.Split(fmt.Sprintf("%d", i), strK)) - 1
    }
    return count
}

func DigitCounts(k int, n int) int {
    num := 0
    if k == 0 {
        num++
    }
    for i := 0; i <= n; i++ {
        for m := i; m != 0; {
            j := m % 10
            m = m / 10
            if j == k {
                num++
            }
        }
    }
    return num
}

import (
    "strconv"
)
func DigitCounts(k int, n int) int {
    str := strconv.Itoa(n)
    maxBit := 6
    tenPow := make([]int, maxBit)
    tenPow[0] = 1
    for i := 1; i < maxBit; i++ {
        tenPow[i] = tenPow[i-1] * 10
    }
    res := 0
    for i := 0; i < len(str); i++ {
        curNum := int(str[i] - '0')
        count := 0
        // i位置前的可能性
        if i > 0 {
            if k != 0 {
                count = n / tenPow[len(str)-i] * tenPow[len(str)-1-i]
            } else {
                count = (n/tenPow[len(str)-i] - 1) * tenPow[len(str)-1-i]
            }
        }
        // i位置后面的可能性
        if i > 0 || k != 0 {
            if curNum > k {
                count += tenPow[len(str)-i-1]
            } else if curNum == k {
                count += n%tenPow[len(str)-i-1] + 1
            }
        }
        res += count
    }
    if k == 0 {
        res++
    }
    return res
}

2 · 尾部的零

BenchmarkTrailingZeros-8 136642118 8.064 ns/op

func TrailingZeros(n int64) int64 {
    // write your code here
    ans := int64(0)
    for n > 0 {
        n /= 5
        ans += n
    }
    return ans
}

1 · A + B 问题

BenchmarkAplusb-8 1000000000 0.2842 ns/op

func Aplusb(a int, b int) int {
    // write your code here
    return a+b
}