【当前排名67359】挑战leetcode进入前1w名

李恒道

https://leetcode.cn/problems/shortest-palindrome/submissions/591347819/
竟然是KMP题，没想到
真妙

const generateNext = (str) => {
  const arr = [-1];
  let j = -1;
  for (let i = 1; i < str.length; i++) {
    const char = str[i];
    while (j >= 0 && char != str[j + 1]) {
      j = arr[j];
    }
    if (char == str[j + 1]) {
      j++;
    }
    arr[i] = j;
  }
  return arr;
};
const shortestPalindrome = (s) => {
  const rev_s = s.split("").reverse().join("");
  const next = generateNext(s + "#" + rev_s);
  return rev_s+s.substring(next.pop()+1)
};

李恒道

https://leetcode.cn/problems/transpose-file/submissions/591347880/
gpt过了，我操

#!/bin/bash

input_file="file.txt"

awk '
{
    for (i=1; i<=NF; i++)  {
        a[NR,i] = $i
    }
}
NF>p { p = NF }
END {
    for(j=1; j<=p; j++) {
        str=a[1,j]
        for(i=2; i<=NR; i++){
            str=str" "a[i,j]
        }
        print str
    }
}' $input_file

李恒道

https://leetcode.cn/problems/word-frequency/submissions/591347896/
又试了一下
gpt精准度真的不错...

tr -s ' ' '\n' < words.txt | sort | uniq -c | sort -nr | awk '{print $2, $1}'

李恒道

https://leetcode.cn/problems/compare-version-numbers/submissions/591524367/
简单题，k了

var compareVersion = function(version1, version2) {
  version1=version1.split('.').map((item)=>parseInt(item))
  version2=version2.split('.').map((item)=>parseInt(item))
  for (let index = 0; index < Math.max(version1.length,version2.length); index++) {
    const num1 = version1[index]??0;
    const num2 = version2[index]??0;
    if(num1<num2){
      return -1
    }
    if(num1>num2){
      return 1
    }
  }
  return 0
};

李恒道

https://leetcode.cn/problems/combination-sum-iii/submissions/591526048/
回溯题，不想用位运算计算

var combinationSum3 = function (k, n) {
  const ban = new Array(10).fill(false);
  const ans = [];
  const dfs = (times, total, pos) => {
    if (times == 0 && total == 0) {
      const list = ban
        .map((val, index) => {
          if (val) {
            return index;
          } else {
            return -1;
          }
        })
        .filter((item) => item !== -1);
      ans.push(list);
      return;
    }
    if (times == 0) {
      return;
    }
    if (total == 0) {
      return;
    }
    for (let index = pos; index < 10; index++) {
      if (!ban[index]) {
        ban[index] = true;
        dfs(times - 1, total - index, index + 1);
        ban[index] = false;
      }
    }
  };
  dfs(k, n, (pos = 1));
  return ans;
};

李恒道

https://leetcode.cn/problems/number-of-changing-keys/submissions/591570953/
打卡题，今天懒得做了

var countKeyChanges = function(s) {
  s= s.toLowerCase();
  let ans=0
  for (let index = 0; index < s.length-1; index++) {
    ans+=s[index]==s[index+1]?0:  1
  }
  return ans
};

李恒道

https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/
讲道理，题目写的太抽象了

var validSubstringCount = function (word1, word2) {
  let list = new Array(26).fill(0);
  for (const word of word2) {
    list[word.charCodeAt() - 97]++;
  }
  let less = 0;
  for (const value of list) {
    if (value !== 0) {
      less++;
    }
  }
  let left = 0;
  let  ans=0
  for (let index = 0; index < word1.length; index++) {
    const word = word1[index].charCodeAt() - 97;
    list[word]--;
    if (list[word] == 0) {
      less--;
    }
    while (less == 0) {
      const outChar = word1[left].charCodeAt() - 97;
      left++;
      if (list[outChar] == 0) {
        less++;
      }
      list[outChar]++;
    }
    ans+=left
  }
  return ans
};

李恒道

https://leetcode.cn/submissions/detail/592007875/
一样的题

var validSubstringCount = function (word1, word2) {
  let list = new Array(26).fill(0);
  for (const word of word2) {
    list[word.charCodeAt() - 97]++;
  }
  let less = 0;
  for (const value of list) {
    if (value !== 0) {
      less++;
    }
  }
  let left = 0;
  let  ans=0
  for (let index = 0; index < word1.length; index++) {
    const word = word1[index].charCodeAt() - 97;
    list[word]--;
    if (list[word] == 0) {
      less--;
    }
    while (less == 0) {
      const outChar = word1[left].charCodeAt() - 97;
      left++;
      if (list[outChar] == 0) {
        less++;
      }
      list[outChar]++;
    }
    ans+=left
  }
  return ans
};

李恒道

https://leetcode.cn/problems/find-the-key-of-the-numbers/submissions/592403977/
简单题，打个卡

var generateKey = function (num1, num2, num3) {
  const generate = (num) => {
    num = num + "";
    while (num.length < 4) {
      num = "0" + num;
    }
    return num;
  };
  num1 = generate(num1);
  num2 = generate(num2);
  num3 = generate(num3);
  let ans = "";
  for (let index = 0; index < 4; index++) {
    const char1 = parseInt(num1[index]);
    const char2 = parseInt(num2[index]);
    const char3 = parseInt(num3[index]);
    ans=ans+Math.min(char1,char2,char3)
  }
  return parseInt(ans)
};

李恒道

https://leetcode.cn/problems/sort-an-array/submissions/592498000/
快排竟然没过去
归并过了...

var sortArray = function (nums) {
  const mergeSort = (l, r) => {
    if (l == r) {
      return [nums[l]];
    }
    const center = l + Math.floor((r - l) / 2);
    const arr1 = mergeSort(l, center);
    const arr2 = mergeSort(center + 1, r);
    return merge(arr1, arr2);
  };
  const merge = (arr1, arr2) => {
    const result = [];
    let p1 = 0;
    let p2 = 0;
    while (p1 < arr1.length && p2 < arr2.length) {
      if (arr1[p1] <= arr2[p2]) {
        result.push(arr1[p1++]);
      } else {
        result.push(arr2[p2++]);
      }
    }
    while (p1 < arr1.length) {
      result.push(arr1[p1++]);
    }
    while (p2 < arr2.length) {
      result.push(arr2[p2++]);
    }
    return  result
  };
  return mergeSort(0,nums.length-1)
};