Reverse Linked List
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre = null, cur = null, next = null;
cur = head;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
Reverse Words in a String
public class Solution {
public string ReverseWords(string s)
{
var word_list = new List();
string word = "";
foreach (char ch in s)
{
if (ch != ' ')
{
word += ch;
}
else if (word != "")
{
word_list.Add(word);
word = "";
}
}
if (word != " ") word_list.Add(word);
word_list.Reverse();
return string.Join(" ", word_list);
}
}
Balanced Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public bool IsBalanced(TreeNode root) {
int res = GetRes(root);
return res == -1 ? false:true;
}
public int GetRes(TreeNode node){
if(node == null) return 0;
int leftRes = GetRes(node.left);
if(leftRes == -1) return -1;
int rightRes = GetRes(node.right);
if(rightRes == -1) return -1;
if(Math.Abs(leftRes - rightRes)<= 1){
return Math.Max(leftRes, rightRes)+1;
}
return -1;
}
}
Combinations
public class Solution {
public IList> Combine(int n, int k)
{
IList> res = new List>();
int[] cur = new int[k];
helper(1, 0, k, n, cur, res);
return res;
}
public void helper(int i, int j, int k, int n, int[] cur, IList> res)
{
if (k == j)
{
res.Add(new List(cur));
return;
}
for (int iter = i; iter <= n; ++iter)
{
cur[j] = iter;
helper(iter + 1, j + 1, k, n, cur, res);
}
}
}
Edit Distance
public class Solution {
public int MinDistance(string word1, string word2) {
int len1 = word1.Length;
int len2 = word2.Length;
int[] last_dp = new int[len2+1];
for(int i = 1; i <= len2; ++i) last_dp[i] = i;
for(int i = 1; i <= len1; ++i){
int[] cur_dp = new int[len2+1];
cur_dp[0] = i;
for(int j = 1; j <= len2; ++j){
int rep = word1[i-1] == word2[j-1] ? 0:1;
int insOrdel = Math.Min(last_dp[j], cur_dp[j - 1]) + 1;
cur_dp[j] = Math.Min(insOrdel, last_dp[j - 1] + rep);
}
last_dp = cur_dp;
}
return last_dp[len2];
}
}
Sqrt(x)
public class Solution {
public int MySqrt(int x) {
if(x <= 1) return x;
int start = 0, end = x/2;
int mid = start + (end - start)/2;
long multi = (long)mid*mid;
while(start <= end){
if(multi == x) return mid;
else if(multi < x){
start = mid+1;
} else {
end = mid-1;
}
mid = (end + start) / 2;
multi = (long)mid*mid;
}
return mid;
}
}
Anagrams
public class Solution {
public IList Anagrams(string[] strs) {
IList res = new List();
int len = strs.Length;
var visited = new Dictionary();
for(int i = 0; i <= len-1; ++i){
char[] a = strs[i].ToArray();
Array.Sort(a);
string str = string.Join("", a);
if (visited.ContainsKey(str))
{
if (visited[str] != -1)
{
res.Add(strs[visited[str]]);
visited[str] = -1;
}
res.Add(strs[i]);
}
else
{
visited[str] = i;
}
}
return res;
}
}
Evaluate Reverse Polish Notation
public class Solution {
public int EvalRPN(string[] tokens)
{
var stack = new Stack();
int num1, num2, num;
foreach (var token in tokens)
{
switch (token)
{
case "+":
num1 = stack.Pop();
num2 = stack.Pop();
num = num2 + num1;
break;
case "-":
num1 = stack.Pop();
num2 = stack.Pop();
num = num2 - num1;
break;
case "*":
num1 = stack.Pop();
num2 = stack.Pop();
num = num2 * num1;
break;
case "/":
num1 = stack.Pop();
num2 = stack.Pop();
num = num2 / num1;
break;
default:
num = int.Parse(token);
break;
}
stack.Push(num);
}
return stack.Peek();
}
}
Clone Graph
/**
* Definition for undirected graph.
* public class UndirectedGraphNode {
* public int label;
* public IList neighbors;
* public UndirectedGraphNode(int x) { label = x; neighbors = new List(); }
* };
*/
public class Solution {
public UndirectedGraphNode CloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
var nodeDict = new Dictionary();
return helper(node, nodeDict);
}
public UndirectedGraphNode helper(UndirectedGraphNode node, Dictionary nodeDict){
if(nodeDict.ContainsKey(node)) return nodeDict[node];
var newNode = new UndirectedGraphNode(node.label);
nodeDict[node] = newNode;
foreach(var neighbor in node.neighbors){
newNode.neighbors.Add(helper(neighbor, nodeDict));
}
return newNode;
}
}
Sort Colors
public class Solution {
public void Swap(int[] nums, int ptr1, int ptr2){
int temp = nums[ptr1];
nums[ptr1] = nums[ptr2];
nums[ptr2] = temp;
}
public void SortColors(int[] nums) {
int len = nums.Length;
int ptr1 = 0, ptr2 = 0;
while (ptr2 <= len - 1)
{
if (nums[ptr2] == 0 && nums[ptr1] != 0) Swap(nums, ptr1, ptr2);
if (nums[ptr1] == 0) ++ptr1;
++ptr2;
}
ptr1 = ptr2 = len - 1;
while (ptr2 >= 0)
{
if (nums[ptr2] == 2 && nums[ptr1] != 2) Swap(nums, ptr1, ptr2);
if (nums[ptr1] == 2) --ptr1;
--ptr2;
}
}
}
Reverse Bits
public class Solution {
public uint reverseBits(uint n) {
uint res = n&1;
n >>= 1;
for(int i = 0; i <= 30; ++i){
res <<= 1;
res |= n&1;
n >>= 1;
}
return res;
}
}
Binary Tree Zigzag Level Order Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public IList> ZigzagLevelOrder(TreeNode root) {
var res = new List>();
helper(res, root, 0);
for (int i = 1; i <= res.Count / 2; ++i)
{
int idx = (i - 1) * 2 + 1;
var list = (List)res[idx];
list.Reverse();
}
return res;
}
public void helper(List> res, TreeNode node, int depth){
if(node == null) return;
if(depth == res.Count){
res.Add(new List());
}
res[depth].Add(node.val);
++depth;
helper(res, node.left, depth);
helper(res, node.right, depth);
}
}