LeetCode задачи и решения

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Solution 1(Brute Force)



class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        var searchedFirstIndex = 0
        for (i in 0..nums.size-1){
            for(j in 1..nums.size-1){
                if(((nums[i] + nums[j])==target))
                    return intArrayOf(i, j)
            }
            
        } 
        return intArrayOf(0, 0)
    }
}

Solution 2(HashMap) – Intelligence



fun twoSum(nums: IntArray, target: Int): IntArray {
    var indexMap = HashMap<Int,Int>()
    for(i in 0..nums.size){
        var requiredNum = target - nums[i]
        if(indexMap.containsKey(requiredNum)){
           return intArrayOf(indexMap.get(requiredNum)!!, i)
        }
        indexMap.put(nums[i], i)
    }
    return intArrayOf(0, 0)
}

 

2. Add Two Numbers

 

Нам даны два не пустых связанных списка, которые представлены не отрицательными числами. Числа представлены в обратном порядке, и каждый из узлов содержит число. Необходимо сложить два числа и вернуть сумму в виде связанного списка.

Мы можем быть уверены, что любое из двух чисел не содержит ноль.

Пример данных на входе:

 l1 = [2,4,3], l2 = [5,6,4]

Результат:

 [7,0,8]

Решение:

342 + 465 = 807.

Задача хоть и идет с уровнем сложности средний, на самом деле не представляет каких то сложностей. Первый элемент в списке представляет собой первый разряд числа, второй элемент
представляет собой десяток, третья цифра сотни и т.д.

Решение:

1. Обходим связанные списки
2. В Каждой итерации добавляем числа в связанный список
3. Если списки не одинаковы(в плане длины), то меньший закончится раньше большего. В этом случае поместим оставшиеся узлы большего списка.
4. Если сумма двух чисел окажется больше 9, вводим дополнительную переменную, carry, для отслеживания переносимых разрядов.

class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        var head2 = l2
        var head1 = l1
        var head : ListNode? = null
        var temp : ListNode? = null
        var carry = 0
        while(head1!=null || head2!=null){
            var sum = carry
            if(head1!=null){
                sum  += head1.`val`
                head1 = head1.next
            }
            if(head2!=null){
                sum += head2.`val`
                head2 = head2.next
            }
            val node = ListNode(sum%10)
            carry = sum/10
            if(temp==null){
                head = node
                temp = head
            }else{
                temp.next = node
                temp = temp.next
            }
        }
        if(carry>0){
            temp!!.next = ListNode(carry)
        }
        return head
    }
}

и Java решение:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode temp = null;
        int carry = 0;
        while(l1!=null || l2!=null){
            int sum = carry;
            if(l1!=null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                sum += l2.val;
                l2 = l2.next;
            }
            ListNode node = new ListNode(sum%10);
            carry = sum/10;
            if(temp == null){
                temp = head = node;
            }else{
                temp.next = node;
                temp = temp.next;
            }

        }
        if(carry>0){
            temp.next = new ListNode(carry);
        }
        return head;

    }
}