[PYTHON] LeetCode Ich habe versucht, die einfachen zusammenzufassen

LeetCode Ich habe versucht, die einfachen zusammenzufassen

Eine Zusammenfassung der Problemstellung, des Java- und Python-Codes.

Contains Duplicate Description

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1] Output: true

Example 2:

Input: [1,2,3,4] Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2] Output: true

Solution Code

solution.java


// return true if there are dup items in array
// pre: nums[1,2,3,1]
// post: true
public boolean containsDuplicate(int[] nums) {
    // corner case: if nums.length <= 1, return false 
    if (nums.length <= 1) return false;
    
    Map<Integer, Boolean> map = new HashMap<>();
    // single linear scan left -> right, build hashMap as we go
    for (int num : nums) {
        // if map.containsKey(nums[i]) == true, then dup found so return true
        if (map.containsKey(num)) return true;
        
        map.put(num, true);
    }
    
    // return false
    return false;
}

solution.py


class Solution:
    # return true if nums[] contains duplicate
    # pre: nums[1,2,3,1]
    # post: true
    def containsDuplicate(self, nums: List[int]) -> bool:
        # corner case: nums is empty or size 1, return false
        if len(nums) <= 1:
            return False;
        
        # step1: single linear scan left -> right, build hashMap as we go
        map = {}
        
        for num in nums:
            # step 2: if map.containsKey(nums[i]) == true, then dup found so return true
            if num in map:
                return True;
            
            map[num] = True
        
        return False;

First Unique Character in a String Description

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

s = "leetcode" return 0.

s = "loveleetcode" return 2.

Note: You may assume the string contains only lowercase English letters. Solution Code

solution.java


// return index of first char that is unique
// pre: s="leetcode"
// post: 0
public int firstUniqChar(String s) {
    // corner case: if s.length <=1, return 0
    if (s.length() == 1) return 0;
    
    Map<Integer, Integer> map = new HashMap<>();
    
    // need to scan all the chars and keep count of occurrence
    for (char c : s.toCharArray()) {
        if (!map.containsKey((int) c)) {
            map.put((int) c, 1);
        }
        else {
            map.put((int) c, map.get((int) c) + 1); // increment count
        }
    }
    
    // second pass: need to go through string again to return index 
    for (int i = 0; i < s.length(); i++) {
        if (map.get((int) s.charAt(i)) == 1) {
            return i;
        }
    }
    
    return -1;
}

solution.py


class Solution:
    # return index of first unique char in array
    # pre: s = "leetcode"
    # post: 0
    def firstUniqChar(self, s: str) -> int:    
        map = {}
        
        # step1: single linear scan left -> right
        for char in s:
            if char in map:
                map[char] = map[char] + 1
            else:
                map[char] = 1
 
        # step 2: second pass, need to go through string again to return index 
        for i in range(0, len(s)):
            if map[s[i]] == 1:
                return i
        
        return -1

Two Sum Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Solution Code

solution.java


public int[] twoSum(int[] nums, int target) {
    // clarification: guaranteed to have a pair sums up to target
    int[] result = new int[2];
    
    // logic: single linear scan left-right - nums[0...i...N-1]
    Map<Integer, Integer> hashmap = new HashMap<>();
    // test case: [2,7,1], target=3
    for (int i = 0; i < nums.length; i++) {
        // if nums[i] is in hashMap or hashMap.contains(target - nums[i]), then found it, need to return indeces so return [i, hashMap.get(nums[i])]
        if (hashmap.containsKey(nums[i])) {
            result[0] = hashmap.get(nums[i]);
            result[1] = i;
            break;
        }
        
        // else, put target-nums[i] and i as key-value as Entry(diff, index)
        hashmap.put(target - nums[i], i);
    }
    
    return result;
}

solution.py


class Solution:
    # return indeces of two items summing up to target
    # pre: nums[2,7,11,15],target=9
    # post: [0,1]
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        results = []
        map = {}
        
        # step1: linear scan array left -> right, and build map       
        for i in range(0, len(nums)):
            # step 2: check if (target - nums[i]) exists in hashmap, if so return two indices
            complement = target - nums[i]
            if complement in map:
                # return indeces
                results.append(map[complement])
                results.append(i)
            else:
                # step 3: else, add (nums[i], i) to hashmap
                map[nums[i]] = i
        
        return results;

Reverse String Description

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

Example 1:

Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

Solution Code

solution.java


// reverse chars in array in-place
// pre: chars[dog]
// post: chars[god]
public void reverseString(char[] s) {
    // input check: if empty, return s
    if (s.length == 0) return;
    
    // run front & end indeces toward the middle and swap
    int front = 0;
    int end = s.length - 1;
    // test1: char[d,o,g], front=0, end=2
    // test2: char[d,o], front=0, end=1
    while (front < end) {
        char tmp = s[front];
        s[front] = s[end];
        s[end] = tmp;
        
        front++;
        end--;
        
        // test1: char[g,o,d], front=1, end=1
        // test2: char[o,d], front=1, end=0
    }
}

solution.py


class Solution:
    # reverse chars in string in place
    # pre: s="dog"
    # post: s="god"
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def swap(s: List[str], front: int, end: int):
            tmp = s[front]
            s[front] = s[end]
            s[end] = tmp
            
        # step1: run front & end indeces toward the middle
        front = 0
        end = len(s) - 1
        
        # testcases: s="", s="a", s="ab", s="abc"
        while front < end:
            # step 2: swap array[front] and array[end]
            swap(s, front, end)
        
            # step 3: move indeces
            front += 1
            end -= 1

Move Zeroes Description

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12] Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array. Minimize the total number of operations.

Solution Code

solution.java


// move zeros to the end while maintaining non-zero item's order
// pre: nums[0,1,0,3,12]
// post: nums[1,3,12,0,0]
public void moveZeroes(int[] nums) {
    // corner case: if nums.length == 0, return it
    if (nums.length == 0) return;
    
    int nonZeroLast = 0;
    int runnerIndex = 0;
    // linear scan left -> right while runnerIndex < nums.length
    while (runnerIndex < nums.length) {
        // split array into two sections, non-zero and zero sections using two indeces
    
        // if nums[runnerIndex] != 0, then swap(nums[nonZeroLast], nums[runnerIndex])
        // test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=0
        // test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=1
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=2
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=3
        if (nums[runnerIndex] != 0) {
            swap(nums, nonZeroLast, runnerIndex);
            
            // advance nonZeroLast only when after swapped
            nonZeroLast++;
        }
    
        // always advance runnerIndex++
        // test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=1
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=2
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=3
        // test case: nums[1,3,0,0,12], nonZeroIndex=2, runner=4
        runnerIndex++;
    }
    
    return;
}
 
private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

solution.py


class Solution:
    # move all zeros toward the end, while maintaining non-zero item order
    # pre: nums[0,1,0,3,12]
    # post: nums[1,3,12,0,0]
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
 
        def swap(nums: List[int], i: int, j: int):
            tmp = nums[i]
            nums[i] = nums[j]
            nums[j] = tmp
 
        # step1: linear scan left -> right while runnerIndex < nums.length
        nonZeroLastIndex = 0
        runner = 0
        
        # testcases: nums[], nums[1], nums[1,3], nums[1,3,0], nums[0], nums[0,3], nums[1,0,3]
        while runner < len(nums):
            # step 2: split array into two sections, non-zero and zero sections using two indeces
        
            # step 3: if nums[runnerIndex] != 0, then swap(nums[nonZeroLast], nums[runnerIndex])
            if nums[runner] != 0:
                swap(nums, nonZeroLastIndex, runner)
                nonZeroLastIndex += 1
 
            runner += 1

Remove Element Description

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution Code

solution.java


// "remove val from array" (move them to end) and return length of non-val-array
// pre: nums[3,2,2,3], val=3
// post: 2, nums[2,2,3,3]
public int removeElement(int[] nums, int val) {
    // corner case: val might not exist
    
    // single linear scan left -> right
    int nonValLastIndex = 0;
    int runner = 0;
    
    // testcase1: nums[3,2,2,3], val=3, nonVal=0, runner=0
    // testcase1: nums[3,2,2,3], val=3, nonVal=0, runner=1
    // testcase1: nums[2,3,2,3], val=3, nonVal=1, runner=2
    // testcase1: nums[2,2,3,3], val=3, nonVal=2, runner=3
    
    // testcase2: nums[3,3], val=3, nonVal=0, runner=0
    // testcase2: nums[3,3], val=3, nonVal=0, runner=1
    
    // testcase3: nums[2,3], val=3, nonVal=0, runner=0
    // testcase3: nums[2,3], val=3, nonVal=1, runner=1
    while (runner < nums.length) {
        // split array into two sections: non-val vs val
        // if nums[runner] == val, then move on
        
        // if nums[runner] != val, swap(nums[nonValLastIndex], nums[runner] )
        if (nums[runner] != val) {
            swap(nums, nonValLastIndex, runner);
            nonValLastIndex++;
        }
        
        runner++;
    }
    
    // return nonValLastIndex
    return nonValLastIndex;
}
 
private void swap(int[] nums, int index1, int index2) {
    int tmp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = tmp;
}

solution.py


class Solution:
    # return length of array section without value
    # pre: nums[3,2,2,3], val=3
    # post: 2 (nums[2,2,3,3])
    def removeElement(self, nums: List[int], val: int) -> int:
        def swap(nums: List[int], i: int, j: int):
            tmp = nums[i]
            nums[i] = nums[j]
            nums[j] = tmp
            
        # step1: linear scan left -> right while runnerIndex < nums.length
        nonValLastIndex = 0
        runner = 0
        
        # testcase: nums[3,2,2,3], val=0
        while runner < len(nums):
            # step 2: split array into two sections, non-val and val sections using two indeces
        
            # step 3: if nums[runnerIndex] != val, then swap(nums[nonValLastIndex], nums[runnerIndex])
            if nums[runner] != val:
                swap(nums, nonValLastIndex, runner)
                nonValLastIndex += 1
            
            runner += 1
        
        return nonValLastIndex;

Zusammenfassung

Herstellung...

Recommended Posts

LeetCode Ich habe versucht, die einfachen zusammenzufassen
Ich habe versucht, den Befehl umask zusammenzufassen
Ich habe versucht, die grafische Modellierung zusammenzufassen.
Ich habe versucht, SparseMatrix zusammenzufassen
Ich habe versucht, die Grundform von GPLVM zusammenzufassen
Ich habe versucht, die String-Operationen von Python zusammenzufassen
Ich habe versucht, den Ball zu bewegen
Ich habe versucht, den Abschnitt zu schätzen.
[Erste COTOHA-API] Ich habe versucht, die alte Geschichte zusammenzufassen
Ich habe versucht, die im Geschäftsleben häufig verwendeten Befehle zusammenzufassen
[Maschinelles Lernen] Ich habe versucht, die Theorie von Adaboost zusammenzufassen
Ich habe versucht zusammenzufassen, wie das EPEL-Repository erneut verwendet wird
Ich habe versucht, die Behandlung von Python-Ausnahmen zusammenzufassen
Ich versuchte das Weckwort zu erkennen
Python3-Standardeingabe habe ich versucht zusammenzufassen
Ich habe versucht, das Umfangsverhältnis π probabilistisch abzuschätzen
Ich habe versucht, die COTOHA-API zu berühren
Ich habe versucht, Ansibles Module-Linux-Edition zusammenzufassen
[Linux] Ich habe versucht, die Ressourcenbestätigungsbefehle zusammenzufassen
Ich habe versucht, die Befehle zusammenzufassen, die Anfängeringenieure heute verwenden
Ich habe versucht, die häufig verwendete Implementierungsmethode von pytest-mock zusammenzufassen
Ich habe Web Scraping versucht, um die Texte zu analysieren.
[Python] Ich habe versucht, den kollektiven Typ (Satz) auf leicht verständliche Weise zusammenzufassen.
Ich versuchte zusammenzufassen, bis ich die Bank verließ und Ingenieur wurde
Ich habe versucht, den allgemeinen Ablauf bis zur Erstellung von Diensten selbst zusammenzufassen.
Ich habe versucht, die Trapezform des Bildes zu korrigieren
Ich habe versucht, verschiedene Sätze mit der automatischen Zusammenfassungs-API "summpy" zusammenzufassen.
Ich habe versucht zu debuggen.
Ich habe versucht, die logische Denkweise über Objektorientierung zusammenzufassen.
Qiita Job Ich habe versucht, den Job zu analysieren
Ich habe versucht, die Linux-Befehle zusammenzufassen, die heute von Anfängeringenieuren verwendet werden - Teil 1-
Ich habe versucht, das Problem des Handlungsreisenden umzusetzen
Ich habe versucht, die Texte von Hinatazaka 46 zu vektorisieren!
Ich habe versucht, die Beziehung zwischen Wahrscheinlichkeitsverteilungen ausgehend von der Bernoulli-Verteilung zusammenzufassen
Ich habe versucht, die Einstellungen für verschiedene Datenbanken von Django (MySQL, PostgreSQL) zusammenzufassen.
Ich habe versucht, die Operationen zusammenzufassen, die wahrscheinlich mit numpy-stl verwendet werden
Ich habe die Größenänderung von TensorFlow nicht verstanden und sie daher visuell zusammengefasst.
Ich habe versucht, die Sündenfunktion mit Chainer zu trainieren
Ich habe versucht, die in Python installierten Pakete grafisch darzustellen
Ich habe versucht, Iris aus dem Kamerabild zu erkennen
Ich habe versucht, das Spiel in der J League vorherzusagen (Datenanalyse)
Ich habe versucht, Soma Cube mit Python zu lösen
Ich habe versucht, die Sündenfunktion mit Chainer zu approximieren
Ich habe versucht, vier Optimierungsmethoden für neuronale Netze zusammenzufassen
Ich habe versucht, Pytest in die eigentliche Schlacht zu bringen
[Python] Ich habe versucht, die Top 10 der Lidschatten grafisch darzustellen
Ich habe versucht, die Spacha-Informationen von VTuber zu visualisieren
Ich habe versucht zusammenzufassen, wie man Pandas von Python benutzt
Ich habe versucht, das Problem mit Python Vol.1 zu lösen
Ich habe versucht, die Methode zur Mittelung der Dollarkosten zu simulieren
Ich habe versucht, die Sprache mit CNN + Melspectogram zu identifizieren
Ich habe versucht, das Wissensdiagramm mit OpenKE zu ergänzen
Ich habe versucht, die Stimmen der Sprecher zu klassifizieren
Ich habe versucht, das Bild mithilfe von maschinellem Lernen zu komprimieren
Ich habe versucht, PredNet zu lernen
Ich habe versucht, SVM zu organisieren.
Ich habe versucht, PCANet zu implementieren