Skip to content

Commit 4667a5a

Browse files
DuHouAnDuHouAn
committed
Java
1 parent 384c4c5 commit 4667a5a

31 files changed

Lines changed: 968 additions & 1517 deletions

‎docs/AimForOffer/数据结构相关/1_数组和矩阵.md‎

Lines changed: 34 additions & 315 deletions
Large diffs are not rendered by default.

‎docs/AimForOffer/数据结构相关/2_字符串.md‎

Lines changed: 7 additions & 235 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
# 字符串
22

3-
## 1、替换空格（4）
3+
## 1、替换空格
44

55
[替换空格](https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423?tpId=13&tqId=11155&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
66

@@ -36,7 +36,7 @@ public String replaceSpace(StringBuffer str) {
3636

3737

3838

39-
## *2、正则表达式匹配（5）
39+
## *2、正则表达式匹配
4040

4141
[正则表达式匹配](https://www.nowcoder.com/practice/45327ae22b7b413ea21df13ee7d6429c?tpId=13&tqId=11205&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
4242

@@ -98,7 +98,7 @@ private boolean match(char[] str,int strIndex,char[] pattern,int patternIndex){
9898

9999

100100

101-
## 3、表示数值的字符串（6）
101+
## 3、表示数值的字符串
102102

103103
[表示数值的字符串](https://www.nowcoder.com/practice/6f8c901d091949a5837e24bb82a731f2?tpId=13&tqId=11206&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
104104

@@ -131,7 +131,7 @@ public boolean isNumeric(char[] str) {
131131

132132

133133

134-
## 4、字符流中第一个不重复的字符（7）
134+
## 4、字符流中第一个不重复的字符
135135

136136
[字符流中第一个不重复的字符](https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720?tpId=13&tqId=11207&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
137137

@@ -188,7 +188,7 @@ public char FirstAppearingOnce(){
188188

189189

190190

191-
## *5、字符串的排列（42）
191+
## *5、字符串的排列
192192

193193
[字符串的排列](https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
194194

@@ -234,7 +234,7 @@ private void permute(char[] chs,int index,StringBuilder p){
234234

235235

236236

237-
## 6、把数组排成最小的数（47）
237+
## 6、把数组排成最小的数
238238

239239
[把数组排成最小的数](https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
240240

@@ -277,7 +277,7 @@ public String PrintMinNumber(int [] numbers) {
277277

278278

279279

280-
## 7、把字符串转换成整数（64）
280+
## 7、把字符串转换成整数
281281

282282
[把字符串转换成整数](https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&tqId=11202&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
283283

@@ -385,231 +385,3 @@ private void reverse(char[] chs,int start,int end){
385385
```
386386

387387

388-
389-
## *10、最长不含重复字符的子字符串
390-
391-
[最长不含重复字符的子字符串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
392-
393-
```java
394-
//思路：
395-
// 使用滑动窗口 [l,r]
396-
// 在滑动窗口中的元素是不会重复的
397-
398-
public int lengthOfLongestSubstring(String s) {
399-
int res=0;
400-
401-
//统计滑动窗口中出现的字符的次数
402-
int[] freq = new int[256];
403-
404-
int l=0;
405-
int r=-1; //[l,r] 开区间
406-
int n =s.length();
407-
while (l<n){
408-
if(r+1<n && freq[s.charAt(r+1)]==0){ //扩展窗口
409-
r++;
410-
freq[s.charAt(r)]++;
411-
}else{ //缩小窗口
412-
freq[s.charAt(l)]--;
413-
l++;
414-
}
415-
res = Math.max(res,r-l+1);
416-
}
417-
return res;
418-
}
419-
```
420-
421-
422-
423-
## 11、字符串相加
424-
425-
[字符串相加](https://leetcode-cn.com/problems/add-strings/)
426-
427-
```java
428-
public String addStrings(String num1, String num2) {
429-
if(num1==null || num1.length()==0){
430-
return num2;
431-
}
432-
if(num2==null || num2.length()==0){
433-
return num1;
434-
}
435-
436-
char[] chs1=num1.toCharArray();
437-
char[] chs2=num2.toCharArray();
438-
439-
int i=chs1.length-1;
440-
int j=chs2.length-1;
441-
442-
int c=0;
443-
444-
StringBuilder res = new StringBuilder();
445-
446-
//从后向前按位相加
447-
while(i>=0 || j>=0){
448-
c+=(i>=0)?chs1[i--]-'0':0;
449-
c+=(j>=0)?chs2[j--]-'0':0;
450-
res.append(c%10);
451-
c/=10;
452-
}
453-
if(c==1){
454-
res.append(1);
455-
}
456-
return res.reverse().toString();
457-
}
458-
```
459-
460-
461-
462-
## *12、KMP 算法
463-
464-
[实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/)
465-
466-
```java
467-
public int strStr(String haystack, String needle) {
468-
int m=haystack.length();
469-
int n=needle.length();
470-
471-
if(n==0){ // needle 是空字符串，默认返回 0
472-
return 0;
473-
}
474-
475-
int i=0,j=0;
476-
int k=0;
477-
while(i<m && j<n){
478-
if(haystack.charAt(i)==needle.charAt(j)){
479-
i++;
480-
j++;
481-
}else{
482-
j=0;
483-
i=++k;
484-
}
485-
}
486-
if(j==n){ //说明 needle 完全匹配
487-
return k;
488-
}
489-
return -1;
490-
}
491-
```
492-
493-
494-
495-
## 13、最长回文串
496-
497-
[最长回文串](https://leetcode-cn.com/problems/longest-palindrome/)
498-
499-
```java
500-
// 思路：
501-
// 构成回文串的两种情况：
502-
// 1.字符出现次数为双数的组合
503-
// 2.字符出现次数为双数的组合+一个字符
504-
505-
public int longestPalindrome(String s) {
506-
if(s.length()==1){
507-
return 1;
508-
}
509-
//统计成对出现的字符次数
510-
int cnt=0;
511-
//set 不会存储相同的字符
512-
Set<Character> set=new HashSet<>();
513-
514-
for(int i=0;i<s.length();i++){
515-
char c=s.charAt(i);
516-
if(!set.contains(c)){
517-
set.add(c);
518-
}else{ //说明 c 成对出现
519-
set.remove((Character) c);
520-
cnt++;
521-
}
522-
}
523-
524-
return (set.isEmpty()?(2*cnt):(2*cnt+1));
525-
}
526-
```
527-
528-
529-
530-
## 14、最长回文子序列
531-
532-
[最长回文子序列](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)
533-
534-
```java
535-
public int longestPalindromeSubseq(String s) {
536-
int n=s.length();
537-
if(n<=1){
538-
return n;
539-
}
540-
541-
//dp[i][j] 表示 s[i,j] 之间最长的回文子序列的长度
542-
int[][] dp=new int[n][n];
543-
for(int i=n-1;i>=0;i--){
544-
dp[i][i]=1; // TODO:只有一个元素，最长回文子序列的长度为 1
545-
for(int j=i+1;j<n;j++){ // j 从 j+1 开始
546-
if(s.charAt(i)==s.charAt(j)){
547-
dp[i][j]=dp[i+1][j-1]+2;
548-
}else{
549-
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
550-
}
551-
}
552-
}
553-
return dp[0][n-1];
554-
}
555-
```
556-
557-
558-
559-
## 15、最长回文子串
560-
561-
[最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/)
562-
563-
```java
564-
public String longestPalindrome(String s) {
565-
int n=s.length();
566-
if(n==0){
567-
return "";
568-
}
569-
int maxN=0; //最长回文子串的最大长度
570-
int startIndex=0;//最长回文子串的开始位置
571-
int endIndex=0;//最长回文子串的结束位置
572-
573-
//处理 aba 这种情况，以i为中心向两边扩展
574-
for(int i=1;i<n;i++){ // 注意: 这里 i 从 1 开始
575-
int l=i-1;
576-
int r=i+1;
577-
while((l>=0 && r<n) && s.charAt(l)==s.charAt(r)){
578-
int len=r-l+1; //当前回文子串的长度
579-
if(len>maxN){ //更新最长回文子串
580-
maxN=len;
581-
startIndex=l;
582-
endIndex=r;
583-
}
584-
//从中心向两边扩展，所以这里需要 l-- 并且 r++
585-
l--;
586-
r++;
587-
}
588-
}
589-
590-
//处理 baab 这种情况，以 i,i+1 为中心向两边扩展
591-
for(int i=0;i<n;i++){
592-
int l=i;
593-
int r=i+1;
594-
while((l>=0 && r<n) && s.charAt(l)==s.charAt(r)){
595-
int len=r-l+1;
596-
if(len>maxN){
597-
maxN=len;
598-
startIndex=l;
599-
endIndex=r;
600-
}
601-
l--;
602-
r++;
603-
}
604-
}
605-
606-
//注意 substting 左闭右开的特性。
607-
return s.substring(startIndex,endIndex+1);
608-
}
609-
```
610-
611-
612-
613-
# 补充
614-
615-
[13 道题搞定 BAT 面试——字符串](https://www.weiweiblog.cn/13string/)

‎docs/AimForOffer/数据结构相关/3_链表.md‎

Lines changed: 0 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -529,37 +529,5 @@ public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
529529

530530

531531

532-
## 13、移除链表元素
533-
534-
[移除链表元素](https://leetcode-cn.com/problems/remove-linked-list-elements/)
535-
536-
```java
537-
// 思路：创建虚拟头结点
538-
539-
540-
```
541-
542-
543-
544-
## 14、两两交换链表中的节点
545-
546-
[两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
547-
548-
```java
549-
550-
```
551-
552-
553-
554-
## 15、删除链表中的节点
555-
556-
[删除链表中的节点](https://leetcode-cn.com/problems/delete-node-in-a-linked-list/)
557-
558-
```java
559-
560-
```
561-
562-
563-
564532

565533

0 commit comments

Comments
 (0)