leetcode303 Weekly Match Replay

ps：My first official competition,The first question was done quickly,The second question took a while,The third question is made,但是超时,Finally completed two questions.
Everyone's strength is terrifying,1st place completes all in 8 minutes,And I'm still on the first question in eight minutes.Didn't finish in an hour and a half,究其原因,Still not familiar with algorithms.Still have to continue to work hard to temper yourself！

6124. 第一个出现两次的字母

Or look at the constraints,The discovery range is100以内,Don't have to worry about and timeout issues
The next topic request,Find out the first two letters.My first thought was to use a list to record the elements that appeared,If an element appears twice,返回这个元素.时间复杂度O(n) ,空间复杂度O(n)

class Solution:
    def repeatedCharacter(self, s: str) -> str:
        dic=dict()
        for i in s:
            if i in dic:
                return i
            else:
                dic[i]=0
        return -1

Although the task was completed quickly,But I don't think it's the best solution.查找重复的元素,The best way should be xor

6125. 相等行列对


First look at the constraintsn在200以内,So even the brute force solution will not calculate for a long time..
在看题目,Looking for the same,My first thought was violence,Turn each row and column into a string,然后比较,If a line element string in the column,So remember to appear a pair.但是这样有个问题,If there are two identical columns in the column,should be counted twice.Ultimately my approach was to count the number of occurrences of the string in the column.（I found out I'm a statistics freak）,于是有了下面的代码

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        le = len(grid[0])
        hang_str = []
        lie_str = []
        count=0
        dic={
    }
        for i in range(le):
            hang_str.append(",".join([str(i ) for i in grid[i]]))
            lie_str.append(",".join([ str(k[i]) for k in grid ]))
        for k in lie_str:
            if not k in dic:
                dic[k]=1
            else:
                dic[k]+=1
        # print(hang_str,lie_str)
        for i in hang_str:
            count+=dic.get(i,0)
        return count

But the brute force algorithm,可以有,但是没必要.于是我又去leetcodeRead other people's solutions,New ideas not learned,The following method is consistent with my thinking,but concise,学到了几个python的内置函数.

class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        cnt = Counter(tuple(row) for row in grid)
        return sum(cnt[col] for col in zip(*grid)) #Count the number of times a column appears in a row
作者：endlesscheng
链接：https://leetcode.cn/problems/equal-row-and-column-pairs/solution/ha-xi-biao-python-liang-xing-by-endlessc-ljae

cnt是count的缩写,学习了
*grid 是解包,有关️The usage of the previous review mentionedleetcode第302Weekly replay
And then followed by azip函数,如果是ziptwo lists,is packed into tuples according to the columns.This is exactly the purpose of the statistical column.

zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的对象.
a = [1,2,3]
b = [4,5,6]
c = [4,5,6,7,8]
zipped = zip(a,b) # 返回一个对象
zipped <zip object at 0x103abc288>
list(zipped) # list() 转换为列表
[(1, 4), (2, 5), (3, 6)]
list(zip(a,c)) # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]

6126. 设计食物评分系统



First look at the constraints,n的范围是$10^4$ ,Call number is$10^4$,So consider whether it will time out.
Analyze the topics below：主要实现两个功能：

1. Modify food ratings
2. find a way to cook,top rated food（with the same score,In the dictionary order small one）

First look at function one,Modify food ratings,foodsall characters in,可以使用foods作为键,构建一个字典food_info,for quick findfood对应的评分“rating” implement linear modification.

food_info={
    'food':
		{
    
		'rating':xx,
		'suisines':'xxx'
		}
}
suisines_info={
    'suisines':
			[(rating1,food1),(rating2,food2)]
			}

Looking at feature two：Need to find a way of cooking,top rated food.可以使用suisines建立一个字典suisines_info,The value is an ordered list,元素为（rating,food）的元组.This needs to find the highest rated food,Just take the first element of the list in the dictionary corresponding to the cooking mode.When feature one modifies the rating,It will also cause a change in ranking,Reordering after modification takes time,导致超时.Since the list when modifying the score is an ordered list,So you can delete and then insert,So don't use sorting here.（The entire ordered list is constructed by,The way to insert an ordered list is done）

PS：Some readers may think thatfood_infoDictionary is useless,实则并非如此.在suisines_info字典,删除对应（food,rating）元组时,first don't knowfoodWhich cooking method corresponds tosuisines,i.e. don't know what the keys of the dictionary are,In addition, after finding the key, you also need to find the corresponding food namefood.That is to say, each modification needs to traverse the entiresuisines_info字典,但是使用food_info字典后,只需要O(1)time to find,the foodfood在suisines_infolocation in dictionary,以空间换时间.
此外,Arrange lexicographically for the same value,存在一个小问题：假设列表为
[(16,‘a’),(14,‘c’),(16,‘b’) ]
If sorted by score in descending order,Then the letters are also in descending order,Sequencing results are obtained as follows
[(16,‘b’),(16,‘a’),(14,‘c’) ]
In this case, you cannot get the maximum score according to the meaning of the question.,Food name with the lowest number in the dictionary.
Here's a little trick to negate fractions【想法来源：力扣用户 tsreaper】
[(-16,‘a’),(-14,‘b’),(-16,‘c’) ]
Then in ascending order you can get
[(-16,‘a’),(-16,‘b’),(-14,‘c’) ]

下面代码

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.info_list = dict()
        c=set(cuisines)
        self.cuisines_list=dict(zip(c,[ [] for _ in range(len(c))]))
        for index, ele in enumerate(foods):
            bisect.insort_right(self.cuisines_list[cuisines[index]], (-ratings[index],ele))
            self.info_list[ele] = {
    'cuisines': cuisines[index], 'ratings': -ratings[index]}

    def changeRating(self, food: str, newRating: int) -> None:
        ratings=self.info_list[food]['ratings']
        cuisine=self.info_list[food]['cuisines']
        self.info_list[food]['ratings'] = -newRating
        self.cuisines_list[cuisine].remove((ratings, food))
        bisect.insort_right(self.cuisines_list[cuisine], (-newRating,food))

    def highestRated(self, cuisine: str) -> str:
        now,food=self.cuisines_list[cuisine][0]
        return food



# Your FoodRatings object will be instantiated and called as such:
# obj = FoodRatings(foods, cuisines, ratings)
# obj.changeRating(food,newRating)
# param_2 = obj.highestRated(cuisine)

This topic is really the history of blood and tears,只要n大一点,i will time out;But little by little,Finally submitted successfully on the edge of timeout

6127. 优质数对的数目

First look at the constraints 数字的个数 $10^5$ ,size of a single digit$10^9$超级大,Therefore, we need to consider how to optimize the time complexity.此外k的取值范围是[1,60] ,The value of the number is greater than1的,因此当k等于1时,All pairs in the array satisfy the condition,Of course no duplicate elements.

Start looking at the topic below,Find the number of high quality in a digital array pairs,A good pair has two conditions

• Both numbers must appear in the array,Can be the same number twice,Digital is only a repeat;

• binary of these two numbers“或”与二进制的“与”中,包含“1”The total number should be greater than or equal tok

   						以3和5为例,3=0b11,5=0b101
   						3&5=0b1 ,包含1个“1”;
   						3|5=0b111,包含3个“1”,共计4个
  

此处有个细节：
When two numbers are made in binary“或” 操作时,The result will only keep all of the two numbers in binary“1” But the overlap is only counted as one,所以有：
$$“或”In\; binary\; number\; after\; operation“1”的个数=Two\; binary\; number“1”的个数-重叠的个数$$
When two numbers are made in binary“与” 操作时,The result will only keep the overlapping of the two numbers in the binary“1”
$$“与”In\; binary\; number\; after\; operation“1”的个数=重叠的个数$$
final conclusion
binary of these two numbers“或”与二进制的“与”中,包含“1”的个数总数=two-digit binary number“1”的个数

Therefore, only the binary number of each number in the array is required to contain“1”的个数,Then is greater than the sum of the two NumbersK就可以了.Therefore, the original array will be repeated first,Then convert each number in the array to its binary containing1的个数.
If the original array[1,3,2,1] -去重复->[1,3,2]-转化为“1”的个数->[1,2,1].
At this point the problem becomes,Select two numbers in an array whose sum is greater than or equal toK,有多少种选法
Violence to solve word is two layersfor循环,But this will definitely time out.
So sort first,Then traverse the array from back to front,

• If the value of the current array is2times greater than or equal tok,那么次数加一
• The current numericalnums[i]and target valuek的差值,Find position of difference in sorted arrayd,那么d到iAll numbers in are satisfied,又由于（1,2）和（2,1）算两个,Therefore, the number of times should be increased2*（i-d）次

After analyzing the problem, it is almost solved,下面是代码：

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        cnt = 0
        nums = sorted([bin(i).count("1") for i in set(nums)])
        length = len(nums)
        if k == 1:
            return length * length
        for i in range(length-1,-1,-1):
            if nums[i] * 2 >= k:
                cnt += 1
            index = bisect_left(nums, k - nums[i])
            if index>i:#如果index的位置大于i 不合法,因为已经遍历过了
                break
            cnt += 2 * ( i-index)
        return cnt

There is no guarantee that the above ideas will be correct,欢迎一起交流