牛客21天刷题_day#1

牛客 

Contents

1.对称的二叉树

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

解答

# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def isSymmetrical(self, pRoot):        return self.isSymmetrical1(pRoot,pRoot)            def isSymmetrical1(self,pRoot1,pRoot2):#一个递归调用的函数（自己调用自己，遍历树）        if pRoot1==None and pRoot2==None:#如果这棵树就是none,算作对称。遍历到最后就一定是到none了            return True        if pRoot1==None or pRoot2==None:#只有一个是None另一个不是，那么一定不对称            return False        if pRoot1.val !=pRoot2.val:#包含这一句的三个if,都是处理特殊情况            return False        return self.isSymmetrical1(pRoot1.left,pRoot2.right) and self.isSymmetrical1(pRoot1.right,pRoot2.left)#1左等于2右且1右等于2左,那么就是对称的，这一句需要，虽然刚开始调用的时候root1==root2，但是发生递归之后就不一样了

要注意的几点：

• 注意类内不同的函数间的调用，要加上self
• 递归函数的意义，过程：
  • 首先是看几个特殊情况，满足就直接判断
  • 判断不了，那么就自己调用自己：
    • root.left,root.right是子树，也是一棵树，相当于判断这两棵子树是不是对称
    • root.left.left,root.left.right和root.right.left,root.right.right
    • 以此类推，直到遇到不对称的，或者到最后

2.下厨房

• 输入描述:

  每个输入包含 1 个测试用例。每个测试用例的第 i 行，表示完成第 i 件料理需要哪些材料，各个材料用空格隔开，输入只包含大写英文字母和空格，输入文件不超过 50 行，每一行不超过 50 个字符。

• 输出描述:

  输出一行一个数字表示完成所有料理需要多少种不同的材料

思路：

其实就是给我一堆str,然后我要统计这些str里边不重复的有多少个，相当于取并集,可以用set；

那么另一个问题就来了：如何去把一行行的字符串取出来，得到一个list?

• 参考了一下别人提交的代码

# -*- coding: utf-8 -*#这个很奇怪，没有class solution....也没有输入变量之类的东西import sysfoodset=set()for line in sys.stdin:    if line.strip()=='':        break    for food in line.split():        foodset.add(food)print len(foodset)

• 比较疑惑的几点
  • sys.tdin到底是什么？是一个字符串类型的变量吗？
    • 测试了一下发现，不是一个字符串变量，是一个file object，这样就可以解释了，先要从文件当中一行一行地读入字符串，然后将每一行一个词一个词这样区分开，分别加入set里边，再取set长度就可以得到结果
  • 如果是字符串的话，那么按照他的做法，是直接去通过for得到每一行，但是下边我试了一下，并不可以...
  • strip(),split()

import sysstd_in='''Bob AliceHenry Bob'''std_in.split('\n')

['Bob Alice', 'Henry Bob']

---

for line in std_in:    print(line)#这里就不对了....

Bob AliceHenry Bob

---

std_in.split()#不给参数的话，就是分词

['Bob', 'Alice', 'Henry', 'Bob']

---

std_in.strip()

'Bob Alice\nHenry Bob'

---

• strip()的作用是：
  • 去除字符串前后出现的某个符号
  • 如果没有给参数，就默认去除字符串前后的空格，换行符等