Skip to content

Commit 69583c4

Browse files
DreamCatsDreamCats
committed
📝 update alg lc
1 parent 0345f2d commit 69583c4

4 files changed

Lines changed: 345 additions & 1 deletion

File tree

‎Java/alg/README.md‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -95,4 +95,13 @@
9595
- [914.卡牌分组](lc/914.卡牌分组.md)
9696
- [1013.将数组分成和相等的三个部分](lc/1013.将数组分成和相等的三个部分.md)
9797
- [1071.字符串的最大公因子](lc/1071.字符串的最大公因子.md)
98-
- [1103.分糖果2](lc/1103.分糖果2.md)
98+
- [1103.分糖果2](lc/1103.分糖果2.md)
99+
100+
## Medium
101+
- [2.两数相加](lc/2.两数相加.md)
102+
- [3.无重复字符的最长子串](lc/3.无重复字符的最长子串.md)
103+
- [5.最长回文子串](lc/5.最长回文子串.md)
104+
105+
## 笔试
106+
107+
<!-- - [1.分苹果](we/1.分苹果.md) -->

‎Java/alg/lc/2.两数相加.md‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
# 1.两数之和
2+
3+
[url](https://leetcode-cn.com/problems/add-two-numbers/)
4+
5+
## 题目
6+
7+
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
8+
9+
请你将两个数相加，并以相同形式返回一个表示和的链表。
10+
11+
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
12+
13+
![lc-addtwonumber1-snb8Qb](http://imgs.dreamcat.ink/uPic/lc-addtwonumber1-snb8Qb.jpeg)
14+
15+
```
16+
输入：l1 = [2,4,3], l2 = [5,6,4]
17+
输出：[7,0,8]
18+
解释：342 + 465 = 807.
19+
输入：l1 = [0], l2 = [0]
20+
输出：[0]
21+
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
22+
输出：[8,9,9,9,0,0,0,1]
23+
```
24+
25+
## 方法
26+
27+
28+
## code
29+
30+
### js
31+
32+
```js
33+
let addTwoNumbers = (l1, l2) => {
34+
if (l1 === null)
35+
return l2;
36+
if (l2 === null)
37+
return l1;
38+
let p1 = l1, p2 = l2;
39+
let l3 = new ListNode(0);
40+
let p3 = l3, carry = 0;
41+
while (p1 !== null || p2 !== null) {
42+
let a = p1 === null ? 0 : p1.val;
43+
let b = p2 === null ? 0 : p2.val;
44+
p3.next = new ListNode((a + b + carry) % 10);
45+
carry = Math.floor((a + b + carry) / 10);
46+
p1 = p1 === null ? null : p1.next;
47+
p2 = p2 === null ? null : p2.next;
48+
p3 = p3.next;
49+
}
50+
p3.next = carry === 1 ? new ListNode(1) : null;
51+
return l3.next;
52+
};
53+
```
54+
55+
### go
56+
57+
```go
58+
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
59+
if l1 == nil {
60+
return l2
61+
}
62+
if l2 == nil {
63+
return l1
64+
}
65+
p1, p2 := l1, l2
66+
l3 := &ListNode{Val: 0}
67+
p3 := l3
68+
carry := 0
69+
for p1 != nil || p2 != nil {
70+
a := 0
71+
b := 0
72+
if p1 != nil {
73+
a = p1.Val
74+
p1 = p1.Next
75+
}
76+
if p2 != nil {
77+
b = p2.Val
78+
p2 = p2.Next
79+
}
80+
p3.Next = &ListNode{Val: (a + b +carry) % 10}
81+
carry = (a + b + carry) / 10
82+
p3 = p3.Next
83+
}
84+
if carry == 1 {
85+
p3.Next = &ListNode{Val: 1}
86+
}
87+
return l3.Next
88+
}
89+
```
90+
91+
### java
92+
93+
```java
94+
class Solution {
95+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
96+
if (l1 == null)
97+
return l2;
98+
if (l2 == null)
99+
return l1;
100+
ListNode p1 = l1, p2 = l2;
101+
ListNode l3 = new ListNode(0);
102+
ListNode p3 = l3;
103+
int carry = 0;
104+
while (p1 != null || p2 != null) {
105+
int a = p1 == null ? 0 : p1.val;
106+
int b = p2 == null ? 0 : p2.val;
107+
p3.next = new ListNode((a + b + carry) % 10);
108+
carry = (a + b + carry) / 10;
109+
p1 = p1 == null ? null : p1.next;
110+
p2 = p2 == null ? null : p2.next;
111+
p3 = p3.next;
112+
}
113+
p3.next = carry == 1 ? new ListNode(1) : null;
114+
return l3.next;
115+
}
116+
}
117+
```
118+

‎Java/alg/lc/3.无重复字符的最长子串.md‎

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
# 3. 无重复字符的最长子串
2+
3+
[url](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
4+
5+
## 题目
6+
7+
8+
```
9+
输入: s = "abcabcbb"
10+
输出: 3
11+
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
12+
输入: s = "bbbbb"
13+
输出: 1
14+
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
15+
输入: s = "pwwkew"
16+
输出: 3
17+
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
18+
  请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
19+
```
20+
21+
## 方法
22+
23+
24+
## code
25+
26+
### js
27+
28+
```js
29+
let lengthOfLongestSubstring = s => {
30+
if (s === null || s.length === 0)
31+
return -1;
32+
let n = s.length, max = 0;
33+
let map = new Map();
34+
for (let i = 0, j = 0; j < n; j++) {
35+
let c = s[j];
36+
if (map.has(c)) {
37+
i = Math.max(i, map.get(c));
38+
}
39+
max = Math.max(max, j - i + 1);
40+
map.set(c, j + 1);
41+
}
42+
return max;
43+
};
44+
```
45+
46+
### go
47+
48+
```go
49+
func lengthOfLongestSubstring(s string) int {
50+
if len(s) == 0 {
51+
return -1
52+
}
53+
n := len(s)
54+
max := 0
55+
m := make(map[byte]int, 0)
56+
for i, j := 0, 0; j < n; j++ {
57+
c := s[j]
58+
if v, ok := m[c]; ok {
59+
i = max6(i, v)
60+
}
61+
max = max6(max, j - i + 1)
62+
m[c] = j + 1
63+
}
64+
return max
65+
}
66+
func max6(a int, b int) int {
67+
if a < b {
68+
return b
69+
} else {
70+
return a
71+
}
72+
}
73+
```
74+
75+
### java
76+
77+
```java
78+
class Solution {
79+
public int lengthOfLongestSubstring(String s) {
80+
if (s == null || s.length() == 0)
81+
return -1;
82+
int n = s.length();
83+
int max = 0;
84+
Map<Character, Integer> map = new HashMap<>();
85+
for (int i = 0, j = 0; j < n; j++){
86+
char c = s.charAt(j);
87+
if (map.containsKey(c)){
88+
i = Math.max(i, map.get(c));
89+
}
90+
max = Math.max(max, j - i + 1);
91+
map.put(c, j + 1);
92+
}
93+
return max;
94+
}
95+
}
96+
```
97+

‎Java/alg/lc/5.最长回文子串.md‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
# 5. 最长回文子串
2+
3+
[url](https://leetcode-cn.com/problems/longest-palindromic-substring/)
4+
5+
## 题目
6+
7+
给你一个字符串 s，找到 s 中最长的回文子串。
8+
9+
```
10+
输入：s = "babad"
11+
输出："bab"
12+
解释："aba" 同样是符合题意的答案。
13+
输入：s = "cbbd"
14+
输出："bb"
15+
输入：s = "a"
16+
输出："a"
17+
输入：s = "ac"
18+
输出："a"
19+
```
20+
21+
## 方法
22+
23+
24+
## code
25+
26+
### js
27+
28+
```js
29+
let longestPalindrome = s => {
30+
let expand = (s, l, r) => {
31+
while (l >= 0 && r < s.length && s[l] === s[r]) {
32+
l--;
33+
r++;
34+
}
35+
return r - l - 1;
36+
};
37+
if (s === null || s.length === 0)
38+
return s;
39+
let start = 0, end = 0, len1 = 0, len2 = 0, maxLen = 0;
40+
for (let i = 0; i < s.length; i ++) {
41+
len1 = expand(s, i - 1, i + 1);
42+
len2 = expand(s, i, i + 1);
43+
maxLen = Math.max(len1, len2);
44+
if (maxLen > (end - start)) {
45+
start = i - Math.floor((maxLen - 1) / 2);
46+
end = i + Math.floor(maxLen / 2);
47+
}
48+
}
49+
return s.substring(start, end + 1);
50+
};
51+
```
52+
53+
### go
54+
55+
```go
56+
func longestPalindrome2(s string) string {
57+
if len(s) == 0 {
58+
return s
59+
}
60+
start, end := 0, 0
61+
len1, len2 := 0, 0
62+
maxLen := 0
63+
for i := 0; i < len(s); i++ {
64+
len1 = expand(s, i - 1, i + 1)
65+
len2 = expand(s, i, i + 1)
66+
maxLen = max7(len1, len2)
67+
if maxLen > (end - start) {
68+
start = i - (maxLen - 1) / 2
69+
end = i + maxLen / 2
70+
}
71+
}
72+
return s[start : end + 1]
73+
}
74+
func expand(s string, l int, r int) int {
75+
for l >= 0 && r < len(s) && s[l] == s[r] {
76+
l--
77+
r++
78+
}
79+
return r - l - 1
80+
}
81+
func max7(a int, b int) int {
82+
if a < b {
83+
return b
84+
} else {
85+
return a
86+
}
87+
}
88+
```
89+
90+
### java
91+
92+
```java
93+
class Solution {
94+
public String longestPalindrome(String s) {
95+
if (s == null || s.length() == 0)
96+
return s;
97+
int start = 0, end = 0;
98+
int len1 = 0, len2 = 0;
99+
int maxLen = 0;
100+
for (int i = 0; i < s.length(); i++) {
101+
len1 = expand(s, i - 1, i + 1);
102+
len2 = expand(s, i, i + 1);
103+
maxLen = Math.max(len1, len2);
104+
if (maxLen > (end - start)) {
105+
start = i - (maxLen - 1) / 2;
106+
end = i + maxLen / 2;
107+
}
108+
}
109+
return s.substring(start, end + 1);
110+
}
111+
public int expand(String s, int l, int r) {
112+
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
113+
l--;
114+
r++;
115+
}
116+
return r - l -1;
117+
}
118+
}
119+
```
120+

0 commit comments

Comments
 (0)