Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcfcb131

Browse files
author
haotf
committed
feat:去除重复字母
1 parent6003d88 commitcfcb131

File tree

3 files changed

+122
-4
lines changed

3 files changed

+122
-4
lines changed

‎16.最接近的三数之和.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
importjava.util.Arrays;
2+
3+
/*
4+
* @lc app=leetcode.cn id=16 lang=java
5+
*
6+
* [16] 最接近的三数之和
7+
*/
8+
9+
// @lc code=start
10+
classSolution {
11+
publicintthreeSumClosest(int[]nums,inttarget) {
12+
if (nums.length <3) {
13+
return0;
14+
}
15+
// 别忘了要先排序数组
16+
Arrays.sort(nums);
17+
// 记录三数之和与目标值的偏差
18+
intdelta =Integer.MAX_VALUE;
19+
for (inti =0;i <nums.length -2;i++) {
20+
// 固定 nums[i] 为三数之和中的第一个数，
21+
// 然后对 nums[i+1..] 搜索接近 target - nums[i] 的两数之和
22+
intsum =nums[i] +twoSumClosest(nums,i +1,target -nums[i]);
23+
if (Math.abs(delta) >Math.abs(target -sum)) {
24+
delta =target -sum;
25+
}
26+
}
27+
returntarget -delta;
28+
}
29+
30+
// 在 nums[start..] 搜索最接近 target 的两数之和
31+
inttwoSumClosest(int[]nums,intstart,inttarget) {
32+
intlo =start,hi =nums.length -1;
33+
// 记录两数之和与目标值的偏差
34+
intdelta =Integer.MAX_VALUE;
35+
while (lo <hi) {
36+
intsum =nums[lo] +nums[hi];
37+
if (Math.abs(delta) >Math.abs(target -sum)) {
38+
delta =target -sum;
39+
}
40+
if (sum <target) {
41+
lo++;
42+
}else {
43+
hi--;
44+
}
45+
}
46+
returntarget -delta;
47+
}
48+
}
49+
// @lc code=end

‎316.去除重复字母.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
importjava.util.ArrayDeque;
2+
importjava.util.Deque;
3+
importjava.util.HashMap;
4+
importjava.util.Map;
5+
6+
/*
7+
* @lc app=leetcode.cn id=316 lang=java
8+
*
9+
* [316] 去除重复字母
10+
*/
11+
12+
// @lc code=start
13+
classSolution {
14+
publicStringremoveDuplicateLetters(Strings) {
15+
16+
Map<Character,Integer>map =newHashMap<>();
17+
Map<Character,Boolean>visited =newHashMap<>();
18+
// 记录每个字符的个数
19+
for (inti =0;i <s.length();i++) {
20+
map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0) +1);
21+
visited.put(s.charAt(i),false);
22+
}
23+
24+
StringBuilderresult =newStringBuilder();
25+
Deque<Character>stack =newArrayDeque<>();
26+
for (inti =0;i <s.length();i++) {
27+
Characterc =s.charAt(i);
28+
if (visited.get(c)) {
29+
map.put(c,map.get(c) -1);
30+
continue;
31+
}
32+
while (stack.size() >0) {
33+
Characterpeek =stack.peek();
34+
if (peek >=c &&map.get(peek) >1) {
35+
visited.put(peek,false);
36+
stack.pop();
37+
map.put(peek,map.get(peek) -1);
38+
}else {
39+
break;
40+
}
41+
}
42+
stack.push(c);
43+
visited.put(c,true);
44+
}
45+
46+
while (!stack.isEmpty()) {
47+
result.append(stack.pop());
48+
}
49+
50+
returnresult.reverse().toString();
51+
}
52+
}
53+
// @lc code=end

‎98.验证二叉搜索树.java‎

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -8,12 +8,12 @@
88
/**
99
* Definition for a binary tree node.
1010
* public class TreeNode {
11-
*int val;
11+
*long val;
1212
* TreeNode left;
1313
* TreeNode right;
1414
* TreeNode() {}
15-
* TreeNode(int val) { this.val = val; }
16-
* TreeNode(int val, TreeNode left, TreeNode right) {
15+
* TreeNode(long val) { this.val = val; }
16+
* TreeNode(long val, TreeNode left, TreeNode right) {
1717
* this.val = val;
1818
* this.left = left;
1919
* this.right = right;
@@ -22,7 +22,9 @@
2222
*/
2323
classSolution {
2424
publicbooleanisValidBST(TreeNoderoot) {
25-
returnvalid(root,null,null);
25+
// return valid(root, null, null);
26+
long[]result =traverse(root);
27+
returnresult[0] ==1;
2628
}
2729

2830
privatebooleanvalid(TreeNoderoot,TreeNodemax,TreeNodemin) {
@@ -35,5 +37,19 @@ private boolean valid(TreeNode root, TreeNode max, TreeNode min) {
3537

3638
returnvalid(root.left,root,min) &&valid(root.right,max,root);
3739
}
40+
41+
privatelong[]traverse(TreeNoderoot) {
42+
if (root ==null)
43+
returnnewlong[] {1,Long.MAX_VALUE,Long.MIN_VALUE };
44+
45+
long[]left =traverse(root.left);
46+
long[]right =traverse(root.right);
47+
48+
if (left[0] ==0 ||right[0] ==0)
49+
returnnewlong[] {0 };
50+
if (root.val >left[2] &&root.val <right[1])
51+
returnnewlong[] {1,Math.min(left[1],root.val),Math.max(right[2],root.val) };
52+
returnnewlong[] {0 };
53+
}
3854
}
3955
// @lc code=end

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp