繁依Fanyi0

这个屌丝很懒，什么也没留下！

热门标签

刷题学习—数据结构(字符串、栈和队列、链表、数组与矩阵、哈希表、位运算)_加进位,在两头,

作者：繁依Fanyi0 | 2024-02-25 01:30:01

踩

加进位,在两头,

参考了很多大佬的题解，仅作为自己学习笔记用。

数据结构相关

第一章字符串

1.字符串循环移位包含

给定两个字符串 s1 和 s2，要求判定 s2 是否能够被 s1 做循环移位得到的字符串包含
解决办法：s1 进行循环移位的结果是 s1s1 的子字符串，因此只要判断 s2 是否是 s1s1 的子字符串即可。

public class Exer {
   
    public boolean strStr(String s1, String s2) {
   
        StringBuilder sb = new StringBuilder(s1);
        sb.append(s1);
        return sb.toString().contains(s2);
    }
}
1
2
3
4
5
6
7
8
9

思路：先进行拼串，看s2是不是s1s1的子字符

2.字符串循环移位

将字符串向右循环移动 k 位
解决办法：从k处分开，前后字符串翻转后拼接再翻转

public class Exer {
   
    public static void main(String[] args) {
   
        String s = "abcd123";
        int k = 3 ;
        String overturn = overturn(s, k);
        System.out.println(overturn);

    }
	//拼接截取
    public static String overturn(String s,int k) {
   
        StringBuilder sb = new StringBuilder(s);
        sb.append(s);
        return sb.toString().substring(sb.length()-k-s.length(),sb.length()-k);
    }
    //对前后两部分的字符串都进行翻转，拼串后再翻转
    public static String overturn(String s, int k) {
   
        String s2 = s.substring(s.length() - k, s.length());
        String s1 = s.substring(0, s.length() - k);
        StringBuilder s11 = new StringBuilder(s1).reverse();
        StringBuilder s22 = new StringBuilder(s2).reverse();
        return s11.append(s22).reverse().toString();
    }
}
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

思路：

首先将字符串分开截取成两段，前字符串和后字符串
分别进行翻转
反转后进行拼接即可得到

3.字符串中单词的翻转

将每个单词翻转，然后将整个字符串翻转

public class Exer {
   
    public static void main(String[] args) {
   
        String s = "I am a student";
        String s1 = word_overturn(s);
        System.out.println(s1);
    }

    public static String word_overturn(String s) {
   
        StringBuilder sb = new StringBuilder();
        String[] strs = s.trim().split(" ");
        for (int i = strs.length - 1; i >= 0; i--) {
   
            if(strs[i].equals(""))continue;
            sb.append(strs[i] + " ");
        }
        return sb.toString().trim();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

思路：可以用栈来实现，但这里用个简单的

将字符串去首尾的空格，按照空字符串分为单词
倒着将所有单词拼起来，如果是空字符跳过
最后返回值再去一下首尾

4.两个字符串包含的字符是否完全相同

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

	public boolean isAnagram(String s, String t) {
   
        char[] schars = s.toCharArray();
        char[] tchars = t.toCharArray();

        Arrays.sort(schars);
        Arrays.sort(tchars);

        return Arrays.equals(schars,tchars);
    }
    //将s每个字符按照26个字母的数量存入，再用t减掉，如果有字母数量不是0的话就不是字母异位词
    public boolean isAnagram(String s,String t) {
   
        int[] arr = new int[26];
        for (char c : s.toCharArray()) {
   
            arr[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
   
            arr[c - 'a']--;
        }
        for (int i : arr) {
   
            if (i != 0) {
   
                return false;
            }
        }
        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

思路：

取得字符的char[]数组
字符底层都是数字，排序之后，只要两个数组不一样就说明单词组成不一样
调用数组的equals方法即可判断

5. 计算一组字符集合可以组成的回文字符串的最大长度

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

class Solution {
   
    public int longestPalindrome(String s) {
   
        int[] cnts = new int[256];
        for (char c : s.toCharArray()) {
   
            cnts[c]++;
        }
        int palindrome = 0;
        for (int cnt : cnts) {
   
            palindrome += (cnt / 2) * 2;
        }

        if (palindrome < s.length()) {
   
            palindrome++;
        }
        return palindrome;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路：

发现回文数最大长度与奇偶数有关，所以要统计每个字符出现的次数
使用长度为 256 的整型数组来统计每个字符出现的个数，每个字符有偶数个可以用来构成回文字符串。cnt / 2可以把出现为1次的筛掉
如果回文串的长度小于整个字符串的长度，那必有一个出现一次的字符可以放在回文串的正中间

6.同构字符串

给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

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

思路：

首先，同构同构，长度不一样绝对不同构
记录每个字符上一次出现的位置，两字符串的当前字符上次位置不同的话就是不同构

7.回文子串

给你一个字符串s，请你统计并返回这个字符串中回文子串的数目。

class Solution {
   
    int count = 0;
    public int countSubstrings(String s){
   
        if(s == null || s.length() < 1){
   
            return 0;
        }
        for (int i = 0; i < s.length(); i++) {
   
            extendPalindrome(s,i,i+1);
            extendPalindrome(s,i,i);
        }
        return count;
    }

    public void extendPalindrome(String s, int left, int right){
   
        while(left >= 0 && right <s.length() && s.charAt(left--) == s.charAt(right++)){
   
            count++;
        }
    }
}
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

思路：中心扩散法

把每一个字符看作中心向两边扩散，扩散的子串判断是否为回文串
字符串的构成可能是奇数也可能是偶数，所以要考虑两种情况作为中心
定义左右指针从中心向两边扩散，判断回文子串，是就记录，最后得到结果count

8.判断一个整数是否是回文数

如：121，则返回true
方法一：把数换成字符，遍历首尾字符比较

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

方法二：直接计算倒序数，从后向前计算每一位数，计算完成后和原数对比

		if(x >= 0){
   
            if(x == 0){
   
                return true;
            }
            int cur = 0;
            int num = x;
            while(num != 0){
   
                cur = cur * 10 + num % 10;//当前数乘10再把num的个位数加上
                num /= 10;//此时num再小10倍
            }
            return cur == x;
        }
        return false;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

结果：在这里插入图片描述

9.统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数

暴力手撕成功，但超时

public static int countBinarySubstrings(String s) {
   
        int time = 0;
        for (int i = 0; i < s.length(); i++) {
   
            for (int j = i+1; j < s.length(); j++) {
   
                String substring = s.substring(i, j + 1);
                if(isBSstr(substring)){
   
                    time++;
                }
            }
        }
        return time;
    }

    public static boolean isBSstr(String s){
   
        if(s.length() % 2 != 0){
   
            return false;
        }

        if(s.contains("0") && !s.contains("1") || !s.contains("0") && s.contains("1")){
   
            return false;
        }

        if(s.substring(0,s.length()/2).contains("0") && s.substring(0,s.length()/2).contains("1")
                || s.substring(s.length()/2,s.length()).contains("0") && s.substring(s.length()/2,s.length()).contains("1")){
   
            return false;
        }
        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

思路：

统计所有字串
对所有字串判断，从中间分开。①如果前半部分或后半部分有0且有1就false ②奇数个字串也false ③全为0或者全为1就false
最后统计得到结果
改进：

class Solution {
   
    public int countBinarySubstrings(String s) {
   
        int preLen = 0, curLen = 1, count = 0;
	    for (int i = 1; i < s.length(); i++) {
   
	        if (s.charAt(i) == s.charAt(i - 1)) {
   
	            curLen++;
	        } else {
   
	            preLen = curLen;
	            curLen = 1;
	        }
	
	        if (preLen >= curLen) {
   
	            count++;
	        }
	    }
	    return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路：

该问题对字符串需进行逐位遍历，如果当前两字符相等，则设置一个当前相等的长度数curlen，每相等一次长度就加长一次
如果统计到当前两字符不相等，就把之前的当前长度数curlen赋值给之前的长度数prelen当前的长度数重新置为1
此时出现不一样的字符了(之前是0)，对于此时不一样的字符(1)后面的字符如果一样(1)，比如00011，则还需要统计0011
所以每次移位复制结束后，再判断一下如果当前长度数(curlen) <= 之前长度数(prelen)，则需要累加统计数，即可得到结果

10.（难）亲密字符串

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。

class Solution {
   
    public boolean buddyStrings(String s, String goal) {
   
        if(s.length() != goal.length())return false;
        if (s.equals(goal)) {
   
            int[] sarr = new int[26];
            for (char c : s.toCharArray()) {
   
                if (++sarr[c - 'a'] > 1) {
   
                    return true;
                }
            }
            return false;
        }
        char sc = ' ';
        char gc = ' ';
        int time = 0,index = 0;
        for (int i = 0; i < s.length(); i++) {
   
            if (s.charAt(i) != goal.charAt(i)) {
   
                if (time == 1) {
   
                    index = i;
                    time++;
                    continue;
                } else if (time == 2) {
   
                    return false;
                }
                sc = s.charAt(i);
                gc = goal.charAt(i);
                time++;
            }
        }
        return !(sc != goal.charAt(index) || gc != s.charAt(index));
    }
}
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

思路：

如果两字符串相等，只要有两个重复的字符就可以交换，如果有大于1的，就一定有重复字母
长度不等返回false，定义第二次不相同时位置的索引index，第一次不同时的字符sc，gc，time是字符不同的次数
对字符开始遍历，当前两字符串中的字符相等直接进入下一循环。
如果不相等，记录此时不相等的次数，第二次不相等就记录下当前索引位置，第二次不相等就只能false了因为题目只让交换一次。记录第一次不相等时两字符串中的字符
最后比较第一次与第二次字符是否对应相等，是否完成了交换，返回结果

字符串题型总结

双指针法是字符串处理的常客，KMP算法是字符串查找最重要的算法。
一般字符串题型比较简单，会应用一些字符串常用的API来解决
equals()：比较两个字符串是否相等
equalsIgnoreCase( )：忽略大小写的两个字符串是否相等比较
String.valueOf()：把数字转换成String类型（不用担心object是否为null值这一问题）
subString()：截取字符串中的一段字符串
String str;
（1）str＝str.substring(int beginIndex);
截取掉str从首字母起长度为beginIndex的字符串，将剩余字符串赋值给str；
（2）str＝str.substring(int beginIndex，int endIndex);
截取str中从beginIndex开始至endIndex结束时的字符串，并将其赋值给str;
charAt()：返回指定索引处char值
toLowerCase()：将所有在此字符串中的字符转化为小写 toUpperCase()方法: 将字符全部转化为大写
indexOf()：指出 String 对象内子字符串的开始位置
replace的参数是char和CharSequence，即可以支持字符的替换，也支持字符串的替换
getBytes()：得到一个系统默认的编码格式的字节数组
StringBuffer的append()方法：用于拼串
StringBuffer或者StringBuilder.toString()就可以将其转化为String类型
获取字符串长度方法length()：str.length();
字符串比较：
(1) 不忽略字符串大小写情况下字符串的大小比较方法compareTo(another str)
(2) 忽略字符串大小写情况下字符串的大小比较方法compareTOIgnoreCase(another str)
以上都是输出三种比较结果：若该字符串的Unicode值<参数字符串的Unicode值，结果返回一负整数；若若该字符串的Unicode值=参数字符串的Unicode值，结果返回0；若该字符串的Unicode值>参数字符串的Unicode值，结果返回一正整数。
(3) 不忽略字符串大小写情况下判别字符串相等的方法equals(another str)
当且仅当str1和str2的长度相等，且对应位置字符的Unicode编码完全相等，返回true,否则返回false
(4) 忽略字符串大小写情况下判别字符串相等的方法equalsIgnoreCase(another str)
str.toCharArray();将字符串改成char型数组

主要是以一些API的应用为主，逻辑方面不会太难

第二章栈和队列

1.用栈实现队列

class MyQueue{
   
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    public MyQueue() {
   }

    public void push(int x) {
   
        if(stack2.isEmpty()){
   
            stack1.push(x);
        }else {
   
            while (!stack2.isEmpty()){
   
                stack1.push(stack2.pop());
            }
            stack1.push(x);
        }
    }

    public int pop() {
   
        if(stack1.isEmpty() && stack2.isEmpty()){
   
           return 0;
        }

        while (
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/137547