Arrays & Hashing (2)

 

238. Product of Array Except Self

 

nums = [1,2,3,4] 일 때  ,  각 리스트에 원소에  자기 자신을 제외한 값의  곲을 넣어야 한다.

 

class Solution {
   public int[] productExceptSelf(int[] nums) {
        int n = nums.length ;
        List<Integer> index  = new ArrayList<>();
        int pro = 1 ;
        for(int i = 0 ; i <  n ; i++) {
            if(nums[i] == 0 ) index.add(i) ;
            if(nums[i] != 0) pro *= nums[i] ;
        }
        if(index.size()  > 1) {
            return new int[n] ;
        }
        if(index.size() == 1) {
            Arrays.fill(nums,0);
            nums[index.get(0)] = pro;
            return nums ;
        }

        for(int i = 0 ; i <  n ; i++) {
            nums[i] = pro / nums[i] ;
        }
        return nums ;
    }
}

 

 

36. Valid Sudoku

 

스도쿠다 ,행열  줄 1~ 9 반복이 없어야하며 9 개로 나눴을때 각 부분이 1 ~ 9 겹치는게 없는지 확인하는 문제로 접근 하였고 정답은 맞췄지만, 작성과 디버깅시  소요 시간이 너무 길었고 시간, 공간 복잡도에서 자신이 없었지만

???

메모리를 효율적으로 짰다,, (?)

class Solution {

    public boolean isValidSudoku(char[][] board) {
        // loop  row check
        for(char[] line :board) {
            if(isRowDuplicate(line)) return false;
        }
        // loop column check

        for(int i = 0 ; i < 9 ;i++) {
            Map<Character , Integer> map = new HashMap<>();
            for(int j = 0 ; j < 9 ; j++) {
                char item = board[j][i];
                if(item== '.') continue;
                if(map.containsKey(item)) {
                    return false;
                }
                else {
                    map.put(item,0);
                }
            }
        }

        // loop  3 boxed check
        if(isBoxDuplicate(board)) return false;
        return true;
    }
     private boolean isBoxDuplicate(char[][] board) {
        for (int s = 0; s < 7; s = s + 3) {
            int count = 0 ;
            Map<Character, Integer> map = new HashMap<>();
            for (int j = 0; j < 9 ; j++) {
                for (int i = s; i < s + 3; i++) {
                    count++;
                    if(count > 9) {
                        count = 1;
                        map = new HashMap<>();
                    }
                    char item = board[j][i];
                    if (item == '.')
                        continue;
                    if (map.containsKey(item))
                        return true;
                    map.put(item, 0);
                }
            }
        }
        return false;
    }
    public boolean isRowDuplicate(char[] list){
        Map<Character , Integer> map = new HashMap<>();
        for(char item : list) {
            if(item == '.') continue;
            if(map.containsKey(item)) {
                return true;
            }
            else {
                map.put(item,0);
            }
        }
        return false;
    }
}

 

128. Longest Consecutive Sequence

 

한번에 클리어를 못했다 ,, 매우 단순 한 문제 , 디버깅 , IDE 없이 원큐로 푸는것을 연습하자 . 

import java.util.* ; 

class Solution {
    public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        List<Integer> arr = Arrays.stream(nums).
                distinct().
                boxed().
                collect(Collectors.toList());
        int maxC = 0 ;
        int co = 0 ;  
        if(nums.length == 0 ) return 0 ;
        if(nums.length == 1 || arr.size() ==1 ) return 1 ;
        

        int past = nums[0] ; 
        for(int item : arr){
            past++;
            if(item == past) {
                co++ ;
                maxC = Math.max(co,maxC);
            }else{
                co = 1;
            }
            past = item;
        }
        if(maxC == 0) return 1;
        return maxC ; 
    }
}