字符串旋转、fizzbuzz、落单的数、翻转整数
1.字符串旋转
来源: lintcode-字符串旋转
问题描述
描述
给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)
样例
对于字符串 “abcdefg”.
offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"挑战
在数组上原地旋转，使用O(1)的额外空间
解决思路
这道题比较简单，可以简单粗暴的直接截断重新拼接即可，但是题目要求使用O(1)的额外空间。
这就要换个思路了，O(1)的空间，就代表着每次只可以移动一个字符，那么解决的思路就变成了：每次移动一个字符，移动offset次。
即：每次将末尾的字符移动到第一位，其他位置的字符向后移动一位。将这个单字符的移动操作进行offset次。
注意事项
1.题目中并没有规定offset必定小于字符串长度，因此需要处理这个逻辑，易知，当后移n(n=字符串长度)的时候，字符串回归原位置，因此可以将offset对字符串长度取模，得到真正的位移距离。
2.在取模过程中，字符串长度作为除数，因此需要提前进行字符串长度是否等于0的判断。
实现代码
public String stringRotate(String string, int offset) {
if (null == string || string.length() == 0) {
return "";
}
offset = offset % string.length();
char[] charss = string.toCharArray();
for (int i = 0; i < offset; i++) {
charss = moveLastToFirst(charss);
}
return new String(charss);
}
private char[] moveLastToFirst(char[] chars) {
int l = chars.length - 1;
char a = chars[l];
for (; l > 0; l--) {
chars[l] = chars[l - 1];
}
chars[0] = a;
return chars;
}2.Fizz和Buzz
来源: lintcode-fizz-buzz
问题描述
描述
给你一个整数n. 从 1 到 n 按照下面的规则打印每个数：
- 如果这个数被3整除，打印fizz.
- 如果这个数被5整除，打印buzz.
- 如果这个数能同时被3和5整除，打印fizz buzz.
样例
比如 n = 15, 返回一个字符串数组：
[
"1", "2", "fizz",
"4", "buzz", "fizz",
"7", "8", "fizz",
"buzz", "11", "fizz",
"13", "14", "fizz buzz"
]挑战
Can you do it with only one if statement?
解决思路
这个是真的简单，，，我就不写思路了吧。。
从1到n，遍历，并且对每个做是否整除3，整除5，整除15的判断。
至于挑战：Can you do it with only one if statement?
** No, I can’t **
实现代码
public List<String> fizzBuzz(int n) {
List<String> result = new ArrayList<>();
int i = 1;
while (i <= n){
if (i % 15 == 0){
result.add("fizz buzz");
}else {
if (i % 3 == 0){
result.add("fizz");
}else if (i % 5 == 0){
result.add("buzz");
}else {
result.add(String.valueOf(i));
}
}
i++;
}
return result;
}3.反转一个3位整数
来源: lintcode-反转一个3位整数
问题描述
描述
反转一个只有3位数的整数。
样例
- 123 反转之后是 321。
- 900 反转之后是 9。
解决思路
这道题其实不限制与三位数，实现思路是善加利用除法和取模运算。
123 的翻转为 3 * 100 + 2 * 10 + 1； 那么怎么来控制每位数字乘10的次数呢？当然是取模运算后，越早得到的数字乘十次数越多。
假设传入值为 n=12345,结果result =0；
1.
tmp = n % 10 = 5;
result = result * 10 + tmp = 5;;
n = n / 10;
2.tmp = n % 10 = 4;
result = result * 10 + tmp = 54；
n = n / 10;
有没有看出什么呢？
后面的不再写啦直接代码见。实现代码
public int rotateInt(int number) {
int result = 0;
while (number != 0) {
result = (result * 10) + (number % 10);
number /= 10;
}
return result;
}这个难度为入门的有点简单的过分啊，，，不再做了吧。
4.落单的数
来源: lintcode-落单的数
问题描述
描述
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
样例
给出 [1,2,2,1,3,4,3]，返回 4
挑战
一次遍历，常数级的额外空间复杂度
解决思路
这道题，暴力的方法就不讲了，主难在挑战上。
首先你要懂得异或的原理，即可以得出3个结论：
- 相同的数字异或结果为0
- 和0异或结果为自身
- 异或也符合结合律。
即
a ^ a = 0;
a ^ 0 = a;
a ^ b ^ c = a ^ (b ^ c);这样就相当的明了了，我们只需要数组中的数字异或，根据结合律，两个相同的数字得到0，0和落单的数异或得到结果。
实现代码
public int singleNumber(int[] A) {
if (A.length == 0) {
return 0;
}
int a = A[0];
for (int i = 1; i < A.length; i++) {
a ^= A[i];
}
return a;
}ChangeLog
2018-09-22 添加前4道题
以上皆为个人所思所得，如有错误欢迎评论区指正。
欢迎转载，烦请署名并保留原文链接。
联系邮箱：huyanshi2580@gmail.com