刷题日记 - 4

class Solution {
    public long numberOfRightTriangles(int[][] grid) {
        int m = grid.length; // 获取网格的行数
        int n = grid[0].length; // 获取网格的列数
        
        int[] rowPoints = new int[m]; // 用于记录每一行中的点数
        int[] colPoints = new int[n]; // 用于记录每一列中的点数

        // 统计每一行和每一列中的点数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // 如果当前格子有一个点
                    rowPoints[i]++; // 增加对应行的点数
                    colPoints[j]++; // 增加对应列的点数
                }
            }
        }

        long res = 0; // 用于存储直角三角形的数量

        // 计算直角三角形的数量
        for (int i = 0; i < m; i++) {
            if (rowPoints[i] < 2) continue; // 如果当前行的点数少于2，则跳过
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // 如果当前格子有一个点
                    // 如果当前位置有一个点，计算以该点为直角的直角三角形数量
                    res += (colPoints[j] - 1) * (rowPoints[i] - 1); 
                    // 列中的点数减去1，表示该列除去当前点的其他点
                    // 行中的点数减去1，表示该行除去当前点的其他点
                }
            }
        }

        return res; // 返回计算得到的直角三角形数量
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
        return kmp(haystack,needle);
    }

    private int[] computeLSPArray(String pattern){
        int len = pattern.length();
        char[] charArray = pattern.toCharArray();
        int[] lsp = new int[len];
        lsp[0] = 0;

        int i = 1;
        int j = 0;

        while(i<len){
            if(charArray[i]==charArray[j]){
                j++;
                lsp[i] = j;
                i++;
            }else{
                if(j!=0){
                    j = lsp[j-1];
                }else{
                    i++;
                }
            }
        }
        return lsp;
    }

    private int kmp(String text,String pattern){

        int N =  text.length();
        int M = pattern.length();

        char[] textChars = text.toCharArray();
        char[] patternChars = pattern.toCharArray();

        int[] lsp = computeLSPArray(pattern);

        int i = 0;
        int j = 0;

        while(i<N){
            if(textChars[i]==patternChars[j]){
                i++;
                j++;
            }

            if(j==M){
                int idx = i-j;
                return idx;
//                j = lsp[j-1];
            }else if(i<N && textChars[i]!=patternChars[j]){
                if(j==0){
                    i++;
                }else{
                    j = lsp[j-1];
                }
            }
        }
        return -1;
    }
}

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();  // 存放结果字符串的列表
        LinkedList<String> tmp = new LinkedList<>();  // 存放当前行的单词
        int tmpLen = 0;  // 当前行单词长度之和
        int SPACE = 1;  // 空格长度
        int len = words.length;  // 单词数组长度
        int p = 0;  // 当前单词指针
        
        while(p < len) {
            String word = words[p];
            if(tmpLen == 0) {  // 如果当前行没有单词
                tmpLen += word.length();  // 更新当前行长度
                tmp.offer(word);  // 加入当前单词
            } else if(tmpLen + word.length() + SPACE <= maxWidth) {  // 如果加入当前单词后长度不超过最大宽度
                tmpLen = tmpLen + word.length() + SPACE;  // 更新当前行长度
                tmp.offer(word);  // 加入当前单词
            } else {  // 如果加入当前单词后长度会超过最大宽度，表明现在需要将tmp中的所有单词作为一行了
                String tmpString = fun(tmp, tmpLen, maxWidth);  // 对齐当前行单词
                res.add(tmpString);  // 将对齐后的字符串加入结果列表
                tmpLen = 0;  // 重置当前行长度
                continue;  // 继续处理当前单词
            }
            p++;  // 移动到下一个单词
        }

        // 特殊处理最后一行 （最后一行左对齐）
        StringBuilder sb = new StringBuilder();
        sb.append(tmp.poll());
        while(!tmp.isEmpty()){
            sb.append(' ');
            sb.append(tmp.poll());
        }
        if(sb.length()<maxWidth){
            for(int i=sb.length();i<maxWidth;i++){
                sb.append(' ');
            }
        }
        res.add(sb.toString());
        
        return res;
    }
	
    // 将当前行的单词组合输出成两点对齐的字符串
    private String fun(LinkedList<String> tmp, int tmpLen, int maxWidth) {
        
        int wordCount = tmp.size();  // 当前行单词数
        int spaceCount = maxWidth - tmpLen + wordCount - 1;  // 需要填充的空格数
        StringBuilder sb = new StringBuilder();
        int p = 0;
        int[] spaces = new int[wordCount - 1];  // 每个间隔应填充的空格数
        
        if(wordCount > 1) {
            int base = spaceCount / (wordCount - 1);  // 平均每个间隔的空格数
            for(int i = 0; i < wordCount - 1; i++) {
                spaces[i] = base;
            }
            int remain = spaceCount % (wordCount - 1);  // 处理空格分配不均匀的情况
            int idx = 0;
            while(remain > 0) {
                spaces[idx]++;
                remain--;
                idx++;
            }
        }
        
        while(p < wordCount) {
            String word = tmp.poll();
            if(p == wordCount - 1) {
                sb.append(word);   // 最后一个单词之后没有间隔
            } else {
                sb.append(word); // 添加当前单词
                for(int i = 0; i < spaces[p]; i++) { // 添加当前单词后的间隔
                    sb.append(' ');
                }
            }
            p++;
        }

        if(sb.length() < maxWidth) {
            for(int i = sb.length(); i < maxWidth; i++) {
                sb.append(' ');
            }
        }
        return sb.toString();
    }
}

class Solution {
    public boolean isPalindrome(String s) {
        char[] charArray = s.toCharArray();  // 将字符串转换为字符数组

        // 提取出所有的字母数字字符
        StringBuilder sb = new StringBuilder();
        for (char ch : charArray) {
            if ('A' <= ch && ch <= 'Z') {
                sb.append((char) (ch - 'A' + 'a'));  // 将大写字母转换为小写字母
            } else if (('a' <= ch && ch <= 'z') || ('0' <= ch && ch <= '9')) {
                sb.append(ch);  // 保留小写字母和数字
            }
        }

        char[] newCharArray = sb.toString().toCharArray();  // 将过滤后的字符串转换为字符数组
        // 判断是否为回文
        int head = 0;  // 头指针
        int tail = sb.length() - 1;  // 尾指针
        boolean flag = true;  // 标志位，用于判断是否为回文

        while (head < tail) {  // 当头指针小于尾指针时
            char headChar = newCharArray[head];  // 取头指针指向的字符
            char tailChar = newCharArray[tail];  // 取尾指针指向的字符
            if (headChar != tailChar) {  // 如果两个字符不相等
                flag = false;  // 标志位设为false，表示不是回文
                break;  // 退出循环
            }
            head++;  // 头指针向右移动
            tail--;  // 尾指针向左移动
        }

        return flag;  // 返回标志位
    }
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        boolean res = false;  // 结果标志，初始化为false
        
        int sLen = s.length();  // 字符串s的长度
        int tLen = t.length();  // 字符串t的长度
        
        if (sLen < 1) {  // 如果字符串s为空
            return true;  // 空字符串总是其他字符串的子序列
        }

        char[] sChars = s.toCharArray();  // 将字符串s转换为字符数组
        char[] tChars = t.toCharArray();  // 将字符串t转换为字符数组

        int q = 0;  // 指向字符串s的指针
        int p = 0;  // 指向字符串t的指针

        char sCur = sChars[q];  // 当前s中的字符
        char tCur;
        while (p < tLen) {  // 遍历字符串t
            tCur = tChars[p];  // 当前t中的字符
            if (tCur == sCur) {  // 如果t中的字符和s中的字符相同
                q++;  // 移动s的指针
                if (q == sLen) {  // 如果s的指针到达s的末尾
                    res = true;  // 表示s是t的子序列
                    break;  // 退出循环
                }
                sCur = sChars[q];  // 更新当前s中的字符
            }
            p++;  // 移动t的指针
        }

        return res;  // 返回结果
    }
}

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        // 预处理字符串s
        char[] sChars = s.toCharArray();
        int len = s.length();
        int[][] dp = new int[len+1][26];  // 动态规划数组，用于记录每个字符下一个出现的位置
        								  // dp[i][ch-'a'] = j 表明，在字符串s中 索引为i到len-1的子字符串中，字符ch出现的下一个位置
        
        // 初始化dp数组
        for (char ch = 'a'; ch <= 'z'; ch++) {
            int nextPos = -1;
            for (int i = len - 1; i >= 0; i--) {
                if (sChars[i] == ch) {
                    nextPos = i;  // 更新当前字符的位置
                }
                dp[i][ch - 'a'] = nextPos;  // 记录字符ch在位置i的下一个出现位置
            }
        }

        // 填充字符串末尾的情况
        Arrays.fill(dp[len], -1);

        int res = 0;  // 记录匹配的子序列数量
        boolean flag;  // 标志位，记录是否找到匹配的子序列
        
        // 遍历每个单词，检查是否是s的子序列
        for (String word : words) {
            flag = true;
            int idx = -1;  // 初始化索引为-1，用于dp数组的查找
            for (char ch : word.toCharArray()) {
                idx = dp[idx + 1][ch - 'a'];  // 查找字符ch在s中的下一个出现位置
                if (idx == -1) {  // 如果找不到字符ch
                    flag = false;  // 标记为false
                    break;  // 结束当前单词的检查
                }
            }
            if (flag) res++;  // 如果找到匹配的子序列，结果加1
        }

        return res;  // 返回匹配的子序列数量
    }
}