202401 #

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
      swap(arr, j - 1, j);
      j--;
    }
  }
  return arr;
}
function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
insertSort([222, 333, 1, 2, 3333, 4, 6, 77]);
// 输入：nums = [4,5,6,7,0,1,2], target = 0
// 输出：4
function trans(nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    let mid = l + Math.floor((r - l) / 2);
    if (nums[mid] == target) return mid;
    // 左右分段
    if (nums[l] <= nums[mid]) {
      if (target >= nums[l] && target < nums[mid]) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    } else {
      if (target > nums[mid] && target <= nums[r]) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
  }
  return -1;
}

/**
 * 1.螺旋矩阵
 * 2.岛屿数量
 * 3.三数之和
 * 4.接雨水
 * 5.最长递增子序列
 * 6.useRequest
 */
// 螺旋矩阵
// 入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
// 输出：[1,2,3,6,9,8,7,4,5]
function matrix(nums) {
  if (!nnums.length) return [];
  // 上 右 下 左
  let res = [];
  let up = 0;
  let down = nums.length - 1;
  let left = 0;
  let right = nums[0].length - 1;
  while (true) {
    // 往右
    for (let i = left; i <= right; i++) {
      res.push(nums[up][i]);
    }
    if (++up > down) break;
    // 往下
    for (let i = up; i <= down; i++) {
      res.push(nums[i][right]);
    }
    if (--right < left) break;
    // 往左
    for (let i = right; i >= left; i--) {
      res.push(nums[down][i]);
    }
    if (up > --down) break;
    // 往上
    for (let i = down; i >= up; i--) {
      res.push(nums[i][left]);
    }
    if (right < ++left) break;
  }
  return res;
}

// 岛屿数量
// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
// 此外，你可以假设该网格的四条边均被水包围。
/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let isValid = (grid, r, c) => {
    return grid.length > r && grid[0].length > c && r >= 0 && c >= 0;
  };
  let dfs = (grid, r, c) => {
    if (!isValid(grid, r, c) || grid[r][c] != "1") return "0";
    grid[r][c] = "2";
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
  };
  let count = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] == "1") {
        count = count + 1;
        dfs(grid, i, j);
      }
    }
  }
  return count;
};

//

// 字符串相乘
function multiply(a, b) {
  let len = a.length + b.length;
  let res = new Array(len).fill(0);
  for (let i = 0; i < a.length; i++) {
    for (let j = 0; j < b.length; j++) {
      let p1 = i + j;
      let p2 = p1 + 1;
      let sum = +a[i] * +b[j] + res[p2];
      res[p2] = sum % 10;
      res[p1] = Math.floor(sum / 10) + res[p1];
    }
  }
  while (res[0] == 0) {
    res.shift();
  }
  return res.join("");
}
multiply("11", "11");

// 三数之和
function treeSum() {}

node -e 'console.log(process.env)'

function generate(n) {
  let dp = [];
  for (let i = 0; i < n; i++) {
    dp = new Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) {
      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    }
  }
  return dp;
}

function longestPand(s) {
  if (s.length < 2) return s;
  let len = s.length;
  let dp = new Array(len).fill().map(() => new Array(len).fill(false));
  let maxLen = 1;
  let begin = 0;
  // 从下往上 从左到右
  for (let i = len - 1; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      if (s[j] == s[i]) {
        if (j - i <= 1) {
          dp[i][j] = true;
        } else if (dp[i + 1][j - 1]) {
          dp[i][j] = true;
        }
      }
      if (dp[i][j] && j - i + 1 > maxLen) {
        maxLen = j - i + 1;
        begin = i;
      }
    }
  }
  return s.substring(begin, begin + maxLen);
}
longestPand("dcabac");

function render(node, parent) {
  const mount = el ? (el) => parent.appendChild(el) : (el) => el;
  if (typeof node == "string") {
    return mount(document.createTextNode(node));
  } else {
    let vNode = mount(document.createElement(node.tag));
    // props
    Object.keys(node.props).forEach((key) => {
      let val = node.props[key];
      vNode.setAttribute(key, val);
    });
    // child
    if (node.children && node.children.length) {
      node.children.forEach((child) => {
        document.appendChild(render(child, parent));
      });
    }
    return vNode;
  }
}