Runtime: 1 ms, faster than 85.87% of Java online submissions for Maximum Subarray.
O(N) 코드
classSolution{publicintmaxSubArray(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를 구하기 위해서 필요함.
publicclassSolution{int max =0;int[] nums ;publicintmaxSubArray(int[] nums){
max = nums[0];this.nums = nums;divideAndConquer(0, nums.length-1);return max;}public Data divideAndConquer(int start,int end){
Data data =newData();if(start == end){
data.full = nums[start];
data.leftMost = nums[start];
data.rightMost = nums[start];
max = Math.max(max ,data.full);return data;}elseif(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;}}classData{int leftMost;int full;int rightMost;}
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.
classSolution{publicintbitwiseComplement(int N){if(N==0){return1;}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;}}
두번째 코드
classSolution{publicintbitwiseComplement(int N){int digit =1;int n = N;while((n= n >>1)>0){
digit++;}int compare =(2<< digit-1)-1;return N^compare;}}
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.
classSolution{publicbooleanrepeatedSubstringPattern(String s){//abcabcabcabcchar[] arr = s.toCharArray();// distancefor(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){returntrue;}}returnfalse;}}
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.
방문한 곳은 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.
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.
실제 코인의 이동이 아니라 코인이 없더라도 음수대로 값을 채움 ( 있는것처럼 가상의 코인을 움직인다 )
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.
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
classSolution{public String removeDuplicates(String S){// "abbaca"if(S.length()<=1){return S;}char[] chars = S.toCharArray();
Stack<Character> stack =newStack<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 =newchar[stack.size()];int index = stack.size()-1;while(!stack.isEmpty()){
Character last = stack.pop();
result[index--]= last;}returnnewString(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.
classSolution{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 =newStringBuilder();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 =newchar[resltLenth];int resultIndex =0;for(int i=0; i<chars.length; i++){if(chars[i]!='0'){
result[resultIndex++]= chars[i];}}returnnewString(result);
