滑动窗口

219. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

// 滑动窗口做法

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        
        
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;

    }
}

// 我的做法 效率>98%

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer>map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                int val = map.get(nums[i]);
                if(Math.abs(val - i) <= k){
                    return true;
                }
            }
           
            map.put(nums[i], i);
            
        }
        return false;
    }
}

220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

官方解答：
x是nums[]里面的一个元素。 |x+y| <= t 那么只要满足 x - t <= y <= x + t所以给定一个区间[x-t, x+t]
然后因为还要满足 |i - j|下标 <= k那么我们使用一个滑动窗口（也就是一个队列，他的长度是k）
我们只需要找到 set集合中最接近abs(x-t)的那个值然后让其 <= x +t即可
如果size()>k移出首个元素，保证在集合set内的元素下标都满足k的要求

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        // 使用long类型防止超界
        TreeSet<Long>set = new TreeSet<>();
        for(int i = 0; i < n; i++){
            // set.ceiling(key)寻找比比key大而且最接近key的值
            // 如果set中不存在的话，就返回null
            Long ceiling = set.ceiling((long)nums[i] - (long)t);// nums[i] - t
            if(ceiling != null && ceiling <= ((long)nums[i] + (long)t)){
                return true;// nums[i] + t
            }
            set.add((long)nums[i]);
            if(set.size() > k){
                set.remove((long)nums[i - k]);// set集合的大小超过了k就移出第一个元素
            }
        }
        return false;
    }
}

双指针

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

// Leecode大神的做法： 好像效率比下面的低一些

class Solution {
    public String reverseWords(String s) {
        
       
        // 先去除掉头尾空格
        s = s.trim();
        int n = s.length();
        int i = n - 1, j = n - 1;// 两个指针从后面向前遍历
        StringBuilder sb = new StringBuilder();
        while(i >= 0){
            // 遇见不是空格就向前移动
            while(i >= 0 && s.charAt(i) != ' '){
                i--;
            }

            sb.append(s.substring(i + 1, j + 1)).append(" ");

            // 跳过空格
            while(i >= 0 && s.charAt(i) == ' '){
                i--;
            }
            j = i;
        }
        return sb.toString().trim();
    }
}

// 我的做法：切分+拼接

class Solution {
    public String reverseWords(String s) {
        
        String[] str = s.split(" ");
        StringBuilder sb = new StringBuilder();
        // System.out.println(Arrays.toString(str));
        for(int i = str.length - 1; i >= 0; i--){
            if("".equals(str[i])){
                continue;
            }
            else{
                sb.append(str[i]).append(" ");
            }
        }
        // 删除掉最后一个元素 空格
        if(sb.length() > 0){
            return sb.deleteCharAt(sb.length() - 1).toString();
        }
        else{
            // 如果是空串 或者全部都是空格
            return "";
        }
        
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

class Solution {
    public int missingNumber(int[] nums) {

        // 主要就是看下标和元素值是否对应
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == i){
                continue;
            }
            else{
                return i;
            }
        }
        return nums.length;
    }
}

动态规划

剑指 Offer 47. 礼物的最大价值

在一个 m * n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

// 只能向下移动或者向左移动

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // dp[i][j]表示到达第grid[i][j]这个位置时候可以获得的礼物最大价值
        // dp[i][j] = Math.max(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j])分别对应右移和下移
        // 所以最后返回的值是 dp[m - 1][n - 1]
        int[][] dp = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 && j == 0){
                    dp[0][0] = grid[0][0];
                }
                else if(i == 0 && j > 0){
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }
                else if(i > 0 && j == 0){
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                }
                else{
                    dp[i][j] = Math.max(
                        dp[i - 1][j] + grid[i][j],
                        dp[i][j - 1] + grid[i][j]
                    );
                }
                
            }
        }
        return dp[m - 1][n - 1];

    }
}