public class BalancedBinaryTree { //方法一：先序遍历 public boolean isBalanced1(TreeNode root) { if(root==null) return true; return Math.abs(height(root.left)-height(root.right))<=1 &&isBalanced(root.left) &&isBalanced(root.right); } //方法二：后序遍历 public boolean isBalanced(TreeNode root) { r...

//方法一：先序遍历 public TreeNode invertTree(TreeNode root) { if ( root == null ) return null; TreeNode temp = root.left; root.left = root.right; root.right = temp; invertTree( root.left ); invertTree( root.right ); return root; } //方法二：后序遍历 public TreeNode invertTree(TreeNode root) { if ( root == null ) r...

import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; public class Mergelntervals { //按区间左边界排序 public int[][] merge(int[][] intervals) { //定义一个结果数组 ArrayList<int[]> result = new ArrayList<>(); //1.将所有区间按照左边界排序 Arrays.sort(intervals, new Comparator<int[]>...

import java.util.Arrays; public class SortColors { //方法一：直接调库 public void sortColors1(int[] nums) { Arrays.sort(nums); } //方法二：基于选择排序的一种实现 public void sortColors2(int[] nums) { //定义一个指针，指向当前应该填入元素的位置 int cur = 0; //1.遍历数组，将所有的0交换到起始位置 for (int i = 0; i <nums.length ; i++) { if(nums[i]==0){ swap(n...

import java.util.Arrays; import java.util.Random; public class FindKthLargest { //方法一：直接排序(调库) public int findKthLargest1(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; } //方法二：基于快排的选择 public int findKthLargest2(int[] nums, int k) { return quickSelect(nums,0,nums.length-1,nums.l...

import java.util.Stack; public class LargestRectangleInHistorgram { //方法一：暴力法(遍历所以可能的宽度) public int largestRectangleArea1(int[] heights) { //定义变量保存最大面积 int largestArea= 0; //遍历数组，作为矩形左边界 for (int left = 0; left <heights.length ; left++) { //定义变量保存当前矩形高度 int currHeight = heights[left]; //遍历数组，选取矩形...

import java.util.Deque; import java.util.LinkedList; public class VaildParentheses { //使用栈 public boolean isVaild(String s){ Deque<Character> stack = new LinkedList<>(); //遍历字符串中所有字符,依次判断 for (int i = 0; i < s.length(); i++) { //获取当前字符 char c = s.charAt(i); //判断当前字符是左括号还是右括号 //如果是左括号，...

import java.util.Stack; //用两个栈实现 public class MyQueue { //定义两个栈 Stack<Integer> stack1; Stack<Integer> stack2; public MyQueue() { stack1 = new Stack<>(); stack2 = new Stack<>(); } //入队方法 public void push(int x){ //1.将stack1中的弹出压入stack2中 while (!stack1.isEmpty()){ stack2.push(s...

import java.util.LinkedList; import java.util.Queue; // 使用两个队列实现自定义栈 public class MyStack { // 定义两个队列 Queue<Integer> queue1; Queue<Integer> queue2; public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } // 入栈方法 public void push(int x){ // 1. 把x保存到queue...

//方法一：使用LinkedHashMap import java.util.LinkedHashMap; import java.util.Map; public class LRUCache extends LinkedHashMap<Integer,Integer> { //定义缓存容量 private int capacity; public LRUCache(int capacity) { super(capacity,0.75f,true); this.capacity = capacity; } //访问数据方法 public int get(int key){ if...

import java.util.HashSet; public class LongestConsecutive { //1.暴力法 public int longestConsecutive1(int[] nums) { //定义一个变量，保存当前最长连续序列的长度 int maxLength = 0; //遍历数组，以每个元素作为起始点，寻找连续序列 for (int i = 0; i <nums.length ; i++) { //保存当前元素作为起始点 int currNum = nums[i]; //保存当前连续序列长度 int currLength = 1; //寻找后续数...

import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; public class SingleNumber { //方法一：暴力破解 public int singleNumber1(int[] nums) { int result = nums[0]; for (int i = 0; i <nums.length ; i++) { boolean flag = true; for (int j = 0; j <nums.length ; j++) { //不与自身比较 if(i...

import java.util.Stack; public class RemoveNthEnd { //方法一：计算链表长度 public ListNode removeNthFromEnd1(ListNode head, int n) { //1.遍历链表，得到长度l int l = getLength(head); ListNode result = null; //2.从前到后遍历，找到正数第l-n+1个元素 //定义一个哨兵节点,next指向头节点 ListNode sentinel = new ListNode(-1,head); ListNode curr = sentinel...

public class MergeTwoSortedLists { //方法一：迭代法 public ListNode mergeTwoLists1(ListNode l1, ListNode l2) { //首先定义一个哨兵节点,它的next指向最终结果的头节点 ListNode sentinel = new ListNode(-1); //保存当前结果链表里的最后一个节点作为判断比较的前一个节点 ListNode prev = sentinel; //迭代遍历两个链表 ，直到至少有一个null while (l1!=null&&l2!=null){ //比较当前两个链表头...