695. Max Area of Island - LeetCode

In this part, I try to solve the problem of 659 with C#, and this level is medium.

Problem

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

My Answer

I use the DFS to solve this problem.

Concept following:

  1. Loop grid
  2. Traverse all island and compare the max count of island areas
  3. Get the max result of island

I split the program to partial class to help us easy to read, and define an enum of area to mark the traversal.
Finally, I use the function TraverseIsland that is an algorithm of DFS to help us traverse the four directions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public partial class Solution {      

/// <summary>
/// MaxAreaOfIsland
/// </summary>
/// <param name="grid">grid</param>
/// <returns>maximum area of an island</returns>
public int MaxAreaOfIsland(int[][] grid) {
var maxAreaOfIsland = 0;
for(var i=0;i<grid.Length;i++)
{
for(var j=0;j<grid[0].Length;j++)
{
if(IsIsland(grid[i][j]))
{
var islandAreas = new List<(int,int)>();
TraverseIsland(islandAreas,grid,i,j);
maxAreaOfIsland = Math.Max(islandAreas.Count,maxAreaOfIsland);
}
}
}
return maxAreaOfIsland;
}
}

///
/// private method & variant
///
public partial class Solution {

private enum AreaEnum
{
None = 0,
Island = 1,
HasBeenTraverse = 2,
};

/// <summary>
/// Check the location that is island
/// </summary>
/// <param name="gridValue">value of grid</param>
/// <returns>bool</returns>
private bool IsIsland(int gridValue)
=> gridValue == (int)AreaEnum.Island;

/// <summary>
/// Mark the traversal to avoid infinite loops
/// </summary>
/// <param name="grid">grid</param>
/// <param name="i">i of grid</param>
/// <param name="j">j of grid</param>
private void MarkTraversal(int[][] grid,int i,int j)
=> grid[i][j] = (int)AreaEnum.HasBeenTraverse;

/// <summary>
/// Traverse Island
/// Traverse the grid 4-directionally
/// </summary>
/// <param name="islandAreas">areas of the island</param>
/// <param name="grid">grid object</param>
/// <param name="i">i of grid</param>
/// <param name="j">j of grid</param>
private void TraverseIsland (
List<(int,int)> islandAreas,
int[][] grid,
int i,
int j)
{
islandAreas.Add((i,j));
MarkTraversal(grid,i,j);

// top
if(i-1 >= 0 && IsIsland(grid[i-1][j]))
TraverseIsland(islandAreas,grid,i-1,j);
// bottom
if(i+1 < grid.Length && IsIsland(grid[i+1][j]))
TraverseIsland(islandAreas,grid,i+1,j);
// left
if(j-1 >= 0 && IsIsland(grid[i][j-1]))
TraverseIsland(islandAreas,grid,i,j-1);
// right
if(j+1 < grid[0].Length && IsIsland(grid[i][j+1]))
TraverseIsland(islandAreas,grid,i,j+1);
}
}

Run Result:

1
2
Runtime: 98 ms, faster than 93.42% of C# online submissions for Max Area of Island.
Memory Usage: 43.9 MB, less than 6.70% of C# online submissions for Max Area of Island.

C# create the non-reference object (Deep Clone)

In my work, I usually have a problem about how to create a non-reference object in C#. So today I want to solve it with a simple way that use the serialization and deserialization of JSON.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using System;
using System.Text.Json;

namespace NonReferenceObj
{
internal class Program
{
/// <summary>
/// Order
/// </summary>
public class Order
{
public int Seq { get; set; }
public string No { get; set; }
public decimal Amount { get; set; }
}

/// <summary>
/// Util
/// </summary>
public class Util
{
/// <summary>
/// Deep Clone
/// Copy a non-reference object
/// </summary>
/// <typeparam name="T">T</typeparam>
/// <param name="obj">obj</param>
/// <returns></returns>
public static T DeepClone<T>(T obj)
=> JsonSerializer.Deserialize<T>(JsonSerializer.Serialize(obj));
}

static void Main()
{
var order = new Order
{
Seq = 1,
No = "20220608",
Amount = 100,
};

var copy = Util.DeepClone(order);

// Check the reference of object
Console.WriteLine($"Check the reference of object: {object.ReferenceEquals(order, copy)}");
// Check the equal of value
Console.WriteLine($"Check the equal of value: {order.No == copy.No && order.Seq == copy.Seq && order.Amount == copy.Amount}");
}
}
}

Finally, we got the output below:

1
2
Check the reference of object: False
Check the equal of value: True

Refactor the code - function

First, we find a section of code that contains different operations, such as initialization and print. We can try to refactor that extracts them into functions.

Concepts

  1. The process of restructuring code, while not changing its original functionality.
  2. Easier to understand
  3. Cheaper to modify
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using System;
using System.Collections.Generic;

namespace refactor01
{
internal class Program
{
static void Main(string[] args)
{
var numbers = new List<string>();
for(var i = 0; i < 10; i++)
{
numbers.Add(i.ToString());
}
foreach (var item in numbers)
{
Console.Write(item);
}
}
}
}

Now, We extract the different operations into functions, and each function just do one thing. We can more easily control something we want to do.

  1. Extract the different operations into functions.
  2. Add the summary.
  3. Remove the unused parameter.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using System;
using System.Collections.Generic;

namespace refactor01
{
internal class Program
{
static void Main()
{
var numbers = new List<string>();
initNumbers(numbers);
printNumbers(numbers);
}

/// <summary>
/// init the numbers
/// </summary>
/// <param name="numbers">list of numbers</param>
public static void initNumbers(List<string> numbers)
{
for (var i = 0; i < 10; i++)
{
numbers.Add(i.ToString());
}
}

/// <summary>
/// print the numbers
/// </summary>
/// <param name="numbers">list of numbers</param>
public static void printNumbers(List<string> numbers)
{
foreach (var item in numbers)
{
Console.Write(item);
}
}
}
}

In conclusion

Finally, we did it that finished the refactoring and just made it easy to maintain and read.

SQL Server透過建立索引提升查詢速度

因為最近遇到資料庫量大的瓶頸,因此稍微紀錄一下調效能的作法建立「索引」。
之前有提到過: SQL Server 叢集索引vs非叢集索引 可以先看這邊。

而這回主要透過建立索引去改善查詢效能,如下實作:

實作

1.首先先建立一張表

1
2
3
4
5
6
7
8
9
10
11
12
USE [TodoDB]
CREATE TABLE [Todos](
[Id] [int] IDENTITY(1,1) NOT NULL,
[Name] [nvarchar](100) NULL,
[Priority] [tinyint] NULL,
[UserId] [int] NOT NULL,
[IsValid] [bit] NOT NULL,
[CreatedOn] [datetime] NOT NULL,
[UpdatedOn] [datetime] NOT NULL
CONSTRAINT [PK_Todos] PRIMARY KEY CLUSTERED ([Id] ASC)
);
GO

2.增加幾筆資料

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
USE [TodoDB]
INSERT INTO [Todos]
(
[Name],
[Priority],
[UserId],
[IsValid],
[CreatedOn],
[UpdatedOn]
)
VALUES
('測試1',1,1,1,'2022-05-31','2022-05-31'),
('測試2',4,2,1,'2022-05-31','2022-05-31'),
('測試3',3,3,1,'2022-05-31','2022-05-31'),
('測試4',2,1,1,'2022-05-31','2022-05-31'),
('測試5',1,1,1,'2022-05-31','2022-05-31')
GO

3.建立非叢集索引

1
2
3
4
USE [TodoDB]
CREATE NONCLUSTERED INDEX IX_Priority
ON [Todos](Priority ASC,Id ASC)
GO

這時如過資料量筆數大
進行查詢剛好排序了Priority ASC、Id ASC速度就會提升。

參考資料

程式千萬筆資料量級搜尋提速方式

千萬筆資料要怎麼讓每次搜尋的速度提升呢?
我以前一直蠻好奇的,最近有幸理解到一個簡單理解的做法。

用C#舉例,如下程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;

namespace LargeData
{
public class OrderModel
{
public string OrderNumber { get; set; }
}
public class Program
{
private static readonly int _dataCount = 20000000;
public static void Main()
{
var list = new List<OrderModel>();
for (var i = 0; i < _dataCount; i++)
{
list.Add(new OrderModel
{
OrderNumber = $"{i + 1}"
});
}

Stopwatch sw = new Stopwatch();
sw.Reset();
sw.Start();

var result = list.ToList();
var targetOrderNumber = "20000000";
var targetOrder = list
.Where(x => x.OrderNumber == targetOrderNumber)
.FirstOrDefault();

Console.WriteLine($"TargetOrder:{targetOrder.OrderNumber}");

sw.Stop();
string second = (sw.Elapsed.TotalMilliseconds / 1000).ToString();
Console.WriteLine($"Run:{second}");
}
}
}

output:

1
2
TargetOrder:20000000
Run Second:0.89836

如上,在2千萬筆資料中查詢只耗了0.8秒。

簡單來說就是靠快取,我們將17~24行的資料儲存到記憶體中或是其他Redis伺服器當作快取。
每次在程式中去撈取時只要從該入口去提取資料即可,雖然耗費記憶體,但提速效果極高。
這作法前提:當資料異動時需同步更新快取資料,必須做好單一入口去做存取。

在30~34行中,我們可以使用演算法去優化,在這裡用最簡單的O(n)作法,如果有使用如二元樹搜尋那可以最佳化到O(log n),最差O(n)。

我在執行以上的程式使用了2.4G記憶體。

電腦效能:

  • Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz 2.81 GHz
  • 16.0 GB (15.9 GB usable)

如果把這個快取資料放到其他伺服器做,那記憶體在程式上就幾乎不占記憶體。
把記憶體耗損轉移到其他伺服器上,記憶體不足時也只要去擴增快取伺服器的記憶體。

結論

算是有點火影忍者卡卡西萬花筒血輪眼神威的作法,把負載轉移到其他空間的快取。

C# 資料分群

在這邊主要介紹List的分群,如有以下的五筆資料

1
["00001","00002","00003","00004","00005"]

這時想要以2來群分,變成下方結果

1
[["00001","00002"],["00003","00004"],["00005"]]

程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text.Json;

namespace ListGroupBy
{
internal class Program
{
static void Main(string[] args)
{
var numbers = new List<string>
{
"00001","00002","00003","00004","00005"
};

var numberGroup = numbers
.Select((number, index) => new { number, index })
.GroupBy(g => g.index / 2, i => i.number)
.ToList();

//It will iterate through each groups
foreach (var group in numberGroup)
{
Console.WriteLine($"{group.Key} , count: {group.Count()}");
//Iterate through each number of a group
foreach (var number in group)
Console.WriteLine($" number : {number}");
}
}
}
}

output:

1
2
3
4
5
6
7
8
0 ,  count: 2
number : 00001
number : 00002
1 , count: 2
number : 00003
number : 00004
2 , count: 1
number : 00005

SQL Server 叢集索引vs非叢集索引

為了能讓資料庫提升資料搜查效率,我們能透過建立索引去調整搜尋。

索引

索引是一種與資料表或檢視有關的磁碟內存結構,它會加快從該資料表或檢視中擷取資料列的速度。 索引中包含從資料表或檢視中一或多個資料行建出的索引鍵。 這些索引鍵儲存在結構 (B 型樹狀結構) 中,讓 SQL Server 可以快速有效地尋找與索引鍵值相關的一個或多個資料列。

叢集vs非叢集

比較 叢集索引
Clustered Index
非叢集索引
NonClustered Index
解釋 1.叢集索引將資料表或檢視中的資料列依其索引鍵值排序與儲存。 這些就是索引定義中包含的資料行。 因為資料列本身只能以一種順序排序,所以每個資料表只能有一個叢集索引。
2.只有當資料表包含叢集索引時,資料表中的資料列才會以排序順序儲存。 當資料表有叢集索引時,資料表又稱為叢集資料表。 如果資料表沒有任何叢集索引,它的資料列就儲存在未排序的結構中,這個結構稱為堆積。
1.非叢集索引有一個與資料列完全分開的結構。 非叢集索引包含非叢集索引鍵值,而每個索引鍵值項目都有一個指標,指向包含索引鍵值的資料列。
2.從非叢集索引中的索引列指向資料列的指標被稱為資料列定位器。 資料列定位器的結構須視資料頁儲存在堆積或叢集資料表而定。 若是堆積,資料列定位器是指向資料列的指標。 若是叢集資料表,資料列定位器就是叢集索引鍵。
3.您可以將非索引鍵之資料行新增至非叢集索引的分葉層級中,以規避現有索引鍵的限制,並執行完全涵蓋的索引查詢。 如需詳細資訊,請參閱 使用內含資料行建立索引。 如需索引鍵限制的詳細資訊,請參閱SQL Server的容量規格上限。
注意 1.一個資料表只能有一個「叢集索引」,因為實體資料列的排列順序不可能有多種。
2.如果在SQL Server主索引鍵(PK)會預設為叢集索引,如果要更改為其他叢集索引就必須先取消PK的叢集索引。
3.不可用於(image/text/xml/max 型態,如 varchar(max))型態
4.每個索引最多可以包括 16 個欄位
1.一個資料表可以有多個非叢集索引。
2.每個索引最多可以包括 16 個欄位
常用於 1.常被引用為外來鍵的欄位
2.最常被搜尋的日期欄位
3.常被用來 ORDER BY 或是 GROUP BY 的欄位
1.為了改善叢集索引未涵蓋但經常使用之查詢的效能

參考資料

談React框架難以維護的問題

這篇聊一下過去在寫React實作上遇到的問題,以及本篇重點為什麼難以維護。
以下:

  1. React如果選擇純Javascript,專案越大越難維護
  2. 維護的前人是高手,接手的人是新手
  3. 過度抽象的邏輯
  4. JSX不好了解全局
  5. 每個都元件,但不寫文件
  6. 過度封裝的巢狀元件
  7. 無固定寫法,套件選擇難以控制

1.React如果選擇純Javascript,專案越大越難維護

因為javascript本身就有很多雷坑
1.await、async
2.javascript reference的問題
3.函式參數型態不明確,比如不知道傳進來的參數是陣列、物件、物件屬性的內容又是什麼。因為大多數React專案都是直接原生Javascript,造成容易犯原生的錯。

1
const getOrderReceiptData({order}) => order?.detail?.receipt?.data

解決方法
請使用Typescript、ESLint可以避免。

2. 維護的前人是高手,接手的人是新手

因為React很自由,所以可能前人會ES6、React Hook、React Class、各種bind用法,並把它發揮的非常透徹。
這時接手的人必須每遇到一個就去查用法,直到補完所有用法才知道在寫什麼。

解決方法
限制Code統一寫法。且至少要兩人,不然好懂難懂只有寫的人知道。

3. 過度抽象的邏輯

1
2
3
const getData({pid,od,o}) => { 
//略 以下作一些複雜的pid、od、o的資料處理
}

添加一些自己覺得合理但其實超難讀的簡寫參數。
然後getData因為最後要取得data所以就抽象叫做getData,但不寫註解,讓人要盤完內容才能知道做什麼。一個還好,當A call B、B call C時,就會很可怕。

解決方法
解決方法:Typescript、ESLint。

4. JSX不好了解全局

因為需使用原生寫法造成三元運算子大量使用。
難以看懂原本畫面、動態變更後結果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<div>
{
<div>
A
</div>?
<span>
<div>
A
</div>?
<span>
B
</span>:
<div>
C
</div>
</span>:
<div>
C
</div>
}
</div>

解決方法
無解

5. 每個都元件,但不寫文件

封裝的套件又沒說明文件時。
一個套件外面傳入N個參數,前往實作看到1000行js,很可怕。
要改一個小東西,要重寫也無法,因為全部吃那一套。
寫React真的別閉門造車,特別是不寫說明文件的人,請去用開源套件謝謝…。

1
2
3
4
5
6
7
8
9
10
11
12
<CustomTable
data={data}
key={id}
isDeleted={checkedList}
...
/>
<Dn
isDeleted={checkedList}
/>
<RSpan
data={data}
/>

解決方法
寫說明文件、範例檔案

6. 過度封裝的巢狀元件

當你一直前往發現套件裡面還有更多套件,像是俄羅斯娃娃,而這些俄羅斯娃娃又拆的很散。
解決方法
無解,現行前端的通病。

7. 無固定寫法,套件選擇難以控制

React官方沒有固定範例寫法,只提供基本library,就是基礎ES6 JS去寫,所以每個人寫出的code都不一樣,如果又是新手剛學所寫的,一開始架構沒規劃好,後面就是建立一個歪掉的建築。
在套件依賴上也很多選擇,造成版本依賴性問題。
所以React…維護的專案會很可怕。
相比Vue,Vue官方做的很好,完整的範例可以參考,大家寫法也99%一致。

解決方法
無解。

結論

其實很多人鼓吹JQuery淘汰,都改去寫React是有問題的,因為React容易要改一個東西要讀前人的一串技術債,改法絕對沒JQuery輕鬆而且會改到很崩潰。
不是元件化了?那前提是元件化是合理的…當發現一些不合理參數傳進去、設計奇怪的元件、客製化又封裝…,如果你是接手的,JQuery還痛快些。

綜合上述,寫React會遇到上述的這些機率超高,所以難以維護,塊陶…。

那Vue呢?
Vue有官方完整應用範例,像人在看的HTML Template不像React的jsx,畫面好上手、包好的語法糖,後面接手的人都不會太有壓力。即使Vue是用js寫不是Typescript,因為他不用像React過度抽象化,很多官方語法糖都包好了。

然後如果是大專案,Typescript是必須的,否則你的js會在多人改來改去下炸鍋。

以上是個人體驗後的結論。

SQL Server 建立複合鍵(composite primary key)

在這篇簡易紀錄一下SQL複合鍵的做法。

1
2
3
4
5
6
7
8
9
CREATE TABLE Orders(
OrderNumber NVARCHAR(50),
OrderType TINYINT,
CreatedOn DATETIME,
UpdatedOn DATETIME,
IsValid BIT,
Remarks NVARCHAR(100) NULL
PRIMARY KEY (OrderNumber, OrderType)
)

就是在PRIMARY KEY加入兩個鍵值即可。
在此以OrderNumber、OrderType,表示同一訂單類型的編號不可重複。

如果是在SQL Server的介面設計上,就是點CTRL把需要設定的PK給匡列,之後再右鍵設定PK即可。

PostgreSQL get the start and end dates of prev month query

My table has below data, and I want to get the previous data of month,and today is 2022-05-04.

1
2
3
4
2022-03-01
2022-04-01
2022-04-01
2022-05-03

This is the answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
WITH TEMP_TABLE AS
(
SELECT '2022-03-01'::TIMESTAMP WITHOUT TIME ZONE AS MYDATE
UNION ALL
SELECT '2022-04-01'::TIMESTAMP WITHOUT TIME ZONE AS MYDATE
UNION ALL
SELECT '2022-04-02'::TIMESTAMP WITHOUT TIME ZONE AS MYDATE
UNION ALL
SELECT '2022-05-03'::TIMESTAMP WITHOUT TIME ZONE AS MYDATE
)
SELECT
*
FROM
TEMP_TABLE TT
WHERE
TT.MYDATE >= DATE_TRUNC('MONTH',NOW()) - INTERVEL '1 MONTH'
AND TT.MYDATE < DATE_TRUNC('MONTH',NOW())

explain
The function DATE_TRUNC will help us convert datetime to first date of month.
It’s like Now() is 2022-05-09, and function DATE_TRUNC(‘MONTH’,NOW()) will convert datetime to 2022-05-01.I use the DATE_TRUNC create a duration.

Example:
NOW() = 2022-05-09

1
2
x >= 2022-04-01 
x < 2022-05-01

So,the result is 2022-04-01~2022-04-30.