字符串旋转、fizzbuzz、落单的数、翻转整数

Posted1 by 呼延十 on September 22, 2018 Hot:

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

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