int left = 0, right = 0;

while (right < s.length()) {
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

/* 滑动窗口算法框架 */
public String slidingWindow(String s, String t) {
  
    // 需要的字符散列表 全部初始化为1(表示需要)
    char[] sArray = s.toCharArray();
    HashMap<Character, Integer> need = new HashMap<>();
    for (char key : sArray) {
      need.put(key, need.getOrDefault(key, 0) + 1);
    }
    HashMap<Character, Integer> window = new HashMap<>();// 用于记录「窗口」中的相应字符的出现次数

    int left = 0, right = 0;
    int valid = 0; // 表示窗口中满足need条件的字符个数
  	
    while (right < sArray.length) {
        // in 是将移入窗口的字符
        char in = sArray[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        System.out.println("window: [" + left + "," + right + "]\n");
        /********************/

        // 判断左侧窗口是否要收缩
        while (valid==need.size()) {
            // out 是将移出窗口的字符
            char out = sArray[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

// 快速排序
Random random = new Random();
public static void quickSort(int[] nums, int start, int end) {
  
  if(start>=end) return; // 只有一个元素时终止

  int left = start;
  int right = end;
  
  // 随机选择枢纽点
  int i =random.nextInt(end - start + 1)+start;
  int temp = nums[left];
  nums[left]=nums[i];
  nums[i]=temp;
  
  int pivot = nums[left]; // 枢纽点pivot选取第一个元素
  
  while (left < right) {
    // high指针往左寻找一个小于 pivot的数
    while (left<right&&nums[right]>=pivot) {
      right--;
    }
    nums[left]=nums[right]; // 将小于 pivot 的数放在低位

    // low指针往右寻找一个大于 pivot 的数
    while (left<right&&nums[left]<=pivot) {
      left++;
    }
    nums[right]=nums[left]; // 将大于 pivot 的数放在高位
  }
  // 复原 pivot的值
  nums[left] = pivot;
  quickSort(nums, start, left - 1); // 递归排序左半部分
  quickSort(nums, left + 1, end); // 递归排序右半部分
}

// 堆排序
public static void sort(int[] arr) {
  int length = arr.length;
  //构建堆
  buildHeap(arr, length);
  for ( int i = length - 1; i > 0; i-- ) {
    //将堆顶元素与末位元素调换
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    //数组长度-1 隐藏堆尾元素
    length--;
    //将堆顶元素下沉 目的是将最大的元素浮到堆顶来
    sink(arr, 0, length);
  }
}
private static void buildHeap(int[] arr, int length) {
  for (int i = length / 2; i >= 0; i--) {
    sink(arr, i, length);
  }
}

/**
 * 下沉调整
 * @param arr 数组
 * @param index 调整位置
 * @param length 数组范围
 */
private static void sink(int[] arr, int index, int length) {
  int leftChild = 2 * index + 1;//左子节点下标
  int rightChild = 2 * index + 2;//右子节点下标
  int present = index;//要调整的节点下标

  //下沉左边
  if (leftChild < length && arr[leftChild] > arr[present]) {
    present = leftChild;
  }

  //下沉右边
  if (rightChild < length && arr[rightChild] > arr[present]) {
    present = rightChild;
  }

  //如果下标不相等 证明调换过了
  if (present != index) {
    //交换值
    int temp = arr[index];
    arr[index] = arr[present];
    arr[present] = temp;

    //继续下沉
    sink(arr, present, length);
  }
}

int intervalSchedule(int[][] intvs) {}

public int  getResult(int[][] intvs){
  Arrays.sort(intvs,(a,b)->a[1]-b[1]);

  int count = 1;
  int xEnd = intvs[0][1];
  for (int[] intv : intvs) {
    int start = intv[0];
    if (start>=xEnd){
      count++;
      xEnd = intv[1];
    }
  }
  return count;
}

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

if(nums[mid] == target)
    return mid;

//...
while(left < right) {
    // ...
}
return nums[left] == target ? left : -1;

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意


    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 为什么不需要减1 因为搜索区间是[low,high)
        }
    }
    return left;
}

while (left < right) {
    //...
}
// target 比所有数都大
if (left == nums.length) return -1;
// 类似之前算法的处理方式
if (nums[left] != target) return -1;

    if (nums[mid] == target)
        right = mid;

int left_bound(int[] nums, int target) {
    // 搜索区间为 [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // if else ...
    }

if (nums[mid] < target) {
    // 搜索区间变为 [mid+1, right]
    left = mid + 1;
} else if (nums[mid] > target) {
    // 搜索区间变为 [left, mid-1]
    right = mid - 1;
} else if (nums[mid] == target) {
    // 收缩右侧边界
    right = mid - 1;
}

if (left >= nums.length || nums[left] != target)
    return -1;
return left;

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

if (nums[mid] == target) {
    left = mid + 1;

if (nums[mid] == target) {
    left = mid + 1;
    // 这样想: mid = left - 1

while (left < right) {
    // ...
}
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况，见下图
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid


因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界


又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}


int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}




int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

# 回溯模版
List<String> result = new ArrayList<String>();
public void backtrack(路径, 选择列表):
    if (满足结束条件): // 递归出口
        result.add(路径)
        return;

    for 选择 in 选择列表:
        // 做选择
        backtrack(路径, 选择列表)
        // 撤销选择

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    LinkedList<TreeNode> queue = new LinkedList<>(); // 核心数据结构
    Set<Node> visited; // 避免走回头路

    queue.offer(start); // offer是queue的插入方法，将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (!queue.isEmpty()) {
        int size = queue.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < size; i++) {
            Node cur = queue.poll(); // poll() 检索并删除此列表的头部（第一个元素）
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

// 自定义TreeNode节点
static class TreeNode {
  public int val;
  public TreeNode left;
  public TreeNode right;

  public TreeNode(int val) {
    this.val = val;
  }

  TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

public int lengthOfLongestSubstring(String s) {

  // window计数器
  HashMap<Character, Integer> window = new HashMap<>();

  int left = 0;int right = 0;
  int result = 0; // 记录结果

  char[] sArray = s.toCharArray();
  while (right < s.length()) {
    // right扩大
    Character c = sArray[right];
    right++;
    // 进行窗口内数据的一系列更新
    window.put(c, window.getOrDefault(c, 0) + 1);

    // 何时收缩？ 当前字符计数值大于1时收缩
    while (window.get(c) > 1) {
      Character d = sArray[left];
      left++;
      // 进行窗口内数据的一系列更新
      window.put(d, window.get(d) - 1);
    }

    // 收缩结束 已经没有重复字符(在这里更新答案)
    result = Math.max(result, right - left);
  }
  return result;
}

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

// 方法一：扩展中心
private String res = "";
public String longestPalindrome(String s) {
  for (int i = 0; i < s.length(); i++) {
    // 找到以 s[i] 为中心的回文串
    isPalindrome(s,i,i);
    // 找到以 s[i] 和 s[i+1] 为中心的回文串
    isPalindrome(s, i, i + 1);
  }
  return res;
}
// 寻找最长回文串函数
private void isPalindrome(String s, int left, int right) {
  // ⚠️ 防止索引越界(先扩展指针，如果不符合了再缩小左右边界防止索引越界)
  while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
    // 双向展开
    left--;
    right++;
  }
  // 更新res为s[left]和s[right]为中心的最长回文串
  if((right-1)-(left+1)+1>res.length()){ // 因为在while循环中多扩展了一次，计算长度时记得收回
    res = s.substring(left+1,right-1+1); // substring(int beginIndex, int endIndex),不包括endIndex
  }
}

// 方法二 动态规划
public String longestPalindrome(String s) {
  String res = "";
  boolean[][] dp = new boolean[s.length()][s.length()];
  // 注意遍历顺序
  for (int i= s.length() - 1; i >= 0; i--){  
    for (int j = i; j < s.length(); j++){
      if (s.charAt(i) == s.charAt(j)) {
        if (j - i < 2) { // case1 和 case2
          dp[i][j] = true;
          if(j-i+1>res.length()) res = s.substring(i,j+1);
        } else if (dp[i + 1][j - 1]) { // case3
          dp[i][j] = true;
          if(j-i+1>res.length()) res = s.substring(i,j+1);
        }
      }
    }
  }
  return res;
}

// 通过循环将数字 x 的每一位拆开，在计算新值的时候判断是否溢出
public int reverse(int x) {
  int ans = 0; // 当前计算结果
  while (x != 0) {
    int pop = x%10; // 下一位pop
    x = x/10;
    // int 的范围 -2147483648 - 2147483647 ， 所以判断7和-8
    if (ans > Integer.MAX_VALUE/10 || (ans == Integer.MAX_VALUE/10 && pop > 7)) 
      return 0;
    if (ans < Integer.MIN_VALUE/10 || (ans == Integer.MIN_VALUE/10 && pop < -8)) 
      return 0;
    ans = ans * 10 + pop;
  }
  return ans;
}

// 方法一
public boolean isPalindrome(int x) {
  if(x < 0) return false;
  int cur = 0;
  int num = x;
  while(num != 0) {
    cur = cur * 10 + num % 10;
    num /= 10;
  }
  return cur == x; //如果溢出了说明反转前后肯定不一样 那肯定不是回文数了
}

// 方法一优化版(实际上比较一半即可)
public boolean isPalindrome(int x) {
  // 排除一些特殊情况，负数、10的倍数(0除外)
  if (x < 0 || (x % 10 == 0 && x != 0))
    return false;
  int rev = 0;
  while (rev < x) {
    rev = x % 10 + rev * 10;
    x /= 10; //一半就是 /= 后剩的值大小
  }    
  return (rev == x || rev/10 == x);//长度为偶数时rev==x;奇数时候rev/10==x
}

// 方法二 
public boolean isPalindrome(int x) {

  String s = String.valueOf(x);
  int left = s.length()/2;
  int right = s.length()/2;
  if(s.length()%2==0){
    left = s.length()/2;
    right = s.length()/2-1;
  }
  while(left>=0&&right<s.length()){
    if(s.charAt(left)!=s.charAt(right)) return false;
    left--;
    right++;
  }
  return true;
}

class Solution {
    public int maxArea(int[] height) {
      	// 设置双指针 i,j 分别位于容器壁两端
        int i = 0, j = height.length - 1, res = 0;
      	// 每次向内移动短板，并且更新面积最大值 res，直到 i == j 时返回 res。
        while(i < j){
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]): 
                Math.max(res, (j - i) * height[j--]); 
        }
        return res;
    }
}

public ListNode removeNthFromEnd(ListNode head, int n) {
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  
  ListNode pre = dummy;
  ListNode slow = head;
  ListNode fast = head;
  while(n!=0){
    fast = fast.next;
    n--;
  }
  
  while(fast!=null){ // 再简单一点的话slow指针可以删掉,直接pre.next = pre.next.next
    pre = pre.next;
    slow = slow.next;
    fast = fast.next;
  }
  pre.next = slow.next;
  return dummy.next;
}

public boolean isValid(String s) {
  Map<Character, Character> map = new HashMap<Character, Character>();
  map.put('{', '}');
  map.put('[', ']');
  map.put('(', ')');
  map.put('?', '?');

  LinkedList<Character> stack = new LinkedList<Character>();
  stack.add('?');  
  
  for (Character c : s.toCharArray()) {
    if (map.containsKey(c)) {
      stack.push(c);
    }else if (map.get(stack.pop()) != c){
      return false;
    }
  }
  return stack.size() == 1; // s已左括号结尾也可以正常结束，但是stack会存在两个元素(?和左括号)。 
}

public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
  // 哨兵节点
  ListNode dummyHead = new ListNode(-1);
  ListNode cur = dummyHead;
  
  while(head1!=null&&head2!=null){
    if(head1.val<=head2.val){
      cur.next = head1;
      head1 = head1.next;
    }else{
      cur.next = head2;
      head2 = head2.next;
    }
    cur = cur.next;
  }
  cur.next = head1==null?head2:head1;
  return dummyHead.next;
}

# 回溯模版
List<String> result = new ArrayList<String>();
public void backtrack(路径, 选择列表):
    if (满足结束条件): // 递归出口
        result.add(路径)
        return;

    for 选择 in 选择列表:
        // 做选择
        backtrack(路径, 选择列表)
        // 撤销选择

private LinkedList<String> res = new LinkedList<>();
public List<String> generateParenthesis(int n) {
  int[] arr = new int[2]; // 描述当前括号的状态[左括号数量，右括号数量]
  StringBuilder list = new StringBuilder();
  backtrack(arr,list,n);
  return res;
}

private void backtrack(int[] arr, StringBuilder list,int max) {
  if (arr[0]<arr[1]){ // 剪枝 左括号数量一定要大于右括号
    return;
  }
  if (arr[0]==max&&arr[1]==max){
    res.add(list.toString());
    return;
  }

  // (
  if (arr[0]<=max){
    arr[0] = arr[0]+1;
    list.append('(');
    backtrack(arr,list,max);
    list.deleteCharAt(list.length()-1);
    arr[0] = arr[0]-1;
  }


  // )
  if (arr[1]<=max){
    arr[1] = arr[1]+1;
    list.append(')');
    backtrack(arr,list,max);
    list.deleteCharAt(list.length()-1);
    arr[1] = arr[1]-1;
  }

}
}

// 方法一
public ListNode reverseKGroup(ListNode head, int k) {
  if (head == null) {
    return null;
  }
  Stack<ListNode> stack = new Stack<>();
  ListNode dummyNode = new ListNode(-1);
  ListNode cur = dummyNode;

  while (head!= null || !stack.isEmpty()) {
    // k个一组压栈
    for (int i = 0; i < k; i++) {
      // 注意链表最后不足k的部分不需要翻转，这时候直接把栈底的节点连接到cur之后即可。
      if (head == null) {
        while(!stack.isEmpty()){
          ListNode node = stack.pop();
          if(stack.size()==0){
            cur.next = node;
          }
        }
        break;
      }
      stack.push(head);
      head = head.next;
    }

    // 出栈构建新链表
    while (!stack.isEmpty()) {
      ListNode node = stack.pop();
      cur.next = node;
      node.next = null;
      cur = node;
    }
  }
  return dummyNode.next;
}

// 方法二
public ListNode reverseKGroup(ListNode head, int k) {
  if (head == null || head.next == null){
    return head;
  }
  //定义一个假的节点。
  ListNode dummy=new ListNode(0);
  //假节点的next指向head。
  // dummy->1->2->3->4->5
  dummy.next=head;
  //初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点
  ListNode pre=dummy;
  ListNode end=dummy;

  while(end.next!=null){
    //循环k次，找到需要翻转的链表的结尾,这里每次循环要判断end是否等于空,因为如果为空，end.next会报空指针异常。
    //dummy->1->2->3->4->5 若k为2，循环2次，end指向2
    for(int i=0;i<k;i++){
      if(end== null) break;
      end=end.next;
    }
    //如果end==null，即需要翻转的链表的节点数小于k，不执行翻转。
    if(end==null){
      break;
    }
    //先记录下end.next,方便后面链接链表
    ListNode next=end.next;
    //然后断开链表
    end.next=null;
    //记录下要翻转链表的头节点
    ListNode start=pre.next;
    //翻转链表,pre.next指向翻转后的链表。1->2 变成2->1。 dummy->2->1
    pre.next=reverse(start);
    //翻转后头节点变到最后。通过.next把断开的链表重新链接。
    start.next=next;
    //将pre换成下次要翻转的链表的头结点的上一个节点。即start
    pre=start;
    //翻转结束，将end置为下次要翻转的链表的头结点的上一个节点。即start
    end=start;
  }
  return dummy.next;
}

//链表翻转
// 例子：   head： 1->2->3->4
public ListNode reverse(ListNode head) {
  //单链表为空或只有一个节点，直接返回原单链表
  if (head == null){
    return null;
  }
  //前一个节点指针
  ListNode preNode = null;
  //当前节点指针
  ListNode curNode = head;
  //下一个节点指针
  ListNode nextNode = null;
  while (curNode != null){
    nextNode = curNode.next;//nextNode 指向下一个节点,保存当前节点后面的链表。
    curNode.next=preNode;//将当前节点next域指向前一个节点   null<-1<-2<-3<-4
    preNode = curNode;//preNode 指针向后移动。preNode指向当前节点。
    curNode = nextNode;//curNode指针向后移动。下一个节点变成当前节点
  }
  return preNode;

}

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            nums[++i]=nums[j];
        }
    }
    return i + 1;
}

// 栈
public int longestValidParentheses(String s) {
  int res = 0;
  Deque<Integer> stack = new LinkedList<Integer>();
  stack.push(-1);
  for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == '(') {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.empty()) {
        stack.push(i);
      } else {
        res = Math.max(res, i - stack.peek());
      }
    }
  }
  return res;
}

class Solution {
  public int[] searchRange(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    // 寻找左边界
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > target) {
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] == target) {
        right = mid - 1;
      }
    }
    // 越界或不存在补丁
    int res1 = left;
    if (left >= nums.length || nums[left] != target) {
      res1 = -1;
    }

    // 寻找右边界
    left = 0;
    right = nums.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > target) {
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else if (nums[mid] == target) {
        left = mid + 1;
      }
    }
    // 越界或不存在补丁
    int res2 = right;
    if (right < 0 || nums[right] != target) {
      res2 = -1;
    }

    return new int[]{res1, res2};
  }
}

void traverse(TreeNode root) {
    for (TreeNode child : root.childern)
        // 前序遍历需要的操作
        traverse(child);
        // 后序遍历需要的操作
}

class Solution {
  
  private List<List<Integer>> res = new LinkedList<>();

  /* 主函数，输入一组不重复的数字，返回它们的全排列 */
  public List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
  }

  // 路径：记录在 track 中
  // 选择列表：nums 中不存在于 track 的那些元素
  // 结束条件：nums 中的元素全都在 track 中出现
  public void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
		  // 就是你 list 是个引用类型，你把它 push 到 res 里面之后，其实 push 的是同一个玩意，到最后输出的全是空的。
      res.add(new LinkedList(track));
      return;
    }

    for (int i = 0; i < nums.length; i++) {
      // 判断何时才能前进，排除不合法的选择
      if (!track.contains(nums[i])){
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
      }
    }
  }
}

private List<List<String>> res = new LinkedList<>();

/* 输入棋盘边长 n，返回所有合法的放置 */
public List<List<String>> solveNQueens(int n) {
    // '.' 表示空，'Q' 表示皇后，初始化空棋盘。
    char[][] board = new char[n][n];
    //初始化数组
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        board[i][j] = '.';

    backtrack(board, 0);
    return res;
}

// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
public void backtrack(char[][] board, int row) {
    // 触发结束条件,最后一行都走完了，说明找到了一组，把它加入到集合res中 
    if (row == board.length) {
        res.add(construct(board));
        return;
    }

    // 遍历选择列表
    for (int col = 0; col < board.length; col++) {
        // 判断何时前进,排除不合法选择
        if (isValid(board, row, col)) {
          // 做选择
          board[row][col] = 'Q';
          // backtrack(路径，选择列表)
          backtrack(board, row + 1);
          // 撤销选择
          board[row][col] = '.';
      }
    }
}

//把数组转为list
private List<String> construct(char[][] board) {
    List<String> path = new ArrayList<>();
    for (int i = 0; i < board.length; i++) {
      path.add(new String(board[i]));
    }
    return path;
}

/* 是否可以在 board[row][col] 放置皇后？ */
private boolean isValid(char[][] board, int row, int col) {
  //判断当前列有没有皇后,因为他是一行一行往下走的，
  //我们只需要检查走过的行数即可，通俗一点就是判断当前
  //坐标位置的上面有没有皇后
  for (int i = 0; i < row; i++) {
    if (board[i][col] == 'Q') {
      return false;
    }
  }
  //判断当前坐标的右上角有没有皇后
  for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
    if (board[i][j] == 'Q') {
      return false;
    }
  }
  //判断当前坐标的左上角有没有皇后
  for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] == 'Q') {
      return false;
    }
  }
  return true;
}

// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
    // 触发结束条件
    if (row == board.size()) {
        res.push_back(board);
        return true;
    }
    ...
    for (int col = 0; col < n; col++) {
        ...
        board[row][col] = 'Q';

        if (backtrack(board, row + 1))
            return true;

        board[row][col] = '.';
    }

    return false;
}

int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    res = Math.max(res, dp[i]);
}
return res;

// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

int maxSubArray(int[] nums) {
    int n = nums.length;
    int res = nums[0];
    if (n == 0) return 0;
    int[] dp = new int[n];
    // base case
    // 第一个元素前面没有子数组
    dp[0] = nums[0];
    // 状态转移方程
    for (int i = 1; i < n; i++) {
        dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        res = Math.max(res, dp[i]);
    }
    return res;
}

int maxSubArray(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
    // base case
    int dp_0 = nums[0];
    int dp_1 = 0, res = dp_0;


    for (int i = 1; i < n; i++) {
        // dp[i] = max(nums[i], nums[i] + dp[i-1])
        dp_1 = Math.max(nums[i], nums[i] + dp_0);
        dp_0 = dp_1;
        // 顺便计算最大的结果
        res = Math.max(res, dp_1);
    }


    return res;
}

// 二分查找
public int mySqrt(int x) {
  int l = 0, r = x, ans = -1;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if ((long) mid * mid <= x) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return ans;
}

// 牛顿迭代法
public int mySqrt(int x) {
  if (x == 0) {
    return 0;
  }

  double C = x, x0 = x;
  while (true) {
    double xi = 0.5 * (x0 + C / x0);
    if (Math.abs(x0 - xi) < 1e-7) {
      break;
    }
    x0 = xi;
  }
  return (int) x0;
}

class Solution {
  public int minDistance(String word1, String word2) {

    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    // base case
    for (int i = 0; i <= m; i++) {
      dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
      dp[0][j] = j;
    }

    // 自底向上求解
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (word1.charAt(i - 1) == word2.charAt(j - 1))
          dp[i][j] = dp[i - 1][j - 1];
        else
          dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),
                              dp[i - 1][j - 1] + 1);
      }
    }
    // 储存着整个 s1 和 s2 的最小编辑距离
    return dp[m][n];
  }
}