Monday, January 7, 2019

34. Find First and Last Position of Element in Sorted Array Medium

34. Find First and Last Position of Element in Sorted Array Medium

문제 링크

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
두단계로 끊어서 생각
시간 복잡도는 O(log n) 인것 같은데 이상하게 느리네 ;;
Runtime: 6 ms, faster than 37.73% of Java online submissions for Find First and Last Position of Element in Sorted Array.

1단계

  • binary search를 탐색하는거를 만들고
  • 로그를 출력하면서 잘 탐색을 하는지 확인
 public void find(int start, int end, int[] nums) {
  if (end <= start) {
   return;
  }

  int mid = start + (end - start) / 2;
  System.out.println(mid);
  // lef
  find(start, mid, nums);
  // right
  find(mid + 1, end, nums);
 }

// output  ex) new int[]{1,2,3,4,5,6,7}
/**  
3
1
0
2
5
4
6
**/

2단계

  • 1단계를 응용해서 변경
public class FindFirstLast {
 int low = Integer.MAX_VALUE;
 int max = Integer.MIN_VALUE;
 
 public int[] searchRange(int[] nums, int target) {
  
  find(0, nums.length, nums, target);
  
  if(low != Integer.MAX_VALUE){
   return new int[]{low, max};
  }else{
   return new int[]{-1, -1}; 
  }
  
    }
 
 public void find(int start, int end, int[] nums, int target){
  if(end <= start){
   return;
  }  
  
  int mid = start + (end - start)/2; 
//  System.out.println(mid);
  
  if(nums[mid] == target){
   low = Math.min(mid, low);
   max = Math.max(mid, max);
   if(start < low){
    find(start, mid, nums, target); 
   }
   
   if(end > max){
    find(mid+1, end, nums, target); 
   }    
      
  }else if(nums[mid] < target){
   find(mid+1, end, nums, target); 
  }else if(nums[mid] > target){
   find(start, mid, nums, target); 
  }
  
 }
 
 public static void main(String args[]){
  new FindFirstLast().searchRange(new int[]{1,2,3,4,5,6,7,8}, 5);
 }
 

}
Written with StackEdit.

Saturday, December 29, 2018

I solved all intro problem in codesignal~

I solved all codesignal problem in intro,

next I will try graph arcade. I think graph problem is more difficult than intro.



Wednesday, December 26, 2018

395. Longest Substring with At Least K Repeating Characters

395. Longest Substring with At Least K Repeating Characters

문제

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

풀이 사고

  • k보다 적은 카운트의 경우 k위치를 기준으로 자른다음 재귀로 문제 접근
  • ex ) ababcaaad k=2
    • 전체의 카운트
      • a = 5, b=2, c=1; d=1 즉 k보다 작은게 존재하면 작은 캐릭터 기준으로 자른다
      • c 와 d 를 콤마(,)로 치환
      • abab,aaa,
      • , 를 기준으로 split한후 다시 자른 String으로 반복로직 구현

Runtime: 3 ms, faster than 77.01% of Java online submissions for Longest Substring with At Least K Repeating Characters.

class Solution {
    int max;

    public int longestSubstring(String s, int k) {
        max =0;

        if(k>s.length()){return 0;}
        findMax(s, k);
        return max;
    }

    public void findMax(String s, int k){
        int arr[] = new int['z' - 'a' +1];

        // setting
        for(int i=0; i<s.length(); i++){
            int index = s.charAt(i) -'a';
            arr[index]++;
        }

        // 전부다 k보다 더 큰 수가 나오는 경우는 max값을 갱신
        if(allEqualOrBigger(arr, k)){
           max = Math.max(max, s.length());
        }else{
            char[] str= new char[s.length()];
            for(int i=0; i<s.length(); i++){
                int index = s.charAt(i) -'a';

                if(arr[index] == 0 ){
                    continue;
                }else if(arr[index] >=k){ //
                    str[i] = s.charAt(i);
                }else{
                    str[i] = ',';
                }
            }
            String[] subs = new String(str).split(",");
            for(int i=0; i<subs.length; i++){
                if(subs[i].length() <= max){
                    continue;
                }
                findMax(subs[i], k);
            }
        }
    }

    public boolean allEqualOrBigger(int arr[], int k){
        for(int i=0; i< arr.length; i++){
            if(arr[i] >0 && arr[i]<k){
                return false;
            }
        }
        return true;
    }
}

Wednesday, December 5, 2018

stack을 이용한 알고리즘

stack을 이용한 알고리즘

문제

https://leetcode.com/problems/flatten-nested-list-iterator/discuss/?orderBy=recent_activity

접근

  1. 재귀로 접근을 하면 flat하게 값만 쉽게 추출할수 있을것 같았다. 사실 이렇게 되면 사이즈가 클 경우 초기화 하는 시간이 오래 걸리니 초기화 하는 시간은 최대한 줄이는 방법을 생각해보았다.
  2. 그래서 Queue를 이용해서 어떻게 할 수 있나 생각해보았다. Queue로 생각을 해도 답이 안나왔음.
  3. 그래서 Stack을 이용해서 답을 구함
  4. 너무 Runtime에 신경쓰지 않기로함 ㅎ

최종그림

enter image description here

Runtime: 6 ms, faster than 42.53% of Java online submissions for Flatten Nested List Iterator.

public class NestedIterator implements Iterator<Integer> {

   Stack<NestedInteger> stack = new Stack<NestedInteger>();
    public NestedIterator(List<NestedInteger> nestedList) {
    	for(int i= nestedList.size() -1; i>=0; i--){    		
    		stack.push(nestedList.get(i));	    		
		}   	
    }

    @Override
    public Integer next() {
    	return stack.pop().getInteger();		
    }

    @Override
    public boolean hasNext() {
    	while(stack.size()>0){
    		NestedInteger nestedInteger = stack.peek();
    		if(nestedInteger.isInteger()){
    			return true;
    		}else{
    			nestedInteger = stack.pop();
    			List<NestedInteger> list = nestedInteger.getList();
    			for(int i=list.size()-1; i>=0; i--){
    				//stack.push(list.get(i));
    				if(list.get(i).isInteger()){
    	    			stack.push(list.get(i));	
    	    		}else{
    	    			if(list.get(i).getList().size()>0){
    	    				stack.push(list.get(i));
    	    			}
    	    		}
    			}
    		}
    	}
    	return false;
    }
}

Tuesday, October 16, 2018

greedy algorithm https://leetcode.com/problems/task-scheduler/description/


# task-scheduler ( medium ) https://leetcode.com/problems/task-scheduler/description/ 매번 최대 count를 가진 character의 count를 줄여가면서 값을 찾음 ### 좋은 예제 - AAAABBCCDD inteval = 1 ```java public class Solution { public int leastInterval(char[] tasks, int n) { HashMap map = new HashMap(); Comparator comparator = new Comparator() { @Override public int compare(Number o1, Number o2) { return (o2.c - o1.c); } }; PriorityQueue numbers = new PriorityQueue(100, comparator); for(int i=0; i0){ count =0; ArrayList list = new ArrayList(); for(int i=0; i<=n; i++){ Number number = numbers.poll(); if(number == null){ break; } number.c--; count++; if(number.c ==0){ }else{ list.add(number); } } numbers.addAll(list); list.clear(); if(numbers.size() >0){ total += (n+1); } } total+= count; return total; } public class Number{ char n; int c; Number(char n , int c){ this.n = n; this.c = c; } } }```

Sunday, October 7, 2018

typescript basic-types

Basic Types

link TypeScript-Handbook/Basic Types.md at master · Microsoft/TypeScript-Handbook · GitHub

Introduction

열거 형을 제공한다.

Boolean

1let isDone: boolean = false;

Number

  • ECMAScript 2015에서 고새된 바이너리와 8진법도 가능하다
1234let decimal: number = 6
let hex: number = 0xf00d;
let binary: number = 0b1010;
let octal: number = 0O744

String

  • type스크립트에서도 싱글 qoute나 double qoute (쌍따옴표) 모두 사용 가능하다
  • java에서는 상따옴표만 사용가능
12let color: string= "blue";
color = 'red';
  • 템플릿도 사용 가능 하다 이때는 ` 기호를 사용해야한다. 템플릿자체가 멀티라인도 가능함

TypeScript example

12345let fullName: string = `Bob Bobbington`;
let age: number = 37;
let sentence: string = `Hello, my name is ${ fullName }.

I'll be ${ age + 1 } years old next month.`;

to Javascript

123var fullName = "Bob Bobbington";
var age = 37;
var sentence = "Hello, my name is " + fullName + ".\n\nI'll be " + (age + 1) + " years old next month.";

Array

  • Typescript에서도 array를 사용할 수 있다.
  • 선언하는 두가지 방법
123let list: number[] = [1, 2, 3];

let list: Array<number> = [1, 2, 3];

Tuple

  • 튜플을 array의 형식처럼 지원한다. 튜플 안의 type은 동일할 필요가 없지만 사용 할때는 지정한 타입과 동일하게 사용해야함
123456// Declare a tuple type
let x: [string, number];
// Initialize it
x = ["hello", 10]; // OK
// Initialize it incorrectly
x = [10, "hello"]; // Error

Enum

  • 도움이 되는 데이터타입이 enum 이다. c#처럼 numeric 값들을 조금더 친근하게 셋팅할 수 있다.
123enum Color {Red, Green, Blue}
let c: Color = Color.Green;

  • javascript Converting
123456789var Color;
(function (Color) {
    Color[Color["Red"] = 0] = "Red";
    Color[Color["Green"] = 1] = "Green";
    Color[Color["Blue"] = 2] = "Blue";
})(Color || (Color = {}));
var c = Color.Green;

{0: "Red", 1: "Green", 2: "Blue", Red: 0, Green: 1, Blue: 2}

Any

  • Any 타입은 변수의 값이 숫자였다가 String값이 였다가 boolean 마음대로
1234567891011let notSure: any = 4;
notSure = "maybe a string instead";
notSure = false; // okay, definitely a boolean

// 오브젝트는 할당만 가능하고 임의의 메소드를 사용 못한다.
let notSure: any = 4;
notSure.ifItExists(); // okay, ifItExists might exist at runtime
notSure.toFixed(); // okay, toFixed exists (but the compiler doesn't check)

let prettySure: Object = 4;
prettySure.toFixed(); // Error: Property 'toFixed' doesn't exist on type 'Object'.
  • 이것은 java에서는 상상도 못할 조금 신세계
123let list: any[] = [1, true, "free"];

list[1] = 100;

Void 타입??

  • Void 는 리턴값이 없는 메소드에서 지정할 수 있고
  • void 타입에 바인딩 할 수 있는 데이터는 오직 null 과 undefined만 적용 할 수 있다.
12345function warnUser(): void {
    console.log("This is my warning message");
}

let unusable: void = undefined;

Null and Undefined

  • null 과 undefined는 모든 타입의 서브 타입이다
  • 즉 number에 null을 할당 할 수 있다.
  • union type도 있긴 한데 나중에 확인 하겠다.
12345// Not much else we can assign to these variables!
let u: undefined = undefined;
let n: null = null;

// subtype 증명

Never

  • 이해하기로는 반환값에 절대로 나타날수 없는 타입으로 사용할때 never를 사용한다.
123456789101112131415// Function returning never must have unreachable end point
function error(message: string): never {
    throw new Error(message);
}

// Inferred return type is never
function fail() {
    return error("Something failed");
}

// Function returning never must have unreachable end point
function infiniteLoop(): never {
    while (true) {
    }
}

Object

  • 잘 이해가 안감 ㅎㅎㅎ
  • object 는 number, string, boolean, symbol, null, undefined가 아닌 non-primitive type 이다
  • Object.creat Api를 더 잘 표현할 수 있다.
123456789declare function create(o: object | null): void;

create({ prop: 0 }); // OK
create(null); // OK

create(42); // Error
create("string"); // Error
create(false); // Error
create(undefined); // Error

Type assertions

  • 다른 언어의 형변환과 비슷하지만 특수 검사나 데이터 재구성을 하지 않으며 런타임시 영향을 미치지는 않는다 다만 컴파일러에서만 사용한다. 두가지 방법이 있는데 java처럼 angle-bracket syntax를 사용하는 방법이 있고 다른 하나는 as - syntax 를 사용하는 방법이 있다.
12345678// angle-bracket
let someValue: any = "this is a string";
let strLength: number = (<string>someValue).length;

// as syntax
let someValue: any = "this is a string";
let strLength: number = (someValue as string).length;

Saturday, October 6, 2018

오랫만에 풀어본 문제 serialized and desirialize

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/ dfs 로 길을 갔었고 가는 곳 마다 흔적을 남겼고 다시 그 흔적을 따라 deserialized를 하면 풀리는 문제