题目

# 题目

# 两数之和

// 暴力解法
var twoSum = function (nums, target) {
  const n = nums.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      if (nums[j] === target - nums[i]) {
        return [i, j];
      }
    }
  }
};

// 哈希表法
var twoSum = function (nums, target) {
  const m = new Map();
  for (let i = 0; i < nums.length; i++) {
    const s = target - nums[i];
    if (m.has(s)) {
      return [m.get(s), i];
    } else {
      m.set(nums[i], i);
    }
  }
};

# 两数相加

var addTwoNumbers = function (l1, l2) {
  let l3 = new ListNode();
  let p1 = l1,
    p2 = l2,
    p3 = l3,
    tmp = 0;
  while (p1 || p2) {
    let a = p1 ? p1.val : 0;
    let b = p2 ? p2.val : 0;
    let c = Math.floor((a + b + tmp) / 10);
    p3.next = new ListNode(c);
    if (p1) {
      p1 = p1.next;
    }
    if (p2) {
      p2 = p2.next;
    }
    p3 = p3.next;
  }
  if (tmp) {
    p3.next = new ListNode(tmp);
  }
  return l3.next;
};

# 无重复子字符的最长字串

var lengthOfLongesSubstring = function (s) {
  let l = 0,
    res = 0;
  let m = new Map();
  for (let r = 0; r < s.length; r++) {
    if (m.has(s[r]) && m.get(s[r]) >= l) {
      l = m.get(s[r]) + 1;
    }
    res = Math.max(res, r - l + 1);
    m.set(s[r], r);
  }
  return res;
};

# 最长回文子串

var longestPalindrome = function (s) {
  const valid = (s, l, r) => {
    while (l < r) {
      if (s[l] !== s[r]) {
        return false;
      }
      l++;
      r++;
    }
    return true;
  };

  const n = s.length;
  let maxLen = 1,
    begin = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (j - i + 1 > maxLen && valid(s, i, j)) {
        maxLen = j - i + 1;
        begin = i;
      }
    }
  }
};

# Z 字形变换

var convert = function(s, numRows) {
    if(numRows < 2) return s
    let curRow = 0, flag = -1, res = []
    for(let i = 0; i < numRows, i++) {
        res.push('')
    }
    for(let j = 0; j < s.lenght; j++) {
        res[curRow] += s[i]
        if(curRow === 0 || curRow === numRows - 1) {
            flag = -flag
        }
        curRow += flag
    }
    return res.join('')
}

# 整数反转

var reverse = function (x) {
  let res = 0;
  while (x) {
    res = rex * 10 + (x % 10);
    x = x > 0 ? Math.floor(x / 10) : Math.ceil(x / 10);
  }
  if (res > 2147483646 || res < -2147483648) {
    return 0;
  }
  return res;
};

# 字符串转整数(atoi)

var myAtoi = function (s) {
  const INT_MAX = 2147483647,
    INT_MIN = -2147483648;
  let res = 0,
    flag = 1,
    i = 0;
  while (s[i] === " ") {
    i++;
  }
  if (s[i] === "-") {
    flag = -1;
  }
  if (s[i] === "+" || s[i] === "-") {
    i++;
  }
  while (i < s.length && /\d/.test(s[i])) {
    let r = s[i] - "0";
    if (
      res > Math.floor(INT_MAX / 10) ||
      (res === Math.floor(INT_MAX / 10) && r > 7)
    ) {
      return flag > 0 ? INT_MAX : INT_MIN;
    }
    res = res * 10 + r;
    i++;
  }
  return flag > 0 ? res : -res;
};

# 回文数

var isPalindrome = function (x) {
  if (x < 0) return false;
  let res = 0,
    tmp = x;
  while (x) {
    res = res * 10 + (tmp % 10);
    tmp = Math.floor(tmp / 10);
  }
  return x === res ? true : false;
};

# 盛最多水的容器

// 暴力解法 +> 超时警告
var maxArea = function (height) {
  let res = 0,
    n = height.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = i + 1; j < n; j++) {
      res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
    }
  }
  return res;
};

// 双指针解法 +> 1. 指针在两边; 2. 长度短的向内移动
var maxArea = function (height) {
  let res = 0,
    l = 0,
    r = height.length - 1;
  while (l < r) {
    res = Math.max(res, Math.min(height[l], height[r]) * (r - l));
    height[l] < height[r] ? l++ : r--;
  }
  return res;
};

# 最长公共前缀

var longestCommonPrefix = function (strs) {
  let res = "",
    min = 0;
  strs.map((str) => {
    // 第一次min一定是0,没有比0短的字符串了,第一次为0应该特殊处理
    min = str.length < min || !min ? str.length : min;
  });
  for (let i = 0; i < min; i++) {
    const tmp = strs.map((str) => str.substring(0, i + 1));
    const a = [...new Set(tmp)];
    if (a.length === 1) {
      res = a[0];
    }
  }
  return res;
};

// 横向扫描
var longestCommonPrefix = function (strs) {
  if (!strs.length) return "";

  const lcp = (str1, str2) => {
    const n = Math.min(str1.length, str2.length);
    let idx = 0;
    while (idx < n && str1[idx] === str2[idx]) {
      idx++;
    }
    return str1.substring(0, idx);
  };

  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    prefix = lcp(prefix, strs[i]);
    if (!prefix) break;
  }

  return prefix;
};

# 把 entry 转换成如下对象

var entry = {
  "a.b.c.dd": "value",
  "a.d.xx": "val",
  "a.e": "v",
};

// 蠢比解法
const keys = Object.keys(entry);
const output = {};
let keyArr = [];

for (let idx in keys) {
  let tmp = keys[idx].split(".");
  if (keyArr.length) {
    tmp = tmp.filter((item) => !keyArr.includes(item));
  }
  keyArr = [...new Set([...keyArr, ...tmp])];

  let pre = output;
  for (let i = 0; i < tmp.length; i++) {
    if (i === tmp.length - 1) {
      pre[tmp[i]] = entry[keys[idx]];
      pre = output;
    } else {
      pre[tmp[i]] = {};
      pre = pre[tmp[i]];
    }
  }
}

// reduce解法
const changObjStructureOfNormal = (entry) => {
  const keys = Object.keys(entry);
  const resObj = {};
  for (const key of keys) {
    const everyKey = key.split(".");
    everyKey.reduce((pre, next, index, array) => {
      if (index === array.length - 1) {
        pre[next] = entry[key];
        return;
      }
      pre[next] = pre[next] || {};
      return pre[next];
    }, resObj);
  }
  return resObj;
};
changObjStructureOfNormal(entry);

# 合并两个有序链表

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function mergeTwoLists(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const res = new ListNode(0);
  let p = res;
  while (l1 & l2) {
    if (l1.val < l2.val) {
      p.next = l1;
      l1 = l1.next;
    } else {
      p.next = l2;
      l2 = l2.next;
    }
    p = p.next;
  }
  p.next = l1 === null ? l2 : l1;
  return res.next;
}

# 合并 K 个升序链表

// 暴力解法
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  // 将所有节点的值放到arr中
  // 创建存贮结果的链表
  let arr = [],
    res = new ListNode(),
    cur = res;
  lists.forEach((item) => {
    let l = item;
    while (l) {
      arr.push(l.val);
      l = l.next;
    }
  });
  // 将存储到的结果进行排序
  arr.sort((a, b) => a - b);
  arr.forEach((item) => {
    cur.next = new ListNode(item);
    cur = cur.next;
  });

  return res.next;
}
// 分治解法
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  const mergeTwoLists = (l1: ListNode, l2: ListNode): ListNode => {
    let res = new ListNode(),
      cur = res;
    while (l1 && l2) {
      if (l1.val <= l2.val) {
        cur.next = l1;
        l1 = l1.next;
      } else {
        cur.next = l2;
        l2 = l2.next;
      }
      cur = cur.next;
    }
  };

  let n = lists.length,
    interval = 1;
  while (interval < n) {
    for (let i = 0; i < n - interval; i += 2 * interval) {
      lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }
  return n > 0 ? lists[0] : null;
}