价格减免(2024年6月18日)
点击去力扣 ->>> 价格减免
句子
是由若干个单词组成的字符串,单词之间用单个空格分隔,其中每个单词可以包含数字、小写字母、和美元符号
'$'
。如果单词的形式为美元符号后跟着一个非负实数,那么这个单词就表示一个
价格 。
例如 "$100"
、"$23"
和 "$6"
表示价格,而 "100"
、"$"
和 "$1e5
不是。
给你一个字符串 sentence
表示一个句子和一个整数
discount
。对于每个表示价格的单词,都在价格的基础上减免
discount%
,并 更新
该单词到句子中。所有更新后的价格应该表示为一个
恰好保留小数点后两位 的数字。
返回表示修改后句子的字符串。
注意:所有价格 最多 为 10
位数字。
示例 1:
1 2 3 4 5 6 输入:sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50 输出:"there are $0.50 $1.00 and 5$ candies in the shop" 解释: 表示价格的单词是 "$1" 和 "$2" 。 - "$1" 减免 50% 为 "$0.50" ,所以 "$1" 替换为 "$0.50" 。 - "$2" 减免 50% 为 "$1" ,所以 "$1" 替换为 "$1.00" 。
示例 2:
1 2 3 4 5 6 输入:sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100 输出:"1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$" 解释: 任何价格减免 100% 都会得到 0 。 表示价格的单词分别是 "$3"、"$5"、"$6" 和 "$9"。 每个单词都替换为 "$0.00"。
提示:
1 <= sentence.length <= 105
sentence
由小写英文字母、数字、' '
和
'$'
组成
sentence
不含前导和尾随空格
sentence
的所有单词都用单个空格分隔
所有价格都是 正 整数且不含前导零
所有价格 最多 为 10
位数字
0 <= discount <= 100
官方题解
方法一:模拟
思路与算法
我们按照题目中的要求进行模拟即可。
首先我们将给定的字符串 sentence
根据空格进行分割,得到其中的每一个单词。随后我们遍历每个单词,如果该单词:
以 $ 开头; 后续至少有一个字符,且均在 [0,9]中;
那么该单词就表示一个价格。我们提取后续的字符,转换成整数,计算折扣(即乘上
1−(discount / 100),保留两位小数,再转换回字符串,并添加开头的 $
即可。
当所有单词遍历完成之后,我们就可以再加上空格,得到最终的字符串。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public String discountPrices (String sentence, int discount) { String[] words = sentence.split(" " ); for (int i = 0 ; i < words.length; i++) { String word = words[i]; if (word.charAt(0 ) == '$' && isNumeric(word.substring(1 ))) { double price = Long.parseLong(word.substring(1 )) * (1 - discount / 100.0 ); words[i] = String.format("$%.2f" , price); } } StringBuilder sb = new StringBuilder (); for (int i = 0 ; i < words.length; i++) { if (i > 0 ) { sb.append(" " ); } sb.append(words[i]); } return sb.toString(); } public boolean isNumeric (String s) { if (s.isEmpty()) { return false ; } for (int i = 0 ; i < s.length(); i++) { if (!Character.isDigit(s.charAt(i))) { return false ; } } return true ; } }
矩阵中严格递增的单元格数(2024年6月19日)
点击去力扣 ->>> 矩阵中严格递增的单元格数
给你一个下标从 1 开始、大小为 m x n
的整数矩阵 mat
,你可以选择任一单元格作为
起始单元格 。
从起始单元格出发,你可以移动到 同一行或同一列
中的任何其他单元格,但前提是目标单元格的值 严格大于
当前单元格的值。
你可以多次重复这一过程,从一个单元格移动到另一个单元格,直到无法再进行任何移动。
请你找出从某个单元开始访问矩阵所能访问的
单元格的最大数量 。
返回一个表示可访问单元格最大数量的整数。
示例 1:
1 2 3 输入:mat = [[3,1],[3,4]] 输出:2 解释:上图展示了从第 1 行、第 2 列的单元格开始,可以访问 2 个单元格。可以证明,无论从哪个单元格开始,最多只能访问 2 个单元格,因此答案是 2 。
示例 2:
1 2 3 输入:mat = [[1,1],[1,1]] 输出:1 解释:由于目标单元格必须严格大于当前单元格,在本示例中只能访问 1 个单元格。
示例 3:
1 2 3 输入:mat = [[3,1,6],[-9,5,7]] 输出:4 解释:上图展示了从第 2 行、第 1 列的单元格开始,可以访问 4 个单元格。可以证明,无论从哪个单元格开始,最多只能访问 4 个单元格,因此答案是 4 。
自己解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public int maxIncreasingCells (int [][] mat) { ArrayList<Integer> results = new ArrayList <>(); for (int i = 0 ;i<mat.length;i++){ for (int j = 0 ; j<mat[0 ].length;j++) { int res = getMin(mat, mat[i][j], i, j) + 1 ; results.add(res); } } Collections.sort(results, new Comparator <Integer>() { @Override public int compare (Integer p1, Integer p2) { return p2 - p1; } }); return results.get(0 ); } int getMin (int [][] mat,int nowNum,int line,int column) { ArrayList<Integer> max = new ArrayList <>(); for (int i = 0 ;i<mat[0 ].length;i++) { if (mat[line][i] > nowNum) { int temp = getMin(mat,mat[line][i],line,i) + 1 ; max.add(temp); } } for (int j = 0 ;j<mat.length;j++) { if (mat[j][column] > nowNum) { int temp = getMin(mat,mat[j][column],j,column) + 1 ; max.add(temp); } } if (max.isEmpty()) { return 0 ; } Collections.sort(max, new Comparator <Integer>() { @Override public int compare (Integer p1, Integer p2) { return p2 - p1; } }); return max.get(0 ); } }
报错 :超出时间限制🤣
image-20240620102354273
感觉是可以优化的。比如已经获得最短路径的单元格就不需要再去遍历了。
优化后 :
我添加了HashMap用来存储每个数字对应的最短路径值,然后每次到这个数的时候就查表。但是我漏了一个需求,同一个数字重复出现的位置不同会导致最短路径不同。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 class Solution { public int maxIncreasingCells (int [][] mat) { ArrayList<Integer> results = new ArrayList <>(); HashMap<Integer,Integer> minPath = new HashMap <>(); for (int i = 0 ;i<mat.length;i++){ for (int j = 0 ; j<mat[0 ].length;j++) { int res = getMin(mat, mat[i][j], i, j,minPath); results.add(res); } } Collections.sort(results, new Comparator <Integer>() { @Override public int compare (Integer p1, Integer p2) { return p2 - p1; } }); return results.get(0 ); } int getMin (int [][] mat,int nowNum,int line,int column,HashMap<Integer,Integer> minPath) { ArrayList<Integer> maxList = new ArrayList <>(); for (int i = 0 ;i<mat[0 ].length;i++) { if (mat[line][i] > nowNum) { if (!minPath.containsKey(mat[line][i])){ int temp = getMin(mat,mat[line][i],line,i,minPath) + 1 ; maxList.add(temp); continue ; } maxList.add(minPath.get(mat[line][i]) + 1 ); } } for (int j = 0 ;j<mat.length;j++) { if (mat[j][column] > nowNum) { if (!minPath.containsKey(mat[j][column])){ int temp = getMin(mat,mat[j][column],j,column,minPath) + 1 ; maxList.add(temp); continue ; } maxList.add(minPath.get(mat[j][column]) + 1 ); } } if (maxList.isEmpty()) { minPath.put(nowNum,1 ); return 1 ; } maxList.sort(new Comparator <Integer>() { @Override public int compare (Integer p1, Integer p2) { return p2 - p1; } }); int nowMinPath = maxList.get(0 ); minPath.put(nowNum,nowMinPath); maxList.clear(); return nowMinPath; } }
我继续改为使用遍历的方式存储每一个单元格的最路径值。并且使用HashMap,将键设置为横纵坐标拼起来的字符串,确保键唯一,即使这样,还是第424个测试用例没有通过,我已经检查不出问题了。。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 import java.util.*;public class testCode { public static void main (String[] args) { Solution solution = new Solution (); int [][] mat = {{3 ,1 ,6 },{-9 ,5 ,7 }}; int i = solution.maxIncreasingCells(mat); System.out.println(i); } } class Solution { public int maxIncreasingCells (int [][] mat) { ArrayList<Pos> results = new ArrayList <>(); HashMap<String, Pos> pos = new HashMap <>(); for (int i = 0 ;i<mat.length;i++){ for (int j = 0 ; j<mat[0 ].length;j++) { if (!pos.containsKey(String.valueOf(i) + j)){ int temp = getMin(mat,mat[i][j],i,j,pos); } } } int res = 0 ; for (Map.Entry<String, Pos> entry : pos.entrySet()) { if (entry.getValue().getMinPath() > res) { res = entry.getValue().getMinPath(); } } return res; } int getMin (int [][] mat,int nowNum,int line,int column,HashMap<String, Pos> pos) { ArrayList<Pos> maxList = new ArrayList <>(); for (int i = 0 ;i<mat[0 ].length;i++) { if (mat[line][i] > nowNum) { if (!pos.containsKey(String.valueOf(line) + i)){ int temp = getMin(mat,mat[line][i],line,i,pos); Pos pos1 = new Pos (); pos1.setNumber(nowNum); pos1.setLine(line); pos1.setColumn(column); pos1.setMinPath(temp + 1 ); maxList.add(pos1); continue ; } Pos tempPos = pos.get(String.valueOf(line) + i); Pos pos1 = new Pos (); pos1.setNumber(nowNum); pos1.setLine(line); pos1.setColumn(column); pos1.setMinPath(tempPos.getMinPath() + 1 ); maxList.add(pos1); } } for (int j = 0 ;j<mat.length;j++) { if (mat[j][column] > nowNum) { if (!pos.containsKey(String.valueOf(j) + column)){ int temp = getMin(mat,mat[j][column],j,column,pos); Pos pos1 = new Pos (); pos1.setNumber(nowNum); pos1.setLine(line); pos1.setColumn(column); pos1.setMinPath(temp + 1 ); maxList.add(pos1); continue ; } Pos tempPos = pos.get(String.valueOf(j) + column); Pos pos1 = new Pos (); pos1.setNumber(nowNum); pos1.setLine(line); pos1.setColumn(column); pos1.setMinPath(tempPos.getMinPath() + 1 ); maxList.add(pos1); } } if (maxList.isEmpty()) { Pos pos1 = new Pos (); pos1.setColumn(column); pos1.setLine(line); pos1.setNumber(nowNum); pos1.setMinPath(1 ); pos.put(String.valueOf(line) + column,pos1); return 1 ; } maxList.sort(new Comparator <Pos>() { @Override public int compare (Pos p1, Pos p2) { return p2.getMinPath() - p1.getMinPath(); } }); Pos maxPos = maxList.get(0 ); String key = String.valueOf(line) + column; if (!pos.containsKey(key)){ pos.put(key,maxPos); } return maxPos.getMinPath(); } } class Pos { int number; int line; int column; public int getMinPath () { return minPath; } public void setMinPath (int minPath) { this .minPath = minPath; } int minPath; public int getNumber () { return number; } public void setNumber (int number) { this .number = number; } public int getLine () { return line; } public void setLine (int line) { this .line = line; } public int getColumn () { return column; } public void setColumn (int column) { this .column = column; } }
官方题解
方法一:动态规划
image-20240620212415601
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public int maxIncreasingCells (int [][] mat) { int m = mat.length, n = mat[0 ].length; Map<Integer, List<int []>> mp = new HashMap <Integer, List<int []>>(); int [] row = new int [m]; int [] col = new int [n]; for (int i = 0 ; i < m; i++) { for (int j = 0 ; j < n; j++) { mp.putIfAbsent(mat[i][j], new ArrayList <int []>()); mp.get(mat[i][j]).add(new int []{i, j}); } } List<Integer> keys = new ArrayList <Integer>(mp.keySet()); Collections.sort(keys); for (int key : keys) { List<int []> pos = mp.get(key); List<Integer> res = new ArrayList <Integer>(); for (int [] arr : pos) { res.add(Math.max(row[arr[0 ]], col[arr[1 ]]) + 1 ); } for (int i = 0 ; i < pos.size(); i++) { int [] arr = pos.get(i); int d = res.get(i); row[arr[0 ]] = Math.max(row[arr[0 ]], d); col[arr[1 ]] = Math.max(col[arr[1 ]], d); } } return Arrays.stream(row).max().getAsInt(); } }
美丽下标对的数目
点击去力扣 ->>> 美丽下标对的数目
自己解答
写一个函数用来判断两个数是不是互质,返回一个布尔值。为真则自变量加1,遍历完成之后返回。判断互质我采用了辗转相除法加上递归。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public int countBeautifulPairs (int [] nums) { int res = 0 ; for (int i = 0 ;i<nums.length - 1 ;i++) { for (int j = i + 1 ;j<nums.length;j++) { String num1 = Integer.toString(nums[i]); int num_first = num1.charAt(0 ) - '0' ; String num2 = Integer.toString(nums[j]); int num_last = num2.charAt(num2.length() - 1 ) - '0' ; if (isGcd(num_first,num_last)) { res += 1 ; } } } return res; } public boolean isGcd (int num1,int num2) { if (num1 == num2 && num1 != 1 ) { return false ; } int num_max = getMaxNUm(num1,num2); int num_min = getMinNUm(num1,num2); int new_num = num_max / num_min; int remainder = num_max % num_min; if (remainder == 0 ) { if (num_min == 1 ) { return true ; }else { return false ; } } else { return isGcd(getMaxNUm(new_num,num_min),remainder); } } public int getMaxNUm (int num1,int num2) { return num1 > num2 ? num1 : num2; } public int getMinNUm (int num1,int num2) { return num1 > num2 ? num2 : num1; } }
执行结果: 只击败了5%的用户🤣
image-20240621155225154
阿文
官方题解
方法一:暴力枚举
image-20240621155621320
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int countBeautifulPairs (int [] nums) { int res = 0 , n = nums.length; for (int i = 0 ; i < n; i++) { while (nums[i] >= 10 ) { nums[i] /= 10 ; } for (int j = i + 1 ; j < n; j++) { if (gcd(nums[i], nums[j] % 10 ) == 1 ) { res++; } } } return res; } private int gcd (int a, int b) { return b == 0 ? a : gcd(b, a % b); } }
方法二:哈希表
image-20240621155655669
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int countBeautifulPairs (int [] nums) { int res = 0 ; int [] cnt = new int [10 ]; for (int x : nums) { for (int y = 1 ; y <= 9 ; y++) { if (gcd(x % 10 , y) == 1 ) { res += cnt[y]; } } while (x >= 10 ) { x /= 10 ; } cnt[x]++; } return res; } private int gcd (int a, int b) { return b == 0 ? a : gcd(b, a % b); } }
复杂度分析
image-20240621155743266
检测大写字母
点击去力扣 ->>> 检测大写字母
我们定义,在以下情况时,单词的大写用法是正确的:
全部字母都是大写,比如 "USA"
。
单词中所有字母都不是大写,比如 "leetcode"
。
如果单词不只含有一个字母,只有首字母大写, 比如
"Google"
。
给你一个字符串 word
。如果大写用法正确,返回
true
;否则,返回 false
。
示例 1:
输入:word = “USA” 输出:true
示例 2:
输入:word = “FlaG” 输出:false
提示:
1 <= word.length <= 100
word
由小写和大写英文字母组成
自己解答
想法是分三种情况考虑。第一种是全都大写,第二种是第一个字母大写其他小写,第三种是全部小写。分别实现即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { public boolean detectCapitalUse (String word) { if (word.length() == 1 ) { return true ; } if (checkBig(word.charAt(0 ))) { if (checkBig(word.charAt(1 ))) { for (int i = 2 ; i < word.length();i++) { if (!checkBig(word.charAt(i))) { return false ; } } return true ; } else { for (int i = 2 ; i < word.length();i++) { if (checkBig(word.charAt(i))) { return false ; } } return true ; } } else { for (int i = 1 ; i < word.length();i++) { if (checkBig(word.charAt(i))) { return false ; } } return true ; } } boolean checkBig (char word) { if (word >= 'A' && word <= 'Z' ) { return true ; } return false ; } }
官方题解
方法一:根据题目要求实现
思路和算法
根据题目要求,若单词的大写用法正确,则需要满足:
若第 个字母为大写,则其他字母必须均为大写或均为小写,即其他字母必须与第
个字母的大小写相同;
若第
个字母为小写,则其他字母必须均为小写。
根据以上规则,可以整理得到以下更简单的判断规则:
无论第
个字母是否大写,其他字母必须与第
个字母的大小写相同;
若第
个字母为小写,则需额外判断第
个字母是否为小写。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public boolean detectCapitalUse (String word) { if (word.length() >= 2 && Character.isLowerCase(word.charAt(0 )) && Character.isUpperCase(word.charAt(1 ))) { return false ; } for (int i = 2 ; i < word.length(); ++i) { if (Character.isLowerCase(word.charAt(i)) ^ Character.isLowerCase(word.charAt(1 ))) { return false ; } } return true ; } }
下一个更大元素 II
点击去力扣 ->>> 下一个更大元素 II
给定一个循环数组 nums
(
nums[nums.length - 1]
的下一个元素是 nums[0]
),返回 *nums
中每个元素的
下一个更大元素 。
数字 x
的 下一个更大的元素
是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出
-1
。
示例 1:
输入: 输出: 解释: 第一个 的下一个更大的数是 ; 数字 找不到下一个更大的数; 第二个 的下一个最大的数需要循环搜索,结果也是
。
示例 2:
输入: 输出:
提示:
1 <= nums.length <= 104
-109 <= nums[i] <= 109
自己解答
整体思路是遍历整个数组,然后从第一个开始,判断出第一个之后的最大值就存在 里面,然后根据需要确定是否需要再次遍历 来确定最大值。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class Solution { public int [] nextGreaterElements(int [] nums) { boolean CHECK = false ; boolean MAX = false ; int maxPos = -1 ; ArrayList<Integer> maxNum = new ArrayList (); for (int i = 0 ;i<nums.length;i++) { for (int j = i + 1 ;j<nums.length;j++) { if (nums[i] < nums[j]) { maxNum.add(nums[j]); break ; } if (j == nums.length - 1 ) { CHECK = true ; } } if (CHECK || i == nums.length - 1 ) { if (maxNum.isEmpty()) { MAX = true ; } for (int k = 0 ;k<maxNum.size();k++) { if (maxNum.get(k) == -1 && maxPos == k) { if (nums[i] == nums[k]) { maxNum.add(-1 ); break ; } maxNum.add(nums[k]); break ; } if (nums[i] < maxNum.get(k)) { if (nums[i] < nums[k]) { maxNum.add(nums[k]); break ; } maxNum.add(maxNum.get(k)); break ; } if (k == maxNum.size() - 1 ) { MAX = true ; } } CHECK = false ; } if (MAX) { maxPos = i; maxNum.add(-1 ); MAX = false ; } } int [] res = new int [maxNum.size()]; for (int i = 0 ; i < maxNum.size(); i++) { res[i] = maxNum.get(i); } return res; } }
image-20240624195930951
官方解答
方法一:单调栈 + 循环数组
思路及算法
我们可以使用单调栈解决本题。单调栈中保存的是下标,从栈底到栈顶的下标在数组
中对应的值是单调不升的。
每次我们移动到数组中的一个新的位置 ,我们就将当前单调栈中所有对应值小于
的下标弹出单调栈,这些值的下一个更大元素即为 (证明很简单:如果有更靠前的更大元素,那么这些位置将被提前弹出栈)。随后我们将位置
入栈。
但是注意到只遍历一次序列是不够的,例如序列 ,最后单调栈中将剩余 ,其中元素 的下一个更大元素还是不知道的。
一个朴素的思想是,我们可以把这个循环数组「拉直」,即复制该序列的前
个元素拼接在原序列的后面。这样我们就可以将这个新序列当作普通序列,用上文的方法来处理。
而在本题中,我们不需要显性地将该循环数组「拉直」,而只需要在处理时对下标取模即可。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int [] nextGreaterElements(int [] nums) { int n = nums.length; int [] ret = new int [n]; Arrays.fill(ret, -1 ); Deque<Integer> stack = new LinkedList <Integer>(); for (int i = 0 ; i < n * 2 - 1 ; i++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) { ret[stack.pop()] = nums[i % n]; } stack.push(i % n); } return ret; } }
复杂度分析
时间复杂度: ,其中
是序列的长度。我们需要遍历该数组中每个元素最多 次,每个元素出栈与入栈的总次数也不超过
次。
空间复杂度: ,其中
是序列的长度。空间复杂度主要取决于栈的大小,栈的大小至多为 。
找到矩阵中的好子集
点击去力扣 ->>> 找到矩阵中的好子集
给你一个下标从 0 开始大小为 m x n
的二进制矩阵 grid
。
从原矩阵中选出若干行构成一个行的 非空
子集,如果子集中任何一列的和至多为子集大小的一半,那么我们称这个子集是
好子集 。
更正式的,如果选出来的行子集大小(即行的数量)为
k,那么每一列的和至多为 floor(k / 2)
。
请你返回一个整数数组,它包含好子集的行下标,请你将其
升序 返回。
如果有多个好子集,你可以返回任意一个。如果没有好子集,请你返回一个空数组。
一个矩阵 grid
的行 子集 ,是删除
grid
中某些(也可能不删除)行后,剩余行构成的元素集合。
示例 1:
输入: 输出: 解释:我们可以选择第 和第 行构成一个好子集。 选出来的子集大小为
。
第 列的和为 ,小于等于子集大小的一半。
第 列的和为 ,小于等于子集大小的一半。
第 列的和为 ,小于等于子集大小的一半。
第 列的和为 ,小于等于子集大小的一半。
示例 2:
输入: 输出: 解释:我们可以选择第 行构成一个好子集。 选出来的子集大小为
。
示例 3:
输入:
输出:
解释:没有办法得到一个好子集。
提示:
m == grid.length
n == grid[i].length
1 <= m <= 104
1 <= n <= 5
grid[i][j]
要么是 0
,要么是
1
。
自己解法
想着用python来写的。我自己的思路是遍历取出两个行出来,使用python中的.T拿到其中一个的转置,然后看乘积是否大于等于1,若大于等于1则表示两个不满足条件,反则满足返回。但是对语法不熟悉,没有成功实现
官方解法
方法一:分类讨论
思路
对所选出来的行数进行分类讨论,有以下几种情况:
假设答案至少一行,那么需要这一行满足全为 。
假设答案至少两行,那么不存在一列这两行都是 。分别用 和
表示这两行所表示的数,能推出至少存在两行 & 。
假设答案至少三行,那么这三行每一列加起来的和不超过 。这个条件比两行的情况更严格,如果两行都找不到答案,那么一定没有三行的情况了。
假设答案至少四行,那么这四行每一列加起来的和不超过 。如果两行找不到答案,说明任选两行至少存在一列这两行都是
。同时这一列这两行已经都是 了,那么这一列的其他两行必须是 0
才满足条件。所以,当答案有四行的情况下,需要满足任选两行这一列都是 1
同时其他两行必须是 0 至少需要 列,但题意说矩阵的列数 ,因此这种情况不存在。
一般的,对于任意一行,假设答案至少需要选取 行。考虑任选两行至少存在一列这两行都是
的构造,一共需要 对构造,当这一列选择了 后,其他 行最多有 个 ,所以最多能贡献 个构造。因为 ,
所以这一行至少需要 个 才能达到 个构造,同时因为列数不超过 ,所以至多有 列是 。因此任意一行 的个数比 更多,进而推出任选 行, 的总数比
更多,无法找到一个合法的构造满足题意。
综上所述,只需要考虑答案小于等于两行的情况。每行二进制所表示的数一共有
种情况,其中 为矩阵的列数。
Java:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public List<Integer> goodSubsetofBinaryMatrix (int [][] grid) { List<Integer> ans = new ArrayList <Integer>(); Map<Integer, Integer> mp = new HashMap <Integer, Integer>(); int m = grid.length; int n = grid[0 ].length; for (int j = 0 ; j < m; j++) { int st = 0 ; for (int i = 0 ; i < n; i++) { st |= (grid[j][i] << i); } mp.put(st, j); } if (mp.containsKey(0 )) { ans.add(mp.get(0 )); return ans; } for (Map.Entry<Integer, Integer> entry1 : mp.entrySet()) { int x = entry1.getKey(), i = entry1.getValue(); for (Map.Entry<Integer, Integer> entry2 : mp.entrySet()) { int y = entry2.getKey(), j = entry2.getValue(); if ((x & y) == 0 ) { List<Integer> list = new ArrayList <Integer>(); list.add(Math.min(i, j)); list.add(Math.max(i, j)); return list; } } } return ans; } }
Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def goodSubsetofBinaryMatrix (self, grid: List [List [int ]] ) -> List [int ]: ans = [] mp = {} m = len (grid) n = len (grid[0 ]) for j in range (m): st = 0 for i in range (n): st |= (grid[j][i] << i) mp[st] = j if 0 in mp: ans.append(mp[0 ]) return ans for x, i in mp.items(): for y, j in mp.items(): if not (x & y): return [min (i, j), max (i, j)] return ans
复杂度分析
时间复杂度: ,其中
为矩阵的行数, 为矩阵的列数, 表示每一行所表示数的范围。
空间复杂度: ,其中 为矩阵的列数。
有效的括号
点击去力扣 ->>> 有效的括号
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1:
示例 2:
示例 3:
提示:
1 <= s.length <= 104
s
仅由括号 '()[]{}'
组成
自己解答
思路是利用栈来判断。遍历字符,如果遇到左边的括号,比如({[
这样的就入栈,遇到右边的字符就将栈顶的字符出栈与当前字符比较,若匹配则继续遍历,若不匹配则直接返回false
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public boolean isValid (String s) { char [] check = s.toCharArray(); Deque<Character> stack = new ArrayDeque <>(); for (char c : check){ if (c == '(' || c == '{' || c=='[' ){ stack.push(c); } if (c == ')' ) { boolean res = isSameChar('(' ,stack); if (res) { continue ; } return false ; } if (c == '}' ) { boolean res = isSameChar('{' ,stack); if (res) { continue ; } return false ; } if (c == ']' ) { boolean res = isSameChar('[' ,stack); if (res) { continue ; } return false ; } } return stack.isEmpty() ? true : false ; } public boolean isSameChar (char c,Deque<Character> stack) { if (stack.isEmpty()){ return false ; } return c == stack.pop() ? true : false ; } }
官方解答
官方跟我的思路差不多,就直接上代码了。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public boolean isValid (String s) { int n = s.length(); if (n % 2 == 1 ) { return false ; } Map<Character, Character> pairs = new HashMap <Character, Character>() {{ put(')' , '(' ); put(']' , '[' ); put('}' , '{' ); }}; Deque<Character> stack = new LinkedList <Character>(); for (int i = 0 ; i < n; i++) { char ch = s.charAt(i); if (pairs.containsKey(ch)) { if (stack.isEmpty() || stack.peek() != pairs.get(ch)) { return false ; } stack.pop(); } else { stack.push(ch); } } return stack.isEmpty(); } }
Python代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def isValid (self, s: str ) -> bool : if len (s) % 2 == 1 : return False pairs = { ")" : "(" , "]" : "[" , "}" : "{" , } stack = list () for ch in s: if ch in pairs: if not stack or stack[-1 ] != pairs[ch]: return False stack.pop() else : stack.append(ch) return not stack