Leetcode 每日一题 日常

[hankviv]

https://leetcode-cn.com/problems/majority-element/

[hankviv]

解法一 空间换时间

func majorityElement(nums []int) int {
    hashMap := make(map[int]int)
    count := len(nums)
    var res int

    for _,v := range nums{
        if value,ok := hashMap[v]; ok{
            hashMap[v] = value + 1
        }else{
            hashMap[v] = 1
        }
    }
    for k,v := range hashMap{
        if v > count/2{
            res = k
        }
    }
    return res
}

[hankviv]

骚方法： 确定存在众数的话 排序 然后取中间值

func majorityElement(nums []int) int {
    sort.Ints(nums)
    return nums[len(nums)/2]
}

[hankviv]

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

[hankviv]

回溯法： 每次递归都带点货

var phone = []string{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}

func recursive(digits string,index int,s string,p *[]string){
    //fmt.Println(digits,index,s)
    if index == len(digits){
        *p = append(*p,s)
        return
    }
    keysInt,_ := strconv.Atoi(string(digits[index]))
    //fmt.Println(keysInt)
    letter := phone[keysInt]
    for i:=0;i < len(letter); i++{
        recursive(digits,index+1,s + string(letter[i]),p)
    }

}

func letterCombinations(digits string) []string {
    var p = make([]string,0)
    if digits == ""{
        return p
    }
    recursive(digits,0,"",&p)
    return p
}

[hankviv]

https://leetcode-cn.com/problems/kids-with-the-greatest-number-of-candies/

[hankviv]

解题：该孩子持有糖果数+额外糖果数>=持有最多糖果的孩子的糖果数 则该孩子满足条件。 先求出最大糖果数，然后一一比较就好

func kidsWithCandies(candies []int, extraCandies int) []bool {
    lens := len(candies)
    maxCandies := 0

    for i := 0; i < lens; i++ {
        maxCandies = max(maxCandies, candies[i])
    }
    res := make([]bool, lens)

    for i := 0; i < lens; i++ {
        res[i] = candies[i] + extraCandies >= maxCandies
    }
    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

[hankviv]

https://leetcode-cn.com/problems/lemonade-change/

[hankviv]

1、解题：模拟生活场景 直接解题 贪心算法逻辑，如果每次解都是最优处理 最终是最优解就是贪心算法。

func lemonadeChange(bills []int) bool {
    fiveNum, tenNum := 0, 0;
    for _, k := range bills {
        switch k {
        case 5:
            fiveNum += 1
        case 10:
            if fiveNum >= 1 {
                fiveNum -= 1
                tenNum += 1
            } else {
                return false
            }
        case 20:
            if fiveNum >= 1 && tenNum >= 1 {
                fiveNum -= 1
                tenNum -= 1
            } else if fiveNum >= 3 {
                fiveNum -= 3
            } else {
                return false
            }
        }
    }
    return true
}

[hankviv]

func toLowerCase(s string) string {
    bs := []byte(s)
    for i := 0; i < len(bs); i++ {
        if bs[i] >= 'A' && bs[i] <= 'Z' {
            bs[i] += 32
        }
    }
    return string(bs)
}

[hankviv]

58. 最后一个单词的长度

func lengthOfLastWord(s string) int {
    pre,curr := 0, 0
    for _, v := range s {
        if v != ' ' {
            curr++
        }
        //又出现空格了，如果当前字符串个数不是0 就记录当前个数为上一个字符串个数，并且重置字符串个数
        if v == ' ' && curr != 0 {
                pre = curr
                curr = 0
        }
    }
    if curr == 0 {
        return pre
    }
    return curr
}

[hankviv]

387. 字符串中的第一个唯一字符

     
     func firstUniqChar(s string) int {
     for i := 0; i < len(s); i++ {
         has := 0
         for j := 0; j < len(s); j++ {
             if i == j {
                 continue
             }
             if s[i] == s[j] {
                 has = 1
                 break
             }
         }
         if has == 0 {
             return i
         }
     }
     return -1
     }

[hankviv]

344. 反转字符串

func reverseString(s []byte) {
    left, right := 0, len(s)-1
    //当相等的时候代表单数字符串最中间，不用交换
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}