#力扣刷题

// 方法一 对数组每一项迭代求前面的和,性能比较差,每次都会加重复累加上次的和
function runningSum(nums) {
  return nums.map((item, index) =>
    nums.slice(0, index + 1).reduce((acc, item) => acc + item, 0)
  );
}

// 方法二 遍历数组
function runningSum(nums) {
  let res = [],
    sum = 0;
  for (let item of nums) {
    sum += item;
    res.push(s);
  }
  return res;
}

function singleNumber(nums) {
  let arr = nums.sort();
  while (arr.length > 0) {
    let start = arr.shift();
    let end = arr.shift();
    if (start !== end && !arr.includes(start)) {
      return s;
    }
  }
}

// 暴力法: map后sort排序
function sortSquares(nums) {
  return nums.map((i) => i * i).sort((a, b) => a - b);
}

// 双指针法
var sortedSquares = function (nums) {
  let l = 0,
    r = nums.length - 1,
    res = [];
  while (l <= r) {
    // 左右双指针,依次添加元素到结果中
    if (Math.abs(nums[r]) >= Math.abs(nums[l])) {
      res.push(nums[r] ** 2);
      r--; // 分别移动指针
    } else {
      res.push(nums[l] ** 2);
      l++;
    }
  }
  return res.reverse();
};

// 数组排序 ==> 去掉头尾 ==> reduce求和 ==> 取平均数
function avarage(salary) {
  let arr = salary.sort((a, b) => a - b);
  arr.pop();
  arr.shift();
  return arr.reduce((acc, item) => acc + item, 0) / arr.length;
}

// 数组找出最大最小值 ==> 数组遍历求和 ==> 去掉最大最小值后的和取平均值
function average(salary) {
  let max = Math.max(...salary);
  let min = Math.min(...salary);
  let sum = 0;
  for (let item of salary) {
    sum += item;
  }
  return (sum - max - min) / (salary.length - 2);
}

// 数组从中间切开 ==> 遍历数组元素 ==> 每次遍历添加后半段数组的头部元素
function shuffle(nums, n) {
  let arr1 = nums.slice(0, n);
  let arr2 = nums.slice(-n);
  let res = [];
  for (let item of arr1) {
    res.push(item, arr2.shift());
  }
  return res;
}

// 一行流解法: 取数组后面半段 ==> 对每个元素进行map返回新元素 ==>使用flat扁平化数组
function shuffle(nums, n) {
  return nums
    .slice(-n)
    .map((item, index) => [nums[index], item])
    .flat();
}

// 第一次解的时候没发现相同大小的数组元素不能用作比较大小,最大的三个数必须是各不相同的,所以第一步需要对数组去重

/* 方法一 */
function thirdMax(nums) {
  let arr = [...new Set(nums)].sort((a, b) => a - b).slice(-3);
  return arr.length < 3 ? arr.pop() : arr[0];
}

/* 方法二 */
var thirdMax = function (nums) {
  let arr = [...new Set(nums)];
  if (arr.length < 3) {
    return Math.max(...arr);
  } // 没啥讲的,数组去重判断返回
  for (let i = 0; i < 3; i++) {
    // 冒泡三次,最大的三个数依次在尾部归位
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 结构语法交换两元素位置,就不需要引入第三变量了
      }
    }
  }
  return arr[arr.length - 3]; // 直接返回第三大元素
};

/* 方法三 */
var thirdMax = function (nums) {
  let arr = [...new Set(nums)]; // 数组去重
  if (arr.length < 3) {
    return Math.max(...arr); // 长度小于三直接返回最大值
  }
  arr.splice(arr.indexOf(Math.max(...arr)), 1); // 删除掉数组最大数
  arr.splice(arr.indexOf(Math.max(...arr)), 1); // 删除数组中第二大数
  return Math.max(...arr); // 返回第三大
};

// 方法一, 求出范围内的数组 ==> 过滤出数组中不包含的元素
function missingNumber(nums) {
  let arr = [];
  for (let i = 0; i <= nums.length; i++) {
    arr.push(i);
  }
  return arr.filter((item) => !nums.includes(item));
}

// 方法二 原本应该的数组和减去现在数组和
function missingNumber(nums) {
  let sum = 0;
  for (let i = 0; i <= nums.length; i++) {
    sum += i;
  }
  return sum - n;
}

// 使用暴力循环,两个指针把所有的可能都扫一遍
function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (target - nums[i] === nums[j]) {
        return [];
      }
    }
  }
}

// 使用哈希map
var twoSum = function (nums, target) {
  let map = new Map(); // 用哈希表来存储遍历过的元素和索引
  for (let i = 0; i < nums.length; i++) {
    // 每遍历一个元素,看看表中是否存在满足要求的目标数字
    let match = target - nums[i];
    if (map.has(match)) {
      return [map.get(match), i]; // 如果表中有匹配的数直接返回[目标元素的索引,当前索引]
    }
    map.set(nums[i], i); // 哈希表中存储当前的元素和对应的索引
  }
  return [];
};

let moveZeroes = function (nums) {
  let write = 0; // 设置默认开始时写指针的位置
  nums.forEach((item, index) => {
    // 遍历数组
    if (item !== 0) {
      nums[write] = item; // 如果遍历的值不是0 则写指针改写值,并且指针位置下次右移动
      write++;
    }
  }); // 此时写指针之前都是遍历到的非0数
  for (let i = write; i < nums.length; i++) {
    nums[i] = 0; // 修改写指针后面的所有数为0
  }
  return nums;
};

// 读写双指针: 读指针向右侧遍历遇到不是目标的元素则左侧的写指针开始复刻并移动指针.
var removeElement = function (nums, val) {
  let len = nums.length; // 记录下最开始的长度
  for (var l = 0, r = 0; r < len; r++) {
    if (nums[r] !== val) {
      // 遇到不是目标元素,左指针开始改写并右移
      nums[l] = nums[r];
      l++;
    }
  }
  return l;
};
var removeElement = function (nums, val) {
  let index = 0; // 定义写指针
  for (let item of nums) {
    // 遍历数组,如果遍历的值和目标不等,则写指针写入该值
    if (item !== val) {
      nums[index] = item;
      index++; // 改写完成后,对写指针后移
    }
  } // 非目标元素已全部移动到写指针前方
  nums.splice(index, nums.length); // 直接切掉指针后方的无用元素
  return nums.length;
};

var findDuplicate = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    // 外层循环控制左指针
    for (let j = i + 1; j < nums.length; j++) {
      // 内层循环遍历左指针右侧的值
      if (nums[i] === nums[j]) {
        // 判断左右指针是否相等
        return nums[i];
      }
    }
  }
};

var isPalidrome = function (s) {
  s = s.toLocaleLowerCase(); // 字符串都小写
  let str = "";
  for (let i = 0; i < s.length; i++) {
    let zg = /^[0-9a-zA-Z]*$/; // 使用正则表达式匹配其中的字母和数字
    if (zg.test(s[i])) {
      str += s[i];
    }
  } // 得到处理好的正常字符串
  let revesedStr = str.split("").reverse().join("");
  return str === revesedStr;
};

var isPalindrome = function (s) {
  s = s.toLocaleLowerCase(); // 字符串都小写
  let str = "";
  for (let i = 0; i < s.length; i++) {
    let zg = /^[0-9a-zA-Z]*$/; // 使用正则表达式匹配其中的字母和数字
    if (zg.test(s[i])) {
      str += s[i];
    }
  } // 得到处理好的正常字符串
  for (let i = 0; i < Math.ceil(str.length - 1); i++) {
    // 双指针从前往后遍历字符串只需要遍历字符串的中间
    if (str[i] !== str[str.length - 1 - i]) {
      // 如果左右指针一但不相等则直接不是回文
      return false;
    }
  }
  return true;
};

var reversePrefix = function (word, ch) {
  let arr = word.split("");
  return !arr.includes(ch)
    ? word
    : [...arr.splice(0, arr.indexOf(ch) + 1).reverse(), ...arr].join("");
};

var checkPerfectNumber = function (num) {
  let res = 0;
  for (let i = 1; i <= num / 2; i++) {
    // 数字的只需要遍历到一半的数据就行
    if (num % i === 0) {
      res += i;
    }
  }
  return res === num ? true : false;
};

var fizzBuzz = function (n) {
  let arr = [];
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      // 同时满足3和5的倍数优先级比较高,需要放在开始
      arr.push("FizzBuzz");
    } else if (i % 3 === 0) {
      arr.push("Fizz");
    } else if (i % 5 === 0) {
      arr.push("Buzz");
    } else {
      arr.push(i.toString());
    }
  }
  return arr;
};

var twoSum = function (numbers, target) {
  let res = [];
  numbers.forEach((item, index) => {
    // 遍历数组
    for (let i = index + 1; i < numbers.length; i++) {
      // 每次遍历到的数字判断右指针的值
      if (item + numbers[i] === target) {
        res.push(index + 1, i + 1);
      }
    }
  });
  return res;
};

function plusOne(digits) {
  return (BigInt(digits.join("")) + 1n).toString().split(""); // BigInt数据类型用n表示
}

function plusOne(digits) {
  digits.unshift(0); // 刚开始就给数组头添加一个0,防止一直进位
  for (let i = digits.length - 1; i >= 0; i--) {
    // 从后往前遍历数组
    if (digits[i] !== 9) {
      // 数字不为9,直接加一
      digits[i]++;
      if (digits[0] == 0) {
        // 当数组首位为0,说明没有一直进位,切掉数组头部
        digits.shift();
      }
      return digits;
    } else {
      // 数字为9,改写当前值为0
      digits[i] = 0;
    }
  }
}

var isHappy = function (n) {
  let set = new Set(); // 创建一个set用来存取每次的n值
  while (n > 1) {
    n = n
      .toString()
      .split("")
      .map((i) => parseInt(i) ** 2)
      .reduce((acc, cur) => acc + cur); // 每次求和添加到set中
    if (set.has(n)) {
      // 如果set中有了n值说明当前的循环开始重复,永远无法变成 1 ,直接返回false
      return false;
    }
    set.add(n);
  }
  return true; // 如果能走完循环则说明最终n变成了1
};

var targetIndices = function (nums, target) {
  let res = [];
  nums
    .sort((a, b) => a - b)
    .forEach((item, index) => {
      // 对数组排序后遍历数组
      if (item === target) {
        // 如果当前值等于数组索引,则返回数组下标
        res.push(index);
      }
    });
  return res;
};

var search = function (nums, target) {
  return nums.indexOf(target);
};

var search = function (nums, target) {
  let start = 0,
    end = nums.length - 1,
    middle,
    element;
  while (start <= end) {
    middle = ~~((start + end) / 2); // 定义中间节点坐标
    element = nums[middle]; // 中间元素值
    if (element == target) {
      // 中间元素等于目标直接返回索引
      return middle;
    } else if (target < element) {
      // 目标小于中间元素,右指针移动到中间指针左侧
      end = middle - 1;
    } else {
      start = middle + 1; // 目标大于中间元素,左指针移到到中间指针右侧
    }
  }
  return -1;
};

// 直接遍历数组,判断是否相等
var game = function (guess, answer) {
  let count = 0;
  for (let i in guess) {
    if (guess[i] === answer[i]) {
      count++;
    }
  }
  return count;
};

// 对二位数组中的每一项求和并返回原数组,最后取最大值
var maximumWealth = function (accounts) {
  return Math.max(...accounts.map((i) => i.reduce((acc, cur) => acc + cur)));
};

// 直接使用join('')拼接
var arrayStringsAreEqual = function (word1, word2) {
  return word1.join("") === word2.join("");
};

// 用数组reduce()方法迭代拼接字符
var arrayStringsAreEqual = function (word1, word2) {
  let str1 = word1.reduce((acc, cur) => acc + cur, "");
  let str2 = word2.reduce((acc, cur) => acc + cur, "");
  return str2 === str1;
};

// 方法一,用对象累计存储数据计数
var majorityElement = function (nums) {
  let obj = {}; // 声明一个对象用来对每个元素计数
  for (let item of nums) {
    item.toString() in obj ? obj[item]++ : (obj[item] = 1); // 遍历数组,如果对象中没有这个值就初始化为1,否则加一
  }
  for (let key in obj) {
    if (obj[key] > nums.length / 2) {
      // 遍历对象属性值,找出多数元素
      return key;
    }
  }
};

// 方法二: 直接对数组排序后,取超过数组长度一半的数
var majorityElement = function (nums) {
  return nums.sort((a, b) => a - b)[~~(nums.length / 2)];
};

// 方法一: 直接遍历数组,并返回
var buildArray = function (nums) {
  let arr = [];
  nums.forEach((item) => arr.push(nums[item]));
  return arr;
};

// 方法二: 使用reduce()迭代
var buildArray = function (nums) {
  return nums.reduce((acc, cur) => {
    acc.push(nums[cur]);
    return acc;
  }, []);
};

// 方法三: 使用map()方法
var buildArray = function (nums) {
  return nums.map((i) => nums[i]);
};

// 数组排序后,取数最大和最小各两个值的乘积差
var maxProductDifference = function (nums) {
  let arr = nums.sort((a, b) => a - b);
  return arr[arr.length - 1] * arr[arr.length - 2] - arr[0] * arr[1];
};

// 直接使用splice()
var createTargetArray = function (nums, index) {
  let target = [];
  for (let i in index) {
    target.splice(index[i], 0, nums[i]);
  }
  return target;
};

// 使用reduce()迭代
var createTargetArray = function (nums, index) {
  return index.reduce((acc, cur, inx) => {
    acc.splice(cur, 0, nums[inx]);
    return acc;
  }, []);
};

var mostWordsFound = function (sentences) {
  return Math.max(...sentences.map((item) => item.split(" ").length));
};

// reduce()迭代
var largestAltitude = function (gain) {
  return Math.max(
    ...gain.reduce(
      (acc, cur) => {
        acc.push(acc[acc.length - 1] + cur);
        return acc;
      },
      [0]
    )
  );
};

// 翻转每一行 ==> 反转图片
var flipAndInvertImage = function (image) {
  return image.map((item) => item.reverse().map((i) => Number(!i)));
  // return image.map(item => item.reverse().map(i => i ^ 1));
  // 或者与1进行异或运算
};

// 穷举法
var findGCD = function (nums) {
  let min = Math.min(...nums);
  let max = Math.max(...nums);
  let res = [];
  for (let i = 1; i <= min; i++) {
    if (min % i === 0 && max % i === 0) {
      res.push(i);
    }
  }
  return Math.max(...res);
};

// 用对象对每个元素出现的次数进行累计,找出只出现过一次的数,并求和
var sumOfUnique = function (nums) {
  let obj = {},
    sum = 0;
  for (let item of nums) {
    item in obj ? obj[item]++ : (obj[item] = 1);
  }
  for (let key in obj) {
    if (obj[key] === 1) {
      sum += Number(key);
    }
  }
  return sum;
};

// 用哈希map()来存储计数
var sumOfUnique = function (nums) {
  let map = new Map(),
    sum = 0;
  for (let item of nums) {
    map.has(item) ? map.set(item, 1) : map.set(item, 0);
  }
  map.forEach((value, key) => {
    if (value === 0) {
      sum += Number(key);
    }
  });
  return sum;
};

var truncateSentence = function (s, k) {
  return s.split(" ").splice(0, k).join(" ");
};

// 先对数组排序,迭代数组判断是否相等.""
var heightChecker = function (heights) {
  let sorter = [...heights].sort((a, b) => a - b);
  return heights.reduce((acc, cur, idx) => {
    if (cur !== sorter[idx]) {
      acc++;
    }
    return acc;
  }, 0);
};

// 先对数组排序 ==> 用等差数列通项公式遍历判断
var canMakeArithmeticProgression = function (arr) {
  let sorter = arr.sort((a, b) => a - b);
  let d = sorter[1] - sorter[0];
  for (let key in arr) {
    if (arr[key] !== sorter[0] + key * d) {
      return false;
    }
  }
  return true;
};

var diagonalSum = function (mat) {
  let arr = [];
  for (let i = 0; i < mat.length; i++) {
    // 遍历二维数组,将对角线上的数组元素存到数组中
    arr.push(mat[i][i], mat[i][mat.length - i - 1]);
  }
  if (mat.length % 2 == 1) {
    // 如果数组的长度为偶数的时候,矩阵中心会被重复累加,需要去除这个元素
    arr.splice(mat.length, 1);
  }
  return arr.reduce((acc, cur) => acc + cur, 0); // reduce()求和
};

// 从后往前遍历,比较右侧最大值,修改原数组
var replaceElements = function (arr) {
  let max = -1,
    res = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    res[i] = max;
    max = arr[i] > max ? arr[i] : max;
  }
  return res;
};

// 遍历数组,如果数组值为0,直接返回0,计算出所有值的乘积,再进行判断.
var arraySign = function (nums) {
  let res = 1;
  for (let item of nums) {
    if (item === 0) {
      return 0;
    }
    res *= item;
  }
  return res > 0 ? 1 : -1;
};

// 方法二: 累积负数次数
var arraySign = function (nums) {
  let countNeg = 0; // 累积数组中负数的个数
  for (let item of nums) {
    if (item === 0) {
      // 如果元素为0,直接返回0
      return 0;
    }
    if (item < 0) {
      countNeg++;
    }
  }
  return countNeg % 2 === 0 ? 1 : -1; // 负数的个数如果为偶数次返回1,奇数次则返回-1;
};

// 直接使用for循环,最大值用数组中的字符串拼接转换出来
var printNumbers = function (n) {
  let res = [],
    max = Number(new Array(n).fill(9).join(""));
  for (let i = 1; i <= max; i++) {
    res.push(i);
  }
  return res;
};

// 最大值也可以使用10的n次幂求出来
var printNumbers = function (n) {
  let res = [],
    max = 10 ** n;
  for (let i = 1; i < max; i++) {
    res.push(i);
  }
  return res;
};

// 方法一: 数组排序后找出最大的两个元素,累乘
var maxProduct = function (nums) {
  return nums
    .sort((a, b) => b - a)
    .slice(0, 2)
    .reduce((acc, cur) => acc * (cur - 1), 1);
};

// 方法二: 遍历找出最大值,和次大值
var maxProduct = function (nums) {
  let max = Math.max(...nums);
  for (let key in nums) {
    if (nums[key] === max) {
      nums[key] = 0; // 对遍历到的最大值置0
      let secondMax = Math.max(...nums); // 再求出次大值
      return (secondMax - 1) * (max - 1);
    }
  }
};

var finalPrices = function (prices) {
  for (let i = 0; i < prices.length; i++) {
    // 外层循环控制写指针
    for (let j = i + 1; j < prices.length; j++) {
      // 内层循环控制读指针
      if (prices[j] <= prices[i]) {
        // 一但遍历到合适的条件写指针改写元素的折扣值
        prices[i] -= prices[j];
        break;
      }
    }
  }
  return prices;
};

// 双指针法
var twoSum = function (nums, target) {
  let left = 0,
    right = nums.length - 1; // 定义左指针,右指针
  while (left < right) {
    // 只有左右指针没有相遇就一直循环
    let sum = nums[left] + nums[right];
    if (sum === target) {
      return [nums[left], nums[right]];
    } else if (sum < target) {
      // 和小于目标值,左指针右移变大
      left++;
    } else {
      // 和大于目标值,右指针左移变小
      right--;
    }
  }
};

// 直接使用库函数
var reverseLeftWords = function (s, n) {
  return `${s.slice(n)}${s.slice(0, n)}`;
};

// 遍历字符串
var reverseLeftWords = function (s, n) {
  let res = [];
  for (let i = n; i < s.length; i++) {
    res.push(s[i]);
  }
  for (let i = 0; i < n; i++) {
    res.push(s[i]);
  }
  return res.join("");
};

// api写法
var reverseWords = function (s) {
  return s
    .split(" ")
    .map((item) => [...item].reverse().join(""))
    .join(" ");
};

// 用数组来存
var reverseWords = function (s) {
  let arr = [],
    i = 0;
  while (i < s.length) {
    let start = i;
    while (i < s.length && s[i] !== " ") {
      i++;
    }
    for (let j = start; j < i; j++) {
      arr.push(s[start + i - j - 1]);
    }
    arr.push(" ");
    i++;
  }
  return arr.join("").trimEnd();
};

// 双指针写法
var reverseWords = function (s) {
  let arr = [...s],
    l = 0,
    r = l; // 定义左右指针
  while (l < arr.length) {
    //找到结尾的空格
    while (arr[r] && arr[r] !== " ") {
      r++;
    }
    //反转单词
    for (let i = l, j = r - 1; i < j; i++, j--) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    //跳到下一个单词
    l = r + 1;
    r = l;
  }
  return arr.join("");
};

// 双重for循环遍历,对于每次遍历过的数组,都改写其值,使其下次遍历不会被比较
var intersect = function (nums1, nums2) {
  let res = [];
  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      if (nums1[i] === nums2[j]) {
        res.push(nums1[i]);
        nums1[i] = "$";
        nums2[j] = "@";
      }
    }
  }
  return res;
};

// 左右指针分别遍历两个数组
var intersect = function (nums1, nums2) {
  let res = [],
    l = 0,
    r = 0; // 左右指针,分别指向两个数组
  nums1.sort((a, b) => a - b); // 对两个数组排序
  nums2.sort((a, b) => a - b);
  while (l < nums1.length && r < nums2.length) {
    // 遍历两个数组,只要两个指针还小于数组的长度时候就一直遍历
    if (nums1[l] === nums2[r]) {
      res.push(nums1[l]); // 如果左右指针数据相等则加入数组,并且指针分别移动
      l++;
      r++;
    } else {
      nums1[l] < nums2[r] ? l++ : r++;
    }
  }
  return res;
};