LeetCode簡単なのをまとめてみた

#LeetCode簡単なのをまとめてみた
問題文の概要,JavaとPythonのコードを載せてあります.

#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
```java: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;
}

```
```python: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
```java: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;
}
```
```python: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
```java: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;
}
```
```python: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
```java: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
    }
}
```
```python: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

```java: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;
}
```

```python: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

```java: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;
}
```

```python: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;
```

#まとめ
作成中...