2020-3-28

820.单词的压缩编码

✒解题思路：

1. 字典树

class Solution {
	public int minimumLengthEncoding(String[] words) {
		Trie trie = new Trie();
		int len = 0;
		Arrays.sort(words, (s1, s2) -> s2.length() - s1.length());
		for (String s : words) {
			len += trie.insert(s);
		}
		return len;
	}

	class TrieNode {
		char val;
		TrieNode[] children = new TrieNode[26];
	}

	class Trie {
		TrieNode root;

		public Trie() {
			root = new TrieNode();
		}

		public int insert(String word) {
			TrieNode cur = root;
			boolean isNew = false;
			for (int i = word.length() - 1; i >= 0; i--) {
				int c = word.charAt(i) - 'a';
				if (cur.children[c] == null) {
					isNew = true;
					cur.children[c] = new TrieNode();
				}
				cur = cur.children[c];
			}
			return isNew ? word.length() + 1 : 0;
		}
	}
}

1161.最大层内元素和

✒解题思路：

1. BFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public int maxLevelSum(TreeNode root) {
		if (root.left == null && root.right == null) {
			return 1;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		int m = 1;
		int sum = root.val;
        int result = sum;
		while (!queue.isEmpty()) {
			int size = queue.size();
			int temp = 0;
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				temp += node.val;
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			if (temp > sum) {
                sum = temp;
				result = m;
			}
            m++;
		}
		return result;
	}
}