教程集 www.jiaochengji.com
教程集 >  Golang编程  >  golang教程  >  正文 算法题-golang实现

算法题-golang实现

发布时间:2021-12-11   编辑:jiaochengji.com
教程集为您提供算法题-golang实现等资源,欢迎您收藏本站,我们将为您提供最新的算法题-golang实现资源
<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"/></svg>

<h3>算法题-golang实现</h3> <ul><li>第一章</li><li><ul><li>1.无重复字符的最长子串</li><li>2.最长公共前缀</li><li>3.字符串的排列</li><li>4.字符串相乘</li><li>5.翻转字符串里的单词</li><li>6.简化Linux路径</li><li>7.复原IP地址</li></ul></li></ul>

<h1>第一章</h1>

题目来源于Leetcode题库

<h2>1.无重复字符的最长子串</h2>

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

<pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token punctuation">(</span> <span class="token string">"fmt"</span> <span class="token punctuation">)</span> <span class="token keyword">func</span> <span class="token function">get</span><span class="token punctuation">(</span>index <span class="token builtin">int</span><span class="token punctuation">,</span> st <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">rune</span><span class="token punctuation">,</span> mp <span class="token keyword">map</span><span class="token punctuation">[</span><span class="token builtin">rune</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span> <span class="token punctuation">{</span> <span class="token keyword">var</span> lenstr <span class="token builtin">int</span> <span class="token operator">=</span> <span class="token number">0</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> index<span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token function">len</span><span class="token punctuation">(</span>st<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator"> </span><span class="token punctuation">{</span> <span class="token keyword">if</span> mp<span class="token punctuation">[</span>st<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span> mp<span class="token punctuation">[</span>st<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">=</span> i <span class="token operator"> </span> <span class="token number">1</span> lenstr<span class="token operator"> </span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> mp <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token keyword">map</span><span class="token punctuation">[</span><span class="token builtin">rune</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token function">max</span><span class="token punctuation">(</span>i <span class="token operator">-</span> index<span class="token punctuation">,</span> <span class="token function">get</span><span class="token punctuation">(</span>index <span class="token operator"> </span> <span class="token number">1</span><span class="token punctuation">,</span> st<span class="token punctuation">,</span> mp<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>lenstr<span class="token punctuation">)</span> <span class="token keyword">return</span> lenstr <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">max</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span> y <span class="token builtin">int</span><span class="token punctuation">)</span> <span class="token builtin">int</span><span class="token punctuation">{</span> <span class="token keyword">if</span> x <span class="token operator"><</span> y <span class="token punctuation">{</span> <span class="token keyword">return</span> y <span class="token punctuation">}</span> <span class="token keyword">return</span> x <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> s <span class="token operator">:=</span> <span class="token string">"bbbbb"</span> mp <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token keyword">map</span><span class="token punctuation">[</span><span class="token builtin">rune</span><span class="token punctuation">]</span><span class="token builtin">int</span><span class="token punctuation">)</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token function">rune</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">,</span> mp<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <h2>
2.最长公共前缀</h2>

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入: [“flower”,“flow”,“flight”]
输出: “fl”
示例 2:
输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

<pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token punctuation">(</span> <span class="token string">"fmt"</span> <span class="token punctuation">)</span> <span class="token keyword">func</span> <span class="token function">getLongestStr</span><span class="token punctuation">(</span>strs <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">string</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> strs <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token operator">||</span> <span class="token function">len</span><span class="token punctuation">(</span>strs<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token string">""</span> <span class="token punctuation">}</span> minStr <span class="token operator">:=</span> <span class="token function">getMinStr</span><span class="token punctuation">(</span>strs<span class="token punctuation">)</span> subStrs <span class="token operator">:=</span> <span class="token function">getSubStrs</span><span class="token punctuation">(</span>minStr<span class="token punctuation">)</span> stopFlag <span class="token operator">:=</span> <span class="token boolean">false</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>subStrs<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span> <span class="token punctuation">{</span> stopFlag <span class="token operator">=</span> <span class="token boolean">false</span> <span class="token keyword">for</span> <span class="token boolean">_</span><span class="token punctuation">,</span> org <span class="token operator">:=</span> <span class="token keyword">range</span> strs <span class="token punctuation">{</span> <span class="token keyword">if</span> org<span class="token punctuation">[</span><span class="token number">0</span> <span class="token punctuation">:</span> <span class="token function">len</span><span class="token punctuation">(</span>subStrs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">!=</span> subStrs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">{</span> stopFlag <span class="token operator">=</span> <span class="token boolean">true</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> <span class="token operator">!</span>stopFlag <span class="token punctuation">{</span> <span class="token keyword">return</span> subStrs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token string">""</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">getMinStr</span><span class="token punctuation">(</span>strs <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">string</span> <span class="token punctuation">{</span> length <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>strs<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> index <span class="token operator">:=</span> <span class="token number">0</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token function">len</span><span class="token punctuation">(</span>strs<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>strs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator"><=</span> length <span class="token punctuation">{</span> length <span class="token operator">=</span> <span class="token function">len</span><span class="token punctuation">(</span>strs<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> index <span class="token operator">=</span> i <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> strs<span class="token punctuation">[</span>index<span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">getSubStrs</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span> <span class="token punctuation">{</span> subStrs <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator"> </span> <span class="token punctuation">{</span> subStrs<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> s<span class="token punctuation">[</span><span class="token number">0</span> <span class="token punctuation">:</span> i <span class="token operator"> </span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> subStrs <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> strs <span class="token operator">:=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span> <span class="token punctuation">{</span><span class="token string">"flower"</span><span class="token punctuation">,</span><span class="token string">"flow"</span><span class="token punctuation">,</span><span class="token string">"flight"</span><span class="token punctuation">}</span> s <span class="token operator">:=</span> <span class="token function">getLongestStr</span><span class="token punctuation">(</span>strs<span class="token punctuation">)</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <h2>
3.字符串的排列</h2>

给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例2:
输入: s1= “ab” s2 = “eidboaoo”
输出: False
注意:
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

<pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token punctuation">(</span> <span class="token string">"fmt"</span> <span class="token punctuation">)</span> <span class="token keyword">func</span> <span class="token function">check</span><span class="token punctuation">(</span>s1 <span class="token builtin">string</span><span class="token punctuation">,</span> s2 <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">bool</span> <span class="token punctuation">{</span> l1<span class="token operator">:=</span><span class="token function">len</span><span class="token punctuation">(</span>s1<span class="token punctuation">)</span> l2<span class="token operator">:=</span><span class="token function">len</span><span class="token punctuation">(</span>s2<span class="token punctuation">)</span> <span class="token keyword">if</span> l2<span class="token operator"><</span>l1<span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token boolean">false</span> <span class="token punctuation">}</span> <span class="token keyword">var</span> c1 <span class="token punctuation">[</span><span class="token number">26</span><span class="token punctuation">]</span><span class="token builtin">int</span> <span class="token keyword">var</span> c2 <span class="token punctuation">[</span><span class="token number">26</span><span class="token punctuation">]</span><span class="token builtin">int</span> <span class="token keyword">for</span> k<span class="token punctuation">,</span>v <span class="token operator">:=</span> <span class="token keyword">range</span> s1 <span class="token punctuation">{</span> c1<span class="token punctuation">[</span>v<span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span><span class="token operator"> </span> c2<span class="token punctuation">[</span>s2<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span><span class="token operator"> </span> <span class="token punctuation">}</span> <span class="token keyword">for</span> i<span class="token operator">:=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator"><</span>l2<span class="token operator">-</span>l1<span class="token operator"> </span><span class="token number">1</span> <span class="token punctuation">;</span>i<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token keyword">if</span> c1<span class="token operator">==</span>c2 <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token boolean">true</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> i<span class="token operator"><</span>l2<span class="token operator">-</span>l1 <span class="token punctuation">{</span> c2<span class="token punctuation">[</span>s2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span><span class="token operator">--</span> c2<span class="token punctuation">[</span>s2<span class="token punctuation">[</span>i<span class="token operator"> </span>l1<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">'a'</span><span class="token punctuation">]</span><span class="token operator"> </span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>c2<span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token boolean">false</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> s1 <span class="token operator">:=</span> <span class="token string">"adc"</span> s2 <span class="token operator">:=</span> <span class="token string">"dcda"</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token function">check</span><span class="token punctuation">(</span>s1<span class="token punctuation">,</span> s2<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <h2>
4.字符串相乘</h2>

给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
说明:
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头,除非是数字 0 本身。
不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。

<pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token punctuation">(</span> <span class="token string">"fmt"</span> <span class="token punctuation">)</span> <span class="token keyword">func</span> <span class="token function">multiply</span><span class="token punctuation">(</span>num1 <span class="token builtin">string</span><span class="token punctuation">,</span> num2 <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">string</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> num1 <span class="token operator">==</span> <span class="token string">"0"</span> <span class="token operator">||</span> num2 <span class="token operator">==</span> <span class="token string">"0"</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token string">"0"</span> <span class="token punctuation">}</span> s<span class="token operator">:=</span><span class="token string">""</span> num1len<span class="token punctuation">,</span> num2len <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>num1<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">len</span><span class="token punctuation">(</span>num2<span class="token punctuation">)</span> <span class="token keyword">var</span> mul<span class="token punctuation">,</span> sum <span class="token builtin">byte</span> resArr <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">byte</span><span class="token punctuation">,</span> num1len <span class="token operator"> </span> num2len<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> num1len <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> j <span class="token operator">:=</span> num2len <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">--</span> <span class="token punctuation">{</span> mul <span class="token operator">=</span> <span class="token punctuation">(</span>num1<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>num2<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token string">'0'</span><span class="token punctuation">)</span> sum <span class="token operator">=</span> resArr<span class="token punctuation">[</span>i <span class="token operator"> </span> j <span class="token operator"> </span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator"> </span> mul resArr<span class="token punctuation">[</span>i <span class="token operator"> </span> j<span class="token punctuation">]</span> <span class="token operator"> =</span> sum <span class="token operator">/</span> <span class="token number">10</span> resArr<span class="token punctuation">[</span>i <span class="token operator"> </span> j <span class="token operator"> </span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> sum <span class="token operator">%</span> <span class="token number">10</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">for</span> <span class="token boolean">_</span><span class="token punctuation">,</span> v <span class="token operator">:=</span> <span class="token keyword">range</span> resArr <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span> <span class="token keyword">if</span> <span class="token operator">!</span><span class="token punctuation">(</span><span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">&&</span> v <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> s <span class="token operator"> =</span> <span class="token function">string</span><span class="token punctuation">(</span>v<span class="token operator"> </span><span class="token string">'0'</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> s <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token function">multiply</span><span class="token punctuation">(</span><span class="token string">"20"</span><span class="token punctuation">,</span><span class="token string">"30"</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <h2>
5.翻转字符串里的单词</h2>

给定一个字符串,逐个翻转字符串中的每个单词。
示例 1:
输入: “the sky is blue”
输出: “blue is sky the”
示例 2:
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
说明:
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

<pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token punctuation">(</span> <span class="token string">"fmt"</span> <span class="token punctuation">)</span> <span class="token keyword">func</span> <span class="token function">reverseWords</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">string</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token string">""</span> <span class="token punctuation">}</span> res <span class="token operator">:=</span> <span class="token string">""</span> i <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">for</span> i <span class="token operator">>=</span> <span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">32</span> <span class="token operator">&&</span> i<span class="token operator">-</span><span class="token number">1</span> <span class="token operator">></span> <span class="token number">0</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token number">32</span> <span class="token punctuation">{</span> res <span class="token operator"> =</span> <span class="token string">" "</span> i<span class="token operator">--</span> endIndex <span class="token operator">:=</span> i <span class="token operator"> </span> <span class="token number">1</span> <span class="token keyword">for</span> i <span class="token operator">>=</span> <span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">32</span> <span class="token punctuation">{</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> i<span class="token operator">--</span> <span class="token punctuation">}</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">:</span>endIndex<span class="token punctuation">]</span><span class="token punctuation">)</span> res <span class="token operator"> =</span> <span class="token function">string</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">:</span>endIndex<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token number">32</span> <span class="token punctuation">{</span> res <span class="token operator"> =</span> <span class="token string">" "</span> endIndex <span class="token operator">:=</span> i <span class="token operator"> </span> <span class="token number">1</span> <span class="token keyword">for</span> i <span class="token operator">>=</span><span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">32</span><span class="token punctuation">{</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> i<span class="token operator">--</span> <span class="token punctuation">}</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">:</span>endIndex<span class="token punctuation">]</span><span class="token punctuation">)</span> res <span class="token operator"> =</span> <span class="token function">string</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">:</span>endIndex<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> i<span class="token operator">--</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span> <span class="token operator">></span> <span class="token number">1</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> res<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">:</span><span class="token function">len</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> res <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> str <span class="token operator">:=</span> <span class="token string">"a good example"</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token function">reverseWords</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <h2>
6.简化Linux路径</h2>

简化路径
以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。
在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (…) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径
请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。
示例 1:
输入:"/home/"
输出:"/home"
解释:注意,最后一个目录名后面没有斜杠。
示例 2:
输入:"/…/"
输出:"/"
解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。
示例 3:
输入:"/home//foo/"
输出:"/home/foo"
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。
示例 4:
输入:"/a/./b/…/…/c/"
输出:"/c"
示例 5:
输入:"/a/…/…/b/…/c//.//"
输出:"/c"
示例 6:
输入:"/a//bc/d//././/…"
输出:"/a/b/c"
注意:存在文件名为.home or …home的

<pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token punctuation">(</span> <span class="token string">"fmt"</span> <span class="token punctuation">)</span> <span class="token keyword">func</span> <span class="token function">simplifyPath</span><span class="token punctuation">(</span>path <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token builtin">string</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>path<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token string">""</span> <span class="token punctuation">}</span> level <span class="token operator">:=</span> <span class="token number">0</span> resPath <span class="token operator">:=</span> <span class="token string">""</span> length <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>path<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><</span> length<span class="token punctuation">;</span> i<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token keyword">if</span> path<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">47</span> <span class="token punctuation">{</span> <span class="token comment">// /</span> <span class="token keyword">continue</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator"> </span> <span class="token number">1</span> <span class="token operator">==</span> length <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">46</span> <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">46</span><span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token punctuation">(</span>i <span class="token operator"> </span> <span class="token number">2</span> <span class="token operator"><</span> length <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">46</span> <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">46</span> <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">47</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// mathch../ or end with ..</span> level<span class="token operator">--</span> <span class="token keyword">if</span> level <span class="token operator"><</span> <span class="token number">0</span> <span class="token punctuation">{</span> level <span class="token operator">=</span> <span class="token number">0</span> resPath <span class="token operator">=</span> <span class="token string">""</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> spliceFlag <span class="token operator">:=</span> <span class="token number">0</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>resPath<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> resPath<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">47</span> <span class="token punctuation">{</span> spliceFlag <span class="token operator">=</span> i <span class="token keyword">break</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> resPath <span class="token operator">=</span> <span class="token function">string</span><span class="token punctuation">(</span>resPath<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">:</span>spliceFlag<span class="token punctuation">]</span><span class="token punctuation">)</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token string">"spliceFlag:"</span><span class="token punctuation">,</span> spliceFlag<span class="token punctuation">)</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token string">"subtract:"</span><span class="token punctuation">,</span> resPath<span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>i <span class="token operator"> </span> <span class="token number">1</span> <span class="token operator"><</span> length <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">46</span> <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token operator"> </span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">47</span><span class="token punctuation">)</span> <span class="token operator">||</span> <span class="token punctuation">(</span>i <span class="token operator">==</span> length <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">&&</span> path<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">46</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// mathch./ or end with .</span> <span class="token keyword">continue</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> resPath <span class="token operator"> =</span> <span class="token string">"/"</span> <span class="token keyword">for</span> i <span class="token operator"><</span> length <span class="token punctuation">{</span> <span class="token keyword">if</span> path<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">47</span> <span class="token punctuation">{</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> resPath <span class="token operator"> =</span> <span class="token function">string</span><span class="token punctuation">(</span>path<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token string">"add:"</span><span class="token punctuation">,</span> resPath<span class="token punctuation">)</span> <span class="token punctuation">}</span> i<span class="token operator"> </span> <span class="token punctuation">}</span> level<span class="token operator"> </span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>resPath<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token string">"/"</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> resPath <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> path <span class="token operator">:=</span> <span class="token string">"/..hidden"</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span>path<span class="token punctuation">)</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token string">"result:"</span><span class="token punctuation">,</span> <span class="token function">simplifyPath</span><span class="token punctuation">(</span>path<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <h2>
7.复原IP地址</h2>

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]
思路:回溯法

<pre><code class="lang-go hljs"><span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token punctuation">(</span> <span class="token string">"fmt"</span> <span class="token punctuation">)</span> <span class="token keyword">func</span> <span class="token function">restoreIpAddresses</span><span class="token punctuation">(</span>s <span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span> <span class="token punctuation">{</span> result <span class="token operator">:=</span> <span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token function">backtrack</span><span class="token punctuation">(</span><span class="token function">make</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> s<span class="token punctuation">,</span> <span class="token operator">&</span>result<span class="token punctuation">)</span> <span class="token keyword">return</span> result <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">backtrack</span><span class="token punctuation">(</span>putStr <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">,</span> s <span class="token builtin">string</span><span class="token punctuation">,</span> result <span class="token operator">*</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token builtin">string</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> resultLen <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>putStr<span class="token punctuation">)</span> <span class="token keyword">if</span> resultLen <span class="token operator">==</span> <span class="token number">4</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">{</span> <span class="token operator">*</span>result <span class="token operator">=</span> <span class="token function">append</span><span class="token punctuation">(</span><span class="token operator">*</span>result<span class="token punctuation">,</span> putStr<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator"> </span><span class="token string">"."</span><span class="token operator"> </span>putStr<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator"> </span><span class="token string">"."</span><span class="token operator"> </span>putStr<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator"> </span><span class="token string">"."</span><span class="token operator"> </span>putStr<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token punctuation">}</span> <span class="token keyword">for</span> i <span class="token operator">:=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> <span class="token number">3</span><span class="token punctuation">;</span> i<span class="token operator"> </span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>s<span class="token punctuation">)</span> <span class="token operator"><</span> i <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token punctuation">}</span> str <span class="token operator">:=</span> s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">:</span>i<span class="token punctuation">]</span> strLen <span class="token operator">:=</span> <span class="token function">len</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span> <span class="token keyword">if</span> strLen <span class="token operator">==</span> <span class="token number">3</span> <span class="token operator">&&</span> strings<span class="token punctuation">.</span><span class="token function">Compare</span><span class="token punctuation">(</span>str<span class="token punctuation">,</span> <span class="token string">"255"</span><span class="token punctuation">)</span> <span class="token operator">></span> <span class="token number">0</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> strLen <span class="token operator">></span> <span class="token number">1</span> <span class="token operator">&&</span> s<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token string">'0'</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token punctuation">}</span> putStr <span class="token operator">=</span> <span class="token function">append</span><span class="token punctuation">(</span>putStr<span class="token punctuation">,</span> str<span class="token punctuation">)</span> <span class="token function">backtrack</span><span class="token punctuation">(</span>putStr<span class="token punctuation">,</span> s<span class="token punctuation">[</span>i<span class="token punctuation">:</span><span class="token punctuation">]</span><span class="token punctuation">,</span> result<span class="token punctuation">)</span> putStr <span class="token operator">=</span> putStr<span class="token punctuation">[</span><span class="token punctuation">:</span><span class="token function">len</span><span class="token punctuation">(</span>putStr<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token function">restoreIpAddresses</span><span class="token punctuation">(</span><span class="token string">"25525511135"</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> 到此这篇关于“算法题-golang实现”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持JQ教程网!

您可能感兴趣的文章:
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
golang runtime 简析
Golang中的垃圾回收算法
Go实战--golang中各种排序算法实现以及生成随机数
golang 爬楼梯算法(递归&非递归)
Golang算法题目小计
Golang 一致性Hash算法实现
Golang笔记:语法,并发思想,web开发,Go微服务相关
golang的map为什么不设计成同步(安全)的
golang 算法课 给定乱序的0, 1 输出前0 后1

[关闭]
~ ~