LeetCode 热题 HOT 100 简单篇（已完结）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map <Integer,Integer>hash=new HashMap<>();
        //知识点：
        //hash的常用方法：存放数据put(key,value)  获取vaule值get(key) 
        //获取长度size()  替换某个key的value值replace(key,new value)
        //获取value值，如果不存在key，则进行设置默认value getOrDefault(key,defaultValue)

        //思路：遍历数组，将数组中的每个值和索引以键值对的形式存放放到hashmap中，当hash中存在target-nums[i]，返回对应的下标。
        //注意：先判断是否存在target-nums[i]再进行存放，不然可能会出现自己与自己匹配的情况。
        for(int i=0;i<nums.length;i++){
        if(hash.containsKey(target-nums[i])){
            return new int[]{hash.get(target-nums[i]),i};
        }else{
            hash.put(nums[i],i);
        }
        }
        //不存在时返回一个空数组
        return new int[0];
    }
}

class Solution {
    public boolean isValid(String s) {
        //基础知识：
        //栈的特性，只能在一端进行操作，先进后出
        //栈的操作 入栈stack.push() 出栈并返回弹出的元素pop()  
        //peek() 返回栈顶元素但不删除  empty()判断栈是否为空，是返回true，非空返回false
        //size() 判断栈的长度
        
        //思路：利用栈先进后出的特性进行对括号进行存储,先入栈的左括号后闭合；
        //利用HashMap中key-value的特性，对括号进行配对。

        //特殊情况，若s长度为奇数，直接返回false，若第一个括号为右括号，直接返回false
        if(s.length()%2!=0 || s.charAt(0)==')' || s.charAt(0)=='}' || s.charAt(0)==']'){
            return false;
        }
        Map<Character,Character> hash=new HashMap<>();
        hash.put(')','(');
        hash.put(']','[');
        hash.put('}','{');
        hash.put('?','?');

        Stack<Character> stack=new Stack<Character>();
        stack.push('?');
        for(int i=0;i<s.length();i++){
            //思路：
            //如果是左括号，就直接入栈
            //如果是右括号，通过hashMap进行对应其左括号是否与栈顶的元素相等，相等的话就出栈然后继续遍历，不相等的话，则直接返回false;
            if(s.charAt(i)=='(' || s.charAt(i)=='{' || s.charAt(i)=='['){
                stack.push(s.charAt(i));
            }else {
                if(hash.get(s.charAt(i))==stack.peek()){
                    //注意这个测试用例 "(){}}{"
                    //pop() 空栈会报错，所以最开始要放个多放个符号进去，防止报错
                    //最后判断stack的长度是不是1
                    stack.pop();
                }else{
                    return false;
                } 
            }
        }
        //如果stack最后不为空的话，返回fasle
        if(stack.size()!=1){
            return false; 
        }
        return true;
        
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //知识点：节点的值：node.val， 节点的指针：node.next
        
        //方法一：递归 套娃，自己调用自己。比如 f(x)=f(x-1)+x 后边数的取值取决于前一个数的取值
        //关于这道题，判断list1和list2节点的值的大小，小的值在前并且改变其next指针即可，当list1为空时，后边的不用比较，直接返回list2即可,list2为空时也是同理
        //具体代码实现如下：
        if(list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }else if(list1.val<list2.val){//如果list1小的话，改变list1的next指针域，下次递归调用输入的就是list1.next
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else{//同理
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }

        //时间复杂度：递归算法的时间复杂度=递归调用的次数*计算时间复杂度
        //m、n 为 list1,list2的节点个数，且只进行了next指针的赋值操作，时间复杂度为O(1)
        //所以递归的总时间复杂度为O(m+n)

        //空间复杂度：递归次数为m+n,使用了m+n个栈帧，所以空间复杂度也为O(m+n)
        //注：栈帧也叫过程活动记录，是编译器用来记录函数调用过程的一个数据结构。

    }
}

class Solution{
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //知识点：定义链表头节点的规范的写法。ListNode list=new ListNode(0);做一个哨兵节点，答案存放在list.next之后。list不变，维护一个prev指针，prev=lsit,使prev去动。
        //方法二：迭代，通过控制循环，逐渐逼近正确答案
        //思路：新建一个链表list，对list1和list2中的每一个节点进行比较，较小的放在前边，大的往后放，知道一个链表结束时list的next指针指向未结束的链表所在的节点
        ListNode list=new ListNode(0);
        ListNode prev=list;
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                prev.next=list1;
                list1=list1.next;
            }else{
                prev.next=list2;
                list2=list2.next;
            }
            prev =prev.next;
        }
        //<判别式>?s1 : s2  判别式成立，返回s1,不成立，返回s2
        prev.next= list1==null?list2:list1;
        return list.next;
    }
    //时间复杂度：O(m+n)   n 和 m分别为两个链表的长度。每次迭代循环中，while 循环的次数不会超过两个链表的长度之和。
    //空间复杂度：O(1）。我们只需要常数的空间存放若干变量。
}        

class Solution {
    public int maxSubArray(int[] nums) {
        //明确：子序列 是不要求连续的；子数组和子串一样，是需要连续的。
        //思路：求和的最大值，最值问题很可能就是动态规划的问题。设置一个动态数组dp[i],存放前i元素之中连续子数组的最大和，令dp[0]=nums[0]。当dp[i-1]>0时，dp[i]=nums[i]+dp[i-1];当dp[i-1]<=0时，dp[i]=nums[i]。使用max来记录在遍历过程中的dp中的最大值
        int []dp=new int[nums.length];
        dp[0]=nums[0];
        int max=nums[0];
        for(int i=1;i<nums.length;i++){
            if(dp[i-1]>0){
                dp[i]=nums[i]+dp[i-1];
            }else{
                dp[i]=nums[i];
            }
            max=Math.max(max,dp[i]);
        }
        return max;

    }
}

class Solution {
    public int climbStairs(int n) {
        //这三题有相同的思路：最后一条要么跳一阶要么跳两阶。那么将前一阶的跳法+前两阶的跳法加起来，所得到的即为
        //所以f(n)=f(n-1)+f(n-2)
        //设置一个dp[i]用于记录i阶楼梯的跳法。
        //0阶楼梯可以不跳，也算一种方法。
        int [] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<n+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

class Solution {
    List<Integer> res=new ArrayList<Integer>();//写在递归外边，无需一直新建数组
    public List<Integer> inorderTraversal(TreeNode root) {
        //知识点：二叉树的遍历，所有的前序中序后序指的是根的位置
        //前序遍历：根-》左-》右
        //中序遍历：左-》根-》右，按顺序写下来即可，横着。
        //后序遍历：左-》右-》根
        //根：root 根的左节点：root.left  根的右节点：root.right
        //要返回List数组，所以使用ArrayList。ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。
        //ArrayList 继承了 AbstractList ，并实现了 List 接口。
        //ArrayList使用add()添加元素；使用get(索引)访问元素，数组的索引值从 0 开始；set(索引，修改的值)进行修改元素；remove(索引)删除元素。
        //方法一：递归，自己调用自己，套娃。
        if(root!=null){
            //中序遍历：左根右
            inorderTraversal(root.left);
            //根的值放进去
            res.add(root.val);
            inorderTraversal(root.right);
        }
        return res;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //方法二：迭代，使用while循环
        //思路：递归的函数可以用迭代的方法进行实现，区别在于递归时隐式的维护了一个栈，在迭代的时候需要将这个栈显式的模拟出来。
        //知识点：
        //deque 和stack 的区别。
        //Stack栈比较熟悉，后进先出，一端开口，可以进行压入push(E),栈顶弹出pop(E),取栈顶peek(E);
        //Deque 是 double-ended queue 的缩写,允许两头都进，两头都出，这种队列叫双端队列。Deque是一个接口，它的实现类有ArrayDeque和LinkedList。可以利用deque实现栈的功能。
        //Java的集合类并没有单独的Stack接口，因为有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来“模拟”一个Stack了。但是只能调用这三个方法，不可以调用栈的其他方法。
        //Queue时队列，前端进行删除操作，后端进行**操作，先进先出。
        
        List<Integer> res=new ArrayList<Integer>();
        Deque<TreeNode> stack=new LinkedList<>();
        //考虑两种情况，root不为空，stack不为空
        while(root!=null || ! stack.isEmpty()){
            //root不为空时，不断向左子树的方向走，每走一次将当前节点保存到栈中
            if(root!=null){
            stack.push(root);
            root=root.left;
            }else{//stack不为空时，栈顶元素进行弹出，root=root.right;
            TreeNode temp=stack.pop();
            res.add(temp.val);
            root=temp.right;
            }
        }
        return res;

    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //思路：实现一个递归函数，同时控制两个指针移动，分别遍历根节点下的左子树和右子树，左子树的左节点和右子树的右节点比，检查值是否相等。
        return check(root,root);
    }

    public boolean check(TreeNode p,TreeNode q){
        if(p == null && q==null){//p.q都为空时，一定相等。
            return true;
        }else if(p!=null && q!=null){//p、q都不为空时，判断值是否相等，并且继续判断左右是否相等

            return p.val==q.val && check(p.left,q.right) && check(p.right,q.left);
        }else{//左空右不空或者右空左不空，一定不对称。
            return false;
        }

    }

}

class Solution {
    public int maxDepth(TreeNode root) {
        //我的思路：根的左右树进行分开，进行递归maxDepth(root.left),maxDepth(root.right),利用Math.max()求最大值
        //注意：递归不需要使用循环，包含while,for，他自然而然的会动。
        if(root==null){
            return 0;
        }else{
            int left=maxDepth(root.left)+1;
            int right=maxDepth(root.right)+1;
            return Math.max(left,right);
        }       
    }
}

class Solution {
    public int maxProfit(int[] prices) {
//思路：看到最这个字，条件反射会想到用动态规划来做。
//max用来记录最大的利润，初始值为0.
//把最小的股票价格记录下来min_price。
//先用当前的股票价格和历史最小值比较，如果比历史价格还小，利润不变，更新min_price;如果当前 的价格比min高，用当前价格减去min_price,跟max相比，取最大值。
        int max=0;
        int min_price=prices[0];
        //遍历price数组,按思路去写即可。
        for(int i=1;i<prices.length;i++){
            if(prices[i]<min_price){
                min_price=prices[i];
            }else{
                max=Math.max(max,prices[i]-min_price);
            }
        }
        return max;
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        //我的思路：读题就想用HashMap做，但是题目说不允许使用额外空间。实在不行可以暴力求解，两次循环，第一次循环记录cur,第二次循环找有没有cur,不过时间复杂度到O(N^),还是不要这种了。
        //评论区里边说：不许额外空间往位运算上想。

        //位运算知识：
         //二进制中的与 或 非 异或
        //与& 全1则1
        //或| 有1则1
        //非~ 按位取反   ~10000 =01111
        //异或^  相同取0，不同取1  
        //异或规则① 任何数和0异或都等于他本身
        //异或规则② 自己和自己异或结果为0

        //出现两次的数字自己异或自己，消掉得0，出现一次的数字与0异或还是他本身。
        for(int i=1;i<nums.length;i++){
            nums[0]=nums[0]^nums[i];
        }
        return nums[0];
    }

}

public class Solution {
    public boolean hasCycle(ListNode head) {
        //我的思路：把链表放进hash表中，listNode值存在时，返回true
    //不能只存node.val，因为链表所存数据的值是可以存在重复值的，但是Set不可以重复存放。
        Set<ListNode> hash=new HashSet<ListNode>();
        while(head!=null){
            if(!hash.add(head)){
                return true;
            }else{
                hash.add(head);
                head=head.next;
            }
        }
        return false;
    }
}

class MinStack {
//liweiwei思路：用栈检索最小元素，栈特性后进先出，用两个栈，一个栈存放数据dataStack,一个栈存放前n个元素中最小的元素minStack。
    Stack<Integer> dataStack;
    Stack<Integer> minStack;
    public MinStack() {
        dataStack=new Stack<>();
        minStack=new Stack<>();
    }
    //入栈：数据栈正常push()进入。最小元素栈：当栈为空时，正常放入；当最小栈不为空时，最小栈当前的栈顶元素和需要进栈的元素进行比较 ，当当前元素大于栈顶元素时，将栈顶元素再次入栈，当前元素小于栈顶元素时，当前元素进行入栈
    public void push(int val) {
        //数据栈
        dataStack.push(val);
        //最小栈
        if(minStack.isEmpty() || minStack.peek()>=val){
            minStack.push(val);
        }else{
            minStack.push(minStack.peek());
        }
    }
    //两个栈进行出栈时，最小栈和数据栈都进行出栈操作。
    public void pop() {
        if(!dataStack.isEmpty()){
        minStack.pop();
        dataStack.pop();
        }
        
    }
    
    //获取栈顶元素的方法
    public int top() {
        return dataStack.peek();
    }
    //从最小栈获取最小元素
    public int getMin() {
        return minStack.peek();
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //我的思路：比如ListA=a+c两部分组成，ListB=b+c组成，c是公共部分。则a+c+b=b+c+a，一个指针listA从A上走，走完A后走完B特有的=指针从B走完走到A特有的部分，那个地方就是相交节点。
        //知识点：链表的公共节点不仅是值相同，还必须是指针指向的地址相同，不能单纯凭值判断。
        ListNode listA=headA;
        ListNode listB=headB;
        while(listA!=listB){
            //<判别式>?成立结果:不成立的结果
           listA= listA==null ?headB:listA.next;
           listB= listB==null ?headA:listB.next;
        }
        return listA;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //链表的公共节点是存的内存地址相同，而不是val相同
        //在公共结点之后，两个链表指针指向的地址是相同的。

        //如果AB存在空的话，没有公共节点
        if(headA==null || headB==null){
            return null;
        }



        //这道题可以使用双指针
        //但是有一个问题是他俩的长度不相同，但是headA+headB=headB+headA,把两个链表都加上对方的长度，则它们到达公共节点时，指向的就是一个相同的公告节点了

        ListNode pb=headA;
        ListNode pa=headB;
        //让两个指针先从对方身上走一圈，直到走回自己身上的公共节点即可
        //pa pb 没到公共节点时
        while(pa!=pb){
            //当pb为空时，说明指针走完了A，就移回B上，不为空时就接着在A上走
            pb= pb==null?headB: pb.next;
            pa= pa==null?headA:pa.next;
        }
        //已经移到公共节点了
        return pa;

    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        //思路：一个自然而然的想法就是把节点的next指针域转移到前边来，设置两个指针prev,curr;
        //改变next指针，curr.next=prev；然后进行迭代令prev=curr,curr=curr.next,但是此时会有一个问题，curr.next已经指向前边的prev,和后边的节点断开连接了，为了解决这个问题，要把在改变next指针之间，先把curr.next存储起来
        //不存next时：1⬅2  3→4→5→null  链表断开，无法迭代
        ListNode prev=null;
        ListNode curr=head;
        //当curr!=null时,
        while(curr!=null){
            //先把next存起来
            ListNode next=curr.next;
            //next指针进行反转
            curr.next=prev;
            prev=curr;
            curr=next;
        }
        //在最后一次循环中，curr==null;prev成为了头节点
        return prev;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //思路：二叉树常用方法就是进行：递归
        //规律：从根节点开始，交换当前节点的左右节点，再递归交换当前节点的左节点，递归交换当前节点的右节点
        
        //终止条件：当前节点为null时返回  
        if(root==null){
            return root;
        }
        //交换当前节点的左右子树
        TreeNode temp=root.right;
        root.right=root.left;
        root.left=temp;

        //交换当前节点的左子树
        invertTree(root.left);

        //交换当前节点的右子树
        invertTree(root.right);

        //函数返回时表示当前节点以及他的左右子树都已经交换完了
        return root;

    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        //思路：将链表先放入数组，双指针进行循环判断是否为回文链表
        //动态数组列表的定义：ArrayList可以任意伸缩数组长度的对象，add()添加一个新的元素，remove()删除一个元素，size()获取ArrayList的长度，下表是从0开始的,获取下标为index的元素get(index)
        List<Integer> nums=new ArrayList<>();

        //复制链表中的值
        ListNode node=head;
        while(node!=null){
            nums.add(node.val);
            node=node.next;
        }
        //双指针遍历数组
        for(int i=0,j=nums.size()-1;i<j;){
            if(nums.get(i)==nums.get(j)){
                i++;
                j--;
            }else{
                return false;
            }
        }
       return true;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        //思路：遍历数组，记录当前非0的元素和非0元素的个数，用当前非0元素对原数组进行覆盖，未被二次覆盖的数组进行置0
        int cnt=0;
        for(int i=0;i<nums.length;i++){
          if(nums[i]!=0){
            int temp=nums[i];
            nums[cnt]=temp;
            cnt++;
          }  
        }
        //将数组未被覆盖部分的元素置0
        while(cnt<nums.length){
            nums[cnt]=0;
            cnt++;
        }
    }
}

class Solution {
    public int[] countBits(int n) {
        //思路：先从0开始到n,求每个数字在二进制中包含的1的个数;0的二进制为不包含1
        //&运算全1得1，二进制数进行右移>>>1
        int []res=new int[n+1];
        res[0]=0;
        for(int i=1;i<=n;i++){
            res[i]=countOnes(i);
        }
        return res;
    }
    //定义方法计算每个二进制数中1的个数
    public int countOnes(int x){
        int cnt=0;
        while(x>0){
            if((x&1)==1){
                cnt++;
            }
            //二进制数进行右移
            x=x>>>1;
        }
        return cnt;
    }
}

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //思路：求1-n内没有在数组中的数字，利用HashSet的特性，set中已经存在的key存不下相同的key值了，可以把数组存到set里，再从1-n进行循环，如果可以加入set中的值，说明是数组中不存在的数，也把他加入动态数组中去。
        List<Integer> res=new ArrayList<>();
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        //从1-n的数字如果可以加进去，说明数组中没有该数字，就把数组加到动态数组中去
        //动态数组列表的定义：ArrayList可以任意伸缩数组长度的对象，add()添加一个新的元素，remove()删除一个元素，size()获取ArrayList的长度，下表是从0开始的,获取下标为index的元素get(index)
        for(int i=1;i<=nums.length;i++){
            if(set.add(i)){
                res.add(i);
            }
        }
        return res;
    }
}

class Solution {
    public int hammingDistance(int x, int y) {
        //思路：二进制的异或 ^,相同取0，不同取1，可以先将x,y进行异或，求所得结果中1的个数,使用与&运算，全1则1,s进行右移，当s=0时结束循环
        int s=x^y;
        int cnt=0;
        while(s!=0){
            if((s&1)==1){
                cnt++;
            }
            s=s>>>1;
        }
        return cnt;
    }
}

class Solution {
    //思路：求二叉树的直径长度翻译一下就是 找出二叉树中最长的两个节点之间的最短路径，在拆解成两步就是：①求两个叶子节点之间的最短路径②在所有叶子节点中找到最长的路径。
        //路径的长度=经过节点数-1；任意一条路径可以看作某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。这样计算出每个节点的最大直径（左子树深度+右子树深度）和当前最大值进行比较，取最大值。
        int maxd=0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxd;
    }
    public int depth(TreeNode node){
        //递归终止条件
        if(node==null){
            return 0;
        }
        int left=depth(node.left);
        int right=depth(node.right);
        maxd=Math.max(left+right,maxd);//每个节点的最大直径取较大值
        return Math.max(left,right)+1;//返回节点的深度
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //思路：深搜的过程，左空右空为null;一个为空值为另一个；都非空则为他们的和
        //跳出递归的条件
         if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}