Skip to content

Commit f56ab35

Browse files
committed
Java
1 parent 6680f16 commit f56ab35

2 files changed

Lines changed: 70 additions & 66 deletions

File tree

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

Lines changed: 50 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -464,17 +464,14 @@ public String addStrings(String num1, String num2) {
464464
[实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/)
465465

466466
```java
467-
// 思路一:暴力解法
468-
// 按位置去匹配,如果不合适,就移到下一位
469-
470467
public int strStr(String haystack, String needle) {
471-
if(needle==null || needle.length()==0){
472-
return -1;
473-
}
474-
475468
int m=haystack.length();
476469
int n=needle.length();
477470

471+
if(n==0){ // needle 是空字符串,默认返回 0
472+
return 0;
473+
}
474+
478475
int i=0,j=0;
479476
int k=0;
480477
while(i<m && j<n){
@@ -486,62 +483,11 @@ public int strStr(String haystack, String needle) {
486483
i=++k;
487484
}
488485
}
489-
if(j==n){
486+
if(j==n){ //说明 needle 完全匹配
490487
return k;
491488
}
492-
493-
return -1;
494-
}
495-
```
496-
497-
498-
499-
```java
500-
// 思路二 :KMP 算法
501-
502-
public int strStr(String haystack, String needle) {
503-
if(needle==null || needle.length()==0){
504-
return 0;
505-
}
506-
int[] next=getNext(needle);
507-
int i=0,j=0;
508-
while(i<haystack.length() && j<needle.length()){
509-
if(j==-1 || haystack.charAt(i)==needle.charAt(j)){
510-
i++;
511-
j++;
512-
}else{
513-
j=next[j];
514-
}
515-
}
516-
//说明模板串是待匹配串的子串
517-
if(j==needle.length()){
518-
//返回的是待匹配串的下标
519-
return i-needle.length();
520-
}
521489
return -1;
522490
}
523-
524-
// 获取 next 数组
525-
// next[j]的值(也就是t)表示,
526-
// 当P[j] != T[i]时,j 指针的下一步要移动到的位置(其中P是模式串,T是主串)。
527-
528-
private int[] getNext(String needle) {
529-
int[] next=new int[needle.length()];
530-
int j=0,t=-1;
531-
next[0]=-1;
532-
while (j<needle.length()-1){
533-
if(t==-1 || needle.charAt(j)==needle.charAt(t)){
534-
//needle.charAt(j): 表示后缀的单个字符
535-
//needle.charAt(t): 表示前缀的单个字符
536-
next[j+1]=t+1;
537-
t++;
538-
j++;
539-
}else{
540-
t=next[t];
541-
}
542-
}
543-
return next;
544-
}
545491
```
546492

547493

@@ -551,7 +497,32 @@ private int[] getNext(String needle) {
551497
[最长回文串](https://leetcode-cn.com/problems/longest-palindrome/)
552498

553499
```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+
}
554523

524+
return (set.isEmpty()?(2*cnt):(2*cnt+1));
525+
}
555526
```
556527

557528

@@ -561,7 +532,26 @@ private int[] getNext(String needle) {
561532
[最长回文子序列](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)
562533

563534
```java
564-
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+
}
565555
```
566556

567557

‎docs/Java_Concurrency/9_并发实践.md‎

Lines changed: 20 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -407,15 +407,21 @@ public class JoinExample {
407407
b.start();
408408
a.start();
409409
}
410-
}Copy to clipboardErrorCopied
410+
}
411+
411412
public static void main(String[] args) {
412413
JoinExample example = new JoinExample();
413414
example.test();
414-
}Copy to clipboardErrorCopied
415+
}
416+
```
417+
418+
```html
415419
A
416-
BCopy to clipboardErrorCopied
420+
B
417421
```
418422

423+
424+
419425
### wait() notify() notifyAll()
420426

421427
调用 wait() 使得线程等待某个条件满足,线程在等待时会被挂起,当其他线程的运行使得这个条件满足时,其它线程会调用 notify() 或者 notifyAll() 来唤醒挂起的线程。
@@ -442,7 +448,8 @@ public class WaitNotifyExample {
442448
}
443449
System.out.println("after");
444450
}
445-
}Copy to clipboardErrorCopied
451+
}
452+
446453
public static void main(String[] args) {
447454
ExecutorService executorService = Executors.newCachedThreadPool();
448455
WaitNotifyExample example = new WaitNotifyExample();
@@ -491,7 +498,8 @@ public class AwaitSignalExample {
491498
lock.unlock();
492499
}
493500
}
494-
}Copy to clipboardErrorCopied
501+
}
502+
495503
public static void main(String[] args) {
496504
ExecutorService executorService = Executors.newCachedThreadPool();
497505
AwaitSignalExample example = new AwaitSignalExample();
@@ -505,7 +513,9 @@ before
505513
after
506514
```
507515

508-
## 生产者和消费者
516+
517+
518+
## 实现生产者和消费者
509519

510520
### 1. wait() / notifyAll()
511521

@@ -609,6 +619,8 @@ public class ProducerConsumer {
609619
生产者 producer 退出 wait
610620
```
611621

622+
623+
612624
### 2. await() / sigalAll()
613625

614626
```java
@@ -718,6 +730,8 @@ public class ProducerConsumer {
718730
生产者 producer 退出 wait
719731
```
720732

733+
734+
721735
### 3. 阻塞队列
722736

723737
```java

0 commit comments

Comments
 (0)