标签: 字符串

一个开发中用到的报文压缩实现

之前开发中用到的一个报文压缩的实现方案,简单在这里单独提出来写一下,分为Java和JS两版代码。

Java版代码是服务端使用,用来在各服务端之间发送接收报文使用。JS版是在前端页面上用来查看或者调试接口报文使用的。

Java代码,压缩和解压缩方法


/**
 * 
 * 功能描述:字符串压缩 <br>
 * 将字符串压缩
 *
 * @param str 待压缩的字符串
 * @return 压缩后的字符串
 */
@SuppressWarnings("restriction")
public static String gzip(String str) {
    // 创建字符流
    ByteArrayOutputStream out = new ByteArrayOutputStream();
    GZIPOutputStream gzip = null;
    try {
        // 对字符串进行压缩并写入压缩流
        gzip = new GZIPOutputStream(out);
        gzip.write(str.getBytes());
    } catch (IOException e) {
        String errMsg = e.getMessage();
        logger.error(errMsg);
    } finally {
        if (gzip != null) {
            try {
                gzip.close();
            } catch (IOException e) {
                String errMsg = e.getMessage();
                logger.error(errMsg);
            }
        }
    }
    // 返回压缩后的字符串
    return new sun.misc.BASE64Encoder().encode(out.toByteArray());
}

/**
 * 
 * 功能描述: 字符串解压<br>
 * 将字符串解压
 *
 * @param str 待解压的字符串
 * @return 解压后的字符串
 * @throws Exception
 */
@SuppressWarnings("restriction")
public static String gunzip(String str) {
    // 校验压缩数据
    if (str == null) {
        return null;
    }

    // 创建读取流
    ByteArrayOutputStream out = new ByteArrayOutputStream();
    ByteArrayInputStream in = null;
    // 解压缩流
    GZIPInputStream ginzip = null;
    byte[] compressed = null;
    // 原始字符串
    String decompressed = null;

    try {
        // 进行解压缩操作
        compressed = new sun.misc.BASE64Decoder().decodeBuffer(str);
        in = new ByteArrayInputStream(compressed);
        ginzip = new GZIPInputStream(in);

        byte[] buffer = new byte[BYTE_SIZE];
        int offset = -1;
        while ((offset = ginzip.read(buffer)) != -1) {
            out.write(buffer, 0, offset);
        }
        decompressed = out.toString();
    } catch (IOException e) {
        String errMsg = e.getMessage();
        logger.error(errMsg);
        logger.error("解析压缩字符串异常", e);
    } finally {
        if (ginzip != null) {
            try {
                ginzip.close();
            } catch (IOException e) {
                String errMsg = e.getMessage();
                logger.error(errMsg);
            }
        }
        if (in != null) {
            try {
                in.close();
            } catch (IOException e) {
                String errMsg = e.getMessage();
                logger.error(errMsg);
            }
        }
        try {
            out.close();
        } catch (IOException e) {
            String errMsg = e.getMessage();
            logger.error(errMsg);
        }
    }
    // 返回原始字符串
    return decompressed;
}

JavaScript代码,js的压缩解压缩需要调用到pako包的内容,可以在https://www.bootcdn.cn/pako/ 上找到需要的版本引用,或者简单点直接把需要min版本代码复制到你需要的页面里, https://cdn.bootcdn.net/ajax/libs/pako/2.0.4/pako.min.js,另外也用到浏览器自带的base64加密解密的方法btoa和atob

Continue reading

LeetCode刷题【1447】最简分数

给你一个整数 n ,请你返回所有 0 到 1 之间(不包括 0 和 1)满足分母小于等于  n 的 最简 分数 。分数可以以 任意 顺序返回。

 

示例 1:

输入:n = 2
输出:["1/2"]
解释:"1/2" 是唯一一个分母小于等于 2 的最简分数。

示例 2:

输入:n = 3
输出:["1/2","1/3","2/3"]

示例 3:

输入:n = 4
输出:["1/2","1/3","1/4","2/3","3/4"]
解释:"2/4" 不是最简分数,因为它可以化简为 "1/2" 。

示例 4:

输入:n = 1
输出:[]

 

提示:

  • 1 <= n <= 100
Related Topics
  • 数学
  • 字符串
  • 数论

  • 👍 84
  • 👎 0
  • GCD辗转相除法【欧几里德算法(Euclidean algorithm)】
    相关知识链接碾转相除法

    这是一个求最大公约数的方法

    1. 实现一个gcd(int a, int b)辗转相除方法,判断两个数的最大公约数是否为1
    2. 如果为1则表明这两个数互质
    3. 剩下的就是枚举从in和从i+1n的分子分母关系了
    class Solution {
        public List<String> simplifiedFractions(int n) {
            List<String> list = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                for (int j = i+1; j <=n ; j++) {
                    if (gcd(i,j)==1){
                        list.add(i+"/"+j);
                    }
                }
            }
            return list;
        }
    
        int gcd(int a, int b){
            if (b==0){
                return a;
            }
            return gcd(b,a%b);
        }
    }

    LeetCode刷题【748】最短补全词

    给你一个字符串 licensePlate 和一个字符串数组 words ,请你找出 words 中的 最短补全词

    补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 不区分大小写。如果某个字母在 licensePlate 中出现不止一次,那么该字母在补全词中的出现次数应当一致或者更多。

    例如:licensePlate = "aBc 12c",那么它的补全词应当包含字母 'a''b' (忽略大写)和两个 'c' 。可能的 补全词"abccdef""caaacab" 以及 "cbca"

    请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words第一个 出现的那个。

     

    示例 1:

    输入:licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
    输出:"steps"
    解释:最短补全词应该包括 "s"、"p"、"s"(忽略大小写) 以及 "t"。
    "step" 包含 "t"、"p",但只包含一个 "s",所以它不符合条件。
    "steps" 包含 "t"、"p" 和两个 "s"。
    "stripe" 缺一个 "s"。
    "stepple" 缺一个 "s"。
    因此,"steps" 是唯一一个包含所有字母的单词,也是本例的答案。

    示例 2:

    输入:licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
    输出:"pest"
    解释:licensePlate 只包含字母 "s" 。所有的单词都包含字母 "s" ,其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest" ,因为它是三个单词中在 words 里最靠前的那个。
    

     

    提示:

    • 1 <= licensePlate.length <= 7
    • licensePlate 由数字、大小写字母或空格 ' ' 组成
    • 1 <= words.length <= 1000
    • 1 <= words[i].length <= 15
    • words[i] 由小写英文字母组成
    Related Topics
    • 数组
    • 哈希表
    • 字符串

  • 👍 116
  • 👎 0
  • 哈希表,字符统计,简单,特纯粹的哈希表统计

    1. 统计licensePlate中字符出现次数
    2. 遍历words[] 分别统计每个word的字符出现次数
    3. 对比两者统计结果,需要满足
      • licensePlate中出现的字符,在word中出现的次数要大于等于在licensePlate中出现的次数
      • 判断需要返回的结果ans 和当前word的长度,取较小的一个,相等的情况不变,即长度相等取现出现的

    就…纯粹的哈希表统计

    代码

    class Solution {
        public String shortestCompletingWord(String licensePlate, String[] words) {
            int[] arr = charCnt(licensePlate);
            String ans = null;
            for (String word : words) {
                int[] wArr = charCnt(word);
                boolean flag = true;
                for (int i = 0; flag && i < arr.length; i++) {
                    if (arr[i]>0 && wArr[i] <arr[i]){
                        flag = false;
                    }
                }
                ans = flag && ( ans == null || word.length() < ans.length()) ? word : ans;
            }
            return ans;
        }
    
        private int[] charCnt(String str){
            int[] arr = new int[26];
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if (c >= 'a' && c <= 'z'){
                    arr[str.charAt(i)-'a']++;
                }
                if (c >= 'A' && c <= 'Z'){
                    arr[str.charAt(i)-'A']++;
                }
            }
            return arr;
        }
    }

    LeetCode刷题【794】有效的井字游戏

    给你一个字符串数组 board 表示井字游戏的棋盘。当且仅当在井字游戏过程中,棋盘有可能达到 board 所显示的状态时,才返回 true

    井字游戏的棋盘是一个 3 x 3 数组,由字符 ' ''X''O' 组成。字符 ' ' 代表一个空位。

    以下是井字游戏的规则:

    • 玩家轮流将字符放入空位(' ')中。
    • 玩家 1 总是放字符 'X' ,而玩家 2 总是放字符 'O'
    • 'X''O' 只允许放置在空位中,不允许对已放有字符的位置进行填充。
    • 当有 3 个相同(且非空)的字符填充任何行、列或对角线时,游戏结束。
    • 当所有位置非空时,也算为游戏结束。
    • 如果游戏结束,玩家不允许再放置字符。

     

    示例 1:

    输入:board = ["O  ","   ","   "]
    输出:false
    解释:玩家 1 总是放字符 "X" 。
    

    示例 2:

    输入:board = ["XOX"," X ","   "]
    输出:false
    解释:玩家应该轮流放字符。
    

    示例 3:

    输入:board = ["XOX","O O","XOX"]
    输出:true
    

     

    提示:

    • board.length == 3
    • board[i].length == 3
    • board[i][j]'X''O'' '
    Related Topics
    • 数组
    • 字符串

  • 👍 112
  • 👎 0
  • 略坑,又臭又长,可以看看

    1. XO数量情况符合 0 <= XO <= 1
    2. 输赢情况判断
      • X赢 :X三连数量为1个或者两个,O三连数量为0个, 此时因为X先手,必然有 数量统计结果XO == 1
      • O赢 : X三连数量为0个,O三连数量为1个,因为O后手,必然有 数量统计结果XO == 0
      • 两人都还没赢: X三连数量为0个,O三连数量为0个

    写二维坐标计算统计太麻烦了,我把board[0] + board[1] + board[2]拼起来了,
    用这样的一维坐标计算统计了

        0 1 2
        3 4 5
        6 7 8
    
        对应为
    
        0 1 2 3 4 5 6 7 8

    代码

    class Solution {
    
        char X = 'X';
        char O = 'O';
    
        public boolean validTicTacToe(String[] board) {
            int xCnt = 0;
            int oCnt = 0;
            String str = board[0] + board[1] + board[2];
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == X){
                    xCnt++;
                }
                if (str.charAt(i) == O){
                    oCnt++;
                }
            }
            if (xCnt - oCnt == 1 || xCnt - oCnt == 0){
                int[] res = countLine(str);
                if (res[0] >=1 && res[1]==0){
                    //X赢
                    // 有个特殊情况,X是可以连成两个3连的
                    // X X X
                    // O O X
                    // O O X
                    return  xCnt - oCnt == 1;
                }else if(res[0]==0 && res[1]==1){
                    //O赢
                    return xCnt - oCnt == 0;
                }else if (res[0] == 0 && res[1] == 0){
                    //都还没赢 比如
                    // X O X
                    // O   O
                    // X O X
                    return true;
                }
            }
            return false;
        }
    
    
        public int[] countLine(String str){
            // 下标转换下,写起来方便
            // 0 1 2
            // 3 4 5
            // 6 7 8
            int[][] arr = new int[8][2];
            arr[0][0] = charCount(str , X, 0,1,2);
            arr[1][0] = charCount(str , X, 3,4,5);
            arr[2][0] = charCount(str , X, 6,7,8);
            arr[0][1] = charCount(str , O, 0,1,2);
            arr[1][1] = charCount(str , O, 3,4,5);
            arr[2][1] = charCount(str , O, 6,7,8);
            arr[3][0] = charCount(str , X, 0,3,6);
            arr[4][0] = charCount(str , X, 1,4,7);
            arr[5][0] = charCount(str , X, 2,5,8);
            arr[3][1] = charCount(str , O, 0,3,6);
            arr[4][1] = charCount(str , O, 1,4,7);
            arr[5][1] = charCount(str , O, 2,5,8);
            arr[6][0] = charCount(str , X, 0,4,8);
            arr[6][1] = charCount(str , O, 0,4,8);
            arr[7][0] = charCount(str , X, 2,4,6);
            arr[7][1] = charCount(str , O, 2,4,6);
            int[] res = new int[2];
            for (int[] ints : arr) {
                res[0] += ints[0]==3?1:0;
                res[1] += ints[1]==3?1:0;
            }
            return res;
        }
    
        public int charCount(String str, char c, int i1, int i2, int i3){
            int count = 0;
            count += str.charAt(i1)==c? 1 : 0;
            count += str.charAt(i2)==c? 1 : 0;
            count += str.charAt(i3)==c? 1 : 0;
            return count;
        }
    
    }

    LeetCode刷题【剑指 Offer 38】字符串的排列

    输入一个字符串,打印出该字符串中字符的所有排列。

     

    你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

     

    示例:

    输入:s = "abc"
    输出:["abc","acb","bac","bca","cab","cba"]
    

     

    限制:

    1 <= s 的长度 <= 8

    Related Topics
    • 字符串
    • 回溯

  • 👍 573
  • 👎 0
  • 回溯基本操作了

    解题思路

    回溯基本操作了

    代码

    class Solution {
    
    
        private List<String> list;
    
        private Integer length;
    
        public String[] permutation(String s) {
            list = new ArrayList<>();
            length = s.length();
            boolean[] visited = new boolean[s.length()];
            dfs(s.toCharArray(),visited,0,new char[s.length()]);
            String[] res = new String[list.size()];
            int i = 0;
            for (String s1 : list) {
                res[i] = s1;
                i++;
            }
            return res;
        }
    
    
        private void dfs(char[] charArr,boolean[] visited,int index,char[] newCharArr){
            if (index==length){
                list.add(new String(newCharArr));
                return;
            }
            Set<Character> sameChar = new HashSet<>();
            for (int i = 0; i < charArr.length; i++) {
                if (visited[i]){
                    continue;
                }
                if (sameChar.contains(charArr[i])){
                    continue;
                }
                sameChar.add(charArr[i]);
                visited[i] = true;
                newCharArr[index] = charArr[i];
                dfs(charArr,visited,index+1,newCharArr);
                visited[i] = false;
            }
        }
    }

    LeetCode刷题【1816】截断句子

    句子 是一个单词列表,列表中的单词之间用单个空格隔开,且不存在前导或尾随空格。每个单词仅由大小写英文字母组成(不含标点符号)。

    • 例如,"Hello World""HELLO""hello world hello world" 都是句子。

    给你一个句子 s​​​​​​ 和一个整数 k​​​​​​ ,请你将 s​​ 截断 ​,​​​使截断后的句子仅含 k​​​​​​ 个单词。返回 截断 s​​​​​​ 后得到的句子

     

    示例 1:

    输入:s = "Hello how are you Contestant", k = 4
    输出:"Hello how are you"
    解释:
    s 中的单词为 ["Hello", "how" "are", "you", "Contestant"]
    前 4 个单词为 ["Hello", "how", "are", "you"]
    因此,应当返回 "Hello how are you"
    

    示例 2:

    输入:s = "What is the solution to this problem", k = 4
    输出:"What is the solution"
    解释:
    s 中的单词为 ["What", "is" "the", "solution", "to", "this", "problem"]
    前 4 个单词为 ["What", "is", "the", "solution"]
    因此,应当返回 "What is the solution"

    示例 3:

    输入:s = "chopper is not a tanuki", k = 5
    输出:"chopper is not a tanuki"
    

     

    提示:

    • 1 <= s.length <= 500
    • k 的取值范围是 [1,  s 中单词的数目]
    • s 仅由大小写英文字母和空格组成
    • s 中的单词之间由单个空格隔开
    • 不存在前导或尾随空格
    Related Topics
    • 数组
    • 字符串

  • 👍 57
  • 👎 0
  • 空格判断、字符复制

    1. 简单,就复制字符
    2. 字符复制完了加一个空格
    3. 计数,小于k
    4. 最后会多复制一个空格最后要截掉

    代码

    class Solution {
        public String truncateSentence(String s, int k) {
            char[] arr = new char[501];
            int cnt = 0;
            int idx = 0;
            int arrIdx = -1;
            while (cnt < k && idx < s.length()){
                if (s.charAt(idx) == ' '){
                    idx++;
                    continue;
                }
                while (idx < s.length() && s.charAt(idx) != ' ' ){
                    arr[++arrIdx] = s.charAt(idx++);
                }
                arr[++arrIdx] = ' ';
                cnt++;
            }
            char[] arr2 = new char[arrIdx];
            System.arraycopy(arr,0,arr2,0,arrIdx);
            return new String(arr2);
        }
    }

    其实题目给了限制条件了

     1 <= s.length <= 500 
     k 的取值范围是 [1, s 中单词的数目] 
     s 仅由大小写英文字母和空格组成 
     s 中的单词之间由单个空格隔开 
     不存在前导或尾随空格 

    所以可以更简单点,直接判断遇到的空格的个数就可以了

    代码

    class Solution {
        public String truncateSentence(String s, int k) {
            char[] arr = s.toCharArray();
            int cnt = 0;
            int idx = -1;
            while (cnt < k && ++idx < s.length()){
                if (arr[idx] == ' '){
                    cnt++;
                }
            }
            char[] arr2 = new char[idx];
            System.arraycopy(arr,0,arr2,0,idx);
            return new String(arr2);
        }
    }

    LeetCode刷题【383】赎金信

    给你两个字符串:ransomNotemagazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。

    如果可以,返回 true ;否则返回 false

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

     

    示例 1:

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

    示例 2:

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

    示例 3:

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

     

    提示:

    • 1 <= ransomNote.length, magazine.length <= 105
    • ransomNotemagazine 由小写英文字母组成
    Related Topics
    • 哈希表
    • 字符串
    • 计数

  • 👍 363
  • 👎 0
  • 哈希统计

    class Solution {
        public boolean canConstruct(String ransomNote, String magazine) {
            int[] arr = new int[26];
            for (int i = 0; i < magazine.length(); i++) {
                arr[magazine.charAt(i)-'a']++;
            }
            for (int i = 0; i < ransomNote.length(); i++) {
                arr[ransomNote.charAt(i)-'a']--;
                if (arr[ransomNote.charAt(i)-'a'] < 0 ){
                    return false;
                }
            }
            return true;
        }
    }