public class Solution {
public int RemoveDuplicates(int[] nums) {
if (nums == null || nums.Length == 0)
{
return 0;
}
int fast = 1;
int slow = 0;
while (fast < nums.Length)
{
if (nums[fast] == nums[slow])
{
fast++;
continue;
}
slow++;
nums[slow] = nums[fast];
fast++;
}
return slow+1;
}
}
Wednesday, August 24, 2016
Leetcode 26. Remove Duplicates from Sorted Array
Tuesday, August 23, 2016
Leetcode 22. Generate Parentheses
public class Solution { public IList<string> GenerateParenthesis(int n) { List<string> ret = new List<string>(); string current = ""; helper(n, 0, 0, current, ret); return ret; } void helper(int n, int leftcount, int rightcount, string current, List<string> ret) { if (leftcount + rightcount == n * 2) { ret.Add(current); return; } if (leftcount < n) { helper(n, leftcount+1, rightcount, current + "(", ret); } if (rightcount <leftcount) { helper(n, leftcount, rightcount + 1, current + ")", ret); } } }
Leetcode 15. 3Sum
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
List<IList<int>> ret = new List<IList<int>>();
if (nums == null || nums.Length < 3)
{
return ret;
}
Array.Sort(nums);
int a = 0;
HashSet<string> hash = new HashSet<string>();
while (a <= nums.Length - 3)
{
if (a > 0 && nums[a] == nums[a-1])
{
a++;
continue;
}
int b = a + 1;
int c = nums.Length - 1;
while (b < c)
{
int sum = nums[a] + nums[b] + nums[c];
string array = String.Join(",", new int[3]{nums[a], nums[b], nums[c]});
if (sum == 0 && !hash.Contains(array))
{
List<int> res = new List<int>();
res.Add(nums[a]);
res.Add(nums[b]);
res.Add(nums[c]);
hash.Add(array);
ret.Add(res);
b++;
c--;
}
else if (sum < 0)
{
b++;
}
else
{
c--;
}
}
a++;
}
return ret;
}
}
Leetcode 11. Container With Most Water
public class Solution {
public int MaxArea(int[] height) {
if (height == null)
{
return 0;
}
int start = 0;
int end = height.Length - 1;
int max = 0;
while (start < end)
{
int current = (end - start) * Math.Min(height[start], height[end]);
max = Math.Max(max, current);
if (height[start] < height[end] && end > start + 1)
{
start++;
continue;
}
if (height[start] > height[end] && end - 1 > start)
{
end--;
continue;
}
start++;
end--;
}
return max;
}
}
Leetcode 199. Binary Tree Right Side View
/**
* 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<int> RightSideView(TreeNode root) {
List<int> ret = new List<int>();
if (root == null)
{
return ret;
}
List<TreeNode> list = new List<TreeNode>();
list.Add(root);
while (list.Count > 0)
{
// Get children of all items from the list, and keep record of the last one
List<TreeNode> newlist = new List<TreeNode>();
foreach(TreeNode item in list)
{
if (item.left != null)
{
newlist.Add(item.left);
}
if (item.right != null)
{
newlist.Add(item.right);
}
}
TreeNode last = list[list.Count - 1];
ret.Add(last.val);
list = newlist;
}
return ret;
}
}
Monday, August 22, 2016
Leetcode 62. Unique Paths
public class Solution {
public int UniquePaths(int m, int n) {
if (m < 1 || n < 1)
{
return 0;
}
int[] dp = new int[n];
for (int i = 0; i < n; i++)
{
dp[i] = 1;
}
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
}
Leetcode 20. Valid Parentheses
public class Solution {
public bool IsValid(string s) {
if (s == null)
{
return false;
}
char[] a = s.ToCharArray();
List<char> stack = new List<char>();
foreach(char c in a)
{
if (c =='(' || c=='[' || c=='{')
{
stack.Add(c);
}
else
{
if (c==')')
{
if (stack.Count ==0 || stack[stack.Count - 1] != '(')
{
return false;
}
stack.RemoveAt(stack.Count - 1);
}
if (c==']')
{
if (stack.Count ==0 || stack[stack.Count - 1] != '[')
{
return false;
}
stack.RemoveAt(stack.Count - 1);
}
if (c=='}')
{
if (stack.Count ==0 || stack[stack.Count - 1] != '{')
{
return false;
}
stack.RemoveAt(stack.Count - 1);
}
}
}
if (stack.Count != 0)
{
return false;
}
return true;
}
}
Leetcode 77. Combinations
public class Solution {
public IList<IList<int>> Combine(int n, int k) {
List<IList<int>> ret = new List<IList<int>>();
if (n <= 0 || n < k)
{
return ret;
}
List<int> path = new List<int>();
dfs(n, k, 0, path, ret);
return ret;
}
public void dfs(int n, int k, int index, List<int> path, List<IList<int>> ret)
{
if (path.Count == k)
{
List<int> res = new List<int>(path);
ret.Add(res);
return;
}
for (int i = index; i < n; i++)
{
path.Add(i + 1);
dfs(n, k, i+1, path, ret);
path.RemoveAt(path.Count - 1);
}
}
}
Leetcode 112. Path Sum
/**
* 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 HasPathSum(TreeNode root, int sum) {
if (root == null)
{
return false;
}
List<int> list = calculate(root, sum);
return list.Contains(sum);
}
List<int> calculate(TreeNode root, int sum)
{
List<int> list = new List<int>();
if (root.left == null && root.right == null)
{
list.Add(root.val);
}
if (root.left != null)
{
foreach (int num in calculate(root.left, sum))
{
list.Add(root.val + num);
}
}
if (root.right != null)
{
foreach (int num in calculate(root.right, sum))
{
list.Add(root.val + num);
}
}
return list;
}
}
Leetcode 46. Permutations
public class Solution {
public IList<IList<int>> Permute(int[] nums) {
List<IList<int>> ret = new List<IList<int>>();
if (nums == null || nums.Length == 0)
{
return ret;
}
List<int> res = new List<int>();
bool[] used = new bool[nums.Length];
doPermute(nums, 0, used, res, ret);
return ret;
}
private void doPermute(int[] nums, int step, bool[] used, List<int> res, List<IList<int>> ret)
{
if (step == nums.Length)
{
List<int> temp = new List<int>(res);
ret.Add(temp);
return;
}
for (int i = 0; i < nums.Length; i++)
{
if (!used[i])
{
used[i] = true;
res.Add(nums[i]);
doPermute(nums, step + 1, used, res, ret);
res.RemoveAt(res.Count - 1);
used[i] = false;
}
}
}
}
Sunday, August 21, 2016
Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal
Answer:
/**
* 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 TreeNode BuildTree(int[] inorder, int[] postorder) {
return helper(inorder, 0, inorder.Length - 1, postorder, 0, postorder.Length - 1);
}
TreeNode helper(int[] inorder, int istart, int iend, int[] postorder, int pstart, int pend)
{
for (int i = istart; i <= iend; i++)
{
// Find the root from inorder array
if (inorder[i] == postorder[pend])
{
TreeNode root = new TreeNode(inorder[i]);
root.left = helper(inorder, istart, i - 1, postorder, pstart, pstart + i - 1 - istart);
root.right = helper(inorder, i + 1, iend, postorder, pend-1 - (iend-i-1), pend - 1);
return root;
}
}
return null;
}
}
Leetcode 90 Subsets II
Answer:
public class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums) {
List<IList<int>> ret = new List<IList<int>>();
if (nums == null)
{
return ret;
}
// Have to sort first.
Array.Sort(nums);
// Create an empty result and add to ret.
List<int> start = new List<int>();
ret.Add(start);
// Resursive backtrack.
helper(nums, 0, start, ret);
return ret;
}
void helper(int[] nums, int step, List<int> current, List<IList<int>> ret)
{
for(int i = step; i < nums.Length; i++)
{
// Remove dup. The same case has been accounted for in a previous iteration.
if (i > step && nums[i] == nums[i-1])
{
continue;
}
current.Add(nums[i]);
ret.Add(new List<int>(current));
helper(nums, i + 1, current, ret);
current.RemoveAt(current.Count - 1);
}
}
}
Leetcode 78. Subsets
Answer 1:
public class Solution {
public IList<IList<int>> Subsets(int[] nums) {
List<IList<int>> ret = new List<IList<int>>();
if (nums == null)
{
return ret;
}
//Array.Sort(nums);
List<int> cur = new List<int>();
helper(nums, 0, cur, ret);
return ret;
}
void helper(int[] nums, int step, List<int> cur, List<IList<int>> ret)
{
ret.Add(new List<int>(cur));
for (int i = step; i < nums.Length; i++)
{
cur.Add(nums[i]);
helper(nums, i+1, cur, ret);
cur.RemoveAt(cur.Count - 1);
}
}
}
public class Solution {
public IList<IList<int>> Subsets(int[] nums) {
List<IList<int>> ret = new List<IList<int>>();
if (nums == null)
{
return ret;
}
List<int> start = new List<int>();
ret.Add(start);
helper(nums, ret);
return ret;
}
void helper(int[] nums, List<IList<int>> ret)
{
for (int i = 0; i < nums.Length; i++)
{
List<IList<int>> newResults = new List<IList<int>>();
foreach(var prev in ret)
{
List<int> newlist = new List<int>(prev);
newlist.Add(nums[i]);
newResults.Add(newlist);
}
ret.AddRange(newResults);
}
}
}
Leetcode 129. Sum Root to Leaf Numbers
Answer 1:
/**
* 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 int SumNumbers(TreeNode root) {
if (root == null)
{
return 0;
}
List<string> list = helper(root);
int sum = 0;
foreach(string s in list)
{
sum += Int32.Parse(s);
}
return sum;
}
List<string> helper(TreeNode root)
{
List<string> list = new List<string>();
if (root.left == null && root.right == null)
{
list.Add("" + root.val);
}
if (root.left != null)
{
List<string> left = helper(root.left);
foreach (string s in left)
{
list.Add(root.val + s);
}
}
if (root.right != null)
{
List<string> right = helper(root.right);
foreach (string s in right)
{
list.Add(root.val + s);
}
}
return list;
}
}
/**
* 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 int SumNumbers(TreeNode root) {
if (root == null)
{
return 0;
}
List<string> list = new List<string>();
string cur = "";
helper(root, cur, list);
int sum = 0;
foreach(string s in list)
{
sum += Int32.Parse(s);
}
return sum;
}
void helper(TreeNode root, string cur, List<string> list)
{
if (root.left == null && root.right == null)
{
cur += root.val;
list.Add(cur);
return;
}
if (root.left != null)
{
helper(root.left, cur + root.val, list);
}
if (root.right != null)
{
helper(root.right, cur + root.val, list);
}
}
}
Subscribe to:
Comments (Atom)