Leetcode math problems

leetcode Middle mathematics / Array title _MaYingColdPlay The blog of -CSDN Blog 1. Integer inversion idea ： The two methods ,1 Is to convert a number into a string , Traversal in reverse order of strings , Need to open up additional space .2 Yes, it is 10 The way to get the remainder .https://leetcode-cn.com/problems/reverse-integer/solution/hua-jie-suan-fa-7-zheng-shu-fan-zhuan-by-guanpengc/...https://blog.csdn.net/MaYingColdPlay/article/details/106610056?spm=1001.2014.3001.5502

5868 An array of interchangeable rectangles

Power button https://leetcode-cn.com/problems/number-of-pairs-of-interchangeable-rectangles/

I am so stupid , Actually, it is done by traversal . Later, I cut some paper , It's all overtime . Here is my code .

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        cnt = 0
        for i in range(len(rectangles)):
            w1,h1 = rectangles[i][0],rectangles[i][1]
            for j in range(i+1,len(rectangles)):
                w2,h2 = rectangles[j][0],rectangles[j][1]
                if w1/h1 == w2/h2:
                    cnt=cnt+1
        return cnt
                

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        cnt=0
        dp=[[False for _ in range(len(rectangles))] for _ in range(len(rectangles))]
        for i in range(len(rectangles)):
            w1, h1 = rectangles[i][0], rectangles[i][1]
            for j in range(i + 1, len(rectangles)):
                if i>=1:
                    if dp[i - 1][j] == True and dp[i - 1][j - 1] == True and dp[i][j-1]== True:
                        dp[i][j] = True
                        cnt = cnt + 1
                    else:
                        w2, h2 = rectangles[j][0], rectangles[j][1]
                        if w1 / h1 == w2 / h2:
                            dp[i][j] = True
                            cnt = cnt +1
                else:
                    w2, h2 = rectangles[j][0], rectangles[j][1]
                    if w1 / h1 == w2 / h2:
                        dp[i][j] = True
                        cnt = cnt + 1
        return cnt
                

In fact, it is OK to use the combination formula , Reflect on why you didn't think

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        # Traversal array , How many different ratios are there 
        dic={}
        for i in range(len(rectangles)):
            w=rectangles[i][0]
            h=rectangles[i][1]
            value = w/h 
            if value not in dic.keys():
                dic[value]=1
            else:
                dic[value]=dic[value]+1
        res=0
        for key in dic.keys():
            cur_v=dic[key]
            cur_res=cur_v*(cur_v-1)/2
            res=res+cur_res
        return int(res)
        

5877. Detection square

My messy solution , Only through 4 individual case.

class DetectSquares(object):
    def __init__(self):
        self.dic_x={}
        self.dic_y={}
    def add(self, point):
        """
        :type point: List[int]
        :rtype: None
        """
        x=point[0]
        y=point[1]
        if x not in self.dic_x:
            self.dic_x[x]=[y]
        else:
            self.dic_x[x].append(y)
        if y not in self.dic_y:
            self.dic_y[y]=[x]
        else:
            self.dic_y[y].append(x)
    def count(self, point):
        """
        :type point: List[int]
        :rtype: int
        """
        x=point[0]
        y=point[1]
        print("x,y",point,self.dic_x,self.dic_y)
        if x in self.dic_x and y in self.dic_y:
            y_match=self.dic_x[x]
            x_match=self.dic_y[y]
            y_match_helper={}
            x_match_helper={}
            for y_m in y_match:
                if abs(y-y_m) not in y_match_helper:
                    y_match_helper[abs(y-y_m)]=1
                else:
                    y_match_helper[abs(y-y_m)]=y_match_helper[abs(y-y_m)]+1
            for x_m in x_match:
                if abs(x-x_m) not in x_match_helper:
                    x_match_helper[abs(x-x_m)]=1
                else:
                    x_match_helper[abs(x-x_m)]=x_match_helper[abs(x-x_m)]+1
            print("x",x_match_helper)
            print("y",y_match_helper)
            for key in x_match_helper and y_match_helper:
                    duijiao_x=abs(x-key)
                    duijiao_y=abs(y-key)
                    if duijiao_x in self.dic_x and duijiao_y in self.dic_y:
                        return max(x_match_helper[key],y_match_helper[key])
        return 0
# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)

Big guy's clear way to find diagonals

class DetectSquares:
    def __init__(self):
        self.hashmap = collections.defaultdict(int)
        self.v = set()

    def add(self, point: List[int]) -> None:
         x,y = point[0],point[1]
         self.hashmap[(x,y)] += 1
         self.v.add((x,y))

    def count(self, point: List[int]) -> int:
        #  Enumerate diagonals 
        ans = 0
        x1,y1 = point[0],point[1]
        for x2,y2 in self.v:
            if x2 == x1 or y2 == y1:
                continue
            
            if (x1,y2) in self.v and (x2,y1) in self.v:
                d1,d2 = abs(y2 - y1),abs(x2 - x1)
                if d1 == d2:
                    temp = 1
                    temp *= self.hashmap[(x2,y2)]
                    temp *= self.hashmap[(x1,y2)]
                    temp *= self.hashmap[(x2,y1)]
                    ans += temp
        return ans



# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)

31. Next spread

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # Go back and forth , find nums[i]<nums[i+1] The first element of 
        i=len(nums)-2
        while i>=0 and nums[i]>=nums[i+1]:
            i=i-1
        # Go back and forth , find nums[j]>nums[i] The first element of 
        if i>=0:
            j=len(nums)-1
            while j>i and nums[i]>=nums[j]:
                j=j-1
            # In exchange for 
            nums[i],nums[j]=nums[j],nums[i]
        # from i+1 To the last in ascending order 
        left=i+1
        right=len(nums)-1
        while left<right:
            nums[left],nums[right]=nums[right],nums[left]
            left=left+1
            right=right-1
        return nums

60 Arrange the sequence

 

  Power button https://leetcode-cn.com/problems/permutation-sequence/solution/python3-chao-xiang-xi-duo-jie-fa-by-ting-ting-28-3/

264. Ugly number II

The smallest pile + Guang Shu （ Rainwater collection 2 It's also ）

class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        # Generate ugly numbers from small to large 
        # Generate rules ： Minimum number of POPs per time , multiply  2/3/5
        if n==1:
            return 1
        blist=[2,3,5]
        import heapq
        alist=[]
        heapq.heappush(alist,1)
        res=[]
        while len(res)<n:
            min_val=heapq.heappop(alist)
            if min_val not in res:
                res.append(min_val)
            for val in blist:
                new=min_val*val 
                if new not in alist:
                    heapq.heappush(alist,new)
        return res[-1]

solution 2: Multiplex merge

279. Complete square

373. Look for the smallest K Pairs of numbers

solution 1: Heap sort

solution 2: Multiplex merge

668. Number... In the multiplication table k Small number

204. Count prime

enumeration

class Solution {
    public int countPrimes(int n) {
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime(i)) {
                cnt++;
            }
        }
        return cnt;
    }

    private boolean isPrime(int num) {
        int max = (int)Math.sqrt(num);
        for (int i = 2; i <= max; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 author ：sweetiee
 link ：https://leetcode-cn.com/problems/count-primes/solution/kuai-lai-miao-dong-shai-zhi-shu-by-sweetiee/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Ethmoid

class Solution {
    
    public int countPrimes(int n) {
        boolean[] isPrim = new boolean[n];
        Arrays.fill(isPrim, true);
        //  from  2  Start enumerating to  sqrt(n).
        for (int i = 2; i * i < n; i++) {
            //  If the current number is prime 
            if (isPrim[i]) {
                //  From  i*i  Start ,i  All multiples of are set to  false.
                for (int j = i * i; j < n; j+=i) {
                    isPrim[j] = false;
                }
            }
        }

        //  Count 
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (isPrim[i]) {
                cnt++;
            }
        }
        return cnt;
    }
}

 author ：sweetiee
 link ：https://leetcode-cn.com/problems/count-primes/solution/kuai-lai-miao-dong-shai-zhi-shu-by-sweetiee/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

# A sieve ： Take all the numbers first (2 To n) Marked as prime number , And then from 2 Start , Mark its multiples as composite numbers 
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def countPrimes(self, n):
        is_primes = [1 for _ in range(n)]
        for i in range(2, n):
            if is_primes[i] == 1:
                for j in range(2 * i, n, i):
                    #  Set its multiple to 0
                    is_primes[j] = 0
        count = 0
        for i in range(2, n):
            if is_primes[i] == 1:
                count += 1
        return count
n=10
res=Solution().countPrimes(n)
print(res)

1447. Simplest fraction

  Find the greatest common divisor by division

division （ Find the greatest common divisor ）_ A Bula's blog -CSDN Blog

  Find the greatest common divisor （ division ）_ACfun-CSDN Blog _ Find the greatest common divisor by division

class Solution:
    def simplifiedFractions(self, n: int) -> List[str]:
        # n = 5
        # ["1/2","1/3","1/4","2/3","3/4"] ['1/5','2/5','3/5','4/5']
        if n==1:
            return []
        def gcd(a,b):
            while a>0 and b>0:
                if a>b:
                    a=a%b
                else:
                    b=b%a 
            return a+b
        # recursive , The current value plus n-1
        def cal_x(x):
            cur_res=[]
            cur_res.append(str(1) + '/' + str(x))
            for i in range(2,x):
                if gcd(x,i)==1:
                    cur_res.append(str(i)+'/'+str(x))
            return cur_res
        return self.simplifiedFractions(n-1)+cal_x(n)

Find the least common multiple

6019. Replace non coprime numbers in the array

 

  Stack + The greatest common divisor and the least common multiple

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stack=[]
        def gcd(a1,a2):
            # Find the greatest common divisor 
            while a1>0 and a2>0:
                if a1>a2:
                    a1=a1%a2 
                else:
                    a2=a2%a1
            return a1+a2
        def check(stack):
            while len(stack)>=2 and gcd(stack[-1],stack[-2])>1:
                lcm=stack[-1]*stack[-2]//gcd(stack[-1],stack[-2])
                stack.pop()
                stack.pop()
                stack.append(lcm)
                
        for i in range(len(nums)):
            if stack and gcd(nums[i],stack[-1])>1:
                lcm=nums[i]*stack[-1]//gcd(nums[i],stack[-1])
                stack.pop()
                stack.append(lcm)
            else:
                stack.append(nums[i])
            # Check whether there are non coprime numbers in the stack 
            check(stack)
        return stack

6015. Statistics can be K The number of subscript pairs divisible

  The greatest common factor

k  The remaining prime factor is  y Prime factors that must be included

class Solution(object):
    def coutPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # k/gcd(k,nums[i]), yes nums[j] A factor of 
        def gcd(x,y):
            while x>0 and y>0:
                if x>y:
                    x=x%y
                else:
                    y=y%x 
            return x+y
        alist=[]
        res=0
        for i in range(len(nums)):
            a=gcd(nums[i],k)
            alist.append(a)
        print(alist)

        maps=Counter(alist)
        maps_list=list(maps.keys())
        # Combine , Different key A combination of two (m*n), same key Own internal combination c(2,n),
        for i in range(len(maps_list)):
            if maps_list[i]*maps_list[i] % k==0:
                res+=maps[maps_list[i]]*(maps[maps_list[i]]-1)/2
            for j in range(i+1,len(maps_list)):
                if maps_list[i]*maps_list[j] % k==0:
                    res+=maps[maps_list[i]]*maps[maps_list[j]]
        return res

5994. Find the substring of the given hash value

The property of remainder operation

 

  Positive order ergodic ： Overtime

class Solution(object):
    def subStrHash(self, s, power, modulo, k, hashValue):
        """
        :type s: str
        :type power: int
        :type modulo: int
        :type k: int
        :type hashValue: int
        :rtype: str
        """
        # The calculated length is k Hash value of the substring of 
        # lookup index
        alist=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
        # The first power The calculation is stored in the array 
        power_i=[0 for _ in range(k)]
        power_i[0]=1
        for i in range(1,k):
            power_i[i]=power_i[i-1]*power
        # The first group 
        cur_s=s[:k]
        cur=0
        for j in range(k):
            index=alist.index(cur_s[j])+1
            p=power_i[j]
            cur+=index*p
        if cur%modulo==hashValue:
            return cur_s
        pre=0
        nexts=k
        while nexts<len(s):
            index=alist.index(s[nexts])+1
            p=power_i[k-1]
            cur=(cur-(alist.index(s[pre])+1))/power + index*p 
            if cur%modulo==hashValue:
                return s[pre+1:nexts+1]
            pre+=1
            nexts+=1

  Modular operations satisfy the distributive law

class Solution(object):
    def subStrHash(self, s, power, modulo, k, hashValue):
        """
        :type s: str
        :type power: int
        :type modulo: int
        :type k: int
        :type hashValue: int
        :rtype: str
        """
        # Divisor is not easy to modulo , The quantity is too large to time out 
        # So use the method of flashback traversal , Go back and forth . Modular multiplication satisfies commutative law 

        # First save the result of the power operation 
        power_i=[0 for _ in range(k)]
        power_i[0]=1%modulo
        for i in range(1,k):
            power_i[i]=power_i[i-1]*power%modulo
         # lookup index
        alist=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
        res=[]
        # Last group 
        cur_s=s[len(s)-k:]
        cur_res=0
        for i in range(k):
            index=alist.index(cur_s[i])+1
            p=power_i[i]
            cur_res=cur_res+index*p
        cur_res=cur_res%modulo
        if cur_res == hashValue:
            res.append(cur_s)
        # Flashback traversal 
        remove_index=len(s)-1
        new_index=len(s)-1-k
        while new_index>=0:
            new_value=alist.index(s[new_index])+1
            remove_value=(alist.index(s[remove_index])+1)*power_i[k-1]
            # cur_res=(cur_res-remove_value)*power+new_value 
            # if cur_res%modulo == hashValue:
            #     res.append(s[new_index:remove_index])
            cur_res=((cur_res-remove_value)*power+new_value)%modulo
            if cur_res== hashValue:
                res.append(s[new_index:remove_index])
                # return s[new_index:remove_index]
            new_index=new_index-1
            remove_index=remove_index-1
        return res[-1]

2063. Vowels in all substrings

  The sliding window , Overtime

class Solution:
    def countVowels(self, word: str) -> int:
        alist=['a','e','i','o','u']
        cnt=0
        # Double pointer 
        left=-1
        while left<len(word)-1:
            flag=0
            left+=1
            right=left+1
            cur=word[left]
            if cur in alist:
                cnt+=1
                flag=1
            while right<len(word):
                cur=word[right]
                if cur in alist or flag>0:
                    if cur in alist:
                        flag+=1
                        cnt+=flag
                    else:
                        cnt+=flag
                right+=1
        return cnt

Combinatorial mathematics

class Solution:
    def countVowels(self, word: str) -> int:
        res = 0
        meta = {'a', 'e', 'i', 'o', 'u'}
        n = len(word)
        for i, ch in enumerate(word):
            if ch in meta:
                res += (i + 1) * (n - i)
        return res

 author ：ya-li-ge
 link ：https://leetcode-cn.com/problems/vowels-of-all-substrings/solution/zu-he-wen-ti-xun-huan-bian-li-python-jie-hoxq/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

828. Count the unique characters in the substring

  sliding window , Overtime

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        count=0
        # The sliding window 
        left=-1
        while left<len(s)-1:
            left+=1
            cur=s[left]
            count+=1
            visited={}
            visited[cur]=1
            right=left+1
            while right<len(s):
                cur = s[right]
                if cur in visited:
                   visited[cur]+=1
                else:
                    visited[cur]=1
                cur_count=0
                for key in visited:
                    if visited[key]==1:
                        cur_count+=1
                count += cur_count
                right += 1
        return count

Combinatorial mathematics

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        res=0
        # Turn into ： Each letter is in a substring , contain 1 Number of substrings of current letters .
        for i in range(len(s)):
            cur=s[i]
            # To the left 
            j=i-1
            while j>=0 and s[j]!=cur:
                j=j-1
            left_count=i-j 
            # To the right 
            h=i+1
            while h<=len(s)-1 and s[h]!=cur:
                h=h+1
            right_count=h-i 
            cur_count=left_count*right_count
            res+=cur_count
        return res

5986. The least cost of setting time

 

class Solution {
public:
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        int mins = targetSeconds / 60;
        int secs = targetSeconds % 60;
        int ans1 = calc(startAt, moveCost, pushCost, mins, secs);
        int ans2 = calc(startAt, moveCost, pushCost, mins - 1, secs + 60);
        return min(ans1, ans2);
    }

    int calc(int startAt, int moveCost, int pushCost, int mins, int secs) {
        /*  Illegal input returns  */
        if (mins > 99 || mins < 0 || secs > 99) {
            return INT_MAX;
        }

        /*  To string ,  Remove the lead 0 */
        string s = to_string(mins * 100 + secs);

        int ans = 0;
        /*  Process each number  */
        for (int i = 0; i < s.size(); i++) {
            if (startAt == s[i] - '0') { /*  No extra moveCost */
                ans += pushCost;
            } else {
                ans += moveCost + pushCost;
            }
            startAt = s[i] - '0';
        }
        return ans;
    }
};

 author ：liu-xiang-3
 link ：https://leetcode-cn.com/problems/minimum-cost-to-set-cooking-time/solution/cfen-lei-tao-lun-by-liu-xiang-3-sqem/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
        def cal(minute,second,startAt):
            if minute>99:
                return float('inf')
            # Into four digits 
            target_time=[minute//10,minute%10,second//10,second%10]
            i=0
            cost=0
            # Skip the first 0
            while i<=3 and target_time[i]==0:
                i+=1
            while i<=3:
                cur=target_time[i]
                if cur==startAt:
                    cost=cost+pushCost
                else:
                    cost=cost+pushCost+moveCost
                    startAt=cur 
                i+=1
            return cost
        ans1=float('inf')
        ans2=float("inf")
        # hold targetSeconds Convert to microwave oven time form 
        minute1=targetSeconds//60 
        second1=targetSeconds%60 
        ans1=cal(minute1,second1,startAt)
        # The maximum number of minutes can reach 99 second , When second1 Less than or equal to 39 When , You can take minutes (60 second ) Take it to the second digit 
        if second1<=39:
            second2=second1+60 
            minute2=minute1-1 
            ans2=cal(minute2,second2,startAt)
        return min(ans1,ans2)

233. Numbers 1 The number of

  Violence overtime

Arrange and combine to find rules

Power button

41. First positive number missing

In situ hash

Similar topics ： The finger of the sword offer03, In situ hash

 

from typing import List


class Solution:

    # 3  The index should be placed in  2  The place of 
    # 4  The index should be placed in  3  The place of 

    def firstMissingPositive(self, nums: List[int]) -> int:
        size = len(nums)
        for i in range(size):
            #  First determine whether this number is an index , Then judge whether the number is in the right place 
            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
                self.__swap(nums, i, nums[i] - 1)

        for i in range(size):
            if i + 1 != nums[i]:
                return i + 1

        return size + 1

    def __swap(self, nums, index1, index2):
        nums[index1], nums[index2] = nums[index2], nums[index1]

 author ：liweiwei1419
 link ：https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

440. The second part of the dictionary order K Small number

Arrange by bit

There was a similar question in the previous week's competition t2, Next spread

Power button

class Solution {
    public int findKthNumber(int n, int k) {
        long cur = 1;
        k--;
        while(k > 0) {
            //  With cur The subtree node that is the root has nodes individual 
            int nodes = getNodes(n, cur);
            //  If the number is more than k Less , Then this part can be skipped directly 
            if(k >= nodes) {
                //  Skip all 
                k = k -nodes;
                //  Move one to the right 
                cur++;
            }
            //  If the quantity is more than k many , So we must find the result cur Child nodes under 
            else {
                //  Skip current node 
                k = k - 1;
                //  Go down one floor 
                cur = cur * 10;
            }
        }
        return (int)cur;
    }

    //  To obtain cur Is the number of subtree nodes of the root node 
    private int getNodes(int n, long cur) {
        long next = cur + 1;
        long totalNodes = 0;
        while(cur <= n) {
            //  Calculate the sum of the number of nodes in the next layer at one time , Use it if it is not full n To reduce , If it is full, use it next reduce 
            totalNodes += Math.min(n - cur + 1, next - cur);
            //  Go to the next level 
            next = next * 10;
            cur = cur * 10;
        }
        return (int)totalNodes;
    }
}

 author ：livorth-u
 link ：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order/solution/by-livorth-u-zvxp/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

5253. Find the number of palindromes of the specified length

  It took a long time to adjust during the Zhou match .

class Solution(object):
    def kthPalindrome(self, queries, intLength):
        """
        :type queries: List[int]
        :type intLength: int
        :rtype: List[int]
        """
        len1=9
        len2=9
        len3=9*10
        len4=9*10
        len5=9*10*10
        len6=9*10*10
        len7=9*10*10*10
        len8=9*10*10*10
        len9 = 9 * 10 * 10 * 10* 10
        len10 = 9 * 10 * 10 * 10 * 10
        len11 = 9 * 10 * 10 * 10 * 10* 10
        len12 = 9 * 10 * 10 * 10 * 10* 10
        len13 = 9 * 10 * 10 * 10 * 10 * 10* 10
        len14 = 9 * 10 * 10 * 10 * 10 * 10* 10
        len15 = 9 * 10 * 10 * 10 * 10 * 10 * 10* 10
        # First determine the outermost 
        maps={1:0,2:0,3:1,4:1,5:2,6:2,7:3,8:3,9:4,10:4,11:5,12:5,13:6,14:6,15:7}
        def cal(i,intLength):
            cur_num=queries[i]
            cur_res=[str(0) for _ in range(intLength)]
            v0=maps[intLength]
            v1=10**v0
            tmp_count=0
            flag=False
            for i in range(1,10):
                if i>1:
                    flag=True
                tmp_count=tmp_count+v1
                if cur_num<=tmp_count and flag==False:
                    cur_res[0]=str(i)
                    break
                if cur_num<tmp_count and flag==True:
                    cur_res[0] = str(i-1)
                    cur_num=cur_num-(tmp_count-v1)
                    break
                if cur_num==tmp_count:
                    cur_res[0] = str(i)
                    cur_num = cur_num - (tmp_count - v1)
            # From the second place , There is still left cur_num Number 
            # Even number traverses to 
            intLength=intLength-2
            index=1
            while intLength>1:
                v0 = maps[intLength]
                v1 = 10 ** v0
                tmp_count = 0
                flag = False
                for i in range(10):
                    if i > 0:
                        flag = True
                    tmp_count = tmp_count + v1
                    if cur_num <= tmp_count and flag == False:
                        cur_res[index] = str(i)
                        break
                    if cur_num <= tmp_count and flag == True:
                        cur_res[index] = str(i - 1)
                        cur_num = cur_num - (tmp_count - v1)
                        break
                intLength = intLength - 2
                index = index+1
            # If it's even , Judge the last two , If it's odd , Judge the last 
            if if_oushu==0:
                for i in range(10):
                    cur_num = cur_num - 1
                    if cur_num==0:
                        cur_res[index] = str(i)

            right=len(cur_res)-1
            left=0
            while left<right:
                cur_res[right]=cur_res[left]
                right-=1
                left+=1
            print(cur_res)
            return ''.join(cur_res)
        res=[]
        if_oushu=0
        if intLength%2==0:
            if_oushu=1
        for i in range(len(queries)):
            res.append(int(cal(i,intLength)))
        return res
# queries = [2,4,6], intLength = 4
# queries = [231]
# intLength = 5
# queries =[1,2,3,4,5,90]
# intLength =3

# Discussion on odd and even numbers , First determine the prefix , Even last 2 One needs special treatment , The last odd number needs special treatment 
# The first prefix is specially handled , Because the first prefix cannot have a leading 0
# When determining the prefix , To put count Subtract the number of prefixes that have been determined 
queries =[2,4,6]
intLength =4
res=Solution().kthPalindrome(queries, intLength)
print(res)

Looking for a regular

 

 

class Solution {
    public long[] kthPalindrome(int[] queries, int intLength) {
        /*
         Find rules to generate :
         The core is to find n How many palindromes are there ( Cross border judgment )?+ The first k What is the number of palindromes ?
        */
        int len = queries.length;
        long[] res = new long[len];
        for(int i = 0; i < len; i++) {
            res[i] = getPalindrome(queries[i], (double)intLength);
        }
        return res;
    }
    
    /*
     Return to generation No k Small n Bit palindrome number 
     It is not difficult to find the following rules :
    101, 111, 121, 131, 141, 151, 161, 171, 181, 191
    202, 212, 222, 232, 242, 252, 262, 272, 282, 292
    ...
    909, 919, 929, ............................, 999
     You know 3 The number of palindromes in digits is 90 individual 
     Consider only the left half ( Quite critical ！！！)
    1. Sum up n The total number of digit palindromes is :
    n It's odd :9*10^(n/2);n For the even :9*10^(n/2-1)
     Further :9*10^(ceil(n/2)-1)
     Beyond this range, return -1 that will do 
    2. The first k A small palindrome number is actually 
     Odd number :10^(n/2)+k-1(+ Reverse + Delete the middle position )
     even numbers :10^(n/2-1)+k-1(+ Reverse )
     Further :10^(ceil(n/2)-1)+k-1
    */
    private long getPalindrome(int k, double n) {
        //  If the number exceeds the valid range, it will be returned directly -1
        if(k > 9 * Math.pow(10, Math.ceil(n / 2) - 1)) {
            return -1;
        }
        //  First convert the first half into a string 
        long pre = (long)Math.pow(10, Math.ceil(n / 2) - 1) + k - 1;
        StringBuilder sb1 = new StringBuilder(String.valueOf(pre));
        StringBuilder sb2 = new StringBuilder(sb1);
        //  Splice the back part 
        sb2.append(sb1.reverse());
        // n For odd numbers, the middle digit must be removed 
        if((int)n % 2 == 1) {
            sb2.deleteCharAt((int)n / 2);
        }
        //  Then convert the string to a number 
        return Long.parseLong(sb2.toString());
    }
}

2195. Append... To the array K It's an integer

A sequence of equal differences

780 Reach the end point

Converse thinking

 

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        if(sx > tx || sy > ty) return false;

        while(sx < tx && sy < ty) {
            if(tx > ty) tx %= ty;
            else ty %= tx;
        }
        
        if(tx == sx) { // ty = sy + k * tx, k >= 0
            return (ty - sy) % tx == 0; 
        } else if(ty == sy) { // tx = sx + k * ty, k >= 0
            return (tx - sx) % ty == 0;
        }
        return false;
    }
};

 author ：hxf_wyh
 link ：https://leetcode-cn.com/problems/reaching-points/solution/by-hxf_wyh-g9hj/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

357  Calculate the number of different digits

Permutation and combination

Wrong idea

 

 

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        int res = 1;
        int product = 9;
        for (int i = 1; i < 10 && i <= n; i++) {
            res = product + res;
            product *= (10-i);
        }
        return res;

    }
}