[PYTHON] LeetCode I tried to summarize the simple ones

LeetCode I tried to summarize the simple ones

A summary of the problem statement, Java and Python code is posted.

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;

Summary

making...

Recommended Posts

LeetCode I tried to summarize the simple ones
I tried to summarize the umask command
I tried to summarize the graphical modeling.
I tried to summarize SparseMatrix
I tried to summarize the basic form of GPLVM
I tried to summarize the string operations of Python
I tried to move the ball
I tried to estimate the interval.
[First COTOHA API] I tried to summarize the old story
I tried to summarize the commands often used in business
[Machine learning] I tried to summarize the theory of Adaboost
I tried to summarize how to use the EPEL repository again
I tried to summarize Python exception handling
I tried to recognize the wake word
Python3 standard input I tried to summarize
I tried to estimate the pi stochastically
I tried to touch the COTOHA API
I tried to summarize Ansible modules-Linux edition
[Linux] I tried to summarize the command of resource confirmation system
I tried to summarize the commands used by beginner engineers today
I tried to summarize the frequently used implementation method of pytest-mock
I tried web scraping to analyze the lyrics.
[Python] I tried to summarize the set type (set) in an easy-to-understand manner.
I tried to summarize until I quit the bank and became an engineer
I tried to summarize the general flow up to service creation by self-education.
I tried to touch the API of ebay
I tried to correct the keystone of the image
I tried to summarize various sentences using the automatic summarization API "summpy"
I tried to debug.
I tried to summarize the logical way of thinking about object orientation.
I tried to paste
Qiita Job I tried to analyze the job offer
I tried to summarize the Linux commands used by beginner engineers today-Part 1-
I tried to implement the traveling salesman problem
I tried to predict the price of ETF
I tried to vectorize the lyrics of Hinatazaka46!
I tried to summarize the relationship between probability distributions starting from the Bernoulli distribution
I tried to summarize the settings for various databases of Django (MySQL, PostgreSQL)
I tried to summarize the operations that are likely to be used with numpy-stl
I didn't understand the Resize of TensorFlow so I tried to summarize it visually.
I tried to learn the sin function with chainer
I tried to graph the packages installed in Python
I tried to detect the iris from the camera image
I tried to predict the J-League match (data analysis)
I tried to solve the soma cube with python
I tried to approximate the sin function using chainer
I tried to summarize four neural network optimization methods
I tried to put pytest into the actual battle
[Python] I tried to graph the top 10 eyeshadow rankings
I tried to visualize the spacha information of VTuber
I tried to summarize how to use pandas in python
I tried to solve the problem with Python Vol.1
I tried to simulate the dollar cost averaging method
I tried to identify the language using CNN + Melspectogram
I tried to notify the honeypot report on LINE
I tried to complement the knowledge graph using OpenKE
I tried to classify the voices of voice actors
I tried to compress the image using machine learning
I tried to learn PredNet
I tried to organize SVM.
I tried to implement PCANet