智能pos機長度,002 無重復最長子串長度

 新聞資訊2  |   2023-05-30 09:32  |  投稿人:pos機之家

網(wǎng)上有很多關于智能pos機長度,002 無重復最長子串長度的知識,也有很多人為大家解答關于智能pos機長度的問題,今天pos機之家(m.shineka.com)為大家整理了關于這方面的知識,讓我們一起來看下吧!

本文目錄一覽:

1、智能pos機長度

智能pos機長度

首先,老原則,先直接上代碼。

//// Created by tannzh on 2020/6/11.///*給定一個字符串,請你找出其中不含有重復字符的 最長子串 的長度。示例 1:輸入: "abcabcbb"輸出: 3解釋: 因為無重復字符的最長子串是 "abc",所以其長度為 3。示例 2:輸入: "bbbbb"輸出: 1解釋: 因為無重復字符的最長子串是 "b",所以其長度為 1。示例 3:輸入: "pwwkew"輸出: 3解釋: 因為無重復字符的最長子串是 "wke",所以其長度為 3。  請注意,你的答案必須是 子串 的長度,"pwke" 是一個子序列,不是子串。 */#include <iostream>#include <string>#include <unordered_map>#include <algorithm>using namespace std;class Solution {public: int lengthOfLongestSubstring(string s) { size_t region = 0, start = 0; unordered_map<char, size_t> trace; for(size_t i = 0; i < s.size(); ++i){ auto found = trace.find(s[i]); if(found != trace.end() && found->second >= start) { region = std::max(region, i - start); start = found->second + 1; } trace[s[i]] = i; } return std::max(region, s.size() - start); }};int main(int argc, char **argv){ Solution s; std::string testStr1 = "abcabcbb"; std::string testStr2 = "bbbbb"; std::string testStr3 = "pwwkew"; std::cout << testStr1 << ", lengthOfLongestSubstring: " << s.lengthOfLongestSubstring(testStr1) << std::endl; std::cout << testStr2 << ", lengthOfLongestSubstring: " << s.lengthOfLongestSubstring(testStr2) << std::endl; std::cout << testStr3 << ", lengthOfLongestSubstring: " << s.lengthOfLongestSubstring(testStr3) << std::endl; return 0;}解題思路

首先,求的只是長度,那么一定有一個 trace 來邊記錄邊比較(max)。

其次,沒有重復字符幾乎是唯一條件,那么檢查重復顯然用 k-v mapping.

最后,要考慮一次迭代過程中,如何度量這個長度。

設 substr 的起點為 start(s), 終點為 last(l). 每一次迭代,記錄一張索引表。

上圖所示,last 指向 `a`, 查詢當前表可知,`a` 的位置記錄在案,且 `pos >= start`. 故此刻誕生一個 substr. 長度為 `last - start`. s 更新位置為 `pos + 1`.有:

auto found = cache.find(s[last]);if (found != cache.end() && found->second >= start) { region = max(region, last - start); start = found->second + 1;}cache[s[last]] = last;

注意最終還需要比較一次,返回 max(ret, s.size() - start)

以上就是關于智能pos機長度,002 無重復最長子串長度的知識,后面我們會繼續(xù)為大家整理關于智能pos機長度的知識,希望能夠幫助到大家!

轉(zhuǎn)發(fā)請帶上網(wǎng)址:http://m.shineka.com/newsone/60209.html

你可能會喜歡:

版權聲明:本文內(nèi)容由互聯(lián)網(wǎng)用戶自發(fā)貢獻,該文觀點僅代表作者本人。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。如發(fā)現(xiàn)本站有涉嫌抄襲侵權/違法違規(guī)的內(nèi)容, 請發(fā)送郵件至 babsan@163.com 舉報,一經(jīng)查實,本站將立刻刪除。