Divide Two Integers https://leetcode.com/problems/divide-two-integers/
题目要求不用乘法、除法和取模运算符,实现整型除法运算。
既然不能用乘法和除法运算符,那么基本思路就是用减法来代替。不过如果用每次循环减一次被除数这种方式,是肯定会超时的。所以要想办法加速运算。
Solution class Solution { public: int divide(int dividend, int divisor) { long long quotient = 0; int flag = 1; auto dividend1 = (long long)fabs(dividend); auto divisor1 = (long long)fabs(divisor); if(dividend < 0) { flag = -1; } if(divisor < 0) { flag = flag == 1 ? -1 : 1; } std::vector<std::pair<long long, long long> > vec; long long times = 1; while (dividend1 >= divisor1) { vec.emplace_back(divisor1, times); dividend1 -= divisor1; quotient += times; divisor1 += divisor1; times += times; } for (int i = vec.size() - 1; i >= 0; --i) { while(dividend1 >= vec[i].first) { quotient += vec[i].second; dividend1 -= vec[i].first; } } if(flag == -1) { quotient = -quotient; } if(quotient > INT32_MAX) { return INT32_MAX; } else if (quotient < INT32_MIN) { return INT32_MIN; } return quotient; } }; 首先,我们用两个 long long 的 dividend1, divisor1 来把传进来的参数转成绝对值,用 flag 记下符号,去掉负号方便后面的运算。
...
Container With Most Water https://leetcode.com/problems/container-with-most-water/
给定一个整型数组,表示坐标轴上的一组相应长度的垂直于 x 轴的线段,要求找出两条线跟 x 轴围起来的容器,能装最多的水。
这题一开始我想用最暴力的方法做两层循环O(n^2)的解法提交试一下,可惜超时了,果然 Medium 难度的题目不会这么轻松放我过去的。
既然 O(n^2) 的解法没有办法通过,那就要想办法能不能找出 O(n) 的解法,一遍循环弄出来。我绞尽脑汁想了很久,尝试了好几种方案,始终没有办法解决。我最终不得不求助于前人的经验,看到别人的解法之后,顿时觉得豁然开朗。
Solution class Solution { public: int maxArea(vector<int>& height) { int max_area = 0; int area = 0; int i = 0; int j = height.size() - 1; while(i < j) { if(height[i] > height[j]) { area = (j - i) * height[j]; --j; } else { area = (j - i) * height[i]; ++i; } if(area > max_area) { max_area = area; } } return max_area; } }; 其实这个解法的关键是用两个指针,分别从左右两边向中间开始遍历,每次算出当前两个指针所指的线围成的面积,并比较是不是当前最大的记到 max_area 里,然后每次排除较短的一条线段,继续遍历。
...
在游戏服务器端的开发工作中,很多时候我们不得不面对繁琐的日期和日期处理。比如说一个运营活动的开始和结束时间处理,还有一个限时道具的到期时间处理等等。如果恰好程序的开发语言是 C++,并且框架并没有对时间处理进行过合理的封装,那么这项工作看起来就不是那么轻松愉快了。这个时候使用 time_t 类型和 tm 结构体,进行原始的时间和日期的比较和计算,就俨然成了程序员的梦魇。不过好在写 Boost 的前辈们已经帮我们做了复杂的工作,然后封装成了这个date_time 库。用来真是爽歪歪啊~
date_time 概述 在使用 date_time 库之间,我们首先要明确三个基本概念:时间点(Time Point)、时长(Time Duration)、时段(Time Interval)。所谓时间点就是时间轴上的一个特定的点;时长就是两个时间点的差值,不属于时间轴;时段是两个特定时间点之间确定的区间。基本上所有的时间处理都是围绕的这三个概念进行的。这三者可以进行相互运算,例如时间点+时长=时间点,时长+时长=时长等。
处理日期 date_time 库的日期处理基于格里高利历, 支持从 1400-01-01 到 9999-12-31 之间的日期计算。为了使用 date_time 库的日期功能需要包含头文件 <boost/date_time/gregorian/gregorian.hpp>,即:
#include <boost/date_time/gregorian/gregorian.hpp> using namespace boost::gregorian; date date 是 date_time 库处理日期的核心类,以天为单位表示时间点概念。
date d1(2001, 1, 1); //使用数字构造日期 date d2(2000, Jan, 1); //使用英文指定月份 date d3(d1); //date 支持拷贝构造 assert(d1 == d3); //date 支持比较操作 assert(d2 < d1); date 也可以从一个字符串产生:
date d1 = from_string("1999-12-31"); date d2 = from_string("1999/12/31"); date d3 = from_undelimited_string("19991231"); day_clock day_clock 是一个天级别的时钟,它也是一个工厂类,调用它的静态成员函数 local_day() 或 universal_day() 会返回一个当天的时间对象,分别是本地日期和 UTC 日期。
date d1 = day_clock::local_day(); date d2 = day_clock::universal_day(); date_duration 日期长度是一天为单位的时长,基本的日期长度是 date_duration(days)
...