Fork me on GitHub

HCs blog

勿于浮沙筑高台

0%

发表于 更新于 分类于
本文字数： 543 阅读时长 ≈ 1 分钟

题目

给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

样例

  • 0 <= n <= 104
    输入：n = 3
    输出：0
    解释：3! = 6 ，不含尾随 0

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

输入：n = 0
输出：0

思路1

发现只有5 * 2生成尾随0，以2为因子的数比5多，只要计算所有数有多少个5，把所有5加起来即为答案
有TLE风险

代码1

1
2
3
4
5
6
7
8
9
10
11
func trailingZeroes(n int) int {
    count:=0
    for i:=1;i<=n;i++{
        tmp := i
        for tmp%5==0{
            count += 1
            tmp /= 5
        }
    }   
    return count
}

思路2

进阶 … * (1 * 5) * … * (1 * 5 * 5) * … * (2 * 5 * 5) * … * (3 * 5 * 5) * … * n

每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5… 以此类推。
最终 5 的个数就是 n / 5 + n / 25 + n / 125 …

1
2
3
4
5
6
7
8
func trailingZeroes(n int) int {
    count:=0
    for n>0{
        n /= 5
        count += n
    }   
    return count
}

发表于 更新于 分类于
本文字数： 533 阅读时长 ≈ 1 分钟

题目

自除数 是指可以被它包含的每一位数整除的数。
例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
自除数 不允许包含 0 。
给定两个整数 left 和 right ，返回一个列表，列表的元素是范围 [left, right] 内所有的 自除数

样例

输入：left = 1, right = 22
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
输入：left = 47, right = 85
输出：[48, 55, 66, 77]

思路

简单模拟

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isSelfDividing(num int) bool {
    for x := num; x > 0; x /= 10 {
        if d := x % 10; d == 0 || num%d != 0 {
            return false
        }
    }
    return true
}

func selfDividingNumbers(left, right int) (ans []int) {
    for i := left; i <= right; i++ {
        if isSelfDividing(i) {
            ans = append(ans, i)
        }
    }
    return
}

发表于 更新于 分类于
本文字数： 460 阅读时长 ≈ 1 分钟

题目

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：
换句话说，就是二进制表示中相邻两位的数字永不相同。

思路

  1. 遍历O(N)
  2. 位运算O(1)，利用+1异或生成全1，加1生成全0，与0必为0。养成加括号的条件
    题目给出条件为正整数，负数题目不成立

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func hasAlternatingBits(n int) bool {
    if n==1 {
        return true
    }
    now:=n%2
    n=n>>1
    for n!=0 {
        next:=n%2
        n=n>>1
        if next^now!=1{
            return false
        }else{
            now=next
        }
    }
    return true
}
1
2
3
4
func hasAlternatingBits(n int) bool {
    a := n ^ n>>1
    return a&(a+1) == 0
}

类似

  • 137 190 191 260 405 461 477 526

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

阅读全文 »

发表于 更新于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

样例

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
输入：digits = “”
输出：[]
输入：digits = “2”
输出：[“a”,”b”,”c”]

思路

排列问题，回溯思想，在某个节点加一个元素往下搜，换一个继续。

  • 路径: 目前已经做了的选择集合
  • 选择列表: 还有哪些列表可选
  • 结束条件: 但索引长度等于数组长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var digitsMap = map[byte]string{
    '2':"abc",
    '3':"def",
    '4':"ghi",
    '5':"jkl",
    '6':"mno",
    '7':"pqrs",
    '8':"tuv",
    '9':"wxyz",
}

func letterCombinations(digits string) (ans []string){
    if len(digits)==0{
        return []string{}
    }

    var dfs func(string, int, string)
    dfs = func(digits string,index int,tmpStr string){
        if index==len(digits){
            ans = append(ans,tmpStr)
        }else{
            for _,char := range digitsMap[digits[index]]{
                tmpStr += string(char)
                dfs(digits,index+1,tmpStr)
                tmpStr = tmpStr[:len(tmpStr)-1]
            }
        }
    }
    dfs(digits,0,"")
    return
}

发表于 更新于 分类于
本文字数： 862 阅读时长 ≈ 1 分钟

题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘ ,’]’ 的字符串 s ，判断字符串是否有效。

阅读全文 »

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。

阅读全文 »

发表于 更新于 分类于
本文字数： 0 阅读时长 ≈ 1 分钟

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目

给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。
对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR … OR a[a.length - 1]（下标从 0 开始）。

阅读全文 »

发表于 更新于 分类于
本文字数： 903 阅读时长 ≈ 1 分钟

题目

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

阅读全文 »

发表于 更新于 分类于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

题目

给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

测试用例

输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

解题思路

1、递归写法
根子树顺序访问节点并加入结果切片中
由于传切片作为参数在append时会分配新的地址空间，故最后递归返回时会导致空.故应传切片指针，谨防空指针问题。
2、非递归写法
2.1 从根节点开始，从右到左入栈，出栈，访问后，将子节点从右到左入栈
2.2

  • 每次入栈时都将当前节点的 uu 的第一个子节点压入栈中，直到当前节点为空节点为止。
  • 每次查看栈顶元素 p，如果节点 p 的子节点已经全部访问过，则将节点 p 的从栈中弹出，并从哈希表中移除，表示该以该节点的子树已经全部遍历过；如果当前节点 p 的子节点还有未遍历的，则将当前节点的 p 的下一个未访问的节点压入到栈中，重复上述的入栈操作。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

func preorder(root *Node) []int {
    // var p *[]int 直接会报空指针错误
    // var ans []int; var p *[]int = &ans也可
    ans := make([]int,0)
    p := &ans
    preOrderTraverse(root,p)
    return ans
}

func preOrderTraverse(root *Node,p *[]int){
    if root==nil{
        return
    }
    *p = append(*p,root.Val)
    for _,node:=range root.Children{
        preOrderTraverse(node,p)
    }
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func preorder(root *Node) (ans []int) {
    // 直接dfs:=func(){dfs()}在递归调用时会被编译器内部认为未定义dfs
    var dfs func(*Node)
    dfs = func(node *Node){
        if node==nil {
            return
        }
        ans = append(ans,node.Val)
        for _,val := range(node.Children){
            dfs(val)
        }
    }
    dfs(root)
    return
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func preorder(root *Node) (ans []int) {
    if root == nil {
        return
    }
    st := []*Node{root} //注意与*[]Node区别, 一个指针指向切片
    for len(st) > 0 {
        node := st[len(st)-1]
        st = st[:len(st)-1]
        ans = append(ans, node.Val) //node.Val等同于(*node).Val 括号不能去掉
        for i := len(node.Children) - 1; i >= 0; i-- {
            st = append(st, node.Children[i])
        }
    }
    return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func preorder(root *Node) (ans []int) {
    if root == nil {
        return
    }
    st := []*Node{}
    nextIndex := map[*Node]int{}// 哈希表记录当前节点子树是否被访问完毕
    node := root
    for len(st) > 0 || node != nil {
        // 将非空节点的第一个子节点，逐个访问后入栈
        for node != nil {
            ans = append(ans, node.Val)
            st = append(st, node)
            if len(node.Children) == 0 {
                break
            }
            nextIndex[node] = 1
            node = node.Children[0] //迭代node
        }
        //抽取栈顶第一个非空节点
        node = st[len(st)-1]
        i := nextIndex[node]
        if i < len(node.Children) { // 对当前节点已访问的子树数量进行比较，少于子节点个数则更新哈希表和当前节点为其下一个子节点继续访问
            nextIndex[node] = i + 1
            node = node.Children[i]
        } else { // 若当前节点的子树已全访问完毕，弹出当前节点并对当前节点置空
            st = st[:len(st)-1]
            delete(nextIndex, node)
            node = nil
        }
    }
    return
}

踩坑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import "fmt"

func main() {
	ans := make([]int,0,100)
	ans = append(ans,1) // [1]
	test(ans)
	fmt.Println(ans[:10]) // [1,12,3,4,0,0,...,0]
	fmt.Println(ans) // [1] 调用函数部分的len不变
	test1(ans)
	fmt.Println(ans) // [3]
}

func test(ans []int){
	ans = append(ans,12,3,4)
}

func test1(ans []int){
	ans[0]=3
}

发表于 更新于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

测试用例

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

输入：l1 = [0], l2 = [0]
输出：[0]

输入：l1 = [1], l2 = [9,9,9,9,9,9]
输出：[0,0,0,0,0,0,1]

解题思路

首先注意到遍历完两个链表存在进位情况，需要分配新的节点。
其次使用for循环遍历到两个链表结尾。并逐个判断条件进位相加。

tips：

  • 创建节点指针，并分配新的节点 &{}
  • 将两个不等长链表用一个for循环遍历到结尾
  • 使用头节点统一操作，并作为变量命名返回(不改变函数签名)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func addTwoNumbers(l1 *ListNode, l2 *ListNode) (head *ListNode) {
        var tail *ListNode
        carry:=0
        for l1!=nil||l2!=nil{
            m,n:=0,0
            if l1!=nil{
                m=l1.Val
                l1 = l1.Next
            }
            if l2!=nil{
                n=l2.Val
                l2 = l2.Next
            }
            
            sum := m+n+carry
            sum,carry = sum%10,sum/10
             
            if head==nil{
                head = &ListNode{Val:sum}
                tail = head
            }else{//妙
                tail.Next = &ListNode{Val:sum}
                tail = tail.Next
            }
        }
        if carry!=0{
            tail.Next = &ListNode{Val:carry}
        }
        return
    }