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

695. max-area-of-island

• 방문한 곳은 1 to 2로 치환하고 연결된 모든 섬의 count를 구해서 max sum을 구한다.

Runtime: 2 ms, faster than 100.00% of Java online submissions for Max Area of Island.
Memory Usage: 43.6 MB, less than 55.56% of Java online submissions for Max Area of Island.

public class Solution {
    int maxSum =0;
    public  int maxAreaOfIsland(int[][] grid) {
        if(grid.length ==0){
            return 0;
        }

        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == 1){
                    int sum = visit(i, j, grid);
                    maxSum = Math.max(maxSum, sum);
                }
            }
        }
        return maxSum;
    }

    private int visit(int i, int j, int[][] grid) {
        int sum=0;
        if(i >=0 && i<grid.length && j>=0 && j<grid[i].length){
            if(grid[i][j] ==1){
                sum++;
                grid[i][j] =2;
                sum+=visit(i+1, j, grid);
                sum+=visit(i-1, j, grid);
                sum+=visit(i, j-1, grid);
                sum+=visit(i, j+1, grid);
            }
        }
        return sum;
    }
}

342. power of four

https://leetcode.com/problems/power-of-four/

해결과정

10진수 to 2진수

• 4 -> 100
• 16 -> 10000
• 64 -> 1000000

Runtime: 7 ms, faster than 5.74% of Java online submissions for Power of Four.
Memory Usage: 34.3 MB, less than 6.67% of Java online submissions for Power of Four.

public boolean isPowerOfFour(int num) {
        String binarySring = Integer.toBinaryString(num);
        if(binarySring.length()>=3 && (binarySring.length()-1)%2 ==0){
           return  "1".equals(binarySring.replaceAll("0", ""));
        }

        return false;
    }

second soluton

민수님 numberOfTrailingZero꺼랑 And 논리 연산자를 이용함.
100
011 의 and 0

class Solution {
    public boolean isPowerOfFour(int num) {
        if(num==0)return false;
        return Integer.numberOfTrailingZeros(num) % 2==0 && ((num & num-1) == 0);
    }
}

979. Distribute Coins in Binary Tree

https://leetcode.com/problems/distribute-coins-in-binary-tree/

• 이문제는 풀이는 조금더 생각을 해서 코딩 라인수를 줄여야할필요가 있음

• 실제 코인의 이동이 아니라 코인이 없더라도 음수대로 값을 채움 ( 있는것처럼 가상의 코인을 움직인다 )

• data를 채우는것은 inorder 순서로 적용

Runtime: 1 ms, faster than 87.01% of Java online submissions for Distribute Coins in Binary Tree.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Distribute Coins in Binary Tree.

public class Solution {

    int count =0;
    public int distributeCoins(TreeNode root) {
        if(root == null){
            return 0;
        }
        conqer(root);

        return count;
    }

    public void conqer ( TreeNode root){
        if(root.left != null){
            conqer(root.left);
            calclator(root, root.left);
        }
        if(root.right != null){
            conqer(root.right);
            calclator(root, root.right);
        }
    }
    public void calclator(TreeNode root, TreeNode child){
        if(child.val <=0){
            int increase = 1-child.val;
            count += increase;
            child.val = 1;
            root.val = root.val - increase;
        }else {
            int decrease =  child.val - 1;
            count += decrease;
            child.val = 1;
            root.val = root.val + decrease;
        }
    }
}

1047. Remove All Adjacent Duplicates In String

-https://leetcode.com/problems/verifying-an-alien-dictionary/

Hi! I’m your first Markdown file in StackEdit. If you want to learn about StackEdit, you can read me. If you want to play with Markdown, you can edit me. Once you have finished with me, you can create new files by openi

1차 코드

49 ms	38.5 MB	java

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

        if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();
        Stack<Character> stack  = new Stack<Character>();
        for(int i=0; i<chars.length; i++){


            if(!stack.isEmpty()) {
                Character cha = stack.peek();
                if (cha != null && cha == chars[i]) {
                    stack.pop();
                    continue;
                }
            }
            stack.push(chars[i]);
        }

        char [] result = new char[stack.size()];
        int index = stack.size()-1;
        while(!stack.isEmpty()){
            Character  last = stack.pop();
            result[index--] = last;
        }

        return new String(result);
    }
}

2차코드

• 자료구조 안쓰고 다시 한번더 풀어봐야겠다.
• 조건이 바로 앞뒤 2개의 character 값만 비교하는거라서 마지막 last index를 기억하는걸로
• 앞뒤가 서로 다를때 last index = currentIndex
• 앞뒤가 서로 같을때 find last index and check index ‘0’

Runtime: 4 ms, faster than 98.11% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                while(last >=0 && chars[last] == '0'){
                    last --;
                }
            }else{
                last = i;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                builder.append(chars[i]);
            }
        }

        return builder.toString();
    }
}

3차코드

Runtime: 3 ms, faster than 99.83% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 38.1 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

• 2차코드에서 StringBilder 제거

// "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        int resltLenth = chars.length;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                resltLenth-=2;
                while(last >=0 && chars[last] == '0' ){
                    last --;
                }
            }else{
                last = i;
            }
        }

        char[] result = new char[resltLenth];
        int resultIndex =0;
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                result[resultIndex++] = chars[i];
            }
        }
        return new String(result);

290. word-pattern

• 문제 이해가 문제보다 더 어려운 문제

bijection :  전단사 

class Solution {
    public boolean wordPattern(String pattern, String str) {
        
        String[] map = new String[30];
        char [] patternArr  = pattern.toCharArray();
        String[] strArr = str.split(" ");

        Set<String> used = new HashSet<>();

        if(patternArr.length != strArr.length){
            return false;
        }

        for(int i=0; i<patternArr.length; i++){
            String value = map[patternArr[i]-'a'] ;
            if(value == null){
                if(used .contains(strArr[i])){
                    return false;
                }
                used.add(strArr[i]);
                map[patternArr[i]-'a']  = strArr[i];
            }else{
                if(!map[patternArr[i]-'a'].equals(strArr[i])){
                    return false;
                }
            }
        }

        return true;
    }
}