biginteger없이 factorial 100! 을 기본자료형으로 출력

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
        int carry = 0;
        HashMap<Integer, Integer> q = new HashMap<Integer, Integer>();
        q.put(0, 1);
        for (int j = 1; j <= 100; j++) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int temp = q.get(i);
                temp = (temp * j) + carry;
                carry = temp / 10;
                q.put(i, (temp % 10));
                
            }
            while (carry != 0) {
            
                q.put(size, carry % 10);
                carry /= 10;
                size++;
            }
        }
 
        for (int i = q.size() - 1; i > -1; i--) {
            System.out.print(q.get(i));
        }
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

시간복잡도 O(n (log n)^2)

 

1. hashmap에 숫자를 연산한후 숫자 하나씩 집어넣음

2. 하위 for문의 연산이 끝난 후 carry에 값이 남아있으면 추가적으로 등록시킨다.

3. carry는 숫자 하나씩 집어넣기 위해 10으로 나눈 후 몫을 담고 있는 변수

4. 숫자가 역순으로 들어갔기 때문에 출력할땐 역순으로 뽑으면 된다.

'개발 > algorithm' 카테고리의 다른 글

leetcode 4번문제 Median of Two Sorted Arrays  (0) 2020.04.14
leetcode 3번문제 Longest Substring Without Repeating Characters  (0) 2020.04.14
leetcode 445번문제 add two numbers 2  (0) 2020.04.14
leetcode 2번문제 add two numbers  (0) 2020.04.14
leetcode 653 Two Sum IV - Input is a BST  (0) 2020.04.14

문제와 예시는 주소에서 확인

https://leetcode.com/problems/median-of-two-sorted-arrays/

 

Median of Two Sorted Arrays - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        
       int allSize = (a.length + b.length);
 
        int chkSize = (allSize / 2)+1;
        int[] c = new int[chkSize];
        int chkNum = 0;
        int chkNum2 = 0;
        while (chkSize > 0) {
 
            if (a.length - 1 < chkNum) {
                c[chkSize - 1] = b[chkNum2];
                chkNum2++;
                chkSize--;
                continue;
            }
            if (b.length - 1 < chkNum2) {
                c[chkSize - 1]= a[chkNum];
                chkNum++;
                chkSize--;
                continue;
            }
 
            if (a[chkNum] < b[chkNum2]) {
                c[chkSize - 1] = a[chkNum];
                chkNum++;
            } else {
                c[chkSize - 1] = b[chkNum2];
                chkNum2++;
            }
            chkSize--;
        }
        
        if (allSize % 2 == 0) {
            return ((double)(c[0] + c[1])/2);
        }
        
        return (double)c[0];
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

 

https://it-and-life.tistory.com/48

이 블로그글의 마지막 줄에 등록된 링크에서 힌트를 얻음

 

시간복잡도 O(log n+m)

 

1 .매개배열 2개의 사이즈값을 구해 더한후 반으로 나눠서 1을 더함

   1을 더한 이유는 배열은 0부터 시작하기때문에 숫자 맞춰줄려고 더함

2. 반을 나눈 이유는 두개의 배열을 합친 후 그 중간의 값을 알아야할때 

   합친후 반을 나눈것이랑 같기 때문

3. 그 후 반으로 나눈 숫자와 같아질때까지 숫자를 더해준다.

4. 정렬로 작은 값부터 등록하므로 배열의 인덱스는 따로 관리

 

 

 

 

'개발 > algorithm' 카테고리의 다른 글

okky에서 본 문제 factorial 100 without biginteger  (0) 2020.04.14
leetcode 3번문제 Longest Substring Without Repeating Characters  (0) 2020.04.14
leetcode 445번문제 add two numbers 2  (0) 2020.04.14
leetcode 2번문제 add two numbers  (0) 2020.04.14
leetcode 653 Two Sum IV - Input is a BST  (0) 2020.04.14

문제 Given a string, find the length of the longest substring without repeating characters.

 

예시는 https://leetcode.com/problems/longest-substring-without-repeating-characters/

 

Longest Substring Without Repeating Characters - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

링크에서 확인

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int resCnt = 0;
        if (s.length() > 0) {
            
            char[] a = s.toCharArray();
            
            for (int i = 0; i < a.length; i++) {
                int tempCnt = 0;
                HashMap<Character, Integer> strArr = new HashMap<Character, Integer>();
                tempCnt++;
                strArr.put(a[i],i);
                for (int j = i + 1; j < a.length; j++) {
                    if (strArr.containsKey(a[j])) {
                        break;
                    } else {
                        tempCnt++;
                    }
                    strArr.put(a[j],i);
                }
                resCnt = (tempCnt > resCnt) ? tempCnt : resCnt;
            }
        }
        return resCnt;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

 

시간복잡도 O(n^2)

 

1.hashmap에 담았을때가 두번째로 빠르다.

2.첫번째로 빠른것은 int형 배열

3.list방식은 가장 느리다.

 

 

 

'개발 > algorithm' 카테고리의 다른 글

okky에서 본 문제 factorial 100 without biginteger  (0) 2020.04.14
leetcode 4번문제 Median of Two Sorted Arrays  (0) 2020.04.14
leetcode 445번문제 add two numbers 2  (0) 2020.04.14
leetcode 2번문제 add two numbers  (0) 2020.04.14
leetcode 653 Two Sum IV - Input is a BST  (0) 2020.04.14

문제

add two numbers의 문제와 같지만 이번엔 역순으로 저장되어있지 않다.

 

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 8 -> 0 -> 7

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       int checkNum = 0;
        Stack<Integer> stackL1 = new Stack<Integer>();
        Stack<Integer> stackL2 = new Stack<Integer>();
        
        while (l1 != null) {
            stackL1.add(l1.val);
            l1 = l1.next;
        }
        
        while (l2 != null) {
            stackL2.add(l2.val);
            l2 = l2.next;
        }
        
        ListNode dummy,result = new ListNode(0);
        
        dummy = result;
        
        while (stackL1.size() != 0 || stackL2.size() != 0 || checkNum != 0) {
            
            if (stackL1.size() != 0) {
                checkNum += stackL1.pop();
            }
            
            if (stackL2.size() != 0) {
                checkNum += stackL2.pop();
            }
            
            dummy.val = checkNum % 10;
            
            dummy = new ListNode(0);
            dummy.next = result;
            result = dummy;
            
            checkNum /= 10;        
            
        }
 
        return result.next;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

 

시간복잡도 O (n log n)

 

1.각각의 스택에 매개변수로받은 l1,l2를 집어넣는다.

2. 1번문제와 같이 담을 listnode 생성

3. stack은 pop을 사용할경우 마지막에 넣엇던 값을 출력하며 스택에 담긴 값을 지운다.

4. 39번줄 dummy.val에 stack에서 뽑아낸값을 저장한후 10으로 나눈 나머지를 저장

5. 45번 checkNum에는 10으로 나눈 몫을 저장

6. dummy에 새 listnode인스턴스를 생성한 후 dummy.next dummy의 하위에 result 주소를 담는다.

7. 다시 result에는 dummy주소를 담는다.

8. 이렇게되면 result는 0이 생성되어있고 하위노드는 아까 checkNum으로 나눈 나머지가 저장되어있다.

9. 이런식으로 하위부터 상위를 만들어나간다.

10. 스택에서 뽑아낸값을 썼으므로 하위부터 상위로 만들면 똑바로 나옴

11. 스택을 사용한 이유는 노드는 앞자리 숫자부터 등록되어있기 떄문에 자릿수 연산에 불편함이 있으므로

    스택을 사용하여 편하게 일의 자리숫자부터 연산을 함 

12. while 조건이 끝나면 return

 

 

'개발 > algorithm' 카테고리의 다른 글

leetcode 4번문제 Median of Two Sorted Arrays  (0) 2020.04.14
leetcode 3번문제 Longest Substring Without Repeating Characters  (0) 2020.04.14
leetcode 2번문제 add two numbers  (0) 2020.04.14
leetcode 653 Two Sum IV - Input is a BST  (0) 2020.04.14
leetcode 167번문제 Two Sum 2 - input array is sorted  (0) 2020.04.14

문제

비어있지않은 두개의 링크드리스트가 제공되며 이 각각의 링크드리스트에 숫자들은 반대로 저장되어있다.

그리고 각 노드들은 한개의 숫자만 가지고 있다. 각각의 링크드리스트의 노드들을 더한후 

링크드리스트로 리턴해라

 

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 
        int resultCnt = 0;
        ListNode dummy,resultNode = new ListNode(0);
 
        
        dummy = resultNode;
        
        while (l1 != null || l2 != null || resultCnt != 0) {
            
            if (l1 != null) {
                resultCnt += l1.val;
                l1 = l1.next;
            }
            
            if (l2 != null) {
                resultCnt += l2.val;
                l2 = l2.next;
            }
            
            dummy.next = new ListNode(resultCnt % 10);
            dummy = dummy.next;
            resultCnt /= 10;
            
        }
        
        return resultNode.next;
       
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

 

시간복잡도 O(log n)

 

1. while 셋중에 어느조건이라도 true면 계속 돌아감 , 3개다 false면 멈춤

2. listnode dummy와 resultNode를 생성후 dummy에 resultNode의 인스턴스를 넣어준다.

3. 30번째줄 dummy.next는 resultNode의 next이며 ListNode 인스턴스를 만들어서 넣어줌

4. 31번째줄 dummy에 새롭게 생성된 ListNode 인스턴스를 넣어줌

5. 이런식으로 계속 while문을 돌면서 ListNode안에 ListNode를 생성 하면

   따로 resultNode를 건드리지않아도 dummy가 하위 ListNode를 계속 생성을 함.

6. 노드의 숫자는 한자리수만 들어갈수 있기때문에 10으로 나눠서 남은숫자를 next에 집어넣음

7. 10이상일경우 resultCnt에 담김

8. 그럼 null이 아닐경우 resultCnt와 매개변수로 입력받은 l1,l2를 더해줌 그리고 매개변수 l1과 l2는 하위 노드를

   넣어서 와일이 돌면서 계속 하위의 노드값을 찾을수있게해줌

9. while 조건이 끝나면 resultNode를 리턴함.

 

'개발 > algorithm' 카테고리의 다른 글

leetcode 3번문제 Longest Substring Without Repeating Characters  (0) 2020.04.14
leetcode 445번문제 add two numbers 2  (0) 2020.04.14
leetcode 653 Two Sum IV - Input is a BST  (0) 2020.04.14
leetcode 167번문제 Two Sum 2 - input array is sorted  (0) 2020.04.14
leetcode 1번문제 Two Sum  (0) 2020.04.14

문제

숫자가 담긴 바이너리서치트리와 타겟번호가 주어졌을때 더했을때 합이 타겟과 일치하는지 boolean으로 리턴시켜라

 

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

 

Two Sum IV - Input is a BST - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

예제 bst는 링크참조

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
       HashSet<Integer> hashs = new HashSet<Integer>();
       return dfs(root,hashs,k);
    }
    
    public boolean dfs (TreeNode root,HashSet<Integer> hash, int k) {
        
        if (root == null) {
            return false;
        }
        
        if (hash.contains (k - root.val)) {
            return true;
        }
        
        hash.add(root.val);
        
        return dfs(root.left,hash,k) || dfs(root.right,hash,k);        
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

 

시간복잡도 O(log n)

 

1.노드를 좌측부터 검색해나가면서 hashset에 등록시킨다.

2.재귀로 계속 검색

3.왼쪽 노드가 더이상없을경우 28번줄 return left에서 return이 false가 되며

  오른쪽노드를 검색함 -> 28번줄 right로 이동함.

4.오른쪽도 없을시 false를 리턴하며 이전재귀로 이동하여 left는 false가 되고 다시 오른쪽 노드를 검색함

5.있으면 또 재귀돌면서 왼쪽오른쪽 다 검색한다.

6.이렇게 검색하면서 중간에 hashset에 타겟번호에 현재노드값을 뺀 값이 있는지 확인

7. 있으면 true return이 다 true가 되면서 종료.

8. node a + node b = target t 이므로 target t - node b = node a

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

'개발 > algorithm' 카테고리의 다른 글

leetcode 3번문제 Longest Substring Without Repeating Characters  (0) 2020.04.14
leetcode 445번문제 add two numbers 2  (0) 2020.04.14
leetcode 2번문제 add two numbers  (0) 2020.04.14
leetcode 167번문제 Two Sum 2 - input array is sorted  (0) 2020.04.14
leetcode 1번문제 Two Sum  (0) 2020.04.14

문제

asc로 정렬된 인티저 배열이 제공되고 더 했을때의 합이 타겟과 같은 두개의 숫자가 몇번째 배열인지 리턴하라

 

Input: numbers = [2,7,11,15], target = 9

Output: [1,2] Explanation: The sum of 2 and 7 is 9.

Therefore index1 = 1, index2 = 2.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
 
            if (i != nums.length) {
                for (int j = i+1; j < nums.length; j++) {
                    int res = nums[i] + nums[j];
                    if (res == target) {
                        return new int[] { i+1, j+1 };
                    }
                }
            }
 
        }
        return nums;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

 

시간복잡도 O(n^2)

'개발 > algorithm' 카테고리의 다른 글

leetcode 3번문제 Longest Substring Without Repeating Characters  (0) 2020.04.14
leetcode 445번문제 add two numbers 2  (0) 2020.04.14
leetcode 2번문제 add two numbers  (0) 2020.04.14
leetcode 653 Two Sum IV - Input is a BST  (0) 2020.04.14
leetcode 1번문제 Two Sum  (0) 2020.04.14

문제 인티저의 배열이 주어졌을때 더했을때의 합이 target의 숫자와 일치하는 두개의 숫자의 인덱스 번호를 리턴시켜라

 

Given nums = [2, 7, 11, 15], target = 9,

 

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

 

내가 푼 답

 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
 
        }
        return nums;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

시간복잡도 O(n^2)

'개발 > algorithm' 카테고리의 다른 글

leetcode 3번문제 Longest Substring Without Repeating Characters  (0) 2020.04.14
leetcode 445번문제 add two numbers 2  (0) 2020.04.14
leetcode 2번문제 add two numbers  (0) 2020.04.14
leetcode 653 Two Sum IV - Input is a BST  (0) 2020.04.14
leetcode 167번문제 Two Sum 2 - input array is sorted  (0) 2020.04.14

+ Recent posts

티스토리툴바