文章目录
- 9. 回文数
- 题目链接
- 标签
- 思路
- 代码
- 763. 划分字母区间
- 题目链接
- 标签
- 思路
- 代码
- 198. 打家劫舍
- 题目链接
- 标签
- 思路
- 代码
9. 回文数
题目链接
9. 回文数
标签
数学
思路
回文数就是正序和倒序读都一样的数,例如 0, 121, 22
。注意:负数、10
的倍数 都不是回文数。
可以将回文数分成两半:一半是 原先 的顺序,另一半是 颠倒 的顺序。比如将 121
分成 1
和 12
、将 22
分成 2
和 2
,可以发现有两种情况:
- 如果分成的两个数相等,则该数是回文数。
- 如果分成的两个数不相等,则可能是因为该数有奇数位,这时让 颠倒顺序的一半 除以
10
然后与 原先顺序的一半 比较即可,如果相等,则该数是回文数;否则不是回文数。
代码
class Solution {public boolean isPalindrome(int x) {if (x < 0) { // 如果 x 是负数return false; // 则 x 不是回文数,返回 false} else if (x % 10 == 0 && x != 0) { // 如果 x 是 10 的倍数,但不是 0return false; // 则 x 不是回文数,返回 false}// 反转int rev = 0; // 颠倒的另一半while (x > rev) {rev = (rev * 10) + (x % 10);x /= 10;}return x == rev // 要么 原先顺序的一半 等于 颠倒顺序的一半|| x == rev / 10; // 要么 原先顺序的一半 等于 去除“多余”位数的颠倒顺序的一半}
}
763. 划分字母区间
题目链接
763. 划分字母区间
标签
贪心 哈希表 双指针 字符串
思路
既然需要让同一个字母最多出现在一个片段中,那么就可以使用 贪心 的思想来 枚举每一个片段的右端点:
- 先记录每个小写字母在字符串中最后一次出现的索引。
- 遍历字符串中每一个字符:
- 枚举当前片段的右端点:在 原右端点 和 当前字母最后一次出现的索引 中挑一个较大值。
- 如果 当前索引 是 当前片段的右端点,则说明 这一个片段中没有字母出现在别的片段中,也就是让同一个字母最多出现在一个片段中,达成条件,记录这个片段,更新左、右端点,准备划分下一个区间。
其中,达成条件后记录这个片段 使用了贪心的思想,如果不在此时记录,则不能将字符串划分成尽可能多的片段。
代码
class Solution {public List<Integer> partitionLabels(String s) {char[] sC = s.toCharArray();int len = sC.length;int[] last = new int[26]; // 保存每个小写字符最后出现的索引for (int i = 0; i < len; i++) {last[sC[i] - 'a'] = i;}List<Integer> partition = new ArrayList<>(); // 对字母区间的划分int left = 0, right = 0; // 当前片段的 左端点 和 右端点for (int i = 0; i < len; i++) {right = Math.max(right, last[sC[i] - 'a']); // 枚举当前片段的右端点if (i == right) { // 如果 当前索引 等于 当前片段的右端点partition.add(right - left + 1); // 记录这个片段left = right + 1; // 更新左、右端点}}return partition;}
}
198. 打家劫舍
题目链接
198. 打家劫舍
标签
数组 动态规划
思路
本题需要使用 动态规划 的思想:
- 状态转移方程: f ( i ) = m a x ( f ( i − 1 ) , f ( i − 2 ) + n u m s [ i ] ) f(i) = max(f(i - 1), f(i - 2) + nums[i]) f(i)=max(f(i−1),f(i−2)+nums[i])
- 解释: f ( i ) f(i) f(i) 代表 偷到第
i
个房屋的最大金额, m a x ( a , b ) max(a, b) max(a,b) 代表取a, b
的较大值, n u m s [ i ] nums[i] nums[i] 代表第i
个房屋的金额。 - 思想:如果已知 偷到第
i - 2
个房屋的最大金额 和 偷到第i - 1
个房屋的最大金额,那么就可以计算偷到第i
个房屋的最大金额:要么 延续 偷第i - 1
个房屋的偷法,要么 偷完第i - 2
个房屋 后再 偷第i
个房屋,从中选取一个较大值作为偷到第i
个房屋的最大金额。
- 解释: f ( i ) f(i) f(i) 代表 偷到第
- 初始状态:在状态转移方程中,如果要计算 f ( i ) f(i) f(i),则需要 f ( i − 1 ) f(i - 1) f(i−1) 和 f ( i − 2 ) f(i - 2) f(i−2),也就是需要前两个值,此时就有两个初始状态了:
- 偷第
0
个房屋的最大金额:直接偷第0
个房屋即可,无需多想。 - 偷第
1
个房屋的最大金额:从 第0
个房屋的金额 和 第1
个房屋的金额 中选取一个较大值。
- 偷第
代码
class Solution {public int rob(int[] nums) {if (nums.length == 1) { // 如果只有一个房屋return nums[0]; // 则直接返回这个房屋的金额}int len = nums.length;int[] dp = new int[len + 1]; // dp[i] 表示偷到第 i 个房屋的最大金额dp[0] = nums[0]; // 偷到第 0 个房屋的最大金额就是第 0 个房屋的金额// 偷到第 1 个房屋的最大金额为 从第 0、1 个房屋的金额中 选取的较大值dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < len; i++) {// 从 上一个最大值 和 上上一个最大值+当前值 中选出一个更有价值的偷法dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[len - 1];}
}