牛客网刷题笔记 1

刷题

  1. 实验室锁门了，因为清明节，剑指Offer在教室，大话数据结构在教室，所有书都在教室。。。。除了电脑，所以刷刷题吧；记一下笔记；

1 多态是对于什么的？ (未完成)

下面函数到底输出什么呢？

more >>

剑指Offer 40 数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路

  1. 这不是一道正常题，因为他的考点就是异或运算；我刚开始还在想先排个序，然后每次移动两位；这样就可以比较出来了；然而时间复杂度O（n）可以接受，空间复杂度O（1）是什么鬼？ 除了异或运算应该不可能做到的吧；
  2. 讲讲异或运算，相同的数字亦或运算后就是零；1^0=0^1 = 1;0^0=1^1=0;
    所以我们就获得了重要情报，一群出现两次的数和一个只出现一次的数进行异或运算就是这个只出现一次的；
    那么两个怎么办呢？首先对全部进行异或运算，得到的肯定不是0，因为有两个不一样嘛，这个数中二进制1的位置，表现了两个只出现一次的数的不同，然后我们就可以据此分类；

    more >>

剑指Offer 39 二叉树的深度+平衡二叉树

#二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路

  1. 递归的方法，简单说，就是左右节点分别遍历自己的左右子节点；
  2. 层次遍历，很麻烦的一种算法；你可以想想那么一个队列，扫到节点，就加进来，然后依次找他们的子节点，在加进来，最后肯定能够成功把全部节点都遍历到

    more >>

继续跑<br><br>带着赤子的骄傲