Пётр

Leetcode.com, задача №121. "Лучшее время для покупки и продажи акций"

2019-01-14T08:19:23.687Z

Условие

Дан массив значений стоимости акций. Разрешено сделать одну транзакцию: покупка и продажа. И только в таком порядке. Необходимо вычислить максимальную прибыль, которую можно получить. В противном случае вернуть 0.

Пример №1

Входной массив: [7, 1, 5, 3, 6, 4]

Максимальная прибыль: 5

Объяснение: покупаем акции на второй день по цене 1, продаём - на пятый по цене 6, получается прибыль 5. Продавать по 7 мы не можем, т.к. сначала нужно купить акции.

Пример №2

Входной массив: [7, 6, 4, 3, 1]

Максимальная прибыль: 0

Объяснение: мы не можем в последующие дни купить по цене большей, чем продали в любой день.

Вариант №1 решения

Прежде всего, выразим задачу математически. От нас требуется найти max(price[j] - max[i]) при j > i.

Для начала попробуем простой перебор:

public class Solution {
    public int MaxProfit(int[] prices) {
        int delta;
        int maxProfit = 0;            
        for (int i = 0; i < prices.Length; i++)
        {                
            for (int j = i + 1; j < prices.Length; j++)
            {
                delta = prices[j] - prices[i];
                if (delta > 0)
                    maxProfit = Math.Max(maxProfit, delta);
            }
        }
        return maxProfit;
    }
}

Главный недостаток перебора - время выполнения, которое в данном случае пропорционально n * (n - 1) / 2, где n - количество элементов в массиве. Поэтому временная сложность равняется квадрату количества элементов О(n * n).

Вариант №2

Для решения задачи лучшим способом достаточно одного прохода по массиву. При этом будем отмечать или перезаписывать наименьшее значение и вычислять по отношению к нему разницу со значениями последующих элементов.

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices.Length < 2)
            return 0;

        int maxProfit = 0;
        int minValue = prices[0];
            
        for (int i = 1; i < prices.Length; i++)
        {
            if (prices[i] < minValue)
            {
                minValue = prices[i];
                continue;
            }
            else
            {
                if (prices[i] - minValue > maxProfit)
                    maxProfit = prices[i] - minValue;
            }
        }
        return maxProfit;
    }
}

Временная сложность данного решения - О(n).

Так как на сайте можно смотреть лучшие по быстродействию решения, то свой первоначальный код я немного изменил.

В самом начале добавлена проверка на нулевой массив и массив с одним элементом:

if (prices.Length < 2)
    return 0;

После этой проверки инициализируется переменная minValue нулевым элементом массива. Это позволяет начать цикл for с первого элемента.

В самом цикле после нахождения минимального значения используется ключевое слово continue, немедленно запускающее следующую итерацию.

Установка Microsoft SQL Server Management Studio без интернета

2019-01-14T08:18:41.010Z

В данный момент изучаю Microsoft SQL Server. Для конфигурирования, управления и администрирования всех компонентов этой СУБД (система управления базами данных) используется утилита Management Studio. И понадобилось её установить в отсутствии интернета. Процесс при определённых знаниях несложный, но я на него потратил пару часов. Поэтому делюсь полученными навыками.

1.Устанавливаем Microsoft SQL Server из скаченного заранее файла. Я установил старенькую версию 2012. Её функций более чем достаточно для изучения запросов к базу данных. Во всех окнах во смело жмём "Далее", только при выборе компонентов можно оставить галочки у пунктов "Службы компонента Database Engine", "Репликация SQL Server" и "Пакет SDK средств связи клиента SQL".

2. Запускаем установщик Managment Sudio. Выбираем "Новая установка изолированного экземпляра ..."

3. Добавляем компоненты в существующий экземпляр, созданные при установке в п.1

4. При выборе компонентов ставим галочку "Средства управления - основные".

5. Потом везде жмём "Далее" и готово!

Разбор теста от proglib.io, ч.3

2019-01-14T08:18:04.468Z

17. Что является идентификатором метода при перегрузке?

имя и параметры;
модификаторы доступа, возвращаемый тип и параметры;
~~имя, параметры, возвращаемый тип~~;
параметры и модификаторы доступа.

18. Что означает ключевое слово "params"?

Параметр метода будет принимать переменное число аргументов.
Инициирует передачу аргументов по ссылке.
Ссылается на глобальное пространство имён.
Ссылается на переданные аргументы командной строки.

19. Что из ниже перечисленного не может иметь модификатор "virtual"?

методы;
свойства;
индексаторы;
поля.

20. Какой результат выполнения следующей программы?

public class A
{
    private string name = "Name";

    public void Display()
    {
        Display2(ref name, ref name);
        Console.WriteLine(name);
    }

    public void Display2(ref string x, ref string y)
    {
        Console.WriteLine(name);
        x = "Name 1";
        Console.WriteLine(name);
        y = "Name 2";
        Console.WriteLine(name);
        name = "Name 3";
    }
}
class Program
{
    static void Main(string[] args)
    {
        A overload = new A();
        overload.Display();
        Console.ReadKey();
    }
}

Произойдёт ошибка компиляции.
Name 1 Name 2 Name 3 Name.
Name Name 1 Name 2 Name 3.
Четвёртый вариант.

21. Среди перечисленных конструкций укажите определение индексатора.

string GetName { } { return "Name"; }
string Name [int i]
~~string Name { get { return "Name"; } }~~
string this [int i] { get { return "Name"; } }

P.S. Ничего не знал про индексаторы. Не угадал.

22. Что выведет на экран программа ниже?

class Program
{
    static void Main(string[] args)
    {
        string s;
        s += "string";
        Console.WriteLine(s);
    }
}

~~string~~;
"string";
возникнет ошибка компиляции;
возникнет ошибка времени выполнения.

P.S. Дааа, строки надо инициализировать.

23. Как правильно определять структуры?

~~struct <Имя структуры> () { ... }~~
struct <Имя структуры> (string[ ] args) { ... }
struct { ... }
struct <Имя структуры> { ... }

24. Какой из перечисленных типов не является значимым?

float;
class;
struct;
int.

Разбор теста от proglib.io, ч.2

2019-01-14T08:16:52.066Z

9. Какой будет результат выполнения следующего кода?

public sealed class Car
{
  public readonly int maxSpeed = 0;
  private int currSpeed;
  public Car()
  {
    maxSpeed = 220;
  }
  public Car(int max)
  {
    maxSpeed = max;
  }
  public int Speed
  {
    get { return currSpeed; }
    set
    {
      currSpeed = value;
      if (currSpeed > maxSpeed)
      {
        currSpeed = maxSpeed;
      }
    }
  }
}

public class B : Car
{
  public void Display()
  {
    Console.WriteLine(Speed);
  }
}

class Program
{
  static void Main(string[] args)
  {
    B b = new B();
    b.Speed = 300;
    b.Display();
  }
}

0;
~~220~~;
300;
ошибка на этапе компиляции.

P.S. Не заметил, что class Car запечатанный, а значит class B не может от него наследовать.

10.Можно ли наследовать конструктор и деструктор базового класса?

~~да;~~
нет;
иногда.

P.S. Конструктор базового класса не наследуется, но можно использовать или расширять его через специально слово base.

11. В результате компиляции программы ниже возникнет ошибка, связанная с вызовом метода SomeMethod. Как его правильно вызвать, чтобы программа скомпилировалась?

interface IA
{
  void SomeMethod();
}
  
class A : IA
{
  void IA.SomeMethod()
  {
    Console.WriteLine("Hello");
  }
}
        
class Program
{
  static void Main(string[] args)
  {
    A a = new A();
    a.SomeMethod();
  }        
}

Никак. Ошибки не возникнет.
Использовать оператор as ((a as IA).SomeMethod()).
Использовать оператор is ((a is IA).SomeMethod()).
~~Использовать полное название метода a.IA.SomeMethod()~~.

12. Что выведет программа ниже?

public class A
{
    public A()
    {
        Console.Write("A created; ");
    }
}

public class B : A
{
    private B()
    {
        Console.Write("B created; ");
    }

    public B(string str)
    {
        Console.Write("B created with string: {0}; ", str);
    }
}

public class C : B
{
    public C()
    {
        Console.Write("C created; ");
    }
}

class Program
{
    static void Main(string[] args)
    {
        A ab = new B("parameter");
        A ac = new C();

        Console.ReadKey();
    }        
}

A created; B created with string: parameter; A created; B created; C created;
~~Еще два варианта~~.
Программа не скомпилируется.

P.S. Будет ошибка на этапе компиляции, так как класс С не может наследовать от класса B с конструктором по умолчанию с доступом private.

13. Существует ли возможность отказаться от реализации абстрактного класса в классе наследнике?

Нет, невозможно отказаться от реализации абстрактного класса.
Да, если пометить класс-наследник атрибутом [NonAbstract].
Да, если пометить класс-наследник как абстрактный.
~~Да, достаточно не реализовывать ненужные методы и свойства~~.

14. Что неверно в определении следующих интерфейсов?

public abstract interface IAction
{
    void Move();
}

internal interface IRunAction : IAction
{
    void Run();
}

Интерфейсы не могут иметь модификатор доступа internal.
Интерфейсы не могут иметь модификатор abstract.
Интерфейс IRunAction должен определить метод Move, так как базовый интерфейс IAction является абстрактным.
От абстрактного интерфейса нельзя наследоваться.

P.S. Смекнул, что абстрактный интерфейс - это перебор.

15. Какая из строк вызовет ошибку компиляции?

interface IList
{
    int Count { get; set; }
}

interface ICounter
{
    void Count(int i);
}

interface IListCounter : IList, ICounter { }

class C
{
    void Test(IListCounter x)   // 1
    {
        x.Count(1);             // 2
        x.Count = 1;            // 3
    }
}

public class Program
{
    private static void Main(string[] args)
    {

    }
}

1;
2;
3;
~~никакая, программа рабочая~~.

P.S. В данном случае название метода в приоритете, поэтому будет ошибка в строчке с одноимённым свойством.

16. Какое утверждение об абстрактных методах неверно?

Абстрактный метод неявно представляет собой виртуальный метод.
Объявления абстрактных методов допускаются только в виртуальных классах.
В объявлении абстрактного метода можно использовать статические или виртуальные модификаторы.
Чтобы реализовать абстрактный метод в классе-наследнике, необходимо использовать ключевое слово override.

Разбор теста от proglib.io, ч.1

2019-01-14T08:15:57.290Z

~~Зачёркнутым~~ шрифтом выделены мои неправильные ответы, жирным - верные ответы на вопросы.

ООП поддерживает два вида связывания объектов с кодом методов. Соответствующие методы называются:

виртуальными и абстрактными;
статическими и виртуальными;
~~абстрактными и статическими~~;
публичными и приватными.

P.S. Соответствующие виды связывания: раннее и позднее. Понятия не имел о правильном ответе. Даже после выяснения верного варианта...

2. Какая разница между идентичностью и равенством объектов?

Идентичность означает, что у объектов есть общий неабстрактный предок, а равенство - любой общий предок.
Идентичность означает, что у объектов одинаковые поля, а равенство - что они содержат одинаковые данные.
Идентичность означает, что объекты являются экземпляром одного и того же класса, а равенство - что они содержат одинаковые данные.
Идентичность означает, что две ссылки указывают на один и тот же объект, а равенство - что они содержат одинаковые данные.

3. Какое утверждение верно?

От структуры так же, как и от класса, можно наследоваться.
Если структура или объект класса присваивается новому объекту, то в новую переменную сохраняется копия всех данных.
Структура является размерным типом, а класс - ссылочный.
В структуре нельзя определять конструктор.

4. В чём разница между перегрузкой (overloading) и переопределением (overriding)?

Её не существует. Оба понятия описывают одно и то же явление.
Перегрузка означает наличие двух методов с теми же аргументами, но с различными реализациями. Один из них будет существовать в родительском классе, а другой - в производном или дочернем классе.
Переопределение означает наличие двух или более методов в одном классе с тем же именем, но с разными аргументами.
Ни один из предложенных вариантов не является верным.

P.S. Пункты 2 и 3 являются определениями для переопределения и перегрузки соответственно.

5. Скомпилируется ли программа ниже?

public class A
{
  public string Str { get; protected internal set; } = "Hello";
}
class Program
{
  static void Main(string[] args) 
  {
  A a = new A();
  a.Str += " World";
  Console.WriteLine(a.Str);
  }
}

да;
~~ещё три варианта.~~

P.S. Что-то меня смутил модификатор доступа сеттера свойства Str, и я ответил неверно. Хотя классы и члены классов с модификатором доступаprotected internal доступны из текущей сборки (и из производных классов).

6. Какое из утверждений верно?

У интерфейсов можно объявлять свойства, но без тела у методов доступа свойства.
У интерфейсов нельзя объявлять свойства.
У интерфейсов можно объявлять свойства с помощью ключевого слова "property".
~~У интерфейсов можно объявлять свойства так же, как и у классов.~~

7. Что выведет код?

public class A 
{
  private string str = "Hello";
  public string Str
  {
    set
    {
      str = value;
    }
  }
}
class Program
{
  static void Main(string[] args) 
  {
  A a = new A();
  a.Str = " World";
  Console.WriteLine(a.Str);
  }
}

Hello;
ошибка на этапе компиляции;
~~что-то ещё.~~

P.S. Программа не скомпилируется, т.к. у свойства отсутствует метод для чтения, который необходим при выводе значения свойства в консоль.

8. Какое утверждение неверно?

Свойства позволяют управлять доступом к переменной.
В свойства мы можем вложить дополнительную логику.
В каждом свойстве должны быть get и set блоки.
Благодаря свойствам, реализуется один из принципов ООП - инкапсуляция.