Algorithms: Math

8 minute read

位运算
10进制进位，取余
找规律题目
136. Single Number
```
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
```
- 利用取余操作的特性相同为0，不同为1。可以得出，只出现一次的数字。
```
int singleNumber(vector<int>& nums) {
 int start = 0;
 for (auto n:nums) {
   start ^= n;
 }
 return start;
}
```
  137. Single Number II
```
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
```
- 136的升级版，可以使用32bit保存对应每个bit之和取余进行操作。对重复出现的那个的值进行取余，如本题中的3，上题中的2。 ```c++ int singleNumber(vector& nums) { vector table(32, 0); int res = 0;
for (int i = 0; i < 32; ++i) { for (auto j = 0; j < nums.size(); ++j) { table[i] += ((nums[j] » i)&1); table[i] %= 3; } res |= (table[i] « i); } return res; } ``` —
29. Divide Two Integers
```c++ Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

1. 使用位运算实现除法
2. 主要思想是倍数可以用2的指数和求出
```c++
int divide(int dividend, int divisor) {
    if (!divisor || (dividend == INT_MIN && divisor == -1)) {
        return INT_MAX;
    }
    
    int sign = ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) ) ? -1 : 1;
    long long dvd = labs(dividend);
    long long dvs = labs(divisor);
    int res = 0;
    
    while (dvs <= dvd) {
        long long count = 1, dv = dvs;
        while ((dv << 1) <= dvd) {
            dv <<= 1;
            count <<= 1;
        }
        dvd -= dv;
        res += count;
    }
    return res*sign;
}

50. Pow(x, n)

Implement pow(x, n).

不适用位运算时间复杂度为O(n)，使用位运算时间复杂度为O(logn)

使用位运算的关键是理解将某个数值拆分成二进制表示的形式，如 9的二进制表示为 1001 即是 2^3 + 2^0

double myPow(double x, int n) {
  long long p = labs(n);
  double res = 1;
  while (p > 0) {
      if (p & 1) res *= x;
      x *= x;
      p >>= 1;
  }
  return n < 0 ? 1/res : res;
}

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

巧妙地利用sum记录一般数目，只能在原地进行运算。其实也是移位，不过是10进制的。遍历次数降低一半且空间复杂度为O(1)

bool isPalindrome(int x) {
  if (x < 0 || (x != 0 && x % 10 == 0)) return false;
  int sum = 0;
  while (x > sum) {
      sum = sum*10 + x%10;
      x /= 10;
  }
    
  return (x == sum) || (x == sum/10);
}

8. String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button  to reset your code definition.

实现atoi函数，需要注意的是 1. 去掉前面和后面的空白字符 2. 有效字符必须在’0’和’9’之间 3. 大于INT_MAX的输出INT_MAX，小于INT_MIN的 INT_MIN

int myAtoi(string str) {
  int cur = str.find_first_not_of(' ');
  int pos = 1;
  if (str[cur] == '-' || str[cur] == '+') {
      pos = (str[cur] == '-') ? -1 : 1;
      cur++;
  }
    
  long result = 0;
  while (cur < str.size() && str[cur] >= '0' && str[cur] <= '9') {
      result = result*10 + str[cur++] - '0';
      if (result*pos >= INT_MAX) return INT_MAX;
      if (result*pos <= INT_MIN) return INT_MIN;
  }
  return result*pos;
}

31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解析: 数组的下一个字典顺序
边界：数组大小小于2
思路：找规律的题目，1. 从后往前找第一个相邻的构成升序的p[n] < p[n+1]，n点为违法点。2. 对p[n]之后的元素进行逆序 3. 在排序后的p[n+1]至最后的第一个大于p[n]的元素与p[n]交换
C++ STL中下一个字典顺序的函数，next_permutation(beg, end)

时间复杂度：O(n)

void nextPermutation(vector<int>& nums) {
  if(nums.size() < 2) return;
  int i = nums.size() - 2;
  for (;i >= 0; --i) {
      if (nums[i] < nums[i+1]) break;
  }
  reverse(nums.begin() + i + 1, nums.end());
  if (i == -1) return;
  int j = i+1;
  for (; j < nums.size(); ++j) {
      if (nums[i] < nums[j]) {
          swap(nums[i], nums[j]);
          break;
      }
  }
}

60. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

求[1,n]构成的第k个数列，可以使用31题中的方法一步一步来，也可以根据规律去做。规律如下：第一位为每(n-1)!为1组，则res[0]为nums[k/(n-1)!]。剩下的n-1个数组也是这个规律。每次需要更新k和count，k %= count(含义为该组中第k个)。

string getPermutation(int n, int k) {
  vector<int> nums(n);
  int count = 1;
  for (int i = 0; i < n; ++i) {
      nums[i] = i + 1;
      count *= (i+1);
  }
    
  k--;
  string res;
  for (int i = 0; i < n; ++i) {
      count /= (n - i);
      int cur = k/count;
      res += ('0' + nums[cur]);
        
      k %= count;
      for(int j = cur; j < n - i - 1; ++j) {
          nums[j] = nums[j + 1];
      }
  }
  return res;
}

3. Roman to Integer

```c++ Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

* 罗马数字转换成阿拉伯数字，主要是找出每个罗马数字对应的大小
[//]: # ()
```c++
int romanToInt(string s) {
    unordered_map<char,int> hash_table = {{'I',1}, {'V',5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
    int sum = hash_table[s.back()];
    for (int i = s.size() - 2; i >= 0; --i) {
        if (hash_table[s[i]] < hash_table[s[i+1]]) {
            sum -= hash_table[s[i]];
        } else {
            sum += hash_table[s[i]];
        }
    }
    
    return sum;
}

59. Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

找到规律即可

vector<vector<int>> generateMatrix(int n) {
  vector<vector<int>> vv(n,vector<int>(n,0));
  int rowStart = 0, rowEnd = n - 1;
  int colStart = 0, colEnd = n - 1;
  int cnt = 1;
    
  while (rowStart <= rowEnd && colStart <= colEnd) {
      for(int i = colStart; i<= colEnd; i++)
          vv[rowStart][i] = cnt++;
      rowStart++;
    
      for(int i = rowStart; i<= rowEnd; i++)
          vv[i][colEnd] = cnt++;
      colEnd--;
        
      for (int i = colEnd; i >= colStart; --i) {
          vv[rowEnd][i] = cnt++;
      }
      rowEnd--;
        
      for (int i = rowEnd; i >= rowStart; --i) {
          vv[i][colStart] = cnt++;
      }
      colStart++;
  }
  return vv;
}

48. Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

将数组旋转2次，一次是水平或垂直，一次是斜着沿着轴。顺序无关 ```c++ /*
clockwise rotate
first reverse up to down, then swap the symmetry
1 2 3 7 8 9 7 4 1
4 5 6 => 4 5 6 => 8 5 2
7 8 9 1 2 3 9 6 3 */ void rotate(vector<vector > &matrix) { reverse(matrix.begin(), matrix.end()); for (int i = 0; i < matrix.size(); ++i) { for (int j = i + 1; j < matrix[i].size(); ++j) swap(matrix[i][j], matrix[j][i]); } }
```
---
## [149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)
```c++
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
```
找出一条直线上最多的点
这种题最怕的就是直接被吓到，没思路。其实一步步挨个遍历，下层循环遍历剩余点即可。顶层循环下，当前点做起点，建立最大公约数的map，记录重复点、x相同的点；每次顶层循环，求出以当前为起点哪个直线上的点最多（斜率为0的为1条线）
其中用到数学知识，求最大公约数，使用辗转相除法。余数为0时，小的那个为最大公约数。不为0时，小的为余数，大的为小的。 ```c++ /**
Definition for a point.
struct Point {
int x;
int y;
Point() : x(0), y(0) {}
Point(int a, int b) : x(a), y(b) {}
}; */ class Solution { public: int maxPoints(vector &points) { if(points.size()<2) return points.size(); int result=0; for(int i=0; i<points.size(); i++) { map<pair<int, int>, int> lines; int localmax=0, overlap=0, vertical=0; for(int j=i+1; j<points.size(); j++) { if(points[j].x==points[i].x && points[j].y==points[i].y) { overlap++; continue; } else if(points[j].x==points[i].x) vertical++; else { int a=points[j].x-points[i].x, b=points[j].y-points[i].y; int gcd=GCD(a, b); a/=gcd; b/=gcd; lines[make_pair(a, b)]++; localmax=max(lines[make_pair(a, b)], localmax); } localmax=max(vertical, localmax); } result=max(result, localmax+overlap+1); } return result; }

private: int GCD(int a, int b) { while (b) { int tmp = a%b; a = b; b = tmp; } return a; } }; ```

Share on

Twitter Facebook Google+ LinkedIn

Ruijiang Gao

Algorithms: Math

找规律题目

136. Single Number

137. Single Number II

29. Divide Two Integers

50. Pow(x, n)

9. Palindrome Number

8. String to Integer (atoi)

31. Next Permutation

60. Permutation Sequence

3. Roman to Integer

59. Spiral Matrix II

48. Rotate Image

Share on

You May Also Enjoy

学术搜索技巧

使用IPv6免流量上网

个人网站搭建

Tensorflow安装