-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path62779.html
317 lines (280 loc) · 49.7 KB
/
62779.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no"><title>Java刷题笔记（二） | magic-H</title><meta name="keywords" content="Java,算法"><meta name="author" content="magic-H"><meta name="copyright" content="magic-H"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="一.简介 本系列是用来分享在洛谷，LeetCode的有趣的题目，使用Java编写且代码解释以注释为主。 本篇涉及：双指针，哈希表，原地交换 二.题目1. 移动零题目描述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 输入输出样例：示例 1: 输入: nums = [0">
<meta property="og:type" content="article">
<meta property="og:title" content="Java刷题笔记（二）">
<meta property="og:url" content="https://magic-h.top/62779.html">
<meta property="og:site_name" content="magic-H">
<meta property="og:description" content="一.简介 本系列是用来分享在洛谷，LeetCode的有趣的题目，使用Java编写且代码解释以注释为主。 本篇涉及：双指针，哈希表，原地交换 二.题目1. 移动零题目描述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 请注意 ，必须在不复制数组的情况下原地对数组进行操作。 输入输出样例：示例 1: 输入: nums = [0">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg">
<meta property="article:published_time" content="2022-07-29T00:00:00.000Z">
<meta property="article:modified_time" content="2023-06-09T02:57:26.202Z">
<meta property="article:author" content="magic-H">
<meta property="article:tag" content="Java">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg"><link rel="shortcut icon" href="/img/favicon.ico"><link rel="canonical" href="https://magic-h.top/62779"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//sdk.51.la"/><link rel="preconnect" href="//fonts.googleapis.com" crossorigin=""/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@6/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.css" media="print" onload="this.media='all'"><script>!function(p){"use strict";!function(t){var s=window,e=document,i=p,c="".concat("https:"===e.location.protocol?"https://":"http://","sdk.51.la/js-sdk-pro.min.js"),n=e.createElement("script"),r=e.getElementsByTagName("script")[0];n.type="text/javascript",n.setAttribute("charset","UTF-8"),n.async=!0,n.src=c,n.id="LA_COLLECT",i.d=n;var o=function(){s.LA.ids.push(i)};s.LA?s.LA.ids&&o():(s.LA=p,s.LA.ids=[],o()),r.parentNode.insertBefore(n,r)}()}({id:"Jl7ITgjGBeVbLmqO",ck:"Jl7ITgjGBeVbLmqO"});
</script><script>!(function(c,i,e,b){
var h=i.createElement("script");
var f=i.getElementsByTagName("script")[0];
h.type="text/javascript";
h.crossorigin=true;
h.onload=function(){new c[b]["Monitor"]().init({id:"Jl7IrsA7TWlXlR99"});};
f.parentNode.insertBefore(h,f);h.src=e;})(window,document,"https://sdk.51.la/perf/js-sdk-perf.min.js","LingQue");</script><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Titillium+Web&display=swap" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: false,
post: false
},
runtime: '天',
date_suffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: undefined,
lightbox: 'mediumZoom',
Snackbar: {"chs_to_cht":"你已切换为繁体","cht_to_chs":"你已切换为简体","day_to_night":"你已切换为深色模式","night_to_day":"你已切换为浅色模式","bgLight":"#49b1f5","bgDark":"#1f1f1f","position":"bottom-left"},
source: {
justifiedGallery: {
js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.js',
css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.css'
}
},
isPhotoFigcaption: false,
islazyload: false,
isAnchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: 'Java刷题笔记（二）',
isPost: true,
isHome: false,
isHighlightShrink: false,
isToc: true,
postUpdate: '2023-06-09 02:57:26'
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><link rel="stylesheet" href="/css/mycss.css"><script src="/js/sakura.js"></script><script src="/js/snow2.js"></script><meta name="generator" content="Hexo 6.1.0"><link rel="alternate" href="/atom.xml" title="magic-H" type="application/atom+xml">
</head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://s4.ax1x.com/2022/02/18/HT4dgI.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data is-center"><div class="data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">21</div></a></div><div class="data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a></div><div class="data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">0</div></a></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/%E7%9B%B8%E5%86%8C/"><i class="fa-fw fa fa-video"></i><span> 相册</span></a></div><div class="menus_item"><a class="site-page" href="/questions/"><i class="fa-fw fa fa-video"></i><span> 答疑</span></a></div><div class="menus_item"><a class="site-page" href="/artitalk/"><i class="fa-fw fa fa-home"></i><span> 说说</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间线</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207182124785.png')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">magic-H</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page" href="/%E7%9B%B8%E5%86%8C/"><i class="fa-fw fa fa-video"></i><span> 相册</span></a></div><div class="menus_item"><a class="site-page" href="/questions/"><i class="fa-fw fa fa-video"></i><span> 答疑</span></a></div><div class="menus_item"><a class="site-page" href="/artitalk/"><i class="fa-fw fa fa-home"></i><span> 说说</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间线</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">Java刷题笔记（二）</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2022-07-29T00:00:00.000Z" title="发表于 2022-07-29 00:00:00">2022-07-29</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-09T02:57:26.202Z" title="更新于 2023-06-09 02:57:26">2023-06-09</time></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">1.3k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>4分钟</span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="一-简介"><a href="#一-简介" class="headerlink" title="一.简介"></a><code>一.简介</code></h1><p> 本系列是用来分享在<a target="_blank" rel="noopener" href="https://www.luogu.com.cn/">洛谷</a>，<a target="_blank" rel="noopener" href="https://leetcode.cn/">LeetCode</a>的有趣的题目，使用Java编写且代码解释以注释为主。</p>
<p> 本篇涉及：<strong>双指针，哈希表，原地交换</strong></p>
<hr>
<h1 id="二-题目"><a href="#二-题目" class="headerlink" title="二.题目"></a><code>二.题目</code></h1><h2 id="1-移动零"><a href="#1-移动零" class="headerlink" title="1. 移动零"></a>1. <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/move-zeroes">移动零</a></h2><h3 id="题目描述："><a href="#题目描述：" class="headerlink" title="题目描述："></a>题目描述：</h3><p> 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。</p>
<p>请注意 ，必须在不复制数组的情况下原地对数组进行操作。</p>
<h3 id="输入输出样例："><a href="#输入输出样例：" class="headerlink" title="输入输出样例："></a>输入输出样例：</h3><h4 id="示例-1"><a href="#示例-1" class="headerlink" title="示例 1:"></a>示例 1:</h4><p> <strong>输入: nums = [0,1,0,3,12]</strong><br> <strong>输出: [1,3,12,0,0]</strong></p>
<h4 id="示例-2"><a href="#示例-2" class="headerlink" title="示例 2:"></a>示例 2:</h4><p> <strong>输入: <code>nums = [0]</code></strong><br> <strong>输出: <code>[0]</code></strong></p>
<h4 id="提示"><a href="#提示" class="headerlink" title="提示:"></a>提示:</h4><p>1 <= nums.length <= 104<br>-231 <= nums[i] <= 231 - 1</p>
<h3 id="解法一：双指针"><a href="#解法一：双指针" class="headerlink" title="解法一：双指针"></a>解法一：双指针</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//AC代码</span></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。</span></span><br><span class="line"><span class="comment"> * 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 注意到以下性质：</span></span><br><span class="line"><span class="comment"> * 左指针左边均为非零数；</span></span><br><span class="line"><span class="comment"> * 右指针左边直到左指针处均为零。</span></span><br><span class="line"><span class="comment"> * </span></span><br><span class="line"><span class="comment"> * 复杂度分析：</span></span><br><span class="line"><span class="comment"> * 时间复杂度 O(N)</span></span><br><span class="line"><span class="comment"> * 空间复杂度 O(1)</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">void</span> <span class="title function_">moveZeroes</span><span class="params">(<span class="type">int</span>[] nums)</span> {</span><br><span class="line"> <span class="comment">//定义j为左指针</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"> <span class="comment">//定义i为右指针，不断向右移动</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i < nums.length; i++) {</span><br><span class="line"> <span class="comment">//判断右指针不为零，将左右指针对应的数交换</span></span><br><span class="line"> <span class="keyword">if</span> (nums[i] != <span class="number">0</span>) {</span><br><span class="line"> <span class="comment">//但左右指针相等的时候，跳过判断</span></span><br><span class="line"> <span class="keyword">if</span>(i!=j){</span><br><span class="line"> nums[j] = nums[i];</span><br><span class="line"> <span class="comment">//交换完后，将右指针置为0</span></span><br><span class="line"> nums[i] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//左指针右移</span></span><br><span class="line"> j++;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">//注意：不能将两个if判断写成：if(nums[i]!=0&&i!=j),因为当左指针j需要在右指针i不为零时+1</span></span><br><span class="line"><span class="comment">//可如果写成if(nums[i]!=0&&i!=j)，则当nums[i]!=0而i==j时，j不加1.</span></span><br></pre></td></tr></table></figure>
<p>双指针补充（来源：力扣题解）：</p>
<p><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291443057.gif" alt="双指针"></p>
<h2 id="2-数组中的重复元素"><a href="#2-数组中的重复元素" class="headerlink" title="2. 数组中的重复元素"></a>2. <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/">数组中的重复元素</a></h2><h3 id="题目描述：-1"><a href="#题目描述：-1" class="headerlink" title="题目描述："></a>题目描述：</h3><p> 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。</p>
<h3 id="输入输出样例：-1"><a href="#输入输出样例：-1" class="headerlink" title="输入输出样例："></a>输入输出样例：</h3><h4 id="示例-1-1"><a href="#示例-1-1" class="headerlink" title="示例 1:"></a>示例 1:</h4><p> <strong>输入: <code>[2, 3, 1, 0, 2, 5, 3]</code></strong><br> <strong>输出: <code>2 或 3 </code></strong></p>
<h4 id="提示-1"><a href="#提示-1" class="headerlink" title="提示:"></a>提示:</h4><p> 2 <= n <= 100000</p>
<h3 id="解法一：哈希表-x2F-Set"><a href="#解法一：哈希表-x2F-Set" class="headerlink" title="解法一：哈希表 / Set"></a>解法一：哈希表 / Set</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 算法流程：</span></span><br><span class="line"><span class="comment"> * 初始化： 新建 HashSet ，记为 dic ；</span></span><br><span class="line"><span class="comment"> * 遍历数组 nums 中的每个数字 num ：</span></span><br><span class="line"><span class="comment"> * 当 num 在 dic 中，说明重复，直接返回 num ；</span></span><br><span class="line"><span class="comment"> * 将 num 添加至 dic 中；</span></span><br><span class="line"><span class="comment"> * 返回 -1−1 。本题中一定有重复数字，因此这里返回多少都可以。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 复杂度分析：</span></span><br><span class="line"><span class="comment"> * 时间复杂度 O(N) ： 遍历数组使用 O(N) ，HashSet 添加与查找元素皆为 O(1)。</span></span><br><span class="line"><span class="comment"> * 空间复杂度 O(N) ： HashSet 占用 O(N) 大小的额外空间。</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">findRepeatNumber</span><span class="params">(<span class="type">int</span>[] nums)</span> {</span><br><span class="line"> <span class="comment">//创建哈希表</span></span><br><span class="line"> Set<Integer> dic = <span class="keyword">new</span> <span class="title class_">HashSet</span><>();</span><br><span class="line"> <span class="comment">//遍历nums</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> num : nums) {</span><br><span class="line"> <span class="comment">//当 num 在 dic 中，说明重复，直接返回 num</span></span><br><span class="line"> <span class="keyword">if</span>(dic.contains(num)) <span class="keyword">return</span> num;</span><br><span class="line"> <span class="comment">//向哈希表中添加num</span></span><br><span class="line"> dic.add(num);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="解法二：原地交换"><a href="#解法二：原地交换" class="headerlink" title="解法二：原地交换"></a>解法二：原地交换</h3><p> 题目说明尚未被充分使用，即 在一个长度为 n 的数组<strong>nums</strong>里的所有数字都在 0 ~ n-1 的范围内 。 </p>
<p> 此说明含义：数组元素的<strong>索引</strong>和<strong>值</strong>是<strong>一对多</strong>的关系。</p>
<p> 因此，可遍历数组并通过交换操作，使元素的<strong>索引</strong>与<strong>值</strong>一一对应（即 nums[i] = inums[i]=i ）。</p>
<p> 因而，就能通过索引映射对应的值，起到与字典等价的作用。</p>
<p><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291525568.png" alt="Picture0.png"></p>
<p> 遍历中，第一次遇到数字 xx 时，将其交换至索引 xx 处；而当第二次遇到数字 xx 时，一定有 nums[x] = xnums[x]=x ，此时即可得到一组重复数字。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 1. 遍历数组 nums ，设索引初始值为 i = 0:</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 1. 若 nums[i] = i ： 说明此数字已在对应索引位置，无需交换，因此跳过；</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 2. 若 nums[nums[i]] = nums[i] ： 代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i]；</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 3. 否则： 交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 2. 若遍历完毕尚未返回，则返回 -1 。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 复杂度分析：</span></span><br><span class="line"><span class="comment"> * 时间复杂度 O(N) ： 遍历数组使用 O(N) ，每轮遍历的判断和交换操作使用 O(1) 。</span></span><br><span class="line"><span class="comment"> * 空间复杂度 O(1) ： 使用常数复杂度的额外空间。</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"> <span class="keyword">public</span> <span class="type">int</span> <span class="title function_">findRepeatNumber</span><span class="params">(<span class="type">int</span>[] nums)</span> {</span><br><span class="line"> <span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line"> <span class="comment">//遍历数组</span></span><br><span class="line"> <span class="keyword">while</span>(i < nums.length) {</span><br><span class="line"> <span class="comment">//如果索引和数字相等，跳过此次循环</span></span><br><span class="line"> <span class="keyword">if</span>(nums[i] == i) {</span><br><span class="line"> i++;</span><br><span class="line"> <span class="keyword">continue</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//当索引nums[i]和索引i对于的元素值都为nums[i]时，返回该重复值nums[i]</span></span><br><span class="line"> <span class="keyword">if</span>(nums[nums[i]] == nums[i]) <span class="keyword">return</span> nums[i];</span><br><span class="line"> <span class="comment">//交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。</span></span><br><span class="line"> <span class="type">int</span> <span class="variable">tmp</span> <span class="operator">=</span> nums[i];</span><br><span class="line"> nums[i] = nums[tmp];</span><br><span class="line"> nums[tmp] = tmp;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">magic-H</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://magic-h.top/62779.html">https://magic-h.top/62779.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://magic-H.top" target="_blank">magic-H</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/Java/">Java</a><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">算法</a></div><div class="post_share"><div class="social-share" data-image="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2567.html"><img class="prev-cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">Java刷题笔记（三）</div></div></a></div><div class="next-post pull-right"><a href="/64644.html"><img class="next-cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">线性表（下）</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/2567.html" title="Java刷题笔记（三）"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-30</div><div class="title">Java刷题笔记（三）</div></div></a></div><div><a href="/25921.html" title="Java刷题笔记（一）"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207251735416.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-25</div><div class="title">Java刷题笔记（一）</div></div></a></div><div><a href="/52461.html" title="Java环境配置及入门"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207191420275.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-19</div><div class="title">Java环境配置及入门</div></div></a></div><div><a href="/58601.html" title="时间复杂度"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-26</div><div class="title">时间复杂度</div></div></a></div><div><a href="/27902.html" title="线性表（上）"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-27</div><div class="title">线性表（上）</div></div></a></div><div><a href="/64644.html" title="线性表（下）"><img class="cover" src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-07-28</div><div class="title">线性表（下）</div></div></a></div></div></div><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div id="waline-wrap"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://s4.ax1x.com/2022/02/18/HT4dgI.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">magic-H</div><div class="author-info__description"></div></div><div class="card-info-data is-center"><div class="card-info-data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">21</div></a></div><div class="card-info-data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">9</div></a></div><div class="card-info-data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">0</div></a></div></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/magic-H728"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/magic-H728" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="mailto:[email protected]" target="_blank" title="Email"><i class="fas fa-envelope"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">This is my Blog</div></div><div class="card-widget"><div class="item-headline"><i></i><span></span></div><div class="item-content"></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%B8%80-%E7%AE%80%E4%BB%8B"><span class="toc-text">一.简介</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C-%E9%A2%98%E7%9B%AE"><span class="toc-text">二.题目</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-%E7%A7%BB%E5%8A%A8%E9%9B%B6"><span class="toc-text">1. 移动零</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0%EF%BC%9A"><span class="toc-text">题目描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B%EF%BC%9A"><span class="toc-text">输入输出样例：</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%A4%BA%E4%BE%8B-1"><span class="toc-text">示例 1:</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%A4%BA%E4%BE%8B-2"><span class="toc-text">示例 2:</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8F%90%E7%A4%BA"><span class="toc-text">提示:</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%A7%A3%E6%B3%95%E4%B8%80%EF%BC%9A%E5%8F%8C%E6%8C%87%E9%92%88"><span class="toc-text">解法一：双指针</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0"><span class="toc-text">2. 数组中的重复元素</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0%EF%BC%9A-1"><span class="toc-text">题目描述：</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BE%93%E5%85%A5%E8%BE%93%E5%87%BA%E6%A0%B7%E4%BE%8B%EF%BC%9A-1"><span class="toc-text">输入输出样例：</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%A4%BA%E4%BE%8B-1-1"><span class="toc-text">示例 1:</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8F%90%E7%A4%BA-1"><span class="toc-text">提示:</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%A7%A3%E6%B3%95%E4%B8%80%EF%BC%9A%E5%93%88%E5%B8%8C%E8%A1%A8-x2F-Set"><span class="toc-text">解法一：哈希表 / Set</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%A7%A3%E6%B3%95%E4%BA%8C%EF%BC%9A%E5%8E%9F%E5%9C%B0%E4%BA%A4%E6%8D%A2"><span class="toc-text">解法二：原地交换</span></a></li></ol></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/25737.html" title="数据结构OJ"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202301131413619.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="数据结构OJ"/></a><div class="content"><a class="title" href="/25737.html" title="数据结构OJ">数据结构OJ</a><time datetime="2023-01-13T00:00:00.000Z" title="发表于 2023-01-13 00:00:00">2023-01-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/48665.html" title="Notion知识体系管理工具"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207311705467.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Notion知识体系管理工具"/></a><div class="content"><a class="title" href="/48665.html" title="Notion知识体系管理工具">Notion知识体系管理工具</a><time datetime="2022-07-31T00:00:00.000Z" title="发表于 2022-07-31 00:00:00">2022-07-31</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2567.html" title="Java刷题笔记（三）"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java刷题笔记（三）"/></a><div class="content"><a class="title" href="/2567.html" title="Java刷题笔记（三）">Java刷题笔记（三）</a><time datetime="2022-07-30T00:00:00.000Z" title="发表于 2022-07-30 00:00:00">2022-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/62779.html" title="Java刷题笔记（二）"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207291555693.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java刷题笔记（二）"/></a><div class="content"><a class="title" href="/62779.html" title="Java刷题笔记（二）">Java刷题笔记（二）</a><time datetime="2022-07-29T00:00:00.000Z" title="发表于 2022-07-29 00:00:00">2022-07-29</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/64644.html" title="线性表（下）"><img src="https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207261740136.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="线性表（下）"/></a><div class="content"><a class="title" href="/64644.html" title="线性表（下）">线性表（下）</a><time datetime="2022-07-28T00:00:00.000Z" title="发表于 2022-07-28 00:00:00">2022-07-28</time></div></div></div></div></div></div></main><footer id="footer" style="background-image: url('https://testingcf.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207182124785.png')"><div id="footer-wrap"><div class="copyright">©2022 - 2023 By magic-H</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><img src="https://gcore.jsdelivr.net/gh/magic-H728/Store@master/blog-img/202207181316087.png">
<a href="http://www.beian.miit.gov.cn/" style="color:#f72b07" target="_blank">粤ICP备2022027428号</a><div class="footer_custom_text">Hi, welcome to my <a href="magic-h.top">blog</a>!</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">本地搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/medium-zoom/dist/medium-zoom.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><script>function panguFn () {
if (typeof pangu === 'object') pangu.autoSpacingPage()
else {
getScript('https://cdn.jsdelivr.net/npm/pangu/dist/browser/pangu.min.js')
.then(() => {
pangu.autoSpacingPage()
})
}
}
function panguInit () {
if (false){
GLOBAL_CONFIG_SITE.isPost && panguFn()
} else {
panguFn()
}
}
document.addEventListener('DOMContentLoaded', panguInit)</script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>(() => {
const $mermaidWrap = document.querySelectorAll('#article-container .mermaid-wrap')
if ($mermaidWrap.length) {
window.runMermaid = () => {
window.loadMermaid = true
const theme = document.documentElement.getAttribute('data-theme') === 'dark' ? 'dark' : 'default'
Array.from($mermaidWrap).forEach((item, index) => {
const mermaidSrc = item.firstElementChild
const mermaidThemeConfig = '%%{init:{ \'theme\':\'' + theme + '\'}}%%\n'
const mermaidID = 'mermaid-' + index
const mermaidDefinition = mermaidThemeConfig + mermaidSrc.textContent
mermaid.mermaidAPI.render(mermaidID, mermaidDefinition, (svgCode) => {
mermaidSrc.insertAdjacentHTML('afterend', svgCode)
})
})
}
const loadMermaid = () => {
window.loadMermaid ? runMermaid() : getScript('https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js').then(runMermaid)
}
window.pjax ? loadMermaid() : document.addEventListener('DOMContentLoaded', loadMermaid)
}
})()</script><script>function loadWaline () {
function initWaline () {
const waline = new Waline(Object.assign({
el: '#waline-wrap',
serverURL: 'https://magic-h-mr0qem8oh-magic-h728.vercel.app/',
path: location.pathname,
visitor: false,
dark: 'html[data-theme="dark"]'
}, null))
}
if (typeof Waline === 'function') initWaline()
else getScript('https://cdn.jsdelivr.net/npm/@waline/client/dist/Waline.min.js').then(initWaline)
}
if ('Waline' === 'Waline' || !false) {
if (false) btf.loadComment(document.getElementById('waline-wrap'),loadWaline)
else setTimeout(loadWaline, 0)
} else {
function loadOtherComment () {
loadWaline()
}
}</script></div><canvas class="fireworks" mobile="false"></canvas><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/fireworks.min.js"></script><script defer="defer" id="fluttering_ribbon" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-fluttering-ribbon.min.js"></script><script id="canvas_nest" defer="defer" color="200,100,255" opacity="0.7" zIndex="-1" count="118" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-nest.min.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/activate-power-mode.min.js"></script><script>POWERMODE.colorful = true;
POWERMODE.shake = false;
POWERMODE.mobile = false;
document.body.addEventListener('input', POWERMODE);
</script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors = ["title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"]
var pjax = new Pjax({
elements: 'a:not([target="_blank"]):not([href="/music/"]):not([href="/no-pjax/"])',
selectors: pjaxSelectors,
cacheBust: false,
analytics: false,
scrollRestoration: false
})
document.addEventListener('pjax:send', function () {
// removeEventListener scroll
window.tocScrollFn && window.removeEventListener('scroll', window.tocScrollFn)
window.scrollCollect && window.removeEventListener('scroll', scrollCollect)
typeof preloader === 'object' && preloader.initLoading()
document.getElementById('rightside').style.cssText = "opacity: ''; transform: ''"
if (window.aplayers) {
for (let i = 0; i < window.aplayers.length; i++) {
if (!window.aplayers[i].options.fixed) {
window.aplayers[i].destroy()
}
}
}
typeof typed === 'object' && typed.destroy()
//reset readmode
const $bodyClassList = document.body.classList
$bodyClassList.contains('read-mode') && $bodyClassList.remove('read-mode')
})
document.addEventListener('pjax:complete', function () {
window.refreshFn()
document.querySelectorAll('script[data-pjax]').forEach(item => {
const newScript = document.createElement('script')
const content = item.text || item.textContent || item.innerHTML || ""
Array.from(item.attributes).forEach(attr => newScript.setAttribute(attr.name, attr.value))
newScript.appendChild(document.createTextNode(content))
item.parentNode.replaceChild(newScript, item)
})
GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()
typeof chatBtnFn === 'function' && chatBtnFn()
typeof panguInit === 'function' && panguInit()
// google analytics
typeof gtag === 'function' && gtag('config', '', {'page_path': window.location.pathname});
// baidu analytics
typeof _hmt === 'object' && _hmt.push(['_trackPageview',window.location.pathname]);
typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()
// prismjs
typeof Prism === 'object' && Prism.highlightAll()
typeof preloader === 'object' && preloader.endLoading()
})
document.addEventListener('pjax:error', (e) => {
if (e.request.status === 404) {
pjax.loadUrl('/404.html')
}
})</script></div></body></html>