算法：从入门到变通

哈希

用法

哈希利用空间换取时间，可以快速地统计序列中某个元素出现的次数

示例

题目

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组好数对 。

返回好数对的数目。

解法：创建哈希表并记录

//Java
class Solution {
    public int numIdenticalPairs(int[] nums) {
        int[] hash=new int[101];
        int ans=0;
        for(int i=0;i<hash.length;i++){
            hash[i]=0;
        }
        for(int i=0;i<nums.length;i++){
            hash[ nums[i] ]++;
        }
        for(int i=0;i<hash.length;i++){
            ans += ( hash[i] * (hash[i]-1) ) / 2;
        }
        return ans;
    }
}

滑动窗口

用法

滑动窗口用于快速的对序列进行遍历找出符合要求的子序列

示例

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解法：创建start、end指针进行遍历

//Java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        } 
        int ans=Integer.MAX_VALUE;
        int start=0,end=0;
        int sum=0;
        while(end < n){
            sum+=nums[end];
            while(sum >= target){
                ans=Math.min(ans,end-start+1);
                sum-=nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

动态规划

用法

用于将复杂不直观可解的问题转化为求其子问题的解

示例

题目

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

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

求解DP问题的四个步骤：

1. 定义子问题
2. 写出子问题的递推关系
3. 确定 DP 数组的计算顺序
4. 空间优化

解法：分解子问题

//Java
lass Solution {
    public int rob(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        // 子问题：
        // f(k) = 偷 [0..k) 房间中的最大金额
        // f(0) = 0
        // f(1) = nums[0]
        // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }
        int[] dp=new int[nums.length+1];
        dp[0]=0;
        dp[1]=nums[0];
        for(int k=2;k<=nums.length;k++){
            dp[k]=Math.max(dp[k-1],nums[k-1]+dp[k-2]);
        }
        return dp[nums.length];
    }
}

进阶：空间优化

二分查找

用法

从小到大学的不停二分缩小范围，判断目标区域

示例

题目

整数数组 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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解法：界定左右边界，二分

//Java
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 0){
            return -1;
        }
        if(n == 1){
            return nums[0] == target ? 0 : -1;
        }
        int l = 0 , r = n-1;
        while(l <= r){
            int mid = (l+r)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[0] <= nums[mid]){
                if(nums[0] <= target && target <nums[mid]){
                    r = mid - 1;
                }else{
                    l = mid + 1;
                }
            }else{
                if(nums[mid] < target && target <= nums[n-1]){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

贪心

用法

怎么贪婪怎么来

示例

题目

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

`解法：解法多种多样，关键是判断条件

//Java
//1
class Solution {
    public boolean canJump(int[] nums) {
        //初始化长度
        int tar=nums.length-1;
        for(int i=nums.length-2;i>=0;i--){
            if(i+nums[i] >= tar){
                tar = i;
            }
        }
        if(tar == 0) return true;
        else return false;
    }
}
//2
class Solution {
    public boolean canJump(int[] nums) {
        //初始化长度
        int ans=0,l=nums.length;
        for(int i=0;i<l;i++){
        	if(i<ans){
        		ans = Math.max{ans, i+nums[i]};
        		if(ans >= l-1){
        			return true;
        		}
        	}
        }
        return false;
    }
}