CSharp Coding Practice 2
CSharp Coding Practice 2
121. Palindrome Number (Beginner)
Given an integer, write a function to determine if it is a
palindrome. An integer is a palindrome when it reads the same backward as
forward.
using System;
class Program
{
static void Main()
{
int num = 121;
bool
isPalindrome = IsPalindrome(num);
Console.WriteLine(isPalindrome ? "Palindrome" : "Not
Palindrome");
}
static bool
IsPalindrome(int x)
{
if (x < 0)
return false;
int original =
x, reversed = 0;
while (x >
0)
{
reversed =
reversed * 10 + x % 10;
x /= 10;
}
return
original == reversed;
}
}
122. Move Zeroes (Intermediate)
Given an array of integers, write a function to move all
zeroes to the end of the array without changing the relative order of non-zero
elements.
using System;
class Program
{
static void Main()
{
int[] nums = {
0, 1, 0, 3, 12 };
MoveZeroes(nums);
Console.WriteLine("Array
after moving zeros: " + string.Join(", ", nums));
}
static void
MoveZeroes(int[] nums)
{
int
nonZeroIndex = 0;
for (int i =
0; i < nums.Length; i++)
{
if
(nums[i] != 0)
{
nums[nonZeroIndex++] = nums[i];
}
}
for (int i =
nonZeroIndex; i < nums.Length; i++)
{
nums[i] =
0;
}
}
}
123. Longest Substring Without Repeating Characters
(Intermediate)
Given a string, find the length of the longest substring
without repeating characters.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string s =
"abcabcbb";
int result =
LengthOfLongestSubstring(s);
Console.WriteLine("Longest Substring Without Repeating Characters:
" + result);
}
static int
LengthOfLongestSubstring(string s)
{
int maxLength
= 0;
Dictionary<char, int> map = new Dictionary<char, int>();
int left = 0;
for (int right
= 0; right < s.Length; right++)
{
if
(map.ContainsKey(s[right]))
{
left =
Math.Max(left, map[s[right]] + 1);
}
map[s[right]] = right;
maxLength
= Math.Max(maxLength, right - left + 1);
}
return
maxLength;
}
}
124. Valid Parentheses (Beginner)
Given a string containing just the characters '(', ')', '{', '}', '[',
and ']', write a program to determine if the input string is valid. An
input string is valid if the brackets are closed in the correct order.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string s =
"()[]{}";
bool isValid =
IsValid(s);
Console.WriteLine(isValid ? "Valid" : "Invalid");
}
static bool
IsValid(string s)
{
Stack<char> stack = new Stack<char>();
foreach (char
c in s)
{
if (c ==
'(' || c == '{' || c == '[')
{
stack.Push(c);
}
else
{
if
(stack.Count == 0) return false;
char
top = stack.Pop();
if (c
== ')' && top != '(' || c == '}' && top != '{' || c == ']'
&& top != '[')
{
return false;
}
}
}
return
stack.Count == 0;
}
}
125. Container With Most Water (Advanced)
Given n non-negative integers a1, a2, ..., an,
where each represents a point at coordinate (i, ai). Write a program to
find two lines that together with the x-axis form a container that would hold
the most water.
using System;
class Program
{
static void Main()
{
int[] heights
= { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
int result =
MaxArea(heights);
Console.WriteLine("Max
Area: " + result);
}
static int
MaxArea(int[] height)
{
int left = 0,
right = height.Length - 1;
int maxArea =
0;
while (left
< right)
{
int width
= right - left;
int h =
Math.Min(height[left], height[right]);
maxArea =
Math.Max(maxArea, width * h);
if
(height[left] < height[right])
left++;
else
right--;
}
return
maxArea;
}
}
126. Find Peak Element (Intermediate)
A peak element is an element that is strictly greater than
its neighbors. Given an array of integers, find a peak element. The array may
have multiple peak elements, in that case, return any of the peak elements.
using System;
class Program
{
static void Main()
{
int[] nums = {
1, 2, 3, 1 };
int peak =
FindPeakElement(nums);
Console.WriteLine("Peak Element: " + peak);
}
static int
FindPeakElement(int[] nums)
{
int left = 0,
right = nums.Length - 1;
while (left
< right)
{
int mid =
left + (right - left) / 2;
if
(nums[mid] > nums[mid + 1])
right
= mid;
else
left =
mid + 1;
}
return left;
}
}
127. Find Minimum in Rotated Sorted Array
(Intermediate)
Suppose an array of length n sorted in ascending
order is rotated at some pivot unknown to you beforehand. Find the minimum
element of the array.
using System;
class Program
{
static void Main()
{
int[] nums = {
4, 5, 6, 7, 0, 1, 2 };
int min =
FindMin(nums);
Console.WriteLine("Minimum Element: " + min);
}
static int
FindMin(int[] nums)
{
int left = 0,
right = nums.Length - 1;
while (left
< right)
{
int mid =
left + (right - left) / 2;
if
(nums[mid] > nums[right])
left =
mid + 1;
else
right
= mid;
}
return
nums[left];
}
}
128. Generate Parentheses (Advanced)
Given n pairs of parentheses, write a program to
generate all combinations of well-formed parentheses.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int n = 3;
var result =
GenerateParentheses(n);
Console.WriteLine("Generated Parentheses: " +
string.Join(", ", result));
}
static
List<string> GenerateParentheses(int n)
{
List<string> result = new List<string>();
Backtrack(result, "", 0, 0, n);
return result;
}
static void
Backtrack(List<string> result, string current, int open, int close, int
n)
{
if
(current.Length == n * 2)
{
result.Add(current);
return;
}
if (open <
n)
Backtrack(result,
current + "(", open + 1, close, n);
if (close <
open)
Backtrack(result, current + ")", open, close + 1, n);
}
}
129. Set Matrix Zeroes (Advanced)
Given an m x n matrix, if an element in the matrix
is 0, set its entire row and column to 0.
using System;
class Program
{
static void Main()
{
int[,] matrix
= {
{ 1, 1, 1
},
{ 1, 0, 1
},
{ 1, 1, 1
}
};
SetZeroes(matrix);
Console.WriteLine("Matrix
after setting zeroes:");
for (int i =
0; i < matrix.GetLength(0); i++)
{
for (int j
= 0; j < matrix.GetLength(1); j++)
{
Console.Write(matrix[i, j] + " ");
}
Console.WriteLine();
}
}
static void
SetZeroes(int[,] matrix)
{
bool
firstRowZero = false, firstColZero = false;
// Check if
the first row contains zero
for (int i =
0; i < matrix.GetLength(1); i++)
{
if
(matrix[0, i] == 0)
{
firstRowZero = true;
break;
}
}
// Check if
the first column contains zero
for (int i =
0; i < matrix.GetLength(0); i++)
{
if
(matrix[i, 0] == 0)
{
firstColZero = true;
break;
}
}
// Use the
first row and column to mark zeroes
for (int i =
1; i < matrix.GetLength(0); i++)
{
for (int j
= 1; j < matrix.GetLength(1); j++)
{
if
(matrix[i, j] == 0)
{
matrix[i, 0] = 0;
matrix[0, j] = 0;
}
}
}
// Set matrix
zeroes based on marks
for (int i =
1; i < matrix.GetLength(0); i++)
{
for (int j
= 1; j < matrix.GetLength(1); j++)
{
if
(matrix[i, 0] == 0 || matrix[0, j] == 0)
{
matrix[i, j] = 0;
}
}
}
// Handle the
first row and first column
if
(firstRowZero)
{
for (int i
= 0; i < matrix.GetLength(1); i++)
{
matrix[0, i] = 0;
}
}
if
(firstColZero)
{
for (int i
= 0; i < matrix.GetLength(0); i++)
{
matrix[i, 0] = 0;
}
}
}
}
130. Search Insert Position (Beginner)
Given a sorted array and a target value, return the index if
the target is found. If not, return the index where it would be if it were
inserted in order.
using System;
class Program
{
static void Main()
{
int[] nums = {
1, 3, 5, 6 };
int target =
5;
int position =
SearchInsertPosition(nums, target);
Console.WriteLine("Insert Position: " + position);
}
static int
SearchInsertPosition(int[] nums, int target)
{
int left = 0,
right = nums.Length - 1;
while (left
<= right)
{
int mid =
left + (right - left) / 2;
if
(nums[mid] == target)
return
mid;
else if
(nums[mid] < target)
left =
mid + 1;
else
right
= mid - 1;
}
return left;
}
}
131. String Compression (Intermediate)
Given a string s consisting of characters, write a
function to compress the string using the counts of repeated characters. If the
compressed string is not shorter than the original string, return the original
string.
using System;
using System.Text;
class Program
{
static void Main()
{
string s =
"aabcccccaaa";
string
compressed = CompressString(s);
Console.WriteLine("Compressed String: " + compressed);
}
static string
CompressString(string s)
{
StringBuilder
compressed = new StringBuilder();
int count = 1;
for (int i =
1; i < s.Length; i++)
{
if (s[i]
== s[i - 1])
{
count++;
}
else
{
compressed.Append(s[i - 1]);
compressed.Append(count);
count
= 1;
}
}
compressed.Append(s[s.Length - 1]);
compressed.Append(count);
return
compressed.Length < s.Length ? compressed.ToString() : s;
}
}
132. Reverse Words in a String (Intermediate)
Given an input string s, reverse the order of the
words. A word is defined as a sequence of characters delimited by spaces.
using System;
class Program
{
static void Main()
{
string s =
"the sky is blue";
string
reversed = ReverseWords(s);
Console.WriteLine("Reversed Words: " + reversed);
}
static string
ReverseWords(string s)
{
string[] words
= s.Split(' ');
Array.Reverse(words);
return
string.Join(" ", words);
}
}
133. Intersection of Two Arrays (Intermediate)
Given two arrays, write a function to return their
intersection. Each element in the result should appear as many times as it
shows in both arrays.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int[] nums1 =
{ 1, 2, 2, 1 };
int[] nums2 =
{ 2, 2 };
int[] result =
Intersection(nums1, nums2);
Console.WriteLine("Intersection: " + string.Join(",
", result));
}
static int[]
Intersection(int[] nums1, int[] nums2)
{
HashSet<int> set1 = new HashSet<int>(nums1);
HashSet<int> resultSet = new HashSet<int>();
foreach (var
num in nums2)
{
if
(set1.Contains(num))
{
resultSet.Add(num);
set1.Remove(num); // Avoid duplicates
}
}
int[] result =
new int[resultSet.Count];
resultSet.CopyTo(result);
return result;
}
}
134. Find the Duplicate Number (Intermediate)
Given an array containing n + 1 integers where
each integer is between 1 and n, find the duplicate number.
using System;
class Program
{
static void Main()
{
int[] nums = {
1, 3, 4, 2, 2 };
int duplicate
= FindDuplicate(nums);
Console.WriteLine("Duplicate Number: " + duplicate);
}
static int
FindDuplicate(int[] nums)
{
int slow =
nums[0], fast = nums[0];
// Phase 1:
Find intersection point in the cycle
do
{
slow =
nums[slow];
fast =
nums[nums[fast]];
} while (slow
!= fast);
// Phase 2:
Find the entrance to the cycle
slow =
nums[0];
while (slow !=
fast)
{
slow =
nums[slow];
fast =
nums[fast];
}
return slow;
}
}
135. Power of Two (Beginner)
Write a program to check if a number is a power of two.
using System;
class Program
{
static void Main()
{
int n = 16;
bool
isPowerOfTwo = IsPowerOfTwo(n);
Console.WriteLine(isPowerOfTwo ? "Power of Two" : "Not
Power of Two");
}
static bool
IsPowerOfTwo(int n)
{
return n >
0 && (n & (n - 1)) == 0;
}
}
136. Two Sum (Beginner)
Given an array of integers and a target value, return the
indices of the two numbers that add up to the target.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int[] nums = {
2, 7, 11, 15 };
int target =
9;
int[] result =
TwoSum(nums, target);
Console.WriteLine("Indices: " + string.Join(", ",
result));
}
static int[]
TwoSum(int[] nums, int target)
{
Dictionary<int, int> map = new Dictionary<int, int>();
for (int i =
0; i < nums.Length; i++)
{
int
complement = target - nums[i];
if
(map.ContainsKey(complement))
{
return
new int[] { map[complement], i };
}
map[nums[i]] = i;
}
return new
int[] { -1, -1 }; // Return default if
no solution
}
}
137. Merge Intervals (Intermediate)
Given a collection of intervals, merge all overlapping
intervals.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int[,]
intervals = { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };
var result =
Merge(intervals);
Console.WriteLine("Merged Intervals: ");
foreach (var
interval in result)
{
Console.WriteLine($"[{interval[0]}, {interval[1]}]");
}
}
static
List<int[]> Merge(int[,] intervals)
{
List<int[]> result = new List<int[]>();
List<int[]> intervalsList = new List<int[]>();
for (int i =
0; i < intervals.GetLength(0); i++)
{
intervalsList.Add(new int[] { intervals[i, 0], intervals[i, 1] });
}
intervalsList.Sort((a, b) => a[0] - b[0]);
foreach (var
interval in intervalsList)
{
if
(result.Count == 0 || result[result.Count - 1][1] < interval[0])
{
result.Add(interval);
}
else
{
result[result.Count
- 1][1] = Math.Max(result[result.Count - 1][1], interval[1]);
}
}
return result;
}
}
138. Count and Say (Advanced)
The "count-and-say" sequence is a sequence of
digits, where each term is obtained by reading the previous term, grouping the
digits in pairs of the same digit, and counting the occurrences.
For example:
- 1 is
"one 1" → 11
- 11 is
"two 1s" → 21
- 21 is
"one 2, one 1" → 1211
Write a program to generate the nth term of the
count-and-say sequence.
using System;
class Program
{
static void Main()
{
int n = 4;
string result
= CountAndSay(n);
Console.WriteLine("Count and Say Sequence: " + result);
}
static string
CountAndSay(int n)
{
string result
= "1";
for (int i =
1; i < n; i++)
{
string
current = "";
char prev
= result[0];
int count
= 1;
for (int j
= 1; j < result.Length; j++)
{
if
(result[j] == prev)
{
count++;
}
else
{
current += count.ToString() + prev;
prev = result[j];
count = 1;
}
}
current +=
count.ToString() + prev;
result =
current;
}
return result;
}
}
139. Sum of Two Integers (Intermediate)
Without using the + or - operator, write
a program to compute the sum of two integers.
using System;
class Program
{
static void Main()
{
int a = 5, b =
7;
int result =
GetSum(a, b);
Console.WriteLine("Sum: " + result);
}
static int
GetSum(int a, int b)
{
while (b != 0)
{
int carry
= a & b;
a = a ^ b;
b = carry
<< 1;
}
return a;
}
}
140. Longest Common Prefix (Intermediate)
Write a program to find the longest common prefix string
amongst an array of strings.
using System;
class Program
{
static void Main()
{
string[] strs
= { "flower", "flow", "flight" };
string prefix
= LongestCommonPrefix(strs);
Console.WriteLine("Longest Common Prefix: " + prefix);
}
static string
LongestCommonPrefix(string[] strs)
{
if
(strs.Length == 0) return "";
string prefix
= strs[0];
foreach (var
str in strs)
{
while
(str.IndexOf(prefix) != 0)
{
prefix
= prefix.Substring(0, prefix.Length - 1);
if
(prefix == "")
return "";
}
}
return prefix;
}
}
141. Valid Anagram (Beginner)
Given two strings s and t, return true
if t is an anagram of s. Otherwise, return false.
using System;
class Program
{
static void Main()
{
string s =
"anagram";
string t =
"nagaram";
bool isAnagram
= IsAnagram(s, t);
Console.WriteLine(isAnagram ? "Valid Anagram" : "Not an
Anagram");
}
static bool
IsAnagram(string s, string t)
{
if (s.Length
!= t.Length) return false;
int[] count =
new int[26];
foreach (char
c in s)
{
count[c -
'a']++;
}
foreach (char
c in t)
{
if
(--count[c - 'a'] < 0)
return
false;
}
return true;
}
}
142. Find Missing Number (Intermediate)
Given an array of n numbers in the range from 1
to n+1, with one number missing, find the missing number.
using System;
class Program
{
static void Main()
{
int[] nums = {
1, 2, 4, 5, 6 };
int
missingNumber = FindMissingNumber(nums);
Console.WriteLine("Missing Number: " + missingNumber);
}
static int
FindMissingNumber(int[] nums)
{
int n =
nums.Length + 1;
int sum = n *
(n + 1) / 2;
foreach (var
num in nums)
{
sum -=
num;
}
return sum;
}
}
143. Majority Element (Intermediate)
Given an integer array, find the majority element, which is
the element that appears more than n / 2 times. Assume the majority
element always exists.
using System;
class Program
{
static void Main()
{
int[] nums = {
3, 2, 3 };
int
majorityElement = FindMajorityElement(nums);
Console.WriteLine("Majority Element: " + majorityElement);
}
static int
FindMajorityElement(int[] nums)
{
int count = 0,
candidate = 0;
foreach (var
num in nums)
{
if (count
== 0)
{
candidate = num;
}
count +=
(num == candidate) ? 1 : -1;
}
return
candidate;
}
}
144. Find All Duplicates in an Array (Intermediate)
Given an integer array, find all elements that appear twice
in the array.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int[] nums = {
4, 3, 2, 7, 8, 2, 3, 1 };
var duplicates
= FindDuplicates(nums);
Console.WriteLine("Duplicates: " + string.Join(", ",
duplicates));
}
static
List<int> FindDuplicates(int[] nums)
{
List<int> result = new List<int>();
HashSet<int> seen = new HashSet<int>();
foreach (var
num in nums)
{
if
(seen.Contains(num))
{
result.Add(num);
}
else
{
seen.Add(num);
}
}
return result;
}
}
145. Remove Element (Beginner)
Given an array and a value val, remove all occurrences
of val in the array, and return the new length of the array.
using System;
class Program
{
static void Main()
{
int[] nums = {
3, 2, 2, 3 };
int val = 3;
int length =
RemoveElement(nums, val);
Console.WriteLine("New Length: " + length);
}
static int
RemoveElement(int[] nums, int val)
{
int k = 0;
foreach (var
num in nums)
{
if (num !=
val)
{
nums[k++] = num;
}
}
return k;
}
}
146. Swap Nodes in Pairs (Intermediate)
Given a linked list, swap every two adjacent nodes and
return its head. You must solve it in one pass.
using System;
class ListNode
{
public int val;
public ListNode
next;
public
ListNode(int val = 0, ListNode next = null)
{
this.val =
val;
this.next =
next;
}
}
class Program
{
static void Main()
{
ListNode head
= new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
ListNode
newHead = SwapPairs(head);
Console.WriteLine("Swapped List: ");
while (newHead
!= null)
{
Console.Write(newHead.val + " ");
newHead =
newHead.next;
}
}
static ListNode
SwapPairs(ListNode head)
{
if (head ==
null || head.next == null) return head;
ListNode
newHead = head.next;
ListNode prev
= null;
ListNode
current = head;
while (current
!= null && current.next != null)
{
ListNode
nextPair = current.next.next;
ListNode
second = current.next;
second.next = current;
current.next = nextPair;
if (prev
!= null)
{
prev.next = second;
}
prev =
current;
current =
nextPair;
}
return
newHead;
}
}
147. Reverse Linked List (Beginner)
Reverse a singly linked list.
using System;
class ListNode
{
public int val;
public ListNode
next;
public
ListNode(int val = 0, ListNode next = null)
{
this.val =
val;
this.next =
next;
}
}
class Program
{
static void Main()
{
ListNode head
= new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new
ListNode(5)))));
ListNode
reversedHead = ReverseList(head);
Console.WriteLine("Reversed List: ");
while
(reversedHead != null)
{
Console.Write(reversedHead.val + " ");
reversedHead = reversedHead.next;
}
}
static ListNode
ReverseList(ListNode head)
{
ListNode prev
= null, current = head, next = null;
while (current
!= null)
{
next =
current.next;
current.next = prev;
prev =
current;
current =
next;
}
return prev;
}
}
148. Count Primes (Intermediate)
Count the number of prime numbers less than a given
number n.
using System;
class Program
{
static void Main()
{
int n = 10;
int primeCount
= CountPrimes(n);
Console.WriteLine("Number of Primes Less Than " + n + ":
" + primeCount);
}
static int
CountPrimes(int n)
{
if (n <= 2)
return 0;
bool[] isPrime
= new bool[n];
Array.Fill(isPrime, true);
isPrime[0] =
isPrime[1] = false;
for (int i =
2; i * i < n; i++)
{
if
(isPrime[i])
{
for
(int j = i * i; j < n; j += i)
{
isPrime[j] = false;
}
}
}
int count = 0;
foreach (var
prime in isPrime)
{
if (prime)
count++;
}
return count;
}
}
149. Product of Array Except Self (Intermediate)
Given an array nums of n numbers, return
an array such that each element at index i is the product of all the
numbers in the array except nums[i].
using System;
class Program
{
static void Main()
{
int[] nums = {
1, 2, 3, 4 };
int[] result =
ProductExceptSelf(nums);
Console.WriteLine("Product Except Self: " +
string.Join(", ", result));
}
static int[]
ProductExceptSelf(int[] nums)
{
int n =
nums.Length;
int[] result =
new int[n];
result[0] = 1;
for (int i =
1; i < n; i++)
{
result[i]
= result[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n
- 2; i >= 0; i--)
{
right *=
nums[i + 1];
result[i]
*= right;
}
return result;
}
}
150. Best Time to Buy and Sell Stock (Intermediate)
Given an array where the ith element is the price of a
given stock on day i, find the maximum profit you can achieve by buying
and selling the stock once.
using System;
class Program
{
static void Main()
{
int[] prices =
{ 7, 1, 5, 3, 6, 4 };
int maxProfit
= MaxProfit(prices);
Console.WriteLine("Max Profit: " + maxProfit);
}
static int
MaxProfit(int[] prices)
{
int minPrice =
int.MaxValue;
int maxProfit
= 0;
foreach (var
price in prices)
{
minPrice =
Math.Min(minPrice, price);
maxProfit
= Math.Max(maxProfit, price - minPrice);
}
return
maxProfit;
}
}
151. Permutations (Intermediate)
Given a collection of distinct integers, return all possible
permutations.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int[] nums = {
1, 2, 3 };
var result =
Permute(nums);
Console.WriteLine("Permutations: ");
foreach (var
perm in result)
{
Console.WriteLine(string.Join(", ", perm));
}
}
static
IList<IList<int>> Permute(int[] nums)
{
List<IList<int>> result = new
List<IList<int>>();
GeneratePermutations(nums, 0, result);
return result;
}
static void
GeneratePermutations(int[] nums, int start, List<IList<int>>
result)
{
if (start ==
nums.Length)
{
result.Add(new List<int>(nums));
return;
}
for (int i =
start; i < nums.Length; i++)
{
Swap(nums,
i, start);
GeneratePermutations(nums, start + 1, result);
Swap(nums,
i, start); // backtrack
}
}
static void
Swap(int[] nums, int i, int j)
{
int temp =
nums[i];
nums[i] =
nums[j];
nums[j] =
temp;
}
}
152. Find Peak Element (Intermediate)
A peak element in an array is an element that is strictly
greater than its neighbors. Given an array, find a peak element.
using System;
class Program
{
static void Main()
{
int[] nums = {
1, 2, 3, 1 };
int
peakElement = FindPeakElement(nums);
Console.WriteLine("Peak Element: " + peakElement);
}
static int
FindPeakElement(int[] nums)
{
int left = 0,
right = nums.Length - 1;
while (left
< right)
{
int mid =
left + (right - left) / 2;
if
(nums[mid] > nums[mid + 1])
right
= mid;
else
left =
mid + 1;
}
return left;
}
}
153. Trapping Rain Water (Advanced)
Given an array representing heights of bars in a histogram,
calculate how much water can be trapped after it rains.
using System;
class Program
{
static void Main()
{
int[] height =
{ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
int
trappedWater = Trap(height);
Console.WriteLine("Trapped Water: " + trappedWater);
}
static int
Trap(int[] height)
{
if (height ==
null || height.Length == 0)
return 0;
int left = 0,
right = height.Length - 1;
int leftMax =
0, rightMax = 0;
int water = 0;
while (left
< right)
{
if
(height[left] < height[right])
{
if
(height[left] >= leftMax)
leftMax = height[left];
else
water += leftMax - height[left];
left++;
}
else
{
if
(height[right] >= rightMax)
rightMax = height[right];
else
water += rightMax - height[right];
right--;
}
}
return water;
}
}
154. Search in Rotated Sorted Array (Advanced)
You are given a rotated sorted array. Write a function to
search for a target element. The array was originally sorted in increasing
order but was rotated.
using System;
class Program
{
static void Main()
{
int[] nums = {
4, 5, 6, 7, 0, 1, 2 };
int target =
0;
int index =
Search(nums, target);
Console.WriteLine("Target Index: " + index);
}
static int
Search(int[] nums, int target)
{
int left = 0,
right = nums.Length - 1;
while (left
<= right)
{
int mid =
left + (right - left) / 2;
if
(nums[mid] == target)
return
mid;
if
(nums[left] <= nums[mid])
{
if
(nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else
{
if
(nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
}
155. Kth Largest Element in an Array (Intermediate)
Given an array of integers, find the kth largest element.
using System;
using System.Linq;
class Program
{
static void Main()
{
int[] nums = {
3, 2, 1, 5, 6, 4 };
int k = 2;
int kthLargest
= FindKthLargest(nums, k);
Console.WriteLine("Kth
Largest Element: " + kthLargest);
}
static int
FindKthLargest(int[] nums, int k)
{
return
nums.OrderByDescending(n => n).ElementAt(k - 1);
}
}
156. Top K Frequent Elements (Advanced)
Given a non-empty array of integers, return the k most
frequent elements.
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
int[] nums = {
1, 1, 1, 2, 2, 3 };
int k = 2;
var
topKElements = TopKFrequent(nums, k);
Console.WriteLine("Top K Frequent Elements: " +
string.Join(", ", topKElements));
}
static
IList<int> TopKFrequent(int[] nums, int k)
{
return
nums.GroupBy(x => x)
.OrderByDescending(g
=> g.Count())
.Take(k)
.Select(g => g.Key)
.ToList();
}
}
157. Longest Substring Without Repeating Characters
(Intermediate)
Given a string s, find the length of the longest
substring without repeating characters.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string s =
"abcabcbb";
int length =
LengthOfLongestSubstring(s);
Console.WriteLine("Length of Longest Substring Without Repeating
Characters: " + length);
}
static int
LengthOfLongestSubstring(string s)
{
HashSet<char> set = new HashSet<char>();
int left = 0,
maxLength = 0;
for (int right
= 0; right < s.Length; right++)
{
while
(set.Contains(s[right]))
{
set.Remove(s[left]);
left++;
}
set.Add(s[right]);
maxLength
= Math.Max(maxLength, right - left + 1);
}
return
maxLength;
}
}
158. String to Integer (atoi) (Advanced)
Implement the atoi function, which converts a
string to an integer. The function should discard any leading whitespaces and
handle overflow.
using System;
class Program
{
static void Main()
{
string str =
"42";
int result =
MyAtoi(str);
Console.WriteLine("Converted Integer: " + result);
}
static int
MyAtoi(string str)
{
int i = 0,
sign = 1, result = 0;
while (i <
str.Length && char.IsWhiteSpace(str[i]))
i++;
if (i <
str.Length && (str[i] == '-' || str[i] == '+'))
{
sign =
(str[i] == '-') ? -1 : 1;
i++;
}
while (i <
str.Length && char.IsDigit(str[i]))
{
int digit
= str[i] - '0';
if (result
> int.MaxValue / 10 || (result == int.MaxValue / 10 && digit >
int.MaxValue % 10))
return
sign == 1 ? int.MaxValue : int.MinValue;
result =
result * 10 + digit;
i++;
}
return result
* sign;
}
}
159. Count and Say Sequence (Advanced)
The "count-and-say" sequence is a sequence of
digits where each term is generated by reading the previous term. Given an
integer n, generate the nth term of the sequence.
using System;
class Program
{
static void Main()
{
int n = 5;
string result
= CountAndSay(n);
Console.WriteLine("Count and Say Sequence: " + result);
}
static string
CountAndSay(int n)
{
string result
= "1";
for (int i =
1; i < n; i++)
{
string
temp = "";
int count
= 1;
for (int j
= 1; j < result.Length; j++)
{
if
(result[j] == result[j - 1])
{
count++;
}
else
{
temp += count.ToString() +
result[j - 1];
count = 1;
}
}
temp +=
count.ToString() + result[result.Length - 1];
result =
temp;
}
return result;
}
}
160. Valid Parentheses (Intermediate)
Given a string containing just the characters (, ), {, }, [ and ],
determine if the input string is valid. An input string is valid if the
brackets are closed in the correct order.
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
string s =
"()[]{}";
bool isValid =
IsValid(s);
Console.WriteLine(isValid
? "Valid Parentheses" : "Invalid Parentheses");
}
static bool
IsValid(string s)
{
Stack<char> stack = new Stack<char>();
foreach (var c
in s)
{
if (c ==
'(' || c == '{' || c == '[')
stack.Push(c);
else
{
if
(stack.Count == 0)
return false;
char
top = stack.Pop();
if ((c
== ')' && top != '(') || (c
== '}' && top != '{') || (c == ']' && top !=
'[')) return false; } }
return stack.Count
== 0;
}
}
Comments
Post a Comment