「生活可以更简单, 欢迎来到我的开源世界」
  1. JZ1:二维数组中查找
  2. JZ2:替换空格
  3. JZ3从尾到头打印链表
  4. JZ4 重建二叉树
  5. JZ5用两个栈实现队列
  6. JZ6旋转数组的最小数字
  7. JZ7斐波那契数列
  8. JZ48 不用加减乘除做加法
  9. JZ
  10. JZ
  11. JZ
  12. JZ
  13. JZ
  14. JZ
  15. JZ
  16. JZ
  17. JZ
  18. JZ
  19. JZ
  20. JZ
  21. JZ
  22. JZ
  23. JZ
  24. JZ
  25. JZ
  26. JZ
  27. JZ
  28. JZ
  29. JZ
  30. JZ``JZ
  31. JZ
  32. JZ
  33. JZ
  34. JZ
  35. JZ
牛客网-剑指offer算法专栏
2020-07-09
C++
」 「

对算法题的一些记录。

JZ1:二维数组中查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int row = array.size();
int col = array[0].size();
int m = row-1, n = 0;
while(m>=0 && n < col){
if(target == array[m][n])return true;
else if(target > array[m][n])++n;
else --m;
}
return false;
}
};

循环判断的条件不使用无符号类型

JZ2:替换空格

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

/*
问题1:替换字符串,是在原来的字符串上做替换,还是新开辟一个字符串做替换!
问题2:在当前字符串替换,怎么替换才更有效率(不考虑java里现有的replace方法)。
``从前往后替换,后面的字符要不断往后移动,要多次移动,所以效率低下
``从后往前,先计算需要多少空间,然后从后往前移动,则每个字符只为移动一次,这样效率更高一点。
*/
class Solution {
public:
void replaceSpace(char *str,int length) {
int count=0;
for(int i=0;i<length;i++){
if(str[i]==' ')
count++;
}
for(int i=length-1;i>=0;i--){
if(str[i]!=' '){
str[i+2*count]=str[i];
}
else{
count--;
str[i+2*count]='%';
str[i+2*count+1]='2';
str[i+2*count+2]='0';
}
}
}
};

JZ3从尾到头打印链表

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

思路1:利用栈先入后出的特性完成
思路2:保存数组,数组翻转
思路3:递归
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> temp;
while(head != NULL){
temp.push(head->val);
head = head -> next;
}
vector<int> a;
while(!temp.empty()){
a.push_back(temp.top());
temp.pop();
}
return a;
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> a;
while(head != NULL){
a.push_back(head->val);
head = head -> next;
}
reverse(a.begin(), a.end());
return a;
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> a;
if(head != NULL){
a.insert(a.begin(), head->val);
if(head -> next != NULL){
vector<int> b = printListFromTailToHead(head -> next);
if(!b.empty())a.insert(a.begin(), b.begin(), b.end());
}
}
return a;
}
};

JZ4 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

思路:因为是树的结构,一般都是用递归来实现。

用数学归纳法的思想就是,假设最后一步,就是root的左右子树都已经重建好了,那么我只要考虑将root的左右子树安上去即可。

根据前序遍历的性质,第一个元素必然就是root,那么下面的工作就是如何确定root的左右子树的范围。

根据中序遍历的性质,root元素前面都是root的左子树,后面都是root的右子树。那么我们只要找到中序遍历中root的位置,就可以确定好左右子树的范围。

正如上面所说,只需要将确定的左右子树安到root上即可。递归要注意出口,假设最后只有一个元素了,那么就要返回。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
int vinlen = vin.size();
if(!vinlen)return nullptr;
TreeNode *root = new TreeNode(pre[0]);
if(vinlen == 1)return root;
int gen = 0;
for(int i=0; i< vinlen; i++){
if(pre[0] == vin[i]){
gen = i;
break;
}
}
vector<int> pre_l, pre_r, vin_l, vin_r;
for(int i = 0; i < gen; i++){
vin_l.push_back(vin[i]);
pre_l.push_back(pre[i+1]);
}
for(int i = gen+1; i < vinlen; i++){
vin_r.push_back(vin[i]);
pre_r.push_back(pre[i]);
}
root -> left = reConstructBinaryTree(pre_l, vin_l);
root -> right = reConstructBinaryTree(pre_r, vin_r);
return root;
}
};

JZ5用两个栈实现队列

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

用两个栈实现一个队列的功能:

入队:将元素进栈A
出队:
判断栈B是否为空,如果不为空,栈B直接出栈。
如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;

用两个队列实现一个栈的功能:

入栈:将元素进队列A
出栈:判断队列A中元素的个数是否为1,如果等于1,则出队列,
否则将队列A中的元素出队列,并放入队列B,直到队列A中的元素留下一个,然后队列A出队列,再把队列B中的元素出队列以此放入队列A中。
class Solution
{
public:
void push(int node) {
stack1.push(node);
}

int pop() {
int res = 0;
if(!stack2.empty()){
res = stack2.top();
stack2.pop();
}
else{
while(stack1.size()){
int temp = stack1.top();
stack1.pop();
stack2.push(temp);
}
res = stack2.top();
stack2.pop();
}
return res;
}

private:
stack<int> stack1;
stack<int> stack2;
};

JZ6旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

 思路:

(1)我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则,第一个元素应该是大于最后一个元素的(没有重复的元素)。

但是如果不是旋转,第一个元素肯定小于最后一个元素。

(2)找到数组的中间元素。

中间元素大于第一个元素,则中间元素位于前面的递增子数组,此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素。

移动之后,第一个指针仍然位于前面的递增数组中。

中间元素小于第一个元素,则中间元素位于后面的递增子数组,此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。

移动之后,第二个指针仍然位于后面的递增数组中。

这样可以缩小寻找的范围。

(3)按照以上思路,第一个指针left总是指向前面递增数组的元素,第二个指针right总是指向后面递增的数组元素。

最终第一个指针将指向前面数组的最后一个元素,第二个指针指向后面数组中的第一个元素。

也就是说他们将指向两个相邻的元素,而第二个指针指向的刚好是最小的元素,这就是循环的结束条件。
//C++ 二分法
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.empty()) return 0;
int left = 0, right = rotateArray.size() - 1;
while (left < right) {
//确认子数组是否是类似1,1,2,4,5,..,7的非递减数组
if (rotateArray[left] < rotateArray[right]) return rotateArray[left];

int mid = left + (right - left) / 2;
//如果左半数组为有序数组
if (rotateArray[left] < rotateArray[mid])
left = mid + 1;
//如果右半数组为有序数组
else if (rotateArray[mid] < rotateArray[right])
right = mid;
//否则,rotateArray[left] >= rotateArray[mid] >= rotateArray[right]
/*
例如: 5 4 3 2 1
应该为rotateArray[left] >= rotateArray[mid] >= rotateArray[right]
所以要++left,而不能是--right。
不然按照你的 rotateArray[left] == rotateArray[mid] == rotateArray[right] 话,--right也可行。
*/
else {
++left;
}
}
return rotateArray[left];
}
};

JZ7斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。

n<=39

思路:
1. 常规算法
2. 动态规划
3. 矩阵快速幂
class Solution {
public:
int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int a = 0,b = 1;
int m = 0;
for(int i = 2;i <= n;i++){
m = a + b;
a = b;
b = m;
}
return m;
}
};
// c++动态规划版 
class Solution {
public:
int Fibonacci(int n) {
int f = 0, g = 1;
while(n-->0) {
g += f; //最后g是算到第n+1个
f = g - f; //通过g,算出第n个,算了第n+1个数,然后倒推
}
return f;
}
};

JZ48 不用加减乘除做加法

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

思路:位运算

1. 两个数异或:相当于每一位相加,而不考虑进位;
2. 两个数相与,并左移一位:相当于求得进位;
3. 将上述两步的结果相加
class Solution {
public:
int Add(int num1, int num2)
{
while(num2){
int temp = num1 ^ num2;
num2 = (num1 & num2) << 1;
num1 = temp;
}
return num1;
}
};

JZ

JZ

JZ

JZ

JZ

JZ

JZ

v

JZ

JZ

JZ

v

v

JZ

JZ

JZ

JZ

JZ

JZ

JZ

JZ

JZ

JZ

JZ

JZ``JZ

JZ

JZ

JZ

JZ

JZ

<⇧>