面试题11：旋转数组的最小数字

2020-01-09 算法

题目：https://www.nowcoder.com/ta/coding-interviews

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思考：

利用旋转数组的特性来设计查找最小值的方法。

原数组是非递减排序的，旋转数组可划分为两个非递减子数组，并且前面子数组的元素都>=后面子数组的元素，最小元素恰好是两个数组的分界线；

暴力的o(n)查找

class Solution1:
    def minNumberInRotateArray(self, rotateArray):
        min = rotateArray[0]
        if len(rotateArray)==0:
            return 0 
        else:
            for i in range(1,len(rotateArray)):
                if rotateArray[i] < min:
                    min = rotateArray[i]
            return min

rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution1()
method.minNumberInRotateArray(rotateArray)

# for i in range(0,5):#不会包含最后一个索引，左闭右开
#     print(i)
# for i in range(0,len(rotateArray)):
#     print(rotateArray[i])

根据旋转数组的特性设计二分查找:

1.设置中间点，标记旋转数组首元素和尾元素，中间点将数组分成两半;

2.如果中间点大于等于首元素，说明最小数字在数组后一半，如果中间点小于等于尾元素，说明最小数字在数组前一半;

3.依次改变首、尾元素的位置，当尾元素和首元素挨着的时候，这时候尾元素就是所找的最小值。

class Solution2:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray)-1
        if len(rotateArray)==0:
            return 0
        else:
            while(right - left) > 1:
                mid = (left + right)//2#商向下取整的结果
                if rotateArray[mid] >= rotateArray[left]:#中间值在第一组比左大，最小值在mid右
                    left = mid#更新左 
                elif rotateArray[mid] <= rotateArray[right]:#中间值在第二组比右小，最小值在mid左
                    right = mid#更新右
            return rotateArray[right]#右元素为最小
            #当不满足while条件时，说明数组有两个元素（或者一个元素），直接返回旋转数组右边元素即可

1
2
3

rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution2()
method.minNumberInRotateArray(rotateArray)

特殊的是，当首元素等于尾元素等于中间值时，以上比较规则失效，只能对数组进行顺序查找，增加如下判断：

class Solution3:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray)-1
        if len(rotateArray)==0:
            return 0
        else:
            while(right - left) > 1:
                mid = (left + right)//2#商向下取整的结果
                if rotateArray[mid] == rotateArray[left] and rotateArray[mid] == rotateArray[right]:
                    #特殊情况，当首元素等于尾元素等于中间值时，只能对数组进行顺序查找
                    min = rotateArray[left]
                    for i in range(left,right):
                        if rotateArray[i] < min:
                            min = rotateArray[i]
                    return min 
                elif rotateArray[mid] >= rotateArray[left]:#中间值在第一组比左大，最小值在mid右
                    left = mid#更新左 
                elif rotateArray[mid] <= rotateArray[right]:#中间值在第二组比右小，最小值在mid左
                    right = mid#更新右
            return rotateArray[right]#右元素为最小
            #当不满足while条件时，说明数组有两个元素（或者一个元素），直接返回旋转数组右边元素即可

# rotateArray = [4, 5, 6, 1, 2, 3]
rotateArray = [ 0, 1, 1]
method = Solution3()
method.minNumberInRotateArray(rotateArray)

剑指offer书中还考虑到旋转数组旋转了0个元素的情况，也就是排序数组本身:第一个元素（左）就是最小的元素

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        left = 0
        right = len(rotateArray)-1
        if len(rotateArray)==0:
            return 0
        elif rotateArray[left] < rotateArray[right]:
            return rotateArray[left]
        else:
            while(right - left) > 1:
                mid = (left + right)//2#商向下取整的结果
                if rotateArray[mid] == rotateArray[left] and rotateArray[mid] == rotateArray[right]:
                    #特殊情况，当首元素等于尾元素等于中间值时，只能对数组进行顺序查找
                    min = rotateArray[left]
                    for i in range(left,right):
                        if rotateArray[i] < min:
                            min = rotateArray[i]
                    return min 
                elif rotateArray[mid] >= rotateArray[left]:#中间值在第一组比左大，最小值在mid右
                    left = mid#更新左 
                elif rotateArray[mid] <= rotateArray[right]:#中间值在第二组比右小，最小值在mid左
                    right = mid#更新右
            return rotateArray[right]#右元素为最小
            #当不满足while条件时，说明数组有两个元素（或者一个元素），直接返回旋转数组右边元素即可

rotateArray = [  0, 1,  1, 1]
# rotateArray = [ 1, 0, 1,  1, 1,]
# rotateArray = [ 1, 1, 1, 0, 1]
# rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution()
method.minNumberInRotateArray(rotateArray)

这里补充另一位博主的写法Solution4

# -*- coding:utf-8 -*-
class Solution4:
    def minNumberInRotateArray(self, rotateArray):
        p1, p2 = 0, len(rotateArray) - 1#一样的操作固定首尾
        mid = p1#特殊情况下的最小值索引，即对应之前的旋转为0的旋转数组。结合下列循环条件来看，我觉得这里很精彩
        while rotateArray[p1] >= rotateArray[p2]:#和之前用索引大小来确定循环不同，这里直接用首元素>=尾元素这个特性来确定循环
            if p2 - p1 == 1:#首尾相邻，尾小，即为最小值
                mid = p2#最后统一返回mid索引下的元素
                break
#             mid = (p1 + p2) / 2#原博主写法
            mid = (p1 + p2) // 2#这里我觉得应该是取整才对
            if rotateArray[mid] == rotateArray[p1] and rotateArray[mid] == rotateArray[p2]:
                return self.minInOrder(rotateArray, p1, p2)#特殊情况，判断失效，只能遍历
            if rotateArray[mid] >= rotateArray[p1]:
                p1 = mid
            elif rotateArray[mid] <= rotateArray[p2]:
                p2 = mid
        return rotateArray[mid]#最终p2会停留在mid上,写作rotateArray[p2]也没有区别，这里整段代码都统一返回mid索引值

    def minInOrder(self, nums, index1, index2):#确定首尾，遍历一段数组，得到最小值
#         n1 = nums[index]#原博主写法
        n1 = nums[index1]#应改为
        for i in range(index1 + 1, index2):
            if n1 > nums[i]:
                return nums[i]
        return n1

# rotateArray = [ 0, 1, 1, 1]
# rotateArray = [ 1, 0, 1,  1, 1]
# rotateArray = [ 1, 1, 1, 0, 1]
rotateArray = [4, 5, 6, 1, 2, 3]
method = Solution4()
method.minNumberInRotateArray(rotateArray)

参考：

https://blog.csdn.net/Datawhale/article/details/82143776

https://blog.csdn.net/fuxuemingzhu/article/details/79501202

搭建Hexo博客并部署到Github

2020-01-09 教程

这是zongpu搭建个人博客的过程记录

工具

windows, Git, Node

安装Hexo

利用 npm 命令即可安装。在任意位置点击鼠标右键，选择Git Bash Here。

输入命令：npm install -g hexo

注意：-g是指全局安装hexo。

创建Hexo文件夹

安装完成后，在你喜爱的文件夹下（如C:\Hexo），执行以下指令(在C:\Hexo内点击鼠标右键，选择Git Bash)，Hexo 即会自动在目标文件夹建立网站所需要的所有文件。

hexo init

安装依赖包

npm install

本地查看Hexo博客

现在我们已经搭建起本地的hexo博客了，执行以下命令(在C:\Hexo)，然后到浏览器输入localhost:4000看看。

hexo generate

hexo server

注：因为4000端口占用的原因，我在这里并不能打开本地博客

切换端口以解决

在Hexo文件夹下的_config.yml文件内增加端口服务设置（以切换到5000为例）

1532749382655

#Server

server:

port: 4000

compress: true

header: true

运行如图：

1532749483662

Github创建仓库

创建的时候注意Repository的名字。比如我的Github账号是zongpu，那么我应该创建的Repository的名字是：zongpu.github.io这是特别的约定。

到你刚刚创建的Repository下，找到以下内容：
在仓库里找到HTTPS，复制里面的地址。

1532753657790

然后编辑_config.yml文件（在C:\Hexo下），修改增加内容如下(修改时，冒号后面需要空格)：

deploy:
type: git
repository: https://github.com/zongpu/zongpu.github.io.git
branch: master

并保存。

设置SSHKEYs

在Git Bash输入以下指令（任意位置点击鼠标右键），检查是否已经存在了SSH keys。

ls -al ~/.ssh

如果不存在就没有关系，如果存在的话，直接删除.ssh文件夹里面所有文件：

1532753868572

输入以下指令（邮箱就是你注册Github时候的邮箱）后，回车：

ssh-keygen -t rsa -C “xxx@example.com“

经过几次回车会看到方框状的 key’s randomart image

1532754456771

其中，会提示要你输入passphrase（如上图，我没有输入直接回车，如果你输入的话，要记得，到时候会用到）。之后，如果出现类似下图：

1532754478256

然后键入以下指令：

ssh-agent -s
继续输入指令：

ssh-add ~/.ssh/id_rsa

输入之后，在我这里是出错了，不知道你的有没有出错。

如果你的也是这样子出错了的话，就输入以下指令：（由于编辑格式的原因，这里是：’ssh-agent -s‘，有单引号）

eval ssh-agent -s

ssh-add

6. 到了这一步，就可以添加SSH key到你的Github账户了。键入以下指令，拷贝Key（先拷贝了，等一下可以直接粘贴）：

clip < ~/.ssh/id_rsa.pub

注：这里也可以在.ssh文件夹里找到id_rsa.pub文件并复制里面的内容。
1. 然后到Github里面，找到设置：

1532755270340

添加新的SSH keys

1532755318894

这里title可作为一个key的说明，key值，刚才已经用命令行复制，可直接粘贴，保存，添加。

最后还是测试一下吧，键入以下命令：

ssh -T git@github.com
你可能会看到有警告，没事，输入“yes”就好。

完成部署
1. 最后一步，快要成功了，键入指令：
  
  hexo generate
  
  hexo deploy
2. OK，我们的博客就已经完全搭建起来了，在浏览器输入（当然，是你的用户名）：
  
  http://xxx.github.io/
  
  当然：理想是饱满的，在这里又出现了错误
  
  a. 经搜索错误Error: fatal: HttpRequestException encountered. 了解到，是Github 禁用了TLS v1.0 and v1.1，必须更新Windows的git凭证管理器：GCMW（下载链接：https://github.com/Microsoft/Git-Credential-Manager-for-Windows/releases/tag/v1.14.0）
  
  出处：https://blog.csdn.net/txy864/article/details/79557729
  
  b. 或者键入：
  
  git config –global credential.helper manager
  
  重新发布，也能正常push：https://blog.csdn.net/u010229836/article/details/78229339
3. 注意：每次修改本地文件后，需要键入hexo generate才能保存。每次使用命令时，都要在C:\Hexo目录下。每次想要上传文件到Github时，就应该先键入hexo generate保存之后，再键入hexo deploy。大概成功之后是酱紫的：
  
  对了，记住上图的Username是你的Github账号名称，而不是邮箱；Password就是你的Github的密码。
  
  博客主题修改
  官方主题地址为hexo-themes
  
  命令格式：git clone https://github.com/litten/hexo-theme-yilia.git themes/yilia
  
  一个问题：Hexo的版本控制与持续集成
  参见博客：https://formulahendry.github.io/2016/12/04/hexo-ci/
  
  最后，以上内容部分截图、陈述来自互联网，实在是做的时候自己没留意截图，在此致谢！
  
  主要参考了如下博客，自己也留作参考：

Hello World

2020-01-09

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

2019，开始躺平

2020-01-09 随笔

“这是酝酿了很久的表达，倒不是为了圆一个少不经事的梦，他既没丰富阅历也无多少奇思妙想，只是想试着记录一颗沙砾在生活的泥泞中如何挣扎。所以，这不是什么正经写作，所有的文字都只是一时兴起而已。”

公历2019已经到了尾声，你度过了快乐的一年么？但其实不快乐也没什么关系。对于绝大多数人而言，过去的每一年都只是一个工具人生命中最普通的一年。在时间尺度上，你既抓不住太阳光射向地球的某一瞬，也感受不到千百年为周期的星轨变化，你看到的都只是历史，是事物消逝前的余光；在空间尺度上，你倒是能体会到一些，比如怎么也穿不进的裤子，端倪初现的颈椎，没有归属感的城市，你感受到的是活生生的当下，是把握不住的遗憾。理智告诉你再丧下去将万劫不复，于是开始寻求正能量，可什么又是正能量呢？鸡汤一碗一碗干？健身旅行学英语，电影阅读走走看？我选择躺平，追求简单的快乐也接受不快乐，傻傻地活着。所以，把我喜欢的分享给小伙伴儿们呀，除了获得一点儿快乐，分享还可以满足虚荣心不是么？

—

喜欢的书

《别闹了，费曼先生》/《你干嘛在乎别人怎么想》

——理查德·费曼

“这是我早些年应该看的书，不过谁知道现在看算不算晚呢”

“我无法寄出这封信，因为我已不再知道你的地址”

《果壳中的宇宙》

——史蒂芬·霍金

“思想形成人的伟大。人只不过是一根苇草，是自然界最脆弱的东西，但他是一根能思想的苇草。用不着整个宇宙都拿起武器来才能毁灭他，一口气、一滴水就足以致他死命了。然而，纵使宇宙毁灭了他，人却仍然要比致他于死命的东西高贵得多，因为他知道自己要死亡，以及宇宙对他所具有的优势，而宇宙对此却是一无所知。因而，我们全部的尊严就在于思想。正是由于它而不是由于我们所无法填充的空间和时间，我们才必须提高自己。因此，我们要努力好好地思想。这就是道德的原则。——《人是一根能思想的芦苇（Man is a reed that thinks）》帕斯卡”

之所以看这本书是因为看到新闻说霍金合作者在预印本网站发出了霍金生前最后的工作，相比只能用来装点书架的硬核科普《时间简史》，这本书只是科学家的几篇讲稿一点哲思。“庐山的如琴湖畔提供了当今已经非常稀罕的清静，使我在一个多月内得以专心译述。窗外云雾晴岚、朝晖夕霞瞬息变幻。奇峰异壑、飞瀑流泉间遍布着王羲之、慧远、陶潜、李白、白居易、苏轼和王阳明的遗迹，这一切予人以无限的想象空间。在这种氛围中思索宇宙是再惬意不过的了。——吴忠超”

另外，大刘的《朝闻道》也十分推荐，在时间的尺度上，与思想萌芽所需相比，实现它只不过是一瞬。通过科学这项人类最伟大的事业，即使被禁锢在果壳之内，人仍然可以享有精神的自由。不过，有一天当你收到那个信息的时候请不要回答！不要回答！不要回答！

《这里是中国》

——星球研究所 / 中国青藏高原研究会

“中国从哪里来？将往何处去？”

阅读这本书是因为我非常喜欢星球研究所公众号，你未必能触及中国的每一寸土地，但有另一种阅尽中国的希望。另外，直接打动我的大概是文章中的每一幅配图吧。

贡嘎山倒影

方脸藏狐

连通伊犁河谷与北疆的果子沟大桥

《曙光集》/《晨曦集》/《近代科学进入中国的回顾与前瞻》

——杨振宁

”The party is over”

评价一个科学家首先应该了解的是他的科学成就，以及真正的贡献，而不是八卦。

一直以来我都愿意看科幻、科普作品，除了“科技让生活更美好”的口头禅外，这一年实实在在地受到了工业党思维的冲击，算是多了一些情怀。其实除了上面那些闲书，翻得最多的应该是《矩阵分析》和乱七八糟的论文，“人工智能四大名著”也是心头好，只是他们都颇有难度，废柴如我是没能完全读下去的，只能被疯狂劝退，让我时不时点开无脑小说金庸全集。当然我也不能一字一句读完金庸，毕竟好看的也没有几章，以现在的价值观来看全员渣，可能是作者亲身有过愧疚德损，只好动不动就平安喜乐。

—

喜欢的影视剧

《绝杀慕尼黑》

气氛非常苏，剧情类似《摔跤吧，爸爸》，俄罗斯爱国电影，看的时候也若有若无的感到这是俄罗斯在缅怀那个强大的年代吧，即使她有不好的一面。另外，背景虽然严肃，但是有很多舒缓的情节，时不时穿插苏式幽默，不看重背景就是单纯的运动片，边喝快乐水边欣赏比赛也无违和感。因为时代的局限，我们对那个两雄并立年代的认识是断层的，他们不只是爱喝伏特加，他们也有出众的文学艺术，如同我们自己失去的那些年。

《寄生虫》

借助完备的电影工业体系，韩国人之前拍了太多这种类型的电影，还好我在看的时候没有产生疲劳，这有赖于导演营造的阴森气氛使人清醒清醒。总体给人的感觉不是感官刺激上的害怕，是讽刺癫狂更是难以摆脱的宿命轮回般的绝望。导演奉俊昊作品风格也是多变的，我看过他之前的作品有灾难丧尸类的《汉江怪物》、《雪国列车》，也有剧情悬疑向的《杀人回忆》，但总体都偏阴暗。

《我的大叔》

2018年豆瓣年末盘点的时候《我的大叔》在韩剧榜首，看了简介觉得喜欢而且还短，就在春节的时候看了，但其实片子的气质跟春节一点儿都不匹配。每个人都愁眉苦脸，估计跟那时候的我差不多，于是就看了。忽略掉一些技术上的不合理，垃圾的人生才需要这种东西安慰自己吧，另外配乐也很棒。

어른

Sondia - 나의 아저씨 OST

结尾风格是这样的，还算不错。

另外在某天逛知乎的时候，看到了大约是“哪个影视片段令你印象深刻？”的话题，下面有个抖机灵的回答成功引起了我的注意，于是就找找到了

《电影少女》

没错，片子类型大约是“死宅的幻想”，无聊透顶还恰好有眼缘的可以看看，不长。有趣的是上面开头的两部片子都在今年的豆瓣年度电影榜单之列，算是小小的惊喜。

—

喜欢的音乐

Alison Krauss

When You Say Nothing At All

Alison Krauss - Now That I’ve Found You: A Collection

大佬的歌几乎都好听的列表循环就对了

通常来说，这不是我喜欢的听歌类型，但还是听了不少，

大概是因为听了能让人轻快起来。

日常循环的就是李宗盛、周杰伦和李健了，流行音乐居多，也喜欢乡村和民谣，我不是很能分清楚他们的区别，不过我能明显的感受到歌词的好坏，不喜欢故作“民谣”式的嗓子，喜欢自然的表达。今年其实还听了不少摇滚，可能是无形中受到了电影《波西米亚狂想曲》的影响，也可能脑海中常常回想起的《带我去月球》。还特别喜欢电影《白日梦想家》的插曲

Stay Alive

José González - Stay Alive

Space Oddity

David Bowie;Kristen Wiig - The Secret Life Of Walter Mitty

Don’t You Want Me

Bahamas;The Weather Station - The Secret Life Of Walter Mitty

暑假回校那段时间常听的还有土嗨伍佰

夏夜晚风

伍佰 & China Blue - 爱你伍佰年

—

偶然遇到的诗

跑着的云

告诉蓝天

你要晚一点走

孩子们还没有回家

——《等等》

“平凡枯燥的生活孕育的诗意是渴望。这是诞生在中国最贫困地区的小孩笔下的诗，类似的还有《刮胡刀》、《时间里的刀》、《距离》等等，他们用仅学的最简单的词汇描绘生活。伟大的作品大多来自苦难，自己或是别人的苦难，诗歌也好，电影也罢，普通人的真相大约是工具人实锤了。回想我小时候写的东西早已经都丢掉，印象中模糊地记得义非将操场一角实心球比喻成扒满灰尘的乌龟，不知道为什么记了这么久，大约是我仍旧贫瘠。期待我们的国家彻底摆脱落后贫瘠，苟日新日日新又日新，科技工业的发展铺就成长的路，教育进步成为每个人心中的‘白昼流星’。”

“2020会被消灭的硬骨头”

—

喜欢的照片

昆明的阳光占据了全年的大部，附带赠送强烈紫外线，好处是可以无脑拍出好看的天。

“秋已尽，冬渐藏，望春玉兰芽三两。

千里遥，万般念，啼血杜鹃春风惘？

来年近，近咫尺，关心尤甚，盼红妆。

磐石蒲苇不改，杏黄枫红未逝，心亦常在。”

早晨出门的路上

—

微小的工作

Joint Framework for Image Fusion and Super-Resolution via Multicomponent Analysis and Residual Compensation

今年十一月末算是读研以来的一个分界线，一直以来担心的事情有了暂时的结尾，虽然兜兜转转还是在研究生灌水乐园添了一瓢，安慰自己聊胜于无。两年多的时间里，我大致知道普通人的科研是怎么一回事，大牛们的事迹了解了一些，我固然有兴趣做一点儿什么，但一个人成长，固然需要自身的努力更要看到历史的进程。读硕士的经历足以让我明白，不是我不读研读博，而是我没有那个能力与基础，至此，我更加佩服有勇气继续念下去的同学伙伴，带着一点儿羡慕。当然这不是说我不再自我更新，只是，我很可能与某种形式的学习说再见了，哪怕我曾经对它有过期许。二十多岁，心有戚戚焉，想做的事还多想学的还多，但愿我能继续折腾，达到某个健康的生活状态。

END

—

结语

如同万千工具人一样，自我奋斗能向上攀爬的距离从刚出生开始就已经决定，我能做的只有躺平。前面星星点点的内容皆是小米便签带来的，有的写在火车上，有的写在颓废的深夜，没有多少连贯性，我自己的心境也是，常常很丧偶尔正能量。我曾经用心安利其中一些给别人，但是你珍惜的在别人眼中可能只是垃圾，我也想自己有完美光辉的一面，显然我没法取悦所有人，日常傻一点儿，在朋友圈是积极阳光的，去微博吐槽，去知乎豆瓣装逼，去参与“朝天门抽烟走不走？”，去接受陌生人社交，去丧且正能量地活着。2020，会接着躺平么？

参考

1. 图片来自豆瓣海报、书籍插图、互联网以及个人拍摄

2. 豆瓣2019年度电影榜单https://movie.douban.com/annual/2019?source=navigation

3. 豆瓣2018年度电影榜单https://movie.douban.com/annual/2018?source=broadcast

面试题32：分行从上到下打印二叉树

2019-09-01 算法

题目：https://www.nowcoder.com/ta/coding-interviews?query=&asc=true&order=&page=3

从上到下按层打印二叉树，与之前不同的是：同一层节点从左至右顺序打印（输出），每一层打印（输出）一行。

理解：

这里，根据要求返回二维列表，容易知道，为了把二叉树的每一行单独打印到一行，用列表存储每一层的节点值：[ [ ], [ ], [ ], …, [ ] ],第几层对应第几个子序列。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution1:
# 返回二维列表[[1,2],[4,5]]
    def Print(self,pRoot):
        result = []
        self.level(pRoot, 0, result)
        return result
    
    def level(self, root, level, result):
        if not root:
            return None
        if level == len(result):
            result.append([])#为每一层建立子序列,
            #实际上这里需要追加子序列的情况：1.根节点时level=0=len(result)，建立子序列；
            #2.假如左节点成立的话，左节点时level+1=len(result)，需要建立子序列。而此后在判断同层右节点时，level已经变化多次，不再需要建立子序列。
            #3.假如左节点不成立的话，在判断右节点时level+1=len(result)，需要建立子序列。
        result[level].append(root.val)#将节点值放入对应的子序列
        
        if root.left:
            self.level(root.left, level+1, result)#左节点
        if root.right:
            self.level(root.right, level+1, result)


root = TreeNode(8)
a = TreeNode(6)
b = TreeNode(10)
c = TreeNode(5)
d = TreeNode(7)
e = TreeNode(9)
f = TreeNode(11)
g = TreeNode(12)
h = TreeNode(13)
 
root.left = a
root.right = b
a.left = c
a.right = d
b.left = e
b.right = f
d.left = g
d.right = h

1
2
3

method = Solution1()
answer = method.Print(root)
answer

[[8], [6, 10], [5, 7, 9, 11], [12, 13]]

参考：

1.https://blog.csdn.net/fuxuemingzhu/article/details/79725053

2.https://blog.csdn.net/qq_18254385/article/details/94736589

面试题28：对称的二叉树

2019-09-01 算法

题目：https://www.nowcoder.com/ta/coding-interviews

请实现一个函数，用来判断一颗二叉树是不是对称的。如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

简单的考虑是：

1.比较树的根节点是否存在

2.根节点存在，则比较root.left？==root.right

3.若2成立，则针对两颗子树，判断 root1.left？==root2.right & root1.right？==root2.left，并不断重复这个过程

利用递归设计2-3（返回True或者False），在判断方法中调用

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetrical(self, pRoot):
        if not pRoot:
            return True
        return self.isSymmetricalTree(pRoot.left, pRoot.right)
    def isSymmetricalTree(self,root1,root2):
        if not root1 and not root2:
            return True
        if not root1 or not root2:
            return False
        if root1.val == root2.val:
            return self.isSymmetricalTree(root1.left,root2.right) and self.isSymmetricalTree(root1.right,root2.left)
        else:
            return False

参考：https://blog.csdn.net/u014568072/article/details/87913092

面试题32：之字形打印二叉树

2019-09-01 算法

题目：https://www.nowcoder.com/ta/coding-interviews?page=3

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

考虑：跟之前按行打印二叉树的思路，先将二叉树按行分别存入二维列表，然后将特定的子列表翻转

列表翻转：

1.https://www.runoob.com/python3/python-reversing-list.html

2.https://www.runoob.com/python3/python-slicing-rotate-string.html

#列表翻转
a=[1,2,3,4,5,6,7,8,9] 
print(a) 
d=a[::-1]#对列表切片翻转
print(a) 
c=a
print(d) 
c.reverse() #会改变原有列表
print(c) 
print(a) #??为什么a会被改变

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1]

def Reverse(lst): 
    lst.reverse() 
    return lst 
      
a=[1,2,3,4,5,6,7,8,9] 
print(Reverse(a))

[9, 8, 7, 6, 5, 4, 3, 2, 1]

for循环步长：https://www.runoob.com/python3/python3-loop.html

#将索引为奇数（第偶数：2、4）个子列表翻转
res = [[8], [6, 10], [5, 7, 9, 11], [12, 13]]
for level in range(1, len(res), 2):
    res[level] = res[level][::-1]
print(res)

[[8], [10, 6], [5, 7, 9, 11], [13, 12]]

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

root = TreeNode(8)
a = TreeNode(6)
b = TreeNode(10)
c = TreeNode(5)
d = TreeNode(7)
e = TreeNode(9)
f = TreeNode(11)
g = TreeNode(12)
h = TreeNode(13)
 
root.left = a
root.right = b
a.left = c
a.right = d
b.left = e
b.right = f
d.left = g
d.right = h

class Solution:
    def Print(self, pRoot):
        if not pRoot:
            return []
        result = []
        level = 0
        self.level(pRoot, level, result)#和之前一样，得到按行对应的二维列表
        
        for level in range(1, len(result), 2):#将索引为奇数（第偶数：2、4）个子列表翻转
            result[level] = result[level][::-1]
        return result
    
    def level(self, root, level, result):#和之前一样，得到按行对应的二维列表
        if not root:
            return None
        if level == len(result):
            result.append([])
        result[level].append(root.val)
        if root.left:
            self.level(root.left, level+1, result)
        if root.right:
            self.level(root.right, level+1, result)

1
2
3

method = Solution()
answer = method.Print(root)
answer

[[8], [10, 6], [5, 7, 9, 11], [13, 12]]

参考：https://blog.csdn.net/fuxuemingzhu/article/details/79724959

面试题15：二进制中1的个数

2019-09-01 算法

题目：https://www.nowcoder.com/ta/coding-interviews

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

求整数的补码：

1、正整数的补码是其二进制表示，与原码相同；

例如：5（00000101）

2、负整数的补码：将其对应正数二进制表示所有位取反（包括符号位，0变1，1变0）后加1。

例如：-5对应正数5（00000101）→所有位取反（11111010）→加1(11111011)

根据补码求原码：

已知一个数的补码，则对应原码为：对该补码再求补码。

python中得到一个数n的补码：n & 0xffffffff(这个做法来自网络，具体原因未知)，
所以直接的做法如下：

class Solution1:
    def NumberOf1(self, n):
        if n < 0:
            n = n & 0xffffffff
        return bin(n).count('1')

1
2
3

method = Solution1()
answer = method.NumberOf1(-1)
answer

把一个整数减去1之后再和原来的整数做按位与，得到的结果相当于是把整数的二进制表示中最右边的一个1变成0,一个整数的二进制表示有多少个1则可以进行多少次这样的操作

根据上述特点可以得到一种求解方案，这也是《剑指offer》一书提供的精巧思路

class Solution2:
    def NumberOf1(self, n):
        count = 0
        if n < 0:
            n = n & 0xffffffff#得到负数的补码，计算机中负数以二进制补码形式存在
        while n:
            n = n & (n-1)
            count += 1#count =count + 1
        return count

1
2
3

method = Solution2()
answer = method.NumberOf1(-1)
answer

以下也是一种特别的方案，来自参考链接中的博主。

具体是：将负数-n转换为正n，然后计算(n-1)中的1的位数，再用32减之，刚好得到负数补码中1的位数

class Solution3:
    def NumberOf1(self, n):
        if n>=0:
            count = bin(n).count('1')
        else:
            n=abs(n)
            count = 32 - bin(n-1).count('1')#和之前Solution2中的做法的联系是什么？
        return count

1
2
3

method = Solution3()
answer = method.NumberOf1(-1)
answer

bin(-11)

'-0b1011'

1	bin(-11).replace('0b','')

'-1011'

移位操作：（确定位长）

class Solution4:
    def NumberOf1(self, n):
        count = 0
        for i in range(0,32):
            if n & 1:#与1做位与
                count = count + 1
            n = n >> 1#右移n，舍弃最右位，最左尾添0。右移一次，丢弃最右一个‘1’。
        return count

1
2
3

method = Solution4()
answer = method.NumberOf1(-1)
answer

另一种移位操作：（确定位长）

class Solution5:
    def NumberOf1(self, n):
        count = 0
        operator = 1
        for i in range(0, 32):#32位
            if n & operator:#带判断数n与操作数operator做位与
                count = count + 1
            operator = operator << 1#操作数operator左移，而不是n右移。左移一次，消掉最右一个‘1’。
        return count

1
2
3

method = Solution5()
answer = method.NumberOf1(-1)
answer

参考：
1、https://blog.csdn.net/Datawhale/article/details/82182612

2、https://blog.csdn.net/fuxuemingzhu/article/details/79512764

面试题27：二叉树的镜像

2019-09-01 算法

题目：https://www.nowcoder.com/ta/coding-interviews

操作给定的二叉树，将其变换为源二叉树的镜像。

思考：

反转根节点的左右子节点，这样把左右子节点带着的子树进行了调整；接下来对翻转后的左节点进行左右子节点的调整；翻转后的右节点操作同理；

当交换完所有非也节点的左右子节点后，就可以得到原树的镜像。

实际操作：

反转二叉树的左右节点，其实直接反转就好了：root.left,root.right = root.right, root.left

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def Mirror(self, root):
        if not root:
            return None
        root.left,root.right = root.right, root.left
        if root.left:
            self.Mirror(root.left)
        if root.right:
            self.Mirror(root.right)

面试题10：跳台阶

2019-09-01 算法

题目：https://www.nowcoder.com/ta/coding-interviews

这是在“面试题10：非波拉契数列”中的另一个题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

理解：

如果有1级台阶，只有1种；如果有2级台阶，有1–1、2两种；如果有3级台阶，有1–1–1、1–2、2–1三种跳法

假设n级台阶有F(n)种跳法，一定是先跳1级或者先跳2级这两类方式，再继续跳到n级台阶，跳1级后有F(n-1)种，跳2级后有F(n-2)种，故共有F(n)=F(n-1)+F(n-2)。这与斐波拉契数列一致。

但是跳台阶没有0级台阶：F(1)=1,F(2)=2,F(3)=3,F(4)=5,…,F(n)=F(n-1)+F(n-2),…

class Solution1:
    def jumpFloor(self, number):
        if number == 1:
            return 1
        elif number == 2:
            return 2
        else:
            a = 1
            b = 2
            for i in range(2,number):
                b = a + b
                a = b - a
            return b

1
2
3

method = Solution1()
answer = method.jumpFloor(5)
answer

class Solution:
    def jumpFloor(self, number):
        if number == 1:
            return 1
        elif number == 2:
            return 2
        else:
            a = 1
            b = 2
            for i in range(2,number):
                a,b = b,a+b
            return b

1
2
3

method = Solution()
answer = method.jumpFloor(5)
answer

工具

安装Hexo

创建Hexo文件夹

安装依赖包

本地查看Hexo博客

切换端口以解决

Github创建仓库

设置SSHKEYs

完成部署

博客主题修改

一个问题：Hexo的版本控制与持续集成

Quick Start

Create a new post

Run server

Generate static files

Deploy to remote sites