Coding-everyday

1. 求质数因子
2. 约瑟夫环，轮流报数，然后退出
3. 移动零-Leetcode-283
4. 拼接最小字典序
5. 两串旋转问题，判断是否互为旋转词
6. 句子逆序
7. 反转字符串数组
8. 字符串移位问题
9. 判断数字是否为回文数
10. 不下降序列,求A[i]==i
11. 二进制中1的个数
12. 二进制连续1的个数
13. 求最小公倍数
14. 二进制和十进制之间转换
15. 最大连续数列和
16. 从1到n整数中1出现的次数
17. 从1到n整数中2出现的次数
18. 顺时针旋转矩阵
19. 顺时针打印矩阵
20. 数组中出现次数超过一半的数字
21. 求累加和，不能用乘除法及判断语句
22. 求使一个数变成斐波那契数的最小的步数
23. 波特兰表达式
24. 数据流找到中位数
25. 无重复字符的最长子串
26. 从左到右、从上到下，递增数组的查找
27. 二进制间距

# 编程基础

# 1. 求质数因子

如：180 => 2 2 3 3 5

def getPrimeFactor(n):
  res = []
  i = 2
  
  while n >= 2:
  # while n != 1:
    if n % i == 0:
      res.append(i)
      n = n // i
    else:
      i += 1

  return res

function getPrimeFactor(num) {
  let i = 2;
  const res = [];

  while (num >= 2) {
    if (num % i === 0) {
      res.push(i);
      num = num / i;
    } else {
      i += 1;
    }
  }
  return res;
}

// 或者
function getPrimeFactor(num) {
  let i = 2;
  const res = [];

  while (num >= 2) {
    while (num % i === 0) {
      res.push(i);
      num = num / i;
    } 
    i += 1;
  }
  return res;
}

# 2. 约瑟夫环，轮流报数，然后退出

题目描述：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。求最后一个出列的人的编号。

模拟这个过程就可以得出结果（时间复杂度O(n*m)）

  def solution(n, m):
    if n < 1: return -1

    con = [i for i in range(n)]
    final = -1
    start = 0

    while con:
      k = (start + m - 1) % n
      final = con.pop(k)
      n -= 1
      start = k

    return final

function joseph(n, m) {
  if (n < 1) return -1;
  let final = -1;
  let start = 0;
  let list = Array.from({ length: n }, (_, i) => i);

  let k;

  while (list.length) {
    k = (start + m - 1) % n;
    final = list.pop(k);
    n -= 1;
    start = k;
  }
  return final;
}

数学递归（时间复杂度O(n)）

def solution(n, m):
  s = 0
  for i in range(2, n + 1):
    s = (s + m) % i
  return s

def solution(n, m):
  if n == 1: return 0
  if n == 0: return -1 
  return (solution(n-1, m) + m) % n

解释：假设现在是6个人（编号从0到5）报数，报到（2-1）的退出，即 < m=2>。那么第一次编号为1的人退出圈子，从他之后的人开始算起，序列变为2,3,4,5,0，即问题变成了这5个人报数的问题，将序号做一下转换： 2 ->0 3 ->1 4 ->2 5 ->3 0 ->4

规律如下：

(0 + 2) % 6 = 2
(1 + 2) % 6 = 3
(2 + 2) % 6 = 4
(3 + 2) % 6 = 5
(4 + 2) % 6 = 0

即 old_number = ( new_number + value ) % old_sum

现在假设x为0,1,2,3,4的解，x’设为那么原问题的解（这里注意，2,3,4,5,0的解就是0,1,2,3,4,5的解，因为1出去了，结果还是一个），根据观察发现，x与x’关系为x’=(x+m)%n，因此只要求出x，就可以求x’。x怎么求出呢？继续推导吧。0,1,2,3,4,同样是第二个1出列，变为（2,3,4,0），转换下为 2 ->0 3 ->1 4 ->2 0 ->3 很简单，同样的道理，公式又出来了，x=(x+m)%5，这里变成5了。即求n-1个人的问题就是找出n-2的人的解，n-2就是要找出n-3，等等因此，就可以回去看上面的推导过程了。

好了，思路出来了，下面写递推公式：令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式

f[1]=0; 
f[i]=(f[i-1]+m)%i; (i>1)

1个人时，最后一个出列的一定是他自己，下标为0
2个人时，最后一个出列的是 ( 0 + m) % 2。若m为奇数，最后一个出列的下标为1；若m为偶数，最后一个出列的下标为0
3个人时，最后一个出列的时 ( f[n-1] + m) % 3。比如 m = 1, 最后一个出列的下标为2；m = 2 时，最后一个出列的下标为2...

参考资料：约瑟夫环问题递归解法的一点理解 (opens new window)

# 3. 移动零-Leetcode-283

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:
1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

1. 用一个变量k，表示数组的前k项都是非0元素，初始值为0

2. 依次遍历数组，如果当前值item不为0，赋值给nums[k]，同时k++。

3. 再从k遍历到数组尾部，将k位置以后的全部赋值为0。

var moveZeroes = function(nums) {
    // let _list = []
    
    // for (let item of nums) {
    //     if (item != 0) {
    //         _list.push(item)
    //     }
    // }
    // for (let i = 0; i < nums.length; i++) {
    //     nums[i] = _list[i] || 0
    // }

    // 原地(in place)解决该问题
    // 空间复杂度O(n) => O(1)
    let k = 0 // nums中, [0...k)的元素均为非0元素

    for (let item of nums) {
        if (item) {
            nums[k++] = item
        }
    }
    for (let i = k; i < nums.length; i ++) {
        nums[i] = 0
    }
};

python实现：

def fn(nums):
  k = 0
  
  for item in nums:
    if item:
      nums[k]=item
      k+=1
      
  for i in range(k, len(nums)):
    nums[i]=0

  return nums

# 4. 拼接最小字典序

对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串
是所有可能的拼接中字典序最小的。

给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。

测试样例：
[“abc”,”de”],2

“abcde”

最优解时间复杂度为O(N*log(N))，实质是一种排序

单独对每个字符串进行比较是错误的，比如’b’ 和’ba’比较，实际应为’bab’
应该按照这样的方式，如果str1+str2<str2+str1，则str1在前。不是比较两个单独字符串各自的字典顺序，而是两个字符串彼此拼接之后的结果。

function findSmallest(strs) {
  function sortFunc(a, b) {
    const s1 = a + b;
    const s2 = b + a;
    if (s1 > s2) {
      return 1;
    } else if (s1 < s2) {
      return -1;
    }
    return 0;
  }

  strs.sort(sortFunc);
  return strs.join("");
}

from functools import cmp_to_key

def tcmp(a, b):
  s1 = a + b
  s2 = b + a
  
  if s1 > s2: return 1
  elif s1 < s2: return 0
  else: return -1


def findSmallest(strs):
  res = sorted(strs, key = cmp_to_key(tcmp))
  return ''.join(res)

# 5. 两串旋转问题，判断是否互为旋转词

如果一个字符串 str，把字符串 str 前面的任意部分挪到后面形成的字符串叫做 str 的旋转词。给定两个字符串，判断是否互为旋转词。

比如 a="abcd", b="cdab", true a="abcd", b="bcad", false

def chkRotation(A, B):
  n = len(A)
  m = len(B)

  if n != m: return False

  if B in A + A: return True
  else: return False

# 6. 句子逆序

将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I” 所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符

function reverseSen(str) {
  const list = str.split(/\s/);
  list.reverse();
  return list.join(" ");
}

def reverseSentence(A):
  a = A.split()
  a.reverse()
  return ''.join(a)

# 7. 反转字符串数组

首尾指针自己实现

注意JS中s='abc'，s[0]=1，s并不会改变。

function reverStr(s) {
  let list = s.split("");
  let start = 0;
  let end = list.length - 1;

  while (start < end) {
    [list[start], list[end]] = [list[end], list[start]];
    start += 1;
    end -= 1;
  }

  return list.join("");
}

def reverseString(s):
  beg = 0
  end = len(s) - 1

  while beg < end:
    s[beg], s[end] = s[end], s[beg]
    beg += 1
    end -= 1

  return s

# 8. 字符串移位问题

对于一个字符串，请设计一个算法，将字符串的长度为len的前缀平移到字符串的最后。

给定一个字符串A和它的长度，同时给定len，请返回平移后的字符串。

测试样例： "ABCDE",5,3

返回："DEABC"

思路：

前半边逆序，后半边也逆序，整个字符也逆序，最后即为结果

YX = (X^TY^T)^T

字符串移位问题

def stringTranslation(A, n, len):
  str1 = A[:len]
  str2 = A[len:]

  A = str1[::-1] + str2[::-1]

  return A[::-1]

# 9. 判断数字是否为回文数

首尾指针

def isPlain(x):
  if x < 0: return False
  s = str(x)

  beg, end = 0, len(s) - 1

  while beg < end:
    if s[beg] == s[end]:
      beg += 1
      end -= 1
    else:
      return False

  return True

# 10. 不下降序列,求`A[i]==i`

从头遍历，如果A[i]<i,i+=1；
如果A[i]>i, 则令i=A[i]，跳过A[i]…i个元素；
例如2 2 2 4 5，A[0]=2>0，则i应跳到2位置；
也就是前面的数很大可以跳，前面的数很小不敢跳，说不定下一个就是要找的数

def findMagicIndex(A):
  n = len(A)
  i = 0

  while i < n:
    if A[i] == i:
      return True
    elif A[i] < i:
      i += 1
    else:
      i = A[i]

  return False

# 11. 二进制中1的个数

方式一：

def numberOf1(n):
  count = 0

  for i in range(32):
    if n & 1:
      count += 1
    n >>= 1

  return count

方式二：

def numberOf1(n):
  count = 0

  if n < 0:
    n = n & 0xffffffff

  while n:
    if n & 1:
      count += 1
    n >>= 1

  return count

因为python的int是无限精度的，c++的int是32为的，所以python的负数相当于前面有无限个1，要对python的负数做处理实际上是把python无限长度的负数限制在32位

# 12. 二进制连续1的个数

功能: 求一个byte数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1

def fn(n):
  res = 0
  while n:
    count = 0
    
    while n and n & 1:
      count += 1
      n >>= 1

    res = max(res, count)
    n >>= 1

  return res

# 13. 求最小公倍数

最小公倍数就是两数乘积除以最大公约数

function greatestCommonDivisor(a, b) {
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}

function leastCommonMultiple(a, b) {
  return (a * b) / greatestCommonDivisor(a, b);
}

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

def fn(a, b):
  return a * b // (gcd(a, b))

# 14. 二进制和十进制之间转换

二进制转十进制：比如二进制数111，n=’111’，从右边开始，2的位数次方累加右边第一位：n[3-0-1] * 2^0 = 1 右边第二位：n[3-1-1] * 2^1 = 2 右边第三位：n[3-2-1] * 2^2 = 4

十进制转二进制：不断除以2取余（商接着除），直到商为0，将余数倒过来。比如 10,10/2=5 余0 5/2=2 余1 2/2=1 余0 1/2=0 余1 所以是1010

function two2ten(n) {
  n = `${n}`;
  const len = n.length;
  let res = 0;
  for (let i = 0; i < len; i++) {
    res += Math.pow(2, i) * n[len - i - 1];
  }
  return res;
}

# 二进制数从右向左，每位数乘以2的次方，然后相加求和即可。
def two2ten(n):
  n = str(n)
  nLen = len(n)
  res = 0

  for i in range(nLen):
    res += int(n[nLen - i - 1]) * pow(2, i)

  return res

# 十进制数除2取余，商继续除2取余，直到商为0，所有余数逆顺即可

def ten2two(n):
  res = []
  res.append(str(n % 2))

  while n // 2 != 0:
    n = n // 2
    res.append(str( n % 2))

  res.reverse()

  return int(''.join(res))

JS实现：

// 十进制转二进制
function dec2Bin(n) {
  const res = []
  res.push(n % 2)
  while (parseInt( n / 2, 10)) {
    n = parseInt(n / 2, 10)
    res.push(n % 2)
  }

  res.reverse()
  return parseInt(res.join(''))
}


// 十进制转16进制，其实只是把2换成了16
function dec2Hex(n) {
  const res = []
  res.push(n % 16)
  while (parseInt( n / 16 ) !== 0) {
    n = parseInt(n / 16, 10)
    res.push(n % 16)
  }

  res.reverse()
  return parseInt(res.join(''))
}

注意 JS 是list.join('')，python是''.join(list)

其他解法：

// 10进制转16进制
function int2Hex(num) {
  if (num == 0){
    return '0'
  }
  const HEXS = '0123456789abcdef'
  let hex = '';
  while (num) {
    hex = HEXS[num % 16] + hex;
    num = Math.floor(num / 16)
  }
  return hex;
}


// 10进制转2进制
function int2Binary(num) {
  if (num == 0) {
    return '0'
  }
  const NUMBERS = '01'
  let result = ''
  while (num) {
    result = NUMBERS[num % 2]+ result;
    num = Math.floor(num / 2)
  }
  return result;
}

# 15. 最大连续数列和

题目描述：对于一个有正有负的整数数组，请找出总和最大的连续数列。

测试样例：输入：[1, 2, 3, -6, 1] 输出：6

def solution(A):
  res = A[0] # 当前所有子数组和的最大值
  temp = A[0] # 包含A[i]的连续数组的最大值

  for i in range(1, len(A)):
    temp = max(temp + A[i], A[i])
    res = max(res, temp)

  return res

# 16. 从1到n整数中1出现的次数

题目描述： 1~13中包含1的数字有1、10、11、12、13，因此共出现6次。

def getNum1(n):
  res = 0
  i = 1

  while i <= n:
    a = n // i
    b = n % i

    # 之所以补8，是因为当百位为0，则 a/10==(a+8)/10，
    # 当百位 >= 2，补8会产生进位位，效果等同于 (a/10+1)
    res += ((a+8) // 10) * i + (a % 10 == 1) * (b + 1)
    i *= 10

  return res

解释：

如果第i位（自右至左，从1开始标号）上的数字为0，则第i位可能出现1的次数由更高位决定（若没有高位，视高位为0），等于更高位数字 * 当前位数的权重10^(i−1) 。
如果第i位上的数字为1，则第i位上可能出现1的次数不仅受更高位影响，还受低位影响（若没有低位，视低位为0），等于更高位数字 * 当前位数的权重10^(i−1) +（低位数字+1）。
如果第i位上的数字大于1，则第i位上可能出现1的次数仅由更高位决定（若没有高位，视高位为0），等于（更高位数字+1）* 当前位数的权重10^(i−1) 。

首先要知道以下的规律：

从 1 至 10，在它们的个位数中，任意的 X 都出现了 1 次。
从 1 至 100，在它们的十位数中，任意的 X 都出现了 10 次。
从 1 至 1000，在它们的百位数中，任意的 X 都出现了 100 次。
依此类推，从 1 至 10^i，在它们的左数第二位（右数第 i 位）中，任意的 X 都出现了 10^(i−1) 次。

以 n=2593,X=5 为例来解释如何得到数学公式

3 < X，则个位上可能出现的X的次数仅由更高位决定，等于更高位数字（259） * 10^(1-1)=259
9 > X，则十位上可能出现的X的次数仅由更高位决定，等于更高位数字（25+1） * 10^(2-1)=260
5 == X，则百位上可能出现X的次数不仅受更高位影响，还受低位影响，等于更高位数字（2）* 10^(3-1)+（93+1）=294
2 < X，则千位上可能出现的X的次数仅由更高位决定，等于更高位数字（0）* 10^(4-1)=0）。

# 17. 从1到n整数中2出现的次数

def countNumberOf2s(n):
  res = 0
  i = 1

  while i <= n:
    a = n // i
    b = n % i
    res += ((a + 7) // 10) * i + (b + 1) * (a % 10 == 2)
    i *= 10

  return res

# 18. 顺时针旋转矩阵

原地旋转，不允许新建矩阵：

def rotateM(mm):
  le = len(mm)

  for i in range(le):
    for j in range(i + 1, le):
      mm[i][j], mm[j][i] == mm[j][i], mm[i][j]

  for i in range(le):
    mm[i] == mm[i][::-1]
  return mm

直观解释：

1 2 3      1 4 7      7 4 1
4 5 6  =>  2 5 8  =>  8 5 2
7 8 9      3 6 9      9 6 3

允许新建矩阵：

def rotateM(mm):
  n = len(mm)
  m = len(mm[0])
  res = [[0 for i in range(n)] for j in range(m)]

  for i in range(n):
    for j in range(m):
      res[j][n - i - 1] = mm[i][j]

  return res

旋转之后总结规律：res[j][n-i=1] = mm[i][j]

# 19. 顺时针打印矩阵

题目描述：输入一个矩阵，按照从外到里以顺时针的顺序依次打印出每一个数字。

def printMatrix(matrix):
  res = []

  while matrix:
    res += matrix.pop(0)

    if matrix and matrix[0]:
      for row in matrix:
        res.append(row.pop())

    if matrix:
      res += matrix.pop()[::-1]

    if matrix and matrix[0]:
      for row in matrix[::-1]:
        res.append(row.pop(0))

  return res

# 20. 数组中出现次数超过一半的数字

思路：

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。
在遍历数组时保存两个值：一是数组中一个数字，一是次数。
遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；
若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可

次数归零，就是前面的都不算数，正好抵消，要求的数如果存在一定在后面的数中。

def moreThanHalfNum(arr):
  res = [arr[0], 1]

  for i in arr[1:]:
    if i == res[0]:
      res[1] += 1
    else:
      res[1] -= 1
      if res[1] < 0:
        res = [i, 0]

  return res[0] if res[1] > 0 else 0

# 21. 求累加和，不能用乘除法及判断语句

思路：不能循环就只能递归了

def getSum(n):
  return n and (n + getSum(n - 1))

# 22. 求使一个数变成斐波那契数的最小的步数

def solution(n):
  s = [0, 1]

  while n > s[-1]:
    s.append(s[-1] + s[-2])
  
  return min(s[-1] - n, n - s[-2])

解释：

就是把比n大的最后一个斐波那契数字作为终止条件，不断添加数组；
然后比较最后一个数字与n的差值和倒数第二个数字与n的差值，取较小值。

# 23. 波特兰表达式

思路：

用栈，从左到右遍历原数组，遇到数值就入栈，遇到运算符就弹出两个数，用表达式计算它们，然后把结果入栈，遍历完数组，栈中只剩一个最后的结果，弹出即可。

def evalRPN(A):
  s = []
  res = 0

  while A:
    q = A.pop(0)
    if q in ['+', '-', '*', '/']:
      ope1 = int(s.pop())
      ope2 = int(s.pop())
      if q == '+':
        res = ope2 + ope1
      elif q == '-':
        res = ope2 - ope1
      elif q == '*':
        res = ope2 * ope1
      else:
        res = ope2 // ope1
      s.append(res)
    else:
      s.append(q)
  return s.pop()


# 测试
evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])  # 22

# 24. 数据流找到中位数

使用两个堆：

小根堆：large保存大的半数的数据
大根堆：small保存小的半数的数据
获取中位数的时间复杂度为O（1），插入一个数据的时间复杂度为O（log(n)）

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

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

function lengthOfLongestSubstring(s) {
  let left = 0;
  let lookup = new Set();
  let curLen = 0;
  let maxLen = 0;

  for (let i = 0; i < s.length; i++) {
    curLen += 1;

    while (lookup.has(s[i])) {
      lookup.delete(s[left]);
      left += 1;
      curLen -= 1;
    }
    if (curLen > maxLen) maxLen = curLen;
    lookup.add(s[i]);
  }

  return maxLen;
}

# 26. 从左到右、从上到下，递增数组的查找

var findNumberIn2DArray = function(matrix, target) {
  if (!matrix.length) return false;
  if (!matrix[0].length) return false;

  const n = matrix.length;
  const m = matrix[0].length;
  let i = 0;
  let j = m - 1;

  while (i <= n - 1 && j >= 0) {
    if (matrix[i][j] < target) {
      i += 1;
    } else if (matrix[i][j] > target) {
      j -= 1;
    } else {
      return true;
    }
  }

  return false;
};

# 27. 二进制间距

给定一个正整数 n，找到并返回 n 的二进制表示中两个相邻 1 之间的最长距离。如果不存在两个相邻的 1，返回 0 。

如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此相邻。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。

输入：n = 22
输出：2
解释：22 的二进制是 "10110" 。
在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。
第一对相邻的 1 中，两个 1 之间的距离为 2 。
第二对相邻的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。

var binaryGap = function(n) {
let last = 30;
  let res = 0;
  let i = 0;
  while (n) {
    if (n & 1) {
      res = Math.max(res, i - last);
      last = i;
    }
    n >>= 1;
    i += 1;
  }
  return res;
};

← 剪绳子,使乘积最大堆栈 →