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>
<blockquote class="layui-elem-quote" style="width: 100%;overflow:hidden">
作者: ac123321123321
链接: https://blog.csdn.net/ac123321123321/article/details/113138563
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
</blockquote>
到此这篇关于“算法题-golang实现”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持JQ教程网!
您可能感兴趣的文章:
数据结构和算法(Golang实现)(28)查找算法-AVL树
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
数据结构和算法(Golang实现)(7)简单入门Golang-标准库
数据结构和算法(Golang实现)(1)简单入门Golang-前言
Go语言 几个亟待解决的Go语言问题
数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法
Golang常见数据结构-可变长数组
Golang中的垃圾回收算法
golang runtime 简析
go基础算法思想