力扣算法入门刷题2

12、删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

 输入：head = [1,1,2]

 输出：[1,2[

//链表结构
public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        
        ListNode node = head;
        while(node.next != null){
            if(node.val == node.next.val){
                node.next = node.next.next;
            }else{
                node = node.next;
            }
        }
        return node;
    }
}

13、相同的树 --- 深度优先

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的

public static void dfs(TreeNode node1,TreeNode node2){
    //递归的结束标志，当遍历到树的节点为空时结束当前路径的遍历，并返回true
    if(node1 == null && node2 == null) return true;
    //如果两个节点一个为空一个不为空则不相同
    else if(node1 == null || node2 == null) return false;
    //如果两节点不为空，但值不相等 也不相等
    else if(node1.val != node2.val) return false;
    //再比较左子树和右子树是否相等
    else return dfs(node1.left,node2.left) && dfs(node1.right,node2.right);
 
}

14、求二叉树路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

 public boolean hasPathSum(TreeNode root, int sum) {
        //如果当前节点为空返回false
        if (root == null) {
            return false;
        }
        //如果不为空，但是左子节点和右子节点都为空则为叶子节点
        // 最后一个叶子节点的值应该等于目标值
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        //不满足条件就将总和减去当前节点的值，重复递归
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

15、买卖股票的最佳时机 ----- 动态规划

public int maxProfit(int[] prices) {
       if(prices.length <= 1){
           return 0;
       }
       int max = 0;
       int min = prices[0];
       for(int i = 0;i < prices.length;i++){
           max = Math.max(max,prices[i] - min);
           min = Math.min(min,prices[i]);
       }
       return max;
    }

16、摩尔投票法(同归于尽法)求众数

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution {
    public int majorityElement(int[] nums) {
        //同归于尽法
        //定义第一个占领场地的阵营
        int win = nums[0];
        //此时阵营实力为1
        int count = 1;
        //所有人依次闯进领地
        for(int i = 1; i < nums.length; i++){
            //发现过来的是同一阵营的，实力加一
            if(nums[i] == win){
                count++;
            }else if(count == 0){
                //如果原本占领场地的阵营挂了
                //下次来的人所属阵营为新的占领者
                win = nums[i];
                //实力重赋值为1
                count = 1;
            }else{
                //发现过来的不是同一个阵营的人一换一
                count--;
            }
        }
        //最终留下的人为赢家
        return win;
    }
}