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
感覺我自己的代碼很不錯(cuò)
/**
* 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。如果最后結(jié)果(必定是奇數(shù))仆葡，是1true，否則false登刺。
坑：位運(yùn)算符判斷奇偶 但是== 和 !=的優(yōu)先級大于&
坑： if(n==0) return false;
class Solution {
public boolean isPowerOfTwo(int n) {
if(n==0) return false;//!!
while((n&1)==0){ //位運(yùn)算符判斷奇偶 但是== 和 !=的優(yōu)先級大于&
n>>=1;
}
if(n==1) return true;
return false;
}
}
時(shí)間復(fù)雜度o(logn)
思路2:時(shí)間復(fù)雜讀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是不對的皇耗，因?yàn)閚可能是負(fù)數(shù)
可是為什么上面的做法可以不用管n負(fù)數(shù)不負(fù)數(shù)呢揍很？因?yàn)樨?fù)數(shù)不斷除以二還是負(fù)數(shù)，不可能得到1.
class Solution {
public boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
}
只看了這個(gè)題解其他沒看
235
思路1:遞歸
很典型的遞歸呜袁，不用管內(nèi)部具體是怎么樣的
因?yàn)檫@題是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;
}
}
沒看別人的 但是應(yīng)該看看 人家一個(gè)while就搞定了呢
236
不會 寫了很久
思路1是：
分別保存尋找到兩個(gè)節(jié)點(diǎn)的路徑阶界，最近的公共祖先就是路徑的分岔點(diǎn)聋庵！
在尋找保存節(jié)點(diǎn)的過程中，不是普通的前中后序遍歷直接加入氧映，因?yàn)檫@樣你得到的是遍歷序列脱货！不是找節(jié)點(diǎn)的路徑序列！所以如果在左邊找到了才保存呢臼疫！這是代碼邏輯扣孟！
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;
}
}
沒看別人的
