摘要：反转上述步骤得到的结果字符串，即反转字符串的两部分和给予反转，得到，形式化表示为，这就实现了整个反转。例如，原字符串为，，输出结果为。同单词翻转输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。
旋转字符串 题目描述July 程序员编程艺术：面试和算法心得题目及习题
给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串 “abcdef” 前面的 2 个字符"a"和"b"移动到字符串的尾部，使得原字符串变成字符串 “cdefab”。请写一个函数完成此功能，要求对长度为 n 的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
解题思路：三步反转法对于这个问题，换一个角度思考一下。
将一个字符串分成 X 和 Y 两个部分，在每部分字符串上定义反转操作，如 X^T，即把 X 的所有字符反转（如，X="abc"，那么 X^T="cba"），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。
例如，字符串 abcdef ，若要让 def 翻转到 abc 的前头，只要按照下述 3 个步骤操作即可：
首先将原字符串分为两个部分，即 X:abc，Y:def；
将 X 反转，X->X^T，即得：abc->cba；将 Y 反转，Y->Y^T，即得：def->fed。
反转上述步骤得到的结果字符串 X^TY^T，即反转字符串 cbafed 的两部分（cba 和 fed）给予反转，cbafed 得到 defabc，形式化表示为 (X^TY^T)^T=YX，这就实现了整个反转。
java
public class RotateString { public void solution(char[]s , int k){ reverse(s,0,k-1); reverse(s,k,s.length-1); reverse(s,0,s.length-1); } private void reverse(char[]s, int start, int end){ while(start <= end) { char temp; temp = s[end]; s[end] = s[start]; s[start] = temp; start++; end--; } }
这就是把字符串分为两个部分，先各自反转再整体反转的方法，时间复杂度为 O(n)，空间复杂度为 O(1)，达到了题目的要求。
习题 1、链表翻转给出一个链表和一个数 k，比如，链表为 1→2→3→4→5→6，k=2，则翻转后 2→1→6→5→4→3，若 k=3，翻转后 3→2→1→6→5→4，若 k=4，翻转后 4→3→2→1→6→5，用程序实现。
有介绍链表完全反转
这道题是基于链表反转，链表分成两部分：AB， 先反转A,然后再反转B，把AB相连即可。如图
这里需要注意的是指针要记录链接位置，不要断链。
// S = AB S" =ATBT
public Node solution(Node phead, int k){
Node p = phead;
int i = 1; // A 部分反转次数
int j = 1; // B部分反转次数
if(p!=null){
// A 部分反转
Node q = p.next;
p.next = null;
while(q != null && i< k ){
Node r = q.next;
q.next = p;
p = q;
q = r;
i++;
} // A部分反转结束，p指向结果的头指针，q指向B部分的第一个元素
// B 部分反转
Node qnext = q.next;
q.next = null;
while(qnext != null && j< n-k){
Node r = qnext.next;
qnext.next = q;
q = qnext;
qnext = r;
j++;
}// B部分反转结束，q指向结果的头指针
//连接AB两部分
phead.next = q;
}
return p;
}
2、编写程序
在原字符串中把字符串尾部的 m 个字符移动到字符串的头部，要求：长度为 n 的字符串操作时间复杂度为 O(n)，空间复杂度为 O(1)。 例如，原字符串为 ”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。
同1
3、单词翻转输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如，输入 “I am a student.”，则输出 “student. a am I”。
public void solution(char[]s){
int start = 0;
for(int i=0;i
字符串包含
给定两个分别由字母组成的字符串 A 和字符串 B，字符串 B 的长度比字符串 A 短。请问，如何最快地判断字符串 B 中所有字母是否都在字符串 A 里？
为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数 bool StringContains(string &A, string &B)
比如，如果是下面两个字符串：
String 1：ABCD
String 2：BAD
答案是 true，即 String2 里的字母在 String1 里也都有，或者说 String2 是 String1 的真子集。
如果是下面两个字符串：
String 1：ABCD
String 2：BCE
答案是 false，因为字符串 String2 里的 E 字母不在字符串 String1 里。
同时，如果 string1：ABCD，string 2：AA，同样返回 true。
解题思路
可以构建一个hash表，26位的数组，可以先把长字符串 a 中的所有字符都放入一个 Hashtable 里，比如a 放入 hash[0], d放入 hash3. 然后轮询短字符串 b，看短字符串 b 的每个字符是否都在 Hashtable 里，如果都存在，说明长字符串 a 包含短字符串 b，否则，说明不包含。
这样时间复杂度O(n+m),空间复杂度O(n)
还有一个更简单的方法，时间复杂度O(n+m),空间复杂度O(1)
用到了|和& 操作，补充下：
0001 | 0010 = 0011
0010 & 0001 = 0000
0111 & 0100 = 0100
boolean solution(String a, String b){
int hash = 0;
// 对字符串A，用位运算计算一个签名
for(int i=0;i
变位词
编程珠玑关于变位词
如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，比如 bad 和 adb 即为兄弟字符串，现提供一个字符串，如何在字典中迅速找到它的兄弟字符串，请描述数据结构和查询过程。
解题思路：使用散列表 (Hash), 判断字符出现次数.
哈希表
(1)先创建hashmap，key是字符串的字符，value:统计字符串1中出现的次数；
(2)将哈希表扫描第二个字符串时，扫描到每个字符时候，为哈希表减去1，
(3)如果最后哈希表所有的值都为0，则为变位词，否则不是变位词
public static boolean checkBrother_2(char[] s1, char[] s2){
HashMap recordTable = new HashMap();
for(char s: s1){
if(!recordTable.containsKey(s))
recordTable.put(s, 1);
else{
recordTable.put(s, recordTable.get(s) + 1);
}
}
for(char s : s2){
recordTable.put(s, recordTable.get(s) - 1);
}
int count = 0;
Collection c = recordTable.values();
Iterator iter = c.iterator();
while(iter.hasNext()){
count += Math.abs((Integer) iter.next());
}
if(count == 0)
return true;
else
return false;
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64326.html
摘要：求字符串的全排列字符串的全排列设计一个算法，输出一个字符串字符的全排列。的做法没有结果的，都是在一个字符串上进行的操作。字符串的全组合输入三个字符，则它们的组合有。因此可以循环字符串长度，然后输出对应代表的组合即可。 求字符串的全排列 字符串的全排列 设计一个算法，输出一个字符串字符的全排列。 比如，String = abc 输出是abc,bac,cab,bca,cba,...
摘要：判断一条单向链表是不是回文解法可以借助栈，将遍历到的前半段链表节点放入栈，后半段每当遍历到一个，都要与出栈的节点相比较。如果中间出现不相等的情况，则不是回文。 [July 程序员编程艺术：面试和算法心得题目及习题][1] 字符串转换成整数 also Leetcode 8 String to Integer (atoi) 题目描述 输入一个由数字组成的字符串，把它转换成整...
摘要：遇到问题查查，看看，大神的讲解问问岛胖君下面是我最近整理出来的关于字符串的文章的怎么翻译汇集目录非常希望强化博客的功能，比如分类，置顶。 虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党 最近在看算法和语言，基本属于看知识 --> java实现 --> 整理blog 这个路线。 遇到问题查查st...
摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。 面试算法实践与国外大厂习题指南 翻译自 Kevin Naughton Jr. 维护的仓库 interviews，包含了在线练习、算法概述与大厂习题实战等内容。笔者发现正好和...
阅读 1552·2021-11-17 09:33
阅读 1099·2021-11-12 10:36
阅读 2413·2019-08-30 15:54
阅读 2440·2019-08-30 13:14
阅读 2912·2019-08-26 14:05
阅读 3288·2019-08-26 11:32
阅读 3000·2019-08-26 10:09
阅读 2994·2019-08-26 10:09
