leetcode 771. 宝石与石头

771. 宝石与石头

题目

https://leetcode-cn.com/problems/jewels-and-stones/description/

https://leetcode.com/problems/jewels-and-stones/description/

题目理解

第一个版本

根据题目要求 就遍历字符串j的每个字符，然后统计 s中出现次数
Time complexity: O(n^2)
Space complexity: O(1)
很难优化了只能空间换时间

第二个版本

用hashmap/set/map结构存储s中每个字符 然后遍历字符串j的每个字符
Time complexity: O(nlogn)
Space complexity: O(n)
map和set结构红黑树 一次查找lg（n）
hashmap 有hash计算消耗一定时间

第三版本

用数组存储字符串的个数
遍历判断是否存在
Time complexity: O(n)
Space complexity: O(n)

image.png

类似题目：

1. https://leetcode-cn.com/problems/contiguous-array/description/

110. 平衡二叉树

题目描述

image.png

题目分析：

第一版本

根据定义从上而下来判断 要判断每个节点和每个节点子树 高度
从root到叶子节点 重复计算

Time complexity: O(n2)

第二版本递归遍历

判断平衡二叉树标准

• 左右子树是平衡二叉树
• 左右子树深度不能超过

java

go

balanced-binary-tree

balanced-binary-tree

balanced-binary-tree：通过tree的深度来判断