weekly sdudy 002
from 2022-08-22 to 2022-08-28
1 Algorithm
- leetcode 655.输出二叉树
class Solution {
private final String BLANK = "";
private int height = 0;
int m = 0;
int n = 0;
int r = 0;
int c = 0;
private final List<List<String>> res = new ArrayList<>();
public List<List<String>> printTree(TreeNode root) {
height = traverse(root) - 1;
m = height + 1;
n = (int)Math.pow(2, height + 1) - 1;
r = 0;
c = (n - 1) / 2;
fill();
build(root, r, c);
return res;
}
private void fill() {
for(int i = 0; i < m; i++) {
List<String> currentLevel = new ArrayList<>(n);
for(int j = 0; j < n; j++) {
currentLevel.add(BLANK);
}
res.add(currentLevel);
}
}
private void build(TreeNode root, int r, int c) {
if(root == null) {
return;
}
res.get(r).set(c, String.valueOf(root.val));
build(root.left, r + 1, (int) (c - Math.pow(2, height - r -1)));
build(root.right, r + 1, (int) (c + Math.pow(2, height - r -1)));
}
private int traverse(TreeNode root) {
if(root == null) {
return 0;
。。。 }
int leftHeight = traverse(root.left);
int rightHeight = traverse(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
- 1445.检查单词是否为句中其他单词的前缀
static class Solution {
public static int isPrefixOfWord(String sentence, String searchWord) {
int sentenceIndex = 0;
int wordIndex = 0;
int res = 1;
while(sentenceIndex < sentence.length()) {
if(Character.isWhitespace(sentence.charAt(sentenceIndex))) {
sentenceIndex++;
res++;
}
while(sentence.charAt(sentenceIndex) == searchWord.charAt(wordIndex)) {
if(wordIndex == searchWord.length() - 1) {
return res;
}
sentenceIndex++;
wordIndex++;
}
wordIndex = 0;
while(sentenceIndex < sentence.length() && !Character.isWhitespace(sentence.charAt(sentenceIndex))) {
sentenceIndex++;
}
}
return -1;
}
public static void main(String[] args) {
int prefixOfWord = isPrefixOfWord("dumb dream duck duck i", "dream");
System.out.println(prefixOfWord);
}
}
- 1460.通过翻转子数组使两个数组相等
class Solution {
public boolean canBeEqual(int[] target, int[] arr) {
Arrays.sort(target);
Arrays.sort(arr);
for(int i = 0; i < target.length; i++) {
if(target[i] != arr[i]) {
return false;
}
}
return true;
}
}
- 658.找到 K 个最接近的元素
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int left = 0;
int right = arr.length - 1;
while(right - left != k -1) {
if(x - arr[left] > arr[right] - x) {
left++;
} else {
right--;
}
}
List<Integer> res = new ArrayList<>();
for(int i = left; i <= right; i++) {
res.add(arr[i]);
}
return res;
}
}
- 1464.数组中两元素的最大乘积
class Solution {
public int maxProduct(int[] nums) {
int left = 0, right = nums.length - 1, max = Integer.MIN_VALUE;
while(left < right) {
max = Math.max(max, (nums[right] - 1) * (nums[left] - 1));
if(nums[left] < nums[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
class Solution1 {
public int maxProduct(int[] nums) {
int max0 = Integer.MIN_VALUE, max1 = Integer.MIN_VALUE;
for(int num : nums) {
if(num >= max0) {
max1 = max0;
max0 = num;
} else if(num >= max1){
max1 = num;
}
}
return (max0 - 1) * (max1 - 1);
}
}
- 662.二叉树最大宽度(
public int widthOfBinaryTree(TreeNode root) {
if(root == null) {
return 0;
}
List<Pair<TreeNode, Integer>> currentLevel = new ArrayList<>();
currentLevel.add(new Pair<>(root, 1));
int res = 1;
while(!currentLevel.isEmpty()) {
List<Pair<TreeNode, Integer>> nextLevel = new ArrayList<>();
for (Pair<TreeNode, Integer> treeNodeIntegerPair : currentLevel) {
if (treeNodeIntegerPair.getKey().left != null) {
nextLevel.add(new Pair<>(treeNodeIntegerPair.getKey().left, treeNodeIntegerPair.getValue() * 2));
}
if (treeNodeIntegerPair.getKey().right != null) {
nextLevel.add(new Pair<>(treeNodeIntegerPair.getKey().right, treeNodeIntegerPair.getValue() * 2 + 1));
}
}
res = Math.max(currentLevel.get(currentLevel.size() - 1).getValue() - currentLevel.get(0).getValue() + 1, res);
currentLevel = nextLevel;
}
return res;
}
- 172.阶乘后的零
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while(n >= 5) {
count += n / 5;
n = n / 5;
}
return count;
}
}
2 Reading
3 English Writing
is an entry ticket to : …… 是获得……（成功、健康、爱情）等的通行证
【相似句型】be a passport to sth
【例句精选】
a. But Tadateru Konoe, the IFRC's Japanese persident, reports that neutrality is still an entry ticket to many disaster zones.(The Economist)
但是红十字会与红新月会国际联合会的日裔主席近卫忠辉反驳说，保持中立仍旧是进入许多灾难地区的通行证。
b. While firms' profits have soared, wages for typical worker have barely budged. The middle class——admittedly a vague term in America——feels squeezed. A college degree is no longer a passport to ever-higher pay.(The Economist)
企业利润暴涨，但普通工人的工资几乎没有变动。中产阶级——一个在美国已变得模糊的概念——感到被挤压。大学学位已经不再是获得高薪的保证。