기사 목록

두 갈래 나무의 깊이

평형 두 갈래 나무인지 아닌지 판단한다

수조에 숫자가 한 번만 나타납니다

와 S의 두 숫자

및 S의 연속 정수 시퀀스

단어 순서 서열을 뒤집습니다

좌회전 문자열

고리형 체인 시계의 고리 입구를 찾아라

다섯 장의 카드가 연속적인지

요셉 고리

1 + 2 +... +n

가감 곱셈을 덧셈으로 하지 않아도 된다

문자열을 숫자로 변환합니다

수조에서 중복된 숫자

두 갈래 나무를 여러 줄로 인쇄한다

문자열 흐름에서 첫 번째 중복되지 않는 문자

의 글꼴로 두 갈래 나무를 인쇄합니다

주식의 최대 이윤(수조에서 두 수차의 최대치)

데이터 흐름의 중위수

두 갈래 검색 트리의 k번째 결점

슬라이딩 창의 최대값

두 갈래 나무의 깊이

비귀속 차원 반복

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList();
        int cur = 0, width = 0;	     //cur 	
        int depth = 0;
        queue.offer(root);
        while(!queue.isEmpty())
        {
            width = queue.size();	// 
            cur = 0;				// ，cur=0
            while(cur < width)
            {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
                cur++;
            }
            depth++;
        }
        return depth;
    }
}

역귀작법

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return Math.max(left,right) + 1;
    }
}

평형 두 갈래 나무인지 아닌지를 판단하다

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null)
            return true;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        if(Math.abs(right - left) >=2)
            return false;
        return true;
    }
    public int TreeDepth(TreeNode root)
    {
        if(root == null)
            return 0;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return Math.max(left,right) + 1;
    }
}

그룹에 숫자가 한 번만 나타납니다.

일반적인 사고방식은 HashMap을 사용하는 것이고, 처음 이외의 방법은 이상한 기교를 사용하는 것이다
특이한 기교의 사고방식 요점:

0으로 한 개의 수조를 나누면 수조 중의 같은 숫자가 상쇄되고 마지막 i의 결과는 중복되지 않는 수조 또는 같다

수조의 모든 수나 후의 결과를 분석한 결과 뒤에서 첫 번째가 1인 위치를 판단하고 이 위치로 모든 수를 분류한다. 이렇게 해서 얻은 두 수는 중복되지 않는 수만 포함하고 그 다음에 각각 이 두 수에 대해 0이 또는 0이 된다

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array == null || array.length<2)
            return;
        int n = 0;
        for (int i = 0;i < array.length; i++)
        {
            n ^=array[i];
        }
        int index = findBit1(n);
        num1[0] = 0;
        for(int i = 0;i <array.length;i++)
        {
            if(isBit1(array[i],index))
            {
                num1[0] ^= array[i];
            }
            else
                num2[0] ^= array[i];
        }
    }
    public int findBit1(int n)
    {
        int index = 0;
        while ((n & 1) == 0 && index <= Integer.SIZE)
        {
            n >>= 1;
            index++;
        }
        return index;
    }
    public boolean isBit1(int n, int index)
    {
        while (index != 0)
        {
            n >>= 1;
            index--;
        }
        return ((n&1) == 1);
    }
}

S를 위한 두 개의 숫자

배열은 점차적으로 정렬된다
법 1: HashMap

import java.util.ArrayList;
import java.util.HashMap;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (array == null || array.length < 1)
            return arrayList;
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] temp = new int[2];
        int min = Integer.MAX_VALUE;
        for(int i:array)
        {
            if(!map.containsKey(sum - i))
                map.put(i,sum-i);
            else
            {
                if(i * (sum-1)<min)
                {
                    arrayList.clear();
                    arrayList.add(sum - i);
                    arrayList.add(i);
                }
            }
        }
        return arrayList;
    }
}

방법 2: 이중 포인터

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        if (array == null || array.length<1)
            return list;
        int l = 0;
        int r = array.length - 1;
        while (l <= r)
        {
            int temp = array[l] + array[r];
            if (temp == sum)
            {
                list.add(array[l]);
                list.add(array[r]);
                break;
            }
            if (temp < sum)
                l++;
            if (temp > sum)
                r--;
        }
        return list;
    }
}

및 S의 연속 정수 시퀀스

쌍바늘의 기교

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
        int l = 1;
        int r = 2;
        while (l < r)
        {
            int cur = getSum(l,r);
            if (cur == sum)
            {
                ArrayList<Integer> list = new ArrayList<>();
                for(int i = l; i <= r;i++)
                    list.add(i);
                allList.add(list);
                r++;
            }
            else if(cur > sum)
            {
                l++;
            }
            else if(cur < sum)
            {
                r++;
            }
        }
        return allList;
    }

    public int getSum(int m, int n)
    {
        int sum = 0;
        for (int i = m; i <= n;i++)
        {
            sum += i;
        }
        return sum;
    }
}

단어 순서 시퀀스 뒤집기

먼저 전체를 뒤집고 단어 하나하나를 뒤집습니다. 주의해야 할 것은 여러 개의 빈칸을 입력하면 Trim () 기교를 사용할 수 있습니다.
비교적 폭력적인 방법은 뒤에서 하나씩 처리하는 것이다

public class Solution {
    public String ReverseSentence(String str) {
        if (str.trim().equals(""))	// 
            return str;
        String temp = reverse(str);
        String [] strr = temp.split(" ");
        for(int i = 0;i < strr.length;i++)
        {
            strr[i] = reverse(strr[i]);
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < strr.length;i++)
        {
            sb.append(strr[i] + " ");
        }
        return sb.toString().trim(); //trim() 
    }
    public String reverse(String str)
    {
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString();
    }
}

좌회전 문자열

왼쪽으로 이동할 문자열을 먼저 뒤집은 다음 전체 문자열을 뒤집습니다

public class Solution {
    public String LeftRotateString(String str,int n) {
        if (str.trim() == "")
            return str;
        if (n > str.length())
            return "";
        StringBuilder sb = new StringBuilder(str);
        StringBuilder sb1 = new StringBuilder(sb.substring(0,n));
        StringBuilder sb2 = new StringBuilder(sb.substring(n));
        sb.replace(0,n,sb1.reverse().toString());
        sb.replace(n,sb.length(),sb2.reverse().toString());
        return sb.reverse().toString();
    }
}

폭력적 방법

public class Solution {
    public String LeftRotateString(String str,int n) {
        if (str == null || str.length() < 1)
            return "";
        StringBuilder temp = new StringBuilder();
        for (int i = 0; i < n; i++)
        {
            temp.append(str.charAt(i));
        }
        StringBuilder sb = new StringBuilder(str);
        sb.delete(0,n);
        for (int i = 0; i < temp.length(); i++)
        {
            sb.append(temp.charAt(i));
        }
        return sb.toString();
    }
}

고리형 체인 시계의 고리 입구를 찾다

먼저 두 개의 포인터를 정의하고 두 개의 포인터가 만나는 점을 찾은 다음에 한 포인터를 머리 결점을 가리키고 두 포인터를 동시에 뒤로 이동하며 다시 만나는 결점은 링 입구이다

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if (pHead == null || pHead.next == null || pHead.next.next == null)
            return null;
        ListNode p1 = pHead.next;
        ListNode p2 = pHead.next.next;
        int count = 1;
        while (p1 != p2) {
            if (p2.next != null && p2.next.next!= null)
            {
                p1 = p1.next;
                p2 = p2.next.next;
            }
            else
                return null;
        }
        p1 = pHead;
        while (p1 != p2)
        {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

5장의 카드가 연속적인지 아닌지

짝이 있으면false로 돌아가야 합니다. 0은 어떤 카드로도 사용할 수 있습니다.

import java.util.Arrays;

public class Solution {
    public boolean isContinuous(int [] numbers) {
        if (numbers == null || numbers.length != 5 )
            return false;
        Arrays.sort(numbers);
        int zeroSum = 0;
        int blank = 0;
        for (int i = 0; i < numbers.length - 1; i++)
        {
            if (numbers[i] == 0)
            {
                zeroSum++;
                continue;
            }
            if (numbers[i + 1] == numbers[i])
                return false;
            blank += numbers[i + 1] - numbers[i] - 1;
        }
        if (blank <= zeroSum)
            return true;
        return false;
    }
}

요셉 고리

폭력 해법, 체인 시뮬레이션

import java.util.LinkedList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0;i < n;i++)
        {
            list.add(i);
        }
        int index = 0;
        while (list.size() > 1)
        {
            index = (index + m - 1)%list.size();
            list.remove(index);
        }
        return list.size() == 1 ? list.get(0):-1;
    }
}

밀다

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n < 1 || m < 1)
            return -1;
        if(n == 1)
            return 0;
        return (LastRemaining_Solution(n-1, m)+m)%n;
    }
}

구하다 1 + 2 +... + n

조건문 사용 불가

public class Solution {
    public static int Sum_Solution(int n) {
        int sum = n;
        boolean flag = (sum > 0) && ((sum += Sum_Solution(--n))> 0);
        return sum;
    }
}

가감 곱하기 를 하지 않고 덧셈 을 하다

public class Solution {
    public int Add(int num1,int num2) {
        do {
            int sum = num1 ^ num2; // 
            int temp = (num1 & num2)<<1;// 
            num1 = sum;
            num2 = temp;
        }
        while (num2 != 0);
            return num1;
    }
}

문자열을 숫자로 변환하기

 public class Solution {
    public static int StrToInt(String str) {
        if (str == null)
            return 0;
        str = str.trim();
        if (str.length() == 0)
            return 0;
        int flag = 1;
        int index = 0;
        if (str.charAt(0) == '+')
            index++;
        if (str.charAt(0) == '-')
        {
            flag = -1;
            index++;
        }
        int sum = 0;
        for (int i = index; i < str.length(); i++)
        {
            if (str.charAt(i) < '0' || str.charAt(i) > '9')
                return 0;
            int n = flag > 0?((int)(str.charAt(i) - '0')):((int)('0' - str.charAt(i)));
            sum = sum * 10 + n;
            // ， ， 
            if (sum >= 0 && flag < 0 || sum < 0 && flag > 0)
                return 0;
        }
        return sum;
    }
}

배열에서 중복된 숫자

수조 자체의 특성을 이용하다

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || numbers.length == 0)
            return false;
        for (int i:numbers)
        {
            if (i < 0 || i >=length)
                return false;
        }
        for (int j = 0; j < numbers.length; j++)
        {
            while (j != numbers[j])
            {
                if (numbers[j] == numbers[numbers[j]])
                {
                    duplication[0] = numbers[j];
                    return true;
                }
                int temp = numbers[j];
                numbers[j] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
}

Hash법

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || numbers.length == 0)
            return false;
        for (int i:numbers)
        {
            if (i < 0 || i >=length)
                return false;
        }
        boolean[] bool = new boolean[length];
        for (int i = 0; i < length; i++)
        {
            if (bool[numbers[i]] == true)
            {
                duplication[0] = numbers[i];
                return true;
            }
            else
                bool[numbers[i]] = true;
        }
        return false;
    }
}

두 갈래 나무를 여러 줄로 인쇄하다

비귀속 문법

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if (pRoot == null)
            return allList;
        Queue<TreeNode> queue = new LinkedList<>();
        int width = 0;
        int cur = 0;
        queue.offer(pRoot);
        while (!queue.isEmpty())
        {
            width = queue.size();
            cur = 0;
            ArrayList<Integer> list = new ArrayList<>();
            while (cur < width)
            {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right !=null)
                    queue.offer(node.right);
                cur++;
            }
            allList.add(list);
        }
        return allList;
    }
}

역귀작법

import java.util.ArrayList;

public class Solution {
    ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if (pRoot == null)
            return allList;
        dfs(pRoot,1,allList);
        return allList;
    }
    void dfs(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list)
    {
        if (depth > list.size())
            list.add(new ArrayList<>());
        list.get(depth-1).add(root.val);
        if (root.left != null)
            dfs(root.left,depth+1,list);
        if (root.right != null)
            dfs(root.right,depth+1,list);
    }
}

문자열 흐름 중 첫 번째 중복되지 않는 문자

public class Solution {
    //Insert one char from stringstream
    String s = "";
    char[] hash = new char[128];
    public void Insert(char ch)
    {
        s += ch;
        hash[ch]++;
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for (int i = 0; i<s.length();i++)
        {
            if (hash[s.charAt(i)] == 1)
                return s.charAt(i);
        }
        return '#';
    }
}

글꼴 인쇄 두 갈래 트리

법 1: 창고를 빌려 쓴다.왼쪽 트리를 통해 창고에 들어가는 순서에 따라 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 구축됩니다.

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if (pRoot == null)
            return allList;
        int layer = 1;
        Stack<TreeNode> stack1 = new Stack<>(); // 
        Stack<TreeNode> stack2 = new Stack<>(); // 
        stack1.push(pRoot);
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            if (layer % 2 != 0) {
                while (!stack1.isEmpty()) {
                    TreeNode node = stack1.pop();
                    if (node != null) {
                        list.add(node.val);
                        if (node.left != null) stack2.push(node.left);
                        if (node.right != null) stack2.push(node.right);
                    }
                }
                layer++;
                allList.add(list);
            }
            else if (layer % 2 == 0) {
                while (!stack2.isEmpty()) {
                    TreeNode node2 = stack2.pop();
                    if (node2 != null) {
                        list.add(node2.val);
                        if (node2.right != null) stack1.push(node2.right);
                        if (node2.left != null) stack1.push(node2.left);
                    }
                }
                layer++;
                allList.add(list);
            }
        }
        return allList;
    }
}

법 2: 차원 반복, 짝수 만나면 목록 반전

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    ArrayList<ArrayList<Integer>> allList = new ArrayList<>();
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if (pRoot == null)
            return allList;
        int layer = 1;
        int cur;
        int width;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while (!queue.isEmpty()) {
            width = queue.size();
            cur = 0;
            ArrayList<Integer> list = new ArrayList<>();
                while (cur < width) {
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                    cur++;
                }
                if (layer %2 != 0)
                {
                    layer++;
                    allList.add(list);
                }
                else if (layer %2 == 0)
                {
                    layer++;
                    allList.add(reverseList(list));
                }
        }
        return allList;
    }
    public ArrayList<Integer> reverseList(ArrayList<Integer> list)
    {
        ArrayList<Integer> newList = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--)
        {
            newList.add(list.get(i));
        }
        return newList;
    }
}

주식의 최대 이윤(수조에서 두 수차의 최대치)

public class Solution {
    public static int getMaxDiff(int[] nums)
    {
        if (nums == null || nums.length<2)
            return 0;
        int min = nums[0];
        int maxDiff = nums[1] - min;
        for (int i = 2; i < nums.length; i++)
        {
            if (nums[i -1] < min)
                min = nums[i -1];
            int curDiff = nums[i] - min;
            if (curDiff > maxDiff)
                maxDiff = curDiff;
        }
        return maxDiff;
    }
    public static void main(String[] args) {
        int[] nums = {9,11,8,5,7,12,16,14};
        System.out.println(getMaxDiff(nums));
    }
}

데이터 흐름의 중위수

법 1, 크기 더미
입력이 홀수이면 앞부분의 최대 중위수
만약 입력이 짝수라면, 중위수는 큰 덤프와 작은 덤프 값의 절반이다
두 무더기는 항상 만족해야 한다.
큰 무더기의 더미 원소는 작은 무더기의 더미 원소보다 작거나 같다
큰 무더기의 원소 개수 과부하는 작은 무더기의 원소 개수와 같거나 많음1
두 개의 무더기 원소가 짝수일 때, 큰 무더기에 한 개의 원소를 더 넣기 위해, 큰 무더기->작은 무더기->큰 무더기
원소가 기수일 때, 이때 작은 무더기는 반드시 하나의 원소를 더 쌓아야 한다. 이렇게 하면 큰 무더기와 작은 무더기의 원소 개수가 같아진다. 큰 무더기->작은 무더기

import java.util.PriorityQueue;

public class Solution {

    PriorityQueue<Integer> minQueue = new PriorityQueue<>();
    PriorityQueue<Integer> maxQueue = new PriorityQueue<>((x,y)->(y-x));
    int count = 0;
    public void Insert(Integer num) {
        count++;
        maxQueue.offer(num);
        minQueue.offer(maxQueue.poll());
        if (count % 2 != 0)
            maxQueue.offer(minQueue.poll());
    }

    public Double GetMedian() {
        if (count % 2 == 0)
            return (double)(maxQueue.peek() + minQueue.peek())/2;
        else
            return (double)maxQueue.peek();
    }
}

두 갈래 검색 트리의 k 번째 결점

직접 귀속

public class Solution {
    int count = 0;
    public TreeNode KthNode(TreeNode pRoot, int k)
    {
        if (pRoot!=null)
        {
            TreeNode LNode = KthNode(pRoot.left,k);
            if (LNode != null)
                return LNode;
            count++;
            if (count == k)
                return pRoot;
            TreeNode RNode = KthNode(pRoot.right,k);
            if (RNode != null)
                return RNode;
        }
        return null;
    }
}

활용단어참조

import java.util.ArrayList;

public class Solution {
    ArrayList<TreeNode> list = new ArrayList<>();
    public TreeNode KthNode(TreeNode pRoot, int k)
    {
        if (pRoot == null || k <=0)
            return null;
        dfs(pRoot);
        if (k > list.size())
            return null;
        return list.get(k-1);
    }
    public void dfs(TreeNode root)
    {
        if (root.left != null)
            dfs(root.left);
        list.add(root);
        if (root.right != null)
            dfs(root.right);
    }
}

슬라이딩 창 최대값

양단 대기열

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> list = new ArrayList<>();
        if (num == null || num.length <=0 || size == 0 || size > num.length)
            return list;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < size; i++)
        {
            while (!deque.isEmpty() && num[i] > num[deque.peekLast()])
                deque.removeLast();
            deque.addLast(i);
        }
        for (int i = size; i < num.length; i++)
        {
            list.add(num[deque.peekFirst()]);
            while (!deque.isEmpty() &&  num[i] >= num[deque.peekLast()])
                deque.removeLast();
            if (!deque.isEmpty() &&  (i - deque.peekFirst()) >= size)
                deque.removeFirst();
            deque.addLast(i);
        }
        list.add(num[deque.peekFirst()]);
        return list;
    }
}

폭력 해법

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer
            > maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> list = new ArrayList<>();
        if (num == null || size == 0 || num.length <= 0 || num.length < size)
            return list;
        int []max = new int[2];
        int i = 0;
        int j = size - 1;
        while (j <= num.length - 1)
        {
            max = findMax(num,i,j);
            list.add(max[1]);
            i++;j++;
        }
        return list;
    }
    public int[] findMax(int[] num, int l, int r)
    {
        int max = num[l];
        int maxIndex = l;
        for (int i = l; i <= r; i++)
        {
            if (num[i] > max)
            {
                max = num[i];
                maxIndex = i;
            }
        }
        return new int[]{maxIndex,max};
    }
}