编程导航LeetCode话题讨论

LeetCode

67 参与
分享

快来分享你的内容吧~

点击登录,快来和大家讨论吧~
表情
图片
话题
打卡
综合
交流
文章
问答

刷题经验分享

<html> <head></head> <body> <div class="content ql-editor"> <p>先贴下我的刷题进度,这个图是我之前准备换工作时候刷题的进度,大概是两个半月AC了468道题,而且全是工作外的时间做到的。在面试做题的步骤中,基本上普通的中等难度题十分钟以内就能AC掉。</p> <p><br></p> <p><img src="https://pic.code-nav.cn/planet_post_image/1796153137144709122/933hg0kx.jpeg"></p> <p><br></p> <p>下面这个图是年后想着再找找感觉,但因为工作已经确定下来了,就简单刷了几天,没再继续。</p> <p><img src="https://pic.code-nav.cn/planet_post_image/1796153137144709122/bmonm2d6.jpeg"></p> <p><br></p> <p>目前市面上有很多刷题网站,leetcode应该是最成熟的,这里建议大家在leetcode上刷题,也建议大家办个会员,能让你的刷题效率更高,而且上面还有会员的专属学习计划,一年也就几百块钱,学生好像是有半价优惠,如果单纯是为面试而刷题的同学,可以考虑办个每月自动续费的会员(我就办的这个,刷了四个月后取消的会员)。</p> <p><br></p> <p><br></p> <p><strong>怎么刷题?</strong></p> <p>打开leetcode网站,在网站右侧你会看到精选题单</p> <p><img src="https://pic.code-nav.cn/planet_post_image/1796153137144709122/4h8o6old.jpeg"></p> <p><br></p> <p>建议大家主要刷我圈出来的这几个题单里的题,特别是《剑指offer》和《腾讯精选练习50题》,这里面都是绝对的高频题,一定要掌握的。</p> <p><br></p> <p>可以先刷一遍《腾讯精选练习50题》,里面各种类型题都有,先锻炼你的刷题感觉,确保自己见过常见的类型题,一道题如果20分钟还没思路就可以直接看答案了,我估计20分钟都没思路的题,再花1小时也大概率也是做不出来,不要浪费这个时间,直接看答案就好,但看完答案后不要抄袭,一定要确保理解了这道题的解法,自己重新敲一遍,确保可以通过所有测试case。</p> <p><br></p> <p><strong>这里有一点要注意,不要单纯的追求AC一道题,即便你自己AC了这道题,也要去看题解,看看这道题有没有其它解法,要确保自己理解了这道题的多种常规解法,特别是最优解,然后手敲AC通过才算结束。因为很多面试官的要求不同,你用解法A做出来一道题,但这可能不是他想要看到的,他想要的答案可能是最优解B和你的多种解题思路。</strong></p> <p><br></p> <p>刷完《腾讯精选练习50题》后,可以去刷《剑指offer》,但到了这个阶段,建议不要按顺序刷,而是要按类型去刷,刷完一个类型后,确保自己完全掌握了这种类型题的套路。</p> <p><br></p> <p>比如你刷到了这道题<u style="color: rgb(86, 120, 149);"><a href="https://leetcode.cn/problems/target-sum" target="_blank">https://leetcode.cn/problems/target-sum/</a></u></p> <p><br></p> <p><img src="https://pic.code-nav.cn/planet_post_image/1796153137144709122/yu1dnmtp.jpeg"></p> <p>这里涉及到背包和动态规划的套路,你可以去看看对应的题解,找到点赞最高的几个答案,比如这个题解</p> <p><u style="color: rgb(86, 120, 149);"><a href="https://leetcode.cn/problems/target-sum/solution/gong-shui-san-xie-yi-ti-si-jie-dfs-ji-yi-et5b/%EF%BC%8C%E5%85%B3%E4%BA%8E%E8%BF%99%E9%81%93%E9%A2%98%E8%AE%B2%E8%A7%A3%E7%9A%84%E5%B0%B1%E5%BE%88%E8%AF%A6%E7%BB%86%EF%BC%8C%E6%9B%B4%E9%87%8D%E8%A6%81%E7%9A%84%E6%98%AF%E5%A5%B9%E4%BC%9A%E6%8A%8A%E7%9B%B8%E5%85%B3%E7%9A%84%E9%AB%98%E9%A2%91%E7%B1%BB%E5%9E%8B%E9%A2%98%E5%9C%A8%E9%A2%98%E8%A7%A3%E7%9A%84%E5%90%8E%E9%9D%A2%E7%BB%99%E4%BD%A0%E8%B4%B4%E5%87%BA%E6%9D%A5" target="_blank">https://leetcode.cn/problems/target-sum/solution/gong-shui-san-xie-yi-ti-si-jie-dfs-ji-yi-et5b/</a></u>,</p> <p><br></p> <p>关于这道题讲解的就很详细,更重要的是她会把相关的高频类型题在题解的后面给你贴出来</p> <p><img src="https://pic.code-nav.cn/planet_post_image/1796153137144709122/5woay182.jpeg"></p> <p>可以按照她总结的这个目录去把相关类型题都刷一遍,刷完相关类型题后,<span style="color: unset;">需要确保自己掌握了背包相关的绝大多数解题套路,特别是背包九讲</span><u style="color: rgb(86, 120, 149);"><a href="https://t.zsxq.com/02iQfu3B2%E3%80%82" target="_blank">https://t.zsxq.com/02iQfu3B2。</a></u></p> <p>其他的题型也是类似的刷题套路,比如<strong>排序、二分、回溯、动态规划、背包、二叉树、滑动窗口</strong>,都有套路,都有相关的优质题解。</p> <p><br></p> <p><span style="color: unset;">这里我贴一下自己当时刷题总结的部分笔记链接:</span></p> <p><span style="font-size: 14px;">【岛屿数量】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-" target="_blank">https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/</a></u></p> <p><span style="color: rgb(57, 57, 57); font-size: 14px;">【接雨水】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/trapping-rain-water/solution" target="_blank">https://leetcode-cn.com/problems/trapping-rain-water/solution/</a></u></p> <p><span style="color: rgb(57, 57, 57); font-size: 14px;">【回溯】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-" target="_blank">https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/</a></u></p> <p><span style="color: rgb(57, 57, 57); font-size: 14px;">【背包】</span><u style="color: rgb(86, 120, 149);"><a href="https://t.zsxq.com/02iQfu3B2" target="_blank">https://t.zsxq.com/02iQfu3B2</a></u></p> <p><span style="color: rgb(57, 57, 57); font-size: 14px;">【股票】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/circle/article/qiAgHn" target="_blank">https://leetcode-cn.com/circle/article/qiAgHn/</a></u></p> <p><span style="color: rgb(57, 57, 57); font-size: 14px;">【排序】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/sort-an-array/solution/pai-xu-shu-zu-by-leetcode-solution" target="_blank">https://leetcode-cn.com/problems/sort-an-array/solution/pai-xu-shu-zu-by-leetcode-solution/</a></u></p> <p><u style="color: rgb(86, 120, 149);"><a href="https://blog.csdn.net/han_xiaoyang/article/details/12163251" target="_blank">https://blog.csdn.net/han_xiaoyang/article/details/12163251</a></u></p> <p><span style="color: rgb(57, 57, 57); font-size: 14px;">【动画模拟】</span><u style="color: rgb(86, 120, 149);"><a href="https://www.cs.usfca.edu/~galles/visualization/Algorithms.html" target="_blank">https://www.cs.usfca.edu/~galles/visualization/Algorithms.html</a></u></p> <p><span style="font-size: 14px;">【扫描线】天际线问题</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/the-skyline-problem" target="_blank">https://leetcode-cn.com/problems/the-skyline-problem/</a></u></p> <p><span style="font-size: 14px;">【滑动窗口最大值】单调队列,</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6" target="_blank">https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/</a></u></p> <p><span style="font-size: 14px;">【约瑟夫环问题】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as" target="_blank">https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/</a></u></p> <p><span style="font-size: 14px;">【摩尔投票】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode.cn/problems/majority-element/solution/3chong-fang-fa-by-gfu-2" target="_blank">https://leetcode.cn/problems/majority-element/solution/3chong-fang-fa-by-gfu-2/</a></u></p> <p><span style="font-size: 14px;">【数独</span>】<u style="color: rgb(86, 120, 149);"><a href="https://leetcode.cn/problems/sudoku-solver/solution/37-by-ikaruga" target="_blank">https://leetcode.cn/problems/sudoku-solver/solution/37-by-ikaruga/</a></u></p> <p><span style="font-size: 14px;">【背包】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/target-sum/solution/gong-shui-san-xie-yi-ti-si-jie-dfs-ji-yi-et5b" target="_blank">https://leetcode-cn.com/problems/target-sum/solution/gong-shui-san-xie-yi-ti-si-jie-dfs-ji-yi-et5b/</a></u></p> <p><span style="color: rgb(57, 57, 57); font-size: 14px;">【并查集】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d" target="_blank">https://leetcode-cn.com/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/</a></u></p> <p><span style="font-size: 14px;">【位操作】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/power-of-two/solution/5chong-jie-fa-ni-ying-gai-bei-xia-de-wei-6x9m" target="_blank">https://leetcode-cn.com/problems/power-of-two/solution/5chong-jie-fa-ni-ying-gai-bei-xia-de-wei-6x9m/</a></u></p> <p><span style="font-size: 14px;">【二分】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/solution/gong-shui-san-xie-er-fen-san-fen-cha-zhi-5gfv" target="_blank">https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/solution/gong-shui-san-xie-er-fen-san-fen-cha-zhi-5gfv/</a></u></p> <p><span style="font-size: 14px;">【二分模板(重点)】</span><u style="color: rgb(86, 120, 149);"><a href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/tu-jie-er-fen-zui-qing-xi-yi-dong-de-jia-ddvc" target="_blank">https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/tu-jie-er-fen-zui-qing-xi-yi-dong-de-jia-ddvc/</a></u></p> <p><br></p> <p>这里是我根据自己的个人情况整理的刷题笔记,建议大家自己在刷题过程中整理出一套自己的笔记,有时间就看看,多练练相关的题。</p> <p><br></p> <p>刷题的常见问题:</p> <ol> <li data-list="bullet"><span class="ql-ui"></span>刷题经常要看答案怎么办?</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>看答案很正常,但看完后你要掌握这道题背后的套路,确保自己下次遇到同类型的题时有解题思路。我刷第一遍时基本上每道题都会看答案,无论自己是不是AC。</li> <li data-list="bullet"><span class="ql-ui"></span>刷过的题经常忘怎么办?</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span>那肯定是你没掌握它背后的套路,多刷多练多总结吧。当然,也有很多题是没有套路的,完全智力题,这时可以看看这道题的出题频率,不建议在这种低频高难度题上浪费太多精力,面试时很少考,即便考了你当做面试官SB就好了,又不是面试Google。</li> <li data-list="bullet"><span class="ql-ui"></span>注意一点</li> <li data-list="bullet" class="ql-indent-1"><span class="ql-ui"></span><span style="color: unset;">不要看到这道题已经AC过,就不再做了,不要怕麻烦,即便你之前AC过,你现在也有思路,也建议再手敲刷一遍。面试时人一般都紧张,可能只能发挥出自己平时50%的水平,要孰能生巧,这样在面试时你才能应对的更自如。所以上面你别看我完成了468道题,但其实我可能AC了上千次,有些题刷了好多遍。你也可以每刷一轮题新建一个进度管理的tab。</span></li> </ol> <p><br></p> <p>以上是我刷题的一些经验分享,希望对大家有帮助。</p> <p>这里也分享下leetcode大佬的刷题方法论:<u style="color: rgb(86, 120, 149);"><a href="https://leetcode.cn/circle/discuss/jq9Zke" target="_blank">https://leetcode.cn/circle/discuss/jq9Zke/</a></u></p> <p><br></p> <p><br></p> </div> </body> </html>

Day30_顺序_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">打印从1到最大的n位数</strong></p> <p><br></p> <p><strong>Easy</strong> 原题连接:<a href="https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/" target="_blank" style="color: rgb(65, 131, 196);">打印从1到最大的n位数</a></p> <p>输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: n = <span class="ql-token hljs-number">1</span> </div> <div class="ql-code-block"> 输出: [<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">8</span>,<span class="ql-token hljs-number">9</span>] </div> </div> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>扩容结果数组:n是几就扩到几位数</li> <li data-list="ordered"><span class="ql-ui"></span>遍历补数据</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span>[] printNumbers(<span class="ql-token hljs-type">int</span> n) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">nSize</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(n&gt;<span class="ql-token hljs-number">0</span>){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;nSize *= <span class="ql-token hljs-number">10</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;n--; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] fin = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[nSize-<span class="ql-token hljs-number">1</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">0</span>; i&lt;nSize-<span class="ql-token hljs-number">1</span>; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fin[i] = i+<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> fin; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">数组中的逆序对</strong></h2> <p><br></p> <p><strong>Hard</strong> 原题连接:<a href="https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/" target="_blank" style="color: rgb(65, 131, 196);">数组中的逆序对</a></p> <p>在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: [<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">4</span>] </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">5</span> </div> </div> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">count</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">reversePairs(int[] nums)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">//利用归并排序解答,在合并的时候,当左边的大于右边,就计算逆序数。</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">//计算公式; mid-left+1</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">//定义一个全局的计数器变量</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-built_in">this</span>.count = <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;mergeSort(nums, <span class="ql-token hljs-number">0</span>, nums.length-<span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> count; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">mergeSort(int[] nums,int left,int right)</span>{ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//当只有一个节点的时候,直接返回,退出递归</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(left &gt;= right){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">mid</span> <span class="ql-token hljs-operator">=</span> (left+right)/<span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//左拆分</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;mergeSort(nums,left,mid); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//右拆分</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;mergeSort(nums,mid+<span class="ql-token hljs-number">1</span>,right); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//合并</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;merge(nums,left,mid,right); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">merge(int[] nums,int left,int mid,int right)</span>{ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//定义一个临时数组</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] temp = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[right-left+<span class="ql-token hljs-number">1</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//定义一个指针,指向第一个数组的第一个元素</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> left; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//定义一个指针,指向第二个数组的第一个元素</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">j</span> <span class="ql-token hljs-operator">=</span> mid+<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//定义一个指针,指向临时数组的第一个元素</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">t</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//当两个数组都有元素的时候,遍历比较每个元素大小</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(i &lt;= mid &amp;&amp; j &lt;= right){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//比较两个数组的元素,取较小的元素加入到,临时数组中</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//并将两个指针指向下一个元素</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(nums[i] &lt;= nums[j]){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;temp[t++] = nums[i++]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<span class="ql-token hljs-keyword">else</span>{ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//当左边数组的大与右边数组的元素时,就对当前元素以及后面的元素的个数进行统计,</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//此时这个数就是,逆序数</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//定义一个计数器,记下每次合并中存在的逆序数。</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;count += mid-i+<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;temp[t++] = nums[j++]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//当左边的数组没有遍历完成后,直接将剩余元素加入到临时数组中</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(i &lt;= mid){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;temp[t++] = nums[i++]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//当右边的数组没有遍历完成后,直接将剩余元素加入到临时数组中</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(j &lt;= right){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;temp[t++] =nums[j++]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//将新数组中的元素,覆盖nums旧数组中的元素。</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//此时数组的元素已经是有序的</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">k</span> <span class="ql-token hljs-operator">=0</span>; k&lt; temp.length;k++){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;nums[left+k] = temp[k]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p>身体有点抱恙,hard是借助已有评论的文字伪代码写的,要好好休息了...</p> <p><br></p> <p>我的博客:<a href="https://xcscx.github.io/" target="_blank">IT蛋的个人博客 - 一个平凡人的编程旅途 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/" target="_blank">)</a></p> </div> </body> </html>

Day29_正则表达与顺序_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">正则表达式匹配</strong></p> <p><br></p> <p><strong>Hard</strong> 原题连接:<a href="https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/" target="_blank" style="color: rgb(65, 131, 196);">正则表达式匹配</a></p> <p>请实现一个函数用来匹配包含'. '和'<em>'的正则表达式。模式中的字符'.'表示任意一个字符,而'</em>'表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab<em>ac</em>a"匹配,但与"aa.a"和"ab*a"均不匹配。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: </div> <div class="ql-code-block"> s = <span class="ql-token hljs-string">"aa"</span> </div> <div class="ql-code-block"> p = <span class="ql-token hljs-string">"a"</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-literal">false</span> </div> <div class="ql-code-block"> 解释: <span class="ql-token hljs-string">"a"</span> 无法匹配 <span class="ql-token hljs-string">"aa"</span> 整个字符串。 </div> <div class="ql-code-block"> 输入: </div> <div class="ql-code-block"> s = <span class="ql-token hljs-string">"aa"</span> </div> <div class="ql-code-block"> p = <span class="ql-token hljs-string">"a*"</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-literal">true</span> </div> <div class="ql-code-block"> 解释:&nbsp;因为 <span class="ql-token hljs-string">'*'</span> 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 <span class="ql-token hljs-string">'a'</span>。因此,字符串 <span class="ql-token hljs-string">"aa"</span> 可被视为 <span class="ql-token hljs-string">'a'</span> 重复了一次。 </div> <div class="ql-code-block"> 输入: </div> <div class="ql-code-block"> s = <span class="ql-token hljs-string">"ab"</span> </div> <div class="ql-code-block"> p = <span class="ql-token hljs-string">".*"</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-literal">true</span> </div> <div class="ql-code-block"> 解释: <span class="ql-token hljs-string">".*"</span> 表示可匹配零个或多个(<span class="ql-token hljs-string">'*'</span>)任意字符(<span class="ql-token hljs-string">'.'</span>)。 </div> </div> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>对于正则表达字符,只有三种可能:正常字符,任意字符 ".",长度字符 “*”</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>如果是正常字符,和字符对应位置比较,不同返回false,相同就s和p各往后推一位</li> <li data-list="ordered"><span class="ql-ui"></span>如果是 “.”,就直接向后推</li> <li data-list="ordered"><span class="ql-ui"></span>如果是 “ * ”,需要考虑是否判断,如果前一位值相同或为 “.” ,代表字符可以匹配正则的 “ * ”,字符后移;</li> <li data-list="ordered"><span class="ql-ui"></span> 如果前一位不同,代表 “ * ”取0,正则字符串后移两位</li> </ol> <p>实现:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>先判空</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>字符为空,正则不为空,需要判断:s="" p="a*"</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>字符为空,正则为空,true</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>字符不空,正则为空,false</li> <li data-list="ordered"><span class="ql-ui"></span>判断当前首字符s和p的关系,如果p有后一位,记录(方便查看 “*” 的作用)</li> <li data-list="ordered"><span class="ql-ui"></span>如果p下一位为 “ * ”,符合两者后移就递归,否则就当 “ * ”为0次出现,消除两个p首字段递归</li> <li data-list="ordered"><span class="ql-ui"></span>如果不为 “ * ”,符合消除就两者后移递归,否则返回false</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-title">isMatch(String s, String p)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">m</span> <span class="ql-token hljs-operator">=</span> s.length(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">n</span> <span class="ql-token hljs-operator">=</span> p.length(); </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(m == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(n%<span class="ql-token hljs-number">2</span> != <span class="ql-token hljs-number">0</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(i&lt;n) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(p.charAt(i) != <span class="ql-token hljs-string">'*'</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; &nbsp; &nbsp; &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;i+=<span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">true</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(n == <span class="ql-token hljs-number">0</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">char</span> <span class="ql-token hljs-variable">a1</span> <span class="ql-token hljs-operator">=</span> p.charAt(<span class="ql-token hljs-number">0</span>), a2 = s.charAt(<span class="ql-token hljs-number">0</span>), a3 = <span class="ql-token hljs-string">'a'</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(n &gt; <span class="ql-token hljs-number">1</span>) a3 = p.charAt(<span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(a3 == <span class="ql-token hljs-string">'*'</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(a1 == a2 || a1 == <span class="ql-token hljs-string">'.'</span>) </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isMatch(s.substring(<span class="ql-token hljs-number">1</span>), p) </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|| isMatch(s, p.substring(<span class="ql-token hljs-number">2</span>)); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">else</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isMatch(s, p.substring(<span class="ql-token hljs-number">2</span>)); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; }<span class="ql-token hljs-keyword">else</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(a1 == a2 || a1 == <span class="ql-token hljs-string">'.'</span>) </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isMatch(s.substring(<span class="ql-token hljs-number">1</span>), p.substring(<span class="ql-token hljs-number">1</span>)); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">else</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">丑数</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/chou-shu-lcof/" target="_blank" style="color: rgb(65, 131, 196);">丑数</a></p> <p>我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: n = <span class="ql-token hljs-number">10</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">12</span> </div> <div class="ql-code-block"> 解释: <span class="ql-token hljs-number">1</span>, <span class="ql-token hljs-number">2</span>, <span class="ql-token hljs-number">3</span>, <span class="ql-token hljs-number">4</span>, <span class="ql-token hljs-number">5</span>, <span class="ql-token hljs-number">6</span>, <span class="ql-token hljs-number">8</span>, <span class="ql-token hljs-number">9</span>, <span class="ql-token hljs-number">10</span>, <span class="ql-token hljs-number">12</span> 是前 <span class="ql-token hljs-number">10</span> 个丑数。 </div> </div> <p><strong>说明:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>1 是丑数。</li> <li data-list="ordered"><span class="ql-ui"></span>n <strong>不超过</strong>1690。</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>丑数 = min(一个较小的丑数 * 2 或 * 3 或 *5),比如 4 = 2 * 2,5 = 1* 5,9 = 3 * 3 即拆到最细因子只包含 2,3,5</p> <p>所以<strong>利用已知的丑数推导下一个丑数</strong>,比如已知 1,2,3,4,5 下一位丑数 6 = 2*3,可为什么选2 和 3 是问题所在</p> <p>下一个丑数只可能通过以下三种形式出现</p> <p>已知丑数a * 2 已知丑数b * 3 已知丑数c * 5</p> <p>那么就从头开始记录a, b, c</p> <p>当满足某一次丑数为a * 2,b * 3,c * 5,更新对应的a b c</p> <p>实现:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>初始丑数为1,a,b,c均为0</li> <li data-list="ordered"><span class="ql-ui"></span>向后递推丑数,每次的丑数等于 (第a个丑数 * 2,第b个丑数 * 3,第c个丑数 * 5)三者中的最小值</li> <li data-list="ordered"><span class="ql-ui"></span>2种是谁的最小值,谁就+1,更新abc,直到推导到第n位</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">nthUglyNumber(int n)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">a</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>, b = <span class="ql-token hljs-number">0</span>, c = <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] dp = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[n]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;dp[<span class="ql-token hljs-number">0</span>] = <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">1</span>; i&lt; n; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;dp[i] = Math.min(Math.min(dp[a] * <span class="ql-token hljs-number">2</span>, dp[b] * <span class="ql-token hljs-number">3</span>), dp[c] * <span class="ql-token hljs-number">5</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(dp[i] == dp[a] * <span class="ql-token hljs-number">2</span>) a++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(dp[i] == dp[b] * <span class="ql-token hljs-number">3</span>) b++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(dp[i] == dp[c] * <span class="ql-token hljs-number">5</span>) c++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> dp[n-<span class="ql-token hljs-number">1</span>]; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">n个骰子的点数</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/" target="_blank" style="color: rgb(65, 131, 196);">n个骰子的点数</a></p> <p>把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。</p> <p>你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: <span class="ql-token hljs-number">1</span> </div> <div class="ql-code-block"> 输出: [<span class="ql-token hljs-number">0.16667</span>,<span class="ql-token hljs-number">0.16667</span>,<span class="ql-token hljs-number">0.16667</span>,<span class="ql-token hljs-number">0.16667</span>,<span class="ql-token hljs-number">0.16667</span>,<span class="ql-token hljs-number">0.16667</span>] </div> <div class="ql-code-block"> 输入: <span class="ql-token hljs-number">2</span> </div> <div class="ql-code-block"> 输出: [<span class="ql-token hljs-number">0.02778</span>,<span class="ql-token hljs-number">0.05556</span>,<span class="ql-token hljs-number">0.08333</span>,<span class="ql-token hljs-number">0.11111</span>,<span class="ql-token hljs-number">0.13889</span>,<span class="ql-token hljs-number">0.16667</span>,<span class="ql-token hljs-number">0.13889</span>,<span class="ql-token hljs-number">0.11111</span>,<span class="ql-token hljs-number">0.08333</span>,<span class="ql-token hljs-number">0.05556</span>,<span class="ql-token hljs-number">0.02778</span>] </div> </div> <p><strong>说明:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= n &lt;= 11</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>一个骰子六个面,每个面出现概率1/6,两个骰子,共有36种组合,但是只有11种不同结果(2-12)。</p> <p>以上我们可以得到的信息:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>每多加一个骰子,不同的结果数量就增加5个(最大值+6,最小值+1,差为5)</li> <li data-list="ordered"><span class="ql-ui"></span>多加一个骰子后,<strong>原结果第i个应该影响现结果第i+1到i+6 ,先结果第 i 个应该是原结果 i - 6 到 i - 1的累计作用</strong></li> <li data-list="ordered"><span class="ql-ui"></span>所谓累计作用:原本 i 的概率为 a,新加一个骰子后,i 对于 i+1 影响大了 a/6 ,对 i+2也是a/6,直到 i+6,相同的道理,i+1对 i+2到i+7也有相同影响</li> </ol> <p>简而言之,从只有一个骰子向后递推,每增加一个筛子,扩大结果数组范围,让原结果对先数组的六位累计概率</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">double</span>[] dicesProbability(<span class="ql-token hljs-type">int</span> n) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">double</span>[] ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">double</span>[<span class="ql-token hljs-number">6</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">0</span>; i&lt;<span class="ql-token hljs-number">6</span>; i++) ans[i] = <span class="ql-token hljs-number">1.0</span>/<span class="ql-token hljs-number">6</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">2</span>; i&lt;=n; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">double</span>[] mid = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">double</span>[<span class="ql-token hljs-number">5</span>*i + <span class="ql-token hljs-number">1</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> j=<span class="ql-token hljs-number">0</span>; j&lt;ans.length; j++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> k=<span class="ql-token hljs-number">0</span>;k&lt;<span class="ql-token hljs-number">6</span>; k++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid[j+k] += ans[j]/<span class="ql-token hljs-number">6.0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans = mid; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p>持续加油,还有学习空间</p> <p>我的博客:<a href="https://xcscx.github.io/2023/04/18/leetCode/%E5%89%91%E6%8C%87Offer/Day29_%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%8E%E6%95%B0%E5%AD%97%E8%A7%84%E5%BE%8B/" target="_blank">Day29_正则表达式与数字规律_剑指Offer | IT蛋的个人博客 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/2023/04/18/leetCode/%E5%89%91%E6%8C%87Offer/Day29_%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E4%B8%8E%E6%95%B0%E5%AD%97%E8%A7%84%E5%BE%8B/" target="_blank">)</a></p> </div> </body> </html>

Day28 _序列与顺序_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">序列化二叉树</strong></p> <p><strong>Hard</strong> 原题连接:<a href="https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/" target="_blank" style="color: rgb(65, 131, 196);">序列化二叉树</a></p> <p>请实现两个函数,分别用来序列化和反序列化二叉树。</p> <p>你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。</p> <p>提示:输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:root = [<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-literal">null</span>,<span class="ql-token hljs-literal">null</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>] </div> <div class="ql-code-block"> 输出:[<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-literal">null</span>,<span class="ql-token hljs-literal">null</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>] </div> </div> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>如何序列化二叉树(以什么顺序序列化)</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>先序遍历:<strong>根 (左)(右)</strong>的顺序,根(根左右)(根左右),可以确定当前第一个是根节点,遍历左子树,直到叶子节点,之后是右子树</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>中序遍历:<strong>(左) 根 (右)</strong>的顺序,很难判断出根节点的位置,</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>后序遍历:<strong>(左)(右) 根</strong> 的顺序,同上不便判断出根节点和左右节点之间的区分</li> <li data-list="ordered"><span class="ql-ui"></span>二叉树有几种状态需要区别</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>当前节点:直接把值当字符存储,空节点(叶子节点的子节点)使用特殊字符存储 "#"</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>子节点与根:使用字符连接,便于反序列化时区分各个值 “-”</li> </ol> <p>综上,序列化使用先序遍历,判断是否是null,存储当前值,遍历左子树,遍历右子树</p> <p>反序列化则是按顺序读取序列化的值,凭借自己拆分的字符,拆成一个个数字,按先序连接</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * Definition for a binary tree node.</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * public class TreeNode {</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * &nbsp; &nbsp; int val;</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * &nbsp; &nbsp; TreeNode left;</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * &nbsp; &nbsp; TreeNode right;</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * &nbsp; &nbsp; TreeNode(int x) { val = x; }</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * }</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Codec</span> { </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// Encodes a tree to a single string.</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> String <span class="ql-token hljs-title">serialize(TreeNode root)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(root == <span class="ql-token hljs-literal">null</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-string">"#"</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">StringBuilder</span> <span class="ql-token hljs-variable">sb</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">StringBuilder</span>(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sb.append(root.val); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sb.append(<span class="ql-token hljs-string">"_"</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sb.append(serialize(root.left)); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sb.append(<span class="ql-token hljs-string">"_"</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sb.append(serialize(root.right)); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">String</span> <span class="ql-token hljs-variable">str</span> <span class="ql-token hljs-operator">=</span> sb.toString(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> str; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// Decodes your encoded data to tree.</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> TreeNode <span class="ql-token hljs-title">deserialize(String data)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;String[] values = data.split(<span class="ql-token hljs-string">"_"</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;Queue&lt;String&gt; queue = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">LinkedList</span>&lt;&gt;(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; i &lt; values.length; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;queue.add(values[i]); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> reconOrder(queue); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">//组成树</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">static</span> TreeNode <span class="ql-token hljs-title">reconOrder(Queue&lt;String&gt; queue)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">String</span> <span class="ql-token hljs-variable">value</span> <span class="ql-token hljs-operator">=</span> queue.poll(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(value.equals(<span class="ql-token hljs-string">"#"</span>)){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">null</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">TreeNode</span> <span class="ql-token hljs-variable">head</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">TreeNode</span>(Integer.valueOf(value)); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;head.left = reconOrder(queue); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;head.right = reconOrder(queue); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> head; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// Your Codec object will be instantiated and called as such:</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// Codec codec = new Codec();</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment">// codec.deserialize(codec.serialize(root));</span> </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">字符串的排列</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/" target="_blank" style="color: rgb(65, 131, 196);">字符串的排列</a></p> <p>输入一个字符串,打印出该字符串中字符的所有排列。</p> <p>你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:s = <span class="ql-token hljs-string">"abc"</span> </div> <div class="ql-code-block"> 输出:[<span class="ql-token hljs-string">"abc"</span>,<span class="ql-token hljs-string">"acb"</span>,<span class="ql-token hljs-string">"bac"</span>,<span class="ql-token hljs-string">"bca"</span>,<span class="ql-token hljs-string">"cab"</span>,<span class="ql-token hljs-string">"cba"</span>] </div> </div> <p></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>字符的所有排列,理论上,<strong>一个长度为n的字符最大排列数应该是 !n 个</strong>,但是例子中发现存在重复字符,比如 abb</p> <p>思路变为每一个字符在每一个位置只能出现一次(每一个位置都设置一个hashset存储已经在这个位置站过的字符)</p> <p>第一个位置会遍历n次,第二位置会遍历n-1次....最后位会遍历1次,总计 !n 次</p> <p>但是,一旦出现已经在某个位置重复选过,剪枝</p> <p>直至拼接长度到达目标长度</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// 1.用什么存储</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-type">char</span>[] sortStr; </div> <div class="ql-code-block"> &nbsp; &nbsp;List&lt;String&gt; ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">LinkedList</span>&lt;&gt;(); </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> String[] permutation(String s) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 2.初始化:String 转 charArray</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sortStr = s.toCharArray(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;dfs(<span class="ql-token hljs-number">0</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans.toArray(<span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">String</span>[ans.size()]); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// 3.dfs遍历运算,终止条件是什么,dfs如何递归</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">dfs(int index)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 4.剪枝条件</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(index == sortStr.length-<span class="ql-token hljs-number">1</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans.add(String.valueOf(sortStr)); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;HashSet&lt;Character&gt; set = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">HashSet</span>&lt;&gt;(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=index; i&lt;sortStr.length; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(set.contains(sortStr[i]))<span class="ql-token hljs-keyword">continue</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;set.add(sortStr[i]); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;swap(i, index); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;dfs(index + <span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;swap(i, index); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span>; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// 5.交换函数</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">swap(int a, int b)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">char</span> <span class="ql-token hljs-variable">mid</span> <span class="ql-token hljs-operator">=</span> sortStr[a]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sortStr[a] = sortStr[b]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;sortStr[b] = mid; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p>我的博客:<a href="https://xcscx.github.io/2023/04/17/leetCode/%E5%89%91%E6%8C%87Offer/Day28_%E5%BA%8F%E5%88%97%E4%B8%8E%E9%A1%BA%E5%BA%8F/" target="_blank">Day28_序列与顺序_剑指Offer | IT蛋的个人博客 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/2023/04/17/leetCode/%E5%89%91%E6%8C%87Offer/Day28_%E5%BA%8F%E5%88%97%E4%B8%8E%E9%A1%BA%E5%BA%8F/" target="_blank">)</a></p> </div> </body> </html>

Day27_滑动窗口_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">滑动窗口的最大值</strong></p> <p><br></p> <p><strong>Hard</strong> 原题连接:<a href="https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/" target="_blank" style="color: rgb(65, 131, 196);">滑动窗口的最大值</a></p> <p>给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: nums = [<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">3</span>,-<span class="ql-token hljs-number">1</span>,-<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">7</span>], 和 k = <span class="ql-token hljs-number">3</span> </div> <div class="ql-code-block"> 输出: [<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">7</span>] </div> <div class="ql-code-block"> 解释: </div> <div class="ql-code-block"> &nbsp;滑动窗口的位置 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;最大值 </div> <div class="ql-code-block"> --------------- &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ----- </div> <div class="ql-code-block"> [<span class="ql-token hljs-number">1</span> &nbsp;<span class="ql-token hljs-number">3</span> &nbsp;-<span class="ql-token hljs-number">1</span>] -<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">5</span> &nbsp;<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">6</span> &nbsp;<span class="ql-token hljs-number">7</span> &nbsp; &nbsp; &nbsp; <span class="ql-token hljs-number">3</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-number">1</span> [<span class="ql-token hljs-number">3</span> &nbsp;-<span class="ql-token hljs-number">1</span> &nbsp;-<span class="ql-token hljs-number">3</span>] <span class="ql-token hljs-number">5</span> &nbsp;<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">6</span> &nbsp;<span class="ql-token hljs-number">7</span> &nbsp; &nbsp; &nbsp; <span class="ql-token hljs-number">3</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-number">1</span> &nbsp;<span class="ql-token hljs-number">3</span> [-<span class="ql-token hljs-number">1</span> &nbsp;-<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">5</span>] <span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">6</span> &nbsp;<span class="ql-token hljs-number">7</span> &nbsp; &nbsp; &nbsp; <span class="ql-token hljs-number">5</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-number">1</span> &nbsp;<span class="ql-token hljs-number">3</span> &nbsp;-<span class="ql-token hljs-number">1</span> [-<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">5</span> &nbsp;<span class="ql-token hljs-number">3</span>] <span class="ql-token hljs-number">6</span> &nbsp;<span class="ql-token hljs-number">7</span> &nbsp; &nbsp; &nbsp; <span class="ql-token hljs-number">5</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-number">1</span> &nbsp;<span class="ql-token hljs-number">3</span> &nbsp;-<span class="ql-token hljs-number">1</span> &nbsp;-<span class="ql-token hljs-number">3</span> [<span class="ql-token hljs-number">5</span> &nbsp;<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">6</span>] <span class="ql-token hljs-number">7</span> &nbsp; &nbsp; &nbsp; <span class="ql-token hljs-number">6</span> </div> <div class="ql-code-block"> <span class="ql-token hljs-number">1</span> &nbsp;<span class="ql-token hljs-number">3</span> &nbsp;-<span class="ql-token hljs-number">1</span> &nbsp;-<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">5</span> [<span class="ql-token hljs-number">3</span> &nbsp;<span class="ql-token hljs-number">6</span> &nbsp;<span class="ql-token hljs-number">7</span>] &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-number">7</span> </div> </div> <p><strong>提示:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>你可以假设 <em>k</em> 总是有效的,在输入数组 <strong>不为空</strong> 的情况下,1 ≤ k ≤ <a href="http://nums.length" target="_blank">nums.length</a>。</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>问题:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>需要时刻记录当前窗口中的最大值</li> <li data-list="ordered"><span class="ql-ui"></span>当窗口移动时需要考虑是否移除的是之前的最大值,以及插入的新值该排在什么位置</li> <li data-list="ordered"><span class="ql-ui"></span>暴力算法会超时</li> </ol> <p>实现:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>使用双端队列存储最大值信息(存储:不严格递减存储,不符合的不存)利于删除头节点(最大值),添加删除尾节点(后续的大值)</li> </ol> <p>例如: 【1,6,5,2,5,3】,4 ,队列会存储【6,5,5,3】</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>移动时删除左端:如果左端值和队列头相同,队列弹出,下一个值作为队列头返回最大值</li> <li data-list="ordered"><span class="ql-ui"></span>移动时添加右端:弹出双端队列中从<strong>队尾到队头</strong>所有小于添加节点的值,再添加节点,如上述例子下一步为:1,【6,5,2,5,3,4】,队列存储【6,5,5,4】弹出了3,添加了4</li> <li data-list="ordered"><span class="ql-ui"></span> 利用两个循环,一个用户创建基础滑动窗口,并获得对应初始队列;一个用于滑动运算</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span>[] maxSlidingWindow(<span class="ql-token hljs-type">int</span>[] nums, <span class="ql-token hljs-type">int</span> k) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(nums.length == <span class="ql-token hljs-number">0</span> || k == <span class="ql-token hljs-number">0</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[<span class="ql-token hljs-number">0</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[nums.length -k + <span class="ql-token hljs-number">1</span>]; </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;Deque&lt;Integer&gt; maxValue = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">LinkedList</span>&lt;&gt;(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">0</span>; i&lt;k; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(!maxValue.isEmpty() &amp;&amp; maxValue.peekLast() &lt; nums[i]) maxValue.removeLast(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;maxValue.addLast(nums[i]); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;ans[<span class="ql-token hljs-number">0</span>] = maxValue.peekFirst(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=k; i&lt;nums.length; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(maxValue.peekFirst() == nums[i-k]) maxValue.removeFirst(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(!maxValue.isEmpty() &amp;&amp; maxValue.peekLast() &lt; nums[i]) maxValue.removeLast(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;maxValue.addLast(nums[i]); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans[i-k+<span class="ql-token hljs-number">1</span>] = maxValue.peekFirst(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">队列的最大值</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/" target="_blank" style="color: rgb(65, 131, 196);">队列的最大值</a></p> <p>请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。</p> <p>若队列为空,pop_front 和 max_value 需要返回 -1</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: </div> <div class="ql-code-block"> [<span class="ql-token hljs-string">"MaxQueue"</span>,<span class="ql-token hljs-string">"push_back"</span>,<span class="ql-token hljs-string">"push_back"</span>,<span class="ql-token hljs-string">"max_value"</span>,<span class="ql-token hljs-string">"pop_front"</span>,<span class="ql-token hljs-string">"max_value"</span>] </div> <div class="ql-code-block"> [[],[<span class="ql-token hljs-number">1</span>],[<span class="ql-token hljs-number">2</span>],[],[],[]] </div> <div class="ql-code-block"> 输出:&nbsp;[<span class="ql-token hljs-literal">null</span>,<span class="ql-token hljs-literal">null</span>,<span class="ql-token hljs-literal">null</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>] </div> <div class="ql-code-block"> 输入: </div> <div class="ql-code-block"> [<span class="ql-token hljs-string">"MaxQueue"</span>,<span class="ql-token hljs-string">"pop_front"</span>,<span class="ql-token hljs-string">"max_value"</span>] </div> <div class="ql-code-block"> [[],[],[]] </div> <div class="ql-code-block"> 输出: [<span class="ql-token hljs-literal">null</span>,-<span class="ql-token hljs-number">1</span>,-<span class="ql-token hljs-number">1</span>]位有符号整数范围。 </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp;因此返回 INT_MIN (−<span class="ql-token hljs-number">231</span>) 。 </div> </div> <p></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>和第一题很类似,是一个不固定长度的滑动窗口</p> <p>数据信息和最大排序都是用双端队列存储,每次添加数据时做判断,弹出最大排序中所有小于插入值的值</p> <p>获取最大值和弹出时额外判断是否为空即可</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">MaxQueue</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;Deque&lt;Integer&gt; numMessage; </div> <div class="ql-code-block"> &nbsp; &nbsp;Deque&lt;Integer&gt; maxMessage; </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-title">MaxQueue()</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;numMessage = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">LinkedList</span>&lt;&gt;(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;maxMessage = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">LinkedList</span>&lt;&gt;(); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">max_value()</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(maxMessage.isEmpty()) <span class="ql-token hljs-keyword">return</span> -<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> maxMessage.peekFirst(); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-keyword">void</span> <span class="ql-token hljs-title">push_back(int value)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;numMessage.addLast(value); &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(!maxMessage.isEmpty() &amp;&amp; maxMessage.peekLast() &lt; value) maxMessage.removeLast(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;maxMessage.addLast(value); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">pop_front()</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(numMessage.isEmpty()) <span class="ql-token hljs-keyword">return</span> -<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(maxMessage.peekFirst().equals(numMessage.peekFirst())) maxMessage.removeFirst(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> numMessage.peekFirst(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;numMessage.removeFirst(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"><span class="ql-token hljs-comment">/**</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * Your MaxQueue object will be instantiated and called as such:</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * MaxQueue obj = new MaxQueue();</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * int param_1 = obj.max_value();</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * obj.push_back(value);</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> * int param_3 = obj.pop_front();</span> </div> <div class="ql-code-block"><span class="ql-token hljs-comment"> */</span> </div> </div> <p>我的博客:<a href="https://xcscx.github.io/" target="_blank">IT蛋的个人博客 - 一个平凡人的编程旅途 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/" target="_blank">)</a></p> </div> </body> </html>

Day26-字符与数字转换_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">表示数值的字符串</strong></p> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/" target="_blank" style="color: rgb(65, 131, 196);">表示数值的字符串</a></p> <p>请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。</p> <p>数值(按顺序)可以分成以下几个部分:</p> <p><strong>若干空格一个 小数 或者 整数(可选)一个 'e' 或 'E' ,后面跟着一个 整数若干空格小数(按顺序)</strong>可以分成以下几个部分:</p> <p><strong>(可选)一个符号字符('+' 或 '-')</strong>下述格式之一:至少一位数字,后面跟着一个点 '.'至少一位数字,后面跟着一个点 '.' ,后面再跟着至少一位数字一个点 '.' ,后面跟着至少一位数字<strong>整数(按顺序)</strong></p> <p>可以分成以下几个部分:</p> <p><strong>(可选)一个符号字符('+' 或 '-')至少一位数字</strong>部分数值列举:["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]</p> <p>部分非数值列举:["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:s = <span class="ql-token hljs-string">"0"</span> </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-literal">true</span> </div> <div class="ql-code-block"> 输入:s = <span class="ql-token hljs-string">"e"</span> </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-literal">false</span> </div> <div class="ql-code-block"> 输入:s = <span class="ql-token hljs-string">"."</span> </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-literal">false</span> </div> <div class="ql-code-block"> 输入:s = <span class="ql-token hljs-string">" &nbsp; .1 "</span> </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-literal">true</span> </div> </div> <p><strong>提示:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= s.length &lt;= 20</li> <li data-list="ordered"><span class="ql-ui"></span>s 仅含英文字母(大写和小写),数字(0-9),加号 '+' ,减号 '-' ,空格 ' ' 或者点 '.' 。</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>一个包含全部可能的最大目标大致可以分为:</p> <p><strong>空格 正负 数字 小数点 数字 e/E 正负 数字 空格</strong></p> <p>从前到后依次划分部分进行检验:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>删除前后空格</li> <li data-list="ordered"><span class="ql-ui"></span>判断首字节是否为+-</li> <li data-list="ordered"><span class="ql-ui"></span>依据E/e拆分为两个部分</li> <li data-list="ordered"><span class="ql-ui"></span>前者判断是否由小数点,拆为两个部分</li> <li data-list="ordered"><span class="ql-ui"></span>3中剩下的部分,4中的两个部分,检测是否为纯数字</li> </ol> <p>注:允许4的前半部分为空</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-title">isNumber(String s)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 空格 正负 数字 小数点 数字 e/E 正负 数字 空格</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 1.将s删去前后空格,判断charAt(0)是否是正负号</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;s = s.trim(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(s.length() == <span class="ql-token hljs-number">0</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(s.charAt(<span class="ql-token hljs-number">0</span>) == <span class="ql-token hljs-string">'+'</span> || s.charAt(<span class="ql-token hljs-number">0</span>) == <span class="ql-token hljs-string">'-'</span>) s = s.substring(<span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 2.将剩余string依据e/E划分为两个部分,如果第二部分长度不为零,判断charAt(0)是否为符号</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;s = s.replace(<span class="ql-token hljs-string">'E'</span>,<span class="ql-token hljs-string">'e'</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(s.indexOf(<span class="ql-token hljs-string">'e'</span>) &gt;= <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">index</span> <span class="ql-token hljs-operator">=</span> s.indexOf(<span class="ql-token hljs-string">'e'</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">String</span> <span class="ql-token hljs-variable">firstStr</span> <span class="ql-token hljs-operator">=</span> s.substring(<span class="ql-token hljs-number">0</span>,index); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">String</span> <span class="ql-token hljs-variable">secondStr</span> <span class="ql-token hljs-operator">=</span> s.substring(index+<span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(secondStr.length() &gt; <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(secondStr.charAt(<span class="ql-token hljs-number">0</span>) == <span class="ql-token hljs-string">'+'</span> || secondStr.charAt(<span class="ql-token hljs-number">0</span>) == <span class="ql-token hljs-string">'-'</span>) secondStr = secondStr.substring(<span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isNum(firstStr) &amp;&amp; isInteger(secondStr); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isNum(s); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// 3.由2得到的两个字符,前者做数字判断(可为小数),后者做整数判断</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// 判断是否为整数(不可以为小数)</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-title">isInteger(String str)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(str == <span class="ql-token hljs-string">""</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">char</span> a : str.toCharArray()) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(a &lt; <span class="ql-token hljs-string">'0'</span> || a &gt; <span class="ql-token hljs-string">'9'</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">true</span>; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-comment">// 判断是否为数(可以为小数)</span> </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-title">isNum(String str)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(str.indexOf(<span class="ql-token hljs-string">'.'</span>) &gt;= <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">index</span> <span class="ql-token hljs-operator">=</span> str.indexOf(<span class="ql-token hljs-string">'.'</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">String</span> <span class="ql-token hljs-variable">firstStr</span> <span class="ql-token hljs-operator">=</span> str.substring(<span class="ql-token hljs-number">0</span>,index); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">String</span> <span class="ql-token hljs-variable">secondStr</span> <span class="ql-token hljs-operator">=</span> str.substring(index+<span class="ql-token hljs-number">1</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(firstStr.length() &gt;<span class="ql-token hljs-number">0</span> &amp;&amp; secondStr.length() &gt;<span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isInteger(firstStr) &amp;&amp; isInteger(secondStr); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<span class="ql-token hljs-keyword">else</span> <span class="ql-token hljs-keyword">if</span>(secondStr.length() &gt;<span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isInteger(secondStr); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<span class="ql-token hljs-keyword">else</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isInteger(firstStr); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> isInteger(str); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">把字符串转换成整数</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/" target="_blank" style="color: rgb(65, 131, 196);"> 把字符串转换成整数</a></p> <p>写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。</p> <p></p> <p>首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。</p> <p>当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。</p> <p>该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。</p> <p>注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。</p> <p>在任何情况下,若函数不能进行有效的转换时,请返回 0。</p> <p>说明:</p> <p>假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围,请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31)</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: <span class="ql-token hljs-string">"42"</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">42</span> </div> <div class="ql-code-block"> 输入: <span class="ql-token hljs-string">" &nbsp; -42"</span> </div> <div class="ql-code-block"> 输出: -<span class="ql-token hljs-number">42</span> </div> <div class="ql-code-block"> 解释: 第一个非空白字符为 <span class="ql-token hljs-string">'-'</span>, 它是一个负号。 </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp;我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -<span class="ql-token hljs-number">42</span> 。 </div> <div class="ql-code-block"> 输入: <span class="ql-token hljs-string">"4193 with words"</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">4193</span> </div> <div class="ql-code-block"> 输入: <span class="ql-token hljs-string">"words and 987"</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">0</span> </div> <div class="ql-code-block"> 解释: 第一个非空字符是 <span class="ql-token hljs-string">'w'</span>, 但它不是数字或正、负号。 </div> <div class="ql-code-block"> &nbsp; &nbsp; 因此无法执行有效的转换。 </div> <div class="ql-code-block"> 输入: <span class="ql-token hljs-string">"-91283472332"</span> </div> <div class="ql-code-block"> 输出: -<span class="ql-token hljs-number">2147483648</span> </div> <div class="ql-code-block"> 解释: 数字 <span class="ql-token hljs-string">"-91283472332"</span> 超过 <span class="ql-token hljs-number">32</span> 位有符号整数范围。 </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp;因此返回 INT_MIN (−<span class="ql-token hljs-number">231</span>) 。 </div> </div> <p></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>和第一题有些类似,删除空格,判断符号,遇到字母就跳出</p> <p>需要注意的是,如果第一个字符是符号,数字需要从下标为1的地方开始读,如果没有符号,则从0开始读</p> <p>为了避免超过int类型的最大值,可以在循环中判断,是否即将超过最大值(因为每次记录结果是将ans= ans*10+new)</p> <p>所以<strong>先判断是否依据超过了int最大值的十分之一</strong>(否则接下来进行*10运算会超过最大值)</p> <p>又或者恰好为2147483648 2147483649,刚好超过一两位,所以在ans已经相等于int最大值的十分之一时判断最后一位的值是否大于7</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">strToInt(String str)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 1.删去str前后端的空格,并判断charAt(0)是否为符号,做记录(符号sign与数字开始位i)</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;str = str.trim(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(str.length() == <span class="ql-token hljs-number">0</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">sign</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">1</span>, index = <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(str.charAt(<span class="ql-token hljs-number">0</span>) == <span class="ql-token hljs-string">'-'</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sign = -<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; }<span class="ql-token hljs-keyword">else</span> <span class="ql-token hljs-keyword">if</span>(str.charAt(<span class="ql-token hljs-number">0</span>) != <span class="ql-token hljs-string">'+'</span>){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;index = <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>, max = Integer.MAX_VALUE/<span class="ql-token hljs-number">10</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 2.循环对数每一位做判断:</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(; index &lt; str.length(); index++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 3.弹出条件之一:遇到不是数字的数,break</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(str.charAt(index)&lt;<span class="ql-token hljs-string">'0'</span> || str.charAt(index)&gt;<span class="ql-token hljs-string">'9'</span>) <span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 4.弹出条件之二:已经超过最大值(符号已经记录,单纯看数值大小)</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(ans&gt;max || (ans==max &amp;&amp; str.charAt(index)&gt;<span class="ql-token hljs-string">'7'</span>)) </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">return</span> <span class="ql-token hljs-variable">sign</span> <span class="ql-token hljs-operator">=</span>= <span class="ql-token hljs-number">1</span> ? Integer.MAX_VALUE : Integer.MIN_VALUE; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans = ans*<span class="ql-token hljs-number">10</span>+(str.charAt(index)-<span class="ql-token hljs-string">'0'</span>); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans*sign; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p>我的博客:<a href="https://xcscx.github.io/2023/04/15/leetCode/%E5%89%91%E6%8C%87Offer/Day26_%E5%AD%97%E7%AC%A6%E4%B8%8E%E6%95%B0%E5%AD%97/" target="_blank">Day26_字符与数字_剑指Offer | IT蛋的个人博客 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/2023/04/15/leetCode/%E5%89%91%E6%8C%87Offer/Day26_%E5%AD%97%E7%AC%A6%E4%B8%8E%E6%95%B0%E5%AD%97/" target="_blank">)</a></p> </div> </body> </html>

Day25_顺序问题_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">顺时针打印矩阵</strong></p> <p><br></p> <p><strong>Easy</strong> 原题连接:<a href="https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/" target="_blank" style="color: rgb(65, 131, 196);"> 顺时针打印矩阵</a></p> <p>输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:matrix = [[<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>],[<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">6</span>],[<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">8</span>,<span class="ql-token hljs-number">9</span>]] </div> <div class="ql-code-block"> 输出:[<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">9</span>,<span class="ql-token hljs-number">8</span>,<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>] </div> <div class="ql-code-block"> 输入:matrix = [[<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>],[<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">8</span>],[<span class="ql-token hljs-number">9</span>,<span class="ql-token hljs-number">10</span>,<span class="ql-token hljs-number">11</span>,<span class="ql-token hljs-number">12</span>]] </div> <div class="ql-code-block"> 输出:[<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">8</span>,<span class="ql-token hljs-number">12</span>,<span class="ql-token hljs-number">11</span>,<span class="ql-token hljs-number">10</span>,<span class="ql-token hljs-number">9</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">7</span>] </div> </div> <p><strong>提示:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>0 &lt;= <a href="http://matrix.length" target="_blank">matrix.length</a> &lt;= 100</li> <li data-list="ordered"><span class="ql-ui"></span>0 &lt;= matrix[i].length &lt;= 100</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>固定顺时针:向左,向下,向右,向上</p> <p>实现:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>设立上下左右边界,在走完一边后,减少对应的边界范围(如:输出矩阵最上一行后,上边届从0转至1)</li> <li data-list="ordered"><span class="ql-ui"></span>依据 <strong>向左,向下,向右,向上</strong> 循环执行输出,完成一端需要判断下一步是否有路可走(向左到端头,先判断向下是否可以走)</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span>[] spiralOrder(<span class="ql-token hljs-type">int</span>[][] matrix) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(matrix.length == <span class="ql-token hljs-number">0</span> || matrix[<span class="ql-token hljs-number">0</span>].length == <span class="ql-token hljs-number">0</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[<span class="ql-token hljs-number">0</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[matrix.length * matrix[<span class="ql-token hljs-number">0</span>].length]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> size=<span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">leftNum</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>, rightNum = matrix[<span class="ql-token hljs-number">0</span>].length-<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">onNum</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>, downNum = matrix.length-<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(leftNum&lt;=rightNum &amp;&amp; onNum&lt;=downNum) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">j</span> <span class="ql-token hljs-operator">=</span> leftNum; j&lt;=rightNum; j++) ans[size++] = matrix[onNum][j]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(++onNum &gt; downNum)<span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> onNum; i&lt;=downNum; i++) ans[size++] = matrix[i][rightNum]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(leftNum &gt; --rightNum)<span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">j</span> <span class="ql-token hljs-operator">=</span> rightNum; j&gt;=leftNum; j--) ans[size++] = matrix[downNum][j]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(onNum &gt; --downNum)<span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">i</span> <span class="ql-token hljs-operator">=</span> downNum; i&gt;=onNum; i--) ans[size++] = matrix[i][leftNum]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(++leftNum &gt; rightNum)<span class="ql-token hljs-keyword">break</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">栈的压入、弹出序列</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/" target="_blank" style="color: rgb(65, 131, 196);">栈的压入、弹出序列</a></p> <p>输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:pushed = [<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>], popped = [<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">1</span>] </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-literal">true</span> </div> <div class="ql-code-block"> 解释:我们可以按以下顺序执行: </div> <div class="ql-code-block"> push(<span class="ql-token hljs-number">1</span>), push(<span class="ql-token hljs-number">2</span>), push(<span class="ql-token hljs-number">3</span>), push(<span class="ql-token hljs-number">4</span>), pop() -&gt; <span class="ql-token hljs-number">4</span>, </div> <div class="ql-code-block"> push(<span class="ql-token hljs-number">5</span>), pop() -&gt; <span class="ql-token hljs-number">5</span>, pop() -&gt; <span class="ql-token hljs-number">3</span>, pop() -&gt; <span class="ql-token hljs-number">2</span>, pop() -&gt; <span class="ql-token hljs-number">1</span> </div> <div class="ql-code-block"> 输入:pushed = [<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>], popped = [<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>] </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-literal">false</span> </div> <div class="ql-code-block"> 解释:<span class="ql-token hljs-number">1</span> 不能在 <span class="ql-token hljs-number">2</span> 之前弹出。 </div> </div> <p><strong>限制:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>0 &lt;= <a href="http://pushed.length" target="_blank">pushed.length</a> == <a href="http://popped.length" target="_blank">popped.length</a> &lt;= 1000</li> <li data-list="ordered"><span class="ql-ui"></span>0 &lt;= pushed[i], popped[i] &lt; 1000</li> <li data-list="ordered"><span class="ql-ui"></span>pushed 是 popped 的排列。</li> </ol> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>思路:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>使用栈存储数组信息</li> <li data-list="ordered"><span class="ql-ui"></span>如果栈为空,压入条件数组的当前值</li> <li data-list="ordered"><span class="ql-ui"></span>如果当前栈顶和目标数组的当前值一致,弹出,否则一直压入条件数组,直至超过范围或和目标数组一致</li> <li data-list="ordered"><span class="ql-ui"></span>循环2-3,如果最终栈全部弹出,返回true,否则一定在 3 中返回false</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">boolean</span> <span class="ql-token hljs-title">validateStackSequences(int[] pushed, int[] popped)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(pushed.length == <span class="ql-token hljs-number">0</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">true</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">mid</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>,j = <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;Stack&lt;Integer&gt; stack = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">Stack</span>&lt;&gt;(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;stack.push(pushed[<span class="ql-token hljs-number">0</span>]); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">0</span>; i&lt;popped.length; i++){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid = popped[i]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(stack.isEmpty()){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;stack.push(pushed[j]); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;j++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(stack.peek() != mid){ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(j&gt;=pushed.length) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">false</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;stack.push(pushed[j]); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;j++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;stack.pop(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-literal">true</span>; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p>博客:<a href="https://xcscx.github.io/2023/04/14/leetCode/%E5%89%91%E6%8C%87Offer/Day25_%E9%A1%BA%E5%BA%8F/" target="_blank">Day25_顺序_剑指Offer | IT蛋的个人博客 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/2023/04/14/leetCode/%E5%89%91%E6%8C%87Offer/Day25_%E9%A1%BA%E5%BA%8F/" target="_blank">)</a></p> </div> </body> </html>

Day24_数字规律_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">剪绳子</strong></p> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/jian-sheng-zi-lcof/" target="_blank" style="color: rgb(65, 131, 196);">剪绳子</a></p> <p>给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n&gt;1并且m&gt;1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]<em>k[1]</em>...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: <span class="ql-token hljs-number">2</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">1</span> </div> <div class="ql-code-block"> 解释: <span class="ql-token hljs-number">2</span> = <span class="ql-token hljs-number">1</span> + <span class="ql-token hljs-number">1</span>, <span class="ql-token hljs-number">1</span> × <span class="ql-token hljs-number">1</span> = <span class="ql-token hljs-number">1</span> </div> <div class="ql-code-block"> 输入: <span class="ql-token hljs-number">10</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">36</span> </div> <div class="ql-code-block"> 解释: <span class="ql-token hljs-number">10</span> = <span class="ql-token hljs-number">3</span> + <span class="ql-token hljs-number">3</span> + <span class="ql-token hljs-number">4</span>, <span class="ql-token hljs-number">3</span> × <span class="ql-token hljs-number">3</span> × <span class="ql-token hljs-number">4</span> = <span class="ql-token hljs-number">36</span> </div> </div> <p><strong>提示:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>2 &lt;= n &lt;= 58</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>总长度固定,拆成不同长短的子段,算最大乘积</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>子段长度越相等,积越大(算术几何均值不等式)</li> <li data-list="ordered"><span class="ql-ui"></span>不要分出长度为1的子段</li> <li data-list="ordered"><span class="ql-ui"></span>自然对数 e 约等于 2.7</li> </ol> <p>所以设总长度为常数N,拆成a段长度为x,我们有:</p> <p>N = a * x ; ans = x ^ a;</p> <p>得到:ans = ( <strong>x ^ ( 1 / x )</strong> ) ^ N,由于N为常数,ans最终的值会趋近于 2.7 * N,但是绳子要是整数</p> <p>所以目标是<strong>将绳子尽可能化成越多的3</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>当长度可以被3整除,全部转为长度为3的绳子,求值</li> <li data-list="ordered"><span class="ql-ui"></span>当长度对3除余,得到2,转换为一个2和其他为3的数段,求值</li> <li data-list="ordered"><span class="ql-ui"></span>当长度对3除余,得到1,转换为一个4和其他为3的数段,求值</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">cuttingRope(int n)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(n &lt;= <span class="ql-token hljs-number">3</span>)<span class="ql-token hljs-keyword">return</span> n-<span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">a</span> <span class="ql-token hljs-operator">=</span> (<span class="ql-token hljs-type">int</span>)n/<span class="ql-token hljs-number">3</span>, b = n%<span class="ql-token hljs-number">3</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(b == <span class="ql-token hljs-number">2</span>) <span class="ql-token hljs-keyword">return</span> (<span class="ql-token hljs-type">int</span>)Math.pow(<span class="ql-token hljs-number">3</span>,a)*<span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(b == <span class="ql-token hljs-number">1</span>) <span class="ql-token hljs-keyword">return</span> (<span class="ql-token hljs-type">int</span>)Math.pow(<span class="ql-token hljs-number">3</span>,a-<span class="ql-token hljs-number">1</span>)*<span class="ql-token hljs-number">4</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> (<span class="ql-token hljs-type">int</span>)Math.pow(<span class="ql-token hljs-number">3</span>,a); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">和为s的连续正数序列</strong></h2> <p><br></p> <p><strong>Easy</strong> 原题连接:<a href="https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/" target="_blank" style="color: rgb(65, 131, 196);"> 和为s的连续正数序列</a></p> <p>输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。</p> <p>序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:target = <span class="ql-token hljs-number">9</span> </div> <div class="ql-code-block"> 输出:[[<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>],[<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>]] </div> <div class="ql-code-block"> 输入:target = <span class="ql-token hljs-number">15</span> </div> <div class="ql-code-block"> 输出:[[<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>],[<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>,<span class="ql-token hljs-number">6</span>],[<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">8</span>]] </div> </div> <p><strong>限制:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= target &lt;= 10^5</li> <li data-list="ordered"><span class="ql-ui"></span></li> </ol> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>连续数组首先想到滑动窗口:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>设立滑动窗口,左端left,右端right,得到窗口总值:sum = left + right</li> <li data-list="ordered"><span class="ql-ui"></span>判断sum与target的关系:</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>sum == target : 符合目标信息,存储滑动窗口中的数据,窗口小数端移动(符合题目要求:不同序列按照首数字大小排列)</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>sum &lt; target :滑动窗口大数端移动</li> <li data-list="ordered" class="ql-indent-1"><span class="ql-ui"></span>sum &gt; target :滑动窗口小数端移动</li> <li data-list="ordered"><span class="ql-ui"></span>循环2,直至left与right相遇:(窗口最小数已经大于target的一半,无法划分了)</li> </ol> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-comment">// 当你需要从0开始赋值数组,但是你的值随另一个数组变动:</span> </div> <div class="ql-code-block"><span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=left; i&lt;=right; i++) { </div> <div class="ql-code-block"> ans[i-left] = i; </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span>[][] findContinuousSequence(<span class="ql-token hljs-type">int</span> target) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">left</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">1</span>, right =<span class="ql-token hljs-number">2</span>, sum = left + right; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;List&lt;<span class="ql-token hljs-type">int</span>[]&gt; ansList = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">ArrayList</span>&lt;&gt;(); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(left &lt; right) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(sum == target) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[right - left + <span class="ql-token hljs-number">1</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=left; i&lt;=right; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans[i-left] = i; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ansList.add(ans); </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(sum &gt;= target) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sum -= left; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;left++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<span class="ql-token hljs-keyword">else</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;right++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sum += right; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ansList.toArray(<span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[<span class="ql-token hljs-number">0</span>][]); </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">圆圈中最后剩下的数字</strong></h2> <p><br></p> <p><strong>Easy</strong> 原题连接:<a href="https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/" target="_blank" style="color: rgb(65, 131, 196);">圆圈中最后剩下的数字</a></p> <p>0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。</p> <p>例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: n = <span class="ql-token hljs-number">5</span>, m = <span class="ql-token hljs-number">3</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">3</span> </div> <div class="ql-code-block"> 输入: n = <span class="ql-token hljs-number">10</span>, m = <span class="ql-token hljs-number">17</span> </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">2</span> </div> </div> <p><strong>提示:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= n &lt;= 10^5</li> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= m &lt;= 10^6</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p><strong>约瑟夫环问题</strong>:每次都会删除环中一个节点,想知道谁留到最后,由题目提示给的数据量来看,死算是过不了的</p> <p>首先,在最后一次删除后,所剩下的一个数,是当前数组的0位(因为只有一位了)</p> <p>每次删除后,从下一个开始当作新的删除计数,删除 <strong>当前值+( m % i )</strong>, i 为当前循环中的数的总数,为了避免总数超出上线,对 i 去余</p> <p>综合以上两者,可以从一位向前推到(已知最后剩下的是最后数组的0号位,能退出前一次删除的是哪个位置)</p> <p>直到数组长度回复到n,返回最初0号位目前所在的位置即可</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">lastRemaining(int n, int m)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(n == <span class="ql-token hljs-number">1</span>) <span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">1</span>; i&lt;=n; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans = (ans + m) % i; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p>我的博客:<a href="https://xcscx.github.io/2023/04/13/leetCode/%E5%89%91%E6%8C%87Offer/Day24_%E6%95%B0%E5%AD%97%E8%A7%84%E5%BE%8B/" target="_blank">Day24_数字规律_剑指Offer | IT蛋的个人博客 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/2023/04/13/leetCode/%E5%89%91%E6%8C%87Offer/Day24_%E6%95%B0%E5%AD%97%E8%A7%84%E5%BE%8B/" target="_blank">)</a></p> </div> </body> </html>

Day23_数组计算_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">数组中出现次数超过一半的数字</strong></p> <p><br></p> <p><strong>Easy</strong> 原题连接:<a href="https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/" target="_blank" style="color: rgb(65, 131, 196);">数组中出现次数超过一半的数字</a></p> <p>数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。</p> <p>你可以假设数组是非空的,并且给定的数组总是存在多数元素。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: [<span class="ql-token hljs-number">1</span>, <span class="ql-token hljs-number">2</span>, <span class="ql-token hljs-number">3</span>, <span class="ql-token hljs-number">2</span>, <span class="ql-token hljs-number">2</span>, <span class="ql-token hljs-number">2</span>, <span class="ql-token hljs-number">5</span>, <span class="ql-token hljs-number">4</span>, <span class="ql-token hljs-number">2</span>] </div> <div class="ql-code-block"> 输出: <span class="ql-token hljs-number">2</span> </div> </div> <p><strong>限制:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= 数组长度 &lt;= 50000</li> </ol> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>摩尔投票:记录一个值当作目标值,对比接下来的值是否和目标值一致,一致则计数加一,否则减一,当计数为零时更换目标值</p> <p>使用前提:数组中<strong>一定存在超过一半的符合要求的数</strong>,否则算法不成立【1,1,4,4,4,7,7】会返回 7 而不是 4 ,当数组中一定存在超过一半的目标数,剩余的数全部对撞目标数,留下的也一定是目标数。</p> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">majorityElement(int[] nums)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">//摩尔投票算法:对拼消耗</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>, maxNum = <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> num : nums) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(maxNum == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans = num; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>(num == ans) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;maxNum++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }<span class="ql-token hljs-keyword">else</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;maxNum--; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">构建乘积数组</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/" target="_blank" style="color: rgb(65, 131, 196);">构建乘积数组</a></p> <p>给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入: [<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">5</span>] </div> <div class="ql-code-block"> 输出: [<span class="ql-token hljs-number">120</span>,<span class="ql-token hljs-number">60</span>,<span class="ql-token hljs-number">40</span>,<span class="ql-token hljs-number">30</span>,<span class="ql-token hljs-number">24</span>] </div> </div> <p><strong>提示:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>所有元素乘积之和不会溢出 32 位整数</li> <li data-list="ordered"><span class="ql-ui"></span>a.length &lt;= 100000</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>题目提示长度可能达到10w,循环暴力破解肯定是超时下策,但是每个数乘积又需要遍历得到,这时应该考虑复用计算结果</p> <p>将计算 i 位的目标乘积分为两部分来看的话:<strong>i 以前的累乘 * i 以后的累乘</strong></p> <p>计算 i 位的前 i-1 位目标乘积时,i+1 位只需要在此基础上多乘个 a[i]</p> <p>计算 i 位的后 a.length - i 位乘积时,i-1 位只需要再次基础上多乘个 a[i]</p> <p>实现:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>创建对应长度的数组,附上1便于做乘积</li> <li data-list="ordered"><span class="ql-ui"></span>首次循环,计算 i 之前的累积,使用中间值mid存储累积结果</li> <li data-list="ordered"><span class="ql-ui"></span>第二次循环,计算 i 之后的累积,使用中间值mid存储累积结果</li> <li data-list="ordered"><span class="ql-ui"></span>返回结果</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span>[] constructArr(<span class="ql-token hljs-type">int</span>[] a) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[a.length]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">mid</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">0</span>; i&lt;ans.length; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans[i] = <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans[i] *= mid; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid *= a[i]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;mid = <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=ans.length-<span class="ql-token hljs-number">1</span>; i&gt;=<span class="ql-token hljs-number">0</span>; i--) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans[i] *= mid; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid *= a[i]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> ​ </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> ans; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p>笔试笔试,面试面试。应该签三方吗?</p> <p><br></p> <p>我的博客:<a href="https://xcscx.github.io/2023/04/12/leetCode/%E5%89%91%E6%8C%87Offer/Day23_%E6%95%B0%E7%BB%84%E8%AE%A1%E7%AE%97/" target="_blank">Day23_数组计算_剑指Offer | IT蛋的个人博客 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/2023/04/12/leetCode/%E5%89%91%E6%8C%87Offer/Day23_%E6%95%B0%E7%BB%84%E8%AE%A1%E7%AE%97/" target="_blank">)</a></p> </div> </body> </html>

Day22_数组中的重复数字_剑指Offer

<html> <head></head> <body> <div class="content ql-editor"> <p><strong style="font-size: 1.5em;font-style;font-variant-ligatures;font-variant-caps; color: rgb(51, 51, 51);">数组中数字出现的次数</strong></p> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/" target="_blank" style="color: rgb(65, 131, 196);">数组中数字出现的次数</a></p> <p>一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:nums = [<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">6</span>] </div> <div class="ql-code-block"> 输出:[<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">6</span>] 或 [<span class="ql-token hljs-number">6</span>,<span class="ql-token hljs-number">1</span>] </div> <div class="ql-code-block"> 输入:nums = [<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">10</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">3</span>] </div> <div class="ql-code-block"> 输出:[<span class="ql-token hljs-number">2</span>,<span class="ql-token hljs-number">10</span>] 或 [<span class="ql-token hljs-number">10</span>,<span class="ql-token hljs-number">2</span>] </div> </div> <p><strong>限制:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>2 &lt;= <a href="http://nums.length" target="_blank">nums.length</a> &lt;= 10000</li> </ol> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <p>因为题目要求了时间复杂度不能超过O(n),空间复杂度不能超过O(1),所以无法使用HashMap做记录统计值</p> <p>前置知识:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>关于异或(相同返回0,不同返回1):<strong>A^A=0 , A^B=B^A 和 A^0=A</strong> ,所以<strong>A^B^A = A^A^B = 0^B = B</strong></li> <li data-list="ordered"><span class="ql-ui"></span>一个十位数,对应着唯一的二进制值(废话),所以如果两个数的<strong>二进制某个位置值不同,那一定是不同值</strong></li> </ol> <p>实现:</p> <ol> <li data-list="ordered"><span class="ql-ui"></span>对nums中所有数据进行异或,能得到除了重复数字之外的,两个只出现了一次的数的异或结果</li> <li data-list="ordered"><span class="ql-ui"></span>找到这个异或结果的一个“1”,因为是不同值,所以异或一定不为0,找到一个异或结果为1的部分,说明两个数在这个位置二进制值一定不同</li> <li data-list="ordered"><span class="ql-ui"></span>根据2得到的部位,将nums划分为两个部分分别进行异或,得到的两个值就是目标</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span>[] singleNumbers(<span class="ql-token hljs-type">int</span>[] nums) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">ans1</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>, ans2 = <span class="ql-token hljs-number">0</span>, mid = <span class="ql-token hljs-number">0</span>, firstDif = <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 1.找出两个单次出现的数字的异或结果</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> num : nums) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;mid = mid ^ num; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 2.找到区分位</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>((mid &amp; firstDif) == <span class="ql-token hljs-number">0</span>) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;firstDif = firstDif &lt;&lt; <span class="ql-token hljs-number">1</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 3.依据区分为去异或</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> num : nums) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">if</span>((num &amp; firstDif) == <span class="ql-token hljs-number">0</span>)ans1 = ans1 ^ num; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">else</span> ans2 = ans2 ^ num; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[]{ans1, ans2}; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p><br></p> <p><br></p> <h2><strong style="color: rgb(51, 51, 51);">数组中数字出现的次数 II</strong></h2> <p><br></p> <p><strong>medium</strong> 原题连接:<a href="https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/" target="_blank" style="color: rgb(65, 131, 196);">数组中数字出现的次数 II</a></p> <p>在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。</p> <p><strong>示例:</strong></p> <div class="ql-code-block-container"> <div class="ql-code-block"> 输入:nums = [<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">4</span>,<span class="ql-token hljs-number">3</span>,<span class="ql-token hljs-number">3</span>] </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-number">4</span> </div> <div class="ql-code-block"> 输入:nums = [<span class="ql-token hljs-number">9</span>,<span class="ql-token hljs-number">1</span>,<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">9</span>,<span class="ql-token hljs-number">7</span>,<span class="ql-token hljs-number">9</span>,<span class="ql-token hljs-number">7</span>] </div> <div class="ql-code-block"> 输出:<span class="ql-token hljs-number">1</span> </div> </div> <p><strong>提示:</strong></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= <a href="http://nums.length" target="_blank">nums.length</a> &lt;= 10000</li> <li data-list="ordered"><span class="ql-ui"></span>1 &lt;= nums[i] &lt; 2^31</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">解题思路</strong></h3> <p><br></p> <ol> <li data-list="ordered"><span class="ql-ui"></span>数组中出现三次,说明数字转换成二进制后,每个为1的对应位置在数组中会至少有3个1</li> <li data-list="ordered"><span class="ql-ui"></span>将nums的数字全部转换为32位二进制,按对应位填入32位的数组</li> <li data-list="ordered"><span class="ql-ui"></span>对该数组每一位都对3取余,只出现一次的会留下一个1</li> <li data-list="ordered"><span class="ql-ui"></span>重新拼接数组为十进制数,得到结果</li> </ol> <p><br></p> <p><br></p> <h3><strong style="color: rgb(51, 51, 51);">Java代码</strong></h3> <p><br></p> <div class="ql-code-block-container"> <div class="ql-code-block"><span class="ql-token hljs-keyword">class</span> <span class="ql-token hljs-title">Solution</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp;<span class="ql-token hljs-keyword">public</span> <span class="ql-token hljs-type">int</span> <span class="ql-token hljs-title">singleNumber(int[] nums)</span> { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 1.遍历数组,每一位都拆为二进制,按值放入32位数组</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span>[] ans = <span class="ql-token hljs-keyword">new</span> <span class="ql-token hljs-title">int</span>[<span class="ql-token hljs-number">32</span>]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> num : nums) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">while</span>(num &gt;<span class="ql-token hljs-number">0</span> ) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans[i] += num%<span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;num /= <span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;i++; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 2.对数组每一位都取3的模,获得结果</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=<span class="ql-token hljs-number">0</span>; i &lt; ans.length; i++) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;ans[i] = ans[i]%<span class="ql-token hljs-number">3</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-comment">// 3.将结果拼为十位数</span> </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-type">int</span> <span class="ql-token hljs-variable">value</span> <span class="ql-token hljs-operator">=</span> <span class="ql-token hljs-number">0</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">for</span>(<span class="ql-token hljs-type">int</span> i=ans.length-<span class="ql-token hljs-number">1</span>; i&gt;=<span class="ql-token hljs-number">0</span>; i--) { </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;value *= <span class="ql-token hljs-number">2</span>; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;value += ans[i]; </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; } </div> <div class="ql-code-block"> &nbsp; &nbsp; &nbsp; &nbsp;<span class="ql-token hljs-keyword">return</span> value; </div> <div class="ql-code-block"> &nbsp; } </div> <div class="ql-code-block"> } </div> </div> <p>设计项目总是会在前端上掉链子,掉头发的嘞...</p> <p>我的博客:<a href="https://xcscx.github.io/2023/04/11/leetCode/%E5%89%91%E6%8C%87Offer/Day22_%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E6%95%B0%E5%AD%97/" target="_blank">Day22_数组中的重复数字_剑指Offer | IT蛋的个人博客 (</a><a href="http://xcscx.github.io" target="_blank">xcscx.github.io</a><a href="https://xcscx.github.io/2023/04/11/leetCode/%E5%89%91%E6%8C%87Offer/Day22_%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E6%95%B0%E5%AD%97/" target="_blank">)</a></p> </div> </body> </html>

下载 APP