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

Commit99973f4

Browse files
author
zhenyu zhang
committed
update LeetCode 15、58、66、462、662 leave 71 not solved
1 parentc0b04da commit99973f4

File tree

6 files changed

+317
-0
lines changed

6 files changed

+317
-0
lines changed

‎src/com/hadley/_015.java

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.07.08
5+
15、3Sum
6+
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
7+
8+
Note:
9+
10+
The solution set must not contain duplicate triplets.
11+
12+
Example:
13+
14+
Given array nums = [-1, 0, 1, 2, -1, -4],
15+
16+
A solution set is:
17+
[
18+
[-1, 0, 1],
19+
[-1, -1, 2]
20+
]
21+
*/
22+
23+
importjava.util.*;
24+
25+
publicclass_015 {
26+
//重复解决不了
27+
publicList<List<Integer>>threeSum(int[]nums) {
28+
List<List<Integer>>res =newArrayList<>();
29+
30+
if(nums.length <3){
31+
returnres;
32+
}
33+
34+
intbit =0;
35+
for(inti =0;i <nums.length;i ++){
36+
if(nums[i] !=0){
37+
bit =1;
38+
}
39+
}
40+
41+
if(bit ==0){
42+
List<Integer>curList =newArrayList<>();
43+
curList.add(0);
44+
curList.add(0);
45+
curList.add(0);
46+
res.add(curList);
47+
returnres;
48+
}
49+
50+
Arrays.sort(nums);
51+
for(inti =0;i <nums.length;i++){
52+
intfirst =nums[i];//对之后的所有数进行2sum操作 2sum = total - first
53+
HashMap<Integer,Integer>map =newHashMap<>();
54+
for(intj =i +1;j <nums.length;j++){
55+
inttemp =nums[j];
56+
if(map.containsKey(temp)){
57+
List<Integer>curList =newArrayList<>(3);
58+
curList.add(first);
59+
curList.add(temp);
60+
curList.add(-first-temp);
61+
res.add(curList);
62+
}
63+
map.put(-first-temp,1);
64+
}
65+
66+
}
67+
returnres;
68+
}
69+
70+
//link:https://www.cnblogs.com/stevencooks/p/4472837.html
71+
publicList<List<Integer>>threeSum1(int[]nums) {
72+
List<List<Integer>>result =newArrayList<List<Integer>>();
73+
intlen =nums.length;
74+
if (len <3) {
75+
returnresult;
76+
}
77+
78+
Arrays.sort(nums);
79+
80+
// for all number that can be the 1st number of triplet
81+
for (inti =0;i <len -1;i++) {
82+
intfirstNumber =nums[i];
83+
84+
// skip all duplicated first number
85+
if (i ==0 ||firstNumber !=nums[i -1]) {
86+
87+
intleftIndex =i +1;
88+
intrightIndex =len -1;
89+
inttwoSumTarget =0 -firstNumber;
90+
91+
// try to find two numbers that sum up to twoSumTarget
92+
while (leftIndex <rightIndex) {
93+
inttwoSum =nums[leftIndex] +nums[rightIndex];
94+
if (twoSum ==twoSumTarget) {
95+
// one valid triplet found!!
96+
result.add(Arrays.asList(firstNumber,nums[leftIndex],nums[rightIndex]));
97+
// skip duplicated nums[leftIndex]
98+
while (leftIndex <rightIndex &&nums[leftIndex] ==nums[leftIndex +1]) {
99+
leftIndex++;
100+
}
101+
// skip duplicated nums[rightIndex]
102+
while (leftIndex <rightIndex &&nums[rightIndex] ==nums[rightIndex -1]) {
103+
rightIndex--;
104+
}
105+
// move to next non-duplicates
106+
leftIndex++;
107+
rightIndex--;
108+
}elseif (twoSum <twoSumTarget) {
109+
// move left towards right to
110+
// make twoSum larger to get closer to twoSumTarget
111+
leftIndex++;
112+
}else {
113+
rightIndex--;
114+
}
115+
}
116+
117+
}
118+
}
119+
120+
returnresult;
121+
}
122+
123+
}

‎src/com/hadley/_058.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.07.10
5+
58、Length of Last Word
6+
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.
7+
8+
If the last word does not exist, return 0.
9+
10+
Note: A word is defined as a maximal substring consisting of non-space characters only.
11+
12+
Example:
13+
14+
Input: "Hello World"
15+
Output: 5
16+
*/
17+
18+
publicclass_058 {
19+
20+
publicintlengthOfLastWord(Strings) {
21+
String[]temp =s.split(" ");
22+
if(temp.length ==0 ||temp ==null)return0;
23+
returntemp[temp.length -1].length();
24+
}
25+
26+
//more efficient solution
27+
publicintlengthOfLastWord1(Strings){
28+
s =s.trim();
29+
intlastIndex =s.lastIndexOf(' ') +1;
30+
returns.length() -lastIndex;
31+
}
32+
33+
}

‎src/com/hadley/_066.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.07.06
5+
66、Plus One
6+
Given a non-empty array of digits representing a non-negative integer, plus one to the integer.
7+
8+
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.
9+
10+
You may assume the integer does not contain any leading zero, except the number 0 itself.
11+
12+
Example 1:
13+
14+
Input: [1,2,3]
15+
Output: [1,2,4]
16+
Explanation: The array represents the integer 123.
17+
Example 2:
18+
19+
Input: [4,3,2,1]
20+
Output: [4,3,2,2]
21+
Explanation: The array represents the integer 4321.
22+
*/
23+
24+
publicclass_066 {
25+
26+
publicint[]plusOne(int[]digits) {
27+
28+
inttemp =0;
29+
30+
digits[digits.length -1] =digits[digits.length -1] +1;
31+
for(inti =digits.length -1;i >=0;i--){
32+
if(temp ==1){
33+
digits[i] =digits[i] +1;
34+
}
35+
36+
if(digits[i] ==10){
37+
digits[i] =0;
38+
temp =1;
39+
}else{
40+
temp =0;
41+
}
42+
43+
}
44+
45+
if(temp ==1){
46+
int[]res =newint[digits.length +1];
47+
res[0] =1;
48+
for(inti =0;i <digits.length;i++){
49+
res[i+1] =0;
50+
}
51+
returnres;
52+
}
53+
54+
returndigits;
55+
}
56+
}

‎src/com/hadley/_071.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.07.06
5+
71、Simplify Path
6+
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
7+
8+
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level.
9+
10+
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
11+
12+
13+
14+
Example 1:
15+
16+
Input: "/home/"
17+
Output: "/home"
18+
Explanation: Note that there is no trailing slash after the last directory name.
19+
Example 2:
20+
21+
Input: "/../"
22+
Output: "/"
23+
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
24+
Example 3:
25+
26+
Input: "/home//foo/"
27+
Output: "/home/foo"
28+
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
29+
Example 4:
30+
31+
Input: "/a/./b/../../c/"
32+
Output: "/c"
33+
Example 5:
34+
35+
Input: "/a/../../b/../c//.//"
36+
Output: "/c"
37+
Example 6:
38+
39+
Input: "/a//b////c/d//././/.."
40+
Output: "/a/b/c"
41+
*/
42+
43+
publicclass_071 {
44+
}

‎src/com/hadley/_463.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
packagecom.hadley;
2+
3+
/*
4+
2020.07.07
5+
463、Island Perimeter
6+
7+
*/
8+
publicclass_463 {
9+
//对于每个岛屿格子先默认加上四条边，然后检查其左面和上面是否有岛屿格子，有的话分别减去两条边
10+
publicintislandPerimeter(int[][]grid) {
11+
intres =0;
12+
if(grid.length ==0 ||grid[0].length ==0)return0;
13+
intm =grid.length;
14+
intn =grid[0].length;
15+
16+
for(inti =0;i <m;i++){
17+
for(intj =0;j <n;j++){
18+
if(grid[i][j] ==0)continue;
19+
res +=4;
20+
if(i >0 &&grid[i-1][j] ==1)res -=2;
21+
if(j >0 &&grid[i][j-1] ==1)res -=2;
22+
}
23+
24+
}
25+
returnres;
26+
}
27+
}

‎src/com/hadley/_662.java

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packagecom.hadley;
2+
3+
importjava.util.HashMap;
4+
importjava.util.Map;
5+
6+
/*
7+
2020.07.09
8+
9+
*/
10+
publicclass_662 {
11+
12+
publicclassTreeNode {
13+
intval;
14+
TreeNodeleft;
15+
TreeNoderight;
16+
TreeNode(intx) {val =x; }
17+
18+
}
19+
intans;
20+
Map<Integer,Integer>left;
21+
publicintwidthOfBinaryTree(TreeNoderoot) {
22+
ans =0;
23+
left =newHashMap();
24+
dfs(root,0,0);
25+
returnans;
26+
}
27+
publicvoiddfs(TreeNoderoot,intdepth,intpos) {
28+
if (root ==null)return;
29+
left.computeIfAbsent(depth,x->pos);
30+
ans =Math.max(ans,pos -left.get(depth) +1);
31+
dfs(root.left,depth +1,2 *pos);
32+
dfs(root.right,depth +1,2 *pos +1);
33+
}
34+
}

0 commit comments

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