[toc]

7. 整数反转 #for #整型

Difficulty: 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）。 示例 1： 输入：x = 123 输出：321 示例 2： 输入：x = -123 输出：-321 示例 3： 输入：x = 120 输出：21 示例 4： 输入：x = 0 输出：0 提示： -231 <= x <= 231 - 1

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2<sup>31</sup>, 2<sup>31 </sup>− 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

1
2
输入：x = 123
输出：321

示例 2：

1
2
输入：x = -123
输出：-321

示例 3：

1
2
输入：x = 120
输出：21

示例 4：

1
2
输入：x = 0
输出：0

提示：

  • -2<sup>31</sup> <= x <= 2<sup>31</sup> - 1

Solution

Language: go

1
2
3
4
5
6
7
8
9
10
11
12
func reverse(x int) (rev int) {
    for x != 0 {
        if rev < math.MinInt32/10 || rev > math.MaxInt32/10 {
            return 0
        }

        digit := x % 10
        x /= 10
        rev = rev*10 + digit
    }
    return 
}

1614. 括号的最大嵌套深度 #字符串 #for

如果字符串满足以下条件之一，则可以称之为 有效括号字符串**（valid parentheses string，可以简写为 VPS**）：

  • 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
  • 字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
  • 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。

类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：

  • depth("") = 0
  • depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
  • depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
  • depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串

例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。

给你一个 有效括号字符串 s，返回该字符串的s 嵌套深度 。

示例 1：

1
2
3
输入：s = "(1+(2*3)+((8)/4))+1"
输出：3
解释：数字 8 在嵌套的 3 层括号中。

示例 2：

1
2
输入：s = "(1)+((2))+(((3)))"
输出：3

示例 3：

1
2
输入：s = "1+(2*3)/(2-1)"
输出：1

示例 4：

1
2
输入：s = "1"
输出：0

提示：

  • 1 <= s.length <= 100
  • s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
  • 题目数据保证括号表达式 s 是 有效的括号表达式

Solution

Language: go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxDepth(s string) (ans int) {
    dept := 0
    for _,ch := range s {
        if ch == '(' {
            dept++;
            if dept >= ans {
                ans = dept
            }
        } else if ch == ')' {
            dept--;
        }
    }
    return 
}

71. 简化路径 #字符串切割 #栈

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名（如果存在）不能 以 '/' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

1
2
3
输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

1
2
3
输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

1
2
3
输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

1
2
输入：path = "/a/./b/../../c/"
输出："/c"

提示：

  • 1 <= path.length <= 3000
  • path 由英文字母，数字，'.'，'/' 或 '_' 组成。
  • path 是一个有效的 Unix 风格绝对路径。

Solution

Language: go

1
2
3
4
5
6
7
8
9
10
11
12
13
func simplifyPath(path string) string {
    stack := []string{}
    for _,name := range strings.Split(path, "/") {
        if name == ".." {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]   
            }
        } else if name != "" && name != "." {
            stack = append(stack, name)
        }
    }
    return "/" + strings.Join(stack,"/")
}

1576. 替换所有的问号 #字符串

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你 不能 修改非 '?' 字符。

题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

1
2
3
输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

1
2
3
输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

示例 3：

1
2
输入：s = "j?qg??b"
输出："jaqgacb"

示例 4：

1
2
输入：s = "??yw?ipkj?"
输出："acywaipkja"

提示：

  • 1 <= s.length <= 100

  • s 仅包含小写英文字母和 '?' 字符

Solution

Language: go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func modifyString(s string) string {
    res := []byte(s)
    n := len(res)
    for i,ch := range res {
        if ch == '?' {
            for b := byte('a'); b <= 'c'; b++ {
                if !(i > 0 && res[i-1] == b || i < n - 1 && res[i+1] == b) {
                    res[i] = b
                    break
                }
            }
        }
    }
    return string(res)
}

1629. 按键持续时间最长的键 #数组

LeetCode 设计了一款新式键盘，正在测试其可用性。测试人员将会点击一系列键（总计 n 个），每次一个。

给你一个长度为 n 的字符串 keysPressed ，其中 keysPressed[i] 表示测试序列中第 i 个被按下的键。releaseTimes 是一个升序排列的列表，其中 releaseTimes[i] 表示松开第 i 个键的时间。字符串和数组的 下标都从 0 开始 。第 0 个键在时间为 0 时被按下，接下来每个键都 恰好 在前一个键松开时被按下。

测试人员想要找出按键 持续时间最长 的键。第 i次按键的持续时间为 releaseTimes[i] - releaseTimes[i - 1] ，第 0 次按键的持续时间为 releaseTimes[0] 。

注意，测试期间，同一个键可以在不同时刻被多次按下，而每次的持续时间都可能不同。

请返回按键 持续时间最长 的键，如果有多个这样的键，则返回 按字母顺序排列最大 的那个键。

示例 1：

1
2
3
4
5
6
7
8
9
输入：releaseTimes = [9,29,49,50], keysPressed = "cbcd"
输出："c"
解释：按键顺序和持续时间如下：
按下 'c' ，持续时间 9（时间 0 按下，时间 9 松开）
按下 'b' ，持续时间 29 - 9 = 20（松开上一个键的时间 9 按下，时间 29 松开）
按下 'c' ，持续时间 49 - 29 = 20（松开上一个键的时间 29 按下，时间 49 松开）
按下 'd' ，持续时间 50 - 49 = 1（松开上一个键的时间 49 按下，时间 50 松开）
按键持续时间最长的键是 'b' 和 'c'（第二次按下时），持续时间都是 20
'c' 按字母顺序排列比 'b' 大，所以答案是 'c'

示例 2：

1
2
3
4
5
6
7
8
9
输入：releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
输出："a"
解释：按键顺序和持续时间如下：
按下 's' ，持续时间 12
按下 'p' ，持续时间 23 - 12 = 11
按下 'u' ，持续时间 36 - 23 = 13
按下 'd' ，持续时间 46 - 36 = 10
按下 'a' ，持续时间 62 - 46 = 16
按键持续时间最长的键是 'a' ，持续时间 16

提示：

  • releaseTimes.length == n
  • keysPressed.length == n
  • 2 <= n <= 1000
  • 1 <= releaseTimes[i] <= 10<sup>9</sup>
  • releaseTimes[i] < releaseTimes[i+1]
  • keysPressed 仅由小写英文字母组成

Solution

Language: go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func slowestKey(releaseTimes []int, keysPressed string) byte {
    n := len(releaseTimes)
    var ans byte = keysPressed[0]
    maxTime := releaseTimes[0]
    for i := int(1); i < n; i++ {
        key := keysPressed[i]
        time := releaseTimes[i] - releaseTimes[i-1]

        if(time > maxTime || (time == maxTime && key > ans)) {
            ans = key
            maxTime = time
        }
    }
    return ans
}

206. 反转链表 #链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev * ListNode
    curr := head
    for curr != nil {
        next := curr.Next

        curr.Next = prev
        prev = curr

        curr = next
    }
    return prev
}

121. 买卖股票的最佳时机 #数组 #dp

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 10<sup>5</sup>
  • 0 <= prices[i] <= 10<sup>4</sup>

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxProfit(prices []int) (max int) {
    min := prices[0]
    max = 0
    for _,price := range prices {
        if price < min {
            min = price
        } else {
            if max > price - min {
                continue
            } else {
                max = price - min
            }
        }
    }
    return
}

剑指 Offer 03. 数组中重复的数字 #数组 #坐标交换

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

1
2
3
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

Solution

坐标交换：通俗讲就是每个人都有一个自己位置，坐标交换就是先把每个人都放到自己的位置上，当发现自己的位置被人占了以后，就说明出现了重复元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func findRepeatNumber(nums []int) int {
    i := 0
    for i < len(nums) {
        if nums[i] == i {
            i++
            continue
        }

        if nums[nums[i]] == nums[i] {
            return nums[i]
        }

        nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
    }
    return -1
}