LeedCode – Longest Substring Without Repeating Characters 문제풀이 (난이도:중)

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

Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        boolean[] cache = new boolean[255];
        int count = 0;
        int maxCount = 0;
        int head = 0, tail = 0;
        while(head < s.length()){
            if(cache[s.charAt(head)] != true){
                cache[s.charAt(head)] = true;
                maxCount = Math.max(head-tail+1, maxCount);
                head++;
            }
            else{
                cache[s.charAt(tail)] = false;
                tail++;
            }
        }
        
        return maxCount;
    }
}

Codility – MaxCounters 문제 풀이 (난이도:중)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int[] solution(int N, int[] A) {
        
        int maxCounter = N+1;
        int counters[] = new int[N];
        for(int i = 0 ; i < counters.length ; i++){
            counters[i] = 0;   
        }
        
        int nextMax = 0;
        int curMax = 0;
        for(int i = 0 ; i < A.length ; i++){
            int counterNumber = A[i];
            int counterIndex = counterNumber - 1;
            
            if(counterNumber < maxCounter){
                if(counters[counterIndex] <= curMax){
                    counters[counterIndex] = curMax;
                }
                counters[counterIndex]++;
                nextMax = Math.max(nextMax, counters[counterIndex]);
            }
            else{
                curMax = nextMax;
            }
        }
        
        for(int i = 0 ; i < counters.length ; i++){
            if(counters[i] < curMax){
                counters[i] = curMax;   
            }
        }
        
        return counters;
    }
}

Codility – FrogRiverOne 문제 풀이 (난이도 : 하)

class Solution {
    public int solution(int X, int[] A) {
        // write your code in Java SE 8
        int leafList[] = new int[X+1];
        for(int i = 0 ; i < leafList.length ; i++){
            leafList[i] = -1;   
        }
        
        for(int i = 0 ; i < A.length ; i++){
            int leaf = A[i];
            if(leaf <= X ){
                if(leafList[leaf] == -1){
                    leafList[leaf] = i;
                }
                else{
                    leafList[leaf] = Math.min(i, leafList[leaf]);    
                }
            }
        }
        
        int result = 0;
        for(int i = 1 ; i < leafList.length ; i++){
            if(leafList[i] == -1){
                result = -1;
                break;
            }
            result = Math.max(result, leafList[i]);
        }
        
        return result;
    }
}

Codility – CountDiv 문제 풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int A, int B, int K) {
        // write your code in Java SE 8
        int result = B/K + 1;
        if(A != 0){
            result -= ((A-1)/K + 1);
        }
        return result;
    }
}

Codility – PassingCars 문제 풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int toEast = 0;
        
        long pairCount = 0;
        
        for(int i = 0 ; i < A.length ; i++){
            if(A[i] == 0){
                toEast++; 
            } else{
                pairCount += toEast; 
            }
        }

        if(pairCount > 1000000000){
            return -1;   
        }
        
        return (int)pairCount;
    }
}

Codility – Missing Integer 문제 풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        boolean checker[] = new boolean[A.length + 1];
        
        for(int i = 0 ; i < A.length ; i++){
            int value = A[i];
            if(value > 0 && value < checker.length){
                checker[value] = true;
            }
        }
        
        for(int i = 1 ; i < checker.length ; i++){
            if(checker[i] == false){
                return i;   
            }
        }
        
        return checker.length;
    }
}

Codility – PermCheck 문제 풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        boolean checker[] = new boolean[A.length+1];
        
        for(int i = 0 ; i < A.length; i++){
            int value = A[i];
            if(value < checker.length){
                checker[value] = true;   
            }
        }
        
        int result = 1;
        for(int i = 1 ; i < checker.length ; i++){
            if(checker[i] == false){
                result = 0;
                break;
            }
        }
        
        return result;
    }
}

Codility – PermMissingElem 문제 풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        boolean occurred[] = new boolean[A.length + 2];
        
        for(int i = 0 ; i < A.length ; i++){
            int occurredNumber = A[i];
            occurred[occurredNumber] = true;
        }
        
        for(int i = 1 ; i < occurred.length ; i++){
            if(!occurred[i]){
                return i;
            }
        }
        
        return 0;
    }
}

Codility – FrogJmp 문제풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int X, int Y, int D) {
        // write your code in Java SE 8
        int distance = Y - X;
        return distance%D == 0 ? distance/D : distance/D + 1;
    }
}

Codility –  TapeEquilibrium 문제 풀이 (난이도 : 하)

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        
        int front = 0;
        int back = 0;
        for(int i = 0 ; i < A.length ; i++){
            back += A[i];   
        }
        
        int minDiff = Integer.MAX_VALUE;
        int p = 1;
        for(int i = 1 ; i < A.length ; i++){
            front += A[i-1];
            back -= A[i-1];
            p = i;
            minDiff = Math.min(minDiff, Math.abs(front - back));
        }
        
        return minDiff;
        
    }
}