devbox
笔尖舞者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

力扣HOT100-Java个人题解整理与总结

作者：笔尖舞者 | 2024-01-30 21:24:22

赞

踩

力扣hot100

 LeetCode 热题 HOT 100

1，两数之和

难度简单13695

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路：

  • 采用两层遍历法，代码比较简单，单复杂度高、
  • 为了减少时间复杂度，因为题干中说明了，只有一种情况的答案，顾可以采用map<value,index>去存储nums数组，达到减少时间复杂度。
  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {   
  3.         for(int i=0;i<nums.length-1;i++){
  4.             for(int j=i+1;j<nums.length;j++){
  5.                 if(nums[i]+nums[j]==target)
  6.                 return new int[]{i,j};
  7.             }
  8.         }
  9.         return new int[]{0,0};
  10.     }
  11. }
  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {   
  3.         HashMap<Integer,Integer> m=new HashMap<>();
  4.         for(int i=0;i<nums.length;i++){   
  5.           m.put(nums[i],i);
  6.         }
  7.         for(int i=0;i<nums.length;i++){
  8.             int t=target-nums[i];
  9.             if(m.containsKey(t)&&m.get(t)!=i){// 相同的位置的值不能出现在答案中
  10.                 return new int[]{i,m.get(t)};
  11.             }
  12.         }
  13.         return new int[]{0,0};
  14.     }
  15. }

2，两数相加（两链表相加）

难度中等7667

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  13.         ListNode res=new ListNode();
  14.         ListNode tail=res;
  15.         res.next=null;
  16.         int jin=0;
  17.         while(l1!=null&&l2!=null){
  18.             int t=l1.val+l2.val+jin;
  19.             if(t>=10){
  20.                 jin=1;
  21.                 t-=10;
  22.             }else{
  23.                 jin=0;
  24.             }
  25.             ListNode temp=new ListNode(t);
  26.             temp.next=null;
  27.             tail.next=temp;
  28.             tail=temp;
  29.             l1=l1.next;
  30.             l2=l2.next;
  31.         }
  32.         while(l1!=null){
  33.             int t=l1.val+jin;
  34.             if(t>=10){
  35.                 jin=1;
  36.                 t-=10;
  37.             }else{
  38.                 jin=0;
  39.             }
  40.            ListNode temp=new ListNode(t);
  41.             temp.next=null;
  42.             tail.next=temp;
  43.             tail=temp;
  44.             l1=l1.next;
  45.         }
  46.          while(l2!=null){
  47.             int t=l2.val+jin;
  48.             if(t>=10){
  49.                 jin=1;
  50.                 t-=10;
  51.             }else{
  52.                 jin=0;
  53.             }
  54.             ListNode temp=new ListNode(t);
  55.             temp.next=null;
  56.             tail.next=temp;
  57.             tail=temp;
  58.             l2=l2.next;
  59.         }
  60.         if(jin==1){
  61.              ListNode temp=new ListNode(1);
  62.             temp.next=null;
  63.             tail.next=temp;
  64.             tail=temp;
  65.         }
  66.        return res.next;
  67.     }
  68. }

3，无重复字符的最长子串（for+indexOf）

难度中等7090

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int res=0;
  4.         String temp="";
  5.         for(int i=0;i<s.length();i++){
  6.             int flag=temp.indexOf(s.charAt(i));
  7.             if(flag>=0){
  8.                 temp=temp.substring(flag+1,temp.length());
  9.             }
  10.             temp=temp+s.charAt(i);
  11.             res=Integer.max(res,temp.length());
  12.         }
  13.         return res;
  14.     }
  15. }

4，寻找两个正序数组的中位数（大小根堆）

难度困难5124

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

  1. class Solution {
  2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3.         ArrayList<Integer> res=new ArrayList<>();
  4.         for(int i:nums1){
  5.             res.add(i);
  6.         }
  7.          for(int i:nums2){
  8.             res.add(i);
  9.         }
  10.         Collections.sort(res);
  11.         int f=nums1.length+nums2.length;
  12.         if(f%2==0){
  13.             return (double)(res.get(f/2-1)+res.get(f/2))/2;
  14.         }else{
  15.             return res.get(f/2);
  16.         }
  17.     }
  18. }

5，最长回文子串（dp）

难度中等4842

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         // 典型的dp问题 dp[i][j] 表示下标i-j的子字符串为回文串
  4.         // dp[i][j]=true or flase
  5.         String res="";
  6.         res=res+s.charAt(0);
  7.         boolean [][]dp=new boolean[s.length()][s.length()];
  8.         for(int i=0;i<s.length();i++){
  9.             dp[i][i]=true;
  10.         }
  11.         for(int len=2;len<=s.length();len++){
  12.             for(int i=0;i<s.length();i++){
  13.                 int j=i+len-1;
  14.                  if(j>=s.length())break;
  15.                  if(s.charAt(i)==s.charAt(j)){
  16.                      if(j-i<=2){
  17.                          dp[i][j]=true;
  18.                      }else{
  19.                          dp[i][j]=dp[i+1][j-1];
  20.                      }
  21.                  }
  22.                  if(dp[i][j]==true&&j-i+1>res.length()){
  23.                      res=s.substring(i,j+1);
  24.                  }
  25.             }
  26.         }
  27.         return res;
  28.     }
  29. }

11，盛最多水的容器（贪心）

难度中等3280

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

  1. class Solution {
  2.     public int maxArea(int[] height) {
  3.         int res=0;
  4.         int left=0;
  5.         int right=height.length-1;
  6.         while(left<right){
  7.             res=Math.max(res,(right-left)*Math.min(height[left],height[right]));
  8.             if(height[left]>height[right]){
  9.                 right--;
  10.             }else if(height[left]<height[right]){
  11.                 left++;
  12.             }else{
  13.                 if(right-left<=2){
  14.                     left++;
  15.                 }else{
  16.                     if(height[left+1]>height[right-1]){
  17.                         left++;
  18.                     }else {
  19.                         right--;
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.         return res;
  25.     }
  26. }

15、三数之和（三层循环）

难度中等4464

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路：

  1. 三数之和，先排序，三层遍历，固定两个索引，从后向前遍历，去重步骤是开头两固定的索引（满足nums[i]!=nums[i-1]）即可达到去重复的目的。
  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         int n = nums.length;
  4.         Arrays.sort(nums);
  5.         List<List<Integer>> ans = new ArrayList<List<Integer>>();
  6.         // 枚举 a
  7.         for (int first = 0; first < n; ++first) {
  8.             // 需要和上一次枚举的数不相同
  9.             if (first > 0 && nums[first] == nums[first - 1]) {
  10.                 continue;
  11.             }
  12.             // c 对应的指针初始指向数组的最右端
  13.             int third = n - 1;
  14.             int target = -nums[first];
  15.             // 枚举 b
  16.             for (int second = first + 1; second < n; ++second) {
  17.                 // 需要和上一次枚举的数不相同
  18.                 if (second > first + 1 && nums[second] == nums[second - 1]) {
  19.                     continue;
  20.                 }
  21.                 // 需要保证 b 的指针在 c 的指针的左侧
  22.                 while (second < third && nums[second] + nums[third] > target) {
  23.                     --third;
  24.                 }
  25.                 // 如果指针重合，随着 b 后续的增加
  26.                 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
  27.                 if (second == third) {
  28.                     break;
  29.                 }
  30.                 if (nums[second] + nums[third] == target) {
  31.                     List<Integer> list = new ArrayList<Integer>();
  32.                     list.add(nums[first]);
  33.                     list.add(nums[second]);
  34.                     list.add(nums[third]);
  35.                     ans.add(list);
  36.                 }
  37.             }
  38.         }
  39.         return ans;
  40.     }
  41. }

17、电话号码的字母组合（dfs）

难度中等1770

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

  1. class Solution {
  2.     List<String> res=new ArrayList<>();
  3.     public List<String> letterCombinations(String digits) {
  4.         if(digits.length()==0)return res;
  5.         String[] map=new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
  6.         dfs(0,digits,"",map);
  7.         return res;
  8.     }
  9.     public void dfs(int index,String s,String cv,String []map){
  10.         if(index==s.length()){
  11.             res.add(new String(cv));
  12.             return;
  13.         }
  14.         for(int i=0;i<map[s.charAt(index)-'0'].length();i++){
  15.             dfs(index+1,s,cv+map[s.charAt(index)-'0'].charAt(i),map);
  16.         }
  17.     }
  18. }

19，删除链表的倒数第N个结点

难度中等1861

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode removeNthFromEnd(ListNode head, int n) {
  13.         ListNode res=new ListNode(-1);
  14.         res.next=head;
  15.         while(n!=0){
  16.             head=head.next;
  17.             n--;
  18.         }
  19.  
  20.         ListNode p1=res,p2=res.next;
  21.         while(head!=null){
  22.             p1=p1.next;
  23.             p2=p2.next;
  24.             head=head.next;
  25.         }
  26.         p1.next=p2.next;
  27.         return res.next;
  28.     }
  29. }

20，有效的括号（栈）

难度简单3073

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         Stack<Character> stack=new Stack<>();
  4.         for(int i=0;i<s.length();i++){
  5.             if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){
  6.                stack.push(s.charAt(i));
  7.             }else{
  8.                if(stack.isEmpty())return false;
  9.                switch(s.charAt(i)){
  10.                    case ')': 
  11.                    if(stack.peek()=='('){
  12.                        stack.pop();
  13.                    }else return false;
  14.                    break;
  15.                    case '}': 
  16.                    if(stack.peek()=='{'){
  17.                        stack.pop();
  18.                    }else return false;
  19.                    break;
  20.                    case ']': 
  21.                    if(stack.peek()=='['){
  22.                        stack.pop();
  23.                    }else return false;
  24.                    break;
  25.                }
  26.             }
  27.             
  28.         }
  29.         return stack.isEmpty();
  30.     }
  31. }

21、合并两个有序链表

难度简单2264

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  13.         ListNode res=new ListNode(-1);
  14.         res.next=null;
  15.         ListNode tail=res;
  16.  
  17.         while(list1!=null&&list2!=null){
  18.             ListNode temp;
  19.             if(list1.val>list2.val){
  20.                 temp=list2;
  21.                 list2=list2.next;
  22.             }else{
  23.                 temp=list1;
  24.                 list1=list1.next;
  25.             }
  26.             temp.next=null;
  27.             tail.next=temp;
  28.             tail=temp;
  29.         }
  30.         if(list1!=null){
  31.             tail.next=list1;
  32.         }
  33.         if(list2!=null){
  34.             tail.next=list2;
  35.         }
  36.         return res.next;
  37.     }
  38. }

22、括号生成（DFS）

难度中等2442

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

思路：

  1. 深度遍历只需要管住(，然后对)的数量小于等于(的数量。
  1. class Solution {
  2.     List<String> res=new ArrayList<>();
  3.     public List<String> generateParenthesis(int n) {
  4.         dfs(0,"",n);
  5.         return res;
  6.     }
  7.     void dfs(int index,String cv,int n){
  8.         if(cv.length()==2*n){
  9.             res.add(new String(cv));
  10.             return;
  11.         }
  12.         if(index<n)
  13.         dfs(index+1,cv+"(",n);
  14.  
  15.         if(2*index>cv.length()){
  16.             dfs(index,cv+")",n);
  17.         }
  18.     }
  19. }

23、合并k个升序链表

难度困难1806

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

注意：

  • throw new IllegalArgumentException("Comparison method violates its general contract!");
  • google了一下：JDK7中的Collections.Sort方法实现中，如果两个值是相等的，那么compare方法需要返回0，否则可能会在排序时抛错，而JDK6是没有这个限制的。
  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode mergeKLists(ListNode[] lists) {
  13.         ListNode res=new ListNode(-1);
  14.         ListNode tail=res;
  15.         res.next=null;
  16.         ArrayList<ListNode> arr=new ArrayList<>();
  17.         for(ListNode temp:lists){
  18.             ListNode t=temp;
  19.             while(t!=null){
  20.                 ListNode tt=t;
  21.                 t=t.next;
  22.                 tt.next=null;
  23.                 arr.add(tt);
  24.             }
  25.         }
  26.         Collections.sort(arr,new Comparator<ListNode>(){
  27.             public int compare(ListNode o1,ListNode o2){
  28.                 // if(o1.val>o2.val)return 1;
  29.                 // else if(o1.val<o2.val) return -1;
  30.                 // else return 0;
  31.                 return o1.val-o2.val;
  32.             }
  33.         });
  34.         for(int i=0;i<arr.size();i++){
  35.             ListNode temp=arr.get(i);
  36.             tail.next=temp;
  37.             tail=temp;
  38.         }
  39.         return res.next;
  40.     }
  41. }

31，下一个排列

难度中等1586

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

思路：

  1. 从后向前遍历，索引i之后的数字只要满足一个大于nums[i]的就可以跳出，将i之后的最小大于nums[i]的数和nums[i]进行交换，在进行Arrays.sort(nums,i+1,nums.length);
  1. class Solution {
  2.     ArrayList<String> list=new ArrayList<>();
  3.     public void nextPermutation(int[] nums) {
  4.         int i=nums.length-1;
  5.         PriorityQueue<Integer> q=new PriorityQueue<>((x,y)->y-x);
  6.         for(;i>=0;i--){
  7.             if(q.isEmpty()){
  8.                 q.add(nums[i]);
  9.             }else{
  10.                 if(nums[i]<q.peek()){
  11.                     break;
  12.                 }else{
  13.                     q.add(nums[i]);
  14.                 }
  15.             }
  16.         }
  17.         if(q.size()==nums.length){
  18.             Arrays.sort(nums,0,nums.length);
  19.             return;
  20.         }
  21.         int last=-1;
  22.         while(!q.isEmpty()&&q.peek()>nums[i]){
  23.             last=q.peek();
  24.             q.poll();
  25.         }
  26.         int j=i+1;
  27.         while(j<nums.length){
  28.             if(nums[j]==last){
  29.                 break;
  30.             }
  31.             j++;
  32.         }
  33.         nums[i]^=nums[j];
  34.         nums[j]^=nums[i];
  35.         nums[i]^=nums[j];
  36.         Arrays.sort(nums,i+1,nums.length);
  37.     }
  38. }

33，搜索旋转排序数组

难度中等1915

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         // 左边从左到右是递增的
  4.         // 右边从右到左是递减的
  5.         int len=nums.length;
  6.         int i=0;
  7.         for(;i<len;i++)
  8.         {
  9.             if(nums[i]==target)return i;
  10.             if(i>0&&nums[i]<nums[i-1]){
  11.                 break;
  12.             }
  13.         } 
  14.         int j=len-1;
  15.         while(i<=j){
  16.             int mid=(i+j)/2;
  17.             if(target==nums[mid]){
  18.                 return mid;
  19.             }else if(nums[mid]>target){
  20.                 j=mid-1;
  21.             }else{
  22.                 i=mid+1;
  23.             }
  24.         }
  25.         return -1;
  26.     }
  27. }

34，在排序数组中查找元素的第一个和最后一个位置

难度中等1533

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.         
  4.         int index=Arrays.binarySearch(nums,target);
  5.         if(index<0)return new int[]{-1,-1};
  6.         int l=index,r=index;
  7.         while(l>=0&&nums[l]==target){
  8.             l--;
  9.         }
  10.         
  11.         l++;
  12.        
  13.         while(r<nums.length&&nums[r]==target){
  14.             r++;
  15.         }
  16.         r--;
  17.         return new int[]{l,r};
  18.  
  19.     }
  20. }

39，组合总和(dfs)注意和139单词拆分的区别

难度中等1824

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

  1. class Solution {
  2.     List<List<Integer>> res=new ArrayList<>();
  3.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  4.         dfs(candidates,target,0,new ArrayList<>());
  5.         return res;
  6.     }
  7.  
  8.     void dfs(int[] candidates,int target,int index,ArrayList<Integer> tep){
  9.         if(index==candidates.length||target<0){
  10.             return;
  11.         }
  12.         if(target==0){
  13.             res.add(new ArrayList<>(tep));
  14.             return;
  15.         }
  16.         dfs(candidates,target,index+1,tep);
  17.  
  18.         if(target-candidates[index]>=0){
  19.             tep.add(candidates[index]);
  20.             dfs(candidates,target-candidates[index],index,tep);
  21.             tep.remove(new Integer(candidates[index]));
  22.         }
  23.     }
  24. }

42，接雨水

难度困难3227

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int left[]=new int[height.length];
  4.         int right[]=new int[height.length];
  5.         int min=-1;
  6.         for(int i=0;i<height.length;i++){
  7.             if(height[i]>min){
  8.                 min=height[i];
  9.             }
  10.             left[i]=min;
  11.         }
  12.         min=-1;
  13.         for(int i=height.length-1;i>=0;i--){
  14.             if(height[i]>min){
  15.                 min=height[i];
  16.             }
  17.             right[i]=min;
  18.         }
  19.         int res=0;
  20.         for(int i=0;i<height.length;i++){
  21.             int cmin=Integer.min(left[i],right[i]);
  22.             if(cmin>height[i]){
  23.                 res+=(cmin-height[i]);
  24.             }
  25.         }
  26.         return res;
  27.     }
  28. }

46，全排列(DFS

难度中等1846

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

  1. class Solution {
  2.     List<List<Integer>> res=new ArrayList<>();
  3.     public List<List<Integer>> permute(int[] nums) {
  4.         dfs(0,nums,new boolean[nums.length],new ArrayList<Integer>());
  5.         return res;
  6.     }
  7.     void dfs(int index,int []nums,boolean []visited,ArrayList<Integer> temp){
  8.         if(index==nums.length){
  9.             res.add(new ArrayList<>(temp));
  10.             return;
  11.         }
  12.         for(int i=0;i<visited.length;i++){
  13.             if(!visited[i]){
  14.                 temp.add(nums[i]);
  15.                 visited[i]=true;
  16.                 dfs(index+1,nums,visited,temp);
  17.                 temp.remove(new Integer(nums[i]));
  18.                 visited[i]=false;
  19.             }
  20.         }
  21.     }
  22. }

48，旋转图像

难度中等1211

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

思路：

  1. 逆时针旋转90°等效于左上角和右下角对换+上交对换。
  2. System.arraycopy()，可以保证对原数组进行从新赋值。
  1. class Solution {
  2.     public void rotate(int[][] matrix) {
  3.         int res[][]=new int[matrix.length][matrix[0].length];
  4.         int index=0;
  5.         for(int i=0;i<matrix.length;i++){
  6.             int tep[]=new int[matrix.length];
  7.             int cv=0;
  8.             for(int j=matrix.length-1;j>=0;j--){
  9.                 tep[cv]=matrix[j][i];
  10.                 cv++;
  11.             }
  12.             res[index]=Arrays.copyOf(tep,tep.length);
  13.             index++;
  14.         }
  15.         // matrix=res;
  16.         for(int i=0;i<matrix.length;i++)
  17.         System.arraycopy(res[i],0,matrix[i],0,matrix.length);
  18.     }
  19. }//

49，字母异或位词分组（DFS+Map<String,List<String>>）

难度中等1054

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

思路：

  1. map<String,value>,String的比较方法被从写，是比较值。
  1. class Solution {
  2.     List<List<String>> res=new LinkedList<>();
  3.     public List<List<String>> groupAnagrams(String[] strs) {
  4.         HashMap<String,List<String>> mymap=new HashMap<>();
  5.         int len=strs.length;
  6.         for(int i=0;i<len;i++)
  7.         {
  8.             char[] chars = strs[i].toCharArray();
  9.             Arrays.sort(chars);
  10.             String tep=new String(chars);
  11.             List<String> strings = mymap.get(tep);
  12.             if(strings==null)
  13.             {
  14.                 strings=new LinkedList<>();
  15.                 strings.add(strs[i]);
  16.                 mymap.put(tep,strings);
  17.             }
  18.             else{
  19.                 strings.add(strs[i]);
  20.             }
  21.         }
  22.         // 对mymap进行遍历
  23.         mymap.forEach((x,y)->{
  24.             res.add(new LinkedList<>(y));
  25.         });
  26.         return res;
  27.     }
  28. }

53，最大子数组和（贪心）

难度简单4543

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int res=Integer.MIN_VALUE;
  4.         int cv=0;
  5.         for(int i:nums){
  6.             if(cv+i<=i){
  7.                 cv=i;
  8.             }else{
  9.                 cv+=i;
  10.             }
  11.             res=Integer.max(res,cv);
  12.         }
  13.         return res;
  14.     }
  15. }

55，跳跃游戏（贪心）

难度中等1715

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：

  1. 从后向前跳跃，贪心思想。
  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int res=1;
  4.         for(int i=nums.length-2;i>=0;i--){
  5.             if(nums[i]>=res){
  6.                 res=1;
  7.             }else{
  8.                 res++;
  9.             }
  10.         }
  11.         return res==1?true:false;
  12.     }
  13. }

56，合并区间

难度中等1375

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         Arrays.sort(intervals, new Comparator<int[]>() {
  4.             @Override
  5.             public int compare(int[] o1, int[] o2) {
  6.                 if(o1[0]>o2[0]){
  7.                     return 1;
  8.                 }else if(o1[0]==o2[0]){
  9.                     if(o1[1]>o2[1]) {
  10.                         return 1;
  11.                     }
  12.                     else if(o1[1]==o2[1]) {
  13.                         return 0;
  14.                     }else{
  15.                         return -1;
  16.                     }
  17.  
  18.                 }else{
  19.                     return -1;
  20.                 }
  21.             }
  22.         });
  23.         List<int[]> res=new ArrayList<>();
  24.         int index=0;
  25.         int l=intervals[0][0];
  26.         int r=intervals[0][1];
  27.         index++;
  28.         while(index<intervals.length){
  29.             // 判断是否相交
  30.             if(l<=intervals[index][0]&&intervals[index][0]<=r){
  31.                 r=Integer.max(r,intervals[index][1]);
  32.             }else{
  33.                 res.add(new int[]{l,r});
  34.                 l=intervals[index][0];
  35.                 r=intervals[index][1];
  36.             }
  37.             index++;
  38.         }
  39.         res.add(new int[]{l,r});
  40.         return res.toArray(new int [0][]);
  41.     }
  42. }

62，不同路径（DP）

难度中等1326

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int dp[][]=new int[m][n];
  4.         for(int i=0;i<m;i++)dp[i][0]=1;
  5.         for(int i=0;i<n;i++)dp[0][i]=1;
  6.  
  7.         for(int i=1;i<m;i++){
  8.             for(int j=1;j<n;j++){
  9.                 dp[i][j]=dp[i-1][j]+dp[i][j-1];
  10.             }
  11.         }
  12.         return dp[m-1][n-1];
  13.     }
  14. }

64，最小路径和（DP）

难度中等1179

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int dp[][]=new int[grid.length][grid[0].length];
  4.         int csum=0;
  5.         for(int i=0;i<grid.length;i++){
  6.             csum+=grid[i][0];
  7.             dp[i][0]=csum;
  8.         }
  9.         csum=0;
  10.          for(int i=0;i<grid[0].length;i++){
  11.             csum+=grid[0][i];
  12.             dp[0][i]=csum;
  13.         }
  14.         for(int i=1;i<grid.length;i++){
  15.             for(int j=1;j<grid[0].length;j++){
  16.                 dp[i][j]=Integer.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
  17.             }
  18.         }
  19.         return dp[grid.length-1][grid[0].length-1];
  20.     }
  21. }

70，爬楼梯（DFS，迭代）

难度简单2264

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         if(n==1)return 1;
  4.         if(n==2)return 2;
  5.         int l1=1,l2=2;
  6.         int res=0;
  7.         for(int i=3;i<=n;i++){
  8.             res=l1+l2;
  9.             l1=l2;
  10.             l2=res;
  11.         }
  12.         return res;
  13.     }
  14. }

75，颜色分类

难度中等1193

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int index0=0;
  4.         int index2=0;
  5.         int index1=0;
  6.         for(int i=0;i<nums.length;i++){
  7.           if(nums[i]==0)index0++;
  8.           else if(nums[i]==1)index1++;
  9.           else index2++;
  10.         }
  11.         Arrays.fill(nums,0,index0,0);
  12.         Arrays.fill(nums,index0,index0+index1,1);
  13.         Arrays.fill(nums,index0+index1,index0+index1+index2,2);
  14.     }
  15. }

78，子集（DFS）

难度中等1528

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

  1. class Solution {
  2.     List<List<Integer>> res=new ArrayList<>();
  3.     public List<List<Integer>> subsets(int[] nums) {
  4.         dfs(0,nums,new ArrayList());
  5.         return res;
  6.     }
  7.     void dfs(int index,int []nums,ArrayList<Integer> cv){
  8.         if(index==nums.length){
  9.             res.add(new ArrayList<>(cv));
  10.             return;
  11.         }
  12.         //
  13.         dfs(index+1,nums,cv);
  14.         
  15.         cv.add(nums[index]);
  16.         dfs(index+1,nums,cv);
  17.         cv.remove(new Integer(nums[index]));
  18.     }
  19. }

79，单词搜索（DFS）

难度中等1224

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
  1. class Solution {
  2.     private boolean res=false;
  3.     public boolean exist(char[][] board, String word) {
  4.         int m=board.length;
  5.         int n=board[0].length;
  6.         boolean [][]visited=new boolean[m][n];
  7.         for(int i=0;i<m;i++){
  8.             if(res)break;
  9.             for(int j=0;j<n;j++){
  10.                 if(res)break;
  11.                 if(board[i][j]==word.charAt(0)){
  12.                     visited[i][j]=true;
  13.                     dfs(i,j,m,n,1,visited,board,word);
  14.                     visited[i][j]=false;
  15.                 }
  16.             }
  17.         }
  18.         return res;
  19.        
  20.     }
  21.     void dfs(int x,int y,int m,int n,int clen,boolean [][]visited,char[][] board,String word){
  22.         if(clen==word.length()){
  23.             res=true;
  24.             return;
  25.         }
  26.         if(res)return;
  27.         for(int i=0;i<4;i++){
  28.             switch(i){
  29.                 case 0: 
  30.                     if(x-1>=0&&!visited[x-1][y]&&board[x-1][y]==word.charAt(clen)){
  31.                         visited[x-1][y]=true;
  32.                         dfs(x-1,y,m,n,clen+1,visited,board,word);
  33.                         visited[x-1][y]=false;
  34.                     }
  35.                 
  36.                 break;
  37.                   case 1: 
  38.                     if(x+1<m&&!visited[x+1][y]&&board[x+1][y]==word.charAt(clen)){
  39.                         visited[x+1][y]=true;
  40.                         dfs(x+1,y,m,n,clen+1,visited,board,word);
  41.                         visited[x+1][y]=false;
  42.                     }
  43.                     break;
  44.                         case 2: 
  45.                     if(y-1>=0&&!visited[x][y-1]&&board[x][y-1]==word.charAt(clen)){
  46.                         visited[x][y-1]=true;
  47.                         dfs(x,y-1,m,n,clen+1,visited,board,word);
  48.                         visited[x][y-1]=false;
  49.                     }
  50.                     break;
  51.                   case 3: 
  52.                     if(y+1<n&&!visited[x][y+1]&&board[x][y+1]==word.charAt(clen)){
  53.                         visited[x][y+1]=true;
  54.                         dfs(x,y+1,m,n,clen+1,visited,board,word);
  55.                         visited[x][y+1]=false;
  56.                     }
  57.                 break;
  58.             }
  59.         }
  60.     }
  61.  
  62. }

94，二叉树的中序遍历

难度简单1323

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

  1. class Solution {
  2.     private List<Integer> res=new ArrayList<>();
  3.     public List<Integer> inorderTraversal(TreeNode root) {
  4.         inorder(root);
  5.         return res;
  6.     }
  7.  
  8.     void inorder(TreeNode root){
  9.         if(root==null){
  10.             return;
  11.         }
  12.         inorder(root.left);
  13.         res.add(root.val);
  14.         inorder(root.right);
  15.     }
  16. }

96，不同的二叉搜索树（DP）

卡特兰数-动态规划

难度中等1624

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

解题思路:
假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
f(i) = G(i-1)*G(n-i)

综合两个公式可以得到 卡特兰数 公式
G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0)

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         int[] dp = new int[n+1];
  4.         dp[0] = 1;// 表示树长度为0
  5.         dp[1] = 1;// 表示树长度为1
  6.         // dp[i]表示长度为i的搜索二叉树的种数，dp[i]=dp[0]*dp[i]+dp[1]*dp[i-1]+dp[2]*dp[i-2]..
  7.         for(int i = 2; i < n + 1; i++)// 树长
  8.             for(int j = 1; j < i + 1; j++) // 表示以j为根节点
  9.                 dp[i] += dp[j-1] * dp[i-j];
  10.         
  11.         return dp[n];
  12.     }
  13. }

98，验证二叉搜索树

难度中等1470

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     private long last=Integer.MAX_VALUE+1L;
  18.     private boolean res=true;
  19.     public boolean isValidBST(TreeNode root) {
  20.         inorder(root);
  21.         return res;
  22.     }
  23.     void inorder(TreeNode root){
  24.         if(root==null)return;
  25.         if(!res)return;
  26.         inorder(root.left);
  27.         if(last==Integer.MAX_VALUE+1L){
  28.             last=root.val;
  29.         }else{
  30.             if(root.val<=last){
  31.                 res=false;
  32.             }else{
  33.                 last=root.val;
  34.             }
  35.         }
  36.         inorder(root.right);
  37.     }
  38. }

101，对称二叉树

难度简单1809

给你一个二叉树的根节点 root ， 检查它是否轴对称。

  1. class Solution {
  2.     private boolean res=true;
  3.     public boolean isSymmetric(TreeNode root) {
  4.         // 根 左右  根 右左
  5.         dfs(root,root);
  6.         return res;
  7.     }
  8.     void dfs(TreeNode root1,TreeNode root2){
  9.         if(root1==null&&root2==null)return;
  10.         if(!res)return;
  11.         if((root1==null||root2==null)||(root1.val!=root2.val)){
  12.             res=false;
  13.             return;
  14.         }
  15.         dfs(root1.left,root2.right);
  16.         dfs(root1.right,root2.left);
  17.     }
  18. }

102，二叉树的层次遍历（队列）

难度中等1229

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     private List<List<Integer>> res=new ArrayList<>();
  18.     public List<List<Integer>> levelOrder(TreeNode root) {
  19.         if(root==null)return res;
  20.         LinkedList<TreeNode> q=new LinkedList<>();
  21.         q.addLast(root);
  22.         int cv=0;
  23.         int clen=1;
  24.         int next=0;
  25.         ArrayList<Integer> list=new ArrayList<>();
  26.         while(!q.isEmpty()){
  27.             TreeNode t= q.getFirst();
  28.             q.removeFirst();
  29.             cv++;
  30.  
  31.             list.add(t.val);
  32.         
  33.             if(t.left!=null){
  34.                 next++;
  35.                 q.addLast(t.left);
  36.             }
  37.             if(t.right!=null){
  38.                 next++;
  39.                 q.addLast(t.right);
  40.             }
  41.  
  42.             if(cv==clen){
  43.                 cv=0;
  44.                 clen=next;
  45.                 next=0;
  46.                 res.add(new ArrayList<>(list));
  47.                 list.clear();
  48.             }
  49.         }
  50.         return res;
  51.     }
  52. }

104，二叉树的最大深度

难度简单1152

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

  1. class Solution {
  2.     private int res=0;
  3.     public int maxDepth(TreeNode root) {
  4.         dfs(root,0);
  5.         return res;
  6.     }
  7.     void dfs(TreeNode root,int cv){
  8.         if(root==null){
  9.             res=Integer.max(res,cv);
  10.             return;
  11.         }
  12.         dfs(root.left,cv+1);
  13.         dfs(root.right,cv+1);
  14.     }
  15. }

105，从前序与中序遍历构造二叉树

难度中等1489

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  18.           HashMap<Integer,Integer> map=new HashMap<>();
  19.           for(int i=0;i<inorder.length;i++){
  20.               map.put(inorder[i],i);
  21.           }  
  22.           return creatTree(0,preorder.length-1,0,inorder.length-1,preorder,inorder,map);
  23.     }
  24.     TreeNode creatTree(int preorder_l,int preorder_r,int inorder_l,int inorder_r,int[] preorder,int inorder[], HashMap<Integer,Integer> map)
  25.     {
  26.         if(inorder_l>inorder_r)return null;
  27.         //根
  28.         TreeNode root=new TreeNode(preorder[preorder_l]);
  29.  
  30.         // 获取中序遍历中根的下标
  31.         int root_index=map.get(preorder[preorder_l]);
  32.  
  33.         // 左子树的长度
  34.         int left_len=root_index-inorder_l;
  35.  
  36.         root.left=creatTree(preorder_l+1,preorder_l+left_len,inorder_l,root_index-1,preorder,inorder, map);
  37.         root.right=creatTree(preorder_l+left_len+1,preorder_r,root_index+1,inorder_r,preorder,inorder, map);
  38.  
  39.         return root;
  40.     }
  41. }

114，二叉树展开为链表

难度中等1104

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。
  1. class Solution {
  2.     ArrayList<TreeNode> temp=new ArrayList<>();
  3.     public void flatten(TreeNode root) {
  4.         if(root==null)return;
  5.         preorder(root);
  6.         TreeNode tail=temp.get(0);
  7.         for(int i=1;i<temp.size();i++){
  8.             tail.left=null;
  9.             tail.right=temp.get(i);
  10.             tail=temp.get(i);
  11.         }
  12.         tail.left=null;
  13.         tail.right=null;
  14.     }
  15.     void preorder(TreeNode root){
  16.         if(root==null)return;
  17.  
  18.         temp.add(root);
  19.  
  20.         preorder(root.left);
  21.  
  22.         preorder(root.right);
  23.     }
  24. }

121，买卖股票的最佳时机（单调栈）

难度简单2208

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路：

  1. 单调栈
  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         Stack<Integer> s=new Stack<>();
  4.         int min=10001;
  5.         int res=0;
  6.         for(int i:prices){
  7.             if(s.isEmpty()){
  8.                 s.push(i);
  9.                 min=i;
  10.             }else{
  11.                 while(!s.isEmpty()&&s.peek()>=i){
  12.                     s.pop();
  13.                 }
  14.                 s.push(i);
  15.                 // 更新min
  16.                 if(s.size()==1){
  17.                     min=i;
  18.                 }
  19.             }
  20.             res=Integer.max(res,i-min);
  21.         }
  22.         return res;
  23.     }
  24. }

128，最长连续序列

难度中等1163

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

  1. // 考虑时间复杂度为o(n)，不考虑空间复杂度
  2. class Solution {
  3.     public int longestConsecutive(int[] nums) {
  4.         int len=nums.length;
  5.         if(len==0)return 0;
  6.         HashSet<Integer> myset=new HashSet<>();
  7.         for(int i=0;i<len;i++)
  8.             myset.add(nums[i]);
  9.         int res=1;
  10.         for(Integer i:myset)
  11.         {
  12.             if(!myset.contains(i-1)) {
  13.                 int tep = i;
  14.                 int cv = 0;
  15.                 while (myset.contains(tep)) {
  16.                     tep++;
  17.                     cv++;
  18.                 }
  19.                 res = Integer.max(res, cv);
  20.             }
  21.         }
  22.         return res;
  23.     }
  24. }
  1. class Solution {
  2.     public int longestConsecutive(int[] nums) {
  3.         Arrays.sort(nums);
  4.         int len=0;
  5.         int last=0;
  6.         int res=0;
  7.         for(int i:nums){
  8.             if(len==0){
  9.                 len++;
  10.                 last=i;
  11.             }else{
  12.                 if(last+1==i){
  13.                     len++;
  14.                 }else if(last==i){
  15.                     
  16.                 }else{
  17.                     len=1;
  18.                 }
  19.                 last=i;
  20.             }
  21.             res=Integer.max(res,len);
  22.         }
  23.         return res;
  24.     }
  25. }

136，只出现一次的数字（二进制）

难度简单2315

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int res=0;
  4.         for(int i:nums)res^=i;
  5.         return res;
  6.     }
  7. }

139，单词拆分（DP）

难度中等1485

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组

 思想：

  1. 采用dfs思想，在配合String.startsWith()进行判断，结果部分用例超时。
  2. 采用dp的思想去解决问题，因为s.length()不算太长，dp[i]表示长度为i的子串（下标为0-i-1）可以被表示出来，dp[i]=dp[j]&&s.substring(j,i)是否为能表示出来。
  1. class Solution {
  2.     public boolean wordBreak(String s, List<String> wordDict) {
  3.         Set<String> wordDictSet = new HashSet(wordDict);
  4.         boolean[] dp = new boolean[s.length() + 1];
  5.         // dp[i]表示以0-i-1的字符串能被字典表示
  6.         dp[0] = true;
  7.         for (int i = 1; i <= s.length(); i++) {// 长度
  8.             for (int j = 0; j < i; j++) {
  9.                 if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
  10.                     dp[i] = true;
  11.                     break;
  12.                 }
  13.             }
  14.         }
  15.         return dp[s.length()];
  16.     }
  17. }

141，环形链表

难度简单1414

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         if(head==null)return false;
  4.         ListNode p1=head;
  5.         ListNode p2=head;
  6.         while(p2!=null&&p1!=null){
  7.             
  8.  
  9.             p1=p1.next;
  10.             if(p1==null)return false;
  11.             p1=p1.next;
  12.  
  13.             p2=p2.next;
  14.  
  15.             if(p1==p2)return true;
  16.         }
  17.         return false;
  18.     }
  19. }

142，环形链表2

难度中等1464

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

 思路：

  1. set记录节点。
  2. 判圈法：女生走一步，男生走两步，直到相遇，在男生从初始点和女生从相遇点一步一步走就能找到环的入口。
  1. public class Solution {
  2.     public ListNode detectCycle(ListNode head) {
  3.        if(head==null)return null;
  4.        ListNode p1=head,p2=head;
  5.  
  6.        // 相遇点，一个走一步，一个走两步
  7.         while(p1!=null&&p2!=null){
  8.             p1=p1.next;
  9.             if(p1==null)return null;
  10.             p1=p1.next;
  11.  
  12.             p2=p2.next;
  13.  
  14.             if(p1==p2){
  15.                 break;
  16.             }
  17.         }
  18.         // 一个为空代表木环
  19.         if(p1==null||p2==null)return null;
  20.  
  21.         // 从头结点和相遇点一步一步走会在此相遇
  22.         while(head!=p1){
  23.             head=head.next;
  24.             p1=p1.next;
  25.         }
  26.         return head;
  27.  
  28.     }
  29. }
  1. public class Solution {
  2.     public ListNode detectCycle(ListNode head) {
  3.         HashSet<ListNode> set=new HashSet<>();
  4.         while(head!=null){
  5.             if(!set.contains(head)){
  6.                 set.add(head);
  7.             }else return head;
  8.             head=head.next;
  9.         }
  10.         return null;
  11.     }
  12. }

146，LRU缓存（linkedHashMap）

难度中等2031

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思想：

LinkedHashMap中存在removeEldestEntry（）方法就能自动开启LRU缓存功能，要写LinkedHashMap子类重写removeEldestEntry方法。

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

// 构造方法，accessOrder表示读取方式，false表示链表为插入顺序，true表示链表保持读取顺序。

  1. class LRUCache extends LinkedHashMap<Integer, Integer>{
  2.     private int capacity;
  3.     
  4.     public LRUCache(int capacity) {
  5.         super(capacity, 0.75F, true);
  6.         this.capacity = capacity;
  7.     }
  8.  
  9.     public int get(int key) {
  10.         return super.getOrDefault(key, -1);
  11.     }
  12.  
  13.     public void put(int key, int value) {
  14.         super.put(key, value);
  15.     }
  16.  
  17.     @Override
  18.     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  19.         return size() > capacity; 
  20.     }
  21. }

148，排序链表（排序）

难度中等1522

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

  1. class Solution {
  2.     public ListNode sortList(ListNode head) {
  3.         if(head==null||head.next==null)return head;
  4.         ArrayList<ListNode> c=new ArrayList<>();
  5.         while(head!=null){
  6.             c.add(head);
  7.             head=head.next;
  8.         }
  9.         Collections.sort(c,new Comparator<ListNode>(){
  10.             public int compare(ListNode o1,ListNode o2){
  11.                 return o1.val-o2.val;
  12.             }
  13.         });
  14.         ListNode res=new ListNode(-1),tail;
  15.         res.next=null;
  16.         tail=res;
  17.         for(int i=0;i<c.size();i++){
  18.             ListNode temp= c.get(i);
  19.             temp.next=null;
  20.             tail.next=temp;
  21.             tail=temp;
  22.         }
  23.         return res.next;
  24.     }
  25. }

152，乘积最大子数组（DP）

难度中等1562

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

  1. class Solution {
  2.     public int maxProduct(int[] nums) {
  3.         int dpmin[]=new int[nums.length];
  4.         int dpmax[]=new int[nums.length];
  5.         dpmax[0]=nums[0];
  6.         dpmin[0]=nums[0];
  7.         int res=nums[0];
  8.         for(int i=1;i<nums.length;i++){
  9.             dpmax[i]=Integer.max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i]);
  10.             dpmax[i]=Integer.max(dpmax[i],nums[i]);
  11.  
  12.             dpmin[i]=Integer.min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i]);
  13.             dpmin[i]=Integer.min(dpmin[i],nums[i]);
  14.  
  15.             res=Integer.max(res,dpmax[i]);
  16.         }
  17.         return res;
  18.     }
  19. }

 155，最小栈（priorityQueue）

难度简单1233

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。
  1. class MinStack {
  2.  
  3.     Stack<Integer> s=new Stack<>();
  4.     PriorityQueue<Integer> que=new PriorityQueue<>();
  5.  
  6.     public MinStack() {
  7.  
  8.     }
  9.     
  10.     public void push(int val) {
  11.         que.add(val);
  12.         s.push(val);
  13.     }
  14.     
  15.     public void pop() {
  16.         que.remove(s.peek());
  17.         s.pop();
  18.     }
  19.     
  20.     public int top() {
  21.         return s.peek();
  22.     }
  23.     
  24.     public int getMin() {
  25.         return que.peek();
  26.     }
  27. }
  28.  
  29. /**
  30.  * Your MinStack object will be instantiated and called as such:
  31.  * MinStack obj = new MinStack();
  32.  * obj.push(val);
  33.  * obj.pop();
  34.  * int param_3 = obj.top();
  35.  * int param_4 = obj.getMin();
  36.  */

160，相交链表

难度简单1611

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         int len1=0,len2=0;
  4.         ListNode h1=headA,h2=headB;
  5.         while(h1!=null){len1++;h1=h1.next;}
  6.         while(h2!=null){h2=h2.next;len2++;}
  7.  
  8.         if(len1<len2){
  9.            int flag=len2-len1;
  10.             while(flag!=0){
  11.                 headB=headB.next;
  12.                 flag--;
  13.             }
  14.         }else{
  15.              int flag=len1-len2;
  16.             while(flag!=0){
  17.                 headA=headA.next;
  18.                 flag--;
  19.             }
  20.         }
  21.         
  22.         while(headA!=null&&headB!=null){
  23.             if(headB==headA){
  24.                 return  headB;
  25.             }
  26.             headB=headB.next;
  27.             headA=headA.next;
  28.         }
  29.         
  30.         return null;
  31.     }
  32. }

 169，多数元素

难度简单1365

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

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

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         int val=0;
  4.         int len=0;
  5.         for(int i:nums){
  6.             if(len==0){
  7.                 len=1;
  8.                 val=i;
  9.             }else{
  10.                 if(val==i){
  11.                     len++;
  12.                 }else{
  13.                     len--;
  14.                 }
  15.             }
  16.         }
  17.         return val;
  18.     }
  19. }

198，打家劫舍（DP）

难度中等1983

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         int n=nums.length;
  4.         int [][]dp=new int[n][2];
  5.         dp[0][0]=0;//不偷
  6.         dp[0][1]=nums[0];//偷
  7.         for(int i=1;i<n;i++){
  8.             dp[i][0]=Integer.max(dp[i-1][1],dp[i-1][0]);
  9.             dp[i][1]=Integer.max(dp[i-1][1],dp[i-1][0]+nums[i]);
  10.         }
  11.         return Integer.max(dp[n-1][0],dp[n-1][1]);
  12.     }
  13. }

 200，岛屿数量（DFS）

难度中等1611

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

  1. class Solution {
  2.     private int res=0;
  3.     public int numIslands(char[][] grid) {
  4.         int m=grid.length, n=grid[0].length;
  5.         boolean [][]visited=new boolean[m][n];
  6.         for(int i=0;i<m;i++){
  7.             for(int j=0;j<n;j++){
  8.                 if(grid[i][j]=='1'&&!visited[i][j]){
  9.                     res++;
  10.                     visited[i][j]=true;
  11.                     dfs(i,j,m,n,visited,grid);
  12.                 }
  13.             }
  14.         }
  15.         return res;
  16.     }
  17.     void dfs(int x,int y,int m,int n,boolean [][]visited,char[][] grid){
  18.         for(int i=0;i<4;i++){
  19.             switch(i){
  20.                 case 0: 
  21.                     if(x-1>=0&&grid[x-1][y]=='1'&&!visited[x-1][y]){
  22.                         visited[x-1][y]=true;
  23.                         dfs(x-1,y,m,n,visited,grid);
  24.                     }
  25.                 break;
  26.                 case 1: 
  27.                     if(x+1<m&&grid[x+1][y]=='1'&&!visited[x+1][y]){
  28.                         visited[x+1][y]=true;
  29.                         dfs(x+1,y,m,n,visited,grid);
  30.                     }
  31.                 break;
  32.                 case 2:
  33.                     if(y-1>=0&&grid[x][y-1]=='1'&&!visited[x][y-1]){
  34.                         visited[x][y-1]=true;
  35.                         dfs(x,y-1,m,n,visited,grid);
  36.                     }
  37.                 break;
  38.                  case 3:
  39.                     if(y+1<n&&grid[x][y+1]=='1'&&!visited[x][y+1]){
  40.                         visited[x][y+1]=true;
  41.                         dfs(x,y+1,m,n,visited,grid);
  42.                     }
  43.                 break;
  44.             }
  45.         }
  46.     }
  47. }

 206，反转链表

难度简单2379

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         ListNode res=new ListNode(-1);
  4.         res.next=null;
  5.         while(head!=null){
  6.             ListNode t=head;
  7.             head=head.next;
  8.             t.next=res.next;
  9.             res.next=t;
  10.         }
  11.         return res.next;
  12.     }
  13. }

207，课程表（拓扑排序）

难度中等1177

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

思想：

  1. 拓扑排序，任务有先后，求出一种没有冲突的任务执行方式，将入度为0的结点加入队列，每次出队为key，将其余结点的入度为key的进行删除并且当一节点入度为0时候进行入队，当出队数等于总结点数则表明可以进行拓扑排序。
  1. class Solution {
  2.     List<List<Integer>> edges;
  3.     int[] indeg;
  4.  
  5.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  6.         edges = new ArrayList<List<Integer>>();
  7.         for (int i = 0; i < numCourses; ++i) {
  8.             edges.add(new ArrayList<Integer>());
  9.         }
  10.         indeg = new int[numCourses];
  11.         for (int[] info : prerequisites) {
  12.             edges.get(info[1]).add(info[0]);
  13.             ++indeg[info[0]];
  14.         }
  15.  
  16.         Queue<Integer> queue = new LinkedList<Integer>();
  17.         for (int i = 0; i < numCourses; ++i) {
  18.             if (indeg[i] == 0) {
  19.                 queue.offer(i);
  20.             }
  21.         }
  22.  
  23.         int visited = 0;
  24.         while (!queue.isEmpty()) {
  25.             ++visited;
  26.             int u = queue.poll();
  27.             for (int v: edges.get(u)) {
  28.                 --indeg[v];
  29.                 if (indeg[v] == 0) {
  30.                     queue.offer(v);
  31.                 }
  32.             }
  33.         }
  34.  
  35.         return visited == numCourses;
  36.     }
  37. }

208，实现trie前缀树

难度中等1115

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
  1. class Trie {
  2.  
  3.     private HashSet<String> set=new HashSet<>();
  4.     public Trie() {
  5.  
  6.     }
  7.     
  8.     public void insert(String word) {
  9.         set.add(word);
  10.     }
  11.     
  12.     public boolean search(String word) {
  13.         return set.contains(word);
  14.     }
  15.     
  16.     public boolean startsWith(String prefix) {
  17.         for(String s:set){
  18.             if(s.startsWith(prefix)){
  19.                 return true;
  20.             }
  21.         }
  22.         return false;
  23.     }
  24. }

215，数组中的第k个最大元素

难度中等1546

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

  1. class Solution {
  2.     PriorityQueue<Integer> q=new PriorityQueue<>();
  3.     public int findKthLargest(int[] nums, int k) {
  4.         for(int i:nums){
  5.             add(i,k);
  6.         }
  7.         return q.peek();
  8.     }
  9.     void add(int val,int k){
  10.         q.add(val);
  11.         if(q.size()>k){
  12.             q.poll();
  13.         }
  14.     }
  15. }

221，最大正方形

难度中等1081

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

  1. class Solution {
  2.     public int maximalSquare(char[][] matrix) {
  3.         int m=matrix.length,n=matrix[0].length;
  4.         int [][]dp=new int[m][n];
  5.         int res=0;
  6.         for(int i=0;i<m;i++){
  7.             dp[i][0]=matrix[i][0]-'0';
  8.             res=Integer.max(dp[i][0],res);
  9.         }
  10.         for(int i=0;i<n;i++)
  11.         {
  12.             dp[0][i]=matrix[0][i]-'0';
  13.             res=Integer.max(dp[0][i],res);
  14.         }
  15.         for(int i=1;i<m;i++){
  16.             for(int j=1;j<n;j++){
  17.                 if(matrix[i][j]=='1'){
  18.                     dp[i][j]=Integer.min(Integer.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
  19.                     res=Integer.max(dp[i][j],res);
  20.                 }
  21.             }
  22.         }
  23.         return res*res;
  24.     }
  25. }

226，翻转二叉树

难度简单1208

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         dfs(root);
  4.         return root;
  5.     }
  6.     void dfs(TreeNode root){
  7.         if(root==null)return;
  8.  
  9.         TreeNode t=root.left;
  10.         root.left=root.right;
  11.         root.right=t;
  12.  
  13.         dfs(root.left);
  14.         dfs(root.right);
  15.     }
  16. }

234，回文链表

难度简单1309

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

  1. class Solution {
  2.     public boolean isPalindrome(ListNode head) {
  3.         StringBuffer a=new StringBuffer();
  4.         while(head!=null){
  5.             a.append(String.valueOf(head.val));
  6.             head=head.next;
  7.         }
  8.         if(a.length()==1)return true;
  9.         String c=a.substring(0,a.length()/2);
  10.         String b=a.reverse().substring(0,a.length()/2);
  11.         
  12.         if(b.equals(c))return true;
  13.         return false;
  14.     }
  15. }

236，二叉树的最近公共祖先

难度中等1633

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

  1. class Solution {
  2.     private TreeNode res=null;
  3.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  4.         dfs(root,p,q);
  5.         return res;
  6.     }
  7.  
  8.     boolean dfs(TreeNode root,TreeNode p,TreeNode q){
  9.         if(root==null)return false;
  10.         boolean l=dfs(root.left,p,q);
  11.         boolean r=dfs(root.right,p,q);
  12.         if((l&&r)||((r||l)&&(root==p||root==q)))
  13.         {
  14.             res=root;
  15.             return true;
  16.         }
  17.         return l||r||(root==p)||(root==q);
  18.     }
  19. }

238，除自身以外组的乘积（两边记性标志-类似于接雨水）

难度中等1097

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

思路：

  1. 双向标记数组。
  1. class Solution {
  2.     public int[] productExceptSelf(int[] nums) {
  3.         int []f=new int[nums.length];
  4.         int []l=new int[nums.length];
  5.  
  6.         int cv=1;
  7.         for(int i=0;i<nums.length;i++){
  8.             cv*=nums[i];
  9.             f[i]=cv;
  10.         }
  11.          cv=1;
  12.         for(int i=nums.length-1;i>=0;i--){
  13.             cv*=nums[i];
  14.             l[i]=cv;
  15.         }
  16.         int res[]=new int[nums.length];
  17.         for(int i=0;i<nums.length;i++){
  18.             if(i==0){
  19.                 res[i]=l[1];
  20.             }else if(i==nums.length-1){
  21.                 res[i]=f[nums.length-2];
  22.             }else{
  23.                  res[i]=l[i+1]*f[i-1];
  24.             }
  25.         }
  26.         return res;
  27.     }
  28. }

240，搜索二维矩阵

难度中等962

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
  1. class Solution {
  2.     public boolean searchMatrix(int[][] matrix, int target) {
  3.         for(int i=0;i<matrix.length;i++){
  4.             if(Arrays.binarySearch(matrix[i],target)>=0){
  5.                 return true;
  6.             }
  7.         }
  8.         return false;
  9.     }
  10. }

279，完全平方数（DP）

难度中等1289

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

思路：

  1. 局部性原路。
  1. class Solution {
  2.     public int numSquares(int n) {
  3.        int []dp=new int[n+1];
  4.        // dp[i]表示数i需要表示为完全平方数之和的最小步数
  5.        Arrays.fill(dp,n+1);
  6.        dp[0]=0;
  7.        for(int i=1;i<=n;i++)
  8.        {
  9.            for(int j=1;j*j<=i;j++)
  10.            {
  11.                dp[i]=Math.min(dp[i],dp[i-j*j]+1);
  12.            }
  13.        }
  14.        return dp[n];
  15.     }
  16.  
  17. }

283，移动零

难度简单1501

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.        int zero=0;
  4.        ArrayList<Integer> arr=new ArrayList<>();
  5.        for(int i:nums){
  6.            if(i==0){
  7.                zero++;
  8.            }else{
  9.                arr.add(i);
  10.            }
  11.        }
  12.        int index=0;
  13.        for(;index<arr.size();index++){
  14.            nums[index]=arr.get(index);
  15.        }
  16.        for(int i=index;i<nums.length;i++){
  17.            nums[i]=0;
  18.        }
  19.     }
  20. }

287，寻找重复数

难度中等1641

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

思路：

  1. 因为数堵在[1,n]之间，我可以对nums[nums[i]%n]加n,遍历完一遍只要nums[i]>2*n的证明至少有两个相同的数存在了。
  1. class Solution {
  2.     public int findDuplicate(int[] nums) {
  3.         int n=nums.length-1;
  4.        for(int i=0;i<n+1;i++){
  5.            nums[nums[i]%n]=nums[nums[i]%n]+n;
  6.        }
  7.        for(int i=0;i<n+1;i++){
  8.            if(nums[i]>2*n){
  9.                return i==0?n:i;
  10.            }
  11.        }
  12.        return 1;
  13.     }
  14. }

300，最长递增子序列（DP）

难度中等2341

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         int n=nums.length;
  4.         int []dp=new int[n];
  5.         Arrays.fill(dp,1);
  6.         int res=1;
  7.         for(int i=1;i<n;i++){
  8.             for(int j=i-1;j>=0;j--){
  9.                 if(nums[i]>nums[j]){
  10.                     dp[i]=Integer.max(dp[i],dp[j]+1);
  11.                 }
  12.             }
  13.             res=Integer.max(res,dp[i]);
  14.         }
  15.         return res;
  16.     }
  17. }

301，删除无效的括号（DFS+剪枝）

难度困难689

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

  1. class Solution {
  2.     HashSet<String> res=new HashSet<>();
  3.     int step_MIN=Integer.MAX_VALUE;
  4.     public List<String> removeInvalidParentheses(String s) {
  5.        
  6.         dfs(0,0,0,0,"",s);
  7.         return new ArrayList<>(res);
  8.  
  9.     }
  10.     void dfs(int l,int r,int index,int step,String cv,String s){
  11.         if(index==s.length())
  12.         {
  13.             if(l==r){
  14.                 if(step<step_MIN){
  15.                     step_MIN=step;
  16.                     res.clear();
  17.                     res.add(new String(cv));
  18.                 }else if(step==step_MIN){
  19.                      res.add(new String(cv));
  20.                 }
  21.             }
  22.             return;
  23.         }
  24.         char flag=s.charAt(index);
  25.         if(flag=='('){
  26.             //可要可不要
  27.             dfs(l+1,r,index+1,step,cv+s.charAt(index),s); 
  28.             dfs(l,r,index+1,step+1,cv,s); 
  29.         }else if(flag==')'){
  30.             if(r+1<=l){
  31.                 //可要可不要
  32.                  dfs(l,r+1,index+1,step,cv+s.charAt(index),s);   
  33.             }
  34.             dfs(l,r,index+1,step+1,cv,s); 
  35.         }else{
  36.             dfs(l,r,index+1,step,cv+s.charAt(index),s);
  37.         }
  38.     }
  39. }

309，最佳买卖股票时机含冷冻期（DP问题）

难度中等1130

给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

思路：

本题的难点在于处理冷冻期，冷冻期是表示当天卖出后一天则不可以买入，关注点不是下一天是否可以买入，而是关注什么是否卖出（必须表示出来）。

一天有两种状态，持股和不持股（不持股也有两种状态，当天卖出不持股，当天没有股票不持股)dp[i][0] ：不持股（当天不卖出），dp[i][1]：持股， dp[i][2]：不持股（当天卖出）

转移方程：

dp[i][0]=max(dp[i-1][0],dp[i-1][2])

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-price[i])// 这里考虑到如果i-1卖出的话就不考虑，考虑了冷冻期

dp[i][2]=dp[i-1][1]+price[i]

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int n=prices.length;
  4.         if(n<=1) return 0;
  5.         int [][] dp=new int[n][3];
  6.         dp[0][0]=0;
  7.         dp[0][1]=-1*prices[0];
  8.         dp[0][2]=0;
  9.         for(int i=1;i<n;i++){//从[1]...[n-1]
  10.           dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]);
  11.             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
  12.             dp[i][2]=dp[i-1][1]+prices[i];
  13.  
  14.         }
  15.         return Math.max(dp[n-1][0],dp[n-1][2]);
  16.     }
  17. }

322，零钱兑换（DP-和单词拆分有着相同的思想）

难度中等1810

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int []dp=new int[amount+1];
  4.         Arrays.sort(coins);
  5.         Arrays.fill(dp,Integer.MAX_VALUE);
  6.         dp[0]=0;
  7.         for(int i=1;i<=amount;i++){
  8.             int cmin=Integer.MAX_VALUE;
  9.             for(int j=0;j<coins.length;j++){
  10.                 if(coins[j]>i){
  11.                     break;
  12.                 }
  13.                 if(dp[i-coins[j]]!=Integer.MAX_VALUE){
  14.                     cmin=Integer.min(cmin,dp[i-coins[j]]+1);
  15.                 }
  16.             }
  17.             dp[i]=cmin;
  18.         }
  19.         return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
  20.     }
  21. }

337，打家劫舍（DP+二叉树）

难度中等1204

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

思路：

  1. 存在子问题结构，f表示该点选择了最大价值，g表示该点不选择后的最大价值。
  1. class Solution {
  2.     Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
  3.     Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();
  4.  
  5.     public int rob(TreeNode root) {
  6.         dfs(root);
  7.         return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
  8.     }
  9.     // 后序遍历的思想+DP思想
  10.     public void dfs(TreeNode node) {
  11.         if (node == null) {
  12.             return;
  13.         }
  14.         dfs(node.left);
  15.         dfs(node.right);
  16.         f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
  17.         g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
  18.     }
  19. }
  20.

338，比特位计数

难度简单939

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

  1. class Solution {
  2.     public int[] countBits(int n) {
  3.         int res[]=new int[n+1];
  4.         for(int i=0;i<32;i++){
  5.             for(int j=1;j<=n;j++){
  6.                 if(((j>>i)&1)==1){
  7.                     res[j]++;
  8.                 }
  9.             }
  10.         }
  11.         return res;
  12.     }
  13. }

347，前k个高频元素

难度中等1077

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

  1. class Solution {
  2.     public int[] topKFrequent(int[] nums, int k) {
  3.  
  4.         HashMap<Integer,Integer> map=new HashMap<>();
  5.         for(int i:nums){
  6.             Integer t= map.get(i);
  7.             if(t==null){
  8.                 map.put(i,1);
  9.             }else{
  10.                 map.put(i,t+1);
  11.             }
  12.         }
  13.         int [][] val=new int[map.size()][2];
  14.         int index=0;
  15.         for(Map.Entry<Integer,Integer> entry:map.entrySet()){
  16.             val[index][0]=entry.getKey();
  17.             val[index][1]=entry.getValue();
  18.             index++;
  19.         }
  20.         Arrays.sort(val, new Comparator<int[]>() {
  21.             @Override
  22.             public int compare(int[] o1, int[] o2) {
  23.                 return o2[1]-o1[1];
  24.             }
  25.         });
  26.         int []res=new int[k];
  27.         for(int i=0;i<k;i++){
  28.             res[i]=val[i][0];
  29.         }
  30.         return res;
  31.     }
  32. }

394，字符串解码（栈）

难度中等1074

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

  1. class Solution {
  2.     public String decodeString(String s) {
  3.         Stack<Integer> n=new Stack<>();
  4.         Stack<Character> chars=new Stack<>();
  5.         String res="";
  6.         boolean last=false;
  7.         for(int i=0;i<s.length();i++){
  8.             if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
  9.                 if(last){
  10.                     int tt=n.peek();
  11.                     n.pop();
  12.                     n.push(tt*10+s.charAt(i)-'0');
  13.                 }else{
  14.                     n.push(s.charAt(i)-'0');
  15.                 }
  16.                 last=true;
  17.             }else if(s.charAt(i)==']'){
  18.                 last=false;
  19.                 // 进行出栈
  20.                 String t="";
  21.                 while(chars.peek()!='['){
  22.                     t=chars.peek()+t;
  23.                     chars.pop();
  24.                 }
  25.                 chars.pop();
  26.  
  27.                 if(chars.isEmpty()){
  28.                     //
  29.                     int flag=n.peek();
  30.                     n.pop();
  31.                     for(int j=0;j<flag;j++){
  32.                         res=res+t;
  33.                     }
  34.                 }else{
  35.                     int flag=n.peek();
  36.                     n.pop();
  37.                     String tep="";
  38.                     for(int j=0;j<flag;j++){
  39.                         tep=tep+t;
  40.                     }
  41.                     for(int j=0;j<tep.length();j++){
  42.                         chars.push(tep.charAt(j));
  43.                     }
  44.                 }
  45.  
  46.             }else{
  47.                 last=false;
  48.                 chars.push(s.charAt(i));
  49.             }
  50.         }
  51.         String temp="";
  52.         while(!chars.isEmpty()){
  53.             temp=chars.peek()+temp;
  54.             chars.pop();
  55.         }
  56.         return res+temp;
  57.     }
  58. }

437，路径总和三（先序遍历）

难度中等1276

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

  1. class Solution {
  2.     public int pathSum(TreeNode root, int targetSum) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.  
  7.         int ret = rootSum(root, targetSum);
  8.         ret += pathSum(root.left, targetSum);
  9.         ret += pathSum(root.right, targetSum);
  10.         return ret;
  11.     }
  12.  
  13.     public int rootSum(TreeNode root, int targetSum) {
  14.         int ret = 0;
  15.  
  16.         if (root == null) {
  17.             return 0;
  18.         }
  19.         int val = root.val;
  20.         if (val == targetSum) {
  21.             ret++;
  22.         } 
  23.  
  24.         ret += rootSum(root.left, targetSum - val);
  25.         ret += rootSum(root.right, targetSum - val);
  26.         return ret;
  27.     }
  28. }

438，找到字符串中所有字母异位词

难度中等820

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  3.         int []flag=new int[26];
  4.         for(int i=0;i<p.length();i++){
  5.             flag[p.charAt(i)-'a']++;
  6.         }
  7.         int []t=new int[26];
  8.         int len=p.length();
  9.         List<Integer> res=new ArrayList<>();
  10.         for(int i=0;i<s.length();i++){
  11.             t[s.charAt(i)-'a']++;
  12.             if(i>=len){
  13.                  t[s.charAt(i-len)-'a']--;
  14.             }
  15.             if(Arrays.equals(t,flag)){
  16.                 res.add(i-len+1);
  17.             }
  18.         }
  19.         // abcd
  20.         return res;
  21.     }
  22. }

448，找到所有数组中消失的数字

难度简单937

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

  1. class Solution {
  2.     public List<Integer> findDisappearedNumbers(int[] nums) {
  3.         for(int i=0,len=nums.length;i<len;i++){
  4.             nums[nums[i]%len]=nums[nums[i]%len]+len;
  5.         }
  6.         List<Integer> res=new ArrayList<>();
  7.         for(int i=0,len=nums.length;i<len;i++){
  8.             if(nums[i]<=len){
  9.                 if(i==0)
  10.                 res.add(len);
  11.                 else res.add(i);
  12.             }
  13.         }
  14.         return res;
  15.     }
  16. }

461，汉明距离

难度简单578

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

  1. class Solution {
  2.     public int hammingDistance(int x, int y) {
  3.         int res=0;
  4.         for(int i=0;i<32;i++){
  5.             if(((x>>i)&1^(y>>i)&1)==1){
  6.                 res++;
  7.             }
  8.         }
  9.         return res;
  10.     }
  11. }

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号