力扣解题汇总_JAVA

以下汇总都是高出题频率题
按照以下顺序刷题
先简单再中等
数学 > 数组 > 链表 > 字符串 > 哈希表 > 双指针 > 递归 > 栈 > 队列 > 树
刷了多轮后再刷
图与回溯算法 >贪心 >动态规划
练熟了之后不能再开智能模式刷题了,一些细节关注不到

数学_简单

13_罗马数字转整数

class Solution {Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{put('I', 1);put('V', 5);put('X', 10);put('L', 50);put('C', 100);put('D', 500);put('M', 1000);}};public int romanToInt(String s) {// I=1// IV=4// V=5// IX=9// X=10// XL=40// L=50// XC=90// C=100// CD=400// D=500// CM=900// M=1000int sum = 0;for(int i=0;i<s.length();i++){int value = symbolValues.get(s.charAt(i));//如果这个字符代表的数比后一个数大就+//反之则－if(i<s.length()-1 && value<symbolValues.get(s.charAt(i+1))){//这里用双&&,也保证当运行到第[s.length()-1]轮时,不执行&&后面的判断条件,就不会报错sum-=value;}else{sum+=value;}}return sum;}
}

66_ 加一

class Solution {public int[] plusOne(int[] digits) {for (int i = digits.length - 1; i >= 0; i--) {if (digits[i] == 9) {digits[i] = 0;} else {digits[i] += 1;return digits;}}//如果所有位都是进位，则长度+1digits= new int[digits.length + 1];digits[0] = 1;return digits;}
}
//千万不要想着将数组变为整数再计算,太麻烦

9_回文数

class Solution {//暴力解法public boolean isPalindrome(int x) {String reversedStr = (new StringBuilder(x+"")).reverse().toString();//StringBuilder是创建了一个StringBuilder对象,但是要转成string对象要toString()return (x+"").equals(reversedStr);//return (x+"")==reversedStr;不能这么比,因为这样比的是地址值}
}

class Solution {// 数学解法public boolean isPalindrome(int x) {//如何是负数不可能是回文//末位是0不可能是回文,除非X=0if (x < 0 || x % 10 == 0 && x != 0) {return false;}//让x代表前半段,reversex代表后半段//以上判断末位0正好除去了这里无法实现的翻转情况int reversex = 0;while (x > reversex) {reversex = reversex * 10 + x % 10;x = x / 10;}return reversex == x || reversex / 10 == x;//两种情况,位数为偶数和奇数}
}

70_爬楼梯

class Solution {public int climbStairs(int n) {//首先本题观察数学规律可知是斐波那契数列,但那逼公式谁记得//用另一种方法//爬到n-1层时,还有一节就到了//爬到n-2层时.还有两节就到了//所以methodNum[n]=method[n-1]+method[n-2]int[] methodNum = new int[n+1];methodNum[0] = 1;methodNum[1] = 1;for (int i = 2; i < methodNum.length; i++) {methodNum[i] = methodNum[i-1]+methodNum[i-2];}return methodNum[n];}
}

69_x的平方根

class Solution {public int mySqrt(int x) {// 非负整数// 二分查找,直到逼近满足k**2<=x的最大kint l = 0, r = x, ans = -1;while (l <= r) {int mid = (r + l) / 2;if ((long) mid * mid <= x) {ans = mid;l = mid + 1;}else {r = mid - 1;}}return ans;}
}

509_斐波那契数列

class Solution {public int fib(int n) {int[] F = new int[n+1];F[0] = 0;if(n>0){F[1]=1;}for (int i = 2; i < F.length; i++) {F[i] = F[i-1]+F[i-2];}return F[n];}
}

2235_两整数相加

class Solution {public int sum(int num1, int num2) {return num1+num2;}
}

67_二进制求和

class Solution {public String addBinary(String a, String b) {//StringBuffer是可变的字符串类,String 是不可变的对象StringBuffer ans = new StringBuffer();//取两个字符串中最大长度的字符串的长度//carry为计算记录,可算出当前位值和进位值int n = Math.max(a.length(), b.length()), carry = 0;for (int i = 0; i < n; ++i) {//比如'1'-'0',两个字符串相减就是ascii码整数差值//从末尾位向前计算//当超过较短字符串长度的位计算,补零计算carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;//添加本位的计算结果ans.append((char) (carry % 2 + '0'));//记录进位值,可能为0,可能为1carry /= 2;}//最后的进位还是1,再进位if (carry > 0) {ans.append('1');}//翻转过来,因为计算是先低位再高位,但是显示应该是先高位再低位ans.reverse();//返回值要返回字符串类型return ans.toString();}
}

415_字符串相加

//思路与二进制求和相同
class Solution {public String addStrings(String num1, String num2) {StringBuffer ans = new StringBuffer();int carry = 0;int maxLen = Math.max(num1.length(),num2.length());for (int i = 0; i < maxLen; i++) {carry+=i<num1.length() ? num1.charAt(num1.length()-1-i)-'0':0;carry+=i<num2.length() ? num2.charAt(num2.length()-1-i)-'0':0;ans.append(carry%10);carry /=10;}if(carry!=0){ans.append(carry);}ans.reverse();return ans.toString();}
}

2413_最小偶倍数

class Solution {public int smallestEvenMultiple(int n) {if(n%2==0){return n;}else{return 2*n;}}
}

2469_温度转换

class Solution {public double[] convertTemperature(double celsius) {double[] ans = new double[2];ans[0] = celsius+273.15;ans[1] = celsius*1.80+32.00;return ans;}
}

704_二分查找(重点)

class Solution {public int search(int[] nums, int target) {Integer l = 0;Integer r = nums.length-1;while(l<=r){Integer mid = (l+r)/2;if(nums[(l+r)/2]>target){//新的右边界一定要是mid-1//边界的更新一定要精确,需要思考最后的极端情况//如果不精确,最后就无法收敛到目标值//或者无法因为数组中不包含目标值,而不能跳出l<=r的满足条件,不精确将一直满足l<=rr = mid-1;}else if(nums[(l+r)/2]<target){//新的左边界一定要是mid+1l = mid+1;}else{return mid;}}return -1;}
}

数组_简单

1_两数之和

class Solution {public int[] twoSum(int[] nums, int target) {//建立一个哈希表,存放数值(key)和下标(value)//使用Map接口作为类型相比使用HashMap更加灵活Map<Integer,Integer> hashtable = new HashMap<Integer,Integer>();for (int i = 0; i < nums.length; i++) {//每次与哈希中比对,保证不重复利用一个数值,因为此数值还没存放到表中if(hashtable.containsKey(target-nums[i])){return new int[]{hashtable.get(target-nums[i]),i};}//没有满足的配对,再将此值放入哈希表中hashtable.put(nums[i], i);}return null;}
}

88_合并两个有序数组

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {//逆双指针int p1 = m-1,p2 = n-1; for (int i = 0; i < nums1.length; i++) {//从后面向nums1中插入值,不会覆盖nums1含值的位置if(p1>=0&&p2>=0){if(nums1[p1]>nums2[p2]){//nums1的含值尾值大,插入num1的尾部nums1[nums1.length-1-i] =  nums1[p1--];}else{//nums2的含值尾值大,插入num1的尾部nums1[nums1.length-1-i] = nums2[p2--];}}else if(p1<0){nums1[nums1.length-1-i] = nums2[p2--];}else if(p1>0){nums1[nums1.length-1-i] = nums1[p1--];}}return;}
}

链表_简单

21_合并两个有序链表

/*** Definition for singly-linked list.* 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 mergeTwoLists(ListNode list1, ListNode list2) {ListNode prehead = new ListNode(-1);ListNode prev = prehead;//此时 prehead和prev只是同一个节点的不同声明,不要将prehead和prev当作两个节点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;}prev.next = list1 == null?list2:list1;return prehead.next;}
}

203_移除链表元素

/*** Definition for singly-linked list.* 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 removeElements(ListNode head, int val) {ListNode newhead = head;ListNode ptr = newhead;while (ptr!=null) {if(newhead.val == val && ptr == newhead){//这是我自己的解法,但是其实官方迭代的思路是在head节点之前//链接一个newhead.next = head,就简单多了,不用嵌套的逻辑了newhead = newhead.next;ptr = newhead;}else{while(ptr.next !=null && ptr.next.val == val){ptr.next = ptr.next.next;}ptr = ptr.next;}}return newhead;}
}

字符串_简单

125_验证回文串

解1

class Solution {public boolean isPalindrome(String s) {//先去除除了字母和数字的特殊字符.放入sgood//将sgood和sgood.reverse对比,相等则回文StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if(Character.isLetterOrDigit(ch)){sgood.append(Character.toLowerCase(ch));}}StringBuffer reverse = new StringBuffer(sgood).reverse();return sgood.toString().equals(reverse.toString());}
}

解2

class Solution {public boolean isPalindrome(String s) {//在原字符串上比对//Time O(n),space O(1)int l = 0;int r = s.length()-1;while(l<r){while(l<r && !Character.isLetterOrDigit(s.charAt(l))){l++;}while(l<r && !Character.isLetterOrDigit(s.charAt(r))){r--;}if(l<r&&Character.toLowerCase(s.charAt(l))!=Character.toLowerCase(s.charAt(r))){return false;}l++;r--;}return true;}
}

哈希表_简单

哈希表的作用

• 统计一系列成员的数量

169_多数元素

import java.util.Map.Entry;
class Solution {public int majorityElement(int[] nums) {//集合只支持放引用数据类型HashMap<Integer,Integer> hashMap = new HashMap<>();for (Integer i = 0; i < nums.length; i++) {Integer num = nums[i];if(!hashMap.containsKey(num)){hashMap.put(num, 1);}else{Integer count = hashMap.get(num);count++;hashMap.put(num, count);}}Integer maxCount = 0;Integer maxValue = null;for (Entry<Integer,Integer> entrySet : hashMap.entrySet()) {if(maxCount < entrySet.getValue()){maxCount = entrySet.getValue();maxValue = entrySet.getKey();}}return maxValue;}
}

242_有效的字母异位词

class Solution {public boolean isAnagram(String s, String t) {HashMap<Character,Integer> sHashMap = new HashMap<>();HashMap<Character,Integer> tHashMap = new HashMap<>();Character sCh;Character tCh;//我这里理解起来比较容易//官方只用了一个hashmap,比较优雅//注意,HashMap的泛型是Character也不严谨,并不完全适用于unicode//Character只存占两字节的字符,而unicode有超过100000个不同的字符//远超65535个,官方也是Character,我觉得也不严谨//所以最正确的方法应该是先强转成Integer型(4字节)再存入hashmapif(s.length()!=t.length()){return false;}for (int i = 0; i < s.length(); i++) {sCh = s.charAt(i);if(!sHashMap.containsKey(sCh)){sHashMap.put(sCh, 1);}else{Integer count = sHashMap.get(sCh);sHashMap.put(sCh, count+1);}tCh = t.charAt(i);if(!tHashMap.containsKey(tCh)){tHashMap.put(tCh, 1);}else{Integer count = tHashMap.get(tCh);tHashMap.put(tCh, count+1);}}return sHashMap.equals(tHashMap);}
}

双指针_简单

28_找出字符串中第一个匹配项的下标

class Solution {public int strStr(String haystack, String needle) {//双指针//一个指针用来匹配//另一个指针如果在另一个指针匹配时,留在疑似匹配串的头部Integer head = 0;for (Integer idx = 0; idx < haystack.length(); ) {if(haystack.charAt(idx)==needle.charAt(idx-head)){if(idx-head+1 ==needle.length()){return head;}idx++;}else{head++;idx = head;}}return -1;}
}

344_反转字符串

class Solution {public void reverseString(char[] s) {Integer len= s.length;Integer i = 0;//意识不到数组的最后一个元素的索引是len-1也是老毛病了while(i<=(len/2-1)){Character temp = s[i];s[i] = s[len-1-i];s[len-1-i]=temp;i++;}}
}

递归_简单

206_反转链表

/*** Definition for singly-linked list.* 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 reverseList(ListNode head) {//递归思想//先用递归方法之前的程序,递归到最后一层(最后一个节点)//再用递归方法之后的程序翻转指针//为什么要加head==null的判断条件,//为什么head==null在前,head.next==null在后//因为如果链表为[],直接报错,触发空指针异常if(head==null||head.next==null){return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;//递归到最后一层的时候防止1<->2互相指,1<->2<-3<-4<-5return newHead; }
}

栈_简单

20_有效的括号

class Solution {public boolean isValid(String s) {//栈思想//栈的接口//Deque是双端队列,是接口,此接口实现了queue队列//LinkedList实现了deque双端队列接口//deque双端队列可以作为栈(push()/pop())或队列(offer()/poll())使用//pop(),从栈顶移除一个元素//peek(),查看栈顶元素//push(),放入栈顶//push和pop都是在队头添加和删除Deque<Character> deque = new LinkedList<>();//Deque为队列,可以作为栈使用for (int i = 0; i < s.length(); i++) {Character ch = s.charAt(i);//有左括号就在栈中放入对应的右括号if(ch == '('){deque.push(')');}else if (ch == '[') {deque.push(']');}else if (ch == '{') {deque.push('}');}//没循环完,且左括号就遍历完,就为空说明有余下的右括号//匹配不上也falseelse if(deque.isEmpty()||deque.peek()!=ch){return false;}else{deque.pop();}}// 完美匹配上,栈应该为空return deque.isEmpty();}
}

232. 用栈实现队列

class MyQueue {Deque<Integer> inStack;Deque<Integer> outStack;//两个栈,一个作为入队列,一个作为出队列public MyQueue() {inStack = new LinkedList<>();outStack = new LinkedList<>();}public void push(int x) {inStack.push(x);}public int pop() {//在出队列的时候才将inStack的数据移到outStack,如果在入队列的时候,每一次移动时间复杂度都将是O(n)//只有outStack为空,才能将inStack移到outStack,不然inStack的新数据将把outStack中的旧数据压到栈底while(outStack.isEmpty()){//移动直到inStack为空while(!inStack.isEmpty()){outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {//与pop()操作同理while(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {if(inStack.isEmpty() && outStack.isEmpty()){return true;}return false;}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

队列_简单

225_用队列实现栈

class MyStack {//LinkedList是类,LinkedList中实现了deque接口//Queue队列是一个接口,deque双端队列中实现了queue接口Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}public void push(int x) {queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

树_简单

104_二叉树的最大深度

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int maxDepth(TreeNode root) {//递归思想if(root == null){return 0;}else{int lDepth = maxDepth(root.left);int rDepth = maxDepth(root.right);return Math.max(lDepth,rDepth) + 1;}}
}

144_二叉树的前序遍历

import com.sun.source.tree.Tree;/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root != null){list.add(root.val);if(root.left != null){List<Integer> left = preorderTraversal(root.left);list.addAll(left);}if(root.right != null){List<Integer> right = preorderTraversal(root.right);list.addAll(right);}}return list;}
}