/**
 * @param {string} s
 */
var problemName = function(s) {
    // Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
	let [x, y] = ...
  
  // Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
    let st = 0;
  	for(let end = 0; end < s.length; s++){
        //Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
        x = new_x;
      	if(condition){
          y = new_y;
        }
      // Step 4 - 情况1
            // 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否超过限定长度 
            // 如果超过了，窗口左指针前移一个单位保证窗口长度固定, 在那之前, 先更新Step 1定义的(部分或所有)维护变量 
            if(窗口长度大于限定值){
               // 更新 (部分或所有) 维护变量 
                // 窗口左指针前移一个单位保证窗口长度固定
            }
              
            // Step 4 - 情况2
            // 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            // 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            // 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while(不合法){
            	//更新 (部分或所有) 维护变量 
              //不断移动窗口左指针直到窗口再次合法
            }           
    }
  // Step 5: 返回答案
  return ...
};

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length==0) return 0;
    //无重复字符的最长子串
    //ex
    // abcabcbb
    // abc -> maxLen = 3
    //滑动窗口
    //1.定义需要维护的变量
    let maxLen = -1;
    let hash = new Map();
    //2.定义窗口的首尾端，然后滑动窗口
    let st = 0;
    for(let end = 0; end < s.length; end++){//第一次debug是end++写成s++了
        //维护变量
        let c = s[end];
        
        //情况2:窗口可变,检查窗口是否合法，不合法就调整st指针直至合法  
        //在该题目中，不合法指的是，字符串中出现重复字符 
        if(hash.has(c)){//c字符不是第一次出现，窗口不合法
            //只要连续移动字符，直到新的窗口的字符中不包含第一次出现的c字符位置
            while( st < end && s[st] != c){
                hash.delete(s[st]);//第二次debug，这一句和下面一句的顺序反了，如果先++在delet，那么相当于delet的是下一个字符，第一个字符永远都不会被移除
                st++;
            } 
            //此时的st应该位于第一个窗口的第一个c字符处
            st++;
            //现在窗口合法了
        }else{//第一次出现
            hash.set(c, 1);
        }

        //窗口的长度为end - st + 1 （左闭右闭区间）
        //如果是左闭右开区间，就是end - st
        maxLen = Math.max(maxLen, end - st + 1);
    }
    return maxLen;
};

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length==0) return 0;
    let maxLen = -1;
    let hash = new Map();
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];    
        if(hash.has(c)){
            while( st < end && s[st] != c){
                hash.delete(s[st]);
                st++;
            } 
            st++;
        }else{
            hash.set(c, 1);
        }
        maxLen = Math.max(maxLen, end - st + 1);
    }
    return maxLen;
};

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    //哈希(异位词)+滑动窗口(子串)
    //异位词的特点是：
    //1.长度相等
    //2.每个字符的出现次数相等
    let hash = new Map();
    let hash2 = new Map();
    let res = [];
    //初始化hash
    for(let i = 0; i < p.length; i++){
        if(hash.has(p[i])){
            hash.set(p[i], hash.get(p[i]) + 1);
        }else hash.set(p[i], 1);
    }
    //初始化窗口，并开始滑动
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];
        if(hash2.has(c)){
            hash2.set(c, hash2.get(c) + 1);
        }else hash2.set(c, 1);

        //窗口不合法1，没有这个字符,两个指针都跳到这个指针后面
        if(!hash.has(c)){
            while(st != end + 1){//debug1,一开始没有跳转到st = end+1，只是st++，这样是不对的，而且跳转完之后，一定要记得移除hash2中前面的（已经不在滑动窗口中的）字母
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }else if(hash2.get(c) > hash.get(c)){
            //窗口不合法2,有这个字符，但是字符数多了,移动st，直到窗口中的c的字符数与hash中的字符数一致
            while(hash2.get(c) != hash.get(c)){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }
        //窗口不合法3，窗口长度超过了
        while(end - st + 1 > p.length){
            hash2.set(s[st], hash2.get(s[st]) - 1);//debug2，滑动了窗口，但是忘记处理hash2了
            st++;
        }
        if(end - st + 1 === p.length){
            res.push(st);
        }
    }
    return res;
};

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let hash = new Map();
    let hash2 = new Map();
    let res = [];
    for(let i = 0; i < p.length; i++){
        if(hash.has(p[i])){
            hash.set(p[i], hash.get(p[i]) + 1);
        }else hash.set(p[i], 1);
    }
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];
        if(hash2.has(c)){
            hash2.set(c, hash2.get(c) + 1);
        }else hash2.set(c, 1);
        if(!hash.has(c)){
            while(st != end + 1){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }else if(hash2.get(c) > hash.get(c)){
            while(hash2.get(c) != hash.get(c)){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }
        while(end - st + 1 > p.length){
            hash2.set(s[st], hash2.get(s[st]) - 1);
            st++;
        }
        if(end - st + 1 === p.length){
            res.push(st);
        }
    }
    return res;
};

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;
    let num1 = 0, num2 = 1;
    let cur;
    for(let i = 2; i <= n; i++){
        cur = num1 + num2;
        num1 = num2;
        num2 = cur;
    }
    return cur;  
};

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    //dp[i]表示爬到i阶楼梯，有dp[i]种方法
    let dp = [0, 1, 2];
    //初始化dp[]
    //状态转移方程
    for(let i = 3; i <= n; i++){
        let cn = 0;
        for(let k = 1; k < i; k++){
            cn += (dp[k] * dp[i - k]);
        }
        //去除重复值
        cn = cn - 2 * i + 5;
        dp.push(cn);
    }
    return dp[n];
};

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    //dp[i]表示爬到i阶楼梯，有dp[i]种方法
    let dp = [0, 1, 2];
    //状态转移方程
    for(let i = 3; i <= n; i++){
        dp.push(dp[i - 1] + dp[i - 2]);//可以不用维护数组，直接用变量来写，写法上一题斐波那契数写法一致，不写了这里
    }
    return dp[n];
};

/**
 * @param {number[]} cost
 * @return {number}
 */

//ct[i]指的是到达i（此时i是楼顶）的最小消费
var minCostClimbingStairs = function(cost) {
    //ct[i]达到i台阶的需要最小消费
    if(cost.length==1) return cost[0];
    if(cost.length==2) return Math.min(cost[0],cost[1]);
    let ct1 = Math.min(cost[0],cost[1]);
    let ct = [0, 0];
    for(let i = 2; i <= cost.length; i++){
        let cur = Math.min(ct[i - 1]+cost[i - 1], ct[i-2]+cost[i-2]);
        ct.push(cur);
    }
    return ct[ct.length - 1];
};

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    //初始化d[x][y]边缘元素为1
    let d = new Array(m + 1);
    for(let x = 1; x <= m; x++){
        d[x] = new Array(n + 1);
        if(x == 1) d[1].fill(1);
        d[x][1] = 1;
    }
    for(let x = 2; x <= m; x++){
        for(let y = 2; y <= n; y++){
            d[x][y] = d[x][y - 1] + d[x - 1][y];
        }
    }
    console.log(d);
    return d[m][n];
};

function dfs(node, visited) {
    if (visited.has(node)) {
        return;
    }
    
    // 处理当前节点
    visited.add(node);
    
    // 遍历当前节点的相邻节点
    for (let neighbor of node.neighbors) {
        if (!visited.has(neighbor)) {
            dfs(neighbor, visited);
        }
    }
}

// 初始化访问记录
let visited = new Set();

// 从起始节点开始进行DFS
dfs(startNode, visited);

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    function dfs(x, y) {
        // 如果越界，则认为这条路径不可行
        if (x >= m || y >= n) return 0;
        // 当到达终点时，返回1
        if (x === m - 1 && y === n - 1) return 1;
        // 向右走 + 向下走
        return dfs(x + 1, y) + dfs(x, y + 1);
    }

    return dfs(0, 0);
};

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    //当（x,y）点是障碍点时，那么达到x,y的路径只能是0条，多加一个判断条件
    //初始化d[x][y]
    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length;
    let d = new Array(m);
    for(let x = 0; x < m; x++){
        d[x] = new Array(n);
        let y = 0;
        while(x==0 && obstacleGrid[0][y]!=1 && y < n){
            d[0][y++] = 1
        }
        while(x==0 && y < n){
            d[0][y++] = 0;
        }
        if(obstacleGrid[x][0]!=1){
            d[x][0] = 1;
        } else {
            while(x < m){//这里有个易错点
              //如果在这个代码块种不加if(x < m)d[x] = new Array(n);，那么因为当x++的时候，下一个d[x]是没有定义为数组的，如果此时使用d[x][0]就会报不能给undefined赋值的错误
                d[x][0] = 0;
                x++;
                if(x < m)d[x] = new Array(n);
            }
        }     
    }
    for(let x = 1; x < m; x++){
        for(let y = 1; y < n; y++){
            if(obstacleGrid[x][y]==1){
                d[x][y] = 0;
            }else{
                d[x][y] = d[x-1][y] + d[x][y-1];
            }
        }
    }
    console.log(d);
    return d[m-1][n-1];

};

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    let maxNum = -1;
    for(let k = 2; k <= n ; k++){
        let m = n % k;//余数
        maxNum = Math.max(((((n-m)/k) + 1))**(m) * (((n-m)/k)) ** (k - m), maxNum);
    }
    return maxNum;
};

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    // 10 
    //  1 9
    // 2 8 
    // 3 7
    //4 6
    // 5 5
    // 6 4
    // 7 3
    // 8 2
    // 9 1
    let dp = new Array(n+1).fill(0);//要先提前初始化为0
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    // 3  
    for(let i = 3; i <= n; i++){
        for(let j = 1; j <= i/2; j++){
            dp[i] = Math.max(j*(i-j), j*dp[i-j],dp[i]);
        }
    }
    return dp[n];

};

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    //d[i]表示有i个节点的二叉搜索树的种数
    let dp = new Array(n+1).fill(1);
    dp[2] = 2;
    for(let i = 3; i <= n; i++){
        let cn = 0;
        for(let j = 0; j < i; j++){
            cn += (dp[j] * dp[i-j-1]);
        }
        dp[i] = cn;
    }
    return dp[n];
};

//数组中插入数据
let arr = [];
arr.push(1);

//arr = [1]
arr.indexOf(1);//0


//比较两个数组是否相等（只适用于数组里面的元素都是原始值）
function arraysAreEqual(array1, array2) {
    // 首先检查数组长度
    if (array1.length !== array2.length) return false;

    // 然后检查每个元素是否相等
    for (let i = 0; i < array1.length; i++) {
        if (array1[i] !== array2[i]) return false;
    }

    // 如果通过了上述检查，那么数组相等
    return true;
}

//数组遍历
let strs = ["hello", "world", "JavaScript"];

//使用for循环
for(let i = 0; i < strs.length; i++){
  console.log(i,strs[i]);
}

//使用for of 与entries()
for (let [i, str] of strs.entries()) {
    console.log(i, str);
}

//数字数组的排序
//在JavaScript中，如果sort()方法没有提供比较函数，它会将数组元素转换成字符串，然后按照字符串的Unicode码点顺序进行排序。
//会导致例如这个数组[100,4,200,1,3,2]排序不成功
//例如，数字100和200在转换为字符串后，会根据它们的第一个字符（"1"和"2"）来进行排序，但当比较2和100时，由于"2"的Unicode码点小于"1"的Unicode码点，所以2会排在100之前。
//需要加入比较函数
nums = [100,4,200,1,3,2];
nums.sort((a, b) => a - b);
//这个比较函数简单地从a中减去b。如果结果是负数，那么a将排在b之前；如果结果是正数，b将排在a之前；如果结果是0，那么它们的顺序不变。
// a-b就是 从小到大排序


//初始化一个长度为n，值为0的数组
let n = 5; // 假设我们想要一个长度为5的数组
let arr = Array(n).fill(0);
console.log(arr); // 输出: [0, 0, 0, 0, 0]

//单个字符转换成ASCII码字
let c = 'a';
let ASCIINum = c.charCodeAt(0);//97

let c1 = 'ab';
let ASCIINum = c.charCodeAt(2);//98

//将字符串分割成单个字符的数组
let str = "hello";
str.split("").forEach(char => console.log(char));
// ['h','e','l','l','o']

//字符串字母排序 
function sortString(str) {
    // 将字符串转换为数组
    let arr = str.split('');
    // 对数组进行排序
    arr.sort();
    // 将数组转换回字符串
    return arr.join('');
}

let originalString = "hello";
let sortedString = sortString(originalString);

console.log(sortedString); // 输出: ehllo

//使用 `has` 方法可以检查 `Map` 中是否存在某个键：
//创建一个 Map
let map = new Map();

//设置键值对
//使用 `set` 方法可以添加或更新键值对：
map.set('key', 'value');
map.set(123, 456);
map.set({}, 'Object');
map.set(function() {}, 'Function');

//获取值
console.log(map.get('key')); // 输出: 'value'
console.log(map.get(123)); // 输出: 456

//检查键是否存在
console.log(map.has('key')); // 输出: true
console.log(map.has('notExist')); // 输出: false

//删除键值对
map.delete('key');

//获取Map的大小
//使用 `size` 属性可以获取 `Map` 中键值对的数量：
console.log(map.size);

//遍历Map
//`Map` 对象可以通过 `forEach` 方法遍历，也可以使用迭代器方法（如 `keys()`, `values()`, 和 `entries()`）进行遍历。

//使用 `forEach` 遍历：
map.forEach((value, key) => {
  console.log(key, value);
});

//使用迭代器遍历：
for (let [key, value] of map.entries()) {
    console.log(key, value);
}

// 或者直接遍历Map对象
for (let [key, value] of map) {
    console.log(key, value);
}

//清空Map
map.clear();

//创建一个 Set
let mySet = new Set();

//也可以在创建时初始化`Set`：
let mySet = new Set([1, 2, 3, 4, 4, 4]);
console.log(mySet); // Set(4) {1, 2, 3, 4}


//注意，即使数组中包含重复的元素，`Set`仍然确保只保存唯一的值。
//添加元素
mySet.add(5);
mySet.add("hello");
mySet.add({a: 1, b: 2});

//检查元素
console.log(mySet.has(1)); // true
console.log(mySet.has(6)); // false

// 删除元素
mySet.delete(1);

//遍历 Set
//`Set`对象可以使用`forEach()`方法和`for...of`循环来遍历：
mySet.forEach(value => {
    console.log(value);
});

for (let item of mySet) {
    console.log(item);
}

//获取 Set 的大小
console.log(mySet.size);

//清空 Set
mySet.clear();

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++){
        let res = [];
        let index;
        if(( index = nums.indexOf(target - nums[i])) != -1 && index != i){
            res.push(i);
            res.push(index);
            return res;
        }
    }

};

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let mp = new Map();//哈希表，<str, arr>

    for(let [i, str] of strs.entries()){
        //排序
        let arr = str.split('').sort();
        let newStr = arr.join('');

        if(mp.has(newStr)){//存过了
            let subArr = mp.get(newStr);
            subArr.push(str);
            mp.set(newStr, subArr);
        }else{
            let subArr = [];
            subArr.push(str);
            mp.set(newStr, subArr);
        }
    }

    let res = [];
    mp.forEach((value, key) => res.push(value));
    return res;

};

//个别用例超时
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if(nums.length===0) return 0;
    let maxNum = 0;
    let minNum = 0;
    nums.map( (v) =>{
        maxNum = Math.max(maxNum, v);
        minNum = Math.min(minNum, v);
    });
    //
    let hashTable1 = Array(maxNum + 1).fill(0);
    let hashTable2
    if(minNum < 0){//有负数
        hashTable2 = Array( -1 * minNum + 1).fill(0);
    }
    
    for(let i = 0; i < nums.length; i++){
        if(nums[i] >= 0){
            hashTable1[nums[i]]++;
        }else{
            hashTable2[ -1 * nums[i]]++;
        }
    }
    
    let res = 0;

    let maxLen1 = -1;
    let maxLen2 = -1;
    let l1 = 0;
    let l2 = 0;
    //正数
    let f1 = false;
    for(let i = 0; i <= maxNum ; i++){
        if(hashTable1[i] != 0){
            res++;
        }else{//有中断
            f1 = true;
            maxLen1 = Math.max(maxLen1, res);
            res = 0;//重新计数
        }
        if(!f1) l1++;
    }
    maxLen1 = Math.max(maxLen1, res);
    //负数
    res = 0
    let f2 = false;
    for(let i = 1; i <= ( -1 * minNum) ; i++){
        if(hashTable2[i] != 0){
            res++;
        }else{//有中断
            f2 = true;
            maxLen2 = Math.max(maxLen2, res);
            res = 0;//重新计数
        }
        if(!f2) l1++;    
    }
    maxLen2 = Math.max(maxLen2, res);

    //计算负-0-正

    return Math.max(maxLen1, maxLen2, l1+l2);

};

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let mySet = new Set();
    nums.map( v => {mySet.add(v);});
    let res = 0, cn = 1;
    for(let i = 0; i < nums.length; i++){
        //判断该数字是否是连续子串的开头
        cn = 1;
        if(!mySet.has(nums[i] - 1)){//是开头
            let st = nums[i] + 1;
            while(mySet.has(st)){
                cn++;
                st++;
            }
            res = Math.max(res, cn);
        }
    }
    return res;
};

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    // 0 1 0 3 12
    //在 0 的位置对非 0 赋值
    let len = nums.length;
    let f = 0, s = 0;
    for(s = 0; s < len; s++){
        while( f < len && nums[f] == 0) f++;
        if(f >= len) break;
        nums[s] = nums[f++];
    }
    while(s<len){
        nums[s++] = 0;
    }
    return nums;
    
};

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let maxNum = -1;
    let st = 0, end = height.length - 1;
    while(st < end){
        maxNum = Math.max(maxNum, (end - st) * Math.min(height[st], height[end]));
        if(height[st] <= height[end]){
            st++;
        }else end--;
    }
    return maxNum;
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let res = [];
    let set = new Set();
    for(let i = 0; i < nums.length; i++){
       for(let j = i; j < nums.length; j++){
            if( i != j){
                let sum = nums[i] + nums[j];
                let index = nums.indexOf(-sum);
                if(index != -1 && index != i && index != j){ 
                    let arr = []; 
                    arr.push(nums[i]);
                    arr.push(nums[index]);
                    arr.push(nums[j]);              
                    arr.sort();
                    if(!set.has(arr)){
                        res.push(arr);
                        set.add(arr);
                    }     
                }
            }
       } 
    }
    return res;
};