Skip to content

Import C# solutions from https://github.com/kfstorm/LeetCode #245

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
yanglbme merged 2 commits into from
Jan 26, 2020
Merged

Import C# solutions from https://github.com/kfstorm/LeetCode #245

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
8653801
Import C# solutions from https://github.com/kfstorm/LeetCode
kfstorm Jan 26, 2020
545e909
Update code due to update of test cases and interfaces
kfstorm Jan 26, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Update code due to update of test cases and interfaces
  • Loading branch information
@kfstorm
kfstorm committed Jan 26, 2020
commit 545e909c8acdc2bb58ae5129996d3a8f75033f31
2 changes: 1 addition & 1 deletion solution/0001.Two Sum/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -8,7 +8,7 @@ public int[] TwoSum(int[] nums, int target) {
int index;
if (dict.TryGetValue(target - nums[i], out index))
{
return new [] { index + 1, i + 1};
return new [] { index, i};
}
if (!dict.ContainsKey(nums[i]))
{
Expand Down
12 changes: 6 additions & 6 deletions solution/0037.Sudoku Solver/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,13 +1,13 @@
public class Solution {
public void SolveSudoku(char[,] board) {
public void SolveSudoku(char[][] board) {
this.board = new ushort?[9,9];
for (var i = 0; i < 9; ++i)
{
for (var j = 0; j < 9; ++j)
{
if (board[i, j] != '.')
if (board[i][j] != '.')
{
this.board[i, j] = (ushort) (1 << (board[i, j] - '0' - 1));
this.board[i, j] = (ushort) (1 << (board[i][j] - '0' - 1));
}
}
}
Expand All @@ -18,12 +18,12 @@ public void SolveSudoku(char[,] board) {
{
for (var j = 0; j < 9; ++j)
{
if (board[i, j] == '.')
if (board[i][j] == '.')
{
board[i, j] = '0';
board[i][j] = '0';
while (this.board[i, j].Value != 0)
{
board[i, j] = (char)(board[i, j] + 1);
board[i][j] = (char)(board[i][j] + 1);
this.board[i, j] >>= 1;
}
}
Expand Down
18 changes: 9 additions & 9 deletions solution/0054.Spiral Matrix/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,9 +2,9 @@
using System.Collections.Generic;

public class Solution {
public IList<int> SpiralOrder(int[,] matrix) {
var lenI = matrix.GetLength(0);
var lenJ = matrix.GetLength(1);
public IList<int> SpiralOrder(int[][] matrix) {
var lenI = matrix.Length;
var lenJ = lenI == 0 ? 0 : matrix[0].Length;
var result = new List<int>(lenI * lenJ);
var rounds = (Math.Min(lenI, lenJ) + 1) / 2;
for (var r = 0; r < rounds; ++r)
Expand All @@ -13,33 +13,33 @@ public IList<int> SpiralOrder(int[,] matrix) {
{
for (var j = r; j < lenJ - r; ++j)
{
result.Add(matrix[r, j]);
result.Add(matrix[r][j]);
}
}
else if (lenJ - r * 2 == 1)
{
for (var i = r; i < lenI - r; ++i)
{
result.Add(matrix[i, r]);
result.Add(matrix[i][r]);
}
}
else
{
for (var j = r; j < lenJ - r - 1; ++j)
{
result.Add(matrix[r, j]);
result.Add(matrix[r][j]);
}
for (var i = r; i < lenI - r - 1; ++i)
{
result.Add(matrix[i, lenJ - r - 1]);
result.Add(matrix[i][lenJ - r - 1]);
}
for (var j = lenJ - r - 1; j > r; --j)
{
result.Add(matrix[lenI - r - 1, j]);
result.Add(matrix[lenI - r - 1][j]);
}
for (var i = lenI - r - 1; i > r; --i)
{
result.Add(matrix[i, r]);
result.Add(matrix[i][r]);
}
}
}
Expand Down
14 changes: 7 additions & 7 deletions solution/0056.Merge Intervals/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,9 +2,9 @@
using System.Linq;

public class Solution {
public IList<Interval> Merge(IList<Interval> intervals) {
var result = new List<Interval>();
foreach (var interval in intervals.OrderBy(i => i.start))
public int[][] Merge(int[][] intervals) {
var result = new List<int[]>();
foreach (var interval in intervals.OrderBy(i => i[0]))
{
if (!result.Any())
{
Expand All @@ -13,16 +13,16 @@ public IList<Interval> Merge(IList<Interval> intervals) {
else
{
var last = result.Last();
if (last.end < interval.start)
if (last[1] < interval[0])
{
result.Add(interval);
}
else if (last.end < interval.end)
else if (last[1] < interval[1])
{
last.end = interval.end;
last[1] = interval[1];
}
}
}
return result;
return result.ToArray();
}
}
16 changes: 8 additions & 8 deletions solution/0057.Insert Interval/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,28 +2,28 @@
using System.Collections.Generic;

public class Solution {
public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval) {
var result = new List<Interval>();
public int[][] Insert(int[][] intervals, int[] newInterval) {
var result = new List<int[]>();
var i = 0;

while (i < intervals.Count && intervals[i].end < newInterval.start)
while (i < intervals.Length && intervals[i][1] < newInterval[0])
{
result.Add(intervals[i++]);
}

while (i < intervals.Count && intervals[i].start <= newInterval.end && intervals[i].end >= newInterval.start)
while (i < intervals.Length && intervals[i][0] <= newInterval[1] && intervals[i][1] >= newInterval[0])
{
newInterval.start = Math.Min(intervals[i].start, newInterval.start);
newInterval.end = Math.Max(intervals[i].end, newInterval.end);
newInterval[0] = Math.Min(intervals[i][0], newInterval[0]);
newInterval[1] = Math.Max(intervals[i][1], newInterval[1]);
++i;
}
result.Add(newInterval);

while (i < intervals.Count)
while (i < intervals.Length)
{
result.Add(intervals[i++]);
}

return result;
return result.ToArray();
}
}
16 changes: 8 additions & 8 deletions solution/0079.Word Search/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,7 +1,7 @@
public class Solution {
public bool Exist(char[,] board, string word) {
var lenI = board.GetLength(0);
var lenJ = board.GetLength(1);
public bool Exist(char[][] board, string word) {
var lenI = board.Length;
var lenJ = lenI == 0 ? 0 : board[0].Length;
var visited = new bool[lenI, lenJ];
for (var i = 0; i < lenI; ++i)
{
Expand All @@ -15,17 +15,17 @@ public bool Exist(char[,] board, string word) {
}
return false;
}

private int[,] paths = new int[4,2] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
private bool Search(char[,] board, bool[,] visited, string word, int lenI, int lenJ, int i, int j, int p)

private bool Search(char[][] board, bool[,] visited, string word, int lenI, int lenJ, int i, int j, int p)
{
if (p == word.Length)
{
return true;
}
if (i < 0 || i >= lenI || j < 0 || j >= lenJ) return false;
if (visited[i, j] || word[p] != board[i, j]) return false;
if (visited[i, j] || word[p] != board[i][j]) return false;
visited[i, j] = true;
for (var k = 0; k < 4; ++k)
{
Expand All @@ -34,4 +34,4 @@ private bool Search(char[,] board, bool[,] visited, string word, int lenI, int l
visited[i, j] = false;
return false;
}
}
}
8 changes: 4 additions & 4 deletions solution/0085.Maximal Rectangle/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -25,16 +25,16 @@ private int MaximalRectangleHistagram(int[] height) {
return result;
}

public int MaximalRectangle(char[,] matrix) {
var lenI = matrix.GetLength(0);
var lenJ = matrix.GetLength(1);
public int MaximalRectangle(char[][] matrix) {
var lenI = matrix.Length;
var lenJ = lenI == 0 ? 0 : matrix[0].Length;
var height = new int[lenJ];
var result = 0;
for (var i = 0; i < lenI; ++i)
{
for (var j = 0; j < lenJ; ++j)
{
if (matrix[i, j] == '1')
if (matrix[i][j] == '1')
{
++height[j];
}
Expand Down
105 changes: 53 additions & 52 deletions solution/0127.Word Ladder/Solution.cs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,65 +3,66 @@
using System.Linq;

public class Solution {
public int LadderLength(string beginWord, string endWord, ISet<string> wordDict) {
if (beginWord == endWord) return 1;
wordDict.Remove(beginWord);
wordDict.Remove(endWord);
var words = new [] { beginWord, endWord }.Concat(wordDict.Where(word => word.Length == beginWord.Length)).Select((word, i) => new { Word = word, Index = i }).ToList();

var paths = new List<int>[words.Count];
for (var i = 0; i < paths.Length; ++i)
{
paths[i] = new List<int>();
}
for (var i = 0; i < beginWord.Length; ++i)
{
public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
var words = Enumerable.Repeat(beginWord, 1).Concat(wordList).Select((word, i) => new { Word = word, Index = i }).ToList();
var endWordIndex = words.Find(w => w.Word == endWord)?.Index;
if (endWordIndex == null) {
return 0;
}

var paths = new List<int>[words.Count];
for (var i = 0; i < paths.Length; ++i)
{
paths[i] = new List<int>();
}
for (var i = 0; i < beginWord.Length; ++i)
{
var hashMap = new Hashtable();
foreach (var item in words)
{
var newWord = string.Format("{0}_{1}", item.Word.Substring(0, i), item.Word.Substring(i + 1));
List<int> similars;
List<int> similars;
if (!hashMap.ContainsKey(newWord))
{
similars = new List<int>();
hashMap.Add(newWord, similars);
}
else
{
similars = (List<int>)hashMap[newWord];
}
foreach (var similar in similars)
{
paths[similar].Add(item.Index);
paths[item.Index].Add(similar);
}
{
similars = new List<int>();
hashMap.Add(newWord, similars);
}
else
{
similars = (List<int>)hashMap[newWord];
}
foreach (var similar in similars)
{
paths[similar].Add(item.Index);
paths[item.Index].Add(similar);
}
similars.Add(item.Index);
}
}
var left = words.Count - 1;
var lastRound = new List<int> { 0 };
var visited = new bool[words.Count];
visited[0] = true;
for (var result = 2; left > 0; ++result)
{
var thisRound = new List<int>();
foreach (var index in lastRound)
{
foreach (var next in paths[index])
{
if (!visited[next])
{
visited[next] = true;
if (next == 1) return result;
thisRound.Add(next);
}
}
}
}

var left = words.Count - 1;
var lastRound = new List<int> { 0 };
var visited = new bool[words.Count];
visited[0] = true;
for (var result = 2; left > 0; ++result)
{
var thisRound = new List<int>();
foreach (var index in lastRound)
{
foreach (var next in paths[index])
{
if (!visited[next])
{
visited[next] = true;
if (next == endWordIndex) return result;
thisRound.Add(next);
}
}
}
if (thisRound.Count == 0) break;
lastRound = thisRound;
}
return 0;
lastRound = thisRound;
}

return 0;
}
}
Loading