题目4 和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

题目解析

我们知道,两个数字,距离越远,乘积越小,距离越近乘积越大。所以我们可以设置两个指针,一个指向开头,一个指向末尾,然后他们不断移动,同时相加看是不是等于所制定的值。移动的条件是:

  1. 若和大于指定值,则将右指针左移;
  2. 若和小于指定值,则将左指针右移;
  3. 若到最后左指针和有指针位于一个位置,那么直接返回。

代码

题目5 左旋转字符串

题目描述

汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

题目解析

这里我们可以使用一个C++里面的函数:

解释如下:
- pos:要复制的第一个字符作为子字符串的位置。 如果这等于字符串长度,则该函数返回一个空字符串;如果这大于字符串长度,则抛出out_of_range
- len:要包含在子字符串中的字符数。若为npos,代表所有的字符。

该函数返回一个string类型的对象。

这个函数的意思是:删除从字符位置pos开始并跨越len个字符的字符串值的部分。

所以我们可以考虑利用substr将所要移动的字符复制出来,放到一个临时的字符串中,然后用erase将这几个字母从原字符串中删除,再将临时字符串加到原来字符串的后面即可。

当然一定不要忘记考虑n若为0或者小于零怎么办。

代码

题目6 不用加减乘除做加法

题目描述

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

题目解析

这个题目就是让我们思考加法的原理。
首先看十进制是如何做的: 5+7=12,三步走
第一步:相加各位的值,不算进位,得到2。
第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。
第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。
同样我们可以用三步走的方式计算二进制值相加: 5-101,7-111
第一步:相加各位的值,不算进位,得到010,二进制每位相加就相当于各位做异或操作,101^111。
第二步:计算进位值,得到1010,相当于各位做与操作得到101,再向左移一位得到1010,(101&111)<<1。
第三步重复上述两步, 各位相加 010^1010=1000,进位值为100=(010&1010)<<1。
继续重复上述两步:1000^100 = 1100,进位值为0,跳出循环,1100为最终结果。

代码

题目7 二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

题目解析

三种情况:

  1. 是该点若有右子树,则继续往右子树中序遍历;
  2. 是该点无右子树,且是父节点的左孩子,则下一节点就是其父节点;
  3. 是该点无右子树,且是父节点的右孩子,则寻找其父节点的父节点的父节点的……,直到当前节点是寻找到的那个点的左孩子为止。

所以总体来说是四种情况(除以上三种,还有二叉树为空的情况)

代码