Skip to content

Commit 90933d9

Browse files
feitengfeiteng
committed
1023
1 parent caecb29 commit 90933d9

9 files changed

Lines changed: 121 additions & 44 deletions

‎bin/NumArray.class‎

968 Bytes
Binary file not shown.

‎bin/NumMatrix.class‎

700 Bytes
Binary file not shown.

‎bin/Solution$1.class‎

0 Bytes
Binary file not shown.

‎bin/Solution$TrieNode.class‎

0 Bytes
Binary file not shown.

‎bin/Solution$vector.class‎

0 Bytes
Binary file not shown.

‎bin/Solution.class‎

196 Bytes
Binary file not shown.

‎src/NumArray.java‎

Lines changed: 67 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,55 +1,96 @@
11
class NumArray
22
{
3-
int[] vals;
3+
SegmentTree _root;
44
int n;
55

6-
public NumArray( int[] nums )
6+
class SegmentTree
77
{
8-
n = nums.length;
9-
vals = new int[2 * n];
10-
for ( int i = 0; i < n; i++ )
11-
vals[i + n] = nums[i];
12-
for ( int i = n - 1; i > 0; i-- )
8+
int _lBound = 0, _rBound = 0, _sum = 0;
9+
SegmentTree _left = null, _right = null;
10+
}
11+
12+
void printSegTree( SegmentTree t )
13+
{
14+
if ( t == null )
15+
return;
16+
if ( t._lBound == t._rBound )
17+
System.out.printf( " %d", t._sum );
18+
printSegTree( t._left );
19+
printSegTree( t._right );
20+
}
21+
22+
SegmentTree buidSegTree( int[] vals, int left, int right )
23+
{
24+
SegmentTree re = new SegmentTree();
25+
if ( left == right )
1326
{
14-
int a = i * 2 >= 2 * n ? 0 : vals[i * 2], b = i * 2 + 1 >= 2 * n ? 0 : vals[i * 2 + 1];
15-
vals[i] = a + b;
27+
re._lBound = re._rBound = left;
28+
re._sum = vals[left];
29+
return re;
1630
}
31+
if ( left > right )
32+
return null;
33+
int mid = ( left + right ) / 2;
34+
re._lBound = left;
35+
re._rBound = right;
36+
re._left = buidSegTree( vals, left, mid );
37+
re._right = buidSegTree( vals, mid + 1, right );
38+
if ( left == right )
39+
re._sum = vals[left];
40+
else
41+
re._sum = re._left._sum + re._right._sum;
42+
return re;
43+
}
1744

45+
public NumArray( int[] nums )
46+
{
47+
n = nums.length;
48+
_root = buidSegTree( nums, 0, n - 1 );
1849
}
1950

2051
public void update( int i, int val )
2152
{
22-
int oldval = vals[i + n];
23-
int k = i + n;
24-
while ( k > 0 )
53+
updateSegTree( i, val, _root );
54+
}
55+
56+
void updateSegTree( int i, int val, SegmentTree t )
57+
{
58+
if ( t._lBound == i && t._rBound == i )
2559
{
26-
vals[k] += val - oldval;
27-
k = k / 2;
60+
t._sum = val;
61+
return;
2862
}
63+
int m = ( t._lBound + t._rBound ) / 2;
64+
if ( i <= m )
65+
updateSegTree( i, val, t._left );
66+
else
67+
updateSegTree( i, val, t._right );
68+
t._sum = t._left._sum + t._right._sum;
2969
}
3070

3171
public int sumRange( int i, int j )
3272
{
33-
return sumHelper( 0, n - 1, i, j, 1 );
73+
return sumHelper( 0, n - 1, i, j, _root );
3474
}
3575

36-
int sumHelper( int L, int R, int i, int j, int p )
76+
int sumHelper( int L, int R, int i, int j, SegmentTree p )
3777
{
38-
if ( j < L || R < i || p >= 2 * n )
78+
if ( j < L || R < i )
3979
return 0;
4080
if ( i <= L && R <= j )
41-
return vals[p];
42-
int left = p * 2, right = p * 2 + 1, M = ( L + R ) / 2;
43-
return sumHelper( L, M, i, j, left ) +
44-
sumHelper( M + 1, R, i, j, right );
81+
return p._sum;
82+
int M = ( L + R ) / 2;
83+
return sumHelper( L, M, i, j, p._left ) +
84+
sumHelper( M + 1, R, i, j, p._right );
4585
}
4686

4787
public static void main( String[] args )
4888
{
4989

50-
String[] ops = { "NumArray", "sumRange", "update", "sumRange", "sumRange", "update", "update", "sumRange", "sumRange", "update", "update" };
51-
int[][] n = { {}, { 5, 6 }, { 9, 27 }, { 2, 3 }, { 6, 7 }, { 1, -82 }, { 3, -72 }, { 3, 7 },
52-
{ 1, 8 }, { 5, 13 }, { 4, -67 } };
90+
String[] ops = { "NumArray", "sumRange", "update", "sumRange", "sumRange",
91+
"update", "update", "sumRange", "sumRange", "update", "update" };
92+
int[][] n = { {}, { 5, 6 }, { 9, 27 }, { 2, 3 }, { 6, 7 },
93+
{ 1, -82 }, { 3, -72 }, { 3, 7 }, { 1, 8 }, { 5, 13 }, { 4, -67 } };
5394
int[] v = { -28, -39, 53, 65, 11, -56, -65, -39, -43, 97 };
5495
NumArray na = new NumArray( v );
5596
for ( int i = 1; i < ops.length; i++ )
@@ -61,6 +102,8 @@ public static void main( String[] args )
61102
na.update( n[i][0], n[i][1] );
62103
System.out.println( "null" );
63104
}
105+
na.printSegTree( na._root );
106+
System.out.println();
64107
}
65108
}
66109

‎src/NumMatrix.java‎

Lines changed: 49 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,45 +1,74 @@
1+
import java.util.Arrays;
12

2-
3-
4-
public class NumMatrix
3+
class NumMatrix
54
{
6-
int[][] sum;
5+
int[][] mat, rowSum;
6+
int m, n;
77

88
public NumMatrix( int[][] matrix )
99
{
10-
sum = new int[matrix.length + 1][matrix[0].length + 1];
11-
for ( int i = 0; i < matrix.length; i++ )
12-
for ( int j = 0; j < matrix[0].length; j++ )
13-
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
10+
if ( matrix == null || matrix.length == 0 || matrix[0].length == 0 )
11+
return;
12+
mat = matrix;
13+
m = matrix.length;
14+
n = matrix[0].length;
15+
rowSum = new int[m][n + 1];
16+
for ( int i = 0; i < m; i++ )
17+
{
18+
for ( int j = 0; j < n; j++ )
19+
{
20+
rowSum[i][j + 1] = rowSum[i][j] + mat[i][j];
21+
}
22+
}
1423

1524
}
1625

17-
public int sumRegion( int row1, int col1, int row2, int col2 )
26+
public void update( int row, int col, int val )
1827
{
19-
return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
28+
for ( int j = col; j < n; j++ )
29+
{
30+
rowSum[row][j + 1] += val - mat[row][col];
31+
}
32+
33+
mat[row][col] = val;
2034
}
2135

22-
void print()
36+
public int sumRegion( int row1, int col1, int row2, int col2 )
2337
{
24-
for ( int i = 0; i < sum.length; i++ )
38+
int re = 0;
39+
for ( int i = row1; i <= row2; i++ )
2540
{
26-
for ( int j = 0; j < sum[0].length; j++ )
27-
System.out.printf( "%d ", sum[i][j] );
28-
System.out.println();
41+
re += rowSum[i][col2 + 1] - rowSum[i][col1];
2942
}
30-
43+
return re;
3144
}
3245

3346
public static void main( String[] args )
3447
{
35-
int[][] n = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
36-
NumMatrix m = new NumMatrix( n );
37-
m.print();
48+
String[] ops = { "NumMatrix", "sumRegion", "update", "sumRegion" };
49+
50+
int[][] n = { {}, { 2, 1, 4, 3 }, { 3, 2, 2 }, { 2, 1, 4, 3 } },
51+
v = { { 3, 0, 1, 4, 2 }, { 5, 6, 3, 2, 1 }, { 1, 2, 0, 1, 5 }, { 4, 1, 0, 1, 7 }, { 1, 0, 3, 0, 5 } };
52+
NumMatrix na = new NumMatrix( v );
53+
for ( int i = 1; i < ops.length; i++ )
54+
{
55+
if ( ops[i].equals( "sumRegion" ) )
56+
System.out.println( na.sumRegion( n[i][0], n[i][1], n[i][2], n[i][3] ) );
57+
else
58+
{
59+
na.update( n[i][0], n[i][1], n[i][2] );
60+
System.out.println( "null" );
61+
}
62+
for ( int[] tm : na.rowSum )
63+
System.out.println( Arrays.toString( tm ) );
64+
}
65+
3866
}
3967
}
4068

4169
/**
4270
* Your NumMatrix object will be instantiated and called as such:
4371
* NumMatrix obj = new NumMatrix(matrix);
44-
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
72+
* obj.update(row,col,val);
73+
* int param_2 = obj.sumRegion(row1,col1,row2,col2);
4574
*/

‎src/Solution.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,6 +69,11 @@ public static void main( String[] args )
6969
System.out.printf( "Run time... %s ms", System.currentTimeMillis() - time );
7070
}
7171

72+
public int minimumDeleteSum( String s1, String s2 )
73+
{
74+
75+
}
76+
7277
public int numDistinctIslands2( int[][] grid )
7378
{
7479
Set<Integer> set = new HashSet<>();

0 commit comments

Comments
 (0)