「常见解法总结」

import java.util.HashMap;

HashMap<String,Object> hashMap = new HashMap<>();
Map<String,Object> hashMap = new HashMap<>();

import java.util.HashMap;

public class Test {
    public static void main(String[] args) {
        // 创建 HashMap 对象 Sites
        HashMap<Integer, String> Sites = new HashMap<Integer, String>();
        // 1、添加键值对
        Sites.put(1, "Google");
        Sites.put(2, "Runoob");
        Sites.put(3, "Taobao");
        Sites.put(4, "Zhihu");
        // 2、使用 get(key) 方法来获取 key 对应的 value
        System.out.println(Sites.get(3));
        // 3、使用 remove(key) 方法来删除 key 对应的键值对
        Sites.remove(4);
        // 4、使用 size()方法计算元素数量
        System.out.println(Sites.size());
        // 5、keySet() 方法获取所有key，values() 方法获取所有value
        // 6、isEmpty() 方法用于检查该 HashMap 是否为空
        // 7、containsKey() 方法检查 hashMap 中是否存在指定的 key 对应的映射关系
        if(sites.containsKey(1)) {
            System.out.println("key 为 1 存在于 sites 中");
        }
        // 8、replace() 方法替换 hashMap 中是指定的 key 对应的 value
        sites.replace(1, "Google", "Wiki");
        // 9、getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
        String value1 = sites.getOrDefault(1, "Not Found");
    }
}

HashSet的基本使用

import java.util.HashSet;

public class Test {
    public static void main(String[] args) {
        HashSet<String> sites = new HashSet<String>();
        // 1、使用 add() 方法添加元素
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");  // 重复的元素不会被添加
        System.out.println(sites);
        // 2、使用 contains() 方法来判断元素是否存在于集合当中
        System.out.println(sites.contains("Taobao"));
        // 3、使用 remove() 方法来删除集合中的元素，成功返回 true，否则为 false
        sites.remove("Taobao");
        // 4、使用size() 方法计算元素数量
        System.out.println(sites.size());
        // 5、使用for-each迭代元素
        for (String i : sites) {
            System.out.println(i);
        }
    }
}

2「字符串常用方法」

String类

• toCharArray()：将字符串转换为字符数组，如char[] ch = str.toCharArray();
• charAt(index)：获得字符串中指定索引的字符，index从0开始
• substring(int beginIndex, int endIndex)：返回从beginIndex（从0开始）到endIndex（不包括）的子字符串
• valueOf(char[] data)：返回 char数组的字符串表示形式
• valueOf(char[] data,int offset, int count)：返回 char 数组参数的特定子数组的字符串表示形式。
• valueOf(int i)：返回 int 参数的字符串表示形式。
• indexOf(int ch)：返回指定字符在此字符串中第一次出现的索引
• indexOf(int ch, int fromindex)： 同上， 从指定索引开始搜索
• indexOf(String str)：返回子串在此字符串中第一次出现的索引
• indexOf(String str, int fromindex)：同上，从指定索引开始搜索
• length()：返回字符串的长度
• 比较：== ， != 判断的是两个字符串地址是否相等，equals()方法是直接比较两个字符串对象的内容，相等返回 true，否则返回false，如str1.equals(str2)

StringBuffer类和StringBuilder类

Ø  public StringBuffer append(String s)：将指定的字符串追加到此字符序列。

Ø  public StringBuffer reverse()：将此字符序列用其反转形式取代

Ø  delete(int start, int end)：移除此序列从start到end-1的字符串

Ø  int capacity()：返回当前容量。

Ø  int length()：返回长度（字符数）

3「双指针法」

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

快慢指针

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode p1 = head; //慢指针
        ListNode p2 = head; //快指针，两个指针从同一节点出发
        while(p2 != null && p2.next != null){
            p1 = p1.next; //慢指针每次移动一位
            p2 = p2.next.next; //快指针每次移动两位
            if(p1 == p2){ //相遇则说明有环
                return true;
            }
        }
        return false;
    }
}

ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null){//快慢指针求中点
    fast = fast.next.next;
    slow = slow.next;
}

对撞指针

滑动窗口

1. 初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」
2. 先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的元素符合条件（相当于在寻找一个可行解）
3. 停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的元素不再符合要求。同时，每次增加 left，都更新一轮结果（优化这个可行解，最终找到最优解）
   

例题1：LC 209. 长度最小的子数组

题目地址：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min  = nums.length+1;
        int left = 0;
        int right = 0;
        int sum = 0;
        while(right < nums.length){
            //移动右指针，累加元素值，寻找满足条件的区间
            sum += nums[right];
            while(sum >= target){
                //找到满足条件的区间，就移动左指针，减去left所指值，寻找满足条件的最小区间
                min = Math.min(min, right-left+1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        //不存在符合条件的子数组就返回0
        return min == nums.length+1 ? 0 : min;
    }
}

例题2：LC 3. 无重复字符的最长子串

题目地址：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i++){
            //移动右指针扩大窗口，当遇到出现过的字符时，取出该重复字符的下标加一与left比较取最大值赋给left
            //其实就是将left移动到重复字符的后面，因为该位置的字符重复了，需要将其前面的字符都移出窗口
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            //不存在就插入，已存在的会替换为新的value值
            map.put(s.charAt(i), i);
            //更新当前的最长子串
            max = Math.max(max, i-left+1);
        }
        return max;
    }
}

4「分治」

分治算法可以分三步走：分解 -> 解决(触底) -> 合并(回溯)

1. 分解原问题为结构相同的子问题。
2. 分解到某个容易求解的边界之后，进行递归求解。
3. 将子问题的解合并成原问题的解。

• 快速排序
• 归并排序
  

5「二分法」

参考资料：【1】二分法（一）：二分法的基本思想  【2】 [学习笔记]二分与分治

6「中心扩散法」

7「KMP算法」