217
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> hashset=new HashSet<>();
for(int i=0;i<nums.length;i++){
if(hashset.add(nums[i])==false){
return true;
}
}
return false;
}
}
230
dfs
感觉我自己的代码很不错
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int ans=0,index=0;
public int kthSmallest(TreeNode root, int k) {
dfs(root,k);
return ans;
}
void dfs(TreeNode root,int k){
if(root==null||index==k) return;
dfs(root.left,k);
if(++index==k){
ans=root.val;
return;
}
dfs(root.right,k);
}
}
231
思路1:2的幂为：12222..
不断除以2。如果最后结果(必定是奇数)，是1true，否则false。
坑：位运算符判断奇偶 但是== 和 !=的优先级大于&
坑： if(n==0) return false;
class Solution {
public boolean isPowerOfTwo(int n) {
if(n==0) return false;//!!
while((n&1)==0){ //位运算符判断奇偶 但是== 和 !=的优先级大于&
n>>=1;
}
if(n==1) return true;
return false;
}
}
时间复杂度o(logn)
思路2:时间复杂读o(1)
https://leetcode-cn.com/problems/power-of-two/solution/power-of-two-er-jin-zhi-ji-jian-by-jyd/
ps n可能小于等于0，所以必须n>0才可以 n!=0是不对的，因为n可能是负数
可是为什么上面的做法可以不用管n负数不负数呢？因为负数不断除以二还是负数，不可能得到1.
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
只看了这个题解其他没看
235
思路1:递归
很典型的递归，不用管内部具体是怎么样的
因为这题是bst
递归的思想：如果他们在左边那我就去找左边的最近公共祖先
如果他们右边那我就去找右边的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(p.val<root.val && q.val<root.val){
return lowestCommonAncestor(root.left,p,q);
}
else if(p.val>root.val && q.val>root.val){
return lowestCommonAncestor(root.right,p,q);
}
else return root;
}
}
没看别人的 但是应该看看 人家一个while就搞定了呢
236
不会 写了很久
思路1是：
分别保存寻找到两个节点的路径，最近的公共祖先就是路径的分岔点！
在寻找保存节点的过程中，不是普通的前中后序遍历直接加入，因为这样你得到的是遍历序列！不是找节点的路径序列！所以如果在左边找到了才保存呢！这是代码逻辑！
20% 90%
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pathp=new ArrayList<>();
List<TreeNode> pathq=new ArrayList<>();
find(root,pathp,p);
find(root,pathq,q);
TreeNode ans=new TreeNode();
for(int i=pathp.size()-1,j=pathq.size()-1;i>=0&&j>=0;i--,j--){
if(pathp.get(i).val!=pathq.get(j).val){
break;
}
ans=pathp.get(i);
}
return ans;
}
boolean find(TreeNode root,List<TreeNode> path,TreeNode node){
if(root==null) return false;
else{
if(root.val==node.val){
path.add(root);
return true;
}
}
if(!find(root.left,path,node)){
if(find(root.right,path,node)){
path.add(root);
return true;
}
else{
return false;
}
}
else{
path.add(root);
return true;
}
}
}
思路2:
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// LCA 问题
if (root == null) {
return root;
}
if (root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
}
return null;
}
}
没看别人的
