2023-01-09

[Zheaoli]

2023-01-09

[dreamhunter2333]

#
# @lc app=leetcode.cn id=2283 lang=python3
#
# [2283] 判断一个数的数字计数是否等于数位的值
#

# @lc code=start
from collections import Counter

class Solution:
    def digitCount(self, num: str) -> bool:
        c = Counter(num)
        return num == "".join(
            str(c.get(str(i), "0"))
            for i in range(len(num))
        )

# @lc code=end
print(Solution().digitCount("1210"))

---

微信id: 而我撑伞 来自 vscode 插件

[dreamhunter2333]

#
# @lc app=leetcode.cn id=1814 lang=python3
#
# [1814] 统计一个数组中好对子的数目
#

# @lc code=start
from typing import List
from collections import defaultdict

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        res = 0
        count_map = defaultdict(int)
        for num in nums:
            rev_num = int(str(num)[::-1])
            res += count_map[num - rev_num]
            count_map[num - rev_num] += 1
        return res % (10 ** 9 + 7)
# @lc code=end

---

微信id: 而我撑伞 来自 vscode 插件

[dreamhunter2333]

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
/*
 * @lc app=leetcode.cn id=1817 lang=cpp
 *
 * [1817] 查找用户活跃分钟数
 */

// @lc code=start
class Solution
{
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>> &logs, int k)
    {
        vector<int> res(k, 0);
        unordered_map<int, unordered_set<int>> cache_map;
        for (auto &&log : logs)
        {
            cache_map[log[0]].emplace(log[1]);
        }
        for (auto &&i : cache_map)
        {
            res[i.second.size() - 1] += 1;
        }
        return res;
    }
};
// @lc code=end

---

微信id: 而我撑伞 来自 vscode 插件

[dreamhunter2333]

#include <iostream>
#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=2303 lang=cpp
 *
 * [2303] 计算应缴税款总额
 */

// @lc code=start
class Solution
{
public:
    double calculateTax(vector<vector<int>> &brackets, int income)
    {
        double res = 0;
        int pre_upper = 0;
        for (auto &&bracket : brackets)
        {
            int upper = bracket[0];
            int percent = bracket[1];
            if (income < upper)
            {
                res += (income - pre_upper) * percent;
                break;
            }
            res += (upper - pre_upper) * percent;
            pre_upper = upper;
        }
        return res / 100;
    }
};
// @lc code=end

---

微信id: 而我撑伞 来自 vscode 插件

[lllong33]

#
# @lc app=leetcode.cn id=1716 lang=python3
#
# [1716] 计算力扣银行的钱
#

# @lc code=start
class Solution:
    def totalMoney(self, n: int) -> int:
        # amt_total = 0
        # 1~n range(1, n)
            # i%7 = 1 周一
            # amt_total += week_cnt + i%7
            # week_cnt = 0, i%7 = 0(周末) -> week_cnt += 1
        amt_total = 0 
        week_cnt = 0
        for i in range(1, n+1):
            amt_total += week_cnt + i%7
            if i%7 == 0:
                amt_total += 7
                week_cnt += 1
            # print('i:', i, 'amt_total:', amt_total, 'week_cnt:', week_cnt)
        return amt_total

        # method2
        # for i in range(1, n+1):
        #     amt_total += i//7 + i%7
        #     if i%7 == 0:
        #       amt_total += 7
        # return amt_total
# @lc code=end

# Solution().totalMoney(10)

---

微信id: lllong33 来自 vscode 插件

[lllong33]

#
# @lc app=leetcode.cn id=1631 lang=python3
#
# [1631] 最小体力消耗路径
#
from typing import List
# @lc code=start
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        dsu = DSU()
        r = len(heights)
        c = len(heights[0])
        edges = [] # (diff, pos1, pos2)
        for i in range(r):
            for j in range(c):
                pos = i*c + j
                if i < r-1: # 下节点, 不能越界
                    edges.append((abs(heights[i+1][j] - heights[i][j])
                                  ,pos
                                  ,pos + c
                                  ))
                if j < c-1: # 右节点
                    edges.append((
                        abs(heights[i][j+1] - heights[i][j])
                        ,pos
                        ,pos+1
                    ))
        edges.sort() 
        for diff, pos1, pos2 in edges:
            dsu.union(pos1, pos2)
            if dsu.connection(0, r*c-1):
                return diff
        return 0

class DSU():
    def __init__(self):
        self.par = list(range(10001))

    def find(self, x):
        if x != self.par[x]: # 递归找到最终的父节点
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        self.par[self.find(x)] = self.find(y)

    def connection(self, x, y):
        return self.find(x) == self.find(y)

# ref Solution: https://leetcode.cn/problems/path-with-minimum-effort/solutions/581494/duo-tu-xiang-xi-fen-xi-jie-ti-si-lu-fen-7z89x/    
# @lc code=end

"""
[[4 ,3,4 ,10,5 ,5,9,2]
,[10,8,2 ,10,9 ,7,5,6]
,[5 ,8,10,10,10,7,4,2]
,[5 ,1,3 ,1 ,1 ,3,1,9]
,[6 ,4,10,6,10 ,9,4,6]]
"""

# heights = [[1,2,2],[3,8,2],[5,3,5]]
# M=3
# N=3
# i j
# 0, 0
# pos = i*N+j = 0*3 + 0 = 0
# i=0 < 3-1=2 -- 边界
# hiehgts[1][0] - hiehgts[0][0] = 3-1=2, pos=0, pos+N=3 # 自身与下节点比较
# j=0 < 3-1=2 -- 边界
# hiehgts[0][1] - hiehgts[0][0] = 2-1=1, pos=0, pos+1=1 # 自身与右节点比较

# 0, 1
# pos = i*N+j = 0*3 + 1 = 1
# i=0 < 3-1=2
# hiehgts[1][1] - hiehgts[0][1] = 8-2=6, pos=1, pos+N=4
# j=1 < 3-1=2
# hiehgts[0][2] - hiehgts[0][1] = 2-2=0, pos=1, pos+1=2

# 0, 2
# pos = i*N+j = 0*3 + 2 = 2
# i=0 < 3-1=2
# hiehgts[1][2] - hiehgts[0][2] = 2-2=0, pos=2, pos+N=5 
# j=2 < 3-1=2
# hiehgts[0][2+1] index out of 

# 1, 0
# pos = i*N+j = 1*3 + 0 = 3
# i=1 < 3-1=2
# hiehgts[2][0] - hiehgts[1][0] = 5-3=2, pos=3, pos+N=6
# j=0 < 3-1=2
# hiehgts[1][1] - hiehgts[1][0] = 8-3=5, pos=3, pos+1=4

# 1, 1
# pos = i*N+j = 1*3 + 1 = 4
# i=1 < 3-1=2
# hiehgts[2][1] - hiehgts[1][1] = 3-8=-5, pos=4, pos+N=7
# j=1 < 3-1=2
# hiehgts[1][2] - hiehgts[1][1] = 2-8=-6, pos=4, pos+1=5

"""
heights = [[1,2,2],[3,8,2],[5,3,5]]
DSU 理解推导
[(2,0,3),(1,0,1)  (6,1,4),(0,1,2)  (0,2,5),   
 (2,3,6),(5,3,4)  (5,4,7),(6,4,5)  (3,5,8)
        ,(2,6,7)         ,(2,7,8)         ,
]

sort 之后, union 处理
(0,1,2) 1<-2
(0,2,5) 2<-5
(1,0,1) 0<-1
(2,0,3) 0<-3
(2,3,6) 3<-6
(2,6,7) 6<-7
(2,7,8) 7<-8  这里就能找到 find(0) == find(8)
(3,5,8)
(5,3,4)
(5,4,7)
(6,1,4)
(6,4,5)

self.par = [0,1,2...1000]
x=1, y=2
self.par[self.find(x)] = self.find(y)
self.par[self.find(1)] = self.find(2)
self.par[1] = 2

x=0, y=8
self.find(0) == self.find(8)

x=2, y=5
self.par[self.find(x)] = self.find(y)
self.par[self.find(2)] = self.find(5)
self.par[2] = 5

self.par[1] <- self.par[2] 
self.par[2] <- self.par[5]

"""

---

微信id: lllong33 来自 vscode 插件