575. distribute candies

https://leetcode.com/problems/distribute-candies/

• 처음 생각해낸 방법은
  두개의 priority qeue 를 생성해서 하나는 asc, 하는 desc 로 생성
  sister 가 asc에서 한개씩 빼고, brother가 desc에서 큰 순으로 하나씩 빼다보면 최대 개수가 나올것 같다고 생각이 들었음.

• 코딩하기 귀찮아서 다른 방법 생각해보니 유니크한 사탕의 종류의 개수에 따라서 간단히 풀수 있었음.

• O(N)

• 종류개수 > length/2 return length/2, else 종류개수

Runtime: 14 ms, faster than 96.34% of Java online submissions for Distribute Candies.

class Solution {
    public int distributeCandies(int[] candies) {
        int [] map = new int[200001];
        int kinds = 0;
        for(int i=0; i<candies.length; i++){
            if(map[candies[i]+100000] == 0){
                kinds ++;
            }
            map[candies[i]+100000]++;
        }
        int maxLen = candies.length/2 ;
        return kinds <= maxLen ? kinds : maxLen;
    }
}

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Runtime: 1 ms, faster than 85.87% of Java online submissions for Maximum Subarray.

O(N) 코드

class Solution {
    public int maxSubArray(int[] nums) {
        
        int max = nums[0];
        int pre = nums[0];
        for(int i=1; i<nums.length; i++){
            if(pre >0){
                pre += nums[i];
                max = Math.max(pre, max);
            }else{
                pre = nums[i];
                max = Math.max(pre, max);
            }
        }
        return max;
    }
}

Divide and Conquer

2ms

• ide 사용하고 debugging하는데 시간이 오래 걸림
• 2개또는 1개로 자른다.
• 데이터를 머지할때 3가지 데이터를 구한다
  • leftMost = 왼쪽 0번째 인덱스 부터 시작해서 가장 큰 sum을 구한다.
  • rightMost = 오른쪽 0번째 인덱스부터 왼쪽으로 가장 큰 sum을 구한다.
  • full 은 머지한전체 sum, leftMost와 rightMost를 구하기 위해서 필요함.

public class Solution {

    int max =0;
    int[] nums ;
    public int maxSubArray(int[] nums) {
        max = nums[0];
        this.nums = nums;
        divideAndConquer(0, nums.length-1);

        return max;
    }

    public Data divideAndConquer(int start, int end){
        Data data = new Data();
        if(start == end){
            data.full = nums[start];
            data.leftMost = nums[start];
            data.rightMost = nums[start];
            max = Math.max(max ,data.full);
            return data;
        }else if (start == end-1){
            data.full = nums[start] + nums[end];
            data.leftMost = Math.max(nums[start], nums[start] + nums[end]);
            data.rightMost = Math.max(nums[end], nums[start] + nums[end]);
            max = Math.max(max ,data.leftMost);
            max = Math.max(max ,data.rightMost);
            return data;
        }
        int mid = (end-start)/2 + start;
        // left
        Data left = divideAndConquer(start, mid);

        // right
        Data right = divideAndConquer(mid+1 ,end);
            
        if(left.rightMost >0 || right.leftMost >0){
            max = Math.max((Math.max(left.rightMost, 0) + Math.max(right.leftMost, 0)), max);
        }
        
        data.leftMost = Math.max(left.leftMost, left.full + right.leftMost);
        data.rightMost = Math.max(right.rightMost, right.full + left.rightMost);
        data.full = right.full + left.full;
        max = Math.max(max, data.leftMost);
        max = Math.max(max, data.rightMost);
        max = Math.max(max, data.full);
        return data;
    }

  
}

class Data {
    int leftMost;
    int full;
    int rightMost;
}

1009. Complement of Base 10 Integer

https://leetcode.com/problems/complement-of-base-10-integer/

첫번째 방법

• 2 로 나누기 비트연산하면서 0 to 1 , 1 to 0으로 변경한 비트 값을 더해줌
  2번째 방법
• digit을 구한후 해당 xor 연산으로 한번에 풀었음

Runtime: 0 ms, faster than 100.00% of Java online submissions for Complement of Base 10 Integer.

class Solution {
    public int bitwiseComplement(int N) {
        if(N==0){
            return 1;
        }
        
        int digit = 0;
        int sum =0;
        while (N> 0){
            int remainder = N % 2 ;
            N = N>>1;
            if(remainder == 0 ){
                sum += 1<< digit;
            }
            digit++;            
        }
       
        return sum;
    }
}

두번째 코드

class Solution {
    public int bitwiseComplement(int N) {
        int digit =1;
        int n = N;
        while((n= n >> 1) > 0){
            digit++;
        }
        
        int compare = (2 << digit-1) -1;
        return N^compare;        
    }
}

java shift 연산

Shift 연산

• bit 연산은
• 16진수? int를 표현하는 방법
• 아래 예제는 전부다 16을 출력

  int a = 0x010;
  System.out.println(a);
  a = 0x0010;
  System.out.println(a);
  a = 0x0000010;
  System.out.println(a);
  a = 0x000000000000000000000000000000000000000010;
  System.out.println(a);

• 16진수를 표현하는 방법?
  • 0x에 0 to f 까지 표현할수 있다. (0 -15)

<< number , >> number 연산자

• 비트값을 왼쪽으로 number만큼 움직여준다.

int a = 8;
System.out.println(Integer.toBinaryString(a));
// 001000
a = a << 2;
System.out.println(Integer.toBinaryString(a));
// 100000
a = a >> 2;
System.out.println(Integer.toBinaryString(a));
// 001000

• 1을 오른쪽으로 비트 연산하게 되는경우 어떻게 나올까??

int a = 1;
System.out.println(Integer.toBinaryString(a));
// 00001
a = a >> 5;
System.out.println(Integer.toBinaryString(a));
// 0

• 으로나온다.

1029. Two City Scheduling

https://leetcode.com/problems/two-city-scheduling/

• a와 b의 갭을 구한다.
• 위의 갭이 큰 값으로 descending 정렬한다.
• 갭순으로 정렬된것중에 중에 작은 값 기준으로 이렇게 정렬되어있다면
  • a b a a a b
  • a b a a b b 이렇게 분류해서 더한다. 왜냐하면 반틈씩 인터뷰를 진행해야한다고 나와있어서
• 위내용을 코딩화 하니깐 생각보다 복잡해졌음

Runtime: 2 ms
Memory Usage: 38.5 MB

class Solution {
     public int twoCitySchedCost(int[][] costs) {
        List<Schedule> list = new  ArrayList<Schedule> ();

        for( int i=0; i<costs.length; i++){
            list.add(new Schedule(costs[i][0], costs[i][1], Math.abs(costs[i][0] - costs[i][1]) ));
        }

        Collections.sort(list, new Comparator<Schedule>() {
            @Override
            public int compare(Schedule o1, Schedule o2) {
                return o2.gap - o1.gap;
            }
        });

        int len = costs.length/2;
        int acount = 0;
        int bcount = 0;
        int index =0;
        int minsum =0;
        while(acount<len && bcount <len){
            Schedule schedule = list.get(index++);
            if(schedule.a< schedule.b){
                acount++;
                minsum+= schedule.a;
            }else{
                bcount++;
                minsum+= schedule.b;
            }
        }

        if(acount != len){
            for (int i=index; i<list.size(); i++ ){
               minsum += list.get(i).a;
               acount++;
            }
        }

        if(bcount != len){
            for (int i=index; i<list.size(); i++ ){
                minsum += list.get(i).b;
                bcount++;
            }
        }
        return minsum;

    }

    class Schedule {
        int a;
        int b;
        int gap;

        Schedule(int a, int b, int gap){
            this.a = a;
            this.b = b;
            this.gap = gap;
        }
    }
}

두번째 코드

• 위의 로직을 조금더 깔끔하게 하는 방법
• solution을 보니깐 compare 하는부분에서 조금더 잘 정렬하던데 머리로 한 70% 이해했음. 코드 짜라고 하면 어려움
• 다음에 한번더 보면 좋을것 같은 문제

public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Math.abs(o2[0]- o2[1]) - Math.abs(o1[0]- o1[1]) ;
            }
        });

        int len = costs.length/2;
        int acount = 0; int bcount = 0; int index =0; int minsum =0;
        while(acount<len && bcount <len){
            int[] schedule = costs[index++];
            if(schedule[0]< schedule[1]){
                acount++;
                minsum+= schedule[0];
            }else{
                bcount++;
                minsum+= schedule[1];
            }
        }
        for (int i=index; i<costs.length; i++ ){
            if(bcount != len){
                minsum += costs[i][1];
                bcount++;
            }else{
                minsum += costs[i][0];
                acount++;
            }
        }
        return minsum;
     }

459. repeated-substring-pattern

• https://leetcode.com/problems/repeated-substring-pattern/

• 문제 난이도는 easy 이지만 생각도 힘들었고 생각을 코드로 구현도 힘들었음.
  
• 파티션으로 나누어서 모든게 일치하면 통과하는식으로 구현
  
• 아래 그림으로 로직 표현
  

Runtime: 15 ms, faster than 71.70% of Java online submissions for Repeated Substring Pattern.
Memory Usage: 36.5 MB, less than 100.00% of Java online submissions for Repeated Substring Pattern.

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        //abcabcabcabc

        char [] arr = s.toCharArray();

        // distance
        for (int i=1; i<=arr.length/2; i++){
            if(arr.length % i !=0){
                continue;
            }
            boolean allSame = true;
            // 각 파티션
            second :
            for(int j=i; j<arr.length; j+=i){
                // 파티션의 distacne 까지 비교
                for(int k=0; k<i; k++){
                    if(arr[k] != arr[j+k]){
                        allSame = false;
                        break second;
                    }
                }
            }
            if(allSame){
                return true;
            }
        }
        return false;
    }
}

83. remove-duplicated-from-sorted

• https://leetcode.com/problems/remove-duplicates-from-sorted-list/

• head.val 과 head.next.val 을 비교해서 같으면 head.next.next를 head.next에 연결해준다.

Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted List.
Memory Usage: 36.2 MB, less than 100.00% of Java online submissions for Remove Duplicates from Sorted List.

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode mockHead = new ListNode(-1);
        mockHead.next = head;

        while(head != null && head.next != null){
            if(head.val == head.next.val){
                head.next = head.next.next;
                continue;
            }
            head = head.next;
        }

        return mockHead.next;
        
    }
}