字符串旋转、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

更多学习笔记见个人博客——>呼延十