《leetcode》华为技术面试题库

旧城等待， 2023-03-01 12:51 22阅读 0赞

### 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;
        }
    };