palindrome

• DP가 약하기도하고 공부도 하고 내용도 복습할겸 정리합니다.
• 기본에서 true 와 false말고 숫자로 표현하면 응용이 가능하다.
• 참고 링크 https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

dp 문제를 푸는 나름대로의 방법

• DP 에서 row와 column에 어떤값을 정확하게 넣어야 할지가 분명하게 서지 않을때 그림을 그리는것은 도움이 된다.

문제

• 여러개의 특정 포지션에서 해당 substring이 palindrome인지 체크 하는 로직을 만드세요
• left = 시작 지점 right = 끝 지점
• ex) str = “abad”

풀이

• T = true, F = false로 간주한다.
• table[left][right]에 대한 값을 담을 수 있는 table을 만들고 값을 채워나간다.
• left == right 같을때는 T 로 셋팅
• left != right
  • left +1 <= right-1 ( size가 3이상인 경우)
    • str[left] == str[right] && table[left+1][right-1] 인경우 table[left][right] T 셋팅
  • left +1 > right-1 ( size 가 2인경우 )
    • str[left] == str[right] 인 경우 table[left][right] T 셋팅

사이즈가 1인경우

사이즈가 2이고 left = 0, right =1 인경우

사이즈가 3이고 left = 0 right =2 인경우

코드

String s = "abac";
boolean[][] table = new boolean[s.length()][s.length()];
for(int i=0; i<s.length(); i++){
    table[i][i] = true;
}
for(int size=2; size<s.length(); size++){
    for(int left=0; left<s.length(); left++){
        int right= left+size-1;
        if(right >= s.length()){
            continue;
        }
        if( size == 2){
            table[left][right] = s.charAt(left) == s.charAt(right);
        }else{
            table[left][right] = s.charAt(left) == s.charAt(right) && table[left+1][right-1];
        }
    }
}

Async Await 사용할때 3가지만 알면 모든게 해결됨

1. async function은 promise 를 리턴함
2. promise는 then이나  await 로 기다림
3. await는 async 안에서만 사용한다.

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;
     }