H5W3
当前位置:H5W3 > java > 正文

【Java】思维私塾——一行代码解决算法

<div class=”output_wrapper” id=”output_wrapper_id”><p>有些算法题目,只要掌握了思路就可以用很短的代码来实现它。比如下面这几道题目:</p>
<h3 id=”h”><span>二的幂</span><span> </span></h3>
<h4 id=”h-1″><span>问题</span></h4>
<p>判断一个数字是否是2的n次方</p>
<h4 id=”h-2″><span>解答</span></h4>
<p>遇到2的幂次方,要建立位移操作的思想,如果n是二的幂,即最高位为1其他位置为0,那么n-1就是最高位为0,其余位置为1,那么n&(n-1)就是0</p>
<pre><span class="linenum hljs-number">1</span><span class="hljs-function"><span class="hljs-keyword">boolean</span> <span class="hljs-title">isPowerOfTow</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span>{
<span class="linenum hljs-number">2</span>    <span class="hljs-keyword">return</span> (n><span class="hljs-number">0</span>)%%(n&(n-<span class="hljs-number">1</span>))==<span class="hljs-number">0</span>;
<span class="linenum hljs-number">3</span>}
</pre>
<h3 id=”h-3″><span>三的幂</span><span> </span></h3>
<h4 id=”h-4″><span>问题</span></h4>
<p>判断一个数字是否为3的n次方</p>
<h4 id=”h-5″><span>解答</span></h4>
<p>int类型中不溢出情况下3的最高次方即为1162261467,那么只要这个数去约n为0,那么说明n的约数只有三,即为3的n次方.</p>
<p>同样的做法也可以适用于5的幂,7的幂,X的幂(X是一个素数)之类的题目。</p>
<pre><span class="linenum hljs-number">1</span><span class="hljs-function"><span class="hljs-keyword">boolean</span> <span class="hljs-title">isPowerOfThree</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span>{
<span class="linenum hljs-number">2</span>    <span class="hljs-keyword">return</span> (n><span class="hljs-number">0</span>)&&(<span class="hljs-number">116261467</span>%n)==<span class="hljs-number">0</span>;
<span class="linenum hljs-number">3</span>}
</pre>
<h3 id=”h1″><span>二进制1的个数</span><span> </span></h3>
<h4 id=”h-6″><span>问题</span></h4>
<p>给定一个数字n,求n转换为二进制表示中1的个数</p>
<h4 id=”h-7″><span>解答</span></h4>
<p>JDK大法好,直接使用自带的方法:</p>
<ul>
<li><span>bitCount:返回二进制中1的个数</span></li>
<li><span>lowestOneBit:返回二进制表示中最低位1的位置</span></li>
<li><span>highestOneBit:返回二进制表示中最高位1的位置</span></li>
<li><span>numberOfLeadingZeros:返回二进制表示中高位0的数目</span></li>
<li><span>numberOfTrailingZeros:返回二进制表示中低位0的数目</span></li>
</ul>
<pre><span class="linenum hljs-number">1</span> <span class="hljs-built_in">int</span> bitCount(<span class="hljs-built_in">int</span> <span class="hljs-built_in">num</span>) {
<span class="linenum hljs-number">2</span>        <span class="hljs-keyword">return</span> Integer.bitCount(<span class="hljs-built_in">num</span>);
<span class="linenum hljs-number">3</span>    }
</pre>
<p>或者也可以不使用jdk类库的解法</p>
<pre><span class="linenum hljs-number">1</span><span class="hljs-built_in">int</span> bitOfOne(<span class="hljs-built_in">int</span> <span class="hljs-built_in">num</span>) {
<span class="linenum hljs-number">2</span>        <span class="hljs-keyword">return</span> <span class="hljs-built_in">num</span> == <span class="hljs-number">0</span> ? <span class="hljs-number">0</span> : <span class="hljs-number">1</span> + bitOfOne(<span class="hljs-built_in">num</span> & (<span class="hljs-built_in">num</span> - <span class="hljs-number">1</span>));
<span class="linenum hljs-number">3</span>    }
</pre>
<h3 id=”h-8″><span>阶乘后的零</span><span> </span></h3>
<h4 id=”h-9″><span>问题</span></h4>
<p>给定一个数字n,求n!位数中的0的个数。</p>
<h4 id=”h-10″><span>解答</span></h4>
<p>这种问题我们要分析0的产生原因,因为10=52,对于一个n!的数字而言,末尾为0的数字即n!的约数中包含的52的次数,因为2的次数是足够的,也就是说这道题等价于求n!中约数5的个数(注意诸如25这种数字,约数中包括了2个5)。</p>
<pre><span class="linenum hljs-number">1</span><span class="hljs-built_in">int</span> zeroAtTheEndCount(<span class="hljs-built_in">int</span> <span class="hljs-built_in">num</span>) {
<span class="linenum hljs-number">2</span>        <span class="hljs-keyword">return</span> <span class="hljs-built_in">num</span> / <span class="hljs-number">5</span> + zeroAtTheEndCount(<span class="hljs-built_in">num</span> / <span class="hljs-number">5</span>);
<span class="linenum hljs-number">3</span>    }
</pre>
<h3 id=”h-11″><span>熄灭的灯</span><span> </span></h3>
<h4 id=”h-12″><span>问题</span></h4>
<p>有x个灯,一个开关控制一个灯,按下开关会使灯熄灭或者打开,现在灯都是熄灭的状态,我们进行n次操作,每次操作都把编号为i的倍数的开关全部按下,即</p>
<ul>
<li><span>将编号为1的倍数的开关全部按下</span></li>
<li><span>将编号为2的倍数的开关全部按下</span></li>
<li><span>…</span></li>
<li><span>将编号为x的倍数的开关全部按下</span></li>
</ul>
<p>已知灯的总数为x,求最后灯亮起来状态的数量</p>
<h4 id=”h-13″><span>解答</span></h4>
<p>首先任意取灯的编号n,会有几次操作会影响这个灯的状态呢?答案是n的所有约数的个数次。</p>
<p>好比说编号为12的灯,12的约数有1,2,3,4,6,12。也就是说编号为12的灯的状态会被切换6次,分别在第1,2,3,4,6,12次切换开关的时候。</p>
<p>那么从下面2种情况考虑:</p>
<ul>
<li><span>假设n是一个非完全平方的数:因为为一个非平方的数的约数个数为偶数个,也就是说会切换偶数次状态,也就是说状态不会变。</span></li>
<li><span>假设n是一个完全平方数:完全平方数的约数是奇数个,其状态会发生改变。</span></li>
</ul>
<p>那么按照题目的要求,一开始全是熄灭状态的,求亮起来状态的灯数目,就是说求会发生变化的编号的数目,也就是相当于求1~x之间完全平方数的个数。</p>
<pre><span class="linenum hljs-number">1</span><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">lightCount</span><span class="hljs-params">(<span class="hljs-keyword">int</span> num)</span> </span>{
<span class="linenum hljs-number">2</span>        <span class="hljs-keyword">return</span> (<span class="hljs-keyword">int</span>) Math.<span class="hljs-built_in">sqrt</span>(num);
<span class="linenum hljs-number">3</span>    }
</pre>
<h3 id=”h-14″><span>奇怪的数</span><span> </span></h3>
<h4 id=”h-15″><span>问题</span></h4>
<p>给定一个非空数组,其中除了一个元素只出现一次外,其他元素都出现了两次,求这个只出现一次的元素</p>
<h4 id=”h-16″><span>解答</span></h4>
<p>这里的一个关键运算符是^ 异或运算符,主要是利用到了异或运算a^b满足的如下规律:</p>
<ul>
<li><span>a^b=b^a 交换律</span></li>
<li><span>a^b^c=a^(b^c)结合律</span></li>
<li><span>a^a=0,同时0^0=0</span></li>
<li><span>0^a=a</span></li>
</ul>
<pre><span class="linenum hljs-number">1</span><span class="hljs-built_in">int</span> loseNumber(<span class="hljs-built_in">int</span>[] <span class="hljs-built_in">num</span>) {
<span class="linenum hljs-number">2</span>        <span class="hljs-keyword">return</span> Arrays.stream(<span class="hljs-built_in">num</span>).reduce(<span class="hljs-number">0</span>, (n1, n2) -> n1 ^ n2);
<span class="linenum hljs-number">3</span>    }
</pre>
<h3 id=”h-17″><span>约瑟夫环问题</span><span> </span></h3>
<h4 id=”h-18″><span>问题</span></h4>
<p>编号为1-n的n个战士围成一圈,从编号1的战士开始依次报数,数到m的战士会淘汰,以后的战士再重新报数,直到剩下一个士兵,求这个士兵的编号</p>
<h4 id=”h-19″><span>解答</span></h4>

删除前(old) 删除后(new)
m-2 n-2
m-1 n-1
m
m+1 1
m+2 2

<ul>
<li><p>假设old为删除前的节点编号,new为删除后的节点编号</p></li>
<li><p>- 关系:old=(new+m-1)%n+1</p></li>
</ul>
<blockquote>
<p>注意:并不是old=(new+m)%n,因为编号是从1开始的而不是从0 开始的,如果new+m==n的话,会导致最后的计算结果old=0.</p>
</blockquote>
<pre><span class="linenum hljs-number">1</span><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">f</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n,<span class="hljs-keyword">int</span> m)</span></span>{
<span class="linenum hljs-number">2</span>    <span class="hljs-keyword">if</span>(n==<span class="hljs-number">1</span>) 
<span class="linenum hljs-number">3</span>        <span class="hljs-keyword">return</span> n;
<span class="linenum hljs-number">4</span>    <span class="hljs-keyword">return</span> (f(n<span class="hljs-number">-1</span>,m)+m<span class="hljs-number">-1</span>)%n+<span class="hljs-number">1</span>;
<span class="linenum hljs-number">5</span>}
</pre>
<h3 id=”h-20″><span>最后</span><span> </span></h3>
<ul>
<li><span>如果觉得看完有收获,希望能关注一下,顺便给我点个赞,这将会是我更新的最大动力,感谢各位的支持</span></li>
<li><span>欢迎各位关注我的公众号【java冢狐】,专注于java和计算机基础知识,保证让你看完有所收获,不信你打我</span></li>
<li><span>求一键三连:点赞、转发、在看。</span></li>
<li><span>如果看完有不同的意见或者建议,欢迎多多评论一起交流。感谢各位的支持以及厚爱。</span></li>
</ul>
<p>——我是冢狐,和你一样热爱编程。</p>
<figure><img alt=”image” title=”image”><figcaption>image</figcaption></figure></div>

本文地址:H5W3 » 【Java】思维私塾——一行代码解决算法

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址