难度: 简单 标题：第一个坏版本

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

找出最先坏的版本。

思路

二分法查询。主要要注意的是mid = head + (tail - head)/2。假如使用head + tail 会越界。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int head = 1;int tail = n;
        while(!isBadVersion(head) && head <= tail){
            int mid = head + (tail - head)/2;
            if(isBadVersion(mid)){
                tail = mid -1;
                
            }else{
                head = mid + 1;
            }
        }
        return head;
    }
}

链接

https://leetcode.com/problems/first-bad-version/

难度: 简单 标题：相同二叉树

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

判断两颗二叉树是否相同。

思路

递归，当左子树相同，右子树相同，值相同时两棵树相同。

取子树之前判断一下是否为 null。否则null.left,null.right,null.val会报错。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null || q == null){
            if(p== null && q == null){
                return true;
            }else return false;
        }
        return p.val == q.val &&isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);
    }
}

链接

https://leetcode.com/problems/same-tree/

难度: 简单 标题：2的冥

Given an integer, write a function to determine if it is a power of two.

判断一个是否是2的幂。

思路

一个数转换成二进制后，假如此数为2的冥，则它的形式一定是100…000。

所以只要不断右移，计算1出现的次数。n & 1 ,假如 n 末尾为1，则结果为1.末尾为 0，结果为 0；

代码

1
2
3
4
5
6
7
8
9
10

public class Solution {
    public boolean isPowerOfTwo(int n) {
        int ctz = 0;
        while(n > 0){
            ctz += (n & 1);
            n = n >> 1;
        }
        return ctz == 1;
    }
}

链接

https://leetcode.com/problems/power-of-two/

本文转载自：http://d7vg.com/topic/26907 原作者：sariel_qiu

奖杯攻略

游戏奖杯非常简单易懂，结局杯 + 收集杯 + 支线杯 + 调查杯 + 回信杯。

结局一共有五个，影响结局的只有1 - 7章的回信，不同的行代表不同的结局。

某些结局为二周目限定。

第一行——灵异结局
第二行——姬森公主结局
第三行——彼此错过结局

第一行——灵异结局
第二行——姬森公主结局
第三行——政府阴谋结局
第四行——彼此错过结局
第五行——真结局

五个结局全部打通即可获得结局杯，按照流程收集杯也可同时获取。

调查杯需要调查200次，通关以后假如没获得，可以对着一个地方连续调查200次。

支线杯只需要完成 支线1 即可完成，在第八章完成以后再做。

回信杯可以等最后五个结局打完，再开始快进到第三章，M开头的刨冰店点饮水机前存个档，信封选项后读档选另外没选的，以此类推，可以跳奖杯。

流程攻略

第一章

贵之的家·房间 调查 书柜第二层右侧信笺
回信
出云机场 调查 右侧书架最底层
出云机场 观光导览
候车室 调查 大门
电车 调查 车箱顶部的黄色传单
温泉站 手机
地图 移动 文野家
文野家 调查 草地
文野家 询问 关于此地
文野家 持有物品 没盖邮戳的信封
文野家 观光导览
地图 移动 神在庵
神在庵 调查 随意调查
神在庵 MAX模式 第四档 我是MAX大胃王！
神在庵 询问 空地的火灾
神在庵 询问 文野家的女儿
神在庵 询问 能够调查火灾的场所
地图 移动 中央图书馆
图书馆 调查 最右边书架
地图 移动 松江庄
松江庄 询问 火灾
松江庄 持有物品 亚弥的照片
大澡堂 询问 职业
地图 移动 京店商店街
京店商店街 询问 认不认识亚弥*2
京店商店街 持有物品 亚弥的照片
地图 移动 美术馆 美丽又成熟的大姐姐！
美术馆 调查 画作
美术馆 思考
美术馆 持有物品 亚弥的照片
地图 移动 松江大庭高中
松江大庭高中 调查 随意调查
松江大庭高中 询问 文野亚弥
地图 移动 中村BAR
中村BAR 调查 照片
中村BAR 询问 野津的苦衷
中村BAR 询问 野津的年龄
中村BAR 持有物品 亚弥的照片

第二章

回信
地图 移动 空地
空地 持有物品 亚弥的照片
空地 观光导览
地图 移动 八重垣神社
八重垣神社 调查 地图最左边的房间
镜池 调查 水池
镜池 询问 为什么在这里
镜池 移动 社务所
社务所 调查 占卜净纸
社务所 移动 镜池
镜池 持有物品 净纸
镜池 调查 水池
镜池 移动 社务所
社务所 询问 神签
社务所 询问 金猫
社务所 观光导览
地图 移动 TSK中央电视台
电视台·柜台 询问 相见美咲 我叫野津or随便
电视台·柜台 调查 柜台贴着的第二张红色海报
电视台·柜台 询问 是不是美咲
电视台·柜台 询问 文野亚弥
电视台·柜台 询问 15年前的笔友
电视台 思考 灵光一现！
地图 移动 松江市公所
松江市公所·柜台 询问 市民生活辅导课
松江市公所·柜台 移动 市民生活辅导课
松江市公所·柜台 调查 柱子上的蓝色公布栏
松江市公所·柜台 询问 田中耕介
松江市公所·柜台 移动 市民生活辅导课
市民生活辅导课 询问 田中耕介and田中所在处
市民生活辅导课 移动 后门外
后门外 询问 田中的绰号
后门外 询问 文野亚弥
后门外 持有物品 三花猫护符
地图 移动 八重垣神社
社务所 询问 神签
八重垣神社 思考
八重垣神社 选项依次为：温柔，凶狠，温柔
八重垣神社 询问 猫的名字
地图 移动 松江市公所
开始追问
持有物品 金猫护符
询问 文野亚弥
询问 对美咲死心塌地
询问 田中的职员证
持有物品 旅馆的报纸
询问 松江新讯
询问 田中是资优生
思考
MAX模式 第四档 你就是个庸才加蠢货！！！
询问 田中的假发 玩舰娘的秃头
MAX模式 第四档 看我把它摘下来！！！
询问 文野亚弥
持有物品 田中先生的领带
MAX模式 第四档 你个死脑筋的半吊子！！！
询问 给亚弥的礼物
追问完毕
后门外 询问 文野亚弥
后门外 持有物品 亚弥的照片

第三章

地图 移动 神在庵
神在庵 询问 今日推荐
神在庵 调查 电视旁边的头像
神在庵 询问 文野家的鬼魂
神在庵 询问 高中生聚集的场所
神在庵 观光游览
地图 移动 Marukoshi
Marukoshi 调查 画面中间的窗户
店内 调查 饮水机
回信
店内 持有物品 亚弥的照片
店内 询问 对松江熟悉的人
地图 移动 白鸟号
白鸟号 询问 随便 什么都别说了上船
船上 调查 左下角桌子上的手册
船上 调查 电视
白鸟号 持有物品 亚弥的照片
白鸟号 询问 15年前的大赛
白鸟号 询问 猴子
白鸟号 思考
地图 移动 图书馆
图书馆 思考
地图 移动 白鸟号
白鸟号 思考
地图 移动 松江大庭高中
操场 询问 教练的绰号
操场 询问 松井同学是王牌
操场 询问 野手
操场 询问 签名球
操场 思考
地图 移动 松江市公所
辅导课 思考
辅导课 询问 告状的人
地图 移动 白鸟号
白鸟号 持有物品 签名球
房间 询问 猴子狂热鸡尾酒的店
地图 移动 中村BAR
店内 询问 亚弥
店内 询问 酒的名字
大街 询问 你是猴子
开始追问
持有物品 决赛报道影本
持有物品 全垒打球
持有物品 大胃王记录照片
MAX模式 第四档 你就是猴子吧！！
询问 暴力事件
询问 大赛夺冠的可能性
MAX模式 第三档 你曾经误入歧途
询问 渡边教会他人生道理
MAX模式 第一档 多亏了她
追问完毕
大桥 询问 文野亚弥
MAX模式 第一档 告诉我联络方式

第四章

回信
房间 询问 姬森公主
地图 移动 城山公园
城山公园 调查 右侧导览图
导览处内部 询问 仓井礼一
导览处内部 移动 镇守之森散步道
喫茶处来春 询问 大庭高中的诅咒
喫茶处来春 询问 笔友
门口 思考
门口 观光导览
地图 移动 京店商店街
京店商店街 询问 推荐的店
京店商店街 观光导览
地图 移动 神在庵
神在庵 持有物品 亚弥照片
神在庵 询问 蛋糕店
地图 移动 京店商店街
京店商店街 持有物品 健身传单
京店商店街 思考
京店商店街 持有物品 蛋糕店传单
地图 移动 Patisserie Pure
Pa Pu 调查 左上角的玻璃油灯
Pa Pu 询问 莓果塔
Pa Pu 询问 大庭高中
地图 移动 卡拉考拉工房
工房内 持有物品 亚弥照片
工房内 调查 满是照片的桌子
地图 移动 Pa Pu
Pa Pu 询问 减肥
千鸟南公园 思考*2
开始追问
持有物品 健身房传单
持有物品 15年前的照片
MAX模式 第二档 只吃一片没关系
询问 询问 油灯
MAX模式 第三档 我的推理没错吧！
MAX模式 第三档 你还没对人家死心吗！
追问完毕
千鸟南公园 询问 亚弥
地图 移动 Pa Pu
Pa Pu 询问 店长
Pa Pu 思考
地图 移动 松江站
伴手礼店 调查 画面中偏下的小兔子
地图 移动 松江庄
房间 询问 蛋糕
地图 移动 空地
空地 询问 工作 由香里姐姐私服也很棒呢
商店街 调查 右侧第一个店家and邮筒and地面
店内 调查 粉色邮筒
店内 询问 观光地点

第五章

回信
房间 询问 女艺人
地图 移动 Pa Pu
Pa Pu 调查 门上的牌子
地图 移动 丸子屋萌音
店内 持有物品 亚弥的照片
店内 询问 蛋糕
店内 询问 同学
地图 移动 出云市·幽浮研究所
幽浮研究所 持有物品 兔子挂饰
研究所内部 调查 墙上海报
研究所内部 询问 幽浮
研究所内部 调查 墙上海报
研究所内部 询问 阿嘎
地图 移动 神在庵
神在庵 调查 右边的沙滩海报
神在庵 导览观光
神在庵 询问 鬼魂
地图 移动 新闻报社
新闻报社 询问 手册
地图 移动 京都商业街
饰品店 调查 画面下方小鸟挂饰
地图 移动 剧院兔子
剧院 询问 佐佐木理子
Water W 持有物品 小鸟
Water W 持有物品 学生名册
Water W 持有物品 亚弥的照片
地图 移动 出云市·幽浮研究所
幽浮研究所 持有物品 兔子挂饰
研究所内部 询问 佐佐木理子
研究所内部 询问 佐佐木亚里沙签名
地图 移动 神在庵
神在庵 询问 RICO的海报
地图 移动 剧院兔子
MAX模式 第四档 写真女星RICO小姐
开始追问
持有物品 名册抄本
持有物品 羽田珠里奈的明星照
持有物品 岬理子的CD
持有物品 RICO的海报
MAX模式 第三党 太奇怪了！
MAX模式 第一档 对不起
持有物品 签名明星照
追问完毕
剧场 思考
剧场 持有物品 亚弥的照片
中村 移动 中村BAR
中村BAR 询问 争执的原因
中村BAR 调查 大门
店内部 调查 桌子上的杯垫
地图 移动 旅馆
房间 持有物品 亚弥的照片
房间 询问 文野亚弥的父亲and文野亚弥
房间 询问 笔友

第六章

回信
房间 询问 英雄
房间 持有物品 小泉八云的书
地图 移动 小泉八云纪念馆
展厅 调查 四个区域都调查一遍
展厅 调查 最右边的照片
展厅 调查 左上侧的海报
展厅 调查 中间偏上的简介
展厅 思考
地图 移动 出云市·幽浮研究所
幽浮研究所 持有物品 兔子挂饰
研究所内部 持有物品 企划宣传单
研究所内部 询问 盛田
研究所内部 询问 阿嘎
地图 移动 电视台
柜台 询问 村上美咲
柜台 调查 海报然后调查拍卖会
柜台 询问 村上美咲
电视台 思考
地图 移动 WaterWork
WaterWork 询问 村上美咲
地图 移动 大庭高中
操场 询问 被咬
操场 询问 编制手环
地图 移动 松江市公所
辅导课 持有物品 石蒜花胸针
辅导课 询问 从前的美咲
地图 移动 神在庵
神在庵 思考
神在庵 调查 电视
地图 移动 丸子屋萌音
丸子屋萌音 询问 小胖的状况
地图 移动 山城公园
开始追问
持有物品 亚弥的照片
询问 一起长大的盛田
持有物品 国中照片
持有物品 编制手环
MAX模式 第一档 你就是阿嘎吧？
持有物品 15年前照片
持有物品 15年前照片
MAX模式 第一档 我只是想要见她
MAX模式 第一档 相信我把
询问 石蒜花胸针
追问完毕
松江城 询问 15年前发生了什么
地图 移动 松江庄
澡堂 询问 有用的资讯
地图 移动 京店商店街
DVD店 调查 上方DVD
地图 移动 松江庄

第七章

回信
房间 询问 妖怪
地图 移动 松江站
松江站 询问 妖怪3
松江站 移动 伴手礼
伴手礼 询问 妖怪2and松江历史馆
伴手礼 观光导览
地图 移动 松江历史馆
馆内 探索 一共能点四处
馆内 询问 凤凰火
馆内 调查 伴手礼
大街 调查 船
地图 移动 松江市公所
辅导课 询问 野津的咨询*2
地图 移动 剧团兔子
地图 移动 WaterWork
地图 移动 中村BAR
中村BAR 调查 大门
中村BAR 询问 野津的咨询
地图 移动 剧团兔子
地图 移动 WaterWork
WaterWork 询问 佐佐木理子来店资讯
WaterWork 询问 野津的咨询
WaterWork 询问 野津的家人and身高
地图 移动 Marukoshi
店内 询问 袭击的理由
店内 询问 袭击的目的
店内 询问 过去的绰号
地图 移动 城山公园
城山公园 询问 问话的对象
城山公园 询问 简讯
松江站前 观光导览
地图 移动 堀川游览船
堀川游览船 思考
乘船场 观光游览
小巷 观光游览
开始追问
持有物品 泼沙婆婆的沙
持有物品 亚弥的照片
询问 野津的过去
持有物品 野津的CD
MAX模式 第二档 你觉得很丢脸吧
询问 阿嘎坐立不安的理由
调查 增高鞋
询问 野津一建设公司的大少爷
询问 野津怕水
询问 野津的母亲
MAX模式 第三档 内心还是个小少爷
MAX模式 第三档 你妈妈会伤心的，宝贝儿子被抓了
追问完毕
小巷 询问 传闻
地图 移动 图书馆
图书馆 调查 依旧最右边的书架
图书馆 询问 14年前的报纸
图书馆 询问 15年前的报纸
地图 移动 Pa Pu
Pa Pu 持有物品 草莓果酱
Pa Pu 询问 自杀

第八章

看信
房间 询问 女生友谊
房间 思考
地图 移动 空地
空地 调查 空地上的花
空地 询问 枯萎的花
空地 持有物品 名册
地图 移动 神在庵
神在庵 思考
神在庵 询问 店长的表情
地图 移动 京店商店街
京店商店街 移动 DVD店
DVD店 调查 CD
地图 移动 丸子屋萌音
店内 询问 胭脂虫
店内 询问 同班同学
丸子屋萌音 观光导览
地图 移动 玉作汤神社
玉作汤神社 调查 左边房子
地图 移动 玉作汤神社
地图 移动 玉造温泉街
地图 移动 伴手礼品店
伴手礼品店 调查 中偏下的挂坠
伴手礼品店 询问 坠子的颜色
地图 移动 松江市公所
地图 移动 剧团兔子
地图 移动 WaterWork
地图 移动 大庭高中
操场 询问 好姐妹
玄关 调查 职员窗户
玄关 询问 手册
地图 移动 城山公园
地图 移动 电视台
柜台 调查 第一张海报
柜台 询问 好姐妹
柜台 询问 美咲的梦想
电视台 思考
地图 移动 美术馆
馆内 询问 石原小姐的姓氏
闺房 询问 要帮什么忙
闺房 询问 酒的名字and石原这个姓氏
开始追问
询问 好姐妹
持有物品 大庭高中手册
持有物品 果渣白兰地酒照片
持有物品 杯垫
询问 喜欢的人
MAX模式 第四档 你就是好姐妹
询问 石原这个姓氏
MAX模式 第一档 你就是好姐妹吧
持有物品 伴手礼手册
MAX模式 第五档(要等) 我的忍耐要到极限了
询问 胭脂虫
询问 美术馆假日
持有物品 报纸照片影本
MAX模式 沉默（一直等到最后） 我爱你啊啊啊
追问完毕
闺房 移动 松江庄

灵异结局

第九章

看信
房间 思考
地图 移动 松江站
松江站 移动 旧书店
松江站 调查 咖啡厅门口的广告
松江站 移动 小云堂
小云堂 询问 想要的东西
小云堂 持有物品 大林朝日的唱片
松江站 询问 不可思议
京店商店街 询问 不可思议
丸子屋萌音 询问 不可思议
京店商店街 询问 不可思议
城山公园 询问 不可思议
城山公园 思考
剧团兔子 询问 不可思议
地图 移动 松江站 小云堂
小云堂 询问 源助柱 新娘岛 城中的狐狸 洗豆桥 小孩的鬼魂 育儿糖 松江城的活祭品
地图 移动 神在庵
神在庵 询问 照烧公鱼
地图 移动 松江庄
地图 移动 宍道湖畔
宍道湖畔 持有物品 11月杂志
宍道湖畔 思考
宍道湖畔 询问 扮演文野的理由
宍道湖畔 询问 扮演文野的经过
宍道湖畔 询问 吉岡栞
宍道湖畔 询问 她的容貌
宍道湖畔 询问 吉岡栞的目的
宍道湖畔 询问 吉岡栞

终章

看信
房间 思考
地图 移动 松江站
松江站 询问 其他同学
松江站 询问 诅咒
松江站 询问 思考
松江站 询问 田中可能去的地方
MAX模式 第四档 只有你！！
文野家 调查 大门
GG

姬森公主

第九章

房间 思考
地图 移动 松江站
旧书店 询问 旧杂志
松江站 调查 咖啡厅门口的广告
松江站 移动 小云堂
小云堂 调查 左上角杂志
小云堂 询问 价格
小云堂 持有物品 大林朝日的唱片
地图 移动 松江庄
房间 询问 想起来的办法
地图 移动 神在庵
神在庵 询问 照烧公鱼
神在庵 询问 松江庄老板娘
地图 移动 松江庄
天守阁 观光游览
灯塔 询问 吉岡栞
地图 移动 Marukoshi
店内 询问 依次询问
店内 持有物品 11月刊
MAX模式 第二档 我想知道15年前发生的事情
宍道湖畔 持有物品 11月刊
宍道湖畔 询问 15年前发生的事情
宍道湖畔 思考
宍道湖畔 询问 15年前发生的事情
宍道湖畔 询问 扮演文野亚弥的经过
宍道湖畔 询问 吉岡栞
宍道湖畔 询问 吉岡栞
宍道湖畔 询问 之后的她
宍道湖畔 询问 吉岡栞
宍道湖畔 询问 毕业庆典
宍道湖畔 询问 吉岡栞

终章

看信
玄关 询问 吉岡小姐的住址
医院 询问 她可能去的地方
WaterWork 思考

政府阴谋

第九章

看信
地图 移动 剧团兔子
地图 移动 WaterWorks
地图 移动 神在庵
地图 移动 丸子屋萌音
店内 持有物品 11月刊
店内 询问 野津的纪念册
店内 思考
旧书店 询问 目的
小云堂 持有物品 大林朝日的唱片
店内 持有物品 野津的纪念册
店内 询问 第一印象
店内 询问 前往文野家的理由
店内 询问 栞的变化
店内 询问 隐瞒吉岡栞的理由
店内 询问 她的真正形象
店内 询问 不好的回忆

终章

看信
房间 思考
大街 思考
幽浮研究所 兔子挂饰
灯塔 思考
END

彼此错过

第九章

看信
房间 询问 十一月号
地图 移动 松江站
旧书店 调查 书堆
旧书店 询问 旧杂志
地图 移动 神在庵
神在庵 询问 照烧公鱼
神在庵 询问 半价
地图 移动 松江站
松江站 调查 咖啡店门口的传单
小云堂 持有物品 大林朝日的唱片
小云堂 调查 左上方的杂志
地图 移动 松江庄
宍道湖畔 持有物品 11月刊
宍道湖畔 询问 15年前
宍道湖畔 询问 通信
宍道湖畔 询问 吉岡栞
宍道湖畔 思考
宍道湖畔 询问 害怕的理由
宍道湖畔 询问 她真正的想法
宍道湖畔 询问 两人的关系
宍道湖畔 询问 之后的她
宍道湖畔 询问 她的所在地

终章

看信
房间 思考
地图 移动 松江站
松江站 调查 伴手礼店
地图 移动 神在庵
地图 移动 城山公园
天守阁 思考
天守阁 询问 回忆的场所
灯塔 询问 田中
灯塔 持有物品 宍道湖徽章
WaterWorks 询问 文野教授的所在处
后院 询问 栞杀的人
END

真结局

第九章

地图 移动 松江站
松江站 移动 旧书店
旧书店 调查 3次书
地图 移动 随机移动五个地点
地图 移动 神在庵
神在庵 询问 盖章积点活动
神在庵 询问 女高中生
小云堂 持有物品 大林朝日的唱片
小云堂 持有物品 SHIMANEKKO毛巾
地图 移动 松江庄
开始追问
持有物品 十一月刊
询问 吉岡栞
询问 通讯的理由
询问 当天旅行发生的事情
询问 扮演亚弥
询问 通讯对象亚弥
询问 不寻常的事情
询问 栞的成绩和田中的成绩
询问 大家所害怕的事情
MAX模式 第二档 害怕喜欢的人被抢走
持有物品 15年前的照片
询问 野津笑的理由
询问 伪装自杀
询问 吉岡栞的现状
追问完毕

终章

天守阁 询问 回忆的场所
天守阁 思考
天守阁 询问 经常去的地方
松江站 询问 交通方式
灯塔 询问 自杀
灯塔 询问 大家的状况
灯塔 询问 大家的梦想
灯塔 思考
灯塔 询问 田中的遭遇
灯塔 询问 现在的田中
灯塔 思考
灯塔 思考
灯塔 询问 文野家的火灾
灯塔 思考
灯塔 思考
灯塔 询问 文野家的火灾
灯塔 询问 文野家的火灾
灯塔 询问 同班同学
灯塔 询问 吉岡栞
灯塔 询问 获得帮助的经验
灯塔 询问 毕业

支线攻略

支线 1.寻找吉祥物

地图 移动 神在庵 调查 看板
美术馆馆内 报告 (之后每次找到都要报告)
地图 移动 空地 调查 民家
地图 移动 松江站 调查 右边道路
地图 移动 商店街 调查 邮筒
地图 移动 城山公园 观光导览处 调查 自动贩卖机
地图 移动 松江大庭高中 操场 调查 左边网子
地图 移动 城山公园 松江城 调查 道路
地图 移动 剧团兔子 室内 调查 窗户
地图 移动 卡拉考拉工房 调查 桌子
地图 移动 城山公园 北总门桥 调查 桥
完成

支线 2.梦幻鸡尾酒

地图 移动 中村BAR 店内
地图 移动 丸子屋萌音 店内 草莓大福
地图 移动 Marukoshi 店内 柠檬汽水
地图 移动 神在庵 店内 薄荷叶
地图 移动 松江庄 橘子
地图 移动 松江历史馆 喫茶处来春 蓝莓

支线 3.奇怪的旅人

地图 移动 空地
地图 移动 美术馆
地图 移动 松江大庭高中
地图 移动 松江市图书馆
地图 移动 松江站
地图 移动 中村BAR
地图 移动 剧团兔子
地图 移动 TSK中央电视台 柜台
地图 移动 城山公园 天守阁

难度：简单 标题：移动零

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

把数组的零移动到末尾，不改变原有非零数字顺序。

思路

双指针，flag指向下一个非零数字存放的位置。i遍历整个数组，当遇到非零数字则复制到num[flag]的位置且flag++。遇到0则跳过。最后把num[flag]以后的所有数字都赋值为0;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Solution {
    public void moveZeroes(int[] nums) {
        int flag = 0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i] != 0){
                nums[flag] = nums[i];
                flag++;
            }
        }
        for (int i = flag;i<nums.length;i++){
            nums[i] = 0;
        }
        return;
    }
}

链接

https://leetcode.com/problems/move-zeroes/

难度: 简单 标题：二叉树最大深度

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

思路

root == null时深度为0;最大深度为左/右的最大深度+1;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int DL = maxDepth(root.left);
        int DR = maxDepth(root.right);
        return (DL>DR?DL:DR)+1;
        
    }
}

链接

https://leetcode.com/problems/maximum-depth-of-binary-tree/

难度： 中等 标题：两数求和

leetcode Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

求两数只和，不能用加法和减法。

思路

a ^ b 表示求和且不进位。a & b 表示按位求与,(a & b) * 2 即为进位。

所以 a + b = ((a & b)<<1) + a ^ b;直到进位为0时。结果就是我们所需要的结果。

代码

1
2
3
4
5
6
7
8
9
10

public class Solution {
    public int getSum(int a, int b) {
        while(b!=0){
            int c = a & b;
            a = a ^ b;
            b = c << 1;
        }
        return a;
    }
}

链接

https://leetcode.com/problems/sum-of-two-integers/

难度： 中等 标题：用栈实现队列

正如标题所述，你需要使用两个栈来实现队列的一些操作。

队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。

pop和top方法都应该返回第一个元素的值。

思路

两个栈,stack1与stack2.stack2中元素顺序和入栈顺序完全相反。每次插入时把stack2里所有数据插入到stack1,然后插入元素到stack1末尾，再倒回stack2.

代码

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

public class Queue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public Queue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void push(int element) {
        if (stack2.empty()){
            stack2.push(element);
        } else {
            while (!stack2.empty()){
                stack1.push(stack2.pop());
            }
            stack1.push(element);
            while (!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
    }

    public int pop() {
        return stack2.pop();
    }

    public int top() {
        return stack2.peek();
    }
}

链接

http://www.lintcode.com/zh-cn/problem/implement-queue-by-two-stacks/

难度： 简单 标题:链表倒数第n个节点

找到单链表倒数第n个节点，保证链表中节点的最少数量为n。

思路

可以选择两个指针，指向第一个(first)和第N个(end)。然后每次first前进一格，则end也前进一格，知道end == null时，first指向的就是倒数第n个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Solution {
    ListNode nthToLast(ListNode head, int n) {
       ListNode first = head;
       ListNode end = head;
       for (int i=0;i<n;i++){
           end = end.next;
       }
       while(end != null){
           end =  end.next;
           first = first.next;
       }
       return first;
    }
}

链接

http://www.lintcode.com/zh-cn/problem/nth-to-last-node-in-list/