Skip to content

Commit 7c148e1

Browse files
DuHouAnDuHouAn
committed
Java
1 parent 1ee8433 commit 7c148e1

8 files changed

Lines changed: 347 additions & 25 deletions

File tree

‎README.md‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -114,7 +114,6 @@
114114
- [第十三节 排序](docs/AimForOffer/13_排序.md)
115115
- [第十四节 堆](docs/AimForOffer/14_堆.md)
116116
- [第十五节 哈希](docs/AimForOffer/15_哈希.md)
117-
- [第十六节 补充](docs/AimForOffer/16_补充.md)
118117

119118
## 💻 LeetCode 题解**
120119

‎docs/AimForOffer/12_数学运算.md‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -198,20 +198,138 @@ public int Sum_Solution(int n) {
198198
[从 1 到 n 整数中 1 出现的次数](https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&tqId=11184&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
199199

200200
```java
201+
public int NumberOf1Between1AndN_Solution(int n) {
202+
if(n<1){
203+
return 0;
204+
}
205+
206+
int res=0;
207+
208+
int base=1;
209+
int round = n; // n 为原始数字
201210

211+
while (round>0){
212+
int weight = round %10;
213+
round /=10;
214+
res += round*base;
215+
if(weight==1){
216+
int formatter = n%base; //formatter 就是 weight 位的后一位
217+
res += formatter+1;
218+
}else if(weight>1){
219+
res += base;
220+
}
221+
base*=10;
222+
}
223+
return res;
224+
}
202225
```
203226

204227
> [Leetcode : 233. Number of Digit One](https://leetcode.com/problems/number-of-digit-one/discuss/64381/4+-lines-O(log-n)-C++JavaPython)
205228
229+
> [参考：从 1 到 n 整数中 1 出现的次数](https://blog.csdn.net/yi_Afly/article/details/52012593)
230+
206231

207232

208233
## 8、数字序列中的某一位数字
209234

210235
数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。
211236

212237
```java
238+
public int getDigitAtIndex(int index) {
239+
if(index<0){
240+
return -1;
241+
}
242+
int place=1;
243+
while(true){
244+
// place 位的数字的个数
245+
int total = getAmountOfPlace(place);
246+
int bits = total*place; //place 位数字的总位数
247+
if(index<bits){
248+
return getDigitAtIndex(index,place);
249+
}
250+
index -= bits;
251+
place++;
252+
}
253+
}
254+
255+
//获取 place 位的起始数字
256+
//比如：
257+
//1 位数的起始数字是 0
258+
//2 位数的起始数字是 10
259+
//3 位数的起始数字是 100
260+
private int getBeginNumOfPlace(int place){
261+
if(place==1){
262+
return 0;
263+
}
264+
return (int)Math.pow(10,(place-1));
265+
}
266+
267+
//获取 place 位的数字的个数
268+
//比如：
269+
//1 位数[0-9]的数字个数是 10
270+
//2 位数[10-99]的数字个数是 90
271+
//3 位数[100-999]的数字个数是 900
272+
private int getAmountOfPlace(int place) {
273+
if(place==1){
274+
return 10;
275+
}
276+
return (int)Math.pow(10,(place-1))*9;
277+
}
213278

279+
//获取 place 位的所有数字中的第 index 位置的数
280+
private int getDigitAtIndex(int index, int place) {
281+
int beginNumber = getBeginNumOfPlace(place);
282+
int shiftNumber = index/place; //rangeNumber 表示 index 有多少个 place 位的数
283+
int offset = index%place; // 偏移量
284+
String number = beginNumber+shiftNumber+"";
285+
return number.charAt(offset)-'0';
286+
}
214287
```
215288

216289

217290

291+
## 9、圆圈中最后剩下的数
292+
293+
[圆圈中最后剩下的数](https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&tqId=11199&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
294+
295+
```java
296+
//思路：
297+
// 实际上就是约瑟夫环问题:
298+
// 将编号为 0～（N–1）这 N 个人进行圆形排列，按顺时针从 0 开始报数，报到 M–1 的人退出圆形队列，
299+
// 剩下的人继续从 0 开始报数，不断重复。求最后出列者最初在圆形队列中的编号。
300+
301+
// 公式如下：f(N,M) = (f(N-1,M)+M) % N
302+
// N 表示 N 个报数人
303+
// M 表示 报的数
304+
// f(N,M) N个人报数，每报到 (M-1) 时就退出环，最后出列者在圆形队列中的编号。
305+
306+
//写法一： 循环版本
307+
public int LastRemaining_Solution(int n, int m) {
308+
if(n==0){
309+
return -1;
310+
}
311+
if(n==1){
312+
return 0;
313+
}
314+
int f=0;
315+
for(int i=2;i<=n;i++){
316+
f=(f+m)%i;
317+
}
318+
return f;
319+
}
320+
```
321+
322+
```java
323+
//写法二：递归版本
324+
public int LastRemaining_Solution(int n, int m) {
325+
if(n==0){
326+
return -1;
327+
}
328+
if(n==1){
329+
return 0;
330+
}
331+
return (LastRemaining_Solution(n-1,m)+m)%n;
332+
}
333+
```
334+
335+
> [参考：约瑟夫环问题](https://blog.csdn.net/u011500062/article/details/72855826)

‎docs/AimForOffer/16_补充.md‎

Lines changed: 0 additions & 12 deletions
This file was deleted.

‎docs/AimForOffer/1_数组.md‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -389,6 +389,31 @@ public int MoreThanHalfNum_Solution(int [] array) {
389389
[扑克牌顺子](https://www.nowcoder.com/practice/762836f4d43d43ca9deb273b3de8e1f4?tpId=13&tqId=11198&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
390390

391391
```java
392+
public boolean isContinuous(int [] numbers) {
393+
if(numbers.length<5){
394+
return false;
395+
}
392396

397+
//统计这些牌中大小王数
398+
int cnt=0;
399+
Arrays.sort(numbers);
400+
for(int num : numbers){
401+
if(num==0){
402+
cnt++;
403+
}else{
404+
break;
405+
}
406+
}
407+
408+
//使用大小王补全相邻数字中间的间隙
409+
for(int i=cnt;i<numbers.length-1;i++){ // i 从 cnt 开始，cnt 位置之前都是 0
410+
if(numbers[i]==numbers[i+1]){
411+
return false;
412+
}
413+
//需要在 [numbers[i],numbers[i+1]] 之间插入 (numbers[i+1]-numbers[i]-1) 个元素
414+
cnt -= (numbers[i+1]-numbers[i]-1);
415+
}
416+
return cnt>=0;
417+
}
393418
```
394419

‎docs/AimForOffer/2_字符串.md‎

Lines changed: 0 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -364,13 +364,3 @@ public int lengthOfLongestSubstring(String s) {
364364
}
365365
```
366366

367-
368-
369-
## 11、把数字翻译成字符串
370-
371-
[把数字翻译成字符串](https://leetcode.com/problems/decode-ways/description/)
372-
373-
```java
374-
375-
```
376-

‎docs/AimForOffer/4_链表.md‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -360,7 +360,101 @@ public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
360360

361361
[复杂链表的复制](https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
362362

363+
![img](https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/66a01953-5303-43b1-8646-0c77b825e980.png)
364+
363365
```java
366+
//思路：
367+
```
368+
369+
第一步，在每个节点的后面插入**复制的节点**。
370+
371+
![img](https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/dfd5d3f8-673c-486b-8ecf-d2082107b67b.png)
372+
373+
第二步，对**复制节点的 random 链接**进行赋值。
374+
375+
![img](https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/cafbfeb8-7dfe-4c0a-a3c9-750eeb824068.png)
376+
377+
第三步，拆分。
378+
379+
![img](https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/e151b5df-5390-4365-b66e-b130cd253c12.png)
380+
381+
```java
382+
public RandomListNode Clone(RandomListNode pHead) {
383+
if(pHead==null){
384+
return null;
385+
}
386+
387+
//第一步，在每个节点的后面插入复制的节点
388+
RandomListNode cur=pHead;
389+
while (cur!=null){
390+
RandomListNode newNode = new RandomListNode(cur.label);
391+
newNode.next = cur.next;
392+
cur.next = newNode;
393+
cur=newNode.next;
394+
}
395+
396+
//对复制节点的 random 链接进行赋值。
397+
cur=pHead;
398+
while(cur!=null){
399+
// cur 是当前的节点
400+
// cur.next 是复制的节点
401+
RandomListNode clone = cur.next;
402+
if(cur.random!=null){
403+
clone.random = cur.random.next; //
404+
//cur.random 是 cur 的random 指向的节点
405+
//cur.random.next 就是 cur.random.next 的复制节点
406+
}
407+
cur=clone.next;
408+
}
364409

410+
//拆分
411+
cur=pHead;
412+
RandomListNode pCloneHead = pHead.next;
413+
while(cur.next!=null){ //拆分出 pHead 原来的链表，剩下的就是 pCloneHead 链表
414+
RandomListNode next = cur.next;
415+
cur.next = next.next;
416+
cur=next;
417+
}
418+
return pCloneHead;
419+
}
420+
```
421+
422+
423+
424+
## 10、在 O(1) 时间删除链表节点
425+
426+
```java
427+
//思路：
428+
//1、如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，
429+
//然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
430+
431+
//2、如果该节点是尾节点，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，
432+
//时间复杂度为 O(N)。
433+
434+
//分析：
435+
// 如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，
436+
// 其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，
437+
// N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。
438+
// (2N-1)/N 约等于 2，因此该算法的平均时间复杂度为 O(1)。
439+
440+
public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
441+
if(head==null || tobeDelete==null){
442+
return null;
443+
}
444+
if(tobeDelete.next!=null){ //待删除的节点不是尾节点
445+
// 令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
446+
ListNode next = tobeDelete.next;
447+
tobeDelete.val = next.val;
448+
tobeDelete.next = next.next;
449+
}else{ //待删除的节点是尾节点
450+
ListNode cur=head;
451+
while (cur.next!=tobeDelete){
452+
cur=cur.next;
453+
}
454+
// cur.next 此时指向 tobeDelete
455+
cur.next=null;
456+
}
457+
return head;
458+
}
365459
```
366460

0 commit comments

Comments
 (0)