Skip to content

Commit 3013283

Browse files
jianminchenjianminchen
committed
check in source code
1 parent b9ac7fe commit 3013283

File tree

4 files changed

+432
-0
lines changed

4 files changed

+432
-0
lines changed

‎2017 July -/Leetcode 132 Palindromic Partition II.cs

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode_132_Palindromic_Partition_II
8+
{
9+
/// <summary>
10+
/// Leetcode 132 Palindromic partition II
11+
/// source code is based on Java code
12+
/// https://github.com/IDeserve/learn/blob/master/PalindromePartitionMinCut.java
13+
/// </summary>
14+
class Program
15+
{
16+
static void Main(string[] args)
17+
{
18+
}
19+
20+
/// <summary>
21+
/// minimum cut - using dynamic programming
22+
///
23+
/// </summary>
24+
/// <param name="s"></param>
25+
/// <returns></returns>
26+
public static int partition(String s) {
27+
int n = s.Length;
28+
var palindrome = new bool[n, n];
29+
30+
//Trivial case: single letter palindromes
31+
for (int i = 0; i < n; i++) {
32+
palindrome[i, i] = true;
33+
}
34+
35+
//Finding palindromes of two characters.
36+
for (int i = 0; i < n-1; i++) {
37+
if (s[i] == s[i+1]) {
38+
palindrome[i, i+1] = true;
39+
}
40+
}
41+
42+
//Finding palindromes of length 3 to n
43+
for (int pLength = 3; pLength <= n; pLength++) {
44+
for (int i = 0; i < n - pLength + 1; i++) {
45+
int j = i + pLength - 1;
46+
47+
if (s[i] == s[j] //1. The first and last characters should match
48+
&& palindrome[i + 1, j - 1]) //2. Rest of the substring should be a palindrome
49+
{
50+
palindrome[i, j] = true;
51+
}
52+
}
53+
}
54+
55+
var cuts = new int[n];
56+
for(int i = 0; i < n; i++)
57+
{
58+
int minimumCut = int.MaxValue;
59+
60+
if (palindrome[0, i])
61+
{
62+
cuts[i] = 0;
63+
}
64+
else
65+
{
66+
// brute force all possible cut for [0,i], which divides into two ranges
67+
// [0, j], [j + 1, i]
68+
for (int j = 0; j < i; j++)
69+
{
70+
var currentCut = cuts[j] + 1;
71+
72+
if ((palindrome[j + 1, i]) && minimumCut > currentCut)
73+
{
74+
minimumCut = currentCut;
75+
}
76+
}
77+
78+
cuts[i] = minimumCut;
79+
}
80+
}
81+
82+
return cuts[n - 1];
83+
}
84+
}
85+
}

‎2017 July -/Leetcode 556 Next Greater Element.cs

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Diagnostics;
4+
using System.Linq;
5+
using System.Text;
6+
using System.Threading.Tasks;
7+
8+
namespace Leetcode556_nextGreaterElement
9+
{
10+
/// <summary>
11+
/// Leetcode 556 - next greater element in the integer 32 bits
12+
/// </summary>
13+
class Program
14+
{
15+
static void Main(string[] args)
16+
{
17+
var result5 = NextGreaterElement(230241);
18+
Debug.Assert(result5 == 230412);
19+
20+
var result3 = NextGreaterElement(1234);
21+
Debug.Assert(result3 == 1243);
22+
23+
var result4 = NextGreaterElement(534976);
24+
Debug.Assert(result4 == 536479);
25+
26+
// 14123 -> 14132
27+
// First find 2 from rightmost to scan left to right
28+
//
29+
var result = NextGreaterElement(14123);
30+
Debug.Assert(result == 14132);
31+
32+
var result2 = NextGreaterElement(218765);
33+
Debug.Assert(result2 == 251678);
34+
}
35+
36+
public static int NextGreaterElement(int n)
37+
{
38+
if (n < 0)
39+
{
40+
return -1;
41+
}
42+
43+
var digits = n.ToString();
44+
var isDescending = isInDescending(digits);
45+
if (isDescending)
46+
{
47+
return -1;
48+
}
49+
50+
var index = findFirstIndexNotDescendingFromRight(digits);
51+
var substring = digits.Substring(index + 1);
52+
var sortedDigits = substring.ToCharArray();
53+
Array.Sort(sortedDigits);
54+
55+
var smallestLarge = findSmallestLargeAndUpdate(digits[index], sortedDigits);
56+
var lastPart = new string(sortedDigits);
57+
58+
var nextGreat = digits.Substring(0, index) + smallestLarge.ToString() + lastPart;
59+
60+
int numValue;
61+
bool parsed = Int32.TryParse(nextGreat, out numValue);
62+
63+
if (parsed)
64+
{
65+
return numValue;
66+
}
67+
else
68+
{
69+
return -1; // online judge: 1999999999 -> should return -1, not 0
70+
}
71+
}
72+
73+
private static bool isInDescending(string s)
74+
{
75+
var digits = s.ToCharArray();
76+
var previous = 9;
77+
for (int i = 0; i < digits.Length; i++)
78+
{
79+
var current = s[i] - '0';
80+
if (current > previous)
81+
return false;
82+
83+
previous = current;
84+
}
85+
86+
return true;
87+
}
88+
89+
private static int findFirstIndexNotDescendingFromRight(string digits)
90+
{
91+
var previous = -1;
92+
93+
for (int i = digits.Length - 1; i >= 0; i--)
94+
{
95+
var current = digits[i];
96+
if (current < previous)
97+
return i;
98+
99+
previous = current;
100+
}
101+
102+
return -1;
103+
}
104+
105+
/// <summary>
106+
/// '5' and "3478", smallest large digit should be 5
107+
///
108+
/// </summary>
109+
/// <param name="digit"></param>
110+
/// <param name="sortedDigits"></param>
111+
/// <returns></returns>
112+
private static int findSmallestLargeAndUpdate(char digit, char[] sortedDigits)
113+
{
114+
var length = sortedDigits.Length;
115+
116+
var value = digit - '0';
117+
118+
for (int i = 0; i < length; i++)
119+
{
120+
var current = sortedDigits[i] - '0'; // missing - '0', catched by online judge
121+
if (value < current)
122+
{
123+
sortedDigits[i] = (char)(value +'0');
124+
return current;
125+
}
126+
}
127+
128+
return -1;
129+
}
130+
}
131+
}

‎Leetcode 132 Palindromic Partition II.cs

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
using System.Text;
5+
using System.Threading.Tasks;
6+
7+
namespace Leetcode_132_Palindromic_Partition_II
8+
{
9+
/// <summary>
10+
/// Leetcode 132 Palindromic partition II
11+
/// source code is based on Java code
12+
/// https://github.com/IDeserve/learn/blob/master/PalindromePartitionMinCut.java
13+
/// </summary>
14+
class Program
15+
{
16+
static void Main(string[] args)
17+
{
18+
}
19+
20+
/// <summary>
21+
/// minimum cut - using dynamic programming
22+
///
23+
/// </summary>
24+
/// <param name="s"></param>
25+
/// <returns></returns>
26+
public static int partition(String s) {
27+
int n = s.Length;
28+
var palindrome = new bool[n, n];
29+
30+
//Trivial case: single letter palindromes
31+
for (int i = 0; i < n; i++) {
32+
palindrome[i, i] = true;
33+
}
34+
35+
//Finding palindromes of two characters.
36+
for (int i = 0; i < n-1; i++) {
37+
if (s[i] == s[i+1]) {
38+
palindrome[i, i+1] = true;
39+
}
40+
}
41+
42+
//Finding palindromes of length 3 to n
43+
for (int pLength = 3; pLength <= n; pLength++) {
44+
for (int i = 0; i < n - pLength + 1; i++) {
45+
int j = i + pLength - 1;
46+
47+
if (s[i] == s[j] //1. The first and last characters should match
48+
&& palindrome[i + 1, j - 1]) //2. Rest of the substring should be a palindrome
49+
{
50+
palindrome[i, j] = true;
51+
}
52+
}
53+
}
54+
55+
var cuts = new int[n];
56+
for(int i = 0; i < n; i++)
57+
{
58+
int minimumCut = int.MaxValue;
59+
60+
if (palindrome[0, i])
61+
{
62+
cuts[i] = 0;
63+
}
64+
else
65+
{
66+
// brute force all possible cut for [0,i], which divides into two ranges
67+
// [0, j], [j + 1, i]
68+
for (int j = 0; j < i; j++)
69+
{
70+
var currentCut = cuts[j] + 1;
71+
72+
if ((palindrome[j + 1, i]) && minimumCut > currentCut)
73+
{
74+
minimumCut = currentCut;
75+
}
76+
}
77+
78+
cuts[i] = minimumCut;
79+
}
80+
}
81+
82+
return cuts[n - 1];
83+
}
84+
}
85+
}

0 commit comments

Comments
 (0)