java数据结构刷题二期-Toy模板网

这篇具有很好参考价值的文章主要介绍了java数据结构刷题二期。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。

给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1：

输入：mat = [[1,2],[3,4]], r = 1, c = 4
输出：[[1,2,3,4]]
示例 2：

输入：mat = [[1,2],[3,4]], r = 2, c = 4
输出：[[1,2],[3,4]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reshape-the-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        //给定参数不合理
        if(r * c != mat.length * mat[0].length){
            return mat;
        }
        //参数合理
        int[][] arr = new int[r][c];
        int n = mat[0].length;//原数组的列数
        //将二维数组映射到一维数组中
        //映射行：元素位数 / 数组列数
        //映射列：元素位数 % 数组列数
        for (int i = 0; i < r * c; i++) {
            arr[i / c][i % c] = mat[i / n][i % n];
        }
        return arr;
    }
}

作者：frosty-7ichtermanwgr
链接：https://leetcode.cn/problems/reshape-the-matrix/solution/566-zhong-su-ju-zhen-by-frosty-7ichterma-fjcl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二
class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length, n = mat[0].length, x = 0;
        if(m * n != r * c) return mat;
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                hash.put(x++, mat[i][j]);
            }
        }
        int[][] newMat = new int[r][c];
        for(int i = 0; i < r; ++i){
            for(int j = 0; j < c; ++j){
                newMat[i][j] = hash.get(i*c + j);
            }
        }


作者：azure-ku
链接：https://leetcode.cn/problems/reshape-the-matrix/solution/hashmapshi-xian-by-azure-ku-9tq9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目二

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

java数据结构刷题二期

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

class Solution {
    public static List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> integers1 = new ArrayList<>();
        //定义一个临时存储上一行结果的集合
        ArrayList<Integer> temp = integers1;
        for (int i = 1; i <= numRows; i++) {
            temp = getRow(temp, i);
            lists.add(temp);
        }
        return lists;
    }
    //该方法通过上一行的数据计算出本行的数据
    public static ArrayList<Integer> getRow(List<Integer> list, int n) {
        ArrayList<Integer> integers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i == 0 || i == n - 1) {
                integers.add(1);
            } else {
                integers.add(list.get(i - 1) + list.get(i));
            }
        }
        return integers;
    }
}

作者：tj-xiong
链接：https://leetcode.cn/problems/pascals-triangle/solution/118yang-hui-san-jiao-by-tj-xiong-0pje/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目3

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

示例 1：

java数据结构刷题二期

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/valid-sudoku/solution/you-xiao-de-shu-du-by-leetcode-solution-50m6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二
class Solution {
    public boolean isValidSudoku(char[][] board) {
        //遍历行
        for (int i = 0; i < 9; i++) {
            //存储第i行的数
            Set<Character> row = new HashSet<>();
            //存储第j列的数字
            Set<Character> column = new HashSet<>();
            //3*3九宫格
            Set<Character> square = new HashSet<>();

            //遍历列
            for (int j = 0; j < 9; j++) {
                //1、判断每行的合理性
                char chRow = board[i][j];//第i行
                //不是空白格，即是数字，判断数字合理性
                if(chRow != '.'){
                    if(row.contains(chRow)){
                        //第i行出现相同数字
                        return false;
                    }else{
                        //未出现该数字将其添加至集合中
                        row.add(chRow);
                    }
                }

                //2、判断每列的合理性
                char chColumn = board[j][i];//第i列
                //判断第i列的合理性
                if(chColumn != '.'){
                    if(column.contains(chColumn)){
                        //第i列出现相同数字
                        return false;
                    }else{
                        //未出现该数字将其添加至集合中
                        column.add(chColumn);
                    }
                }

                //3、判断3*3九宫格的合理性
                char chSquare =  board[i/3*3 + j/3][i%3*3 + j%3];
                if(chSquare != '.'){
                    if(square.contains(chSquare)){
                        return false;
                    }else{
                        //未出现该数字将其添加至集合中
                        square.add(chSquare);
                    }
                }
            }
        }
        return true;
    }
}

作者：frosty-7ichtermanwgr
链接：https://leetcode.cn/problems/valid-sudoku/solution/36-you-xiao-de-shu-du-yi-ci-bian-li-by-f-0fxv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目4

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

387. 字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

解法二
class Solution {
    public int firstUniqChar(String s) {
        int[] arr = new int[26];//记录字符个数
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            arr[ch - 'a']++;//统计个数
        }
        //按照字符串遍历
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(arr[ch - 'a'] == 1){
                return i;
            }
        }
        //未找到
        return -1;
    }
}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

解法二
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character,Integer> map = new HashMap<>();//key-字母   value-个数
        //将magazine中元素存入map中
        for (int i = 0; i < magazine.length(); i++) {
            char ch = magazine.charAt(i);
            //map中存在ch则将他的value值加一，没有ch则value值默认为0再加一
            map.put(ch,map.getOrDefault(ch,0) + 1);
        }
        //将ransomNote中的字母从map中移除，若不存在则返回false
        for (int i = 0; i < ransomNote.length(); i++) {
            char ch = ransomNote.charAt(i);
            //map中存在字母ch并且个数大于0
            if(map.containsKey(ch) && map.get(ch) > 0){
                //存在则value值减一
                map.put(ch,map.get(ch) - 1);
            }else{
                //不存在
                return false;
            }
        }
        return true;
    }
}

. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:文章来源地址https://www.toymoban.com/news/detail-421618.html

输入: s = "rat", t = "car"
输出: false

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}
解法二
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

到了这里，关于java数据结构刷题二期的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！