力扣解题汇总_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=1000
        int 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;
            }

        }
        //如果所有位都是进位，则长度+1
        digits= 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=0
        if (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的最大k
        int 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,可能为1
            carry /= 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<=r
                r = mid-1;
            }
            else if(nums[(l+r)/2]<target){
                //新的左边界一定要是mid+1
                l = 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字节)再存入hashmap
        if(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<-5
        return 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('}');
            }
            //没循环完,且左括号就遍历完,就为空说明有余下的右括号
            //匹配不上也false
            else 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;
    }
}