/**
 * @param nums: A list of integers
 * @return: A integer indicate the sum of max subarray
 */
const maxSubArray = function(nums) {
  let max = nums[0]; // 初始化最大值
  let newMax = nums[0]; // 数组元素相加的缓存值
  for (let i = 1; i < nums.length; i++) {
    newMax = Math.max(newMax + nums[i], nums[i]); // 相加是否大于当前值
    max = Math.max(newMax, max); // 与最大值相比
  }
  return max;
};

/**
 * @param nums: A list of integers
 * @return: A integer indicate the sum of max subarray
 */
const maxSubArray = function(nums) {
  var nSum = nums[0]; // 数组元素相加的缓存值
  var nMax = nSum; // 初始化最大值
  for (var i = 1; i < nums.length; i++) {
    var curNum = nums[i]; // 当前元素
    if (curNum >= 0) nSum = nSum > 0 ? nSum + curNum : curNum;
    // 如果两个值都大于0 两个值相加。否则就取后一个大于0的
    else nSum = nSum < curNum ? curNum : nSum + curNum; // 如果新加的值小于0 判断结果是否大于新加的值 小于的话就改为新加的值
    nMax = Math.max(nMax, nSum); // 最大值与数组元素相加值比较
  }
  return nMax;
};

const maxSubArray = function(nums) {
  let max = {
    num: nums[0],
    start: 0,
    end: 1 // 结束的下标 后面要切割数组 需比当前下标+1.把当前值也切割
  };
  let newMax = {
    num: nums[0],
    start: 0,
    end: 1
  };
  for (let i = 1; i < nums.length; i++) {
    if (newMax.num + nums[i] > nums[i]) {
      // 相加大于当前值 缓存改值和结束下标
      newMax.num = newMax.num + nums[i];
      newMax.end = i + 1;
    } else {
      // 小于当前值 重置start end
      newMax.num = nums[i];
      newMax.start = i;
      newMax.end = i + 1;
    }
    // 最大值被超过 把值赋给最大值
    if (max.num < newMax.num) {
      max.num = newMax.num;
      max.start = newMax.start;
      max.end = newMax.end;
    }
  }
  let arr = nums.slice(max.start, max.end); // 找出最大和的子数组
  return max.num; // 子数组的最大和
};

var rightSideView = function(root) {
  if (!root) return [];
  let res = []; // 结果
  let start = 0; // 树的深度 从0开始
  dfs(root, start, res);
  return res;
};
function dfs(root, step, res) {
  if (root) {
    if (step === res.length) {
      res.push(root.val); // 数组长度等于树的深度时 添加当前值 因为右侧先遍历 有右侧先添加右侧
    }
    dfs(root.right, step + 1, res);
    dfs(root.left, step + 1, res);
  }
}

var rightSideView = function(root) {
  if (!root) return [];
  let queue = [root]; // 队列 把树顶加入队列
  let arr = []; // 用来存储每层最后个元素值
  while (queue.length > 0) {
    let len = queue.length; // 当前层的广度
    while (len) {
      let node = queue.shift(); // 依次取出当前层队列的元素 从左到右
      if (len === 1) arr.push(node.val); // 当是 当前一层的最后一个元素时，把值加入arr
      if (node.left) queue.push(node.left); // 先添加左侧的
      if (node.right) queue.push(node.right); // 最后添加右侧的 等到最后一个元素时即可添加右侧的值
      len--;
    }
  }
  return arr;
};

/**
 * @param nums: A list of integers
 * @return: A list of integers includes the index of the first number and the index of the last number
 */
const subarraySum = function(nums) {};

const subarraySum = function(nums) {
  let [total, res] = [0, []]; // 和,结果
  for (let i = 0; i < nums.length; i++) {
    res = [];
    res[0] = i; // 保存起始位置
    // 需要第二层循环 可能第一个元素直到最后和也不是0 那么需要从第二个元素再找 以此类推
    for (let j = i; j < nums.length; j++) {
      total = total - nums[j]; // 不断减去每个元素 直到结果为0
      if (total === 0) {
        res[1] = j; // 保存第二个下标
        return res; // 返回起始和结束的下标
      }
    }
  }
  return false; // 没找到
};
console.log(subarraySum([-3, 1, 2, -3, 4]));

var restoreIpAddresses = function(s) {
  if (s.length > 12) return [];
  let result = [];
  fn(s, [], result);
  return result;
};
// 递归
function fn(remain, temp, result) {
  // 第四段
  if (temp.length === 3) {
    if (regular(remain)) {
      // 合法即为正确的值
      result.push([...temp, remain].join("."));
    }
    return;
  }
  // 每段长度都可能为1/2/3
  for (let i = 1; i < 4; i++) {
    // 合法才可继续
    if (regular(remain.substr(0, i))) {
      const strArr = [...temp, remain.substr(0, i)]; // 字符段
      const str = remain.substr(i); // 剩下的字符串
      fn(str, strArr, result);
    }
  }
}
// 验证合法性
function regular(s) {
  if (!s.length) return false;
  return 0 <= +s && +s <= 255 && (s.length > 1 ? !!+s[0] : true);
}

lines = ['192.168.1.1', '192.118.2.1', '192.168.1.1'];
return '192.168.1.1';

/**
 * @param ipLines: ip  address
 * @return: return highestFrequency ip address
 */
const highestFrequency = function(ipLines) {
  var [obj, max, name] = [{}, 1, ''];
  ipLines.forEach(value => {
    if (obj[value]) {
      // 已经有值了 就把值+1
      obj[value]++;
      if (obj[value] > max) { // 判断重复次数有没有超过当前最高的
        max = obj[value]; // 重复次数
        name = value; // 当前元素
      }
    } else {
      // 没有值 就初始化一个值
      obj[value] = 1;
    }
  });
  return name;
};

/**
 * @param k: An integer
 * @param n: An integer
 * @return: An integer denote the count of digit k in 1..n
 */
const digitCounts = function(k, n) {
  // write your code here
};

const digitCounts = function(k, n) {
  let count = 0;
  k = k.toString();
  // 遍历n的范围
  for (let i = 0; i <= n; i++) {
    let str = i.toString(); // 存字符
    for (let m = 0; m < str.length; m++) {
      //  遍历字符 计算出现两个k的情况
      if (str[m] === k) {
        count++;
      }
    }
  }
  return count;
};
console.log('输出:', digitCounts(1, 12)); // 5

const digitCounts = function(k, n) {
  let sum = 0,
    s = [...Array(n + 1).keys()].join(''); // 将数字范围转成数组再链接成字符串
  // 比如 s = "0123456789101112", n = 12
  k = k.toString(); // 转字符用于判断
  for (var i = s.length - 1; i >= 0; i--) {
    // 遍历字符串 判断是否与k相等
    if (s[i] === k) {
      sum++;
    }
  }
  return sum;
};
console.log('输出:', digitCounts(1, 12)); // 5

const digitCounts = function(k, n) {
  let num = 0;
  let reg = new RegExp(`${k}`, 'g'); // 正则 全局匹配k
  for (let i = 0; i <= n; i++) {
    let res = i.toString().match(reg); // 搜索i，返回一个匹配的数组
    if (res) {
      num = num + res.length; // 匹配的数量
    }
  }
  return num;
};
console.log('输出:', digitCounts(1, 12)); // 5

const checkPowerOf2 = function (n) {
    var i = 0
    // 一步步增加2的幂次 并对比
    while (i < 32) {
        let multiple = Math.pow(2, i); // 当前幂次
        if (n === multiple) {
            return true // 是2的幂次
        }
        if (multiple > n) return false; // n小于当前幂次 return false 取消无 用遍历 缩短运行时间
        i++
    }
    return false
}
console.log(checkPowerOf2(8),checkPowerOf2(10));

/**
 * @description
 * TODO: 利用二分查找方式
 * 1.利用将数组从中间分开
 * 此时肯定存在前半部分或是后半部分是有序的（重要）
 * 2.对有序部分执行二分查找
 * 3.如果目标值不可能存在于有序部分
 * 4.则将目标查找数组选择在无序部分
 * 5.继续进行1进行判断
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  if (!nums || nums.length === 0) return -1;
  let start = 0;
  let end = nums.length - 1;
  let mid;
  while (start <= end) {
    mid = Math.ceil((start + end) / 2);
    // 首尾中全部验证
    if (nums[mid] === target) return mid;
    if (nums[start] === target) return start;
    if (nums[end] === target) return end;
    // 说明前半部分有序
    if (nums[start] < nums[mid]) {
      // 说明目标值存在于有序部分，将末尾设置为mid
      // 判断目标值是否在前半部分
      // 更新索引 继续执行二分查找
      if (nums[start] < target && target < nums[mid]) {
        end = mid - 1;
      } else {
        // 说明目标值存在于后半段
        start = mid + 1;
      }
    } else {
      // 说明后半部分有序
      // 判断目标值是否在后半部分
      // 更新索引 继续执行二分查找
      if (nums[mid] < target && target < nums[end]) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }
  }
  return -1;
};

/**
 * @param nums: A list of integers
 * @return: An integer denotes the middle number of the array
 */
const median = function(nums) {};

/**
 * @param nums: A list of integers
 * @return: An integer denotes the middle number of the array
 */
const median = function(nums) {
  nums.sort((a, b) => {
    return a - b; // 升序排序
  });
  var num = nums.length; // 保存数组长度
  if (num % 2 !== 0) {
    // 判断奇数偶数
    return nums[(num + 1) / 2 - 1]; // 奇数转偶数
  } else {
    return nums[num / 2 - 1]; // 减一 对应数组下标
  }
};

/**
 * @param nums: A list of integers
 * @return: An integer denotes the middle number of the array
 */
const median = function(nums) {
  nums.sort((v1, v2) => v1 - v2);
  return nums[Math.ceil(nums.length / 2) - 1]; // 
};

输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

输入: [1,2,3,4,5,6,7,8,9]
输出: 2

const wiggleMaxLength = function (nums) {
}

const wiggleMaxLength = function (nums) {
    if (nums.length < 2) {
        return nums.length; // 小于2 直接返回
    }
    let length = 1; // 默认每个数字为1
    let flag = "begin"; // 初始摆动方向
    for (var i = 0; i < nums.length - 1; i++) {
        switch (flag) {
            case "begin":
                if (nums[i] < nums[i + 1]) {
                    flag = "up"; // 摆动方向
                    length++; // 初始两个值为摆动序列
                } else if (nums[i] > nums[i + 1]) {
                    flag = "down";
                    length++; // 初始两个值为摆动序列
                }
                break;
            case "up":
                if (nums[i] > nums[i + 1]) {
                    // 找到下一组下一个值比本身小的值
                    flag = "down";
                    length++;
                }
                break;
            case "down":
                if (nums[i] < nums[i + 1]) {
                    // 找到下一组下一个值比本身大的值
                    flag = "up";
                    length++;
                }
                break;
        }
    }
    return length;
}