ONE NOTE

Rage, rage against the dying of the light.

Posted on In

问题

Link

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

思路

  1. 和昨天的问题一样，属于动态规划问题
  2. 房子排成环形，只需要分类讨论，第一间房子偷不偷，区间是[0,k-2],[1,k-1]
  3. 特殊情况是只有1间或两间房子。
  4. 同样可以节省空间，两个变量循环存储dp数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
	public int rob(int[] nums) {
		int n = nums.length;
		if (n == 1) {
			return nums[0];
		} else if (n == 2) {
			return Math.max(nums[0], nums[1]);
		} else {
			return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
		}
	}

	public int robRange(int[] nums, int start, int end) {
		int prev = 0;
		int curr = 0;
		for (int i = start; i <= end; i++) {
			int temp = Math.max(curr, prev + nums[i]);
			prev = curr;
			curr = temp;
		}
		return curr;
	}
}

Posted on In

问题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

思路

  1. 很经典的动态规划问题
  2. 子问题是偷k间屋子的最大收获。
  3. 递推关系式：f(k)=max{f(k−1),H+f(k−2)},H是k-1间房子的收获。
  4. dp数组初始值为dp[0] = 0; dp[1] = nums[0];

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class 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.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
		}
		return dp[n];
	}
}

优化

由于只要dp数组最后一位，没必要存储整个dp数组。为了节约空间，可以两个变量循环保存中间量。

优化代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	public int rob(int[] nums) {
		int prev = 0;
		int curr = 0;
		for (int i : nums) {
			int temp = Math.max(curr, prev + i);
			prev = curr;
			curr = temp;
		}
		return curr;
	}
}

Posted on In

问题

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。

给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。

后（英文：Queen，Unicode字符♕U+2655，♛U+2656）是国际象棋棋局中实力最强的一种棋子。 后可横直斜走，且格数不限。 吃子与走法相同。 因为后的实力最强，故而在兵升变时，虽然可以选择变为其他棋子，但绝大多数会选择升变为后。

思路

  1. 逆向思维，考虑国王周围的八个方向是否有后。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
	public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
		int[][] directions = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 } };
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		// enumerate all directions
		dirs: for (int i = 0; i < directions.length; i++) {
			int[] tmp = new int[2];
			tmp[0] = king[0];
			tmp[1] = king[1];
			int[] dir = directions[i];
			// extend
			while (!isCross(tmp)) {
				tmp[0] += dir[0];
				tmp[1] += dir[1];
				// compare all queens
				for (int j = 0; j < queens.length; j++) {
					if (Arrays.equals(tmp, queens[j])) {
						List<Integer> posList = new ArrayList<Integer>();
						posList.add(queens[j][0]);
						posList.add(queens[j][1]);
						res.add(posList);
						continue dirs;
					}
				}
			}
		}
		return res;
	}

	boolean isCross(int[] pos) {
		return !(pos[0] > -1 && pos[0] < 8 && pos[1] > -1 && pos[1] < 8);
	}
}

其他注意

  1. 低级错误：int[]类型是引用传递，没注意到导致bug.

另一个想法

  1. 直接将所有坐标的差值计算出来，计算是否满足对角线或直线的规则。
  2. 这么做的话，需要考虑是否有遮挡，也就是一个方向只能用一次（平方和小的）。
  3. 最后将坐标差值加上国王坐标，还原王后坐标。

Posted on In

2596. 检查骑士巡视方案

思路

  1. 应该使用模拟的方法
  2. 对比每次移动是否满足斜着走的规律即可
  3. 为了方便比较每次移动路径，需要将矩阵转化为路径序列

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class 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; i++) {
			if (!isDiagonal(indices[i], indices[i + 1])) {
				return false;
			}
		}
		return true;
	}

	boolean isDiagonal(int[] p1, int[] p2) {
		int diagonal = Math.abs((p1[0] - p2[0]) * (p1[1] - p2[1]));
		return diagonal == 2;
	}
}

Posted on In

Leetcode每日一题之平衡二叉树「简单」

Link

思路

  1. 当且仅当子树都是平衡二叉树时，这个树才是平衡二叉树，明显递归好使
  2. 判断子树高度也需要递归

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class 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), height(node.right)) + 1;
		}
	}
}

优化方向

  1. height函数多次重复调用，可以使用缓存

Posted on In

休みの日、散歩したり、買い物に 行ったり します。

動たり 動たり します。

  • 列举若干有代表性动作
  • た型换为たり

名词与形容词的列举

  • 一类形容词＋かったり「です」
  • 二类形容词/名词＋だったり「です」

小句＋か 「どうか」「表示不确定的内容」

  • 私は 今年の夏、北京へ 行きますか。＋私は わかりません。
  • → 私は 今年の夏 、北京へ 行くか どうか 分かりません。

李さんは もう すぐ 来ると 思います。

小句「简体型」＋と 思います

  • 表示说话人的思考内容

名「人」は 小句 と 言いました。

  • 转述他人的话

〜のです・〜んです

〜のです・〜んです

  • 表示所讲内容与前文有关联

どうして 〜のです・〜んです

  • 询问理由的更完整形式

Posted on In

动词た型

变换方法是て型变换，てーた、でーだ。

动词た型＋ことが あります。「表示过去做过」。

（一度も）动词た型 ことが ありません。「否定」

动词た型 後で「あとで」、〜「表示在一件事之后」

动词た型 ほうが いいです。「怎么怎么做比较好」

也可以用名词＋の＋ほうがいいです：

私は リンゴの ほうが いいです。

速いですから 飛行機のほうが いいです。

动词ましょうか「提议」

简体与敬体

动词简体

敬体简体
现在将来買います、買いません買う、買わない
过去買いました、買いませんでした買った、買わなかった
敬体简体
现在将来あります、ありませんある、ない
过去ありました、ありませんでしたあった、なかった

一类形容词谓语简体

敬体简体
现在将来忙しいです忙しい
现在将来忙しく ないです忙しく ない
过去忙しかったです忙しかった
过去忙しく なかったです忙しく なかった

二类形容词谓语简体

敬体简体
现在将来簡単です簡単だ
现在将来簡単では ありません簡単では ない
过去簡単でした簡単がった
过去簡単では ありませんでした簡単では なかった

名词谓语简体

敬体简体
现在将来晴れです晴れだ
现在将来晴れでは ありません晴れでは ない
过去晴れでした晴れがった
过去晴れでは ありませんでした晴れでは なかった