jie's notes

Appearance

leetcode-contest ​

2023-04-16 ​

6376. 一最多的行 ​

js
// 2023-04-16: 10:30

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var rowAndMaximumOnes = function(mat) {
    let max = -1, row = -1;
    mat.forEach((r, i) => {
        let oneCount = r.filter(x => x === 1).length;
        if (oneCount > max) {
            max = oneCount;
            row = i;
        }
    })
    return [row, max];
};

// mat = [[0,1],[1,0]]

// mat = [[0,0,0],[0,1,1]]

mat = [[0,0],[1,1],[0,0]]

console.log(rowAndMaximumOnes(mat))

6350. 找出可整除性得分最大的整数 ​

js
/**
 * @param {number[]} nums
 * @param {number[]} divisors
 * @return {number}
 */
var maxDivScore = function(nums, divisors) {
    let newDivisors = Array.from(new Set(divisors)).sort((a, b) => a - b);
    let map = new Map();
    for(const d of nums) {
        for(const div of newDivisors) {
            if (d % div === 0) {
                if (map.has(div)) {
                    map.set(div, map.get(div) + 1);
                } else {
                    map.set(div, 1);
                }
            }
        }
    }
    // console.log(map, newDivisors)
    let res = -1, max =  -1;
    newDivisors.forEach(d => {
        if (map.get(d) > max) {
            max = map.get(d);
            res = d;
        }
    });
    if(max === -1) return newDivisors[0];
    return res
};


// nums = [4,7,9,3,9], divisors = [5,2,3]

// nums = [20,14,21,10], divisors = [5,7,5]

// nums = [12], divisors = [10,16]

nums = [73,13,20,6]
divisors = [56,75,83,26,24,53,56,61]

console.log(maxDivScore(nums, divisors))

6375. 构造有效字符串的最少插入数 ​

js
/**
 * @param {string} word
 * @return {number}
 */
var addMinimum = function(word) {
//    console.log(word)
   if(word.length === 0) return 0;
   if(word[0] === 'c') return 2+ addMinimum(word.slice(1));
   if(word[0] === 'b') {
      if(word.length === 1) {
        return 2
      } else if (word.length > 1) {
          if (word[1] === 'c') {
            return 1 + addMinimum(word.slice(2))
          } else {
            return 2 + addMinimum(word.slice(1))
          }
      }
   }
    if(word[0] === 'a') {
        if(word.length === 1) {
            return 2;
        }
        if(word.length >= 2) {
            if(word[1] === 'b') {
                if (word.length>=3 && word[2] === 'c') {
                    return 0 + addMinimum(word.slice(3));
                }else {
                    return 1+ addMinimum(word.slice(2))
                }
            }else if (word[1] === 'a') {
                return 2 + addMinimum(word.slice(1))
            } else if (word[1] === 'c') {
                return 1 + addMinimum(word.slice(2))
            }
        }
    }
};

// word = 'b'

// word = "aaa"

// word = "abc"

// word = "abca"

word = "aaabca"
// 2 2 2

console.log(addMinimum(word))

2022-12-11 ​

6257. 删除每行中的最大值 ​

js
// https://leetcode.cn/contest/weekly-contest-323/
// 20:22 - 21: 10

/**
 * @param {number[][]} grid
 * @return {number}
 */
var deleteGreatestValue = function(grid) {
    let newData = grid.map(items=>[...items].sort((a,b)=>b-a))
    // console.log(newData)
    if (grid.length ==0 || grid[0].length==0){
        return 0
    }
    let res = 0;
    let row = newData.length, col = newData[0].length;
    for(let i=0;i<col;i++){
        let temp = -1
        for(let j=0;j<row;j++){
            // console.log(j,i, grid[j][i])
            temp = Math.max(temp,newData[j][i])
        }
        // console.log(temp)
        res += temp
    }
    return res;
};

// grid = [[1,2,4],[3,3,1]]

grid = [[10]]

console.log(deleteGreatestValue(grid))

6258. 数组中最长的方波 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSquareStreak = function(nums) {
    let countSet = new Set(nums);
    let arr = Array.from(countSet).sort((a,b)=>a-b)
    // console.log(arr, countSet)
    let res =0
    let hasUsed = new Set();
    for(const v of arr){
        if(!hasUsed.has(v)){
            let count = 0
            let cur = v
            while(!hasUsed.has(cur) && countSet.has(cur)){
                // console.log("--",cur)
                hasUsed.add(cur);
                cur = cur * cur;
                count++;
            }
            res = Math.max(res, count);
        }
    }

    return res>=2? res: -1;

};

// nums = [4,3,6,16,8,2]
nums = [2,3,5,6,7]

console.log(longestSquareStreak(nums))

6259. 设计内存分配器 ​

js
/**
 * @param {number} n
 */
var Allocator = function(n) {
    this.arr = new Array(n).fill(null);
    this.edgeMap = new Map();
};

/** 
 * @param {number} size 
 * @param {number} mID
 * @return {number}
 */
Allocator.prototype.allocate = function(size, mID) {
    let left = 0;
    let can = false;
    while(left< this.arr.length){
        let right = left;
        while(right<this.arr.length && right<= (left + size - 1) && this.arr[right]=== null){
            right++
        }
        if (right-left === size){
            can = true;
            break;
        }
        left = right+ 1
    }
    if (can) {
        for(let i=left;i<left+size;i++){
          this.arr[i] = mID
        }
        let oldEdge = this.edgeMap.get(mID) || [left,left+size-1]
        let newEdge = [Math.min(oldEdge[0],left), Math.max(oldEdge[1],left+size-1)]
        this.edgeMap.set(mID, newEdge)
      return left;
    }
    return -1
};

/** 
 * @param {number} mID
 * @return {number}
 */
Allocator.prototype.free = function(mID) {
    if (!this.edgeMap.has(mID)) {
        return 0
    }
    let count = 0
    let edge = this.edgeMap.get(mID)
    for(let i=edge[0];i<=edge[1];i++){
        if(this.arr[i]=== mID){
            this.arr[i] = null
            count++
        }
    }
    this.edgeMap.delete(mID)
    return count;

};

/**
 * Your Allocator object will be instantiated and called as such:
 * var obj = new Allocator(n)
 * var param_1 = obj.allocate(size,mID)
 * var param_2 = obj.free(mID)
 */

2022-12-05 ​

6253. 回环句 ​

js
// https://leetcode.cn/contest/weekly-contest-322/
// 12-04-23:36 - 00:31

/**
 * @param {string} sentence
 * @return {boolean}
 */
 var isCircularSentence = function(sentence) {
    let arr= sentence.split(/\s+/g)
    // console.log(arr)
    if(arr[0][0]!=arr[arr.length-1][(arr[arr.length-1].length)-1]){
        return false
    }
    for(let i=0;i<arr.length;i++){
        if(i+1<arr.length){
            if(arr[i][(arr[i].length)-1]!=arr[i+1][0]){
                return false
            }
        }
    }
    return true
};

// sentence = "leetcode exercises sound delightful"
sentence = "eetcode"
console.log(isCircularSentence(sentence))

6254. 划分技能点相等的团队 ​

js
/**
 * @param {number[]} skill
 * @return {number}
 */
var dividePlayers = function (skill) {
  let sum = skill.reduce((pre, cur) => pre + cur, 0);
  let average = sum / (skill.length / 2);
  if (sum % (skill.length / 2) != 0) {
    return -1;
  }
  // console.log(sum, average)
  let countMap = new Map();
  for (const v of skill) {
    countMap.set(v, (countMap.get(v) || 0) + 1);
  }
  // console.log(countMap)
  let res = 0;
  let hasUsedSet = new Set();
  for (const [key, v] of countMap.entries()) {
    // console.log(key,v)
    if (!hasUsedSet.has(key)) {
      if (key * 2 === average) {
        if (v % 2 == 0) {
          hasUsedSet.add(key);
          // console.log(key, v)
          res += key * key * (v / 2);
        } else {
          return -1;
        }
        continue;
      }
      if (!hasUsedSet.has(average - key) && countMap.get(average - key) === v) {
        // console.log("--1-")
        hasUsedSet.add(key).add(average - key);
        res += key * (average - key) * v;
      } else {
        // console.log("-2--", key,v,hasUsedSet.has(average-key),countMap.get(average-key))
        return -1;
      }
    }
  }
  return res;
};

// skill = [3,2,5,1,3,4]
// skill = [3,4]
// skill = [1,1,2,3]
skill = [2, 2, 2, 2];
console.log(dividePlayers(skill));

6255. 两个城市间路径的最小分数 ​

js
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var minScore = function (n, roads) {
    let pathArr = new Array(n + 1).fill(0)
    for (let i = 0; i < pathArr.length; i++) {
        pathArr[i] = []
    }
    for (const [p1, p2, d] of roads) {
        // console.log(p1,p2,d)
        let arr1 = pathArr[p1];
        arr1.push([p2, d])
        let arr2 = pathArr[p2];
        arr2.push([p1, d])
    }
    // console.log(pathArr)
    let posMinDist = new Map();
    for (let i = 1; i <= n; i++) {
        let min = Infinity;
        for (const [p, d] of pathArr[i]) {
            min = Math.min(min, d)
        }
        posMinDist.set(i, min)
    }
    // console.log(posMinDist)

    let usedSet = new Set();
    let sta = [1];
    let res = posMinDist.get(1);
    while (sta.length > 0) {
        let cur = sta.pop();
        usedSet.add(cur)
        for (const [p] of pathArr[cur]) {
            if (!usedSet.has(p)) {
                sta.push(p)
                usedSet.add(p)
                res = Math.min(res, posMinDist.get(p))
            }
        }

    }
    return res;
};

// n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
// n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]

n =
    20
roads =
    [[18, 20, 9207], [14, 12, 1024], [11, 9, 3056], [8, 19, 416], [3, 18, 5898], [17, 3, 6779], [13, 15, 3539], [15, 11, 1451], [19, 2, 3805], [9, 8, 2238], [1, 16, 618], [16, 14, 55], [17, 7, 6903], [12, 13, 1559], [2, 17, 3693]]

console.log(minScore(n, roads))

2022-11-27 ​

6245. 找出中枢整数 ​

js
/**
 * @param {number} n
 * @return {number}
 */
 var pivotInteger = function(n) {
   const getSum = (start ,end)=>{
    return (start + end)/2 * (end - start +1)
   }
   let left=1; right = n
   let mid
   while(left<=right){
    mid = Math.floor((left+right)/2)
    let leftSum = getSum(1, mid);
    let rightSum = getSum(mid, n);
    // console.log(left, leftSum, right, rightSum, mid)
    if(leftSum == rightSum){
        return mid
    } else if (leftSum < rightSum) {
        left = mid +1
    }else {
        right = mid -1
    }
   }
   return -1
};

6246. 追加字符以获得子序列 ​

js
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
 var appendCharacters = function(s, t) {
    let left = 0;
    for(let i=0;i<s.length;i++){
        if(left<t.length && s[i]==t[left]){
             left++
        }
    }
    return t.length - left
};

6247. 从链表中移除节点 ​

js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var removeNodes = function(head) {
    if (!head){
        return head
    }
    let nodeValueList = []
    let cur= head;
    while(cur){
        nodeValueList.push(cur.val)
        cur=cur.next
    }
    // console.log(nodeValueList)
    // 从当前索引到结尾的最大值
    let maxStack = new Array(nodeValueList.length).fill(-1)
    for(let i=maxStack.length-1;i>=0;i--){
        if(i===maxStack.length-1){
            maxStack[i] = nodeValueList[i]
        }else {
            maxStack[i] =Math.max(maxStack[i+1], nodeValueList[i])
        }
    }
    // console.log(maxStack)
    let numHead = {
        val: 0,
        next: head,
    }
    cur = numHead;
    let index = 0
    while(cur && cur.next){
        if(cur.next && cur.next.val === maxStack[index]){
            cur=cur.next;
        } else {
            cur.next = cur.next.next;
        }
        index++
    }
    return numHead.next;
};

2022-07-17 ​

6120. 数组能形成多少数对 ​

js
/**
 * @param {number[]} nums
 * @return {number[]}
 */
 var numberOfPairs = function(nums) {
    let map = new Map()
    for(const v of nums){
        map.set(v,(map.get(v) || 0) + 1)
    }
    let pairs = 0
    let mod = 0
    for(const [key, v] of map){
        // console.log(key,v)
        pairs+= Math.floor(v/2)
        mod += v%2
    }
    return [pairs,mod]

};
// nums = [1,3,2,1,3,2,2]
nums = [0]
// nums = [1,1]
ans = numberOfPairs(nums)
console.log(ans)

6164. 数位和相等数对的最大和 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
 var maximumSum = function(nums) {
    const getBitSum = num=>{
       return  arr= String(num).split('').reduce((all, cur)=>all+Number(cur), 0)
    }
    nums.sort((a,b)=>a-b)
    let map = new Map()
    for(const v of nums){
      let cur= getBitSum(v)
      let temp = map.get(cur) || []
      temp.push(v)
      map.set(cur, temp)
    }
    // console.log(nums, map)
    let res =  -1
    for(const [key, arr] of map){
       if(arr.length >=2){
        res = Math.max(res, arr[arr.length-1] + arr[arr.length-2])
       }
    }
    return res;
};
// nums = [18,43,36,13,7]
nums = [10,12,19,14]
ans = maximumSum(nums)
console.log(ans)

6121. 裁剪数字后查询第 K 小的数字 ​

js
/**
 * @param {string[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */

var smallestTrimmedNumbers = function(nums, queries) {
    const getTrimNum = (str, trimNum) =>{
       let len = str.length;
       return str.substring(len-trimNum);
    }

    const getTwoStringBig = (str1, str2)=>{
        let len= Math.min(str1.length,str2.length);
        for(let i=0;i<len;i++){
            let a= Number(str1[i])
            let b= Number(str2[i])
            if(a!== b){
                return a-b
            }
        }
        return 0
    }

    // console.log(getTrimNum('12345', 2))
    let maxLen= nums[0].length;
    let dp= new Array(maxLen+1).fill(0)
    for(let i=1; i<=maxLen; i++){
        let tempArr = nums.map(v=>getTrimNum(v, i))
        // console.log(tempArr)
        dp[i] = tempArr;
    }
    // console.log(dp)
    let ans = []
    let sortArrMap = new Map();

    for(const [k, trim] of queries){
        let tempArr= null;
        if(sortArrMap.has(trim)){
           tempArr = sortArrMap.get(trim)
        }else{
            // console.log('--', dp[trim])
            // tempArr = [...dp[trim]].sort((a,b)=>a-b)
            tempArr = [...dp[trim]].map((v,index)=>[v,index]).sort((a,b)=>{
                if(a[0]!=b[0]){
                    // console.log(a[0], b[0], getTwoStringBig(a[0], b[0]))
                    return getTwoStringBig(a[0], b[0])
                }else{
                    return a[1]-b[1]
                }
            })
            sortArrMap.set(trim, tempArr);
        }
        // console.log(k, trim , tempArr, dp[trim])
        let res = tempArr[k-1][1]
        ans.push(res)
    }
    return ans;
};

2022-06-12 ​

5259. 计算应缴税款总额 ​

js
// 20220612-10:30-11:30
/**
 * @param {number[][]} brackets
 * @param {number} income
 * @return {number}
 */
 var calculateTax = function(brackets, income) {
    let ans=0;
    for (let i=0; i<brackets.length; i++){
        // console.log(ans,i, brackets[i])
        let [upper, rate] = brackets[i];
        if(i==0){
            let bigger= Math.min(upper,income);
            ans+=bigger*rate/100;
            // console.log("1",ans)
        }else{
                let bigger= Math.min(upper,income);
                let gap=bigger-brackets[i-1][0]
                // console.log("2",gap,rate, gap*rate/100)
                ans+=gap*rate/100;
        }
        if(income<=upper){
            break;
        }

    }
    return ans;
};

// let brackets = [[3,50],[7,10],[12,25]], income = 10
// let brackets = [[1,0],[4,25],[5,50]], income = 2
let brackets = [[2,50]], income = 0
let ans=calculateTax(brackets,income)

console.log(ans)

5270. 网格中的最小路径代价 ​

js
/**
 * @param {number[][]} grid
 * @param {number[][]} moveCost
 * @return {number}
 */
 var minPathCost = function(grid, moveCost) {
    let m= grid.length, n= grid[0].length;
    let dp= new Array(m).fill(0).map(()=>new Array(n).fill(0));
    // console.log(dp)
    for(let i=m-1;i>=0;i--){
        // i:第几行
        if(i==m-1){
            for(let index=0;index<n;index++){
                dp[i][index]=grid[i][index]
            }
            // console.log('-1--',dp)
        }else{
            // index:当前算的第几列
            for(let index=0;index<n;index++){
                let base=Infinity;
                for(let j=0;j<n;j++){
                  const value=grid[i][index]
                  let temp=value+moveCost[value][j]+dp[i+1][j]
                //   console.log("aa",value  ,temp)
                  base=Math.min(base,temp);
                }
                dp[i][index]=base
            }
            // console.log('---',dp)
        }
    }
    // console.log(dp)
    return Math.min(...dp[0])
};

// let grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
let grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
let ans= minPathCost(grid,moveCost)
console.log(ans)

5289. 公平分发饼干 ​

js
/**
 * @param {number[]} cookies
 * @param {number} k
 * @return {number}
 */
 var distributeCookies = function(cookies, k) {
    let ans= 0;
    let du=Infinity;
    let dp=new Array(k).fill(0);
    const dfs=(index)=>{
        if(index==cookies.length){
            let tempArr=[...dp].sort((a,b)=>a-b);
            let tempDu=tempArr[tempArr.length-1]-tempArr[0];
            // console.log(tempDu,tempArr)
            if(tempDu<du){
                ans=tempArr[tempArr.length-1];
                du=tempDu;
            }else if(tempDu==du){
               ans=Math.max(ans,tempArr[tempArr.length-1]);
            }
            return;
        }
        for(let i=0;i<dp.length;i++){
            dp[i]+=cookies[index];
            dfs(index+1);
            dp[i]-=cookies[index];
        }
    }
    dfs(0);
    return ans;
};

// let cookies = [8,15,10,20,8], k = 2
let cookies = [6,1,3,2,2,4,1,2], k = 3
let ans=distributeCookies(cookies,k)
console.log(ans)

6094. 公司命名 ​

js
/**
 * @param {string[]} ideas
 * @return {number}
 */
var distinctNames = function (ideas) {
  let allWordsSet = new Set(ideas);
  // console.log(allWordsSet)
  let ans = 0;
  let len = ideas.length;
  for (let i = 0; i < len; i++) {
    let word1 = ideas[i];
    for (let j = 0; j < len; j++) {
      if (i == j) {
        continue;
      }
      let word2 = ideas[j];
      let newWord1 = word2[0] + word1.substring(1);
      let newWord2 = word1[0] + word2.substring(1);
      if (!allWordsSet.has(newWord1) && !allWordsSet.has(newWord2)) {
        // console.log(newWord1 + "" + newWord2);
        ans++;
      }
    }
  }

  return ans;
};

// ideas = ["coffee", "donuts", "time", "toffee"];
ideas = ["lack","back"]
let ans = distinctNames(ideas);
console.log(ans);

2022-06-11 ​

2299. 强密码检验器 II ​

js
// 10:34
/**
 * @param {string} password
 * @return {boolean}
 */
 var strongPasswordCheckerII = function(password) {
    let res = true;
    if(password.length<8){
        res = false;
    }
    if(!/[a-z]/.test(password)){
        // console.log(1)
        res = false;
    }
    if(!/[A-Z]/.test(password)){
        // console.log(2)
        res = false;
    }
    if(!/[0-9]/.test(password)){
        // console.log(3)
        res = false;
    }
    if(!/[\!\@\#\$\%\^\&\*\(\)\-\+]/.test(password)){
        // console.log(4)
        res = false;
    }
    if(/([\!\@\#\$\%\^\&\*\(\)\-\+\w])\1/.test(password)){
        // console.log(5)
        res = false;
    }
    return res;
};

// let password = "IloveLe3tcode!"
// let password = "ll"
// let password = "IloveLe3tcode!"
let password = "aA0!bB1@@3rbHkB8Puvl"
let ans =strongPasswordCheckerII(password)
console.log(ans)

2300. 咒语和药水的成功对数 ​

js
/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
 var successfulPairs = function(spells, potions, success) {
    const findTarget = (nums, current, target)=>{
        let l=0,r=nums.length;
        while(l<r){
            let mid = Math.floor((l+r)/2);
            if(nums[mid]* current<target){
                l = mid+1;
            }else if(nums[mid]* current>= target){
                r=mid;
            }
        }
        return nums.length-r;
    }

    let map= new Map();
    let arr=[...potions].sort((a,b)=>a-b);
    let ans= []
    for(const v of spells){
        if(map.has(v)){
            ans.push(map.get(v));
        }else{
            let temp = findTarget(arr,v,success);
            map.set(v,temp);
            ans.push(temp);
        }
    }
    return ans;
};

// let spells = [5,1,3], potions = [1,2,3,4,5], success = 7
let spells = [3,1,2], potions = [8,5,8], success = 16
let ans =successfulPairs(spells, potions, success)
console.log(ans)