source of the question: http://seanzhou.iteye.com/blog/2032981
Question 1 Character-wise Shift For String
Implement an algorithm that can do character-wise shift for strings in either direction. For example,
To shift string "abcdef" to the left by 2 characters, you get "cdefab".
To shift string "abcdef" to the right by 3 characters, you get "defabc"
Performance requirement: assume the length of the string is n, the algorithm should finish in O(n) time and within O(1) space.
My Thoughts
1. Start from the first character, find its target position, put it there. For the character originally in target position of the first character, iteratively find its target positon and put it there again ... and so on.
2. We only need to record how many characters have been put in its correct position.
3. It's possible that n shares some common factor with m, so that after some iteration, you may go back to the first character. So you need to record where did you start. After you go back to starting point, you should go right one step if not all of the characters have found its correct position.
Implementation in Java
package q1; /** * Question 1 Character-wise Shift For String * * Implement an algorithm that can do character-wise shift for strings in either direction. For example, * * To shift string "abcdef" to the left by 2 characters, you get "cdefab". * To shift string "abcdef" to the right by 3 characters, you get "defabc" * * Performance requirement: assume the length of the string is n, the algorithm should finish in O(n) time and within O(1) space. * @author Sean * */ public class StringShift { public static void main(String[] args) { //m & n has no common factors assert "DEFGABC".equals(shift("ABCDEFG", 3, true)); assert "EFGABCD".equals(shift("ABCDEFG", 3, false)); //n is multiple of m assert "EFGHABCD".equals(shift("ABCDEFGH", 4, true)); assert "EFGHABCD".equals(shift("ABCDEFGH", 4, false)); //n and m shares a common factor assert "GHIABCDEF".equals(shift("ABCDEFGHI", 6, true)); assert "DEFGHIABC".equals(shift("ABCDEFGHI", 6, false)); } private static String shift(String origin, int m, boolean left) { // input check if ( origin == null ) return null; int len = origin.length(); if (len == 0 ) return origin; m %= len; if ( m == 0 ) return origin; //get the char array from the String char[] arr = new char[len]; origin.getChars(0, len, arr, 0); //shift left or right? int direction = left ? -1 : 1; //record how many characters have been put in its correct position int found = 0; //record the starting position of the character which we are looing for its target position int start = 0; //record the current position of the character which we are looking for its target position int current = 0; char c = arr[current]; char temp; // do the shift from the beginning character while (found < len) { // find the target position , plus n is to avoid negative current = (direction * m + current + len) % len; // swap the source and target temp = c; c = arr[current]; arr[current] = temp; ++found; // check whether the iteration go back to the starting point if ( current == start) { current = start = ( start + 1) % len; c = arr[current]; } } return new String(arr); } }
相关推荐
Rec. ITU-R BT.709-3 1 RECOMMENDATION ITU-R BT.709-3 ...PARAMETER VALUES FOR THE HDTV STANDARDS FOR PRODUCTION AND INTERNATIONAL PROGRAMME EXCHANGE (Question ITU-R 27/11) (1990-1994-1995-1998)
Rec. ITU-R BT.709-1 1 RECOMMENDATION ITU-R BT.709-1 BASIC PARAMETER VALUES FOR THE HDTV STANDARD FOR THE STUDIO AND FOR INTERNATIONAL PROGRAMME EXCHANGE (Question ITU-R 27/11) (1990-1994)
Java练习题Question1.txtJava练习题Question1.txtJava练习题Question1.txtJava练习题Question1.txtJava练习题Question1.txtJava练习题Question1.txtJava练习题Question1.txtJava练习题Question1.txtJava练习题...
python练习题Question1.txtpython练习题Question1.txtpython练习题Question1.txtpython练习题Question1.txtpython练习题Question1.txtpython练习题Question1.txtpython练习题Question1.txtpython练习题Question1.txt...
d-freebase-mids/ has Freebase mids for each concept in each question, based on YodaQA entity linking results from d-dump. d-freebase-rp/ has extra custom-computed Freebase relation paths. d-freebase-...
Trust the best selling Official Cert Guide series from Cisco Press to help you learn, prepare, and practice for exam success. They are built with the objective of providing assessment, review, and ...
Rice / Coursera算法思维课程的文件第1-2周project1.py-项目1代码application1.py-应用程序1项目的代码dpa_algorithm.py-问题4的DPA算法的实现dpa_trial.py-为dpa算法提供的类application1_question1.png-应用程序1...
The benefits from tumbling two-legged mechatronic creatures and multiprocessor-based question-and-answer games seem hard to discover for noninvolved persons. In general the benefits from fundamental ...
题目1 还未回答 满分1.00 Flag question 题干 判定一个栈ST(最多元素为m0)为栈满的条件是() 选择一项: a. ST-〉top==m0-1 b. ST-〉top!=0 c. ST-〉top==m0 d. ST-〉top==0 题目2 还未回答 满分1.00 Flag question...
Java练习题Question3.txtJava练习题Question3.txtJava练习题Question3.txtJava练习题Question3.txtJava练习题Question3.txtJava练习题Question3.txtJava练习题Question3.txtJava练习题Question3.txtJava练习题...
Java练习题Question2.txtJava练习题Question2.txtJava练习题Question2.txtJava练习题Question2.txtJava练习题Question2.txtJava练习题Question2.txtJava练习题Question2.txtJava练习题Question2.txtJava练习题...
Java练习题Question8.txtJava练习题Question8.txtJava练习题Question8.txtJava练习题Question8.txtJava练习题Question8.txtJava练习题Question8.txtJava练习题Question8.txtJava练习题Question8.txtJava练习题...
Java练习题Question5.txtJava练习题Question5.txtJava练习题Question5.txtJava练习题Question5.txtJava练习题Question5.txtJava练习题Question5.txtJava练习题Question5.txtJava练习题Question5.txtJava练习题...
Java练习题Question9.txtJava练习题Question9.txtJava练习题Question9.txtJava练习题Question9.txtJava练习题Question9.txtJava练习题Question9.txtJava练习题Question9.txtJava练习题Question9.txtJava练习题...
Java练习题Question4.txtJava练习题Question4.txtJava练习题Question4.txtJava练习题Question4.txtJava练习题Question4.txtJava练习题Question4.txtJava练习题Question4.txtJava练习题Question4.txtJava练习题...
Java练习题Question6.txtJava练习题Question6.txtJava练习题Question6.txtJava练习题Question6.txtJava练习题Question6.txtJava练习题Question6.txtJava练习题Question6.txtJava练习题Question6.txtJava练习题...
Java练习题Question7.txtJava练习题Question7.txtJava练习题Question7.txtJava练习题Question7.txtJava练习题Question7.txtJava练习题Question7.txtJava练习题Question7.txtJava练习题Question7.txtJava练习题...
Java练习题Question10.txtJava练习题Question10.txtJava练习题Question10.txtJava练习题Question10.txtJava练习题Question10.txtJava练习题Question10.txtJava练习题Question10.txtJava练习题Question10.txtJava练习...
QuestionOne.java