2019-04-09 BFS 광도 우선 검색 문제 해결 Day1

Leetcode 101 대칭 두 갈래 나무

제목 설명:

두 갈래 나무를 정해서 거울이 대칭적인지 확인하세요.
예를 들어 두 갈래 나무[1,2,2,3,4,3]는 대칭적이다.

    1
  2   2
3  4 4  3

다음은 이게 짝짝이에요.

    1
   / \
  2   2
   \   \
   3    3

생각:

유사한 차원을 두루 돌아다니는 방법은 하나의 대열을 유지하고 뿌리 노드의 왼쪽 아이와 오른쪽 아이가 먼저 순서대로 들어가고 그 후의 층의 노드 수가 4보다 많기 때문에 일정한 순서에 따라 대열을 가입할 수 있다. 왼쪽, 오른쪽, 왼쪽, 오른쪽, 왼쪽, 그 다음에 매번 튀어나오는 두 노드 값이 같은지 아닌지를 순환하면 된다.

코드:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null){
            return true;
        }
        if (root.left==null && root.right==null){
            return true;
        }
        if (root.left!=null&&root.right==null || root.left==null&&root.right!=null){
            return false;
        }
        
        LinkedList queue=new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        
        while (!queue.isEmpty()){
            TreeNode le=queue.poll();
            TreeNode ri=queue.poll();
            if (le==null&&ri==null){
                continue;
            }
            if (le==null||ri==null||le.val!=ri.val){
                return false;
            }
            queue.offer(le.left);
            queue.offer(ri.right);
            queue.offer(le.right);
            queue.offer(ri.left);
        }
        return true;
    }
}

LeetCode 127 단어 접용

제목 설명

두 단어 (beginWord와 endWord) 와 사전을 지정해서 beginWord에서 endWord로 가장 짧은 변환 서열의 길이를 찾습니다.변환은 다음과 같은 규칙을 따릅니다.

매번 변환할 때마다 한 글자만 바뀔 수 있다..

변환 과정 중의 중간 단어는 반드시 사전의 단어이어야 한다..

설명:

이러한 변환 시퀀스가 없으면 0으로 돌아갑니다

모든 단어는 같은 길이를 가지고 있다..

모든 단어는 소문자로만 구성되어 있다..

사전에는 중복된 단어가 없습니다

당신은 beginWord와 endWord가 비어 있고 양자가 다르다고 가정할 수 있습니다

예제 1
입력: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"] 출력: 5 설명: 가장 짧은 변환 서열은 "hit"-> "hot"-> "dot"-> "dog"-> "cog"입니다. 길이를 5로 되돌려줍니다.

코드

class Solution {
    public int ladderLength(String beginWord, String endWord, List wordList) {
        if (wordList==null || !wordList.contains(endWord)){
            return 0;
        }
        Queue queue=new LinkedList();
        Set words=new HashSet<>(wordList);
        queue.offer(beginWord);
        int count=1;
        while (!queue.isEmpty()){
            int size=queue.size();
            count++;
            for (int i=0;i candidates=bfs(words,word);
                for (String candidate:candidates){
                    if (endWord.equals(candidate)){
                        return count;
                    }
                    queue.offer(candidate);
                }
            }
        }
        return 0;
    }
    
    public List bfs(Set words,String word){
        List candidates=new ArrayList<>();
        StringBuffer sb=new StringBuffer(word);
        for (int i=0;i