面试题之算法汇总

面试题之算法集锦

1. 有字符串A,B,求取AB字符串中都含有的字符,例如:①A="hello",B="jeesite",那么输出"e",②A="common",B="month",则输出"mno",输出串的顺序没有要求.

思路1:<span style="color: #000000;">把A去重得到A1</span>,B去重得到B1,然后对A1,B1分别进行排序,然后遍历较短的字符串的每个字符是否存在于较长的字符串中,<span style="color: #000000;">存在则输出问题</span>:1.思路很简单,基本大家都会这么考虑,<span style="color: #000000;">但是面试的时候就没有亮点了思路2</span>:<span style="color: #000000;">假设AB串只包含小写(其实无所谓)</span>,那么创建一个数组,数组的key为a->z,<span style="color: #000000;">value都是0;</span><span style="color: #000000;">php    </span><span style="color: #0000ff;">function</span> stringToChar(<span style="color: #800080;">$str</span>,<span style="color: #800080;">$num</span>=1,<span style="color: #800080;">$tmp</span>=<span style="color: #0000ff;">null</span><span style="color: #000000;">){        </span><span style="color: #0000ff;">if</span>(<span style="color: #0000ff;">empty</span>(<span style="color: #800080;">$tmp</span><span style="color: #000000;">)){</span><span style="color: #800080;">$tmp</span>=<span style="color: #0000ff;">array</span>('a'=>0,'b'=>0,'c'=>0,'d'=>0,'e'=>0,'f'=>0,'g'=>0,'h'=>0,'i'=>0,'j'=>0,'k'=>0,'l'=>0,'m'=>0,'n'=>0,'o'=>0,'p'=>0,'q'=>0,'r'=>0,'s'=>0,'t'=>0,'u'=>0,'v'=>0,'w'=>0,'x'=>0,'y'=>0,'z'=>0<span style="color: #000000;">);        }        </span><span style="color: #800080;">$arr_temp</span>=<span style="color: #008080;">str_split</span>(<span style="color: #800080;">$str</span>,1<span style="color: #000000;">);        </span><span style="color: #0000ff;">foreach</span>(<span style="color: #800080;">$arr_temp</span> <span style="color: #0000ff;">as</span> <span style="color: #800080;">$v</span><span style="color: #000000;">){            </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$tmp</span>[<span style="color: #800080;">$v</span>]$num<span style="color: #000000;">){                </span><span style="color: #800080;">$tmp</span>[<span style="color: #800080;">$v</span>]+=<span style="color: #800080;">$num</span><span style="color: #000000;">;            }        }        </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$tmp</span><span style="color: #000000;">;    }    </span><span style="color: #0000ff;">function</span> getStringIntersect(<span style="color: #800080;">$str1</span>, <span style="color: #800080;">$str2</span><span style="color: #000000;">){        </span><span style="color: #800080;">$temp</span>=stringToChar(<span style="color: #800080;">$str1</span>,1<span style="color: #000000;">);        </span><span style="color: #008000;">//</span><span style="color: #008000;">$str2的$num用2 就是为了区分 stemp中的原来的1 是 $str1中设置的</span>        <span style="color: #800080;">$temp</span>=stringToChar(<span style="color: #800080;">$str2</span>,2,<span style="color: #800080;">$temp</span><span style="color: #000000;">);        </span><span style="color: #800080;">$result</span>=''<span style="color: #000000;">;        </span><span style="color: #0000ff;">foreach</span> (<span style="color: #800080;">$temp</span> <span style="color: #0000ff;">as</span> <span style="color: #800080;">$key</span> => <span style="color: #800080;">$value</span><span style="color: #000000;">) {            </span><span style="color: #0000ff;">if</span>(<span style="color: #800080;">$value</span>===3<span style="color: #000000;">){                </span><span style="color: #800080;">$result</span>.=<span style="color: #800080;">$key</span><span style="color: #000000;">;            }        }        </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$result</span><span style="color: #000000;">;    }    </span><span style="color: #800080;">$A</span>="common";<span style="color: #008000;">//</span><span style="color: #008000;">"hello";</span>    <span style="color: #800080;">$B</span>="month";<span style="color: #008000;">//</span><span style="color: #008000;">"jeesite";</span>    <span style="color: #800080;">$result</span>=getStringIntersect(<span style="color: #800080;">$A</span>, <span style="color: #800080;">$B</span><span style="color: #000000;">);    </span><span style="color: #0000ff;">echo</span> <span style="color: #800080;">$result</span><span style="color: #000000;">;</span>?><br>今天随便浏览网页的时候又发现了这篇文章（一次谷歌面试趣事）<br>我想起来了 思路二出自这篇文章。