从根到叶的二进制数之和
题目：给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。以 10^9 + 7 为模，返回这些数字之和。
题目截图
思路：这道题的思路就是遍历每一条到叶节点的二进制数字，然后取模10的9次方+7,直到遍历到叶子节点，则把这个数值加到结果sum中。我先去尝试实现了。
思路没问题，比想的还要简单，这个参考了昨天的那道数组中被5整除的数的技巧。我直接贴代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int sum ;
public int sumRootToLeaf(TreeNode root) {
getNode(root,0);
return sum;
}
public void getNode(TreeNode root ,int i){
if(root==null) return;
i = (i*2+root.val)%1000000007;
//叶子节点值加到sum中
if(root!=null && root.left==null && root.right==null) sum += i;
getNode(root.left,i);
getNode(root.right,i);
}
}
因为这个性能直接超过百分百，所以我也不额外看题解了，这道题真的就是一个遍历+二进制用十进制表示的方法，都很简单，思路通则路路通。
说起来昨天我做的那个被5整除还是在群友的提点下完成的，表白我群友~好了，下一题。
除数博弈
题目：爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
提示：
1 <= N <= 1000
思路：就是如题所示。我感觉这道题很复杂啊，有个最优解的问题，就是怎么做能让对面输，所以这个除数可以很多，但是如何选择最好的那个。。太懵了，我先去看看题目有啥规律。
好了，算是找到规律了。但是不知道对不对。我反正是自己一个个数导的，又是眼睛看出来的规律。
一个数一个数排查
我去提交了，看看对不对。
提交结果
事实证明就是这么简单，这道题就这样吧。
两地调度
题目：公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。
示例：
输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
提示：
1 <= costs.length <= 100
costs.length 为偶数
1 <= costs[i][0], costs[i][1] <= 1000
思路：这个题第一反应是复杂，甚至都想到了动态规划（最近在学dp，看到啥都想到），后来要实现了才发现没有那么难。其实可以这么想，一个人去a和去b两种选择。肯定是要去一个地方，主要区别就是钱的差值。打个比方：a这个人去A100，去B110.然后b这个人去A10，去B50。我们不用考虑100,110,10,50这四个数的比较，只要知道a去A比B便宜10.而b去A比B便宜40。肯定是选择便宜的多的，也就是a去B，b去A。这个逻辑绕明白了就能明白这道题的做法了。
其实我说的比较乱，因为思路也是才理出来。但是方向应该是对的。每个人只要和自身比较就行了，不要和别人比较。目前的想法是都假设去A。然后再比较去B要便宜的钱数（如果本身B比A大这个钱数就是负数。）然后找出一般的人选择便宜的钱数最多的。差不多就这样，我去实现了先。
这个题做出来了，中间有一些波折，有一个测试案例没通过，这个题的参数是数组型数组，java中创建只能一个个往里填，所以我没办法用debug调试知道到底哪里错了，所以很痛苦，眼睛看数组都花了也没看出错误，所以中间试图打算将数组换成队列来做这道题，就是之前刷算法用到的一个自带排序的queue。PriorityBlockingQueue。不过还好改动不小，并且在改动的时候灵机一动感觉找到了不正确的点，所以~~~过了，哈哈，一波三折啊有么有？
我直接贴实现的代码：
class Solution {
public int twoCitySchedCost(int[][] costs) {
int sum = 0;
//去a和去b的差值不会大于999，所以数组长度2000是包含正负
int[] ar = new int[2000];
for(int [] i :costs ){
sum += i[0];
//这个i[1]-i[0]是说去b比去a贵的。如果是正数要减去
ar[i[1]-i[0]+1000] ++;
}
int index = 0;
int i = 0;
while(i<costs.length/2){
while(ar[index]>0&&i<costs.length/2){
sum += (index-1000);
ar[index]--;
i++;
}
index++;
}
return sum;
}
}
这个题用到了常用的技巧数组下标代替数值，因为这个值可能是负的所以我这里都统一加了1000、一开始我错误的点就是第二个while中只判断了ar[index]大于0而没判断i，这也算是一个失误了，思虑不周而且这种情况我自己测试案例没测出来，讲真leetcode测试案例很强大啊。
这个性能是超过百分之九十九的，所以我也不再换方法了。不过讲真，我现在也觉得之前我想的那个排序队列也是可以实现的，只不过我是真的懒得大刀。
这道题就到这里吧，感觉虽然只做了这一道题，但是不断在复习之前学到的知识，比如数组下标代替数值 ，还有队列啊，其实不断刷题的过程也是一个复习的过程~~下一题。
距离顺序排列矩阵单元格
题目：给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）
示例 1：
输入：R = 1, C = 2, r0 = 0, c0 = 0
输出：[[0,0],[0,1]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
示例 2：
输入：R = 2, C = 2, r0 = 0, c0 = 1
输出：[[0,1],[0,0],[1,1],[1,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
示例 3：
输入：R = 2, C = 3, r0 = 1, c0 = 2
输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。
提示：
1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C
思路：这个题我第一遍审题没明白，然后画图理解的：首先行列确定了这个二维块的大小。其次这个r0，c0确定了起始点。然后我们从起始点（距离是0，肯定是最小的）开始按照距离一个个列出来。
草图！！真的很草
当然还有一个距离的规律：
第一个点最多有4个距离1的点，8个距离2 的点，12个距离3的点，其实不用往下继续标也能看出来，应该是16个距离4的点，20个距离5的点。暂时还不知道这个规律有没有用，反正先放着。
距离规律
其实这个自己画两遍就能理解题意了，这个最外层的点是不算的。
- 比如1行1列，则只有一个点0 0 是有效的。
- 一行两列则只有原点 0 0和 0 1是有效的。别的点都在边边上，不算有效。
- 同样道理，2行三列抛出去最外层的边边，相当于位于2-3之间的有效，也就是6个点。
其实这里要说一下，因为坐标的值从0开始，所以点数哪怕不包含最外面的，但是恰好了，1不包含最外的但是包含0一个点,2不包含最外的2但是包含0,1也是两个点。所以点数就是行列数(其实用二维数组更好理解，元素个数就是两个长度的乘积)
到这为止，起码返回值中的点的个数是知道了的。然后一个点分行列两个坐标。坐标好得，关键是距离的大小。最笨的办法就是都算出返回值，挨个算距离。
但是其实我感觉也不见得没有简单算法。比如我们可以以给定点为基点，直接在获取坐标的时候就按照距离获取。当然了这些都是想法， 我要去撸代码实现了。
emmmm....首先实现了，其次没什么简单算法，我没想出来，最后暴力sort解决的，我先贴代码：
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int[][] res = new int[R*C][2];
int k = 0;
for(int i = R-1;i>=0;i--){
for(int j = C-1;j>=0;j--){
res[k] = new int[]{i,j};
k++;
}
}
Arrays.sort(res,new Comparator<Object>() {
@Override
public int compare(Object arg0, Object arg1) {
int[] aa = (int[])arg0;
int[] bb = (int[])arg1;
int a = Math.abs(aa[0]-r0)+Math.abs(aa[1]-c0);
int b = Math.abs(bb[0]-r0)+Math.abs(bb[1]-c0);
return Integer.compare(a,b);
}
});
return res;
}
}
分两步：
- 获取所有的点
- 给点按照距离排序
自己写的排序规则。然后性能凑合，虽然执行速度不尽人意，但是内存消耗超过百分百，也算是有点优点了。
image.png
然后虽然我没想出来。但是我还是觉得应该是有简单算法的啊，明明知道规律却写不出来，就是 给定r0 和c0和实际的大小的判断。。。哎，我决定还是直接看排行第一的代码吧。
很好，直接给我解惑了。我当时有这个想法，但是一来比较麻烦，二来不确定是不是对的所以没有坚持，但是大体分四种情况都想到了，这种我没做出来别人做到了的感觉，，，啧啧，贴上代码瞻仰瞻仰：
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int[][] ans=new int[R*C][2];
ans[0][0]=r0;
ans[0][1]=c0;
int point_x=r0,point_y=c0;
int order=1;
while(order<R*C){
point_x--;
while(point_x<r0){
if(point_x>=0&&point_y<=C-1){
ans[order][0]=point_x;
ans[order++][1]=point_y;
}
point_x++;
point_y++;
}
while(point_y>c0){
if(point_x<=R-1&&point_y<=C-1){
ans[order][0]=point_x;
ans[order++][1]=point_y;
}
point_x++;
point_y--;
}
while(point_x>r0){
if(point_x<=R-1&&point_y>=0){
ans[order][0]=point_x;
ans[order++][1]=point_y;
}
point_x--;
point_y--;
}
while (point_y<c0){
if(point_x>=0&&point_y>=0){
ans[order][0]=point_x;
ans[order++][1]=point_y;
}
point_x--;
point_y++;
}
}
return ans;
}
}
好的吧，我仔细看了第一二三的代码，都是这样分情况直接往里插入就是准确的，其实我也是前期准备做了一堆，写代码的时候懒了。。。哈哈，反正就这样吧。这道题过。
移动石子直到连续
题目：三枚石子放置在数轴上，位置分别为 a，b，c。每一回合，我们假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]
示例 1：
输入：a = 1, b = 2, c = 5
输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。
示例 2：
输入：a = 4, b = 3, c = 2
输出：[0, 0]
解释：我们无法进行任何移动。
提示：
1 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a
思路：我完全不知道这个题是怎么混进来的、感觉很简单啊。我不知道有什么坑，所以去试试。做出来再说。
好了，做出来了，反正就是很简单的一个逻辑，不过中间也有坑，本来我以为a，b，c小到大和xyz是对应的，现在才知道是随机的，所以要知道最大值最小值和中间值。另外一步到位可以跳过y去另一边，反正说到底都是面上的东西，不复杂。直接贴代码：
class Solution {
public int[] numMovesStones(int a, int b, int c) {
int max = a>b?a:b;
max =max>c?max:c;
int min = a>b?b:a;
min = min>c?c:min;
int mid = a+b+c-min-max;
int[] res = new int[2];
res[1] += max-1-mid;
res[1] += mid-1-min;
if(mid==min+1 && max==mid+1){
res[0] = 0;
}else if(mid!=min+1 && max!=mid+1 && mid!=min+2 && max!=mid+2){
res[0] =2;
}else{
res[0]=1;
}
return res;
}
}
有效的回旋镖
题目:回旋镖定义为一组三个点，这些点各不相同且不在一条直线上。给出平面上三个点组成的列表，判断这些点是否可以构成回旋镖。
示例 1：
输入：[[1,1],[2,3],[3,2]]
输出：true
示例 2：
输入：[[1,1],[2,2],[3,3]]
输出：false
提示：
points.length == 3
points[i].length == 2
0 <= points[i][j] <= 100
思路：这样的题我做过类似的，但是这个题让我有点疑问啊，题目说的意思是不是只要能构成三角形的三个点就有效？不用扔前扔后距离相等？我记得上一个回旋镖的题是有这个要求的啊，我去拿个demo试试。
好的，已经确定能组成三角形就行了。
测试demo
那这个题不是简单的的不得了了么？只要三个点横纵坐标不一样且与x/y轴夹角不一样就行了。我去实现了。
这个实现一波三折，因为是程序代码，涉及到除法int型会取整，所以小数除大数都是0.没法比较，所以我的想法太理所当然了。pass
然后自己想了半天，最后求助百度了，其实这个题就是判断三点是不是一线。
判断三点是不是一线
所以说最终就这么做完了。
其实这个算是学到了新的数学知识了吧。
而且不用这种办法另外一种就是两点连线，判断这个第三个点在不在线上，想想都麻烦，还是这个方法最简单。这个题就这样吧
class Solution {
public boolean isBoomerang(int[][] points) {
int x1 = points[0][0];
int y1 = points[0][1];
int x2 = points[1][0];
int y2 = points[1][1];
int x3 = points[2][0];
int y3 = points[2][1];
//令R1=x2-x1,C1=y2-y1；R2=x3-x2,C2=y3-y2。如果R1*C2=R2*C1，那么这三个点就在同一条线上。
if((x2-x1)*(y3-y2)==(y2-y1)*(x3-x2))return false;
return true;
}
}
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
网友评论