LeetCode趣题分享 | 一个除法函数

小鸡
阅读829 喜欢7 cpp 更新2019-4-26

今天刷Leetcode遇到一个题目挺有趣,虽然思路有了,然而处理整型数溢出处理好久。也可以看出自己在这方面的薄弱。原题地址

题目内容如下,咋一看很简单。

给定两个整数,被除数 a 和除数 b。
将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 a 除以除数 b 得到的商。

示例 1:

输入: a = 10, b = 3
输出: 3

示例 2:

输入: a = 7, b = -3
输出: -2

说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。
本题中,如果除法结果溢出,则返回 2^31 − 1。

除法的思想

题目中已经规定算法不能用乘除和取模等运算。

那么如果我们从除法的定义,也就是一个被除数能够被一个除数连续除多少次
从这个角度看,算法就很好写了,一个循环一直减被除数,直到被除数小于除数。

int divid(int y, int x){
int tmp = 0;
while(y > x){
y -= x;
tmp++;
}
return tmp;
/*
这里还要考虑符号问题,溢出问题等。我只是简单写个思路
*/
}

这里还要考虑符号问题,溢出问题等。我只是简单写个思路。
然而,如果是999999999/2;那么循环要循环999999999/2次,很明显不能用这种方法。

那么还有什么思路可以不用循环这么多次呢?

这里就想到了数值的左移和右移。

移位运算

c++中的移位运算,比如左移

int k = 2;
k = k<<3; //k被左移3位,k=8

这里的移位是在二进制上进行,将k的二进制数左移3位。

10 -> 10000

也就是说某个数左移n位,就等于该数乘于2^n。

这样我们就可以使用位移来得到一个最大接近被除数的数

比如被除数 y = 210,除数 x = 3,初始化结果result = 0

  1. 将x移位得到一个最大接近y但不超过y的数

x<<6 = x * 64 = 172

  1. 然后我们将得到的移位数加到结果里,并且被除数减去这个乘数

result += 1<<6
y -= x<<6

重复1,2步直到 y < x;

算法实现

执行用时 : 16 ms, 在Divide Two Integers的C提交中击败了73.04% 的用户
内存消耗 : 8.2 MB, 在Divide Two Integers的C
提交中击败了76.92% 的用户

#include <iostream>
using namespace std;

class Solution{
public:
int left(unsigned int &d,unsigned int x){
int lef = x, i = 0;
for (; i< 31 && lef<<i <= d; i++);
if(i != 0) {
d -= lef<<(i-1);
return 1<<(i-1);
}
return 0;
}
int divide(int dividend, int divisor) {
if (dividend == 0) {
return 0;
}
if (dividend == INT_MIN && divisor == -1) {
return INT_MAX;
}
if (divisor == INT_MIN && dividend == INT_MIN) {
return 1;
}
if (divisor == INT_MIN) {
return 0;
}
bool sign = (dividend^divisor) < 0;
unsigned int dd = dividend == INT_MIN ? 0x80000000 : abs(dividend);
unsigned int dr = abs(divisor);
if(dr == 1) return sign ? -dd : dd;
int tmp = left(dd, dr), result = tmp;
while(tmp){
tmp = left(dd, dr);
result += tmp;
}
return sign ? -result : result;
}
};

/*
执行用时 : 16 ms, 在Divide Two Integers的C++提交中击败了73.04% 的用户
内存消耗 : 8.2 MB, 在Divide Two Integers的C++提交中击败了76.92% 的用户
*/

思路还是很简单的,但是其中有很多要考虑到的细节,非常烦人,很多意想不到的细节导致出错(主要是溢出),调bug调了1个多小时。

下面顺便写一下另一个比较有趣的

翻转k子链表

给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。

示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5

这里用到以空间换时间的想法,用一个辅助向量存储链表节点,当所有子链都翻转后,在重新连接指针。

执行用时 : 32 ms, 在Reverse Nodes in k-Group的C提交中击败了96.23% 的用户
内存消耗 : 10.1 MB, 在Reverse Nodes in k-Group的C
提交中击败了53.04% 的用户

// Definition for singly-linked list.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(head == NULL) return NULL;
vector<ListNode*> arr;
while(head != NULL){
arr.push_back(head);
head = head->next;
}
if(arr.size() < k)
return arr.front();
for(int i = 0; i <= arr.size()-k; i += k)
for(int j = 0; j < k/2; j++)
swap(arr[i+j], arr[i+k-j-1]);
for(size_t i = 0; i < arr.size()-1; i++){
arr[i]->next = arr[i+1];
}
arr.back()->next = NULL;
return arr.front();
}
}