7. 整数反转

image.png

转化为字符串

  1. class Solution {
  2. public:
  3.     void reverse_str(string& s, int l, int r) {
  4.         for (int i = l, j = r; i < j; i++, j--) swap(s[i], s[j]);
  5.     }
  6.     int reverse(int x) {
  7.         string s = to_string(x);
  8.         if (s[0] == '-') reverse_str(s, 1, s.size() - 1);
  9.         else reverse_str(s, 0, s.size() - 1);
  10.         long long t = stoll(s);
  11.         if (t > INT32_MAX || t < INT32_MIN) return 0;
  12.         else return t;
  13.     }
  15. };

数学方法

因为不能使用long long所以上一个方法有点小问题

  1. class Solution {
  2. public:
  3.     int reverse(int x) {
  4.         int rev = 0;
  5.         while (x != 0) {
  6.             if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
  7.                 return 0;
  8.             }
  9.             int digit = x % 10;
  10.             x /= 10;
  11.             rev = rev * 10 + digit;
  12.         }
  13.         return rev;
  14.     }
  15. };

470. 用 Rand7() 实现 Rand10()

image.png

拆分十分之一为 二分之一乘五分之一

  1. // The rand7() API is already defined for you.
  2. // int rand7();
  3. // @return a random integer in the range 1 to 7
  5. class Solution {
  6. public:
  7.     int rand10() {
  8.         int a, b;
  9.         while ((a = rand7()) > 6); // 限定 a 的范围为 [1 - 6] 判断奇偶， 概率为二分之一
  10.         while ((b = rand7()) > 5); // 限定 b 的范围为 [1 - 5] 每个数的概率为五分之一
  11.         return (a & 1) == 1 ? 5 + b : b;
  12.     }
  13. };

拒绝采样

7 * 7 拒绝大于40的数

  1. class Solution {
  2. public:
  3.     int rand10() {
  4.         int row, col, idx;
  5.         do {
  6.             row = rand7();
  7.             col = rand7();
  8.             idx = col + (row - 1) * 7;
  9.         } while (idx > 40);
  10.         return 1 + (idx - 1) % 10;
  11.     }
  12. };