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

Commitfc90108

Browse files
Merge branch 'neetcode-gh:main' into main
2 parents02ebbb1 +b3d096b commitfc90108

11 files changed

+278
-20
lines changed

‎README.md

Lines changed: 3 additions & 3 deletions
Large diffs are not rendered by default.
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
publicclassSolution
2+
{
3+
publicboolCheckSubarraySum(int[]nums,intk)
4+
{
5+
varremainder=newDictionary<int,int>();
6+
remainder.Add(0,-1);
7+
vartotal=0;
8+
for(vari=0;i<nums.Length;i++)
9+
{
10+
total+=nums[i];
11+
varr=total%k;
12+
if(!remainder.ContainsKey(r))
13+
remainder.Add(r,i);
14+
elseif(i-remainder[r]>1)
15+
returntrue;
16+
}
17+
returnfalse;
18+
}
19+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
classSolution {
2+
publicNodeconnect(Noderoot) {
3+
Nodecurrent =root;
4+
Nodenext =root ==null ?null :root.left;
5+
6+
while (current !=null &&next !=null) {
7+
current.left.next =current.right;
8+
9+
if (current.next !=null) {
10+
current.right.next =current.next.left;
11+
}
12+
13+
current =current.next;
14+
15+
if (current ==null) {
16+
current =next;
17+
next =current.left;
18+
}
19+
}
20+
21+
returnroot;
22+
}
23+
}
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
publicclassSolution {
2+
publicintnumberOfArithmeticSlices(int[]nums) {
3+
intres =0;
4+
intn =nums.length;
5+
6+
Map<Long,Integer>[]dp =newHashMap[n];
7+
for (inti =0;i <n;i++) {
8+
dp[i] =newHashMap<>();
9+
}
10+
11+
for (inti =0;i <n;i++) {
12+
for (intj =0;j <i;j++) {
13+
longdiff = (long)nums[i] - (long)nums[j];
14+
dp[i].put(diff,dp[i].getOrDefault(diff,0) +1 +dp[j].getOrDefault(diff,0));
15+
res +=dp[j].getOrDefault(diff,0);
16+
}
17+
}
18+
19+
returnres;
20+
}
21+
}

‎java/0938-range-sum-of-bst.java

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
/*--------------------------
2+
Time Complexity: O(n)
3+
Space Complexity: O(n)
4+
---------------------------*/
5+
classSolution {
6+
publicintrangeSumBST(TreeNoderoot,intlow,inthigh) {
7+
if(root ==null)
8+
return0;
9+
if(root.val >high)
10+
returnrangeSumBST(root.left,low,high);
11+
if(root.val <low)
12+
returnrangeSumBST(root.right,low,high);
13+
returnroot.val +rangeSumBST(root.left,low,high) +rangeSumBST(root.right,low,high);
14+
}
15+
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
classSolution {
2+
publicStringremoveDuplicates(Strings,intk) {
3+
Stack<Pair<Character,Integer>>stack =newStack<>();
4+
char[]ss =s.toCharArray();
5+
6+
for (charcurrent :ss) {
7+
if (!stack.isEmpty() &&stack.peek().getKey() ==current) {
8+
inttopCharCount =stack.pop().getValue();
9+
stack.push(newPair<>(current,topCharCount +1));
10+
}else {
11+
stack.push(newPair<>(current,1));
12+
}
13+
14+
if (stack.peek().getValue() ==k) {
15+
stack.pop();
16+
}
17+
}
18+
19+
StringBuilderresult =newStringBuilder();
20+
21+
while (!stack.isEmpty()) {
22+
Pair<Character,Integer>poppedPair =stack.pop();
23+
for (inti =0;i <poppedPair.getValue();i++) {
24+
result.append(poppedPair.getKey());
25+
}
26+
}
27+
28+
returnresult.reverse().toString();
29+
}
30+
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
classSolution {
2+
int[][]intervals;
3+
Integer[]cache;
4+
5+
publicintjobScheduling(int[]startTime,int[]endTime,int[]profit) {
6+
intn =startTime.length;
7+
intervals =newint[n][3];
8+
cache =newInteger[n];
9+
10+
for (inti =0;i <n;i++) {
11+
intervals[i] =newint[]{startTime[i],endTime[i],profit[i]};
12+
}
13+
14+
Arrays.sort(intervals, (a,b) ->Integer.compare(a[0],b[0]));
15+
16+
returndfs(0);
17+
}
18+
19+
privateintdfs(inti) {
20+
if (i ==intervals.length) {
21+
return0;
22+
}
23+
24+
if (cache[i] !=null) {
25+
returncache[i];
26+
}
27+
28+
// don't include
29+
intres =dfs(i +1);
30+
31+
// include
32+
intj =binarySearch(intervals,i,intervals[i][1]);
33+
cache[i] =res =Math.max(res,intervals[i][2] +dfs(j));
34+
35+
returnres;
36+
}
37+
38+
privateintbinarySearch(int[][]intervals,intstart,inttarget) {
39+
intleft =start +1;
40+
intright =intervals.length -1;
41+
42+
while (left <=right) {
43+
intmid =left + (right -left) /2;
44+
45+
if (intervals[mid][0] <target) {
46+
left =mid +1;
47+
}else {
48+
right =mid -1;
49+
}
50+
}
51+
52+
returnleft;
53+
}
54+
}

‎kotlin/0155-min-stack.kt

Lines changed: 16 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,26 @@
1-
importkotlin.math.min
2-
31
classMinStack() {
4-
privateclassNode(var `val`:Int,varmin:Int,varnext:Node?)
5-
6-
privatevar head:Node?=null
7-
8-
funpush(x:Int) {
9-
if(head==null) head=Node(x,x,null)else head=Node(x, min(x,head?.min!!),head)
2+
privateval stack=Stack<Int>()
3+
privateval minStack=Stack<Int>()
4+
5+
funpush(`val`:Int) {
6+
val currentMin=if (minStack.isNotEmpty()) minStack.peek()elseInteger.MAX_VALUE
7+
val newMin= minOf(currentMin, `val`)
8+
stack.push(`val`)
9+
minStack.push(newMin)
1010
}
1111

1212
funpop() {
13-
head= head?.next
14-
13+
if (stack.isNotEmpty()) {
14+
stack.pop()
15+
minStack.pop()
16+
}
1517
}
1618

17-
funtop():Int? {
18-
return head?.`val`
19-
19+
funtop():Int {
20+
return stack.peek()
2021
}
2122

22-
fungetMin():Int? {
23-
return head?.min
24-
23+
fungetMin():Int {
24+
return minStack.peek()
2525
}
26-
2726
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
// dp
2+
classSolution {
3+
funnumberOfArithmeticSlices(nums:IntArray):Int {
4+
var res=0
5+
val dp=HashMap<Pair<Int,Long>,Int>()
6+
7+
for (iin0 until nums.size) {
8+
for (jin0 until i) {
9+
val d= nums[i].toLong()- nums[j]
10+
dp[i to d]= (dp[i to d]?:0)+1+ (dp[j to d]?:0)
11+
res+= (dp[j to d]?:0)
12+
}
13+
}
14+
15+
return res
16+
}
17+
}
18+
19+
// recursion + memoization
20+
classSolution {
21+
funnumberOfArithmeticSlices(nums:IntArray):Int {
22+
val dp=HashMap<String,Int>()
23+
val count=HashMap<Long,MutableList<Int>>()
24+
25+
nums.forEachIndexed { i, n->
26+
count.getOrPut(n.toLong()) {mutableListOf() }.apply { add(i) }
27+
}
28+
29+
fundfs(i:Int,d:Long,s:Int):Int {
30+
dp["$i:$d:$s"]?.let {return it }
31+
32+
var res=if (s>2)1else0
33+
count[nums[i]+ d]?.forEach { j->
34+
if (j> i) res+= dfs(j, d, s+1)
35+
}
36+
37+
dp["$i:$d:$s"]= res
38+
return res
39+
}
40+
41+
var res=0
42+
for (iin0 until nums.size) {
43+
for (jin i+1 until nums.size)
44+
res+= dfs(j, nums[j].toLong()- nums[i],2)
45+
}
46+
47+
return res
48+
}
49+
}

‎kotlin/0938-range-sum-of-bst.kt

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
classSolution {
2+
funrangeSumBST(root:TreeNode?,low:Int,high:Int):Int {
3+
root?:return0
4+
5+
returnif (root.`val`> high) rangeSumBST(root.left, low, high)
6+
elseif (root.`val`< low) rangeSumBST(root.right, low, high)
7+
else root.`val`+
8+
rangeSumBST(root.left, low, high)+
9+
rangeSumBST(root.right, low, high)
10+
}
11+
}
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
classSolution {
2+
funjobScheduling(s:IntArray,e:IntArray,p:IntArray):Int {
3+
val dp=IntArray (s.size) {-1 }
4+
5+
val intervals= s.mapIndexed { i, v->
6+
intArrayOf(v, e[i], p[i])
7+
}.sortedWith(compareBy({ it[0] }, { it[1] }))
8+
9+
fundfs(i:Int):Int {
10+
if (i== intervals.size|| i==-1)return0
11+
if (dp[i]!=-1)return dp[i]
12+
13+
// bisect
14+
var l= i
15+
var r= intervals.lastIndex
16+
var res=-1
17+
while (l<= r) {
18+
val m= (r+ l)/2
19+
if (intervals[m][0]>= intervals[i][1]) {
20+
res= m
21+
r= m-1
22+
}else {
23+
l= m+1
24+
}
25+
}
26+
27+
dp[i]= maxOf(
28+
dfs(i+1),// dont include
29+
intervals[i][2]+ dfs(res)//include
30+
)
31+
32+
return dp[i]
33+
}
34+
35+
return dfs(0)
36+
}
37+
}

0 commit comments

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