标签： LeetCode

题目

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。
 

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

提示：

-231 <= x <= 231 - 1

分析

将数当作字符串，反向遍历就能解决问题了，需要注意两个点：

1. 负数的处理；
2. 超出 32 位数范围，直接返回 0。

解答

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
  var isNegativeNumber = false;
  if (x < 0) {
    isNegativeNumber = true;
  }
  var xStr = x.toString();
  var reverseXArr = [];

  for (var i = xStr.length - 1; i >= 0; i--) {
    reverseXArr.push(xStr[i]);
  }

  var result = parseInt(reverseXArr.join(""), 10);

  if (isNegativeNumber) {
    result = 0 - result;
  }

  if (result < -Math.pow(2, 31) || result > Math.pow(2, 31) - 1) {
    result = 0;
  }

  return result;
};

---

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-integer

题目：

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例3:

输入：s = "A", numRows = 1
输出："A"

思考：

先找规律看看

	0	1	2	3	4	5	6
0	P[1]		A[5]		H[9]		N[13]
1	A[2]	P[4]	L[6]	S[8]	I[10]	I[12]	G[14]
2	Y[3]		I[7]		R[11]

	0	1	2	3	4	5	6
0	P[0]			I[6]			N[12]
1	A[1]		L[5]	S[7]		I[11]	G[13]
2	Y[2]	A[4]		H[8]	R[10]
3	P[3]			I[9]

设字符的下标为 n

梯度(t) = numRows + (numRows -2)，以示例2为例，梯度为 4 + (4 – 2) = 6

计算列数(x) :

nt = Math.floor(n / t) 得到字符 n 在第 nt 个梯度内（从 0 开始计数），每个梯度包含 tx 列，tx = numRows – 1

n % t 将所有字符放在第一个梯度内考虑，有两种情况 ：

n % t < numRows 时，x 等于 0 + s[n] 所在的梯度乘以梯的长度，即： x = 0 + nt x tx，整理后是 x = nt x tx。

n % t >= numRows 时，也就是 s[n] 是在 “Z“ 字的折线位置的，放到第一个梯度里面看，x 应该就是 n % numRows 的值，属于其他梯度内的数，加上梯度即可，考虑到下标是从 0 开始的，所以 x = (((n % t) + 1) % numRows) + nt x tx;

计算行数(y)

行数的计算和列数的计算思路一样，把所有字符放到第一个梯度内考虑，而且不需要再加上梯度了。同样分两种情况：

n % t < numRows 时，n % t 将 s[n] 放到第一个梯度内考虑，行数 y = n % numRows ，考虑梯度，最终结果为：y = n % t % numRows。

n % t >= numRows 时，也就是计算 “Z” 字折线上的数字。n % t 将 s[n] 放到第一个梯度内考虑，观察 s[n] 的下标与行数的关系，可以得到 s[n] 不可能出现在第一行和最后一行，第一个梯度内，n + 1 – numRows 可得到 s[n] 到表格底部的距离，numRows – 1 再减去这个距离，就得到行数 y 了，因此结果为：y = numRows – 1 – ((n % t) + 1 – numRows)。

还有一种情况是 numRows === 1 的时候，实际上把原字符串直接输出就是了。

解答

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function (s, numRows) {
  var matrix = [];

  for (var y = 0; y < numRows; y++) {
    // 构建行
    matrix[y] = [];
  }

  // 梯度
  var t = numRows + numRows - 2;

  for (var n = 0; n < s.length; n++) {
    // 测试列的判断逻辑是否正确

    // 初始化列位置
    var x = 0;

    // 初始化行位置
    var y = 0;

    // 得到元素在哪个梯度内
    var nt = Math.floor(n / t);

    // 每个梯度占据的列数
    var tx = numRows - 1;

    if (n % t < numRows) {
      x = 0 + nt * tx;
      y = (n % t) % numRows;
    } else {
      x = (((n % t) + 1) % numRows) + nt * tx;
      y = numRows - 1 - ((n % t) + 1 - numRows);
    }

    matrix[y][x] = s[n];
  }

  var result = "";

  matrix.forEach(function (element) {
    element.forEach(function (item) {
      if (item) result = result.padEnd(result.length + 1, item);
    });
  });

  return result;
};

---

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zigzag-conversion/

题目

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

解题思路：

先找相同字符形成的最长子串（A），如：‘aa’、‘aaa’、‘aaaa’；

然后判断 A 的前面和后面距离与 A 距离相同的字符是否一样，如果一样，继续查找，直到不一样为止，就找到了一个回文字符串；

遍历字符串，找到所有回文字符串，取出最长的一个。

解答：

var findPalindrome = function (s, i) {
  var j = 1;

  while (i + j < s.length && s[i] === s[i + j]) {
    j++;
  }

  var n = 0;
  while (
    i - n >= 0 &&
    i + (j - 1) + n < s.length &&
    s[i - n] === s[i + (j - 1) + n]
  ) {
    n = n + 1;
  }

  return s.substring(i - (n - 1), i + (j - 1) + n);
};

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  var result = "";
  for (var i = 0; i < s.length; i++) {
    var resulti = findPalindrome(s, i) || "";

    if (resulti.length > result.length) {
      result = resulti;
    }
  }

  return result;
};

---

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

题目：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

解题思路：

将两个数组合并成一个数组后排序。

如果合并后的数组的长度是偶数，取中间两个数的平均数；如果合并后的数组的长度是奇数，取中间的数。

解答：

var sortNumber = function (a, b) {
  return a - b;
};

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  var nums = nums1.concat(nums2).sort(sortNumber);
  var isEvenNum = nums.length % 2 === 0;
  var result = 0;
  var len = nums.length;

  if (isEvenNum) {
    result = (nums[len / 2 - 1] + nums[len / 2]) / 2;
  } else {
    result = nums[(len - 1) / 2];
  }

  return result;
};

---

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays