해보자

문제

• Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
  

  Input: nums1 = [1,3], nums2 = [2]
  Output: 2.00000
  Explanation: merged array = [1,2,3] and median is 2.
  

  Example 2:
  
  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106
• Constraints:
• Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
• Example 1:
• The overall run time complexity should be O(log (m+n)).

https://leetcode.com/problems/median-of-two-sorted-arrays/

풀이

이미 정렬된 두개의 배열을 준다고 하여, 그냥 하나로 합쳐서 풀었다.

코드

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0, j = 0, z = 0;
        
        int[] nums = new int[nums1.length + nums2.length];
        while (i < nums1.length && j < nums2.length) {
            nums[z++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
         
        if (i == nums1.length) {
            for (; z < nums.length; z++) {
                nums[z] = nums2[j++];
            }
        }
        else {
            for (; z < nums.length; z++) {
                nums[z] = nums1[i++];
            }
        }
        
         
        if (nums.length % 2 == 0) {
        	return (double)(nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2;
        }
        else {
        	return nums[nums.length / 2]; 
        }
    }
}

결과

문제

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

풀이

이전에는 String에 넣고, 중복된 문자가 있는 경우 다시 시작했던 index의 다음부터 다시 비교하다 보니 시간과 메모리 소요가 컸다.

최대한 반복하지 않고, 변수도 줄일 생각으로 문제를 다시 한번 풀어보았다.

이번에는, 가면서 중복된 문자가 있을 경우 start를 1증가시켜서 다시 비교해 나가는 방식으로 코드를 작성했다.

substring을 사용하여 현재 index의 문자가 없는 부분까지 start를 증가시킨 후, 다음 index부터 비교하도록 하여 반복 시간과 메모리 사용량을 줄였다.

코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int start = 0;
        int idx = 0;
        int maxlength = 0;
        
        while(idx < s.length()) {
        	if(start > idx) {
        		break;
        	}
        	
        	if(!s.substring(start, idx).contains(""+s.charAt(idx))) {
        		idx++;
        		maxlength = (maxlength - (idx - start) > 0) ? maxlength : (idx - start);
        		continue;
        	}
        	
        	start++;
        }
        
        return maxlength;
    }
}

결과

• AS-IS

• TO-BE

문제

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

풀이

하나씩 비교해 가면서 중복된 문자가 있을 경우, start를 1증가시켜서 다시 비교해 나가는 방식으로 코드를 작성했다.

임시로 String을 저장해 놓고 중복된 문자가 있는 경우 기존 문자열(res)보다 큰 경우에 res에 저장하도록 했는데, 문제를 풀기는 했지만 속도와 메모리를 너무 많이 사용한다.

한번의 loop로 끝낼 수 있는 방법을 찾아서 다시 한번 해봐야겠다.

코드

class Solution {
	public int lengthOfLongestSubstring(String s) {
		String res = "";
		String tmp = "";
        
		int start = 0;
		int idx = 0;
        
		while(idx < s.length()) {
			if(start > idx) {
				break;
			}
			if(!tmp.contains("" + s.charAt(idx))) {
				tmp += s.charAt(idx++);
				if(tmp.length() > res.length()) res = tmp.toString();
				continue;
			}
			start++;
			idx = start;
			tmp = "";
		}
        
		return res.length();
	}
}

결과

문제

• Given an integer x, return true if x is palindrome integer.
  • For example, 121 is a palindrome while 123 is not.
  
  

  Input: x = 121
  Output: true
  Explanation: 121 reads as 121 from left to right and from right to left.
  

  Example 2:Example 3:
  
  • -231 <= x <= 231 - 1
• Constraints:
• Input: x = 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
• Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
• Example 1:
• An integer is a palindrome when it reads the same backward as forward.

https://leetcode.com/problems/palindrome-number/

풀이

x값을 String으로 변경하여 Stirng을 reverse 시킨 값과 비교하도록 했다.

코드

class Solution {
	public boolean isPalindrome(int x) {
		String s = Integer.toString(x);
		StringBuilder sb = new StringBuilder(Integer.toString(x));
        
		return s.equals(sb.reverse().toString());
	}
}

결과

문제

• You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
  

  

  Input: l1 = [2,4,3], l2 = [5,6,4]
  Output: [7,0,8]
  Explanation: 342 + 465 = 807.
  

  Example 2:Example 3:
  
  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.
• Constraints:
• Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
• Input: l1 = [0], l2 = [0] Output: [0]
• Example 1:
• You may assume the two numbers do not contain any leading zero, except the number 0 itself.

https://leetcode.com/problems/add-two-numbers/

풀이

return용 노드 생성 후 해당 노드를 복사하여 사용했다.

l1노드나 l2노드를 끝까지 돌면서 더한 값의 나머지를 복사용 노드의 next에 넣고, 현재 가리키는 노드를 다음으로 이동해가며 반복했다.

while문이 끝나고 덧셈의 마지막 carry가 있는 경우 한번 더 복사용 노드에 넣고, return 시 return용 노드의 다음을 return하도록 했다. (응답용 노드의 다음부터 더한 값의 나머지를 넣었기 때문)

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {    
		ListNode res = new ListNode(0);
		ListNode tmp = res;
		int carry = 0;
		
		while(l1 != null || l2 != null) {
			int add = (l1 != null? l1.val : 0) + (l2 != null? l2.val : 0) + carry;
			carry = add / 10;
			add = add % 10;
			tmp.next = new ListNode(add);
			tmp = tmp.next;
			if(l1 != null)l1 = l1.next;
			if(l2 != null)l2 = l2.next;
		}
		
		if(carry != 0) {
			tmp.next = new ListNode(carry);
		}
		
		res = res.next;

		return res;
	}
}

결과

문제

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

https://leetcode.com/problems/two-sum/

풀이

이중 for문을 통해 한번씩 비교해 나가는 방법을 이용했다.

답이 되는 경우가 한가지 밖에 없다고 해서 배열의 0번 숫자와 1~끝까지 더해보고, 1번 숫자와 2~끝가지 더해보는 식으로 이중 for문을 이용했다.

for문을 돌리면서 Map에 target에서 nums배열에 있는 값을 뺀 결과와 인덱스를 저장해 놓고, 다음 nums배열의 숫자가 Map에 있는지 contiains를 통해 확인하는 형식으로 하면 for문을 하나만 사용할 수 있을 것 같긴 하다.

코드

class Solution {
	public int[] twoSum(int[] nums, int target) {
		int[] res = new int[2];
		boolean flage = false;
		for(int i = 0; i < nums.length; i++) {
			res[0] = i;
			for(int j = i+1; j < nums.length; j++) {
				if(nums[res[0]] + nums[j] == target) {
					res[1] = j;
					flage = true;
					break;
				}
			}
			if(flage) {
				break;
			}
		}

		return res;
	}
}

결과