Day08 字符串

• 一、344. 反转字符串
• 二、541. 反转字符串II
• 三、剑指 Offer 05. 替换空格
• 四、151.翻转字符串里的单词
• 五、剑指Offer58-II.左旋转字符串

专注于为中小企业提供成都网站设计、成都网站建设、外贸网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业灵璧免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了成百上千企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

---

一、344. 反转字符串

class Solution {public void reverseString(char[] s) {int left = 0;
        int right = s.length - 1;
        while(left< right){s[left] ^= s[right];
            s[right] ^= s[left]; 
            s[left] ^= s[right];
            left++;
            right--;
        }
    }
}

此题使用双向指针即可，无难度；
关键:此题使用了异或运算，异或可以代替三角交换，需要熟悉。

二、541. 反转字符串II

class Solution {public String reverseStr(String s, int k) {char[] ch = s.toCharArray();
        for(int i = 0; i< ch.length; i += 2 * k){int start = i;
            int end = Math.min(i + k - 1,ch.length - 1);
            while(start< end){ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

此题与上一题类似，区别在于只翻转部分的字符串，对其进行变量控制即可。

三、剑指 Offer 05. 替换空格

class Solution {//使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
	public static String replaceSpace(String s) {if (s == null) {return null;
        }
        //选用 StringBuilder 单线程使用，比较快，选不选都行
        StringBuilder sb = new StringBuilder();
        //使用 sb 逐个复制 s ，碰到空格则替换，否则直接复制
        for (int i = 0; i< s.length(); i++) {//s.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
            //if (" ".equals(String.valueOf(s.charAt(i)))){}
            if (s.charAt(i) == ' ') {sb.append("%20");
            } else {sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

	//方式二：双指针法
    public String replaceSpace(String s) {if(s == null || s.length() == 0){return s;
        }
        StringBuffer sb = new StringBuffer();
        for(int i = 0;i< s.length(); i++){if(s.charAt(i) == ' '){sb.append("  ");
            }
        }
        //若是没有空格直接返回
        if(sb.length() == 0){return s;
        }
        int left = s.length() - 1;
        s += sb.toString();
        int right = s.length() - 1;
        char[] ch = s.toCharArray();
        while(left>=0){if(ch[left] == ' '){ch[right--] = '0';
                ch[right--] = '2';
                ch[right] = '%';  
            }else{ch[right] = ch[left];
            } 
            left--;
            right--;
        }
        return new String(ch);
    }
}

此题有两种解法：
解法一：new一个StringBuilder()，判断是否为空格进行追加就行，无难度
解法二：遍历数组得出有多少空格，算出数组的大小，从后往前填充数组；从后往前遍历数组是该算法的关键

四、151.翻转字符串里的单词

class Solution {public String reverseWords(String s) {// 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
        
    }

     private StringBuilder removeSpace(String s) {int start = 0;
        int end = s.length() - 1;
        //去除开头的空格
        while (s.charAt(start) == ' ') start++;
        //去除末尾的空格
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        //去除中间空格
        while (start<= end) {char c = s.charAt(start);
            //如果是空格就跳过（这里需要保留第一个空格所以需要||后面的那个条件存在）
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {sb.append(c);
            }
            start++;
        }
        
        return sb;
    }
    //翻转字符串，使用方法setCharAt();
    public void reverseString(StringBuilder sb, int start, int end) {while (start< end) {char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }
    
    private void reverseEachWord(StringBuilder sb) {int start = 0;
        int end = 1;
        int n = sb.length();
        while (start< n) {//首先找到第一个单词后面的空格，然后翻转单词
            while (end< n && sb.charAt(end) != ' ') {end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

此题的思路是：先翻转整个字符串，再翻转单个单词。具体看代码内的注释。

五、剑指Offer58-II.左旋转字符串

class Solution {public String reverseLeftWords(String s, int n) {int len=s.length();
        StringBuilder sb=new StringBuilder(s);
        reverseString(sb,0,n-1);
        reverseString(sb,n,len-1);
        return sb.reverse().toString();
    }
    public void reverseString(StringBuilder sb, int start, int end) {while (start< end) {char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }
}

与上一题类似，使用局部翻转加全局翻转即可实现左旋字符串。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：Day08字符串-创新互联
网页网址：http://scyanting.com/article/shcsh.html