力扣算法记录

Abei2024-06-182024-07-10

算法！算法！算法！！！

价格减免（2024年6月18日）

点击去力扣 ->>> 价格减免

句子是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 '$' 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个价格。

例如 "$100"、"$23" 和 "$6" 表示价格，而 "100"、"$" 和 "$1e5 不是。

给你一个字符串 sentence 表示一个句子和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并更新该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。

返回表示修改后句子的字符串。

注意：所有价格最多为 10 位数字。

示例 1：

输入：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：

输入：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），保留两位小数，再转换回字符串，并添加开头的 $ 即可。

当所有单词遍历完成之后，我们就可以再加上空格，得到最终的字符串。

代码：

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：

diag1drawio

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 。

自己解答

遍历每一个单元格进行获取最短路径。

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);
    }
}

报错：超出时间限制🤣

感觉是可以优化的。比如已经获得最短路径的单元格就不需要再去遍历了。

优化后：

我添加了HashMap用来存储每个数字对应的最短路径值，然后每次到这个数的时候就查表。但是我漏了一个需求，同一个数字重复出现的位置不同会导致最短路径不同。

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个测试用例没有通过，我已经检查不出问题了。。。。

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);
//                    temp.setMinPath(temp.getMinPath() + 1);
//                    pos.put(String.valueOf(i) + j,temp);
                }
            }
        }
        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(maxPos.getLine()) + maxPos.getColumn();
        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;
    }
}

官方题解

方法一：动态规划

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>(); // 存放相同数值的答案，便于后续更新 row 和 col
            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，遍历完成之后返回。判断互质我采用了辗转相除法加上递归。

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%的用户🤣

阿文

官方题解

方法一：暴力枚举

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);
    }
}

方法二：哈希表

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);
    }
}

复杂度分析

检测大写字母

点击去力扣 ->>> 检测大写字母

我们定义，在以下情况时，单词的大写用法是正确的：

全部字母都是大写，比如 "USA" 。
单词中所有字母都不是大写，比如 "leetcode" 。
如果单词不只含有一个字母，只有首字母大写，比如 "Google" 。

给你一个字符串 word 。如果大写用法正确，返回 true ；否则，返回 false 。

示例 1：

输入：word = “USA” 输出：true

示例 2：

输入：word = “FlaG” 输出：false

提示：

1 <= word.length <= 100
word 由小写和大写英文字母组成

自己解答

想法是分三种情况考虑。第一种是全都大写，第二种是第一个字母大写其他小写，第三种是全部小写。分别实现即可

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;
    }
}

官方题解

方法一：根据题目要求实现

思路和算法

根据题目要求，若单词的大写用法正确，则需要满足：

若第个字母为大写，则其他字母必须均为大写或均为小写，即其他字母必须与第个字母的大小写相同；

若第个字母为小写，则其他字母必须均为小写。

根据以上规则，可以整理得到以下更简单的判断规则：

无论第个字母是否大写，其他字母必须与第个字母的大小写相同；

若第个字母为小写，则需额外判断第个字母是否为小写。

代码：

class Solution {
    public boolean detectCapitalUse(String word) {
        // 若第 1 个字母为小写，则需额外判断第 2 个字母是否为小写
        if (word.length() >= 2 && Character.isLowerCase(word.charAt(0)) && Character.isUpperCase(word.charAt(1))) {
            return false;
        }
        
        // 无论第 1 个字母是否大写，其他字母必须与第 2 个字母的大小写相同
        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

自己解答

整体思路是遍历整个数组，然后从第一个开始，判断出第一个之后的最大值就存在里面，然后根据需要确定是否需要再次遍历来确定最大值。

代码：

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;
    }
}

官方解答

方法一：单调栈 + 循环数组

思路及算法

我们可以使用单调栈解决本题。单调栈中保存的是下标，从栈底到栈顶的下标在数组中对应的值是单调不升的。

每次我们移动到数组中的一个新的位置，我们就将当前单调栈中所有对应值小于的下标弹出单调栈，这些值的下一个更大元素即为（证明很简单：如果有更靠前的更大元素，那么这些位置将被提前弹出栈）。随后我们将位置入栈。

但是注意到只遍历一次序列是不够的，例如序列，最后单调栈中将剩余，其中元素的下一个更大元素还是不知道的。

一个朴素的思想是，我们可以把这个循环数组「拉直」，即复制该序列的前个元素拼接在原序列的后面。这样我们就可以将这个新序列当作普通序列，用上文的方法来处理。

而在本题中，我们不需要显性地将该循环数组「拉直」，而只需要在处理时对下标取模即可。

代码：

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:

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:

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：

1 2	输入：s = "()" 输出：true

示例 2：

1 2	输入：s = "()[]{}" 输出：true

示例 3：

1 2	输入：s = "(]" 输出：false

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

自己解答

思路是利用栈来判断。遍历字符，如果遇到左边的括号，比如（{[ 这样的就入栈，遇到右边的字符就将栈顶的字符出栈与当前字符比较，若匹配则继续遍历，若不匹配则直接返回false

代码：

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;
    }
}

官方解答

官方跟我的思路差不多，就直接上代码了。

代码：

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代码：

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