每日一题之打家劫舍II
问题Link 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。 思路 和昨天的问题一样，属于动态规划问题 房子排成环形，只需要分类讨论，第一间房子偷不偷，区间是[0,k-2],[1,k-1] 特殊情况是只有1间或两间房子。 同样可以节省空间，两个变量循环存储dp数组 代码1234567891011121314151617181920212223class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; } else if (n == 2) { return Math.max(nums...
每日一题之打家劫舍
问题 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路 很经典的动态规划问题 子问题是偷k间屋子的最大收获。 递推关系式：f(k)=max{f(k−1),H+f(k−2)},H是k-1间房子的收获。 dp数组初始值为 dp[0] = 0; dp[1] = nums[0]; 代码1234567891011121314class Solution { public int rob(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; // init dp[0] = 0; dp[1] = nums[0]; // loop for (int i = 2; i <= n; i++) { dp[i] = Math...
每日一题之可以攻击国王的皇后
问题 在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。 给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。 后（英文：Queen，Unicode字符♕U+2655，♛U+2656）是国际象棋棋局中实力最强的一种棋子。 后可横直斜走，且格数不限。 吃子与走法相同。 因为后的实力最强，故而在兵升变时，虽然可以选择变为其他棋子，但绝大多数会选择升变为后。 思路 逆向思维，考虑国王周围的八个方向是否有后。 代码12345678910111213141516171819202122232425262728293031323334353637import java.util.ArrayList;import java.util.Arrays;import java.util.List;class Solution { public List<List<Integer>> queensAttacktheKing(int[][] quee...
每日一题之检查骑士巡视方案
2596. 检查骑士巡视方案 思路 应该使用模拟的方法 对比每次移动是否满足斜着走的规律即可 为了方便比较每次移动路径，需要将矩阵转化为路径序列 代码1234567891011121314151617181920212223242526class Solution { public boolean checkValidGrid(int[][] grid) { if (grid[0][0] != 0) { return false; } int n = grid.length; int[][] indices = new int[n * n][2]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { indices[grid[i][j]][0] = i; indices[grid[i][j]][1] = j; } } for (int i = 0; i < n * n - 1...
每日一题-平衡二叉树
Leetcode每日一题之平衡二叉树「简单」Link 思路 当且仅当子树都是平衡二叉树时，这个树才是平衡二叉树，明显递归好使 判断子树高度也需要递归 Solution12345678910111213141516class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; } return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } int height(TreeNode node) { if (node == null) { return 0; } else { return Math.max(height(node.left), he...
日本語-第十六弾
休みの日、散歩したり、買い物に 行ったり します。動たり 動たり します。 列举若干有代表性动作 た型换为たり 名词与形容词的列举 一类形容词＋かったり「です」 二类形容词/名词＋だったり「です」 小句＋か 「どうか」「表示不确定的内容」 私は 今年の夏、北京へ 行きますか。＋私は わかりません。 → 私は 今年の夏 、北京へ 行くか どうか 分かりません。 李さんは もう すぐ 来ると 思います。小句「简体型」＋と 思います 表示说话人的思考内容 名「人」は 小句 と 言いました。 转述他人的话 〜のです・〜んです〜のです・〜んです 表示所讲内容与前文有关联 どうして 〜のです・〜んです 询问理由的更完整形式
日本語-第十五弾
动词た型变换方法是て型变换，てーた、でーだ。 动词た型＋ことが あります。「表示过去做过」。（一度も）动词た型 ことが ありません。「否定」 动词た型 後で「あとで」、〜「表示在一件事之后」动词た型 ほうが いいです。「怎么怎么做比较好」也可以用名词＋の＋ほうがいいです： 私は リンゴの ほうが いいです。 速いですから 飛行機のほうが いいです。 动词ましょうか「提议」简体与敬体动词简体 敬体 简体 现在将来 買います、買いません 買う、買わない 过去 買いました、買いませんでした 買った、買わなかった 敬体 简体 现在将来 あります、ありません ある、ない 过去 ありました、ありませんでした あった、なかった 一类形容词谓语简体 敬体 简体 现在将来 忙しいです 忙しい 现在将来 忙しく ないです 忙しく ない 过去 忙しかったです 忙しかった 过去 忙しく なかったです 忙しく なかった 二类形容词谓语简体 敬体 简体 现在将来 簡単です 簡単だ 现在将来 簡単では ありません 簡単で...