电商网站模板引擎,惠阳做网站公司,局域网站开发,户外网站模板最近一直在做以前的题#xff0c;刷题量都没有怎么增长#xff0c;感觉自己算法一直不太行#xff0c;但也只能菜就多练了。
打卡记录 由子序列构造的最长回文串的长度#xff08;区间DP#xff09;
链接
第二次刷这道题#xff0c;相比上回思路来的很快#xff0c;但…最近一直在做以前的题刷题量都没有怎么增长感觉自己算法一直不太行但也只能菜就多练了。
打卡记录 由子序列构造的最长回文串的长度区间DP
链接
第二次刷这道题相比上回思路来的很快但是对 if i len(word1) j 的限制条件依旧不是很会设立。
class Solution:def longestPalindrome(self, word1: str, word2: str) - int:s word1 word2n, ans len(s), 0f [[0] * n for _ in range(n)]for i in range(n - 1, -1, -1):f[i][i] 1for j in range(i 1, n):if s[i] s[j]:f[i][j] f[i 1][j - 1] 2if i len(word1) j:ans max(ans, f[i][j])else:f[i][j] max(f[i][j - 1], f[i 1][j])return ans 阈值距离内邻居最少的城市Floyd
关于 Floyd 的最外层为 k k k 的解释最外层的 k k k 是枚举位于起点和终点中的跳板贪心的正确性必须得到保证而这个保证在于再求 f [ i ] [ j ] f[i][j] f[i][j] 时 f [ i ] [ k ] f[i][k] f[i][k] 和 f [ k ] [ j ] f[k][j] f[k][j] 若可达(一般来说把不可达设置为无穷大)必须为最优值(即最短距离)。
class Solution:def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) - int:g [[0x3f3f3f3f] * (n) for _ in range(n)]for x, y, c in edges:g[x][y] g[y][x] cfor k in range(n):for i in range(n):for j in range(n):g[i][j] min(g[i][j], g[i][k] g[k][j])ans 0min_cnt inffor i in range(n):cnt 0for j in range(n):if j ! i and g[i][j] distanceThreshold:cnt 1if cnt min_cnt:min_cnt cntans ireturn ans
