我正在尝试在testdome.com中解决C#编程的问题,但是我发现了有关性能的问题。怎么解决呢?
BinarySearchTree
using System;
public class Node
{
public int Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int value, Node left, Node right)
{
Value = value;
Left = left;
Right = right;
}
}
public class BinarySearchTree
{
public static bool Contains(Node root, int value)
{
Console.WriteLine("value=" + value);
if(root == null)
return false;
else if(root.Value == value)
return true;
else if(root.Value != value)
{
return Contains(root.Left, value) | Contains(root.Right, value);
}
return false;
}
public static void Main(string[] args)
{
Node n1 = new Node(1, null, null);
Node n3 = new Node(3, null, null);
Node n2 = new Node(2, n1, n3);
Console.WriteLine(Contains(n2, 3));
}
}
Performance test on a large tree: Memory limit exceeded
https://www.testdome.com/for-developers/solve-question/7482
TwoSum
using System;
using System.Collections.Generic;
class TwoSum
{
public static Tuple<int, int> FindTwoSum(IList<int> list, int sum)
{
for(int ctr1=0; ctr1<list.Count; ctr1++)
{
for(int ctr2=0; ctr2<list.Count; ctr2++)
{
if ((ctr1 != ctr2) && (list[ctr1]+list[ctr2] == sum))
return new Tuple<int, int>(ctr1, ctr2);
}
}
return null;
}
public static void Main(string[] args)
{
Tuple<int, int> indices = FindTwoSum(new List<int>() { 1, 3, 5, 7, 9 }, 12);
Console.WriteLine(indices.Item1 + " " + indices.Item2);
}
}
Performance test with a large number of elements: Time limit exceeded
https://www.testdome.com/for-developers/solve-question/8125
最佳答案
对于二进制搜索树,testdome.com提供了一个提示:“如果要搜索的值小于节点的值,则可以忽略右子树。”这将内存消耗减少了一半。
public static bool Contains(Node root, int value) {
Console.WriteLine("value=" + value);
if (root == null) {
return false;
}
else if (value == root.Value) {
return true;
}
else if (value < root.Value) {
// Hint 2: If a value being searched for is smaller than the value of the node,
// then the right subtree can be ignored.
return Contains(root.Left, value);
}
else {
return Contains(root.Right, value);
}
return false;
}
对于TwoSum,如果我们假设输入数组中的值是唯一的,则可以使用字典根据其值(在O(1)时间中)查找索引。这与提示“字典可用于存储预先计算的值,这可能允许具有O(N)复杂度的解决方案”有关。// Write a function that, when passed a list and a target sum,
// returns, efficiently with respect to time used,
// two distinct zero-based indices of any two of the numbers,
// whose sum is equal to the target sum.
// If there are no two numbers, the function should return null.
public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) {
if (list.Count < 2) {
return null;
}
// Hint 2: A dictionary can be used to store pre-calculated values,
// this may allow a solution with O(N) complexity.
var indexByValue = new Dictionary<int, int>();
for (var i = 0; i < list.Count; i++) {
var value = list[i];
// ensure that the values used as keys are unique
// this is OK because we only have to return any tuple matching the sum,
// therefore we can ignore any duplicate values
if (!indexByValue.ContainsKey(value)) {
indexByValue.Add(value, i);
}
}
for (var j = 0; j < list.Count; j++) {
var remainder = sum - list[j];
if (indexByValue.ContainsKey(remainder)) {
return new Tuple<int, int> (j, indexByValue[remainder]);
}
}
return null;
}
关于c# - testdome.com中的TwoSum和BinarySearchTree;如何解决警告消息: Performance test?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/42897865/