LeetCode 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)=max(f(i-1),f(i-2)+nums[i])$
  • 解释：$f(i)$ 代表 偷到第 i 个房屋的最大金额，$max(a,b)$ 代表取 a, b 的较大值，$nums[i]$ 代表第 i 个房屋的金额。
  • 思想：如果已知 偷到第 i - 2 个房屋的最大金额 和 偷到第 i - 1 个房屋的最大金额，那么就可以计算偷到第 i 个房屋的最大金额：要么 延续 偷第 i - 1 个房屋的偷法，要么 偷完第 i - 2 个房屋 后再 偷第 i 个房屋，从中选取一个较大值作为偷到第 i 个房屋的最大金额。
• 初始状态：在状态转移方程中，如果要计算 $f(i)$，则需要 $f(i-1)$ 和 $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];}
}