怎么用ps切片在dw里做网站,背景图网站,阳江做网站多少钱,平台推广是什么工作leetcode-剑指offer-443.面试题43-1#xff5e;n整数中1出现的次数44.面试题44-数字序列中某一位的数字45.面试题45-把数组排成最小的数-快排变种46.面试题46-把数字翻译成字符串47.面试题47-礼物的最大价值-dp48.面试题48-最长不含重复字符的子字符串-滑动窗口法49.面试题49-…
leetcode-剑指offer-443.面试题43-1n整数中1出现的次数44.面试题44-数字序列中某一位的数字45.面试题45-把数组排成最小的数-快排变种46.面试题46-把数字翻译成字符串47.面试题47-礼物的最大价值-dp48.面试题48-最长不含重复字符的子字符串-滑动窗口法49.面试题49-丑数-自底向上递归50.面试题50-第一个只出现一次的字符-hash表51.面试题52-两个链表的第一个公共节点-双指针技巧52.面试题53-在排序数组中找数字54.面试题53-2-0n-1中的缺失数字--二分本系列博文为题库刷题笔记仅在督促自己刷题如有不详之处请参考leetcode官网https://leetcode-cn.com/problemset/lcof/194/164543.面试题43-1n整数中1出现的次数
输入一个整数 n 求1n这n个整数的十进制表示中1出现的次数。 例如输入12112这些整数中包含1 的数字有1、10、11和121一共出现了5次。 完全参考https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/ 分请情况讨论某一位中1出现次数的计算方法。
class Solution(object):def countDigitOne(self, n)::type n: int:rtype: intdigit,res1,0high,cur,lown//10,n%10,0while(high!0 or cur!0):if cur0:reshigh*digitelif cur1:reshigh*digitlow1else:res(high1)*digitlowcur*digitcurhigh%10highhigh//10digit*10return res
44.面试题44-数字序列中某一位的数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中第5位从下标0开始计数是5第13位是1第19位是4等等。 请写一个函数求任意第n位对应的数字。 思路寻找n 与对应数字的关系应该有对应的公式规律。 数字num123 数字中一位数的数量n3 一个数字的位数digit123为3位数dight3 digit 位数的起始数字110100记为start
数字范围start−endstart-endstart−end以上三个量的递推公式为 digitdigit1 startstart10 count9start*dight
求解可以分为三步 1.确定n所在的数字的位数记为digit 2.确定n所在的数字记为num 3.确定n是num中的哪一位并返回结果
class Solution(object):def findNthDigit(self, n)::type n: int:rtype: intdigit,start,count1,1,9# 1.计算n所在的位数区间[1-9]是一位数一共9个[10,99]两位数一共90个while(ncount):n-countstart*10digit1count9*start*digit# 计算在该开始区间内所对应的数字numstart(n-1)//digit# 确定是数字的哪一位index(n-1)%digitreturn int(str(num)[index])45.面试题45-把数组排成最小的数-快排变种
输入一个正整数数组把数组里所有数字拼接起来排成一个数打印能拼接出的所有数字中最小的一个。 问题能拼接的数字很多么找最小的一个
[10,2] 可以拼接成102210明显102最小 本质是一个排序问题排序的目的是使得量级最小的数字排在最前面使得最后按顺序拼接的时候拼接的数字最小.
10,5两个数字谁在前按位数来比较如果放了5组成的3位数以5开头所以不能放5所以应该先放10 总之就是按位排序谁小谁先放数字左对齐比较看看谁小先比的数字对比较结果起决定性作用
比如30和330的量级比3小30应该在3前面。将数字转换成字符串拼接后比较“30”“3”“303”(“3”“30”)“30”“3”
改造快排排序规则
class Solution(object):def minNumber(self, nums)::type nums: List[int]:rtype: strdef quick_sort_str(l,r,data):if lr:ppatition(l,r,data)quick_sort_str(l,p-1,data)quick_sort_str(p1,r,data)def patition(i,j,data):pivortdata[i]while(ij):while(ij and data[j]pivortpivortdata[j]): # 比较规则需要修改j-1data[i]data[j]while(ij and data[i]pivortpivortdata[i]):i1data[j]data[i]data[i]pivortreturn inums_str[]for val in nums:nums_str.append(str(val))quick_sort_str(0,len(nums_str)-1,nums_str)resfor char in nums_str:rescharreturn res46.面试题46-把数字翻译成字符串
给定一个数字我们按照如下规则把它翻译为字符串0 翻译成 “a” 1 翻译成 “b”……11 翻译成 “l”……25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。 dp[i] 表示nums[0]-nums[i-1] 能够翻译成的数字总数 dp 由前面的状态推导后面的状态。 这题有点类似与爬楼梯
class Solution(object):def translateNum(self, num)::type num: int:rtype: intnum_lis[]while(num):num_lis.append(num%10)num//10num_lis.reverse()nlen(num_lis)if n2:return 1dp[0]*(n1)dp[0]1dp[1]1for i in range(2,n1):val10*num_lis[i-2] num_lis[i-1] # 此位置和下一位置构成的数字[0,9],[10,15],[25,99]if 0val10 or 26val99: # 09,26, nums[i]自己翻译只有一种翻译方式dp[i]dp[i-1]if 10val 26: # num12, 2自己单独翻译12一起翻译 dp[i]dp[i-1]dp[i-2]return dp[-1]47.面试题47-礼物的最大价值-dp
在一个 m*n 的棋盘的每一格都放有一个礼物每个礼物都有一定的价值价值大于 0。你可以从棋盘的左上角开始拿格子里的礼物并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值请计算你最多能拿到多少价值的礼物
递归所有的路径时间超出限制20/61。最值问题应该有最有子结构。
class Solution(object):def __init__(self):self.res0def maxValue(self, grid)::type grid: List[List[int]]:rtype: intmlen(grid)nlen(grid[0])def dfs(i,j,val):if im or jn:return valgrid[i][j]if im-1 and jn-1:self.resmax(self.res,val)return # 要不要return 呢dfs(i1,j,val)dfs(i,j1,val)dfs(0,0,0)return self.res动态规划解题dp[i][j]到单元格(i,j) 的最大价值。
48.面试题48-最长不含重复字符的子字符串-滑动窗口法
请从字符串中找出一个最长的不包含重复字符的子字符串计算该最长子字符串的长度。 滑动窗口法[l,r] 中有一个hash表统计每个字符的个数当存在时窗口变小直至个数减为1. 再移动右端。
class Solution(object):def lengthOfLongestSubstring(self, s)::type s: str:rtype: intwin{}left,right0,0res0mlen(s)while(rightm):c1s[right]if win.get(c1)None:win[c1]1else:win[c1]1right1while(win[c1]1):c2s[left]win[c2]-1left1resmax(res,right-left) # 上面right 了1所以直接减去return res49.面试题49-丑数-自底向上递归
我们把只包含质因子 2、3 和 5 的数称作丑数Ugly Number。求按从小到大的顺序的第 n 个丑数。质因子因子是质数 说明: 1 是丑数。 n 不超过1690。 思路丑数的递归性质丑数只包含质因子235因此 丑数某较小的丑数*某因子 暴力解法时间超出限制404/595
class Solution(object):def nthUglyNumber(self, n)::type n: int:rtype: inti1num1isun_hash{1:True,2:True,3:True,5:True}def is_UN(num):for val in [2,3,5]:if num%val0 and isun_hash.get(num//val):return Truereturn Falsewhile(in):num1if is_UN(num) :isun_hash[num]Truei1# print(i,num)return num动态规划 设动态规划列表 dp dp[i]代表第 i 1个丑数。 利用状态更新求解dp[n-1] 即可。 用a,b,c 三个索引指向num[a]*2,nums[b]*3,nums[c]*5第一次超过dp[i-1]索引dp[i] 就更新为最小的那个数。将a,b,c初始化为000依次填充dp 序列
class Solution(object):def nthUglyNumber(self, n)::type n: int:rtype: intdp[1]*na,b,c0,0,0for i in range(1,n):n2,n3,n5dp[a]*2,dp[b]*3,dp[c]*5 dp[i]min(n2,n3,n5)if dp[i]n2: # 只能用if ,n2,n3,n5可能会相等这时需要同时更新下标a1if dp[i]n3:b1if dp[i]n5:c1return dp[-1]50.面试题50-第一个只出现一次的字符-hash表
在字符串 s 中找出第一个只出现一次的字符。如果没有返回一个单空格。 s 只包含小写字母。
class Solution(object):def firstUniqChar(self, s)::type s: str:rtype: strwin_hash{}for char in s:if win_hash.get(char)None:win_hash[char]1else:win_hash[char]1for char in s: # 重新遍历一遍使得返回的字符是最左边第一个出现的字符串if win_hash.get(char)1:return charreturn 51.面试题52-两个链表的第一个公共节点-双指针技巧
输入两个链表找出它们的第一个公共节点。 双指针技巧 注意点先判断两个链表是否相交如果相交在寻找交点
class Solution(object):def getIntersectionNode(self, headA, headB)::type head1, head1: ListNode:rtype: ListNodeif headANone or headBNone:return Nonepa,pbheadA,headBwhile(pa.next):papa.nextwhile(pb.next):pbpb.nextif pa!pb:return Noneelse:pa,pbheadA,headBwhile(pa!pb):if pa.next:papa.nextelse:paheadBif pb.next:pbpb.nextelse:pbheadAreturn pa52.面试题53-在排序数组中找数字
统计一个数字在排序数组中出现的次数。 暴力求解通过了
class Solution(object):def search(self, nums, target)::type nums: List[int]:type target: int:rtype: intres0for num in nums:if numtarget:res1return res大佬说还可以用二分法做。
54.面试题53-2-0n-1中的缺失数字–二分
一个长度为n-1的递增排序数组中的所有数字都是唯一的并且每个数字都在范围0n-1之内。在范围0n-1内的n个数字中有且只有一个数字不在该数组中请找出这个数字。 [0,1,3],n4,l4-13,数字范围[0,3] 一共n 中情况. 缺失数字的左边nums[i]i 缺失数字的位置上nums[i]!i 暴力
class Solution(object):def missingNumber(self, nums)::type nums: List[int]:rtype: intllen(nums)for i in range(l):if nums[i]!i:return ireturn l二分查找
class Solution(object):def missingNumber(self, nums)::type nums: List[int]:rtype: intllen(nums)i,j0,l-1while(ij): # 搜索到ij的那个点就缺失点mid(ij)//2if nums[mid]mid:imid1 # 左边没有缺失else:jmid-1 # 缺失已经发生在左半段return i
