剑指Offer 17.打印从 1 到最大的 n 位数

剑指 Offer 17. 打印从1到最大的n位数 - LeetCode

2020-8-10 16:20:50

题目描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。

解题思路

在测试环境中可能使用简单方法就可以通过测试用例。这里实际上考察大数的处理。

由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 char 数组进行存储。

只要求输出int类型：

1
2
3
4
5
6
7
8
9

class Solution {
    public int[] printNumbers(int n) {
        int end = (int)Math.pow(10, n) - 1;
        int[] res = new int[end];
        for(int i = 0; i < end; i++)
            res[i] = i + 1;
        return res;
    }
}

1. 字符串循环移位包含

编程之美 3.1

1
2

s1 = AABCD, s2 = CDAA
Return : true

给定两个字符串 s1 和 s2，要求判定 s2 是否能够被 s1 做循环移位得到的字符串包含。

s1 进行循环移位的结果是 s1s1 的子字符串，因此只要判断 s2 是否是 s1s1 的子字符串即可。

739.数组中元素与下一个比它大的元素之间的距离(每日温度)

739.Daily Temperatures (Medium)

Leetcode / 力扣

2020-8-6 21:27:37

题目描述

1
2

Input: [73, 74, 75, 71, 69, 72, 76, 73] 
Output: [1, 1, 4, 2, 1, 1, 0, 0]

Or

1
2
3
4
5

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

160. 找到两个链表的交点

160.Intersection of Two Linked Lists (Easy)

Leetcode / 力扣

2020-7-12 22:03:18

题目描述

找到两个单链表相交的起始节点。。

例如以下示例中 A 和 B 两个链表相交于 c1：

1
2
3
4
5

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

但是不会出现以下相交的情况，因为每个节点只有一个 next 指针，也就只能有一个后继节点，而以下示例中节点 c 有两个后继节点。

1
2
3
4
5

A:          a1 → a2       d1 → d2
                    ↘  ↗
                      c
                    ↗  ↘
B:    b1 → b2 → b3        e1 → e2

要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。

※ 0-1背包

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

定义一个二维数组 dp 存储最大价值，其中 $dp[i][j] $表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

• 第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值，就是总体积不超过 j 的前 i-1 件物品的最大价值，$dp[i][j] = dp[i-1][j]$。
• 第 i 件物品添加到背包中，$dp[i][j] = dp[i-1][j-w] + v$。