2025-2月算法刷题

发表于 | 分类于

image-20250307210510015

加油站

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
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int totalCost = 0;
        int currentGas = 0;
        int start = 0;

        // Calculate total gas and total cost
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
        }

        // If total gas is less than total cost, it's impossible to complete the circuit
        if (totalGas < totalCost) {
            return -1;
        }

        // Find the starting station
        for (int i = 0; i < gas.length; i++) {
            currentGas += gas[i] - cost[i];
            if (currentGas < 0) {
                start = i + 1;  // Reset starting point
                currentGas = 0; // Reset current gas
            }
        }

        return start;
    }
}

由于总油量足够（已经在全局检查中确认），我们只需要找到一个起点，使得从该点出发后，油量不会在任何站点变为负数。这个起点一定存在，因为我们不需要重新检查之前的站点。

分发糖果

错误尝试

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
class Solution {
    public int candy(int[] ratings) {
        int a = Integer.MAX_VALUE;
        int b = -1;
        int x = 1;
        int y = 1;
        int all = 1;
        for(int i = 0;i<ratings.length;i++){
            if(ratings[i]<a){
                a = ratings[i];
                b = i;
                
            }
        }

        for(int j=b-1;j>=0;j--){
            if(ratings[j]>ratings[j+1]){
                x=x+1;
                all=x+all;
            }
            else{
                if(x==1){
                    all = x+all;
                }
                else{
                    x--;
                all = x+all;
                }
            }
        }
        for(int k=b+1;k<ratings.length;k++){
            if(ratings[k]>ratings[k-1]){ 
                y=y+1;
                all=y+all;
            }
            else{
                if(y==1){
                    all = y +all;
                }
                else{
                y--;
                all = y + all;
                }
            }
        }
        return all;
    }
}

我的代码在处理评分相等或多个峰值和谷值时容易出错。

两次遍历法：

  • 第一次从左到右遍历，确保每个孩子如果评分比左边高，则糖果数比左边多。
  • 第二次从右到左遍历，确保每个孩子如果评分比右边高，则糖果数比右边多。
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
class Solution {
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
        
        int n = ratings.length;
        int[] candies = new int[n];
        
        // 初始化每个孩子至少分到 1 颗糖果
        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }
        
        // 从左到右遍历
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        
        // 从右到左遍历
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        
        // 计算总糖果数
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }
        
        return totalCandies;
    }
}

接雨水

从左右向中间逼近

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 trap(int[] height) {
        int water = 0;
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        while(left<right){
            if(leftMax<rightMax){
                left++;
                leftMax = Math.max(leftMax,height[left]);
                water +=Math.max(0,leftMax-height[left]);
            }
            else{
                right--;
                rightMax = Math.max(rightMax,height[right]);
                water += Math.max(0,rightMax-height[right]);
            }
        }
        return water;
    }
}

罗马数字转整数

最后一个单词的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLastWord(String s) {
        int flag = 0;
        int count = 0;
        for(int i = s.length()-1;i>=0;i--){
            if(Character.isWhitespace(s.charAt(i))&&flag == 1){
                break;
            }
            if(Character.isWhitespace(s.charAt(i))){
                continue;
            }
            flag = 1;
            count++;
        }
        return count;
    }
}

最长公共前缀

这是两个本题用到的语法。indexOf()用于判断前缀是否匹配，substring()通过减少啊一位来寻找匹配的前缀。

https://www.runoob.com/java/java-string-indexof.html

image-20250205211107264

https://www.runoob.com/java/java-string-substring.html

image-20250205211935836

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null||strs.length == 0){
            return "";
        }
        String prefix = strs[0];
        for(int i = 0;i<strs.length;i++){
            while(strs[i].indexOf(prefix)!=0){
                prefix = prefix.substring(0,prefix.length()-1);
            }
            if(prefix.length() == 0){
                return "";
            }
        }
        return prefix;
    }
}

反转字符串中的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public String reverseWords(String s) {
       s = s.trim().replaceAll("\\s+"," ");
       String[] word=s.split(" ");
       int left=0;
       int right=word.length-1;
       while(left<right){
        String tmp = word[left];
        word[left] = word[right];
        word[right] = tmp;
        left++;
        right--;
       }
       return String.join(" ",word);
    }
}

Z 字形变换

1
2
3
p a h
aplaii
y i r

找出字符串中第一个匹配项的下标

错误尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int strStr(String haystack, String needle) {
        for(int i = 0;i<haystack.length();i++){
            int c = 0;
            for(int j=0;j<needle.length();j++){
                if(haystack.charAt(i+c)!=needle.charAt(j)){
                    break;
                }
                c++;
                if(c==needle.length()){
                    return i;
                }
            }
        }
        return -1;
    }
}

image-20250209114207730

没有考虑到needle长度大于haystack的情况。然后遍历到haystack-needle就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack.length()<needle.length()){
            return -1;
        }
        for(int i = 0;i<haystack.length()-needle.length()+1;i++){
            int c = 0;
            for(int j=0;j<needle.length();j++){
                if(haystack.charAt(i+c)!=needle.charAt(j)){
                    break;
                }
                c++;
                if(c==needle.length()){
                    return i;
                }
            }
        }
        return -1;
    }
}

验证回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isPalindrome(String s) {
        String s1 = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        int left = 0;
        int right = s1.length()-1;
        while(left<right){
            if(s1.charAt(left)!=s1.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

[^a-zA-Z0-9] 用于匹配所有非字母数字字符。通过 replaceAll 方法，将这些字符从字符串中移除。

判断子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length() == 0){
            return true;
        }
        int j = 0;
        for(int i=0;i<t.length();i++){
            if(s.charAt(j) == t.charAt(i)){
                j++;
            }
            if(j == s.length()){
                return true;
            }
        }
        return false;
    }
}

两数之和 II - 输入有序数组

慢速度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int flag = 1;
        for(int i = 0;i<numbers.length;i++){
            for(int j = flag;j<numbers.length;j++){
                if(numbers[i]+numbers[j] == target){
                    return new int[]{i+1,j+1};
                }
            }
            flag++;
        }
        return null;
    }
}

有一个点没注意到就是numbers是从小到大排序的这样就可以这样提高速度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1}; 
            } else if (sum < target) {
                left++; 
            } else {
                right--; 
            }
        }
    
        return null;
    }
}

盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int low = (height[left]<height[right]?height[left]:height[right]);
        int max = low*(right - left);
        while(left<right){
            low = (height[left]<height[right]?height[left]:height[right]);
            if(low*(right - left)>max){
                max = low*(right - left);
            }
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return max;
    }
}

从更低的一边去寻找更高的。

三数之和

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> listOfLists = new ArrayList<>();
        Arrays.sort(nums); // 排序
        for(int i = 0;i<nums.length;i++){
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]==0){
                    listOfLists.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right&&nums[right] == nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }
                else if(nums[i]+nums[left]+nums[right]<0){
                    left++;
                }
                else{
                    right--;
                }
            }
        }
        return listOfLists;
    }
}

长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
            while(sum>=target){
                minLength = Math.min(minLength,i-left+1);
                sum -= nums[left];
                left++;
            }
        }
        return minLength==Integer.MAX_VALUE?0:minLength;
    }
}

无重复字符的最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0;
        int b = 0;
        for(int i = 0;i<s.length();i++){
            for(int j=b;j<i-b;j++){
                if(s.charAt(j)==s.charAt(i)){
                    l = Math.max(l,i-b);
                    b = i;
                }
            }
        }
        return l;
    }
}

修改后b的新值为j+1既为重复字符下一个，不知道第二层循环条件j<i-b怎么想的，直接小于i才能全部遍历。发现重复就停止重复检测，提高效率。最后确保最后一个窗口被计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0;
        int b = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = b; j < i; j++) {
                if (s.charAt(j) == s.charAt(i)) {
                    l = Math.max(l, i - b);
                    b = j + 1;
                    break;
                }
            }
        }
        // 检查最后一个子串的长度
        l = Math.max(l, s.length() - b);
        return l;
    }
}

串联所有单词的子串

https://www.runoob.com/java/java-hashmap-getordefault.html

image-20250215211823415

https://www.runoob.com/java/java-arraylist.html

https://www.runoob.com/java/java-hashmap-containskey.html

image-20250215215346090

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
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(s == null||words == null||words.length == 0){
            return result;
        }
        int wordLen = words[0].length();
        int totalLen = words.length*wordLen;
        int sLen = s.length();
        if(sLen<totalLen){
            return result;
        }
        Map<String,Integer> wordCount = new HashMap<>();
        for(String word : words){
            wordCount.put(word,wordCount.getOrDefault(word,0)+1);
        }
        for(int i = 0;i<wordLen;i++){
            int left = i;
            int right = i;
            Map<String,Integer> seen = new HashMap<>();
            while(right + wordLen<=sLen){
                String word = s.substring(right,right+wordLen);
                right += wordLen;
                if(wordCount.containsKey(word)){
                    seen.put(word,seen.getOrDefault(word,0)+1);
                    while(seen.get(word)>wordCount.get(word)){
                        String leftWord = s.substring(left,left +wordLen);
                        seen.put(leftWord,seen.get(leftWord)-1);
                        left += wordLen;
                    }
                    if(right - left == totalLen){
                        result.add(left);
                    }
                }else{
                    seen.clear();
                    left = right;
                }
            }
        }
        return result;
    }
}

最小覆盖子串

遍历s，去匹配t，当开始匹配成功后，接下来无需匹配t中已经匹配到的。当重复时，将left改为原来left匹配到的下一个匹配到的。当全部覆盖时，建立一个hashmap存储，left以及长度。最后选择出最短的如果没有就返回””。

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
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }

        // 统计 t 中每个字符的出现次数
        Map<Character, Integer> targetCounts = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetCounts.put(c, targetCounts.getOrDefault(c, 0) + 1);
        }

        int required = targetCounts.size(); // 需要匹配的字符种类数
        int formed = 0; // 当前窗口中已经匹配的字符种类数

        int left = 0, right = 0; // 滑动窗口的左右指针
        int minLength = Integer.MAX_VALUE; // 最小窗口的长度
        int minLeft = 0; // 最小窗口的起始位置

        while (right < s.length()) {
            char currentChar = s.charAt(right);

            // 如果当前字符在 t 中
            if (targetCounts.containsKey(currentChar)) {
                targetCounts.put(currentChar, targetCounts.get(currentChar) - 1);

                // 如果当前字符的计数变为 0，表示该字符已经完全匹配
                if (targetCounts.get(currentChar) == 0) {
                    formed++;
                }
            }

            // 当窗口中的字符已经包含了 t 中的所有字符时，尝试收缩窗口
            while (left <= right && formed == required) {
                int currentWindowLength = right - left + 1;

                // 更新最小窗口
                if (currentWindowLength < minLength) {
                    minLength = currentWindowLength;
                    minLeft = left;
                }

                char leftChar = s.charAt(left);

                // 如果左指针指向的字符在 t 中
                if (targetCounts.containsKey(leftChar)) {
                    targetCounts.put(leftChar, targetCounts.get(leftChar) + 1);

                    // 如果左指针移动后，窗口中的字符不再满足 t 的要求
                    if (targetCounts.get(leftChar) > 0) {
                        formed--;
                    }
                }

                left++; // 收缩窗口
            }

            right++; // 扩展窗口
        }

        return minLength == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLength);
    }
}

有效的数独

非常奇妙的数学。当以宫来确定矩阵中的元素时，如何定位到元素所对应的宫呢？
(i/3)*3+j/3

成功读到数字时就在该元素所在行，列，宫进行查询，如果已经有重复就返回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
class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] boxs = new boolean[9][9];
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                char c = board[i][j];
                if(c == '.'){
                    continue;
                }
                int num = c-'1';
                if(rows[i][num]){
                    return false;
                }
                rows[i][num] = true;
                if(cols[j][num]){
                    return false;
                }
                cols[j][num] = true;
                int boxIndex = (i/3)*3+j/3;
                if(boxs[boxIndex][num]){
                    return false;
                }
                boxs[boxIndex][num]=true;
            }
        }
        return true;
    }
}

螺旋矩阵

向右向下向左向上为一轮。每进行一轮进行一次计数。

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
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }

        int rows = matrix.length;
        int columns = matrix[0].length;
        int total = rows * columns;
        int count = 0;
        int round = 0;

        while (count < total) {
            // 从左到右遍历顶部行（确保存在）
            for (int i = round; i < columns - round && count < total; i++) {
                result.add(matrix[round][i]);
                count++;
            }

            // 从上到下遍历右侧列（确保存在）
            for (int j = round + 1; j < rows - round && count < total; j++) {
                result.add(matrix[j][columns - round - 1]);
                count++;
            }

            // 从右到左遍历底部行（需检查是否有剩余行）
            if (round < rows - round - 1) {
                for (int k = columns - round - 2; k >= round && count < total; k--) {
                    result.add(matrix[rows - round - 1][k]);
                    count++;
                }
            }

            // 从下到上遍历左侧列（需检查是否有剩余列）
            if (round < columns - round - 1) {
                for (int l = rows - round - 2; l > round && count < total; l--) {
                    result.add(matrix[l][round]);
                    count++;
                }
            }

            round++;
        }

        return result;
    }
}
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
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }

        int rows = matrix.length;
        int columns = matrix[0].length;
        int top = 0, bottom = rows - 1;
        int left = 0, right = columns - 1;

        while (top <= bottom && left <= right) {
            // 从左到右遍历顶部行
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // 从上到下遍历右侧列
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // 从右到左遍历底部行
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            // 从下到上遍历左侧列
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}

这样解决了重叠和溢出问题。

旋转图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // Step 1: Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        
        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = tmp;
            }
        }
    }
}

矩阵置零

生命游戏

创建一个二维数组directions来与遍历得到的位置进行运算后得到周围8个元素的位置。遍历8个位置判断位置是否在存在的范围并且是否有存活细胞来进行计数。

后面进行判断如果符合死亡条件就置为-1，如果复活就置为2。后面根据不同于0与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
class Solution {
    public void gameOfLife(int[][] board) {
        if(board == null || board.length ==0){
            return;
        }
        int rows = board.length;
        int cols = board[0].length;
        int[][] directions = {{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                int liveNeighbors = 0;
                for(int[] direction : directions){
                    int ni = i+direction[0];
                    int nj = j+direction[1];
                    if(ni>=0&&ni<rows&&nj>=0&&nj<cols&&(board[ni][nj]==1||board[ni][nj]==-1)){
                        liveNeighbors++;
                    }
                }
                if(board[i][j]==1&&(liveNeighbors<2||liveNeighbors>3)){
                    board[i][j] = -1;
                }
                else if(board[i][j] == 0&&liveNeighbors==3){
                    board[i][j]=2;
                }
            }
        }
        for(int i = 0;i<rows;i++){
            for(int j = 0;j<cols;j++){
                if(board[i][j]==-1){
                    board[i][j]=0;
                }
                else if(board[i][j]==2){
                    board[i][j]=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
import java.util.HashMap;

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> Sites = new HashMap<>();
        
        // Count the frequency of each character in ransomNote
        for (char c : ransomNote.toCharArray()) {
            Sites.put(c, Sites.getOrDefault(c, 0) + 1);
        }
        
        // Decrement the count for each character in magazine
        for (char c : magazine.toCharArray()) {
            if (Sites.containsKey(c)) {
                Sites.put(c, Sites.get(c) - 1);
                if (Sites.get(c) == 0) {
                    Sites.remove(c);
                }
            }
        }
        
        // If the map is empty, it means all characters in ransomNote can be constructed from magazine
        return Sites.isEmpty();
    }
}

同构字符串

s中相同的字符的位置在t中也是一样的。

建立一个hashmap，s为key，t为value，先判断有没有s,如果没有就添加映射，如果有就判断是否对应。

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
class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> Site1 = new HashMap<>();
        for(int i=0;i<s.length();i++){
            if(Site1.containsKey(s.charAt(i))){
                if(Site1.get(s.charAt(i))==t.charAt(i)){
                    continue;
                }else{
                    return false;
                }
            }else{
                Site1.put(s.charAt(i),t.charAt(i));
            }
        }
        HashMap<Character, Character> Site2 = new HashMap<>();
        for(int i=0;i<s.length();i++){
            if(Site2.containsKey(t.charAt(i))){
                if(Site2.get(t.charAt(i))==s.charAt(i)){
                    continue;
                }else{
                    return false;
                }
            }else{
                Site2.put(t.charAt(i),s.charAt(i));
            }
        }
        return true;
    }
}

单词规律

和上题差不多吧，把s中的单词单独列出来。新建一个数组然后直接使用split就可以

https://www.runoob.com/java/java-string-split.html

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 wordPattern(String pattern, String s) {
        // 将字符串 s 按空格分割成单词数组
        String[] words = s.split(" ");
        
        // 如果 pattern 的长度和单词数组的长度不一致，直接返回 false
        if (pattern.length() != words.length) {
            return false;
        }
        
        // 使用两个哈希表分别记录字符到单词和单词到字符的映射
        Map<Character, String> charToWord = new HashMap<>();
        Map<String, Character> wordToChar = new HashMap<>();
        
        // 遍历 pattern 和 words
        for (int i = 0; i < pattern.length(); i++) {
            char currentChar = pattern.charAt(i);
            String currentWord = words[i];
            
            // 检查字符到单词的映射是否一致
            if (charToWord.containsKey(currentChar)) {
                if (!charToWord.get(currentChar).equals(currentWord)) {
                    return false; // 映射不一致，返回 false
                }
            } else {
                // 检查单词到字符的映射是否一致
                if (wordToChar.containsKey(currentWord)) {
                    if (wordToChar.get(currentWord) != currentChar) {
                        return false; // 映射不一致，返回 false
                    }
                } else {
                    // 建立双向映射
                    charToWord.put(currentChar, currentWord);
                    wordToChar.put(currentWord, currentChar);
                }
            }
        }
        
        // 遍历结束后没有冲突，返回 true
        return true;
    }
}

有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        char[] sArray = s.toCharArray();
        Arrays.sort(sArray);
        char[] tArray = t.toCharArray();
        Arrays.sort(tArray);
        for(int i=0;i<s.length();i++){
            if(sArray[i]!=tArray[i]){
                return false;
            }
        }
        return true;
    }
}

字母异位词分组

新建一个hashmap，遍历strs，单独的单词进行排序然后进行对比，将同一类都存到同一个key，然后遍历hashmap将同一个key输出为一个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
         for(String s : strs){
            char[] cArray = s.toCharArray();
            Arrays.sort(cArray);
            String sortedStr = new String(cArray);
            if(!map.containsKey(sortedStr)){
                map.put(sortedStr,new ArrayList<>());
            }
            map.get(sortedStr).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

快乐数

https://zhuanlan.zhihu.com/p/105269431

Floyd判圈算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private int getNext(int n){
        int sum = 0;
        while(n>0){
            int digit = n%10;
            sum +=digit*digit;
            n=n/10;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        while(n!=1&&slow!=fast){
            slow=getNext(slow);
            fast=getNext(getNext(fast));
        }
        return fast==1;
    }
}

存在重复元素 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> sites=new HashMap<>();
        int count=0;
        for(int num:nums){
            if(sites.containsKey(num)){
                if(count-sites.get(num)<=k){
                    return true;
                }
                else{
                    sites.put(num,count);
                }
            }else{
                sites.put(num,count);
            }
            count++;
        }
        return false;
    }
}

简化一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.HashMap;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 0;
        
        for (int num : nums) {
            if (map.containsKey(num)) {
                if (index - map.get(num) <= k) {
                    return true;
                }
            }
            map.put(num, index);
            index++;
        }
        
        return 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
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int count=1;
        int maxLength=0;
        Arrays.sort(nums);
        for(int i=1;i<nums.length;i++){
            if(nums[i]==nums[i-1]){
                continue;
            }
            else if(nums[i]-nums[i-1]==1){
                count++;
                maxLength=Math.max(maxLength,count);
            }
            else{
                count=1;
            }
        }
        if(maxLength==0){
            return 1;
        }
        return maxLength;
    }
}

汇总区间

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<String> summaryRanges(int[] nums) {
        if(nums.length==0){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        int index = 0;
        int count=1;
        List<String> result = new ArrayList<>();
        for(int i=1;i<nums.length;i++){
            if(nums[i]-nums[i-1]==1){
                count++;
                continue;
            }
            else{
                if(count>1){
                    String tmp = nums[index]+"->"+nums[i-1];
                    result.add(tmp);
                    index=i;
                    count=1;
                }
                else{
                    String tmp = Integer.toString(nums[index]);
                    result.add(tmp);
                    index=i;
                }
            }
        }
        if (index == nums.length - 1) {
            result.add(Integer.toString(nums[index]));
        } else {
            result.add(nums[index] + "->" + nums[nums.length - 1]);
        }
        return result;
    }
}

合并区间

学到了一个新知识，根据二位数组的子数组的第一个元素进行排序。

1
Arrays.sort(intervals,Comparator.comparingInt(a -> a[0]));
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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }

        // 根据区间的起始时间排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        List<int[]> result = new ArrayList<>();
        int[] currentInterval = intervals[0];
        result.add(currentInterval);

        for (int i = 1; i < intervals.length; i++) {
            int[] nextInterval = intervals[i];

            // 如果当前区间与下一个区间重叠，合并它们
            if (currentInterval[1] >= nextInterval[0]) {
                currentInterval[1] = Math.max(currentInterval[1], nextInterval[1]);
            } else {
                // 没有重叠，将下一个区间添加到结果中
                currentInterval = nextInterval;
                result.add(currentInterval);
            }
        }

        // 将列表转换为二维数组
        return result.toArray(new int[result.size()][]);
    }
}

插入区间

先将intervals中子数组最大范围小于newInterval的最小范围先添加进去。然后再将intervals与newIntervals重合的部分合并，最后再把intervals最小范围比newInterval最大范围还大的添加进去。

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[][] insert(int[][] intervals, int[] newInterval) {
        List<int []> result = new ArrayList<>();
        int i=0;
        while(i<intervals.length&&intervals[i][1]<newInterval[0]){
            result.add(intervals[i]);
            i++;
        }
        //
        while(i<intervals.length&&intervals[i][0]<=newInterval[1]){
            newInterval[0]=Math.min(intervals[i][0],newInterval[0]);
            newInterval[1]=Math.max(intervals[i][1],newInterval[1]);
            i++;
        }
        result.add(newInterval);
        while(i<intervals.length&&intervals[i][0]>newInterval[1]){
            result.add(intervals[i]);
            i++;
        }
        return result.toArray(new int[result.size()][]);
    }
}

用最少数量的箭引爆气球

求交集的，需要解决的问题是如何确定某个point所对应的子区间，而这个子区间会随着遍历而缩小。

1，point是否在确定的区间。但是区间更改会不会把之前在区间的踢出去呢？

2，hashmap存放每个point对应的区间号，list存放区间。最后统计list中的数量即可