當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

LeetCode 391. 完美矩形（扫描线） / 318. 最大单词长度乘积 / 563. 二叉树的坡度

發(fā)布時(shí)間：2024/1/1 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 LeetCode 391. 完美矩形（扫描线） / 318. 最大单词长度乘积 / 563. 二叉树的坡度小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

391. 完美矩形

2021.11.16 每日一題

題目描述

給你一個(gè)數(shù)組 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一個(gè)坐標(biāo)軸平行的矩形。這個(gè)矩形的左下頂點(diǎn)是 (xi, yi) ，右上頂點(diǎn)是 (ai, bi) 。

如果所有矩形一起精確覆蓋了某個(gè)矩形區(qū)域，則返回 true ；否則，返回 false 。

示例 1：

輸入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
輸出：true
解釋：5 個(gè)矩形一起可以精確地覆蓋一個(gè)矩形區(qū)域。

示例 2：

輸入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
輸出：false
解釋：兩個(gè)矩形之間有間隔，無(wú)法覆蓋成一個(gè)矩形。

示例 3：

輸入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
輸出：false
解釋：圖形頂端留有空缺，無(wú)法覆蓋成一個(gè)矩形。

示例 4：

輸入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
輸出：false
解釋：因?yàn)橹虚g有相交區(qū)域，雖然形成了矩形，但不是精確覆蓋。

提示：

1 <= rectangles.length <= 2 * 10^4
rectangles[i].length == 4
-10^5 <= xi, yi, ai, bi <= 10^5

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/perfect-rectangle
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

思路

官解給的思路，就是按照面積和每個(gè)點(diǎn)出現(xiàn)的次數(shù)來(lái)做的

class Solution {public boolean isRectangleCover(int[][] rectangles) {//看了一下提示，掃描線，但是怎么掃描呢//將這個(gè)數(shù)組按照左下角排序//然后從左到右掃描，可以確定左邊的起始位置和高度//然后如果補(bǔ)全了當(dāng)前位置的高度，就向右邊移動(dòng)掃描線，如果不行就false//看了題解，感覺(jué)自己硬想掃描線去了，忘了最基礎(chǔ)的東西//要想成為一個(gè)精確覆蓋的矩形，那么所有矩形的面積之和，應(yīng)該是和總面積相等的，這是一個(gè)大前提//但是光面積相等是不夠的，因?yàn)楸热缭谑纠?中，如果還有一個(gè)矩形，它的下標(biāo)是[1,3,4,4]//那么面積相加也是等于總面積的，但是并不是一個(gè)完美矩形，因?yàn)橛兄睾喜糠?/span>//那么如果檢測(cè)這部分呢，官解給出的方法是統(tǒng)計(jì)每個(gè)點(diǎn)的出現(xiàn)次數(shù)//如果是四個(gè)角的頂點(diǎn)，那么肯定只能出現(xiàn)一次//如果是其他頂點(diǎn)，那么出現(xiàn)兩次或者四次是正常的，如果出現(xiàn)一次或者三次，說(shuō)明肯定有沒(méi)有拼接上的地方，所以false//那么按照這個(gè)思路寫(xiě)一下Map<Point, Integer> map = new HashMap<>();long area = 0; //面積int leftdownX = Integer.MAX_VALUE;int leftdownY = Integer.MAX_VALUE;int rightupX = Integer.MIN_VALUE;int rightupY = Integer.MIN_VALUE;for(int[] rec : rectangles){int ldx = rec[0], ldy = rec[1], rux = rec[2], ruy = rec[3];area += (rux - ldx) * (ruy - ldy);leftdownX = Math.min(leftdownX, ldx);leftdownY = Math.min(leftdownY, ldy);rightupX = Math.max(rightupX, rux);rightupY = Math.max(rightupY, ruy);Point p1 = new Point(ldx, ldy);Point p2 = new Point(ldx, ruy);Point p3 = new Point(rux, ldy);Point p4 = new Point(rux, ruy);map.put(p1, map.getOrDefault(p1, 0) + 1);map.put(p2, map.getOrDefault(p2, 0) + 1);map.put(p3, map.getOrDefault(p3, 0) + 1);map.put(p4, map.getOrDefault(p4, 0) + 1);}/*System.out.println(area);System.out.println(leftdownX);System.out.println(leftdownY);System.out.println(rightupX);System.out.println(rightupY);*///四個(gè)角的頂點(diǎn)Point ld = new Point(leftdownX, leftdownY);Point lu = new Point(leftdownX, rightupY);Point rd = new Point(rightupX, leftdownY);Point ru = new Point(rightupX, rightupY);//如果面積不相等，直接falseif(area != (rightupY - leftdownY) * (rightupX - leftdownX))return false;//如果角出現(xiàn)了多次，那么fasleif(map.getOrDefault(ld, 0) != 1 || map.getOrDefault(lu, 0) != 1 || map.getOrDefault(rd, 0) != 1 || map.getOrDefault(ru, 0) != 1)return false;map.remove(ld);map.remove(lu);map.remove(rd);map.remove(ru);//判斷其他點(diǎn)for(Map.Entry<Point, Integer> entry : map.entrySet()){int count = entry.getValue();//如果不是出現(xiàn)了兩次或者四次，那么就是falseif(count != 2 && count != 4)return false;}return true;} }class Point{int x;int y;public Point(int x, int y){this.x = x;this.y = y;}public int hashCode(){return x + y;}public boolean equals(Object obj){if(this == obj)return true;if(obj == null)return false;if(obj instanceof Point){Point point = (Point)obj;return this.x == point.x && this.y == point.y;}return false;} }

看三葉姐掃描線的做法
但是這個(gè)也需要發(fā)現(xiàn)這個(gè)題的特點(diǎn)，才能寫(xiě)出來(lái)這樣的答案
三葉姐是將每個(gè)矩形用兩條豎直方向的邊（橫坐標(biāo)，豎直方向的下端點(diǎn)，豎直方向的上端點(diǎn)，是左邊/右邊的邊）來(lái)表示，那么這樣的話(huà)，左右兩個(gè)邊界的邊就只有一條，而中間的邊因?yàn)槊總€(gè)邊會(huì)在兩個(gè)矩形中出現(xiàn)，所以會(huì)出現(xiàn)兩次

class Solution {public boolean isRectangleCover(int[][] rectangles) {//三葉姐的掃描線做法，將矩形用豎線表示//然后判斷非邊緣豎線是否出現(xiàn)兩次，邊緣豎線是否出現(xiàn)一次int n = rectangles.length;//先將所有邊變成豎線int[][] rect = new int[n * 2][4];int idx = 0;for(int i = 0; i < n; i++){//當(dāng)前矩形左邊的邊，1表示是右邊的邊rect[idx++] = new int[]{rectangles[i][0], rectangles[i][1], rectangles[i][3], 1};rect[idx++] = new int[]{rectangles[i][2], rectangles[i][1], rectangles[i][3], 0};}Arrays.sort(rect, (a, b) ->(a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));//然后對(duì)這些邊進(jìn)行合并int l = 2 * n;List<int[]> left = new ArrayList<>(); //左邊的邊，也就是flag為0的邊List<int[]> right = new ArrayList<>(); //右邊的邊，也就是flag為1的邊//開(kāi)始掃描for(int i = 0; i < l; ){int r = i; //用一個(gè)新的變量代表右端點(diǎn)left.clear();right.clear();//找橫坐標(biāo)相同的部分while(r < l && rect[r][0] == rect[i][0])r++;//現(xiàn)在從i到r就是橫坐標(biāo)相同的部分 //放到list中進(jìn)行拼接//注意rect是按照第二個(gè)下標(biāo)從小到大排序的for(int j = i; j < r; j++){int[] cur = {rect[j][1], rect[j][2]};//找出此時(shí)是哪個(gè)listList<int[]> list = rect[j][3] == 0 ? left : right;//然后插入到這個(gè)list中，因?yàn)橹安迦胧前错樞騺?lái)的，所以直接取出最上面的if(list.isEmpty()){list.add(cur);}else{int[] last = list.get(list.size() - 1);//如果這兩個(gè)范圍相交了，那么falseif(last[1] > cur[0]) return false;//如果是相連的，那么連接else if(last[1] == cur[0])last[1] = cur[1];else{list.add(cur);}}}//插入完當(dāng)前下標(biāo)以后，判斷是否是成對(duì)的if(i > 0 && r < l){if(left.size() != right.size())return false;for(int j = 0; j < left.size(); j++){if(left.get(j)[0] != right.get(j)[0] || left.get(j)[1] != right.get(j)[1])return false;}//如果是邊緣的邊，看是否是一條完整的邊}else{if(left.size() + right.size() != 1)return false;}//將i置為ri = r;} return true;} }

318. 最大單詞長(zhǎng)度乘積

2021.11.17 每日一題

題目描述

給定一個(gè)字符串?dāng)?shù)組 words，找到 length(word[i]) * length(word[j]) 的最大值，并且這兩個(gè)單詞不含有公共字母。你可以認(rèn)為每個(gè)單詞只包含小寫(xiě)字母。如果不存在這樣的兩個(gè)單詞，返回 0。

示例 1:

輸入: [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
輸出: 16
解釋: 這兩個(gè)單詞為 “abcw”, “xtfn”。

示例 2:

輸入: [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
輸出: 4
解釋: 這兩個(gè)單詞為 “ab”, “cd”。

示例 3:

輸入: [“a”,“aa”,“aaa”,“aaaa”]
輸出: 0
解釋: 不存在這樣的兩個(gè)單詞。

提示：

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 僅包含小寫(xiě)字母

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-product-of-word-lengths
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

思路

26位每一位表示對(duì)應(yīng)字母是否存在
那個(gè)優(yōu)化感覺(jué)作用不大

class Solution {public int maxProduct(String[] words) {//用26位表示每個(gè)單詞中字母出現(xiàn)沒(méi)有//然后異或來(lái)檢查是否重復(fù)出現(xiàn)int n = words.length;int[] num = new int[n];for(int i = 0; i < n; i++){String s = words[i];for(char c : s.toCharArray()){int t = c - 'a';num[i] |= (1 << t);}}int max = 0;for(int i = 0; i < n; i++){String s1 = words[i];for(int j = i + 1; j < n; j++){String s2 = words[j];boolean flag = true;/*for(int k = 0; k < 26; k++){if(((num[i] >> k) & 1) == 1 && (((num[j] >> k) & 1) == 1)){flag = false;break;}}*//*for(int t = num[i]; t > 0; t -= t & -t){int temp = t & -t;if((num[j] & temp) != 0){flag = false;break;}}*/if((num[i] & num[j]) == 0)max = Math.max(max, s1.length() * s2.length());}}return max;} }

563. 二叉樹(shù)的坡度

2021.11.18 每日一題

題目描述

給定一個(gè)二叉樹(shù)，計(jì)算整個(gè)樹(shù) 的坡度。

一個(gè)樹(shù)的節(jié)點(diǎn)的坡度定義即為，該節(jié)點(diǎn)左子樹(shù)的節(jié)點(diǎn)之和和右子樹(shù)節(jié)點(diǎn)之和的差的絕對(duì)值。如果沒(méi)有左子樹(shù)的話(huà)，左子樹(shù)的節(jié)點(diǎn)之和為 0 ；沒(méi)有右子樹(shù)的話(huà)也是一樣。空結(jié)點(diǎn)的坡度是 0 。

整個(gè)樹(shù) 的坡度就是其所有節(jié)點(diǎn)的坡度之和。

示例 1：

輸入：root = [1,2,3]
輸出：1
解釋：
節(jié)點(diǎn) 2 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 3 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 1 的坡度：|2-3| = 1（左子樹(shù)就是左子節(jié)點(diǎn)，所以和是 2 ；右子樹(shù)就是右子節(jié)點(diǎn)，所以和是 3 ）
坡度總和：0 + 0 + 1 = 1

示例 2：

輸入：root = [4,2,9,3,5,null,7]
輸出：15
解釋：
節(jié)點(diǎn) 3 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 5 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 7 的坡度：|0-0| = 0（沒(méi)有子節(jié)點(diǎn)）
節(jié)點(diǎn) 2 的坡度：|3-5| = 2（左子樹(shù)就是左子節(jié)點(diǎn)，所以和是 3 ；右子樹(shù)就是右子節(jié)點(diǎn)，所以和是 5 ）
節(jié)點(diǎn) 9 的坡度：|0-7| = 7（沒(méi)有左子樹(shù)，所以和是 0 ；右子樹(shù)正好是右子節(jié)點(diǎn)，所以和是 7 ）
節(jié)點(diǎn) 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子樹(shù)值為 3、5 和 2 ，和是 10 ；右子樹(shù)值為 9 和 7 ，和是 16 ）
坡度總和：0 + 0 + 0 + 2 + 7 + 6 = 15

示例 3：

輸入：root = [21,7,14,1,1,2,2,3,3]
輸出：9

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目的范圍在 [0, 104] 內(nèi)
-1000 <= Node.val <= 1000

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-tilt
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

思路

一個(gè)簡(jiǎn)單的二叉樹(shù)后序遍歷

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/ class Solution {int sum = 0;public int findTilt(TreeNode root) {//坡度，后序遍歷吧dfs(root);return sum;}public int dfs(TreeNode root){if(root == null)return 0;int left = dfs(root.left);int right = dfs(root.right);int po = Math.abs(left - right);sum += po;return left + right + root.val;} }

總結(jié)

以上是生活随笔為你收集整理的LeetCode 391. 完美矩形（扫描线） / 318. 最大单词长度乘积 / 563. 二叉树的坡度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇：双向板受力特点_单向板与双向板的受力特点
下一篇： IE被改:http://www.686d