leetcode解题思路分析（六十三）535 - 541 题

系统管理员 2022-10-28 10:10 41阅读 0赞

1.  TinyURL 的加密与解密  
    TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原本的URL。

**首先改为N进制存储，然后进行哈希**

class Solution { 
    public:
    
        // Encodes a URL to a shortened URL.
        using ull = unsigned long long;
        const ull base = 11;
        const string code = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        const ull len = code.size();
        unordered_map<string, string> m;
        
        ull hashcode(const string& s) { 
            ull hash = 0;
            for (auto c : s) { 
                hash *= base;
                hash += c;
            }
            return hash;
        }
        
        string ULLToString(ull n) { 
            string s;
            while (n != 0) { 
                s += code[n % len];
                n /= len;
            }
            return s;
        }
        
        string encode(string longUrl) { 
            string shortUrl = ULLToString(hashcode(longUrl));
            m[shortUrl] = longUrl;
            return shortUrl;
        }
    
        // Decodes a shortened URL to its original URL.
        string decode(string shortUrl) { 
            return m[shortUrl];
        }
    };
    
    // Your Solution object will be instantiated and called as such:
    // Solution solution;
    // solution.decode(solution.encode(url));

1.  复数乘法  
    给定两个表示复数的字符串。返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。

**按要求解析，然后计算，最后再转换成字符串即可**

class Solution 
    { 
        void parseStr(int &a, int &b, string str)
        { 
            int i = 0, minus = 1;
    
            if (str[i] == '-')
            { 
                minus = -1;
                i++;
            }
    
            while (str[i] != '+' && i < str.size())
            { 
                a = a * 10 + (str[i] - '0');
                i++;
            }
    
            a *= minus;
    
            minus = 1;
            
            if (str[i] == '+' && str[i + 1] == '-')
            { 
                 minus = -1;
                 i++;
            }
    
            i++;
    
            while (str[i] != 'i' && i < str.size())
            { 
                b = b * 10 + (str[i] - '0');
                i++;
            }
    
            b *= minus;
    
            return;    
        }
    
        void unparseStr(int a, int b, string &str)
        { 
            string str1 = to_string(a);
            string str2 = to_string(b);
    
            str = str1 + '+' + str2 + 'i';
       
            return;
        }
    
    public:
        string complexNumberMultiply(string a, string b) 
        { 
            int firstA = 0, secondA = 0, firstB = 0, secondB = 0;
            parseStr(firstA, secondA, a);
            parseStr(firstB, secondB, b);
    
            int firstRet = 0, secondRet = 0;
            firstRet  = firstA * firstB - secondA * secondB;
            secondRet = firstA * secondB + firstB * secondA;
    
            string ret;
            unparseStr(firstRet, secondRet, ret);
    
            return ret;
        }
    };

1.  把二叉搜索树转换为累加树  
    给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

**利用 Morris 遍历的方法，反序中序遍历该二叉搜索树，即可实现线性时间与常数空间的遍历**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
        TreeNode* getSuccessor(TreeNode* node) { 
            TreeNode* succ = node->right;
            while (succ->left != nullptr && succ->left != node) { 
                succ = succ->left;
            }
            return succ;
        }
    
        TreeNode* convertBST(TreeNode* root) { 
            int sum = 0;
            TreeNode* node = root;
    
            while (node != nullptr) { 
                if (node->right == nullptr) { 
                    sum += node->val;
                    node->val = sum;
                    node = node->left;
                } else { 
                    TreeNode* succ = getSuccessor(node);
                    if (succ->left == nullptr) { 
                        succ->left = node;
                        node = node->right;
                    } else { 
                        succ->left = nullptr;
                        sum += node->val;
                        node->val = sum;
                        node = node->left;
                    }
                }
            }
    
            return root;
        }
    };

1.  最小时间差  
    给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

**转化为分钟排序，12小时以内则直接求差值，12小时以上考虑最后一个数**

class Solution { 
    public: 
        int findMinDifference(vector<string>& timePoints) { 
            int n = timePoints.size();
            int result = INT_MAX;
            vector<int> item(n, 0);
            for(int i = 0; i < n; i++)
                item[i] = stoi(timePoints[i].substr(0, 2)) * 60 + stoi(timePoints[i].substr(3, 2));
    
            sort(item.begin(), item.end());
    
            //如果最后一个和第一个差值在12小时内，那么这个就是最小值
            for(int i = 0; i < n-1; i++){ 
                result = min(result, item[i+1] - item[i]);
            }
            //如果最后一个和第一个差值在12小时外，那么肯定等于最小的+1440（24:00）和最大的差值
            result = min(result, item[0] + 1440 - item[n-1]);
            return result;
        }
    };

1.  有序数组中的单一元素  
    给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

**位操作异或一下就好了**

class Solution { 
    public:
        int singleNonDuplicate(vector<int>& nums) { 
            int ret = 0;
            
            for (auto n : nums)
            { 
                ret ^= n;
            }
    
            return ret;
        }
    };

1.  反转字符串2  
    给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。  
    如果剩余字符少于 k 个，则将剩余字符全部反转。  
    如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

**没啥好说的**

class Solution { 
    public:
        string reverseStr(string s, int k) { 
            for (int i = 0; i < s.size(); i += (2 * k)) { 
                // 1. 每隔 2k 个字符的前 k 个字符进行反转
                // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
                if (i + k <= s.size()) { 
                    reverse(s.begin() + i, s.begin() + i + k );
                    continue;
                }
                // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
                reverse(s.begin() + i, s.begin() + s.size());
            }
            return s;
        }
    };