Eunbibibi

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

이진탐색 두번 시행

1. 시작지점 찾기

2. 끝나는 지점 찾기

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int start = -1;
        int end = -1;

        int left = 0;
        int right = nums.length - 1;
        // start 위치 찾기
        while (left <= right) {

            int mid = (left + right) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            if (nums[mid] == target) {
                start = mid;
            }
        }

        //end 위치 찾기

        left = 0;
        right = nums.length - 1;
        while (left <= right) {

            int mid = (left + right) / 2;

            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            if (nums[mid] == target) {
                end = mid;
            }
        }

        return new int[]{start, end};
    }
}

https://leetcode.com/problems/array-nesting/description/

public int arrayNesting(int[] nums) {
        // 방문했는지 체크하는 임시배열 -1:방문 / 0:방문안함
        int[] tmp = new int[nums.length];
        int res = 0;
        
        for (int i = 0; i < nums.length; i++) {
            //방문한 원소면 스킵하기
            if (tmp[i] == -1) continue;
            
            int cnt = 1;    //방문한 원소 갯수 저장하는 변수
            tmp[i] = -1;
            int next = nums[i]; //다음 방문할 인덱스

            while (tmp[next] == 0) {
                tmp[next] = -1;
                cnt++;
                next = nums[next];
            }

            res = Math.max(res, cnt);
        }

        return res;
    }

https://leetcode.com/problems/max-consecutive-ones-iii/description/

풀이

1. r값이 0인지 체크해서 k값 조정

2. k값이 0보다 작으면 l이동

  2-1 > l값이 0인지 체크해서 k값 조정

  2-2 > l값 이동

3. 가장 긴 길이 저장 

public static int longestOnes(int[] nums, int k) {
        int left = 0;
        int right;
        int res = 0;

        //right 움직이기
        for (right = 0; right < nums.length; right++) {
            //rigth 값이 0이면 k--
            if (nums[right] == 0) {
                k--;
            }

            //k 값이 음수면 left 움직이기
            if (k < 0) {
                if (nums[left] == 0) k++;
                left++;
            }

            //가장 긴값 설정
            if (k >= 0)
                res = Math.max(res, right - left + 1);

        }
        return res;
    }

https://leetcode.com/problems/jump-game-ii/description/

문제

nums[i]의 값만큼 인덱스를 점프해서 마지막 인덱스까지 도달하는 최소한의 점프 값을 구해야 한다.

tmp 배열을 하나 만들어서 배열의 인덱스 i 까지 올수 있는 최소한의 점프 수를 저장한다.

배열에 이미 값이 있으면 그 값이 최소값이므로, 이미 있는 값이 0 일때만 tmp[출발한 인덱스]의 값에 +1 해준다.

코드

package LeetCode;

public class L45 {
    public int jump(int[] nums) {
        int[] tmp = new int[nums.length];

		//tmp 배열 만들기
        for (int i = 0; i < nums.length; i++) {
        	// 인덱스값이 배열의 길이를 넘지 않게 해준다.
            for (int j = 1; j < nums[i] + 1 && (i + j) < nums.length; j++) {
            	// 값이 0일때만 새로운 값 지정하기
                if (tmp[i + j] == 0) tmp[i + j] = tmp[i] + 1;
            }
        }

        return tmp[nums.length - 1];
    }
}

https://leetcode.com/problems/find-peak-element/description/

문제

peek 은 양 옆의 수보다 큰 수 

peek을 찾는 문제 

배열의 처음-1 과 마지막+1 자리는 가장 작은 수 되어 있어서 처음이나 마지막 원소가 그 전 원소보다 크면 peek이다

you must write an algorithm that runs in O(log n) time.

> 이진 탐색으로 풀어라

코드 

public class L162 {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

https://leetcode.com/problems/remove-all-occurrences-of-a-substring/

풀이

StringBuilder 에 indexOf 메서드를 쓰면 part가 포함되어있는 idx를 알려준다. 없으면 -1 리턴.

 -1 이 나올때까지 (포함되어있지 않을때까지) 반복문을 돌리면서 포함되어있으면 delete 해준다.

public static String removeOccurrences(String s, String part) {
    StringBuilder sb = new StringBuilder(s);

    while (sb.indexOf(part) != -1) {
        sb.delete(sb.indexOf(part), sb.indexOf(part) + part.length());
    }
    return sb.toString();
}

https://leetcode.com/problems/compare-version-numbers/description/

버전2개를 비교하는 문제 

풀이

version 2개를 "." 를 기준으로 split하고

길이를 맞춰서 ArrayList에 넣어줬다. 모자른 부분은 0으로 채워둠.

ArrayList 두개 비교 

class Solution {
     public int compareVersion(String version1, String version2) {

        // . 을 기준으로 split
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int maxLength = Math.max(v1.length, v2.length);

        // 0 을 채워 size 동일한 ArrayList 만들기
        List<String> arr1 = getArr(v1, maxLength);
        List<String> arr2 = getArr(v2, maxLength);

        // 크기 비교
        for (int i = 0; i < maxLength; i++) {
            if (Integer.parseInt(arr1.get(i)) > Integer.parseInt(arr2.get(i))) return 1;
            else if (Integer.parseInt(arr1.get(i)) < Integer.parseInt(arr2.get(i))) return -1;
        }

	// 버전이 동일하면 0
        return 0;

    }

    ArrayList<String> getArr(String[] str, int maxLength) {
        ArrayList<String> arr = new ArrayList<>(Arrays.asList(str));

        while (arr.size() != maxLength) {
            arr.add("0");
        }
        return arr;
    }
}

https://leetcode.com/problems/ransom-note/description/

문제

문제에서 2개의 문자열(ransomNote, magazine)이 주어진다.
magazine을 구성하는 문자를 이용하여 ransomNote와 동일한 문자열을 만들 수 있는냐가 문제의 핵심이다.
canConstruct("aab", "baa"); -> true

ransomNote and magazine consist of lowercase English letters.

소문자로만 이루어져서 길이 26의 int배열을 만들고 magazine의 개수를 넣어준다.

배열과 ransomNote를 비교하여 T/F 리턴

public static boolean canConstruct(String ransomNote, String magazine) {

    // 소문자 배열을 만들어서 magzine 넣는다.
    int[] mag = new int[26];
    for (char m : magazine.toCharArray()) {
        int idx = m - 97;
        mag[idx]++;
    }

    // ransomNote 돌려가면서 배열에 있는지 확인한다.
    for (char r : ransomNote.toCharArray()) {
        int idx = r - 97;
        if (mag[idx] == 0) return false;
        mag[idx]--;
    }

    // for문을 다 돌았으면 true 리턴한다.
    return true;
}

시간복잡도 : O(n)