我要评论No.820 单词的压缩编码
题目描述：给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
解题思路：目标是保留所有不是其他单词后缀的单词，因此考虑使用字典树的方法。找到是否不同的单词具有相同的后缀，我们可以将其反序之后插入字典树中。例如，我们有 "time" 和 "me"，可以将 "emit" 和 "em" 插入字典树中。
# 定义字典树中的一个节点
class Node(object):
def __init__(self):
self.children={}
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
words = list(set(words)) #需要去重，否则在之后计算“叶子高度”的时候会重复计算
trie=Node() #这是字典树的根
nodes=[] #这里保存着每个word对应的最后一个节点，比如对于单词time，它保存字母t对应的节点（因为是从后往前找的）
for word in words: #逐个单词遍历
now=trie #定义临时变量保存当前节点
for w in reversed(word): #字符串反转
if w in now.children: #如果在，就继续往下遍历
now=now.children[w]
else:
now.children[w]=Node()
now=now.children[w]
nodes.append(now)
ans=0
for w,c in zip(words,nodes):
if len(c.children)==0: #没有children，意味着这个节点是个叶子，nodes保存着每个word对应的最后一个节点，当它是一个叶子时，我们就该累加这个word的长度+1，这就是为什么我们在最开始要去重
ans+=len(w)+1
return ans
No.1109 航班预订
题目描述：这里有 n 个航班，它们分别从 1 到 n 进行编号。我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。
解题思路：这个题如果采用暴力法，尝试后发现超时，因此考虑使用差分数列的思想。每一次区间性累加，差分数列变的值都是两端的，因此每次计算只要算两个值即可。时间复杂度大大减小。
class Solution:
def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
res=(n+1)*[0]
for i,j,k in bookings:
res[i-1]+=k
res[j]-=k
for i in range(1,n):
res[i]+=res[i-1]
return res[:-1]
No.5 最长回文子串
题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
解题思路：首先这是要求一个回文串，并且求的是子串。这种情况下，首先考虑使用中心扩散法，从中间位置向两边扩散。
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<2) return s;
int maxlen=0,start=0;
for(int i=0;i<s.size()-1;++i)
{
find(s,i,i,start,maxlen);
find(s,i,i+1,start,maxlen);
}
return s.substr(start,maxlen);
}
void find(string s,int left,int right,int& start,int& maxlen)
{
while(left>=0&&right<s.size()&&s[left]==s[right]) //向两边扩散
{
--left;
++right;
}
if(maxlen<right-left-1)
{
start=left+1;
maxlen=right-left-1;
}
}
};
No.2 两数相加
题目描述：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解题思路：并行求两个链表的逐位和
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *newlist=new ListNode(-1),*cur=newlist;
int current=0;//进位值
while(l1||l2)
{
int val1=l1?l1->val:0;
int val2=l2?l2->val:0;
int sum=val1+val2+current;
current=sum/10;
cur->next=new ListNode(sum%10);
cur=cur->next;
if(l1!=nullptr) l1=l1->next;
if(l2!=nullptr) l2=l2->next;
}
if(current) cur->next=new ListNode(1);
return newlist->next;
}
};
本文地址：https://blog.csdn.net/u014509577/article/details/107590520
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论