[数据结构与算法]Leetcode刷题题解（Java版）

前言

leetcode基础题题解，由易到难，持续更新。
附leetcode每题链接。

一、递归

70. 爬楼梯

70. 爬楼梯

class Solution {
    Map<Integer,Integer> hash = new HashMap<>(); //放前面算过的台阶
    int result = 0;
    
    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(hash.get(n) != null) return hash.get(n);//从hashmap拿值 
        else {
            int result = climbStairs(n - 1) + climbStairs(n - 2); //递归

            hash.put(n,result); //将值存入hashmap

            return result;
        } 
        
    }
}

……………………………………………………………………………………………

剑指 Offer 10- I. 斐波那契数列

剑指 Offer 10- I. 斐波那契数列

class Solution {

    Map<Integer,Integer> hash = new HashMap<>(); //注意List<Integer>
    public int fib(int n) {
        if(n == 0) return 0; // 判断用==
        if(n == 1) return 1;
        if(hash.get(n) != null) return hash.get(n);
        else{
            int result = (fib(n-1) + fib(n-2)) % 1000000007;
            hash.put(n,result);
            return result; 
        }
    }
}

…………………………………………………………………………

二、数组

1.两数之和

1.两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];  // 返回两个值，建数组
        // 建立k-v ，一一对应的哈希表
        Map<Integer,Integer> store = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(store.get(target - nums[i]) != null){  //if 后面{}别忘
                result[0] = i;
                result[1] = store.get(target-nums[i]);
                return result;
            }
            // 将数据存入 key为补数 ，value为下标
            else store.put(nums[i],i);
        }       
        return result;
    }
}

…………………………………………………………………………………………

88. 合并两个有序数组

88. 合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;  //p1,p2双指针，从后往前比大小，逆序排列
        int p2 = n - 1;
        int k = m + n - 1;  //新数组指针

        while(p1 >= 0 || p2 >= 0){  // 数组存在条件
            if(p1 < 0) nums1[k--] = nums2[p2--];  //数组1不存在，数组2进
            else if(p2 < 0) break;  //数组2不存在，打断结束
            else if(nums1[p1] < nums2[p2]) nums1[k--] = nums2[p2 --];
            //谁大谁进
            else nums1[k--] = nums1[p1--];
        }   
    }
}

………………………………………………………………………………………………

283. 移动零

283. 移动零

//双指针
//遍历一遍，p1指到非零项，赋值给p2
//此时非零项到前面，将p2后置零
class Solution {
    public void moveZeroes(int[] nums) {
        int p2 = 0;

        for(int p1 = 0; p1 < nums.length; p1 ++){
            if(nums[p1] != 0) nums[p2 ++] = nums[p1];  
            //遍历一遍，p1指到非零项，赋值给p2
        }

        for(int i = p2; i < nums.length; i ++){
            nums[i] = 0; //此时非零项到前面，将p2后置零
        }

    }
}

……………………………………………………………………………………

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

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

//K-1指V
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        
        for(int num : nums){  //遍历一遍，非零置反
            int index = Math.abs(num) - 1;
            if(nums[index] > 0) nums[index] = -nums[index];   
        }

        List<Integer> ret = new ArrayList<Integer>();  //非零加入表，找其对应值
        for(int i = 0; i < nums.length; i ++){
            if(nums[i] > 0) ret.add(i + 1);
        }

        return ret;

    }
}

…………………………………………………………………………………………

三、栈

四、队列

五、散列表