해보자

문제

https://leetcode.com/problems/zigzag-conversion/description/

풀이

문제 설명 그대로 구현했다.

String 형태의 문자 관리가 필요하기에 StringBuilder를 배열 형태로 이용하여 메모리 사용량을 줄이고, append하여 쉽게 구현 가능했다.

다만 문자 수가 열 수보다 작거나 열 수보다 문자 수가 작은 등의 예외 처리에 신경써야 했다.

코드

class Solution {
    public String convert(String s, int numRows) {
        if(s.length() < numRows) {
        	numRows = s.length();
        }
        
        StringBuilder[] temp = new StringBuilder[numRows];
        boolean order = true;
        int idx = 0;
		
        for(int i = 0; i < s.length(); i++) {
        	
        	if(temp[idx] == null) {
        		temp[idx] = new StringBuilder();
        	}
        	
        	temp[idx].append(s.charAt(i));
        	
        	if(idx >= numRows - 1) {
        		order = false;
        	} else if(idx <= 0) {
        		order = true;
        	}
        	
        	idx += order? 1 : -1;
        	if(idx < 0) { 
        		idx = 0;
        	}
        	
        }
        
        for(int i = 1; i < temp.length; i++) {
        	temp[0].append(temp[i].toString());
        }
        
		
		return temp[0].toString();
    }
}

결과

문제

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

https://leetcode.com/problems/longest-palindromic-substring/

풀이

회문인지 조사할 중심점을 잡아서, 중심점이 홀수 일 때와 짝수 일 때를 나눠서 길이를 비교하도록 했다.

for문이나 while문 하나로 할 수 있는 방법이 없나 고민해봤으나, 현재로써는 이 방법이 최선인 듯 하다.

코드

class Solution {
    public String longestPalindrome(String s) {
        String res = new String();
        int maxLen = 0;
        
        for(int i = 0; i < s.length(); i++) {
        	int len = Math.max(find(s, i, i), find(s, i, i+1));
        	if(len >= maxLen) {
        		res = s.substring(i - (len / 2), i + (len / 2) + (len % 2) + 1);
        		maxLen = len;
        	}
        }
		return res;
    }
    
    public int find(String s, int left, int right) {
		int start = 0, end = 0;
		while(left >= 0 && right < s.length()) {
			if(s.charAt(left) == s.charAt(right)) {
				start = left;
				end = right;
				left--;
				right++;
				continue;
			}
			break;
		}
		return end - start;
	}
}

결과

문제

• 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();
	}
}

결과