笔试练习

1、完成find函数---在一个二维数组(vector对象)中查找有无一个数字，难点在于我不知道如何获取该二维数组的行数和列数

 1 class Solution {
 2 public:
 3     bool Find(int target, vector<vector<int> > array) {
 4         //用rowCount、colCount分别代表数组的行数和列数
 5         int rowCount = array.size();
 6         int colCount = array[0].size();
 7         /*判断是否比数组最小的值小，或者比最大的值大，这样在数组很大时可以提高效率。
 8           数组长度为0也是合法的，所以为了避免越界加上列长为0的判断*/
 9         if(colCount == 0 || target < array[0][0] || target > array[rowCount-1][colCount-1]){
10             return false;
11         }
12         //当row大等于0且col小于列长colCount时，查找数组中是否有target
13         for(int row = rowCount-1, col = 0; row >= 0 && col < colCount;){
14             if(target == array[row][col]){
15                 return true;
16             }else if(target < array[row][col]){
17                 row--;
18             }else if(target > array[row][col]){
19                 col++;
20             }
21         }
22         return false;
23     }
24 };

View Code

方法二(遍历法):

 1 public class Solution {
 2     public static boolean Find(int target, int [][] array) {
 3         if(array == null || array.length == 0 || array[0].length == 0)
 4             return false;
 5  
 6         int len1 = array.length;
 7         int len2 = array[0].length;
 8         for(int i = 0; i < len1; i++) {
 9             for(int j = 0; j < len2; j++){
10                     if(array[i][j] == target)
11                         return true;
12                 }
13         }   
14         return false;
15     }

暴力破解法

方法三：

 1 链接：https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?answerType=1&f=discussion
 2 来源：牛客网
 3 
 4 public class Solution {
 5     public static boolean Find(int target, int [][] array) {
 6         if(array == null || array.length == 0 || array[0].length == 0)
 7             return false;
 8  
 9         int len1 = array.length;
10         int len2 = array[0].length;
11         for(int i = 0; i < len1; i++) {
12             if(target == array[i][0] || target == array[i][len2 - 1])
13                 return true;
14             else if(target < array[i][0])
15                 return false;
16             else if(target > array[i][len2 - 1])
17                 continue;
18             else {
19                 if(binaryFind(array[i], target))
20                     return true;
21             }
22         }
23  
24         return false;
25     }
26  
27     public static boolean binaryFind(int[] arr, int target) {
28         int l = 0;
29         int r = arr.length - 1;
30         while(l <= r) {
31             int mid = l + (r - l) / 2;
32             if(arr[mid] == target)
33                 return true;
34             else if(arr[mid] > target)
35                 r = mid - 1;
36             else
37                 l = mid + 1;
38         }
39         return false;
40     }
41 }

遍历每行进行二分查找

2、补充：关于C++中vector<vector<int>> A的使用

以下代码包含了如何向A中插入数据和如何获取A矩阵的行数和列数

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using std::vector;
 5 using std::cout;
 6 using std::endl;
 7 
 8 int main()
 9 {
10     vector<vector<int>> A;
11     //若想定义A = [[0,1,2],[3,4]]，有两种方法
12     //方法一：定义vector B分别为[0,1,2]和[3,4]，然后放入vector A。
13     //vector<int> B;
14     //B.push_back(0); 
15     //B.push_back(1);
16     //B.push_back(2);
17     //A.push_back(B);  //将B放入A中
18 
19     //B.clear();  //清除B中的元素
20     //B.push_back(3);
21     //B.push_back(4);
22     //A.push_back(B);  //将B放入A中
23 
24     //方法二
25     for (int i = 0; i < 2; ++i)  A.push_back(vector<int>());  //相当于告诉编译器有两行(或分配两个vector对象的空间)
26     A[0].push_back(0);
27     A[0].push_back(1);
28     A[0].push_back(2);
29     A[1].push_back(3);
30     A[1].push_back(4);
31 
32     int rowCount = A.size();  //获取A的行数
33     for (int i = 0; i < rowCount; i++)
34     {
35         for (int j = 0; j < A[i].size(); j++)  //A[i].size()为获取第i行的列数
36             cout << A[i][j] << "	";
37         cout << endl;
38     }
39 
40 
41     system("pause");
42     return 0;
43 }

View Code

执行结果：

3、替换空格为其他字符题

假如char* str = "we are happy"; 那么需要将两个空格都替换为%20,因为本身空格就占一个字符了，而一个空格需要增加三个字符，所以一个空格增加另个字符即可

计算出str中所有的空格数count，需要增加的字符数即：2*coumt;

加入要将空格替换为%200，需要增加的字符数即：(4-1)*count; %200一共占4个字符，减去空格本身的就占的一个字符

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using std::vector;
 5 using std::cout;
 6 using std::endl;
 7 using std::cin;
 8 
 9 void replaceSpace(char* str, int length);
10 
11 int main()
12 {
13     char str[100];
14     //str[99] = '';  //不用添加，添加之后会导致最后报错
15     cout << "请输入一个字符串: ";
16     cin.getline(str, 99);
17     replaceSpace(str, sizeof(str));
18     cout << str << endl;
19 
20 
21     system("pause");
22     return 0;
23 }
24 
25 void replaceSpace(char* str, int length)
26 {
27     int count = 0;
28     int i;
29     for (i = 0; i < length; i++)
30         if (str[i] == ' ')
31             count++;
32     for (i = length - 1; i >= 0; i--)
33     {
34         if (str[i] != ' ')
35             str[i + 2 * count] = str[i];
36         else
37         {
38             count--;
39             str[i + 2 * count] = '%';
40             str[i + 2 * count + 1] = '2';
41             str[i + 2 * count + 2] = '0';
42         }
43     }
44 }

vs运行

注意：getline()函数会将最后键盘输入的换行符替换为，故不需要自己手动给char str[]数组添加空字符！！

运行结果：

如果想要将空格替换为%200, 那么只需要将上述代码中的所有2*count替换为3*count即可

4、将字符串或数组元素反转(使用reverse()函数)

01)使用reverse()函数方法

 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> printListFromTailToHead(ListNode* head) {
13         vector<int> A;
14         while (head) {
15             A.push_back(head->val);
16             head = head->next;
17         }
18         reverse(A.begin(), A.end());
19         return A;
20     }
21 };

使用reverse()将数组反转

02)使用栈

 1 public ArrayList printListFromTailToHead(ListNode listNode) {
 2     ArrayList list = new ArrayList();
 3     stack<int> mystack;  //stack需要包含头文件#include <stack>
 4     while (listNode != null) {
 5         mystack.push(listNode.val);
 6         listNode = listNode.next;
 7     }
 8     while (!mystack.empty()) {
 9         list.add(mystack.pop());
10     }
11     return list;
12 }

View Code

栈容器用法介绍：https://blog.csdn.net/lyj2014211626/article/details/66967761

03)递归方法

 1 public class Solution {
 2     ArrayList list = new ArrayList();
 3     public ArrayList printListFromTailToHead(ListNode listNode) {
 4         if(listNode!=null){
 5             printListFromTailToHead(listNode.next);
 6             list.add(listNode.val);
 7         }
 8         return list;
 9     }
10 }

View Code

递归调用笔记：https://www.cnblogs.com/YiYA-blog/p/10525031.html#m7

c++中字符串反转的3种方法:https://blog.csdn.net/Szu_AKer/article/details/52422191

5、旋转数组查找最小值

01)不需要主函数版本

 1 class Solution {
 2 public:
 3     int minNumberInRotateArray(vector<int> rotateArray) {
 4         if(rotateArray.empty())
 5             return 0;
 6         for(int i=0; i<rotateArray.size()-1;i++)
 7         {
 8             if(rotateArray[i]>rotateArray[i+1])
 9                 return rotateArray[i+1];
10         }
11         return rotateArray[0];
12     }
13 };

View Code

02)需要主函数，并且要写上输入输出(小米笔试题)

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using std::vector;
 5 using std::cin;
 6 using std::cout;
 7 using std::endl;
 8 
 9 int find(vector<int> vec)
10 {
11     if (vec.size() == 0)
12         return 0;
13     for (int i = 0; i < vec.size() - 1; i++)
14     {
15         if (vec[i] > vec[i + 1])
16             return vec[i + 1];
17     }
18     return vec[0];
19 }
20 
21 int main()
22 {
23     vector<int> vec;
24     int n;
25     int Min = 0;
26     while (cin >> n)
27         vec.push_back(n);
28     Min = find(vec);
29     cout << Min << endl;
30 
31     system("pause");
32     return 0;
33 }

View Code

做了第二遍（2019.10.29）：

6、指针练习（选择题）

 1 int main()
 2 {
 3          int c[] = { 2,3,4,5 };
 4     int j, *p = c, *q = c;
 5     for (j = 0; j < 4; j++)
 6     {
 7         printf(" %d", *c);    //打印2 2 2 2
 8         ++q;
 9     }
10     for (j = 0; j < 4; j++)
11     {
12         printf(" %d", *p);  //打印2 3 4 5
13         ++p;
14     }  
15 }

运行结果：

7、数组的简单操作(使用vector将一个数组中的奇数和偶数分开)

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using std::cin;
 5 using std::cout;
 6 using std::vector;
 7 
 8 int main()
 9 {
10     vector<int> num;
11     vector<int> num2;
12     int n,m;
13     while(cin>>n)
14         num.push_back(n);
15     m = num.size();
16     for(int i=0;i<m;i++)
17     {
18         if(num[i]%2 == 0)
19             num2.push_back(num[i]);
20     }
21     for(int i=0;i<m;i++)
22     {
23         if(num[i]%2 == 1)
24             num2.push_back(num[i]);
25     }
26     for(int i=0;i<m;i++)
27         cout<<num2[i]<<" ";
28 }

View Code

8、回文数组

题目描述

对于一个给定的正整数组成的数组 a[] ，如果将 a 倒序后数字的排列与 a 完全相同，我们称这个数组为“回文”的。

例如， [1, 2, 3, 2, 1] 的倒序是他自己，所以是一个回文的数组；而 [1, 2, 3, 1, 2] 的倒序是 [2, 1, 3, 2, 1] ，所以不是一个回文的数组。

对于任意一个正整数数组，如果我们向其中某些特定的位置插入一些正整数，那么我们总是能构造出一个回文的数组。

输入一个正整数组成的数组，要求你插入一些数字，使其变为回文的数组，且数组中所有数字的和尽可能小。输出这个插入后数组中元素的和。

例如，对于数组 [1, 2, 3, 1, 2] 我们可以插入两个 1 将其变为回文的数组 [1, 2, 1, 3, 1, 2, 1] ，这种变换方式数组的总和最小，为 11 ，所以输出为 11 。

1 输入描述:
2 输入数据由两行组成： 第一行包含一个正整数 L ，表示数组 a 的长度。 第二行包含 L 个正整数，表示数组 a 。  对于 40% 的数据： 1 < L <= 100 达成条件时需要插入的数字数量不多于 2 个。  对于 100% 的数据： 1 < L <= 1,000 0 < a[i] <= 1,000,000 达成条件时需要插入的数字数量没有限制。
3 输出描述:
4 输出一个整数，表示通过插入若干个正整数使数组 a 回文后，数组 a 的数字和的最小值。

输入输出描述

题目连接：https://www.nowcoder.com/practice/00fccaa8e30d414ab86b9bb229bd8e68

9、斐波那契数列基本实现与优化

斐波那契数列：从第三项开始，每一项等于前两项之和，如：1 1 2 3 5 8 13 21 34...

递推关系为：f(n) = f(n-1) + f(n-2)

一、基本实现方法

 1 /*
 2 01)斐波那契数列：从第三项开始，每一项等于前两项之和，如：1 1 2 3 5 8 13 21 34...
 3 02)使用递归方法实现
 4 */
 5 #include "iostream"
 6 
 7 using namespace std;
 8 
 9 int fibon(int n);
10 
11 int main()
12 {
13     cout << "请输入斐波那契数列的项数: ";
14     int n, Result;
15     cin >> n;
16     Result = fibon(n);
17     cout << n << "项斐波那契数列，第" << n << "个值为: " << Result << endl;
18 
19     system("pause");
20     return 0;
21 }
22 
23 int fibon(int n)
24 {
25     if (n == 1)
26         n = 1;
27     else if (n == 2)
28         n = 1;
29     else
30         n = fibon(n - 1) + fibon(n - 2);
31     return n;
32 }

View Code

运行结果：

二、斐波那契数列的优化

 1 #include "iostream"
 2 
 3 using namespace std;
 4 
 5 int fibon(int first,int second,int n);
 6 
 7 int main()
 8 {
 9     cout << "请输入斐波那契数列的项数: ";
10     int first = 1;  //数列第一项
11     int second = 1;  //数列第二项
12     int n, Result;
13     cin >> n;
14     Result = fibon(first, second, n);
15     cout << n << "项斐波那契数列，第" << n << "个值为: " << Result << endl;
16 
17     system("pause");
18     return 0;
19 }
20 
21 int fibon(int a, int b, int n)
22 {
23     if (n > 2)
24         return fibon(a + b, a, n - 1);
25     return a;
26 }

优化方法实现斐波那契数列

运行结果：

参考博客：https://blog.csdn.net/qq_35256722/article/details/52728739

数组实现斐波那契数列

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         int *array = new int[40];
 5         array[0] = 0;
 6         array[1] = 1;
 7         for(int i=2;i<=n;i++)
 8             array[i]=array[i-1]+array[i-2];
 9         return array[n];
10     }
11 };

数组法实现斐波那契数列

10、n级台阶问题：每次只能上一个台阶或上两个台阶，此类问题试剂上就是斐波那契数列问题

第n阶只能是从第n-1阶台阶上来或者是从第n-2阶台阶上来，假如上n阶台阶有f(n)种方法，那么f(n) = f(n-1) + f(n-2)，即斐波那契数列问题

实现代码和斐波那契数列实现方法是一样的。

参考博客：https://blog.csdn.net/zhang__shuang_/article/details/86768352

11、删除相同的字符串，string变量是不能像数组那样赋值的！！！

题目网址：https://www.nowcoder.com/practice/f0db4c36573d459cae44ac90b90c6212

一、错误的实：使用了string变量str1和str3赋值，str3[k++]= str1[i]，这样做的话，str3始终只有一个值　请参考本文博客遇到的坑（1）

 1 #include "iostream"
 2 #include "string"
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     string str1,str2,str3;
 9     getline(cin,str1);  //输入第一个字符串
10     getline(cin,str2);  //输入第二个字符串
11     int k=0;
12     for(int i=0;i<str1.size();i++)
13     {
14         for(int j=0;j<str2.size();j++)
15         {
16             if(str1[i] == str2[j])
17                 str3[k++] = str1[i+1];  //string变量不能像数组那样直接赋值，这样str3只有一个值
18             else
19                 str3[k++] = str1[i];
20         }
21     }
22     for(int i=0;i<str3.size();i++)
23         cout<<str3[i];
24     return 0;
25 }

错误的实例(自己写的)

二、使用string类中的find()方法和erase()方法

（1）string类中的find()方法

string::npos是字符串可储存的最大字符数，通常是无符号int或无符号long的最大取值。

（2）string类中的erease()方法

erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
erase(position); 删除position处的一个字符(position是个string类型的迭代器)
erase(first,last);删除从first到last之间的字符（first和last都是迭代器）

以上参考博客：https://blog.csdn.net/qq_42376204/article/details/88955774

https://blog.csdn.net/shujh_sysu/article/details/52026108

正确可以实现的代码：

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4  
 5 int main()
 6 {
 7     string s1, s2;
 8     getline(cin, s1);
 9     getline(cin, s2);
10     for (int i = 0; i < s2.size(); i++)
11     {
12         int index;
13         while((index=s1.find(s2[i]))!=-1) //在s1中开始的位置查找有没有字符s2[i],若有则返回s2[i]在s1中首次出现的位置，否则返回-1
14         {
15             s1.erase(index, 1); //删除s1中从index开始的1个字符
16         }
17     }
18     cout << s1 << endl;
19     return 0;
20 }

使用find()和erease()方法实现

12、使用两个栈实现一个队列

(1)首先要了解的是列的特性是先进先出，栈的特性是先进后出；

(2)在进队列的方法里我们只要有容器能装元素就行了，所以直接往栈1里压；

(3)在出队列方法里，要保证出队列的是最先进入的元素：

最直观的想法就是把栈1的元素挨个出栈，然后往栈2里压。

(4)但是还是要思考一下真的这么简单吗？不是的，栈2为空时才允许栈1往外弹元素并压到栈2里。

如果随时都可以往栈2里压，那么往栈1里压两个元素5、6（栈1状态是：{5,6}），马上出栈往栈2里压（栈2状态：{6,5}）；
接着栈1又来了个元素7，栈2的元素5、6还没出栈，此时要是再把7压到栈2那么栈顶元素就变7了，没法先取出5；
所以在往栈2压完一批元素后，栈1进了新的元素想往栈2压的时候，栈2必须把上一批的元素清空了才行(也就是栈2必须是空的)。

题目中的代码实现：

 1 class Solution
 2 {
 3 public:
 4     void push(int node) {
 5         stack1.push(node);
 6     }
 7 
 8     int pop() {
 9         if(stack2.empty())
10         {
11             while(!stack1.empty())
12             {
13                 stack2.push(stack1.top());
14                 stack1.pop();
15             }
16         }
17         int num = stack2.top();
18         stack2.pop();
19         return num;
20     }
21 
22 private:
23     stack<int> stack1;
24     stack<int> stack2;
25 };

View Code

原题网址

13、已排序好的队列移动几个数字，求移动数字的个数(队列最小修改)

题目描述

已知一个奇怪的队列，这个队列中有n个数，初始状态时，顺序是1,2,3,4,…n，是1-n按顺序排列。这个队列只支持一种操作，就是把队列中的第i号元素提前到队首(1<i<=n)，如有4个元素，初始为1，2，3，4,可以将3提前到队首，得到3，1，2，4 。现在给出一个经过若干次操作之后的序列，请你找出这个序列至少是由原序列操作了多少次得到的。

输入描述:

第一行是一个整数n(1<=n<=10^5)，表示序列中数字的数量。接下来一行有n个数，是1-n的一个全排列。数字之间用空格隔开。

输出描述:

输出仅包含一个数字，表示至少操作了几次

解析：

1 输入：
2 5
3 5 2 1 3 4
4 输出：
5 2

输入输出实例

代码：

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 vector<int> array;
 6 int main()
 7 {
 8     int n,num;
 9     int count=0;
10     cin>>n;
11     for(int i=0;i<n;i++)
12     {
13         cin>>num;
14         array.push_back(num);
15     }
16     int res = n-1;  //最多移动n-1次,比如输入5个数字:3 4 5 2 1可以用1 2 3 4 5经过4次移动得到
17     for(int i=n-1;i>0;i--)
18     {
19         if((array[i] > array[i-1])) //没有平移过的肯定是排序好了的
20             res--;
21         else
22             break;      //出现一个array[i] < array[i-1]则退出for循环
23     }
24     cout<<res<<endl;
25     
26     return 0;
27 }

View Code

原题链接

15、字符反转(使用reverse()函数)

题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

reverse函数功能是逆序（或反转），多用于字符串、数组、容器。头文件是#include <algorithm>

reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数无返回值

1 string str="hello world , hi";
2 reverse(str.begin(),str.end());//str结果为 ih , dlrow olleh
3 vector<int> v = {5,4,3,2,1};
4 reverse(v.begin(),v.end());//容器v的值变为1,2,3,4,5

1 string str = "student. a am I";
2 reverse(str.begin(), str.begin() + 2);  //只反转前两个字符,即只反转[0,2)内的字符,不包括2指向的字符
3 cout << str << endl;                    //打印tsudent. a am I

代码如下(两次反转字符串)：

 1 #include<iostream>
 2 #include<string>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 class Solution {
 8 public:
 9     string ReverseSentence(string str) {
10         int len = str.size();
11         int start = 0;
12         for (int i = 0; i < len; i++)
13         {
14             if (str[i] == ' ')
15             {
16                 reverse(str.begin() + start, str.begin() + i);  //遇到第一个空格时,start=0,i=8,反转区间[0,8)区间内的字符,将student.反转为.tneduts a am I
17                 start = i + 1;                                  //遇到第二个空格时,start=9,i=10,反转区间[9,10)区间内的字符,将a反转为a,此时str变为.tneduts a am I
18             }                                                   //遇到第三个空格时,start=11,i=13,反转区间[11,13)区间内的字符,将a反转为a,此时str变为.tneduts a ma I
19             if (i == len - 1)                                   //后start=14，i=14，进入下一个if循环
20             {
21                 reverse(str.begin() + start, str.end());  //反转最后一个空格后的其余字符，此时str变为.tneduts a ma I
22             }
23         }
24         reverse(str.begin(), str.end());  //此时str变为I am a students.
25         return str;
26     }
27 };
28 int main()
29 {
30 
31     Solution so;
32     string str = "student. a am I";
33 
34     string s = so.ReverseSentence(str);
35     cout << s << endl;
36 
37     cout << endl;
38     system("pause");
39     return 0;
40 }

View Code

16、二叉树深度相关

(1)二叉树最小深度

题目描述

求给定二叉树的最小深度。最小深度是指树的根结点到最近叶子结点的最短路径上结点的数量。

 1 class Solution {
 2 public:
 3     int run(TreeNode *root) {
 4         if(root==NULL)          
 5             return 0;
 6         if(root->left==NULL)               //root结点没有左子数，那就要去找右子树的最小深度
 7             return run(root->right)+1;     //加1的目的是为了加上根结点的那层深度
 8         if(root->right==NULL)              //root结点没有右子数，那就要去找右子树的最小深度
 9             return run(root->left)+1;
10         int depthLeft=run(root->left);     //如果root结点左右两个子树都存在，那么就找左右子树的最小值
11         int depthRight=run(root->right);
12         return (depthLeft>depthRight)?(depthRight+1):(depthLeft+1);
13     }
14 };

View Code

leetcode题目链接

牛客网题目链接

(2)二叉树最大深度或者是二叉树深度

二叉树最大深度即二叉树深度

牛客网二叉树深度题目描述: 网址链接

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

leetcode二叉树最大深度题目描述: 网址链接

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     int TreeDepth(TreeNode* pRoot)
13     {
14         int leftDepth=0;
15         int rightDepth=0;
16         if(pRoot==NULL)
17             return 0;
18         leftDepth=TreeDepth(pRoot->left);
19         rightDepth=TreeDepth(pRoot->right);
20         return (leftDepth>rightDepth)?leftDepth+1:rightDepth+1;
21     }
22 };

二叉树深度和二叉树最大深度代码

(3)判断一棵树是否为平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isBalanced(TreeNode* root) {
13         return depthTree(root)!=-1;
14 
15     }
16     int depthTree(TreeNode* root){
17         int leftDepth=0;
18         int rightDepth=0;
19         if(root==NULL)
20             return 0;
21         leftDepth=depthTree(root->left);
22         rightDepth=depthTree(root->right);
23         //在求二叉树最大深度中直接执行的是else中的语句,判断是否为平衡二叉树加了if中的语句
24         if(leftDepth==-1 || rightDepth==-1 || abs(leftDepth-rightDepth)>1)
25             return -1;
26         else
27             return (leftDepth>rightDepth)?leftDepth+1:rightDepth+1;
28     }
29 };

判断二叉树是否为平衡二叉树

leetcode题目链接

牛客网题目链接

if(a == -1  || b == -1 || abs(a-b) > 1)
     return -1;
 //根据定义，左子树不是AVLTree或右子树不是AVLTree或自己本身就算不是AVLTree

17、十六进制字符串转换为十进制，并求连续的十六进制最大值

题目：

给定一个包含大写英文字母和数字的句子，找出这个句子所包含的最大的十六进制整数，返回这个整数的值。数据保证该整数在int表示范围内

网址：https://www.nowcoder.com/practice/ac72e27f34c94856bf62b19f949b8f36?tpId=110&tqId=33455&rp=1&ru=/activity/oj&qru=/ta/job-code/question-ranking

方法：

代码实现：

 1 class Solution {
 2 public:
 3     /**
 4      * 
 5      * @param s string字符串 
 6      * @return int整型
 7      */
 8     //将十六进制字符串转换为十进制
 9     int HexToDecimal(string s)
10     {
11         int temp=0;
12         for(int i=0;i<s.length();i++)
13         {
14             temp=temp*16;      //比如比如字符串123转换为十进制:1*10=10；10+2=12；12*10=120；120+3=123
15             if(s[i]>='0' && s[i]<='9')
16                 temp=temp+s[i]-'0'+0;
17             else if(s[i]>='a' && s[i]<='f')
18                 temp=temp+s[i]-'a'+10;
19             else if(s[i]>='A' && s[i]<='F')
20                 temp=temp+s[i]-'A'+10;
21             //temp=temp*16;  //这一句放在这里就不对！！！！！
22         }
23         return temp;
24     }
25     
26     int solve(string s)
27     {
28         string Hex_string;
29         int value_decimal=0;
30         for(int i=0;i<s.length();i++)
31         {
32             //如果s[i]是十六进制字符集中的一个，则将s[i]临时存储在Hex_string中，直到遇到一个不是十六进制字符集的s[i]              i]
33             //在遇到不是十六进制字符集里面的s[i]之前，Hex_string一定是连续的
34             if((s[i]>='0' && s[i]<='9') ||(s[i]>='a' && s[i]<='f') || (s[i]>='A' && s[i]<='F'))
35                 Hex_string=Hex_string+s[i];  
36             else
37             {
38                 if (i != 0 && ((s[i - 1] >= '0' && s[i - 1] <= '9') || (s[i - 1] >= 'A' && s[i - 1] <= 'F')))
39                     value_decimal = max(value_decimal,HexToDecimal(Hex_string));
40                 Hex_string.clear();
41             }
42         }
43         return value_decimal;
44     }
45 };

View Code

 1 class Solution {
 2 public:
 3     /**
 4      * 
 5      * @param s string字符串 
 6      * @return int整型
 7      */
 8     //将十六进制字符串转换为十进制
 9     int HexToDecimal(string s)
10     {
11         int temp=0;
12         for(int i=0;i<s.length();i++)
13         {
14             temp=temp*16;      //比如比如字符串123转换为十进制:1*10=10；10+2=12；12*10=120；120+3=123
15             if(s[i]>='0' && s[i]<='9')
16                 temp=temp+s[i]-'0'+0;
17             else if(s[i]>='a' && s[i]<='f')
18                 temp=temp+s[i]-'a'+10;
19             else if(s[i]>='A' && s[i]<='F')
20                 temp=temp+s[i]-'A'+10;
21             //temp=temp*16;  //这一句放在这里就不对！！！！！
22         }
23         return temp;
24     }
25     
26     int solve(string s)
27     {
28         string Hex_string;
29         int value_decimal=0;
30         for(int i=0;i<s.length();i++)
31         {
32             //如果s[i]是十六进制字符集中的一个，则将s[i]临时存储在Hex_string中，直到遇到一个不是十六进制字符集的s[i]              i]
33             //在遇到不是十六进制字符集里面的s[i]之前，Hex_string一定是连续的
34             if((s[i]>='0' && s[i]<='9') ||(s[i]>='a' && s[i]<='f') || (s[i]>='A' && s[i]<='F'))
35                 Hex_string=Hex_string+s[i];  
36             else
37             {
38                //这里不加这个if判断也是可以得
39                 if (i != 0 && ((s[i - 1] >= '0' && s[i - 1] <= '9') || (s[i - 1] >= 'A' && s[i - 1] <= 'F')))
40                     value_decimal = max(value_decimal,HexToDecimal(Hex_string));
41                 Hex_string.clear();
42             }
43         }
44         return value_decimal;
45     }
46 };

上面的代码也可以去掉一个if

(1)十六进制转换为十进制方法二(使用cmath头文件中的pow()函数)

 1 #include <iostream>
 2 #include <string>
 3 #include <cmath>
 4 
 5 using namespace std;
 6 
 7 void hexToDecimal(string s)
 8 {
 9     int value=0,bit=0;
10     for(int i=s.size()-1;i>1;--i)
11     {
12         if(s[i]>='0' && s[i]<='9')
13             value+=(s[i]-'0')*pow(16,bit++);
14         else if(s[i]>='a' && s[i]<='f')
15             value+=(s[i]-'a'+10)*pow(16,bit++);
16         else if(s[i]>='A' && s[i]<='F')
17             value+=(s[i]-'A'+10)*pow(16,bit++);
18     }
19     cout<<value<<endl;
20 }
21 
22 int main()
23 {
24     string s;
25     while(cin>>s)
26     {
27         hexToDecimal(s);
28     }
29     return 0;
30 }

View Code

18、环形路上有n个加油站

题目描述

环形路上有n个加油站，第i个加油站的汽油量是gas[i].

你有一辆车，车的油箱可以无限装汽油。从加油站i走到下一个加油站（i+1）花费的油量是cost[i]，你从一个加油站出发，刚开始的时候油箱里面没有汽油。

求从哪个加油站出发可以在环形路上走一圈。返回加油站的下标，如果没有答案的话返回-1。

注意：

答案保证唯一

题目网址：https://www.nowcoder.com/practice/3b1abd8ba2e54452b6e18b31780b3635?tpId=46&tqId=29046&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

 1 class Solution {
 2 public:
 3     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
 4         int start=gas.size()-1;
 5         int end = 0;
 6         int sum=gas[start]-cost[start];
 7         while(start>end)
 8         {
 9             if(sum>=0)
10             {
11                 sum+=gas[end]-cost[end];
12                 end++;
13             }
14             else
15             {
16                 start--;
17                 sum+=gas[start]-cost[start];
18             }
19         }
20         return sum>=0 ? start:-1;
21     }
22 };

View Code

19、糖果分配问题

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

贪心思想分析：期望是让糖果数目最小，限制就是那两个条件，如果下一个要大，那自然最好的选择就是多给一个糖果最好，所以在这里我们先不考虑其他的，就给他一个糖果就好．这样遍历过去主要是无法处理1,2,3,3,2,1这类数据，那么再逆着遍历贪心就行了（这个比较难想到）

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 //形rank为一组学生的排名
 7 //注意：candy()的返回值不能是vector<int> &
 8 //这是因为candyNumber是一个局部变量,candy()执行完后candyNumber即被销毁,所以无法传引用回主函数
 9 //只能传candyNumber的副本回去
10 //贪心体现在如果rank=[1,2,2]那么糖果分配情况是[1,2,1],即保证如果第i+1个学生比第i个学生排名高,那么第i+1个学生比第i个学生多一个糖果即可
11 //其余就不用考虑了
12 vector<int> candy(vector<int> &rank)
13 {
14     int sum = 0;
15     int len = rank.size();
16     vector<int> candyNumber(len, 1);  //先将每个人得到的糖果初始化为1,即保证每个人都有一个糖果
17 
18     for (int i = 0; i < len-1; i++)
19     {
20         if (rank[i + 1] > rank[i])
21             candyNumber[i + 1] = candyNumber[i] + 1;  //如果第i+1个学生比第i个学生排名高,那么第第i+1个学生比第i个学生的糖果多一个
22     }
23     //以上只是解决了类似1,2,3这样排名的糖果分配问题,但是对于1,2,3,2,1这样的排名并不可以解决糖果分配问题
24     //对于1，2，3，2，1必须使用逆序分配
25     for (int i = len - 1; i > 0; i--)
26     {
27         if (rank[i - 1] > rank[i] && candyNumber[i - 1] <= candyNumber[i])
28             candyNumber[i - 1] = candyNumber[i] + 1;
29     }
30 
31     /*cout << "糖果分配结果
";
32     for (int i = 0; i < candyNumber.size(); i++)
33         cout << candyNumber[i] << " ";
34     cout << endl;*/
35 
36     //将分配好的糖果类加起来
37     /*for (int i = 0; i < len; i++)
38         sum += candyNumber[i];*/
39     return candyNumber;
40 }
41 
42 int main()
43 {
44     //vector<int> rank = { 1,2,3,4,5,4,3,2,1,1 };
45     //vector<int> rank = { 1,0,2};
46     vector<int> rank = { 1,2,2 };
47     vector<int> candyResult(rank.size());
48 
49     cout << "学生排名情况:
";
50     for (int i = 0; i < rank.size(); i++)
51         cout << rank[i] << " ";
52 
53     candyResult = candy(rank);
54 
55     cout << "糖果分配结果
";
56     for (int i = 0; i < candyResult.size(); i++)
57         cout << candyResult[i] << " ";
58     cout << endl;
59 
60     int sum = 0;
61     for (int i = 0; i < candyResult.size(); i++)
62         sum += candyResult[i];
63     cout << "需要糖果的总数为:" << sum << endl;
64 
65     system("pause");
66     return 0;
67 }

糖果分配问题

执行结果：

20、使用map容器查找一个字符串中每个字符出现的次数

方法一、使用map类中的find()函数，如果找到了则让iter->second++

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     string str;
10     getline(cin, str);
11     map<char, int> strMap;
12     map<char, int>::iterator iter;
13     for (int i = 0; i < str.size(); i++)
14     {
15         iter = strMap.find(str[i]);//在strMap中查找str[i]
16         if (iter != strMap.end())  //如果iter不等于end()，则说明找到了
17             iter->second++;
18         else                       //否则没有找到，将str[i]和1插入到map中去(类似于创建一个新的键和值)
19             strMap.insert(pair<char, int>(str[i], 1));
20     }
21     for (iter = strMap.begin(); iter != strMap.end(); iter++)
22         cout << iter->first << ":" << iter->second << endl;
23 
24 
25     system("pause");
26     return 0;
27 }

方法一

方法二：使用pair判断是否插入成功来计算字符是否插入到了map中

 1 //使用pair判断是否插入成功来计算字符是否插入到了map中
 2 #include <iostream>
 3 #include <map>
 4 #include <string>
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     string str;
11     getline(cin, str);
12     map<char, int> strMap;
13     map<char, int>::iterator iter;
14     pair<map<char, int>::iterator, bool> insertPair;
15     for (int i = 0; i < str.size(); i++)
16     {
17         insertPair = strMap.insert(pair<char, int>(str[i], 1));  //由于insert是不可以插入相同键值的数据的,因此加入str[i]在strMap中出现过,那么插入就不成功
18         //insertPair = strMap.insert(map<char, int>::value_type(str[i], 1));  //使用哪个插入方法都可
19         if (insertPair.second == false)          //表示在strMap中存在键值str[i],且插入不成功。注意这里访问的是insertPair的第二个参数,insertPair.second,只有第二个参数才是bool类型的
20             insertPair.first->second++;          //insertPair的第一个参数为一个map迭代器
21     }
22     for (iter = strMap.begin(); iter != strMap.end(); iter++)
23         cout << iter->first << ":" << iter->second << endl;
24 
25 
26     system("pause");
27     return 0;
28 }

View Code

方法三、直接使用库里提供的[]运算符重载。通过键值找节点，直接给给实值+1.

 1 //直接使用库里提供的[]运算符重载。通过键值找节点，直接给给实值+1.
 2 #include <iostream>
 3 #include <map>
 4 #include <string>
 5 
 6 using namespace std;
 7 
 8 int main()
 9 {
10     string str;
11     getline(cin, str);
12     map<char, int> strMap;
13     map<char, int>::iterator iter;
14     for (int i = 0; i < str.size(); i++)
15     {
16         strMap[str[i]]++;    //类似于数组插入map数据方法,只不过这里的键类型为char，键对应的值类型为int
17     }
18     for (iter = strMap.begin(); iter != strMap.end(); iter++)
19         cout << iter->first << ":" << iter->second << endl;
20 
21 
22     system("pause");
23     return 0;
24 }

方法三

对思路3补充说明：假设一个map对象map_s中只存在一对pair<char,int>('a',1)，现在执行map_s['b']则map_s中存在两对pair分别是('a',1),('b',0)，是的，没错，'b'的value默认是0，那么如果刚才执行的不是map_s['b']，而是map_s['b']++，那么map_s中的两对pair为('a',1)和('b',1),理解为插入‘b’，然后value值++。

所以，map_s['b']++这个语句的理解如下：

如果map_s中不存在key为‘b’的元素，那么在map_s中添加‘b’，value默认为0，然后map_s['b']++,value变成1.

如果map_s中存在key为 'b' 的元素，那么该语句表示map_s['b']的value++.

21、使用map容器找到一个vector<string>中灭个字符串出现的次数

和上面的方法是一样的，不同之处在于：

上面是查找字符串中字符的多少，所以map容器的定义方法为:map<char,int> strMap;

这个是要找到一个vector<string>中相同字符串的多少，所以map容器的定义方法为:map<string,int> strMap;

 1 //直接使用库里提供的[]运算符重载。通过键值找节点，直接给给实值+1.
 2 #include <iostream>
 3 #include <map>
 4 #include <string>
 5 #include <vector>
 6 
 7 using namespace std;
 8 
 9 int main()
10 {
11     int N = 0;
12     vector<string> vecStr;
13     string temp;
14     cin >> N;
15     getchar();  //接收上一句最后输入的换行符
16     for (int i = 0; i < N; i++)
17     {
18         cin >> temp;
19         getchar();
20         vecStr.push_back(temp);
21     }
22 
23     map<string, int> strMap;
24     map<string, int>::iterator iter;
25     for (int i = 0; i < vecStr.size(); i++)
26     {
27         strMap[vecStr[i]]++;    //类似于数组插入map数据方法,只不过这里的键类型为char，键对应的值类型为int
28     }
29     for (iter = strMap.begin(); iter != strMap.end(); iter++)
30         cout << iter->first << ":" << iter->second << endl;
31 
32 
33     system("pause");
34     return 0;
35 }

View Code

22、华为牛客网机试练习

(1)计算字符串最后一个单词的长度

题目描述

计算字符串最后一个单词的长度，单词以空格隔开。

输入描述:

一行字符串，非空，长度小于5000。

输出描述:

整数N，最后一个单词的长度。

思路：使用getline()接收输入，手写split()函数，并以空格分割字符串，在分割的过程中，不断的将字符串入栈，最后取栈顶元素计算字符个数即可。

 1 #include <iostream>
 2 #include <stack>
 3 #include <string>
 4 #include <sstream>
 5 using namespace std;
 6 
 7 void split(const string str, stack<string> & sta,const char flag)
 8 {
 9     string temp;
10     stringstream iss(str);
11     while (getline(iss,temp,flag))
12     {
13         sta.push(temp);
14         temp.clear();
15     }
16 }
17 
18 int main()
19 {
20     stack<string> sta;
21     string temp;
22     getline(cin, temp);
23     split(temp, sta, ' ');
24 
25     cout << sta.top() << endl;
26 
27     temp = sta.top();
28     int count = 0;
29     cout << sta.top().size() << endl;
30 
31 
32 
33     system("pause");
34     return 0;
35 }

代码示例

(2)明明的随机数(多个数字连续输入) 使用set容器，set容器可以自动排序

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

题目地址：https://www.nowcoder.com/questionTerminal/3245215fffb84b7b81285493eae92ff0

 1 #include <iostream>
 2 #include <set>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int N, temp = 0;
 9     set<int> s;
10     while (cin >> N)
11     {
12         s.clear();
13         while (N--)
14         {
15             cin >> temp;
16             getchar();
17             s.insert(temp);  //set容器会自动进行排序,且不会插入容器中已经有的数据
18         }
19         for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
20             cout << *iter << endl;
21     }
22 
23     system("pause");
24     return 0;
25 }

使用set容器实现

结束输入的方法为输入一个非int型数据

(3)求质子数

题目描述

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（如180的质因子为2 2 3 3 5 ）

最后一个数后面也要有空格

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     long num;
 7     cin >> num;
 8     getchar();
 9     while (num != 1)    //输入一个非long型数据结束输入
10     {
11         for (int i = 2; i <= num; i++)
12         {
13             if (num%i == 0)   //如果num对i取余,余数恒等于0则说明i是num的一个质子
14             {
15                 num = num / i;
16                 cout << i << " ";
17                 break;       //跳出for循环,这是因为180的第一个质子为2，第二个质子还是2
18             }
19         }
20     }
21     cout << endl;
22     system("pause");
23     return 0;
24 }

View Code

(4)蛇形矩阵

题目说明

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

解析：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int N;
 7     int temp = 0;
 8     cin >> N;
 9     getchar();
10     for (int i = 1; i <= N; i++)
11     {
12         for (int j = 1; j <= N - (i - 1); j++)
13         {
14             temp = j + i - 1;
15             cout << (temp*temp + temp) / 2 - (i - 1) << " ";
16         }
17         cout << endl;
18     }
19 
20     system("pause");
21     return 0;
22 }

代码实现

(5)提取不重复的数字

https://www.nowcoder.com/practice/253986e66d114d378ae8de2e6c4577c1?tpId=37&tqId=21232&rp=0&ru=/ta/huawei&qru=/ta/huawei/question-ranking

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>  //for memset() 在牛客网中编译必须加上这个头文件
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int num = 0, temp = 0;
 9     //int arr[10] = { -1 };    //创建包含10个数字的数组,并全部初始化为-1  这样不对！！！
10     int arr[10];
11     memset(arr, -1, sizeof(arr));
12     string str;
13     cin >> num;
14     while (num != 0)
15     {
16         temp = num % 10;
17         if (arr[temp] == -1)   //temp第一次出现
18         {
19             arr[temp] = 1;
20             str += to_string(temp);
21         }
22         num = num / 10;
23     }
24     for (int i = 0; i < str.size(); i++)
25         cout << str[i];
26     cout << endl;
27     system("pause");
28     return 0;
29 }

View Code

使用数组来区分该数字到底有没有出现过

(6)合并表记录(使用map,将键相同的对应的值相加)

题目描述

数据表记录包含表索引和数值（int范围的整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照key值升序进行输出。

输入描述:

先输入键值对的个数
然后输入成对的index和value值，以空格隔开

输出描述:

输出合并后的键值对（多行）

跳转到题目

 1 #include <iostream>
 2 #include <map>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     map<int, int> mapNum;
 8     map<int, int>::iterator iter;
 9     pair<map<int, int>::iterator, bool> p;
10     int N = 0, temp1 = 0, temp2 = 0;
11     cin >> N;
12     getchar();
13     for (int i = 0; i < N; i++)
14     {
15         cin >> temp1 >> temp2;
16         getchar();
17         p = mapNum.insert(pair<int, int>(temp1, temp2));
18         if (p.second == false)
19             p.first->second += temp2;
20     }
21     for (iter = mapNum.begin(); iter != mapNum.end(); iter++)
22         cout << iter->first << " " << iter->second << endl;
23     system("pause");
24     return 0;
25 }

View Code

(7)字符个数统计(不包括重复字符),注意字符范围表示方法,使用map容器

题目描述
编写一个函数，计算字符串中含有的不同字符的个数。字符在ACSII码范围内(0~127)，换行表示结束符，不算在字符里。不在范围内的不作统计。

输入描述:
输入N个字符，字符在ACSII码范围内。

输出描述:
输出范围在(0~127)字符的个数。

示例1
输入:
abc
输出：
3

题目地址

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 int main()
 8 {
 9     map<char, int> mapNum;
10     map<char, int>::iterator iter;
11     string str;
12     int value = 0;
13     getline(cin, str);
14     for (int i = 0; i < str.size(); i++)
15     {
16         if (str[i] >= 0 && str[i] <= 127)    //ASCII码范围的表示的表示方法
17             mapNum.insert(pair<char, int>(str[i], 1));
18     }
19     for (iter = mapNum.begin(); iter != mapNum.end(); iter++)
20         value += iter->second;
21     cout << value << endl;
22     cout << 'a' << endl;
23     system("pause");
24     return 0;
25 }

View Code

注：‘0’表示字符0，字符0的ASCII码为48

(8)float型数据十进制转二进制

十进制小数→二进制小数：(1)把十进制小数乘以2，得到积，把积的整数部分提出；(2)再用所得积的小数部分乘以2，得到积，把积的整数部分提出；(3)重复步骤2；(4)乘以2过程中提出的各个整数部分组成转换后的二进制小数。权的确定规则：最先提出的整数是二进制小数的最高位。

看个例子就明白了 :

37.8125(十进制)的运算分为整数部分和小数部分：

整数部分的结果是100101。
小数部分：0.8125＊2=1.6250，将整数部分1提出；0.6250＊2=1.2500，将整数部分1提出；0.2500＊2=0.5000,整数部分为0；0.5000＊2=1.0000,整数部分为1；所以小数部分的结果是0.1101。
所以最后的结果是100101.1101。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 //整数部分十进制转二进制
 5 void printBinaryForInt(int & value)
 6 {
 7     int a[32];  //由于int型数据占4个字节，最多有32位
 8     int i = 0;
 9     while (value != 0)
10     {
11         a[i++] = value % 2;  //先使用i的值，再给i加1；所以最后一次为a中添加数据后i还是要加1的,即i比数组内最大索引值大1
12         value = value / 2;
13     }
14                             //整数部分十进制转二进制需要逆序输出二进制
15     while (i > 0)           //这里不可以加等号，因为最后i=1的时候条件成立,此时已经输出[0]了
16         cout << a[--i];     //由于i比数组内最大索引值大1,所以此处要先对i减1再使用i的值;
17     cout << ".";            //打印小数点
18 }
19 //小数部分十进制转二进制，注意float可以精确到小数点后6个有效数字
20 //一个有效数字可以用0000~1001表示0~9，所以6为有效数字的位数为24位
21 void printBinaryForDecima(float & value)
22 {
23     int a[24];  //float可以精确到24位,6个有效数字
24     int i = 0, temp = 0;
25     while (value < 1)
26     {
27         value = value * 2;
28         a[i++] = int(value);
29         if (value == 1)
30             break;
31         else if (value > 1)
32             value -= 1;
33     }
34     for (int j = 0; j < i; j++)  //小数部分十进制转二进制正序输出二进制即可
35     {
36         cout << a[j];
37     }
38     cout << endl;
39 }
40 
41 //float型数据分为整数部分和小数部分
42 void divideData(float & value)
43 {
44     int temp1 = int(value);  //取出value的整数部分
45     float temp2 = value - float(temp1);  //取出value的小数部分
46     printBinaryForInt(temp1);     //将整数部分十进制转换为二进制
47     printBinaryForDecima(temp2);  //将小数部分十进制转二进制
48 }
49 
50 int main()
51 {
52     float Num;
53     cin >> Num;
54     getchar();
55     divideData(Num);
56 
57     system("pause");
58     return 0;
59 }

C++代码实现

23、剑指offer

(1)一只青蛙一次可以跳1级台阶、2级台阶、3级台阶、...、n级台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解析：

关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:

f(1) = 1

f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3)

...

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

说明：

1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的跳法数。

2）n = 1时，只有1种跳法，f(1) = 1

3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1），f(2) = f(2-1) + f(2-2)

4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，

那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)

因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：

f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

6)所以当n=n-1时候，5)当n=n-1时，f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

7) 由以上已经是一种结论，但是为了简单，我们可以继续简化：

把6)式带入下式：

f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

可以得出：

f(n) = 2*f(n-1)

7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：

| 1 ,(n=0 )

f(n) = | 1 ,(n=1 )

| 2*f(n-1),(n>=2)

 1 class Solution {
 2 public:
 3     int jumpFloorII(int number) {
 4         int value=0;
 5         if(number<=0)
 6             return 0;
 7         if(number==1)
 8             return 1;
 9         value=2*jumpFloorII(number-1);
10         return value;
11 
12     }
13 };

View Code

题目链接

(2)矩形覆盖问题，依旧是斐波那契数列问题

题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

比如n=3时，2*3的矩形块有3种覆盖方法：

解析：

 1 class Solution {
 2 public:
 3     int rectCover(int number) {
 4         int value=0;
 5         if(number==0)
 6             return 0;
 7         if(number==1)
 8             return 1;
 9         if(number==2)
10             return 2;
11         value=rectCover(number-1)+rectCover(number-2);
12         return value;
13 
14     }
15 };

View Code

题目链接

(3)使用位操作计算一个整数二进制包含1的个数(整数包括正整数、负整数和0)

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

测试flag<<1位运算:

 1 #include <iostream>
 2 using namespace std;
 3 int main() {
 4     int flag = 1;
 5     int count = 0;
 6     while (flag) {
 7         count++;
 8         flag = flag << 1;
 9     }
10     cout << count << endl;  //count=32,这是由于使用的是32位编译器,flag占4个字节32位
11     system("pause");
12     return 0;
13 }

View Code

题目代码：

 1 class Solution {
 2 public:
 3      int  NumberOf1(int n) {
 4          int flag=1;
 5          int count=0;
 6          while(flag){
 7              if(n & flag)
 8                  count++;
 9              flag=flag<<1;  //flag是int型数据,占32位,依次让flag的第一位、第二位...第三十二位等于1
10          }
11          return count;
12      }
13 };

View Code

题目链接

(4)pow()函数实现

 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         int p=abs(exponent);
 5         double r=1.0;
 6         while(p){
 7             if(p & 1)  //如果p的二进制第一位含有1即满足条件
 8                r*=base;
 9             base*=base;
10             p=p>>1;   //等价于p=p/2;
11         }
12         return (exponent>0)?r:(1/r);
13     }
14 };

View Code

别人的解析(快速求幂算法)链接

24、笔试

(1)快速幂+取余快速幂即上面的pow()函数实现

本题说是输入由N个字符构成的二进制，且该二进制的位数不超过L，求构成二进制所有可能有多少个，结果对1000000007取余。如N=2，L=3时候，所有二进制为{0，1，00，01，10，11，000，001，010，100，101，110，111}共14种可能，实际上就是求N的L次方，然后累加即可，但是输入的数会很大，因此必须对中间幂结果取余，因此必须自己实现pow()函数。

 1 /*
 2  int数据类型，在32位系统中（现在基本上int都是32位），范围-2147483648~+2147483647
 3  unsigned类型 的int 范围：0~4294967295 即 0~（2的32次方-1）
 4  unsigned long int 与unsigned long是等价的，即定义的时候int可以不写
 5  unsigned long int的取值范围: 0~4294967295 即 0~（2的32次方-1）
 6  long在32位系统中占4个字节,取值范围和int是一样的
 7 */
 8 #include <iostream>
 9 #include <cmath>
10 using namespace std;
11 
12 unsigned long long temp = 1000000007;
13 
14 unsigned long long Pow(int a, int b) {
15     unsigned long long base = 1;
16     while (b != 0) {
17         if (b & 1)
18             base = (base*a) % temp;
19         a = (a%temp*a%temp) % temp;  //bug：a = (a*a) % temp 
20         b = b >> 1;
21     }
22     return base;
23 }
24 
25 int main() {
26     int N = 0;
27     int L = 0;
28     unsigned long long result = 0;
29     cin >> N >> L;
30     getchar();
31     while (N != 0 && L != 0) {
32         for (int i = 1; i <= L; i++) {
33             result += Pow(N, i);
34         }
35         cout << result % temp << endl;
36         result = 0;
37         cin >> N >> L;
38         getchar();
39     }
40 
41     system("pause");
42     return 0;
43 }

代码实现

(2)计算算数表达式字符串中匹配的字符串个数、不匹配的左括号个数、不匹配的右括号个数

如3*2+(3*3)))(((

输出1 3 2 表示左右括号匹配的有1对,不匹配的左括号个数为3个、不匹配的右括号的个数为2个

 1 #include <iostream>
 2 #include <stack>
 3 #include <string>
 4 using namespace std;
 5 
 6 bool isOperator(const char c) {
 7     if (c == '(' || c == ')')
 8         return true;
 9     else
10         return false;
11 }
12 int main() {
13     string str;
14     stack<char> sta;
15     int res1 = 0, res2 = 0, res3 = 0;
16     getline(cin, str);
17     for (int i = 0; i < str.size(); ++i) {
18         if (!isOperator(str[i]))              //如果str[i]不是括号,则继续循环
19             continue;
20         if (str[i] == '(')                    //如果是左括号,则入栈
21             sta.push(str[i]);
22         else {
23             if (sta.empty() && str[i]==')')  //说明右括号多
24                 res3++;                      //计算不匹配的右括号的个数
25             if (str[i] == ')' &&!sta.empty()&& sta.top() == '(') {
26                 res1++;                      //匹配的括号的个数
27                 sta.pop();
28             }
29         }
30     }
31     res2 = sta.size();                       //计算不匹配的左括号的个数
32     cout << res1 << " " << res2 << " " << res3 << endl;
33     system("pause");
34     return 0;
35 }

使用栈代码实现

(3)完美幂,例如39=3^3+3^2+3^1中的[3 2 1]是39的完美幂,而33=3^3+3^1+3^1中幂有重复的1则不是完美幂

该题可以转换为39转换为3进制为1 1 1 0，即 1*3^3+1*3^2+1*3^1+0*3^0，而33转换为3进制为1 0 2 0,即33=3^3+0*3^2+2*3^1+0*3^0中出现了2即不是完美幂

进而该题就是将十进制数R转换为N进制的问题

 1 #include <iostream>
 2 #include <stack>
 3 using namespace std;
 4 int main() {
 5     stack<int> sta;
 6     int R = 0, N = 0;
 7     int tmp = 0;
 8     bool flag = true;
 9     cin >> R >> N;
10     int tmp2 = R;
11     getchar();
12     while (R != 0) {
13         tmp = R % N;
14         R = R / N;
15         if (tmp != 1 && tmp != 0) {
16             flag = false;            //只要tmp不等与0或1则说明不是完美幂
17         }
18         else
19             flag = true;
20         sta.push(tmp);
21     }
22     if (flag == true) {
23         cout << tmp2 << "是完美幂数字,完美幂为:" << endl;
24         while (!sta.empty()) {
25             cout << sta.top() << " ";
26             sta.pop();
27         }
28         cout << endl;
29     }
30     else
31         cout << tmp2 << "不是完美幂数字" << endl;
32     system("pause");
33     return 0;
34 }

显示N进制中的0版本

 1 #include <iostream>
 2 #include <stack>
 3 using namespace std;
 4 int main() {
 5     stack<int> sta;
 6     int R = 0, N = 0;
 7     int tmp = 0;
 8     bool flag = true;
 9     cin >> R >> N;
10     int tmp2 = R;
11     getchar();
12     while (R != 0) {
13         tmp = R % N;
14         R = R / N;
15         if (tmp != 1 && tmp != 0) {
16             flag = false;            //只要tmp不等与0或1则说明不是完美幂
17             break;
18         }
19         else
20             flag = true;
21         sta.push(tmp);
22     }
23     if (flag == true) {
24         cout << tmp2 << "是完美幂数字,完美幂为:" << endl;
25         while (!sta.empty()) {
26             if(sta.top() ==1)           //不现实R的N进制中的0
27                 cout << sta.top() << " ";
28             sta.pop();
29         }
30         cout << endl;
31     }
32     else
33         cout << tmp2 << "不是完美幂数字" << endl;
34     system("pause");
35     return 0;
36 }

不现实R的N进制中的0版本,且该了flag赋值中的一个bug

 1 #include <iostream>
 2 #include <stack>
 3 using namespace std;
 4 int main() {
 5     stack<int> sta;
 6     int R = 0, N = 0;
 7     int tmp = 0;
 8     bool flag = true;
 9     cin >> R >> N;
10     int tmp2 = R;
11     getchar();
12     while (R != 0) {
13         tmp = R % N;
14         R = R / N;
15         if (tmp != 1 && tmp != 0) {
16             flag = false;            //只要tmp不等与0或1则说明不是完美幂
17             break;
18         }
19         else
20             flag = true;
21         sta.push(tmp);
22     }
23     if (flag == true) {
24         int res = sta.size() - 1;         //由于N进制的位数是从0开始数的
25         cout << tmp2 << "是完美幂数字,完美幂为:" << endl;
26         while (!sta.empty()) {
27             if (sta.top() == 1)           //不现实R的N进制中的0
28                 cout << res << " ";
29             sta.pop();
30             --res;
31         }
32         cout << endl;
33     }
34     else
35         cout << tmp2 << "不是完美幂数字" << endl;
36     system("pause");
37     return 0;
38 }

真正显示幂版本

(4)受到疫情的影响，某手员工工位问题

错误的示例，使用了广度优先搜索算法，这样是不对的，广度优先搜索算法可以保证在当前入口的下一个位置一定满足条件，但是这里找到的入口，为位置[0,1]，下一个没有满足要求的位置，所以是不对的方法

 1 /**
 2     * 获取最大可同事办公员工数
 3     * @param pos char字符型vector<vector<>> 工位分布
 4     * @return int整型
 5     */
 6 #include <iostream>
 7 #include <queue>
 8 #include <vector>
 9 #include <cmath>
10 using namespace std;
11 
12 struct point {
13     int x;
14     int y;
15 };
16 point pmove[4] = { {1,0},{0,1},{-1,0},{0,-1} };  //move为C++内的一个关键字,使用move会报错: C2872: “move”: 不明确的符号
17 
18 int GetMaxStaffs(vector<vector<char> >& pos) {
19     // write code here
20     vector<vector<int>> vis(pos.size(), vector<int>(pos[0].size(), 0));  //初始化vis为pos.size()行,pos[0].size()列,且元素为0(默认也为0)
21     
22     //找到第一个可以使用的位置
23     point enter;
24     for (int i = 0; i < pos.size(); ++i) {
25         for (int j = 0; j < pos[0].size(); ++j)
26             if (pos[i][j] == '.') {
27                 enter.x = i;
28                 enter.y = j;
29                 break;
30             }
31     }
32     queue<point> q;
33     q.push(enter);
34     vis[enter.x][enter.y] = 1;  //标记enter位置已经遍历
35     point tmp1;
36     point tmp2;
37     int res = 0;
38     while (!q.empty()) {
39         tmp1 = q.front();
40         q.pop();
41         for (int i = 0; i < 4; ++i) {
42             tmp2.x = tmp1.x + pmove[i].x;
43             tmp2.y = tmp1.y + pmove[i].y;
44             if (tmp2.x>0 && tmp2.x<pos.size() && tmp2.y>0 && tmp2.y<pos[0].size() && !vis[tmp2.x][tmp2.y] && pos[tmp2.x][tmp2.y] == '.' && (abs(tmp2.x - tmp1.x) > 1 || abs(tmp2.y - tmp1.y) > 1)) {
45                 q.push(tmp2);
46                 vis[tmp2.x][tmp2.y] = 1;
47                 ++res;
48             }
49             else if (tmp2.x > 0 && tmp2.x < pos.size() && tmp2.y>0 && tmp2.y < pos[0].size() && !vis[tmp2.x][tmp2.y] && pos[tmp2.x][tmp2.y] == '.') {
50                 q.push(tmp2);
51                 vis[tmp2.x][tmp2.y] = 1;
52             }
53         }
54     }
55     return res;
56 }
57 
58 int main() {
59     int res = 0;
60     vector<vector<char>> pos = {
61         {'*','.','*','*','.'},
62         {'*','.','*','*','*'},
63         {'*','.','*','*','.'}
64     };
65     res = GetMaxStaffs(pos);
66     cout << res << endl;
67 
68     system("pause");
69     return 0;
70 }

出于学习广度优先搜索算法的目的,还是贴上代码吧

(5)智能手机产能

在智能手机生产线上，每位职工随着对手机加工流程认识的熟悉和经验的增加，日产量也会不断攀升。

假设第一天量产1台，接下来2天(即第二、三天)每天量产2件，接下来3天(即第四、五、六天)每天量产3件 ... ...

以此类推，请编程计算出第n天总共可以量产的手机数量。

思路：

或者是算出来前m天的总产量，减去(m-n)天多产的即可

 1 class Solution {
 2 public:
 3     /**
 4      * 
 5      * @param n int整型 第n天
 6      * @return int整型
 7      */
 8     int solution(int n) {
 9         // write code here
10         int res=0,day=0;
11         int tmp;
12         for(int i=1;i<=n;++i){
13             day+=i;
14             tmp=i*i;
15             res+=tmp;
16             if(day>n || day==n){
17                 if(day>n) 
18                     return res-(day-n)*i; //减去多加的
19                 if(day==n)
20                     return res;
21             }
22         }
23     }
24 };

View Code

题目链接

(6)数位之积

现给定任意正整数 n，请寻找并输出最小的正整数 m（m>9），使得 m 的各位（个位、十位、百位 ... ...）之乘积等于n，若不存在则输出 -1。

示例：

输入36，输出49；

输入100，输出455。

 1 class Solution {
 2 public:
 3     /**
 4      * 输入一个整形数值，返回一个整形值
 5      * @param n int整型 n>9
 6      * @return int整型
 7      */
 8     int solution(int n) {
 9         // write code here
10         int base=1;
11         int res=0;
12         //以下程序从大到小依次寻找n的约数
13         for(int i=9;i>1;--i){
14             //如果i是n的约数，则进入if循环
15             while(n%i==0){
16                 res+=(base*i);  //由于是求最小值,则这里从base=1开始将n的约数组成一个数字
17                 base*=10;
18                 n/=i;
19             }
20         }
21         if(n>1)
22             return -1;
23         else
24             return res;
25     }
26 };

View Code

题目链接

(7)字符串压缩后展开

链接：https://www.nowcoder.com/questionTerminal/c27561e5b7e0441493adb9a54071888d
来源：牛客网

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为[m|S](m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述：

输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输入实例：

HG[3|B[2|CA]]F

对应的输出为：

HGBCACABCACABCACAF

解释：

HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

题目链接

 1 #include <regex>  //for正则表达式
 2 #include <iostream>
 3 #include <vector>
 4 #include <string>
 5 using namespace std;
 6 
 7 int main() {
 8     string str;
 9     getline(cin,str);  
10     /**
11     *\[表示匹配[
12     *(\d+)表示匹配至少一个数字,并将匹配结果做为一个结果放入smatch类对象中
13     *\|表示匹配|
14     *(\w+)表示匹配至少一个字母,并将匹配结果做为一个结果放入smatch类对象中
15     */
16     regex pattern("\[(\d+)\|(\w+)\]");  //匹配类似于[2|CA]字符串
17     smatch res;                              //存放匹配结果
18     vector<string> vec;
19     string s;
20     while (regex_search(str, res, pattern)) {
21         for (int i = 0; i < res.size(); ++i) {
22             vec.push_back(res[i]);  //其中res[0]表示整个匹配的结果,res[1]表示第一个括号内匹配的结果,res[2]表示第二个括号内匹配的结果
23         }
24         int Num = atoi(vec[1].c_str());//c_str()就是将C++的string转化为C的字符串数组,atoi()将字符串转换为整形
25         for (int j = 0; j < Num; ++j)  //
26             s += vec[2];
27         /**
28         *为string中的string& replace (size_t pos, size_t len, const string& s);做参数准备
29         *用s替换指定字符串从起始位置pos开始长度为len的字符
30         */
31         int pos = res.position();  //匹配字串在原字串中的起始位置
32         int len = vec[0].size();   //返回匹配到的整个字符串的长度
33         str.replace(pos, len, s);  //将str起始位置为pos的len个字符替换为s
34         vec.clear();               //清空vec中的数据,为下次循环做准备
35         s.clear();                 //清空s中的数据,为下次循环做准备
36     }
37     cout << str << endl;
38 
39     system("pause");
40     return 0;
41 }

实现代码

(9)工作休息or体育馆

题目描述

由于业绩优秀，公司给小Q放了 n 天的假，身为工作狂的小Q打算在在假期中工作、锻炼或者休息。他有个奇怪的习惯：不会连续两天工作或锻炼。只有当公司营业时，小Q才能去工作，只有当健身房营业时，小Q才能去健身，小Q一天只能干一件事。给出假期中公司，健身房的营业情况，求小Q最少需要休息几天。

输入描述

第一行一个整数

输出描述

一个整数，表示小Q休息的最少天数

输入

4
1 1 0 0
0 1 1 0

输出

输出说明

小Q可以在第一天工作，第二天或第三天健身，小Q最少休息2天

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main() {
 6     int n;
 7     cin >> n;
 8     vector<int> work(n),gem(n);
 9     bool workFlag = false, gemFlag = false;
10     for (int i = 0; i < n; ++i)
11         cin >> work[i];
12     for (int i = 0; i < n; ++i)
13         cin >> gem[i];
14     int sleep = 0;
15     for (int i = 0; i < n; ++i) {
16         //公司和体育馆都不营业,只能休息
17         if (work[i] == 0 && gem[i] == 0) {
18             ++sleep;
19             workFlag = false;
20             gemFlag = false;
21             continue;
22         }
23         //如果公司和体育馆都营业,则不休息
24         if (work[i] == 1 && gem[i] == 1) {
25             //如果两个都能去,则根据明天的状况去做判断
26             if (workFlag == false && gemFlag == false)
27                 continue;
28             //否则去一个，对调今天去工作和去体育馆的状态
29             else {
30                 bool temp = workFlag;
31                 workFlag = gemFlag;
32                 gemFlag = temp;
33                 continue;
34             }
35         }
36         //公司营业,体育馆不营业
37         if (work[i] == 1) {
38             //如果前一天没有去工作,则去工作
39             if (workFlag == false) {
40                 workFlag = true;
41                 gemFlag = false;
42                 continue;
43             }
44             //否则休息(即昨天工作过了，就不去工作了)
45             else {
46                 ++sleep;
47                 workFlag = false;
48                 gemFlag = false;
49                 continue;
50             }
51         }
52         //体育馆营业,公司不营业
53         if (gem[i] == 1) {
54             //如果昨天没有去体育馆,则今天去体育馆
55             if (gemFlag == false) {
56                 workFlag = false;
57                 gemFlag = true;
58                 continue;
59             }
60             //如果去了则休息
61             else {
62                 ++sleep;
63                 workFlag = false;
64                 gemFlag = false;
65                 continue;
66             }
67         }
68     }
69     cout<<sleep<<endl;
70     return 0;
71 }

代码实现

题目链接

(10)输入n组已经排序好的数据,输出这n组中前K大的数据

输入n组已经排序好的数据,输出这n组中前K大的数据，按照递减的方式输出

输入描述：

第一行输入连个数字N和K，其中N表示N组数据，K表示返回N组数据中前K大的数据

接下来输入N行，其中每一行的第一个数字表示该组数据的个数

实例输入

3 5

2 1 2

3 3 4 5

4 6 7 8 9

示例输出

9 8 7 6 5

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main() {
 7     int N, K;
 8     cin >> N >> K;
 9     int n;
10     vector<vector<int>> vec;
11     for (int i = 0; i < N; ++i) {
12         cin >> n;
13         vector<int> vecTmp(n);
14         for (int j = 0; j < n; ++j) {
15             cin >> vecTmp[j];
16         }
17         vec.push_back(vecTmp);
18     }
19     vector<int> vecSort;
20     for (int i = 0; i < vec.size(); ++i) {
21         for (int j = 0; j < vec[i].size(); ++j)
22             vecSort.push_back(vec[i][j]);
23     }
24     sort(vecSort.begin(), vecSort.end());
25     int m = vecSort.size() - 1;
26     int Num = 0;
27     while (Num < K) {
28         cout << vecSort[m--] << " ";
29         Num++;
30     }
31     cout << endl;
32     
33 
34     system("pause");
35     return 0;
36 }

很水的一道题，做题已AC，关键看输入输出方式吧

(11)一个满二叉树,第一层结点编号为1，第二层结点编号为2、3... 求编号为x在第k层的祖先

一个满二叉树,第一层结点编号为1，第二层结点编号为2、3，第三层结点编号为4、5、6、7... 求编号为x在第k层的祖先，不存在则输出-1

输入描述：

第一行输入一个正整数Q，表示Q组测试数据

接下来输入Q组数据，每组包含连个数字x和k，表示返回x的第k层祖先

示例输入：

10 1 //表示返回结点为10的第一层祖先结点

10 3

10 4

示例输出

-1

此题关键要总结出结点数据为i，则左结点数据为2*i，右结点数据为2*i+1，另外就是要找到x所在层的层数，计算层数方法如下：

可以使用pow()函数计算层数

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int main() {
 6     int Q;
 7     cin >> Q;
 8     int x, k;
 9     int ceng;
10     for (int i = 0; i < Q; ++i) {
11         cin >> x >> k;
12         int parent = x;                //先让x的父节点等于x本身
13         for (int j = 0;; ++j) {
14             int tmp1 = pow(2, j);
15             int tmp2 = pow(2, j + 1);
16             if (x >= tmp1 && x < tmp2) {
17                 ceng = j+1;    //j为深度，j+1为层数
18                 break;
19             }
20         }
21         if (ceng <= k) {
22             cout << -1 << endl;
23             continue;               //在考试中也没有写上这个continue
24         }
25         while (ceng > k) {
26             parent /= 2;         //在考试中写成了parent=x/2，这样肯定是不对的啊，因为x是一直不变的
27             ceng--;
28         }
29         cout << parent << endl;
30     }
31     system("pause");
32     return 0;
33 }

代码实现

(12)已知Q，求使n!含有Q个0的最小正整数n

判断N！有多少个零，可用下列公式：

 1 //已知Q，求使n!含有Q个0的最小正整数n
 2 #include <iostream>
 3 using namespace std;
 4 
 5 int main() {
 6     
 7     system("pause");
 8     return 0;
 9 }
10 
11 #include<iostream>
12 #include<cstdio>
13 #include<cstdlib>
14 using namespace std;
15 
16 int ZeroTrail(int n)
17 {
18     int count = 0;
19     while (n>=5)
20     {
21         count += n / 5;
22         n /= 5;
23     }
24     return count;
25 }
26 
27 int main()
28 {
29     int q;
30     cin >> q;
31     if (!q)
32     {
33         cout << 1 << endl;
34         return 0;
35     }
36         /*
37          假如q=2，则4*q/5*5=5,这是由于2*4=8, 8/5=1, 1*5=5的缘故
38         而4*q=8
39        */
40     
41     int i = 4 * q / 5 * 5;
42     //int i = 4 * q;          //这些写是不对
43     while (ZeroTrail() < q)
44         i += 5;
45     if (q == ZeroTrail(i))
46         cout << i << endl;
47     else
48         cout << "No solution" << endl;
49     system("pause");
50     return 0;
51 }

已知Q，求使n!含有Q个0的最小正整数n

需要注意的是：i要初始化为5的倍数，因为增加一个5就相当于在n!结果的结尾中增加一个0

int i = 4 * q / 5 * 5; //原本直接初始化i=4*q即可,这样i正好是5的倍数

(13)写出求a和b最大公约数的函数gcd() -----> 求数组中最简真分数的个数

写出返回值为a和b最大公约数的函数gcd(int a,int b)

如gcd(6,8)返回值为2，即(6,8)的最最大公约数为2（32,8）的最大公约数为8

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int gcd(int a, int b) {
 6     if (a <= 0 || b <= 0)
 7         return -1;
 8     
 9     int tmp = a % b;
10     if (tmp == 0)
11         return b;
12     else
13         return gcd(b, tmp);
14 }
15 
16 int main() {
17 
18     cout << gcd(32, 8) << endl;
19 
20     system("pause");
21     return 0;
22 }

gcd()

化简版本

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int gcd(int a, int b) {
 6     if (b == 0)
 7         return a;
 8     else
 9         return gcd(b, a%b);
10 }
11 
12 int main() {
13 
14     cout << gcd(32, 8) << endl;
15 
16     system("pause");
17     return 0;
18 }

View Code

执行结果

求最大公约数方法二：暴力破解法

 1 int gcd(int a,int b){
 2     if(a<=0 || b<=0)
 3           return -1;
 4     int ret=0;
 5     for(int i=1; i<=a && i<=b; ++i){
 6           if(a%i==0 && b%i==0){
 7                 ret = i;
 8           }
 9     }  
10     return ret;
11 }

求最简真分数

思路：最简真分数，分子分母的最大公约数是1。

如4/5是一个真分数，但是5/4就不是了

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int gcd(int a, int b) {
 7     if (a <= 0 || b <= 0)
 8         return -1;
 9     int tmp = a % b;
10     if (tmp == 0)
11         return b;    //具体返回的是谁可以举例,如gcd(4,2)-->tmp=4%2=0，此时要返回的是2也就是b啊
12     else
13         return gcd(b, tmp);  //gcd(2,4)-->tmp=2%4=2-->此时要转换成gcd(4,2)-->所以写成gcd(b,temp)
14 }
15 
16 int main() {
17 
18     int N;
19     cin >> N;
20     vector<int> vec(N);
21     for (int i = 0; i < N; ++i)
22         cin >> vec[i];
23     //sort(vec.begin(), vec.end());          //这一句不加也可以，加上是为了防止出现gcd(2,4)的现象
24     int cnt = 0;
25     for (int i = 0; i < N - 1; ++i) {
26         for (int j = i + 1; j < N; ++j) 
27             if (gcd(vec[i], vec[j]) == 1)  //如果vec[i]和vec[i+1]的最大公约数为1则说明二者可以组合成一个最简真分数
28                 ++cnt;
29     }
30 
31     cout << cnt << endl;
32 
33     system("pause");
34     return 0;
35 }

最简真分数实现代码

加上了使用sort()降序排序的语句

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int gcd(int a, int b) {
 7     if (a <= 0 || b <= 0)
 8         return -1;
 9     int tmp = a % b;
10     if (tmp == 0)
11         return b;    //具体返回的是谁可以举例,如gcd(4,2)-->tmp=4%2=0，此时要返回的是2也就是b啊
12     else
13         return gcd(b, tmp);  //gcd(2,4)-->tmp=2%4=2-->此时要转换成gcd(4,2)-->所以写成gcd(b,temp)
14 }
15 
16 bool compare(int a, int b) {
17     return a > b;     //降序排序
18 }
19 
20 int main() {
21 
22     int N;
23     cin >> N;
24     vector<int> vec(N);
25     for (int i = 0; i < N; ++i)
26         cin >> vec[i];
27     sort(vec.begin(), vec.end(),compare);          //这一句不加也可以，加上是为了防止出现gcd(2,4)的现象
28     int cnt = 0;
29     for (int i = 0; i < N - 1; ++i) {
30         for (int j = i + 1; j < N; ++j) 
31             if (gcd(vec[i], vec[j]) == 1)  //如果vec[i]和vec[i+1]的最大公约数为1则说明二者可以组合成一个最简真分数
32                 ++cnt;
33     }
34 
35     cout << cnt << endl;
36 
37     system("pause");
38     return 0;
39 }

View Code

(14)求一个n进制的数除以m(十进制)的余数---乐鑫科技秋招提前批---因为一个getchar()整道题没有AC

题目描述

 1 /*
 2  *题目描述使用一个n进制的数作为被除数、m(十进制作为被除数)，求n进制的数除以m的余数
 3  *输入描述：一共两行输入
 4   第一行为两个数字 n m n表示被除数为n进制的数，m为十进制的除数
 5   第二行为n进制的被除数，由'0'~'9'和'a'~'z'组成，其中会包括无效字符，如空格，或11进制中的bcd等均为无效字符
 6  *举例：
 7   输入：
 8   11 10    //11表示被除数为11进制，10为十进制的除数
 9   123abc   //在11进制中bc为无效字符，需要去除
10   输出：
11   6
12 */

View Code

现在各个考试完，加上了getchar()就可以了，真的是服了自己。。。。。。。

 1 /*
 2  *题目描述使用一个n进制的数作为被除数、m(十进制作为被除数)，求n进制的数除以m的余数
 3  *输入描述：一共两行输入
 4   第一行为两个数字 n m n表示被除数为n进制的数，m为十进制的除数
 5   第二行为n进制的被除数，由'0'~'9'和'a'~'z'组成，其中会包括无效字符，如空格，或11进制中的bcd等均为无效字符
 6  *举例：
 7   输入：
 8   11 10    //11表示被除数为11进制，10为十进制的除数
 9   123abc   //在11进制中bc为无效字符，需要去除
10   输出：
11   6
12 */
13 
14 #include <iostream>
15 #include <string>
16 #include <algorithm>
17 #include <cmath>
18 #include <vector>
19 
20 using namespace std;
21 
22 int main() {
23     int n, m;
24     cin >> n >> m;
25     getchar();      //考试的时候由于没有加这一句，导致str为空！！！！
26     string str;
27     getline(cin, str);
28     vector<char> vec;
29     if (n >= 10) {
30         for (int i = 0; i < str.size(); ++i) {
31             if (str[i] >= '0' && str[i] <= '9' && (str[i] - '0') < n)
32                 vec.push_back(str[i]);
33             else if (str[i] >= 'a' && str[i] <= 'z' && (str[i] - 'a' + 10) < n)
34                 vec.push_back(str[i]);
35         }
36     }
37     else {
38         for (int i = 0; i < str.size(); ++i) {
39             if (str[i] >= '0' && str[i] <= '9' && (str[i] - '0') < n)
40                 vec.push_back(str[i]);
41         }
42     }
43     if (vec.size() == 0) {
44         cout << 0 << endl;
45         return 0;
46     }
47 
48     //转换
49     int value = 0;
50     int bit = 0;
51     for (int j = vec.size() - 1; j >= 0; --j) {
52         if (vec[j] >= '0' && vec[j] <= '9') {
53             value += (vec[j] - '0')*pow(n, bit++);
54         }
55         else if (vec[j] >= 'a' && vec[j] <= 'z') {
56             value += (vec[j] - 'a' + 10)*pow(n, bit++);
57         }
58     }
59     cout << (value%m) << endl;
60 
61     system("pause");
62     return 0;
63 }

实现代码

(15)求一组数中选出四组数字，该四组数作为平行四边形的四条边，然后求该平行四边形的最大面积

很奇葩的一道题，本想着平行四边形的面积为a*b*sinα 然后求sinα的最大值，但是我相错了，只要对这组数输入到map中，该数组的数作为键，键对应的值为in类型的，然后找出出现过两次，且键的数值最大、倒数第二大即可

输入描述：

第一行输入一个数len，该数字是数组中数字的个数

第二行输入len个数字，每个数字以空格隔开

输出：该平行四百那些的最大值

主要使用的技术：map，倒序遍历map

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <map>
 5 using namespace std;
 6 
 7 int main() {
 8     int len;
 9     cin >> len;
10     getchar();
11     map<int, int> numMap;
12     map<int, int>::reverse_iterator iter;
13     int tmp = 0;
14     vector<int> vec;
15     for (int i = 0; i < len; ++i) {
16         cin >> tmp;
17         numMap[tmp]++;
18     }
19     for (iter = numMap.rbegin(); iter != numMap.rend(); ++iter) {
20         if (iter->second == 2) {
21             vec.push_back(iter->first);
22         }
23     }
24     cout << vec[0] * vec[1] << endl;
25 
26     system("pause");
27     return 0;
28 }

View Code

(5)单调栈结构

给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

输入描述

第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输入 n 个数字，表示数组的值

输出描述

输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。

示例输入：

7
3 4 1 5 6 2 7

实例输出

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 int main() {
 7     int N = 0;
 8     //vector<int> arr = { 3,4,1,5,6,2,7 };
 9     cin >> N;
10     getchar();
11     vector<int> arr(N);
12     for (int i = 0; i < N; ++i) {
13         cin >> arr[i];
14         getchar();
15     }
16 
17     stack<int> st;
18     vector<int> left(N);
19     vector<int> right(N);
20     //正向遍历，填充left数组
21     for (int i = 0; i < N; ++i) {
22         //将大于arr[i]的元素下标全部移除,目的是找到比arr[i]小的下标
23         while (!st.empty() && arr[st.top()] >= arr[i]) {
24             st.pop();
25         }
26         left[i] = !st.empty() ? st.top() : -1;
27         //将下标i入栈
28         st.push(i);
29     }
30 
31     //清空栈
32     while (!st.empty()) {
33         st.pop();
34     }
35 
36     //正反向遍历，填充right数组
37     for (int i = N - 1; i >= 0; --i) {
38         //将小于arr[i]的元素下标全部移除,目的是找到比arr[i]小的下标
39         while (!st.empty() && arr[st.top()] >= arr[i]) {
40             st.pop();
41         }
42         right[i] = !st.empty() ? st.top() : -1;
43         st.push(i);
44     }
45 
46     for (int i = 0; i < N; ++i) {
47         cout << left[i] << " " << right[i] << endl;
48     }
49 
50     system("pause");
51     return 0;
52 }

算法实现

题目连接

(16)20200907中兴笔试

1）题目及代码实现(AC)

 1 /**
 2 *题目描述：第一行输入n、m分别表示n个人m个科目
 3 *          第二行输入m*n的矩阵，第一行表示第一个科目的n个人的成绩
 4 *          加入一个学生有一科大于该科的平均成绩则发祝贺短信，求总共需要发多少祝贺短信
 5 *          输出：需要发的祝贺短信的条数
 6 *输入举例：
 7 *2 2          //第一个2表示一共2个人 第二个2表示一共两科
 8 *2 3          //改行的2表示学生A在科目1中的得分为2，改行的3表示学生B在科目1中的得分为3
 9 *3 2          //改行的3表示学生A在科目1中的得分为3，改行的2表示学生B在科目1中的得分为2
10 *输出：2      //由于科目1和科目2的平均分都为2.5，所以学生A和B都要发祝贺短信
11 *自己的理解：
12 *此题的关键在于输入的是一个m*n的矩阵，行代表科目数，列代表人数
13 */
14 #include <iostream>
15 #include <vector>
16 using namespace std;
17 
18 int main() {
19     int n = 0, m = 0;
20     cin >> n >> m;
21     getchar();
22     //输入每个人的分数,其中n为人数,m为科目数
23     vector<vector<int>> vec(m, vector<int>(n, 0));
24     for (int i = 0; i < m; ++i) {
25         for (int j = 0; j < n; ++j) {
26             cin >> vec[i][j];
27             getchar();
28         }
29     }
30     //计算每一科的平均成绩
31     vector<double> average;
32     for (int i = 0; i < m; ++i) {
33         double sum = 0.0;
34         for (int j = 0; j < n; ++j) {
35             sum += vec[i][j];
36         }
37         average.push_back(sum / n);
38     }
39 
40     int ret = 0;
41     for (int i = 0; i < n; ++i) {
42         for (int j = 0; j < m; ++j) {
43             if (vec[j][i] > average[j]) {    //很可能出现bug的在这里要写成vec[j][i]
44                 ret++;
45                 break;
46             }
47         }
48     }
49 
50     cout << ret << endl;
51 
52     /*for (int i = 0; i < average.size(); ++i) {
53         cout << average[i] << endl;
54     }*/      //笔试时的测试记录：看求得每科成绩的平均值是否正确
55 
56     /*for (int i = 0; i < m; ++i) {
57         for (int j = 0; j < n; ++j) {
58             cout << vec[i][j] << " ";
59         } //笔试时的测试记录：看输入时候正确
60         cout << endl;
61     }*/
62     system("pause");
63     return 0;
64 }

View Code

2）删除一个数组中的若干个数字，使得删除后的数组是递增或递减需要，输出最少需要删除的数字的个数(考试中没做完)

 1 /**
 2 *题目描述：删除一个数组中的若干个数字，使得删除后的数组是递增或递减需要，输出最少需要删除的数字的个数
 3 *输入描述：第一行一个int型数字T，表示有多少组测试数据
 4 *          第二行一个int型数字n，表示第一组测试数组中有多少个数字
 5 *          第三行一个包含n个数字的数组
 6 *输出：最少删除多少个数字使该数组为递增或递减数组
 7 *输入举例：
 8 2                  //表示两组测试数据
 9 5                  //第一组中数组元素个数为5
10 1 4 2 3 5          //删除一个数字4即可使数组成为递增数组
11 5                   //第二组中数组元素个数为5
12 4 5 3 2 1          //删除一个数字5即可使数组成为递减数组
13 输出
14 1
15 1
16 
17 */
18 #include <iostream>
19 #include <vector>
20 using namespace std;
21 
22 int main() {
23     int T = 0;
24     cin >> T;
25     getchar();
26     while (T--) {
27         int n = 0;
28         cin >> n;
29         getchar();
30         vector<int> arr(n, 0);
31         for (int i = 0; i < n; ++i) {
32             cin >> arr[i];
33             getchar();
34         }
35         //判断arr大部分是是递增还是递减
36         int left = 0, right = 0;
37         for (int i = 0; i < n - 1; ++i) {
38             if (arr[i] < arr[i + 1])
39                 left++;             //大部分是从左到右递增
40             else
41                 right++;            //大部分是从左到右递减
42         }
43     
44         int ret = 0;
45         //从左到有大部分是递增
46         if (left > right) {
47             for (int i = 0; i < n - 1; ++i) {
48                 if (arr[i] > arr[i + 1])
49                     ret++;
50             }
51         }
52         //从左到有大部分是递减
53         else {
54             for (int j = n - 1; j > 0; --j) {
55                 if (arr[j] > arr[j - 1])
56                     ret++;
57             }
58         }
59         cout << ret << endl;
60     }
61 
62     system("pause");
63     return 0;
64 }

View Code

(17)20201011字节笔试

第一题的题目，只通过了15%，但是在vs下运行时没有问题的，估计是还有小漏洞和运行时间额要求吧

 1 /**
 2 *输入n组工号为x的员工的得分y，对这n组数据按照得分进行排序，如果有分数一样的情况，则按照工号进行排序
 3 *输出前m个员工的工号
 4 *举例输入：
 5 *5 3        第一行输入表示有5组输入数据，输出前3个员工的工号
 6 *1 1        工号为1的人得分为1
 7 *2 2        工号为2的人得分为2
 8 *3 3        工号为3的人得分为3
 9 *4 4
10 *4 4
11 *输出：4 3 2
12 */
13 
14 #include <iostream>
15 #include <map>
16 #include <vector>
17 #include <algorithm>
18 using namespace std;
19 typedef pair<int, int> PAIR;
20 
21 //比较函数
22 bool cmp(PAIR p1, PAIR p2) {
23     //如果得分一样，则按照工号进行排序降序排序
24     if (p1.second == p2.second) {     
25         return p1.first > p2.first;
26     }
27     //按照得分进行降序排序
28     return p1.second > p2.second;
29 }
30 int main() {
31     //n表示输入数据的组数，m代表按照得分排序后输出前m个人的工号,如果得分相同，则按照工号进行排序
32     int n, m;
33     cin >> n >> m;
34     map<int, int> mapScore;
35     pair<map<int, int>::iterator, bool> p;
36     for (int i = 0; i < n; ++i) {
37         int num, score;
38         cin >> num >> score;
39         p = mapScore.insert(pair<int, int>(num, score));
40         if (p.second == false) {
41             mapScore[num] += score; 
42         }
43     }
44 
45     vector<PAIR> vec(mapScore.begin(), mapScore.end());
46     sort(vec.begin(), vec.end(), cmp);
47 
48 
49     for (int i=0; i<m; i++) {
50         cout << vec[i].first << " " << vec[i].second << endl;
51     }
52 
53     system("pause");
54     return 0;
55 }

使用map将工号一样的人得分进行累加,使用vector进行排序

(18)20201012百度测试笔试

最大词频，不区分大小写---很心累，只通过了64%

 1 /**
 2 *统计一段文字每个单词出现的次数，单词不区分大小写，即认为this和This是一个单词，统计一次，假如一个单词出现多次，则输出的是第一次出现的格式
 3 *如果两个字符串出现的次数一样，则按照字典中排序的方式字符串
 4 *输入：一段文字
 5 *输出：出现次数最多的单词(第一次出现的格式) 出现的次数
 6 *例如
 7 *输入：This is a cat.This stays there. they are boys.  注意标点符号全部为英文句号
 8 *输出：This 2
 9 *输入：This is. this is. this is
10 *输出：This 3
11 */
12 
13 
14 #include <iostream>
15 #include <string>
16 #include <vector>
17 #include <map>
18 #include <algorithm>    
19 using namespace std;
20 typedef pair<string, int> PAIR;
21 void change(string & s) {
22     for (int i = 0; i < s.size(); ++i) {
23         if (s[i] > 'a' && s[i] < 'z') {
24             s[i] -= 32;
25         }
26     }
27 }
28 
29 bool cmp(PAIR p1, PAIR p2) {
30     if (p1.second == p2.second) {
31         return p1.first[0] < p2.first[0];
32     }
33     return p1.second > p2.second;
34 }
35 
36 int main() {
37     string str;
38     map<string, int> mapString;
39     pair< map<string, int>::iterator, bool> p;
40     vector<string> s;
41     while (!cin.eof() && cin >> str) {
42         string sTmp;
43         if (str[str.size() - 1] == '.') {
44             for (int i = 0; i < str.size() - 2; ++i) {
45                 sTmp[i] = str[i];
46             }
47         }
48         else {
49             sTmp = str;
50         }
51 
52         change(sTmp);
53         p = mapString.insert(pair<string, int>(sTmp, 1));
54         if (!p.second) {
55             mapString[sTmp]++;
56         }
57         else {
58             s.push_back(str);
59         }
60         str.clear();
61     }
62     vector<PAIR> vec(mapString.begin(), mapString.end());
63     sort(vec.begin(), vec.end(), cmp);
64 
65     //cout << vec[0].first << " " << vec[0].second << endl;
66 
67     string tmp;
68     bool flag = false;
69     int i;
70     for ( i= 0; i < s.size(); ++i) {
71          tmp.clear();
72          tmp = s[i];
73          change(tmp);
74          if (tmp == vec[0].first) {
75              flag = true;
76              break;
77          }
78     }
79     cout << s[i] <<" "<< vec[0].second << endl;
80 
81     system("pause");
82     return 0;
83 }

View Code

25、leetcode

(1)整数反转(涉及到int型变量溢出的问题)

题目描述：

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

解析：

 1 class Solution {
 2 public:
 3     int reverse(int x) {
 4         long long val=0;
 5         int pop=0;
 6         while(x!=0){
 7             pop=x%10;
 8             if((val*10+pop)>INT_MAX) return 0;
 9             if((val*10+pop)<INT_MIN)  return 0;
10             val=val*10+pop;
11             x/=10;
12         }
13         return val;
14     }
15 };

实现代码

题目链接

(2)判断回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

解析：将输入的数字反转，然后再和原来的数字做比较即可，相等即为回文数

 1 class Solution {
 2 public:
 3     bool isPalindrome(int x) {
 4         if(x<0)
 5             return false;  //x是负数,则一定不是回文数
 6         int y=x;  //将x复制一遍
 7         long long val=0;     //这里用int会导致第九行出现溢出
 8         int pop=0;
 9         while(x!=0){
10             pop=x%10;
11             if((val*10+pop)>INT_MAX) return 0;
12             if((val*10+pop)<INT_MIN)  return 0;   //这里不加这两个溢出判断也是可以的
13             val=val*10+pop;  //将x构成的数字反过来
14             x/=10;
15         }
16         return val==y? true:false;
17     }
18 };

View Code

题目链接

(3)判断回文字符串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

 1 class Solution {
 2 public:
 3     bool isPalindrome(string s) {
 4         string str;
 5         for(int i=0;i<s.size();i++){
 6             if(islower(s[i]) || isdigit(s[i]))  //判断s[i]是否为小写字母或者是数字
 7                 str+=s[i];
 8             else if(isupper(s[i]))     //判断s[i]是否为大写字母
 9                 str+=(s[i]+32);        //s[i]+32表示将大些字母转换为小写字母
10         }
11         int i=0;
12         int j=str.size()-1;
13         while(i<j){                    //这里的条件刚刚写成了i!=j导致出错,原因在于str.size()为偶数，那么i不等于j是恒成立的
14             if(str[i] != str[j])
15                 return false;
16             i++;
17             j--;
18         }
19         return true;
20     }
21 };

判断回文字符串

题目链接

c++的几个内置函数

1 islower(char c) 是否为小写字母
2 isuppper(char c) 是否为大写字母
3 isdigit(char c) 是否为数字
4 isalpha(char c) 是否为字母
5 isalnum(char c) 是否为字母或者数字
6 toupper(char c) 字母小转大
7 tolower(char c) 字母大转小

另外附上常见字符ASCII码，由此表可以看出大写字母转为小写字母只需要将大写字母加上32即可。

最长回文串

代码实现

 1 class Solution {
 2 public:
 3     int longestPalindrome(string s) {
 4         //创建一个哈希表(就是一个数组),用来存放s中每个字符出现的次数,由于s中包含大小写,大写和小写各26个,所以一共52个位置
 5         int hash[52];
 6         memset(hash,0,sizeof(int)*52);
 7         for(int i=0;i<s.size();++i){
 8             if(s[i]>='a' && s[i]<='z')
 9                 hash[s[i]-'a']++;
10             else if(s[i]>='A' && s[i]<='Z')
11                 hash[s[i]-'A'+26]++;         //刚刚这里没有加26,导致hash['a']和hash['A']重复计数了
12         }
13         int res=0,odd_mark=0;
14         for(int i=0;i<52;++i){
15             if(hash[i] != 0){
16                 //先让hash[i]全加进去,如果hash[i]为奇数(即某一个字符为奇数个),如果要构成回文串,肯定是要去掉一个
17                 res+=hash[i];
18                 if(hash[i] % 2 == 1){
19                     //如果某一个字符的个数为奇数个,那么只有hash[i]-1个字符才能构成回文串
20                     res--;
21                     //标记一下有单独出现的字符
22                     odd_mark=1;
23                 }
24             }
25             //以上循环完毕之后res的个数一定为偶数,即一定有偶数个字符可以构成回文串,但是如果要让这个回文串最大的话，一定是奇数个字符，如bab的形式
26         }
27         if(odd_mark){
28                 //如果odd_mark不为0,即有个数为奇数的字符,那么再给res加上1,以使res为奇数,此时res才是最大的个数
29                 res+=1;
30         }
31         return res;
32     }
33 };

最长回文串

题目链接

ASCII码网址链接

(4)计算完全二叉树结点的个数(使用层序遍历即可)

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int countNodes(TreeNode* root) {
13         if(root==NULL)      //刚刚忘记这一句，导致出错
14             return 0;
15         queue<TreeNode*> q;
16         int res=0;
17         TreeNode* t;
18         q.push(root);
19         while(q.size()!=0){
20             t=q.front();
21             //cout<<t->val;
22             q.pop();
23             res++;
24             if(t->left != NULL)
25                 q.push(t->left);
26             if(t->right != NULL)
27                 q.push(t->right);
28         }
29         return res;
30     }
31 };

使用二叉树层序遍历计算结点数目

leetcode链接

5)无重复字符的最长字串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

使用滑动窗法，原理：

 1 class Solution {
 2 public:
 3     //判断字符串s在区间[start,end)内是否存在字符target
 4     int getPosOfSame(string s,int start,int end,const char target){
 5         for(int i=start;i<end;i++){
 6             if(s[i]==target)
 7                 return i;    //在[start,end)内存在字符target,则返回和target重复的位置i
 8         }
 9         return -1;           //否则在[start,end)内不存在字符target   
10     }
11 
12     int lengthOfLongestSubstring(string s) {
13         int start=0;
14         int end=0;
15         int max_len=0;
16         int pos=0;
17         while(end<s.size()){
18             pos=getPosOfSame(s,start,end,s[end]);
19             if(pos==-1)        //在字符串s的[start,end)区间内不存在s[end]
20                 end++;         //则让窗口终点end右移
21             else{              //否则字符串s的[start,end)区间内存在s[end]
22                 max_len=(end-start)>max_len?(end-start):max_len;  //必须是这个在上面,否则是不对的
23                 start=pos+1;   //则让窗口起点在存在(窗口)重复字符的位置右移一个位置
24             }              
25         }
26         max_len=(end-start)>max_len?(end-start):max_len;
27         return max_len;
28     }
29 };

使用滑动窗法求无重复字符的最长字串

leetcode题目链接

(6)字符串转数字atoi()函数的实现

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例见leetcode题目链接

 1 class Solution {
 2 public:
 3     int myAtoi(string str) {
 4         int res=0;
 5         bool flag=false;
 6         int i=0;
 7         int tmp=0;
 8         //这里不加|| isalpha(str[i])也可以
 9         //如果str[0]是字母,则进不去下面的while循环的,那么res就一直为0,最后返回res=0
10         if(str.size()==0 || isalpha(str[i]))  
11             return 0;
12         while(str[i]==' ')
13             i++; 
14         if(str[i]=='-')
15             flag=true;
16         if(str[i]=='-' || str[i]=='+')
17             i++;
18         //条件(str[i]>='0' && str[i]<='9')可以替换为isdigit(str[i])
19         //INT_MAX=2147483647=214748364/10+7,如果res=2147483647/10=214748364,则tmp的取值不可以超过7
20         //由于已经将字符串中的负号提出来了,则只判断res是否上界溢出即可
21         while(i<str.size() && (str[i]>='0' && str[i]<='9')){
22             tmp=str[i]-'0';
23             if(res>INT_MAX/10 || (res==INT_MAX/10 && tmp>7))
24                 return flag==true? INT_MIN:INT_MAX;
25             res=res*10+tmp;
26             i++; 
27         }
28         return (flag==true)?(-res):res;
29     }
30 };

View Code

(7)寻找两个有序数组的中位数涉及到不同数据类型相除先进行转换的问题

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
 4         for(int i=0;i<nums2.size();++i){
 5             nums1.push_back(nums2[i]);
 6         }
 7         sort(nums1.begin(),nums1.end());
 8         int len=nums1.size();
 9         int mid=len/2;
10         if(len%2==1)
11             return double(nums1[mid]);
12         else
13             return double((nums1[mid-1]+nums1[mid])/2.0);  //这里必须使用2.0
14     }
15 };

View Code

需要注意的是：

 1 int型除以double型，百结果是double型
 2 自动转换遵循以下规则：
 3 1) 若参与运算量的类型不同，则先转换成同一类型，然后进行运算。
 4 2) 转换按数据长度增加的方向进行，以保证精度不度降低。如int型和long型运算时，先把int量转成long型后再进行运算。
 5 a.若两种类型的字节数不同，转换成字节数高的类型
 6 b.若两种类型的字节数相同，且一种有符号，问一种无符号，则转换成无符号类型
 7 3) 所有的浮点运算都是以双精度进行的，即使仅含float单精度量运算的表达答式，也要先转换成double型，再作运算。
 8 4) char型和short型参与运算时，必须先转换成int型。
 9 5) 在赋值运算中，赋值号两边量的数据类型不同时，赋值号右边量的类型将转换为左边量的类型。如果右边量的数据类型长度左边长时，将丢失一部分专数据，这样会降低精度，丢失的部分按属四舍五入向前舍入。
10 例如：
11 int 和double属于不同类型，转换遵循低精度到高精度转换，所以int先转成double型就算，结果就是double型。

View Code

故要使

(nums1[mid-1]+nums1[mid])/2.0的值为double类型，则必须写成2.0的形式，因为nums1[mid-1]和nums1[mid]均是int类型，2.0为double类型，他们进行运算会自动将nums[mid-1]和nums1[mid]转换为double类型，计算值才是正确的。

另外附上int和long型变量的区别：

(9)n!含有0的个数

题目描述

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例

输入5

输出1

解释：5!=120，只含有一个0

预备知识：分解质因数于是360的质因数为2、2、2、3、3、5

算法思路1:
由于2*5可以得出0，所以2的倍数*5的倍数都可以得到0，因此只需要计算n中含有多少个2的倍数和5的倍数，最后取最小值即可，这样算法复杂度为O(NlogN)
于是问题转换成了n!的质因数中含有多少和2和5，并取最小值

 1 class Solution {
 2 public:
 3     int trailingZeroes(int n) {
 4     int nCountTwo=0;
 5     int nCountFive=0;
 6     //计算n中含有2的倍数和5的倍数的个数
 7     for(int i=2;i<=n;++i){
 8         int value=i;
 9         //计算value中含有2的倍数的个数
10         while(value%2==0){
11             ++nCountTwo；
12             value/=2;
13         }
14         //计算value中含有5的倍数的个数
15         //经过第一个value之后value的值已经改变，但是这里并不影响在value中找5的倍数的个数
16         while(value%5==0){
17             ++nCountFive;
18             value/=5;
19         }
20     }
21     return nCountFive>nCountTwo?nCountTwo:nCountFive;  //返回nCountFive和nCountTwo中的最小值
22 };

算法思路1代码

1 算法思路2
2 由于n!中质因数里2的个数总是要比5的个数多(每两个数字多一个质因数2,每5个数字多一个质因数5)，因此问题转换成了求n!中含有多少个质因数5
3 N!有多少个质因数5，即N可以划分成多少组5个数字一组，加上划分成多少组25个数字一组，加上划分多少组成125个数字一组，等等。即Ans = N/5 + N/(5^2) + N/(5^3) + ...
4 Ans = N/5 + N/(5^2) + N/(5^3) + ... = ((N / 5) / 5) / 5 /...

 1 class Solution {
 2 public:
 3     int trailingZeroes(int n) {
 4         int five=0;
 5         while(n>=5){
 6             five+=n/5;
 7             n/=5;
 8         }
 9         return five;
10     }
11 };

算法思路2代码

时间复杂度为O(logn)

(10)字母异位词分组使用的数据结构为map<string,vector<string>> mp;

题目描述：

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

举例：

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
　　["ate","eat","tea"],
　　["nat","tan"],
　　["bat"]
]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

代码实现：

 1 class Solution {
 2 public:
 3     vector<vector<string>> groupAnagrams(vector<string>& strs) {
 4         map<string,vector<string>> strMap;
 5         string word;
 6         for(int i=0;i<strs.size();++i){ 
 7             word=strs[i];
 8             sort(word.begin(),word.end());               //对word进行排序,然后作为strMap的键
 9             if(strMap.find(word) == strMap.end()){       //如果没有找到则说明word是一个新的排序后的键
10                 vector<string> tmp;
11                 tmp.push_back(strs[i]);
12                 strMap.insert(pair<string,vector<string>>(word,tmp));
13             }
14             else{      //如果找到了,则说明strMap中存在word键,直接插入即可,strMap[word]是一个vector<string>
15                 strMap[word].push_back(strs[i]);
16             }
17         }
18         vector<vector<string>> res;   //存放结果并返回
19         map<string,vector<string>>::iterator iter;
20         for(iter=strMap.begin();iter!=strMap.end();++iter){
21             res.push_back(iter->second);
22         }
23         return res;
24     }
25 };

View Code

其中map<s1,s2>中的s1称为键，s2称为键对应的值，键s1是唯一的，且map对根据键自动进行排序，使用find()也是对键查找，如果键不存在，则返回map对象的end()

(11)比较含退格的字符串---使用栈stack,需要注意的是stac<char> sta; 不可以使用sta[1]访问栈中的元素,要使用sta.top();

题目描述

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

题目链接

 1 class Solution {
 2 public:
 3     bool backspaceCompare(string S, string T) {
 4         stack<char> s,t;
 5         s = getnoBackspaceString(S);
 6         t = getnoBackspaceString(T);
 7 
 8         if(s.size() != t.size())
 9             return false;
10         else{
11             while(!s.empty() && !t.empty()){
12                 //if(s[i] != t[i])         //这样写不对的！！！
13                 if(s.top() != t.top())
14                     return false;
15                 s.pop();
16                 t.pop();
17             }
18         }
19         if(!s.empty() || !t.empty())
20             return false;
21         return true;
22     }
23 
24     stack<char> getnoBackspaceString(string s){
25         stack<char> sta;
26         for(int i=0;i<s.size();++i){
27             if(s[i]!='#')
28                 sta.push(s[i]);
29             else if(s[i]=='#' && sta.size()!=0)
30                 sta.pop();          
31         }
32         return sta;
33     }
34 };

代码实现

string对象中添加字符或者是字符串的方法

直接上代码好了

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 int main() {
 6     string s = "hello world";
 7 
 8     /*向s中添加一个字符*/
 9     s.push_back('a');          //合法，此时s=hello worlda
10     s += 'a';                  //合法，此时s=hello worlda
11      
12     /*向s中添加一个字符串*/
13     s.push_back("haijing");    //非法！push_back()接受的是一个const char* 类型的参数
14     s += "haijing";            //合法，此时s=hello worldhaijing
15     s.append("haijing");         //合法，此时s=hello worldhaijing
16     
17     cout << s << endl;
18 
19     system("pause");
20     return 0;
21 }

向string对象中添加一个字符或者是字符串的方法

(12)Z型字符串

题目：

解决原理：

举例：

图原地址

 1 class Solution {
 2 public:
 3     string convert(string s, int numRows) {
 4         if(numRows==1)
 5             return s;
 6         vector<string> vec(s.size()>numRows?numRows:s.size());  //防止出现s.size()小于numsRows的情况
 7         bool flag=false;
 8         int curRow=0;
 9         for(char c:s){
10             vec[curRow]+=c;                        //vec[curRow]相当于一个string
11             if(curRow==0 || curRow==numRows-1){
12                 flag=!flag;
13             }
14             curRow+=flag==true?1:-1;
15         }
16         string ret;
17         for(string tmp:vec){
18             ret+=tmp;
19         }
20         return ret;
21     }
22 };

View Code

题目链接

需要注意的是，上述代码中出现了新的遍历string的方法和新的变量vector的方法，如下：

1 //遍历并打印字符串str中的每一个字符
2 string str;
3 for(char c:string){
4     cout<<c<<" "; 
5 }
6 cout<<endl

1 //遍历并打印vec中的每一个字符串
2 vector<string> vec={"abc","123","hundsun"};
3 for(string s:vec){
4     cout<<s<<" ";
5 }
6 cout<<endl;

(13)单词规律

实现思路：

手写split()将str按照空格分开，存储在一个vector中，遍历str，

如果pattern的首尾相等,但是vec的首尾不想等；或者，vec的首尾相等，但是pattern的首尾不相等.那么返回false

实现代码：

 1 class Solution {
 2 public:
 3     bool wordPattern(string pattern, string str) {
 4         vector<string> vec;
 5         split(str,' ',vec);  //将字符串str以空格分开
 6         if(vec.size() != pattern.size())
 7             return false;
 8         for(int i=0;i<vec.size();++i){
 9             for(int j=vec.size()-1;j>=0;--j){
10                 //如果pattern的首尾相等,但是vec的首尾不想等；或者，vec的首尾相等，但是pattern的首尾不相等.那么返回false
11                 if((pattern[i]==pattern[j]&&vec[i]!=vec[j]) || (pattern[i]!=pattern[j]&&vec[i]==vec[j]))
12                     return false;
13             }
14         }
15         return true;
16     }
17     void split(string str,char flag,vector<string> & vec){
18         stringstream iss(str);
19         string tmp;
20         while(getline(iss,tmp,flag)){
21             vec.push_back(tmp);
22             tmp.clear();
23         }
24     }
25 };

View Code

题目链接

(14)24点游戏：输入4个数执行加减乘除操作后是否可以得到24

题目描述：

思路：

/*
*整体的思路是对数据中的任意两个数进行加或减或乘或除的操作,并将结果替代原来的两个数,例如
*nums=[4,1 8,7]
*那么先对4和1进行加操作得到结果5,此时nums更新为[5,8,7]
*然后再对5和8进行加操作得到结果13,此时nums更新为[13,7]
*然后对13和7进行加操作得到结果20,此时返回false
*再执行第一层余下的递归：
*对4和1进行减操作得到结果3,此时nums更新为[13,8,7]
*对13和8进行加操作得到结果21,此时nums更新为[21,7]...
*/

class Solution {
public:
    /*
    *整体的思路是对数据中的任意两个数进行加或减或乘或除的操作,并将结果替代原来的两个数,例如
    *nums=[4,1 8,7]
    *那么先对4和1进行加操作得到结果5,此时nums更新为[5,8,7]
    *然后再对5和8进行加操作得到结果13,此时nums更新为[13,7]
    *然后对13和7进行加操作得到结果20,此时返回false
    *再执行第一层余下的递归：
    *对4和1进行减操作得到结果3,此时nums更新为[13,8,7]
    *对13和8进行加操作得到结果21,此时nums更新为[21,7]...
    */
    bool judgePoint24(vector<int>& nums) {
        vector<double> Nums;
        for(int x:nums)
            Nums.push_back(x*1.0);   //将nums中的int类型转换为double
        return helper(Nums);
    }
    bool helper(vector<double> & nums){
        int N=nums.size();
        if(N==1){                      //如果最后迭代到nums中只有一个元素,且该元素等于24则返回true
            //abs()取绝对值函数,不取绝对值就过不了...
            return (abs(nums[0]-24)<1e-6);  //由于是double类型的,所以不可以直接使用nums[0]==24
        }

        //取出nums中的两个元素a和b,对这两个元素执行加或减或乘或除运算,得到的结果放在一个新的数组中
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                if(i==j)
                    continue;                          //如果i和j相等，那就不需要做任何操作
                vector<double> newNums;
                for(int k=0;k<N;++k){
                    if(k!=i && k!=j)
                        newNums.push_back(nums[k]);    //将nums中除了a和b两个元素放入新的数组中
                }
                newNums.push_back(-1);                 //保留一个位置给a和b运算后的结果

                double a=nums[i];
                double b=nums[j];

                newNums.back()=a+b;                   //修改newNums的最后一个元素为a+b
                if(helper(newNums)) return true;

                newNums.back()=a-b;
                if(helper(newNums)) return true;

                newNums.back()=a*b;                    //修改newNums的最后一个元素为a*b
                if(helper(newNums)) return true;

                if(b!=0){
                    newNums.back()=a/b;
                    if(helper(newNums)) return true;
                }
            }
        }
        return false;
    }
};

实现代码

题目链接

(15)删除字符串中出现次数最少的字符

思路：将字符串中的每个字符转换为对应的数字，然后对统计相同数字出现的次数，再找出一个最小的出现次数min，最后遍历字符串大于min的才会被输出

#include <iostream>
#include <string>
using namespace std;

int main(){
    string str;
    //getline(cin,str);       //这样不通过
    while(getline(cin,str)){
        //创建一个数组并初始化为0
        int val[26]={0};
        //数字0代表字符a、数字1代表字母b
        for(char x:str){
            val[x-'a']++;
        }
        //找到字符串中出现次数最少的最小值
        int min=val[str[0]-'a'];
        for(int i=1;i<str.size();++i){
            if(min>val[str[i]-'a'])
                min=val[str[i]-'a'];
        }
        //字符出现次数大于min的才会被打印
        for(int i=0; i<str.size();++i){
            if(val[str[i]-'a']>min){
                cout<<str[i];
            }
        }
        cout<<endl;
    }
    
    return 0;
}

实现代码

题目链接

(16)岛屿数量(dfs深度优先搜索解决)

题目描述

举例：

实现：

 1 class Solution {
 2 public:
 3     int numIslands(vector<vector<char>>& grid) {
 4         if(grid.size()==0)
 5             return 0;
 6         vector<vector<int>> visited(grid.size(),vector<int>(grid[0].size(),0));   //新建一个标记数组,用来标记已经访问过了的位置
 7         int islandNum=0;
 8         //遍历grid
 9         for(int i=0;i<grid.size();++i){
10             for(int j=0;j<grid[0].size();++j){
11                 //如果当前位置i、j是陆地,则继续搜索
12                 if(grid[i][j]=='1' && visited[i][j]==0){
13                     dfs(grid,visited,i,j );
14                     //一次深度搜索完毕,则证明是有一个岛屿
15                     ++islandNum;
16                 }
17             }
18         }
19         return islandNum;
20     }
21 
22     //深度优先搜索
23     void dfs(vector<vector<char>>& grid,vector<vector<int>>& vis,int x,int y){
24         //移动方向
25         int dx[4]={-1,1,0,0};
26         int dy[4]={0,0,-1,1};  //定义移动方向：上 下 左 右
27         //标记位置x、y已访问
28         vis[x][y]=1;
29         //遍历移动的方向,目的是遍历grid中的某个位置的上下左右
30         for(int i=0;i<4;++i){
31             int newx=x+dx[i];
32             int newy=y+dy[i];
33             //判断newx、newy是否越界
34             if(newx>=0 && newx<grid.size() && newy>=0 && newy<grid[0].size()){
35                 //如果当前是陆地且当前位置没有被访问过,则继续搜索
36                 if(grid[newx][newy]=='1' && vis[newx][newy]==0){
37                     dfs(grid,vis,newx,newy);
38                 }
39             }
40         }
41     }
42 };

View Code

题目链接

岛屿数量(bfs广度优先搜索解决)

广度优先搜索就是从一个点不断的去试探这个点的上、下、左、右是否是合适的点，方法是使用队列，具体如下：

 1 class Solution {
 2 public:
 3     int numIslands(vector<vector<char>>& grid) {
 4         if(grid.size()==0)
 5             return 0;
 6         vector<vector<int>> visited(grid.size(),vector<int>(grid[0].size(),0));
 7         int islandNum=0;
 8         //遍历grid数组
 9         for(int i=0;i<grid.size();++i){
10             for(int j=0;j<grid[0].size();++j){
11                 if(grid[i][j]=='1' && visited[i][j]==0){
12                     bfs(grid,visited,i,j);
13                     ++islandNum;
14                 }
15             }
16         }
17         return islandNum;
18     }
19 
20     //广度优先搜索
21     void bfs(vector<vector<char>>& grid,vector<vector<int>>& vis,int x,int y){
22         //标记位置x、y已经被访问
23         vis[x][y]=1;
24         //创建队列，并将初始位置加入到队列中去
25         Point pos(x,y);
26         queue<Point> q;
27         q.push(pos);
28         //新建走的方向
29         int dx[4]={-1,1,0,0};
30         int dy[4]={0,0,-1,1};
31         //如果队列非空,则遍历位置pos.x、pos.y的四个方向是否为1
32         while(!q.empty()){
33             //将队首的弹出
34             Point tmp=q.front(); 
35             q.pop(); 
36             //遍历位置x、y的四个方向
37             for(int i=0;i<4;++i){
38                 Point newpos;
39                 newpos.x=tmp.x+dx[i];
40                 newpos.y=tmp.y+dy[i];
41                 //判断newx、newy是否越界
42                 if(newpos.x>=0 && newpos.x<grid.size() && newpos.y>=0 && newpos.y<grid[0].size()){
43                     //如果新位置newpos.x、newpos.y位置为1且没有被访问过,则将newpos入队并标记newpos已经访问过
44                     if(grid[newpos.x][newpos.y]=='1' && vis[newpos.x][newpos.y]==0){
45                         q.push(newpos);
46                         vis[newpos.x][newpos.y]=1;
47                     }
48                 }
49             }
50         }
51     }
52 
53 private:
54     struct Point{
55         int x;
56         int y;
57         Point(int a=0,int b=0){
58             x=a;
59             y=b;
60         }
61     };
62 };

View Code

(17)压缩字符串

题目描述：

直接见题目链接吧

还是直接看代码吧，只可意会的那种

 1 class Solution {
 2 public:
 3     int compress(vector<char>& chars) {
 4         if(chars.empty())
 5             return 0;
 6         int cur=0;                        //chars数组中新字符写入的起始位置
 7         for(int i=0;i<chars.size(); ){
 8             int j=i;                      //记录重复字符起始位置
 9             while(i+1<chars.size() && chars[i]==chars[i+1]){
10                 ++i;                     //i已经加到了重复字符的最后一个位置
11             }
12             if(i-j+1==1){                //如果字符重复的次数只有1次那么是不用写成"a","1"的,直接写成"a"即可
13                 chars[cur++]=chars[j];    //将重复的字符起始位置赋值到chars新的位置cur处,并递增cur
14                 ++i;                     //i继续向右移动
15             }
16             else{                        //否则重复的字符不止一个,此时需要写成类似于"a","2"的形式了
17                 chars[cur++]=chars[j];
18                 string times=to_string(i-j+1);    //将字符重复的次数转为字符串
19                 for(char x:times){                //如果"a"出现了12次,那么times=“12”,需要转换成"a","1","2"
20                     chars[cur++]=x;
21                 }
22                 ++i;
23             }
24         }
25         return cur;
26     }
27 };

View Code

第二遍

 1 class Solution {
 2 public:
 3     int compress(vector<char>& chars) {
 4         int cur=0;
 5         int j=0;
 6         for(int i=0;i<chars.size();++i){
 7             //保留当前字符串的起始位置
 8             j=i;
 9             //找到和当期字符串相同的最后一个字符串的最后一个位置
10             while( i<chars.size()-1 && chars[i]==chars[i+1])
11                 ++i;               
12             //chars[j]只出现了一次
13             if(i-j+1==1){
14                 chars[cur++]=chars[j];
15             }
16             else{
17                 chars[cur++]=chars[j];
18                 string times=to_string(i-j+1);
19                 for(char x:times){
20                     chars[cur++]=x;
21                 }
22             }
23         }
24         return cur;
25     }
26 };

压缩字符串第二遍

(18)最长公共子序列(dp)

代码实现：

 1 class Solution {
 2 public:
 3     int longestCommonSubsequence(string text1, string text2) {
 4         if(text1.size()==0 || text2.size()==0)
 5             return 0;
 6         //创建dp矩阵
 7         vector<vector<int>> dp(text1.size(),vector<int>(text2.size(),0));
 8         //初始化dp[0][0]
 9         dp[0][0] = text1[0]==text2[0] ? 1:0;
10         //初始化dp矩阵的第0行,text1作为行，text2作为列
11         for(int i=1;i<text1.size();++i){
12             dp[i][0] = max(text1[i]==text2[0] ? 1:0, dp[i-1][0]);
13         }
14          //初始化dp矩阵的第0列,text1作为行,text2作为列
15         for(int j=1;j<text2.size();++j){
16             dp[0][j] = max(text1[0]==text2[j] ? 1:0, dp[0][j-1]);
17         }
18         //填充dp矩阵
19         for(int i=1;i<text1.size();++i){
20             for(int j=1;j<text2.size();++j){
21                 //如果text1[i]!=text[j],则dp[i][j]来自于上方(dp[i-1][j])和左方(dp[i][j-1])中较大的一个
22                 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
23                 //如果text1[i]!=text[j],则dp[i][j]来自于左上方加1
24                 if(text1[i]==text2[j]){
25                     dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
26                 }
27             }
28         }
29         return dp[text1.size()-1][text2.size()-1];
30     }
31 };

View Code

题目链接

(19)基本计算器(只包含加减乘除,不包含括号)---58同城笔试

 1 class Solution {
 2 public:
 3     int calculate(string s) {
 4         int res=0,curRes=0;
 5         long num=0;             //刚刚这里num的类型是int就会显示第十行溢出,但是long没事
 6         int n=s.size();
 7         char op='+';
 8         for(int i=0;i<n;++i){
 9             char c=s[i];
10             if(c>='0' && c<='9'){
11                 num=num*10+c-'0';
12             }
13             if(c=='+' || c=='-' || c=='*' || c=='/' || i==n-1){
14                 switch(op){
15                     case('+'):curRes+=num;break;
16                     case('-'):curRes-=num;break;
17                     case('*'):curRes*=num;break;
18                     case('/'):curRes/=num;break;
19                 }
20                 //如果此时c是'*'或者是'/'则不会执行下面的代码,但是op会更新为'*'或者是'/'这样就可以实现先算乘除后算加减
21                 if(c=='+' || c=='-' || i==n-1){
22                     res+=curRes;
23                     curRes=0;
24                 }
25                 op=c;
26                 num=0; 
27             }
28         }
29         return res;
30     }
31 };

基本计算器实现代码

题目链接

26、算法

(1)深度优先遍历

(2)回溯法

回溯法描述：
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯法最重要的是递归函数的实现，下面以dfs()函数为例，说明回溯法模板如何写

 1 定义全局变量reslut,盛放结果                           //result一般是一个二维数组
 2 void dfs(待处理的数组,下标start,中间结果数组temp)
 3 {
 4     if(结束条件)                                    //结束条件一般是strat==待处理数组大小  出口
 5     {
 6         将中间结果temp添加到最终结果result中
 7             return;
 8     }
 9      for(int i=start;i<数组大小;i++)                //入口,入口为i+1
10      {
11          执行具体题目要求的动作;
12          dfs(待处理的数组,i+1;中间结果数组temp);
13          清除中间结果中的数据,以便下次递归存放数据,如果待处理中的数据变了,也要恢复待处理数组中的数据      //清除中间变量中保存的数据
14      }
15 }
16 
17 注:dfs(）返回值类型一般为void

1)分割字符串使子串成为回文串 m2621

题目描述：

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案

 1 class Solution {
 2 public:
 3     vector<vector<string>> partition(string s) {
 4         vector<string> tmp;
 5         dfs(s,0,tmp);
 6         return result;
 7     }
 8 
 9     void dfs(string s, int index, vector<string> & tmp){
10         //出口
11         if(index==s.size()){
12             result.push_back(tmp);
13             return;
14         }
15         //入口
16         for(int i=index;i<s.size();i++){
17             if(isHuiWen(s,index,i)){   //注意这里应该将在for循环中不断增加的i作为第二个参数
18                 tmp.push_back(s.substr(index,i-index+1));
19                 dfs(s,i+1,tmp);        //如果s的index到i之间为回文串,则进一步去探索index到i+1是否为回文串
20                 tmp.pop_back();        //清除中间结果中的数据,以便下次迭代使用
21             }
22         }
23     }
24 
25     //判断字符串s的第start到end之间的字符串是否为回文字符串
26     bool isHuiWen(string s,int start,int end){
27         while(start<end){
28             if(s[start] != s[end])
29                 return false;      //有一个不相同的则说明不是回文串
30             start++;
31             end--;
32         }
33         return true;  //在while中没有返回则说明s的第start到end之间的字符串是回文串
34     }
35 
36 private:
37     vector<vector<string>> result;  //定义全局变量来保存结果
38 };

分割字符串使子串成为回文串

假如第二个参数是index：

leetcode题目链接

2)给n个数字,求这n个数字的全排列 m2622

给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:

输入: [1,2,3]
输出:
[
　　[1,2,3],
　　[1,3,2],
　　[2,1,3],
　　[2,3,1],
　　[3,1,2],
　　[3,2,1]
]

 1 class Solution {
 2 public:
 3     vector<vector<int>> permute(vector<int>& nums) {
 4         if(nums.size()==0){
 5             return result;
 6         }
 7         vector<int> tmp;
 8         dfs(nums,0,tmp);    
 9         return result;    
10     }
11 
12     void dfs(vector<int>& nums,int index,vector<int>& tmp){
13         //出口
14         if(index==nums.size()){
15             result.push_back(tmp);
16             return;
17         }
18         //入口
19         for(int i=index;i<nums.size();i++){
20             Swap(nums[index],nums[i]);
21             tmp.push_back(nums[index]);  //由于是不断的将nums的第i个位置的数交换到index位置上,所以应该将index位置的数添加到tmp中去
22             dfs(nums,index+1,tmp);       //继续寻找tmp中第二个位置上的数字
23             Swap(nums[index],nums[i]);   //为了保持nums中数据的原始顺序,这里需要再交换回来
24             tmp.pop_back();
25         }
26     }
27 
28     //定义交换函数
29     void Swap(int & a,int & b){
30         int temp=a;
31         a=b;
32         b=temp;
33     }
34 
35 private:
36     vector<vector<int>> result;
37 };

View Code

参数问题：

leetcode题目链接

3)给n个数字求这n个数字的全排列(n个数字可能重复)

给定一个可包含重复数字的序列，返回所有不重复的全排列。

方法一：定义一个vector<bool>数组使用过则将对应的位置置为true

 1 class Solution {
 2 public:
 3     vector<vector<int>> permuteUnique(vector<int>& nums) {
 4         vector<bool> used(nums.size(),false);
 5         vector<int> tmp;
 6         sort(nums.begin(),nums.end());
 7         dfs(nums,used,tmp);
 8         return result;
 9     }
10 
11     void dfs(vector<int>& nums,vector<bool>& used,vector<int> tmp){
12         //出口
13         if(tmp.size()==nums.size()){
14             result.push_back(tmp);
15             return;
16         }
17         //入口
18         for(int i=0;i<nums.size();i++){
19             if(!used[i]){
20                 if(i>0 && nums[i]==nums[i-1] && !used[i-1])  //i>0条件是为了防止num[i-1]越界
21                     continue;
22                 tmp.push_back(nums[i]);
23                 used[i]=true;
24                 dfs(nums,used,tmp);
25                 tmp.pop_back();
26                 used[i]=false;
27             }
28         }
29     }
30 private:
31     vector<vector<int>> result;
32 };

解法一

方法二：使用unorder_set类下的count方法去重复

答案链接

leetcode题目链接

(3)广度优先搜索

通用算法步骤：

例、迷宫问题

洪尼玛今天准备去寻宝，在一个n*n （n行, n列）的迷宫中，存在着一个入口、一些墙壁以及一个宝藏。由于迷宫是四连通的，即在迷宫中的一个位置，只能走到与它直接相邻的其他四个位置（上、下、左、右）。现洪尼玛在迷宫的入口处，问他最少需要走几步才能拿到宝藏？若永远无法拿到宝藏，则输出-1。

每组数据输入第一行为正整数n，表示迷宫大小。

接下来n行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'#'表示该位置为墙壁，字符'S'表示该位置为入口，字符'E'表示该位置为宝藏，输入数据中只有这四种字符，并且'S'和'E'仅出现一次。

  1 //使用广度优先搜索解决走迷宫问题
  2 #include <iostream>
  3 #include <queue>
  4 using namespace std;
  5 
  6 //char** maze;      //定义迷宫矩阵  位置1
  7 //以下为方便,定义了全局二维数组,如果需要在dos下手动输入,则将位置1~6取消注释即可
  8 char maze[5][5] = {
  9     {'S','.','#','.','.' },
 10         {'#','.','#','.','#'},
 11         {'#','.','#','.','#'},
 12         {'#','.','.','.','E'},
 13         {'#','.','.','.','.'}
 14 };
 15 
 16 int** pre;       //定义走过的路径
 17 int** vis;       //用来标记已经走过了的位置
 18 struct point {   //定义结构，用来表示移动的数据点
 19     int x;
 20     int y;
 21 };
 22 //定义移动策略,(1,0)表示向下移动,(0,1)表示向右移动,（-1，0）表示向上移动,（0，-1）表示向左移动
 23 point pmove[4]={ {1,0},{0,1},{-1,0},{0,-1} };  
 24 
 25 void creatMaze(int row, int col) {
 26     //先分配空间
 27     //maze = new char*[row];    //位置2
 28     pre = new int*[row];
 29     vis = new int*[row];
 30     for (int i = 0; i < row; ++i) {
 31         //maze[i] = new char[col];  //位置3
 32         pre[i] = new int[col];
 33         vis[i] = new int[col];
 34     }
 35     //二维数组输入数据,接受一行以空格隔开输入方法
 36     for (int i = 0; i < row; ++i) {
 37         for (int j = 0; j < col; ++j) {
 38             /*cin >> maze[i][j];    //位置4
 39             getchar();*/            //位置5
 40             pre[i][j] = 0;
 41             vis[i][j] = 0;   //初始化被访问位置标记为没有被标记
 42         }
 43     }
 44     
 45     for (int i = 0; i < row; ++i) {
 46         for (int j = 0; j < col; ++j)
 47             cout << maze[i][j] << " ";
 48         cout << endl;
 49     }
 50 }
 51 
 52 //使用广度优先搜索找到宝藏的位置
 53 int bfs(int row,int col) {
 54     //先找到入口位置enter和终点位置end
 55     point enter; 
 56     point end;
 57     for (int i = 0; i < row; ++i) {
 58         for (int j = 0; j < col; ++j) {
 59             if (maze[i][j] == 'S') {
 60                 enter.x = i;
 61                 enter.y = j;
 62             }
 63             else if (maze[i][j] == 'E') {
 64                 end.x = i;
 65                 end.y = j;
 66             }
 67         }
 68     }
 69     queue<point> q;                //定义尝试走过的路径
 70     q.push(enter);                //将入口入队
 71     vis[enter.x][enter.y] = 1;  //标记入口位置已经被访问
 72     point tmp1;
 73     point tmp2;
 74     bool flag = false;
 75     int res = 0;                //走的步数
 76     while (!q.empty()) {
 77         tmp1 = q.front();
 78         q.pop();
 79         for (int i = 0; i < 4; ++i) {
 80             tmp2.x = tmp1.x + pmove[i].x;
 81             tmp2.y = tmp1.y + pmove[i].y;
 82             if (tmp2.x >= 0 && tmp2.x < row && tmp2.y>=0 && tmp2.y < col && vis[tmp2.x][tmp2.y] == 0 && maze[tmp2.x][tmp2.y] == '.') {
 83                 vis[tmp2.x][tmp2.y] = 1;    //标记tmp2已经走过
 84                 ++res;                      //步数加1
 85                 if (maze[tmp2.x][tmp2.y] == 'E') {
 86                     flag = true;
 87                     break;
 88                 }
 89                 q.push(tmp2);
 90                 break;         //找到一条可行的路之后就不需要再次去按照方向上的去寻找可以走的点了
 91             }
 92         }
 93         if (flag == true)
 94             break;
 95     }
 96     return res + 1;  //加1表示到达终点的最后一步
 97 }
 98 
 99 int main() {
100     int row = 5, col = 5;
101     //cin >> row >> col;
102     //getchar();
103     creatMaze(row, col);
104     int res = bfs(row, col);
105     cout << res << endl;
106 
107     //释放空间
108     for (int i = 0; i < row; ++i) {
109         //delete[] maze[i];    ////位置6
110         delete[] vis[i];
111         delete[] pre[i];
112     }
113     delete[] vis;
114     delete[] pre;
115 
116     system("pause");
117     return 0;
118 }

View Code

按照以下的步骤走的，显然不是最少的路径

上面的思路是错误的，正确的思路如下：

首先将入口位置的vis[enter.x][enter.y]设置为1，然后不断的寻找可以走的路径，并经对应的路径在原来的基础上，将vis[tmp2.x][tmp2.y]加1

化成表的形式：

由于走的策略是”下右上左”,则5右边的6会把位置7给抢占了,5下边的6则无路可走,该路径结束,且5左边的6会继续向右走,走到6右边的位置7

代码实现如下：

  1 //使用广度优先搜索解决走迷宫问题
  2 #include <iostream>
  3 #include <queue>
  4 using namespace std;
  5 
  6 //char** maze;      //定义迷宫矩阵  位置1
  7 //以下为方便,定义了全局二维数组,如果需要在dos下手动输入,则将位置1~6取消注释即可
  8 char maze[5][5] = {
  9     {'S','.','#','.','.' },
 10         {'#','.','#','.','#'},
 11         {'#','.','#','.','#'},
 12         {'#','.','.','.','E'},
 13         {'#','.','.','.','.'}
 14 };
 15 
 16 int** pre;       //定义走过的路径
 17 int** vis;       //用来标记已经走过了的位置
 18 struct point {   //定义结构，用来表示移动的数据点
 19     int x;
 20     int y;
 21 };
 22 //定义移动策略,(1,0)表示向下移动,(0,1)表示向右移动,（-1，0）表示向上移动,（0，-1）表示向左移动
 23 //point pmove[4]={ {1,0},{0,1},{-1,0},{0,-1} };  //下
 24 point pmove[4] = { {1,0},{0,1},{-1,0},{0,-1} };
 25 
 26 
 27 void creatMaze(int row, int col) {
 28     //先分配空间
 29     //maze = new char*[row];    //位置2
 30     pre = new int*[row];
 31     vis = new int*[row];
 32     for (int i = 0; i < row; ++i) {
 33         //maze[i] = new char[col];  //位置3
 34         pre[i] = new int[col];
 35         vis[i] = new int[col];
 36     }
 37     //二维数组输入数据,接受一行以空格隔开输入方法
 38     for (int i = 0; i < row; ++i) {
 39         for (int j = 0; j < col; ++j) {
 40             /*cin >> maze[i][j];    //位置4
 41             getchar();*/            //位置5
 42             pre[i][j] = 0;
 43             vis[i][j] = 0;   //初始化被访问位置标记为没有被标记
 44         }
 45     }
 46     
 47     for (int i = 0; i < row; ++i) {
 48         for (int j = 0; j < col; ++j)
 49             cout << maze[i][j] << " ";
 50         cout << endl;
 51     }
 52 }
 53 
 54 //使用广度优先搜索找到宝藏的位置
 55 void bfs(int row,int col) {
 56     //先找到入口位置enter和终点位置end
 57     point enter; 
 58     point end;
 59     for (int i = 0; i < row; ++i) {
 60         for (int j = 0; j < col; ++j) {
 61             if (maze[i][j] == 'S') {
 62                 enter.x = i;
 63                 enter.y = j;
 64             }
 65             else if (maze[i][j] == 'E') {
 66                 end.x = i;
 67                 end.y = j;
 68             }
 69         }
 70     }
 71     queue<point> q;                //定义尝试走过的路径
 72     q.push(enter);                //将入口入队
 73     vis[enter.x][enter.y] = 1;  //标记入口位置已经被访问
 74     point tmp1;
 75     point tmp2;
 76     bool flag = false;
 77     while (!q.empty()) {
 78         tmp1 = q.front();
 79         q.pop();
 80         for (int i = 0; i < 4; ++i) {
 81             tmp2.x = tmp1.x + pmove[i].x;
 82             tmp2.y = tmp1.y + pmove[i].y;
 83             /**
 84               *下面的if条件需要注意的地方：
 85               *必须判断tmp2.x是否在[0,row)范围内,如果不判断vis一定会报错数组越界
 86               *必须判断tmp2.y是否在[0,col)范围内,如果不判断vis一定会报错数组越界
 87               *vis[tmp2.x][tmp2.y]初始化为0(未走到的地方).取非后该条件即为真
 88               *maze[tmp2.x][tmp2.y] != '#'不可以替换为maze[tmp2.x][tmp2.y] == '.'，因为还有maze[tmp2.x][tmp2.y] = 'E'的情况
 89                  如果替换为maze[tmp2.x][tmp2.y] == '.'，则tmp2永远不会为enter(enter位置对应的字符为'E'),那么flag永远为false
 90               *
 91             */
 92             if (tmp2.x >= 0 && tmp2.x < row && tmp2.y>=0 && tmp2.y < col && !vis[tmp2.x][tmp2.y] && maze[tmp2.x][tmp2.y] != '#') {
 93                 vis[tmp2.x][tmp2.y] = vis[tmp1.x][tmp1.y] + 1;    //标记tmp2已经走过,原来的位置加1
 94                 q.push(tmp2);
 95                 //break;         //上面的代码没有最优路径就是因为这里有bug,需要注释掉
 96             }
 97         }
 98         if (vis[end.x][end.y]) {
 99             flag = true;
100             break;
101         }
102     }
103     if (flag == true)
104         cout << vis[end.x][end.y] - 1 << endl;
105     else
106         cout << "迷宫无路径可以走出" << endl;
107 }
108 
109 int main() {
110     int row = 5, col = 5;
111     //cin >> row >> col;
112     //getchar();
113     creatMaze(row, col);
114     bfs(row, col);
115 
116     //释放空间
117     for (int i = 0; i < row; ++i) {
118         //delete[] maze[i];    ////位置6
119         delete[] vis[i];
120         delete[] pre[i];
121     }
122     delete[] vis;
123     delete[] pre;
124 
125     system("pause");
126     return 0;
127 }

View Code

题目链接

参考博客参考文库

(4)dp动态规划(以背包问题为例)

理论上新建一个3*4的二维数组vec即可，让后向vec中填充数据，如下：

但是实际上在dp算法中药访问vec[i-1][j]，在for循环中i=0的情况下会出现数组越界的情况，即使for循环中的i从等于1开始,那么也等价于吉他物品的编号为i=1，在i=1上面还是要有一行为空，所以需要可以像下面创建二维数组：

故在实际编程的时候，需要创建空物品、吉他、音响、电脑的价值和重量方法如下：

vector<int> price = { 0,1500,3000,2000 };
vector<int> weight = { 0,1,4,3 };

因此weight.size()-1=实际物品的个数，而在遍历二维数组vec的时候在外层for循环中使用的条件必须是i<实际物品的个数，即填充vec矩阵的伪代码如下：

1 for(int i=1;i<=实际物品的个数；++i）{
2     for(int j=1;j<=实际问题中背包的重量;++j){
3           ...
4     }            
5 }

下面介绍填充vec数据的方法：

(1)对于吉他行，可以选的物品只有吉他，而吉他的重量为1，所以背包1-4均可以放下吉他，将吉他的价值放入第一行：

(2)接着放音响行，此时可以选的物品有吉他和音响，音响的重量为4，价值为3000，而可盛放物品最大重量为1，2，3的背包均不可以放入音响(因为j<weight[i],i=2,j=1,2,3)，因此如下的方法放入：

(i,j)位置放入[i-1,j]位置处的数，即(2,1)位置放(1,1)位置的数字、(2,2)位置放(1,2)位置的数字、(2,3)位置放(1,3)位置的数字

但是j=weight[i],i=2,j=4，且j=4的背包没有剩余容量，直接将3000放入位置(2,4)即可，完成如下：

(3)电脑行的存放数据方法：

此时可以选的物品有吉他、音响和电脑，电脑重量为3，价值为2000，因此背包重量为1、2的背包均放不下电脑，即(因为j<weight[i],i=3,j=1,2)，因此如下的方法放入：

(i,j)位置放入[i-1,j]位置处的数，即(3,1)位置放(2,1)位置的数字、(3,2)位置放(2,2)位置的数字；

j=weight[i],i=3,j=3，且j=4的背包没有剩余容量，直接将2000放入位置(3,3)即可；

j>weight[i],i=3,j=4,此时背包游剩余容量，此时取tmp1和tmp2较大的数字放入(3,4),tmp1和tmp2的取法如下;

取tmp1为当前列下上一行vec中的数据，即tmp1=vec[i-1][j];在本例中，tmp1=vec[2][4];

取tmp2为当前物品价值+背包剩余空间可以盛放的物品价值，即tmp2=price[i] + vec[i-1][j-weight[i]]; //vec的行必须为i-1,因为vec矩阵上一行中的数据永远是最优的，所以选i-1行中某一列即可。

在本例中，tmp1=3000，tmp2=当前电脑的价值+背包重量减去电脑重量可以盛放的价值，即tmp2=2000+vec[3-1][4-3]=2000+1500=3500

所以最后如下：

代码实现如下：

 1 //dp动态规划解决01背包问题
 2 #include <iostream>
 3 #include <vector>
 4 using namespace std;
 5 
 6 //weight[i]表示第i件产品的重量,prive[i]表示第i件产品的价值,bagWeight表示背包可放入物品的最大重量
 7 void dp(vector<int>& weight, vector<int>& price,int bagWeight) {
 8     int size = weight.size()-1;    //由于在weight和price中增加了第一个数字0,所以实际物品的个数必须减1
 9     vector<vector<int>> vec(size+1, vector<int>(bagWeight+1, 0)); //存放物品1~N可以放入1kg背包、2kg背包、3kg背包...的物品的价值
10     /**
11     *外层的for循环表示第i件物品
12     *内层的for循环表示可放入最大质量为j的背包
13     *size为物品的个数
14     */
15     for (int i = 1; i <= size; ++i) {
16         for (int j = 1; j <= bagWeight; ++j) {
17             if (weight[i] > j)                  //如果第i件产品的重量大于当前背包的重量j
18                 vec[i][j] = vec[i - 1][j];      //则放入当前背包j下i-1件产品的价值
19             else {                              //否则第i件产品可以放入到当前背包j下
20                 int tmp1 = vec[i - 1][j];       //矩阵中要装入数据的位置(i,j)的上一个位置(i-1,j)
21                 int tmp2 = price[i] + vec[i - 1][j - weight[i]];  //当前商品i的价值+(行:上一个商品i-1,列:j - weight[i])的背包可放入的价值
22                 vec[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
23             }
24         }
25     }
26     int res = vec[size][bagWeight];
27     cout << res << endl;
28 }
29 
30 
31 int main() {
32     vector<int> price = { 0,1500,3000,2000 };
33     vector<int> weight = { 0,1,4,3 };
34     int bagWeight = 4;
35     dp(weight, price, bagWeight);
36 
37     system("pause");
38     return 0;
39 }

dp算法解决背包问题

选择题

1、假定x和y为double型，则表达式x=2，y=x+3/2的值是3.00000

3/2是表示int型，int型自动取整变为1，x表示是浮点型，浮点型加整形转换为y 浮点型

2、数组的定义方法

3、计算机操作系统的功能是：管理计算机资源并提供用户接口

4、服务器相关

5、不仔细

6、软件调试技术:

试探法（强行排错法），

回溯法：人工沿着程序的控制流程往跟踪代码，直到找出错误根源为止

对分查找法：缩小错误的范围，

归纳演绎

原因排除法

7、以下值不等于3的表达式是_____________（）

8、以下代码的输出结果是：

1 #include <stdio.h>
2 main()
3 {
4   char a[10]={ ‘1’,‘2’,‘3’,‘4’,‘5’,‘6’,‘7’,‘8’,‘9’,0},*p;
5   int i;
6   i=8;
7   p=a+i;
8   printf("%s
",p-3);
9 }

1 输出会把剩下的全部输出！！！参数是头地址！
2 最后一个数字0对应转义字符 ‘0’，为C语言中字符串的结尾。
3 因为输出%s,结果是6789;
4 如果输出%c,结果是6；
5 字符串的结束标志是0和''，注意'0'不是结束标志.strlen是以0和''计算长度的 不包含0和''。sizeof计算占用字节大小时包含0和''所占的字节

解析

%s是输出字符串，这个数组是字符串数组，`/0’是在最后，所以会将/0之前的所有数据全部输出

9、直接递归调用和间接递归调用

直接递归调用就是在函数a（或过程）中直接引用（调用）函数a本身
间接递归调用就是在函数a（或过程）中调用另外一个函数b，而该函数b又引用（调用）了函数a

10、从编程的角度考虑，是否存在 i+1<i ?

存在，加入计算机系统是32位的，int i = 4294967296 - 1; i = i+1; 此时i = 0，即i+1<i (注4294967296是2的32次方)

11、如何判断一个操作系统是16位的还是32位的？

12、字符串“alibaba”有（）个不同的排列？

方法一：

7个字符的全排列是7!=5040，又3个a和2个b有重复，所以总的是7!/2!/3!= 420

方法二：

27、公司真题练习

(1)链表使用冒泡进行排序---首先自己要创建链表，这里使用的是一阶指针创建的链表，和第一次自己写的链表是不一样的(那个是使用的二阶指针)

题目链接

 1 #include <iostream>
 2 using namespace std;
 3 struct node {
 4     int val;
 5     struct node *next;
 6 };
 7 void initList(node *head) {
 8     //head = new node;
 9     head->val = 0;
10     head->next = nullptr;
11 
12 }
13 
14 //在这个应用中表明使用一阶指针作为形参,一阶指针作为实参，在子函数中改变head的值也是可以改变主函数中的实参的值的
15 void insertDatabyHead(node *head) {
16     node *tmp;
17     int n;
18     int x;
19     cin >> n;
20     while (n != 0) {
21         cin >> x;
22         tmp = new node;
23         tmp->val = x;
24         tmp->next = head->next;
25         head->next = tmp;
26         --n;
27     }
28 }
29 void list_sort(node *head) {
30     for (node* p = head->next; p != nullptr; p = p->next) {    //p初始化为head->next也是为了不比较头节点中保存的值(这个值是默认值0)
31         for (node* q = p->next; q != nullptr; q = q->next) {
32             if ((p->val) > (q->val)) {
33                 int tmp = q->val;
34                 q->val = p->val;
35                 p->val = tmp;
36             }
37         }
38     }
39 }
40 
41 int main() {
42     node *head = new node;
43     initList(head);
44 
45     initList(head);
46     insertDatabyHead(head);
47     list_sort(head);
48 
49     while (head != nullptr) {
50         head = head->next;          //放在前面的目的是为了不打印头结点默认指向的值(0)
51         if (head != nullptr)
52             cout << head->val << " ";
53     }
54     cout << endl;
55 
56 
57     system("pause");
58     return 0;
59 }

View Code

注意：

这里除了创建链表使用的一阶指针外，使用的冒泡排序也和以前的思路是不一样的，以前的思路是这个样子的：

1 for (int i = 0; i < s.size() - 1; ++i) {
2     for (int j = 0; j < s.size() - i - 1; ++j) {
3         if (s[j] > s[j + 1]) {
4             //交换s[j]和s[j+1]
5         }
6     }
7 }

而这里使用冒泡排序的思路是：

1 for (int i = 0; i < s.size(); ++i) {
2     for (int j = i + 1; j < s.size(); ++j) {
3         if (s[i] > s[j]) {
4             //交换s[i]和s[j]
5         }
6     }
7 }

(2)栈排序

栈排序。编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

 1 class SortedStack {
 2 public:
 3     SortedStack() {
 4 
 5     }
 6     
 7     void push(int val) {
 8         if(!data.empty() && val > data.top()){
 9             //将data中小于val的值全部放到辅助栈help中去
10             while(!data.empty() && val>data.top()){
11                 int tmp=data.top();
12                 data.pop();
13                 help.push(tmp);
14             }
15             data.push(val);
16         }
17         else
18             data.push(val);
19         
20         //再将辅助栈中的元素再放会data栈中去
21         while(!help.empty()){
22             int tmp=help.top();
23             help.pop();
24             data.push(tmp);
25         }
26     }
27     
28     void pop() {
29         if(!data.empty())
30             data.pop();
31     }
32     
33     int peek() {
34         if(!data.empty())
35             return data.top();
36         return -1;
37     }
38     
39     bool isEmpty() {
40         return data.empty();
41     }
42 private:
43     stack<int> data;
44     stack<int> help;
45 };
46 
47 /**
48  * Your SortedStack object will be instantiated and called as such:
49  * SortedStack* obj = new SortedStack();
50  * obj->push(val);
51  * obj->pop();
52  * int param_3 = obj->peek();
53  * bool param_4 = obj->isEmpty();
54  */

使用双栈实现栈排序代码实现

思路举例：

/*
栈排序
入栈的思路
加入此时栈data中的元素依次是12、18、19、32(肯定是排序好了的)
此时要将20入栈，那么需要一个辅助栈help。
(1)首先发现20比12、18、19都要大，那么依次将12、18、19添加到help栈中，加入完成后help栈中栈顶到栈尾的元素依次是19、18、12并依次将12、18、19从data栈中出栈，然后将20添加到栈data中；此时data栈中栈顶到栈尾的元素依次是20、32
(2)然后将辅助栈中的元素依次出栈，并添加到data栈中，添加完毕后data栈中栈顶到栈尾的元素依次是12、18、19、20、32
*/

题目链接

(3)最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

自己写的，但是超时

 1 class MinStack {
 2 public:
 3     /** initialize your data structure here. */
 4     MinStack() {
 5         
 6     }
 7     
 8     void push(int x) {
 9         data.push(x);
10     }
11     
12     void pop() {
13         if(!data.empty())
14             data.pop();
15     }
16     
17     int top() {
18         if(!data.empty())
19             return data.top();
20         return -1;
21     }
22     
23     int getMin() {
24         int tmp=0;
25         while(!data.empty()){
26             tmp=data.top();
27             help.push(tmp);
28             data.pop();
29             if(tmp<=data.top()){
30                 help.push(data.top());
31                 data.pop();
32             }
33             else{
34                 tmp=data.top();
35                 help.push(data.top());
36                 data.pop();
37             }
38         }
39         //复原data中的数据
40         while(!help.empty()){
41             data.push(help.top());
42             help.pop();
43         }
44         return tmp;
45     }
46 private:
47     stack<int> data;
48     stack<int> help;
49 };
50 
51 /**
52  * Your MinStack object will be instantiated and called as such:
53  * MinStack* obj = new MinStack();
54  * obj->push(x);
55  * obj->pop();
56  * int param_3 = obj->top();
57  * int param_4 = obj->getMin();
58  */

View Code

正确的方法：

按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；

当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；

在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

 1 class MinStack {
 2 public:
 3     /** initialize your data structure here. */
 4     MinStack() {
 5         
 6     }
 7     
 8     void push(int x) {
 9         data.push(x);           //data栈中存储正常插入的数据，data和help中元素的个数始终是一样的
10         if(help.empty())        //如果辅助栈help为空，则直接插入到hekp中
11             help.push(x);
12         else{                   //help中插入的是当前要插入的值x与help栈顶的较小值  
13             int tmp=help.top();
14             if(x<tmp)
15                 help.push(x);
16             else
17                 help.push(tmp);
18         }
19     }
20     
21     void pop() {
22         if(!data.empty()){   //data和help中元素的个数始终是一样的
23             data.pop();
24             help.pop();
25         }
26     }
27     
28     int top() {
29         if(!data.empty())
30             return data.top();
31         return -1;
32     }
33     
34     int getMin() {
35         return help.top();
36     }
37 private:
38     stack<int> data;
39     stack<int> help;
40 };
41 
42 /**
43  * Your MinStack object will be instantiated and called as such:
44  * MinStack* obj = new MinStack();
45  * obj->push(x);
46  * obj->pop();
47  * int param_3 = obj->top();
48  * int param_4 = obj->getMin();
49  */

View Code

题目链接此处可以查看图片动画

时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)O(1)。因为栈的插入、删除与读取操作都是 O(1)O(1)，我们定义的每个操作最多调用栈操作两次。

空间复杂度：O(n)O(n)，其中 nn 为总操作数。最坏情况下，我们会连续插入 nn 个元素，此时两个栈占用的空间为 O(n)O(n)。

(4)最大子序列

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

使用一位数组动态规划的方法：

1 /*
2 dp[i]表示以nums[i]为结尾的最大子序列的和
3 dp[0]=nums[0]     //初始状态
4 dp[i]=max(dp[i-1]+nums[i] , nums[i])  //状态方程
5 */

代码实现

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int numsSize=nums.size();
 5         if(numsSize==0)
 6             return INT_MIN;
 7         else if(numsSize==1)
 8             return nums[0];
 9         vector<int> dp(numsSize);
10         dp[0]=nums[0];
11         //int res=0;     加入nums={-2,-1}最大子序列的值就是-1了啊
12         int res=dp[0];   //初始值非常重要！！！
13         for(int i=1;i<numsSize;++i){
14             dp[i]=max(dp[i-1]+nums[i],nums[i]);
15             res=max(dp[i],res);
16         }
17         return res;
18     }
19 };

View Code

题目链接

(5)求最大斜率(第k大斜率)

题目描述：

在平面直角坐标系上，有n个不同的点。任意两个不同的点确定了一条直线。请求出所有斜率存在的直线按斜率从大到小排序后，第k条直线的斜率为多少。为了避免精度误差，请输出斜率向下取整后的结果。（例如：[1.5]=1，[-1.5]=-2）

输入描述：

第一行，包含两个正整数n和k。

接下来n行，每行包含两个整数xi,yi，表示每个点的横纵坐标。

1 ≤ n≤ 100000 ， k ≤ n ， |xi|, |yi| ≤ 10^8

输出描述：

输出一行，包含一个整数，表示第k小的斜率向下取整的结果。

代码实现：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 using namespace std;
 5 
 6 struct point {
 7     int x;
 8     int y;
 9     bool operator <(point & p) {
10         return x < p.x || ((x == p.x) && y < p.y);
11     }
12 };
13 
14 //for vector sort()
15 bool cmp(int a, int b) {
16     return a > b;
17 }
18 
19 
20 int main() {
21     const int num = 1e5;
22     int n = 0, k = 0;
23     cin >> n >> k;
24     point p[num];     //这里使用point p[n]会报错不能使用n
25 
26     //输入点
27     for (int i = 0; i < n; ++i) {
28         cin >> p[i].x >> p[i].y;
29     }
30 
31     //对这些点根据x进行排序
32     sort(p, p + n);
33 
34     //计算相邻两个点之间的斜率,相邻两个点之间最大的斜率即所有点之间最大斜率
35     vector<double> vec;
36     for (int i = 0; i < n - 1; ++i) {
37         if (p[i].x == p[i + 1].x) {
38             continue;
39         }
40         double curSlop = (p[i].y - p[i + 1].y) / (p[i].x - p[i + 1].x);     //这次情况下把这里的绝对值去掉就好了    
41         vec.push_back(curSlop);
42     }
43     sort(vec.begin(), vec.end(), cmp);
44     cout << vec[k - 1] << endl;
45 
46     system("pause");
47     return 0;
48 }

View Code

原理：

以3个点A、B、C为例：

假如ABC三点共线，那么斜率都已一样

假如ABC三点不共线，那么对A、B、C三点按照x轴数据进行排序后，此时的顺序假如还是A、B、C，那么他们可以构成一个三角形(A是左顶点、B是上顶点、C是右顶点)，那么AC直线的斜率一定是中间大小的斜率，AB、BC中一定有一个比AC斜率大和比AC斜率小的。

(6)求一个数的平方和(工商银行软件开中心2019年笔试)

判断一个数字能不能由若干个数字的平方和组成，如果可以就从小到大输出这些数字，不可以就输出“NA”，例如输入13，输出4 9 ；输入5 输出1 4

 1 #include <iostream>
 2 #include <math.h>
 3 #include <vector>
 4 using namespace std;
 5 
 6 void findPowofNum(int num) {
 7     int tmp = num;             //备份num
 8     vector<int> arr;
 9     while (tmp > 0) {              //在while循环找到num的所有有可能组成num的平方和的数，这些数的平方和有可能比num大或者是比num小
10         int m = sqrt(tmp);         //如sqrt(5)=2.23067,则m=2,由于m是int型,所以会将sqrt()函数的返回值截取为int类型的
11         arr.push_back(m*m);
12         if (m != 1) {
13             tmp -= pow(m, 2);
14         }
15         else {
16             break;
17         }
18     }
19     int sum = 0;
20     for (int i = 0; i < arr.size(); ++i) {
21         sum += arr[i];
22     }
23     if (sum == num) {                //验证一下,arr内的数的平方和是否等于num
24         for (int i = arr.size()-1; i >= 0;--i) {
25             cout << arr[i] << endl;
26         }
27     }
28     else {
29         cout << "NA" << endl;
30     }
31 }
32 
33 int main() {
34     int num;
35     cin >> num;
36     findPowofNum(num);
37 
38     system("pause");
39     return 0;
40 }

View Code

涉及到sqrt()函数的使用，如sqrt(5)的返回值是一个浮点数，而int m = sqrt(5); 此时m=2

28、视频刷题(leetcode)

(1)分发饼干(easy)

题目描述：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。

一个小朋友最多只能拥有一块饼干。

 1 class Solution {
 2 public:
 3     int findContentChildren(vector<int>& g, vector<int>& s) {
 4         /*g为小孩的胃口值，s为你拥有的饼干的尺寸
 5          * 实现的策略为:
 6          * 首先将g和s进行排序，然后遍历每个小孩的需求g，找到一个最小的且满足这个小孩的需求的s[j]
 7         */
 8         sort(g.begin(),g.end());
 9         sort(s.begin(),s.end());
10         int j=0,res=0;
11         //遍历每个小孩的需求
12         for(int i=0;i<g.size();++i){
13             //如果有饼干(j<s.size())且第j块饼干不不满足第i个小孩,
14             //那么就继续找下一块满足第i个小孩且尺寸最小的饼干
15             //(因为已排序,所以找到的第j块饼干一定是最小的且满足第i个小孩)
16             while(j<s.size()&&g[i]>s[j])
17                 ++j;
18             if(j<s.size()&&g[i]<=s[j]){
19                 res++;
20                 ++j;                      //表示第j块饼干已经被用掉了,下一个小孩不能用这个第j块饼干了
21             }
22         }
23         return res;
24     }
25 };

View Code

/*g为小孩的胃口值，s为你拥有的饼干的尺寸
* 实现的策略为:
* 首先将g和s进行排序，然后遍历每个小孩的需求g，找到一个最小的且满足这个小孩的需求的s[j]
*/

 1 class Solution {
 2 public:
 3     int findContentChildren(vector<int>& g, vector<int>& s) {
 4         /*g为小孩的胃口值，s为你拥有的饼干的尺寸
 5          * 实现的策略为:
 6          * 首先将g和s进行排序，然后遍历每个小孩的需求g，找到一个最小的且满足这个小孩的需求的s[j]
 7         */
 8         sort(g.begin(),g.end());
 9         sort(s.begin(),s.end());
10         int j=0,res=0;
11         //遍历每个小孩的需求
12         for(int i=0;i<g.size();++i){
13             //如果有饼干(j<s.size())且第j块饼干不不满足第i个小孩,
14             //那么就继续找下一块满足第i个小孩且尺寸最小的饼干
15             //(因为已排序,所以找到的第j块饼干一定是最小的且满足第i个小孩)
16             while(j<s.size()&&g[i]>s[j])
17                 ++j;
18             if(j<s.size()&&g[i]<=s[j]){
19                 res++;
20                 ++j;                      //表示第j块饼干已经被用掉了,下一个小孩不能用这个第j块饼干了
21             }
22         }
23         return res;
24     }
25 };

View Code

(2)柠檬水找零钱(easy)

题目描述：

由于此题限定顾客的钱只能是5、10、20那就很简单了，只需要遍历每个顾客的钱就好了，然后判断有没有对应的零钱，对于顾客的20元钱，找钱的策略是优先考虑10+5，其次是再考虑5+5+5，实现的方法是先用if判断有没有10元的零钱，如果有那就使用这种策略。

 1 class Solution {
 2 public:
 3     bool lemonadeChange(vector<int>& bills) {
 4         int fives=0,tens=0;      //定义收到的5美元、10美元的个数
 5         for(auto b:bills){
 6             if(b==5){
 7                 fives++;         //如果收到的是5美元,那么fives自加1
 8             }
 9             else if(b==10){   
10                 if(fives!=0){    //如果收到的是10美元，且有5美元可以找，那么10美元的个数加1,5美元的个数减1
11                     tens++;
12                     fives--;
13                 }
14                 else
15                     return false;  //否则返回false
16             }
17             else{                //如果收到的是20美元
18                 int t=15;        //定义要回找的钱数
19                 if(tens != 0){   //要回找15美元，最好的方案是10+5,其次的方案是5+5+5
20                     tens--;
21                     t-=10;
22                 }
23                 while(t!=0 && fives!=0){  //加while循环是为了防止出现没有10美元的零钱,需要使用5+5+5找回
24                     t-=5;
25                     fives--;
26                 }
27                 if(t!=0){         //如果经过上面的while循环之后不能正常的找回15美元，那么返回false
28                     return false;
29                 }
30             }
31         }
32         return true;
33     }
34 };

View Code

(3)数组内跳跃游戏

题目描述：

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置

 1 class Solution {
 2 public:
 3     bool canJump(vector<int>& nums) {
 4         //dist用于记录当前位置可以跳到的最远距离
 5         int dist=0;
 6         /*
 7          *遍历这个数组,然后不断的更新最远距离
 8          *条件dist>=i表示可以到达位置i
 9          *nums[i]+i表示从位置i可以跳到的位置
10         */
11         for(int i=0;i<nums.size()&&dist>=i;++i)
12             dist=max(nums[i]+i,dist);
13         //如果可以跳到的最远距离大于数组中数据的个数，表示可以到达数组的最后一个位置
14         return dist>=(int)nums.size()-1;
15     }
16 };

View Code

题目链接

需要注意的是：nums.size()的返回值是一个无符号整数(unsigned int)，而-1是一个有符号的，所以nums.size()-1返回值是一个无符号整数，假如nums.size()=0,那么此时nums.size()-1的结果就不是-1了，而是2^32-1,因为-1对应无符号数是2^32-1

举例如下：

1 cout<<0u-1<<endl;   //0u表示0是一个无符号整数,此时输出2^32-1
2 cout<<(int)(0u-1)<<endl;   //此时输出-1

View Code

29、同花顺笔试小的知识点总结

(1)string str; char s='a'; str+=a;是正确的

在vs2017下的测试：

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 int main() {
 6     char c = 'a';
 7     string str;
 8     str += c;
 9     cout << str << endl;
10 
11 
12     system("pause");
13     return 0;
14 }

(2)在.h文件和在.cpp文件中创建static变量的问题

1）在.h文件中创建static变量，并在其他的.cpp文件中使用

在A.h文件中：

1 #pragma once
2 static int a = 5;

在A.cpp中没有任何定义，也可以不定义A.cpp文件

在B.h中：

1 #pragma once
2 void bFun(void);  //声明一个函数

在B.cpp中：

 1 #include <iostream>
 2 #include "A.h"        //在A.h文件中定义的静态变量a会被分配一次内存
 3 #include "B.h"
 4 using namespace std;
 5 
 6 void bFun() {
 7     a++;
 8     cout << "bFun():a=" << a << endl;
 9     cout << "bFun():&a=" << &a << endl;
10 }

在main.cpp中：

 1 #include <iostream>
 2 #include "A.h"        //在A.h文件中定义的静态变量a会被分配一次内存
 3 #include "B.h"
 4 using namespace std;
 5 
 6 int main() {
 7     bFun();
 8 
 9     cout << "main():a=" << a << endl;
10     cout << "main():&a=" << &a << endl;
11 
12     system("pause");
13     return 0;
14 }

结论：在.h文件中使用static定义的变量不是全局变量，因为他们的地址是不同的，引用一次该头文件，在头文件里的static变量就申请一次内存。

那如果将A.h中的static int 改为 int a; 此时会报错变量a重复定义。由此可见，定义在头文件中的全局变量，该头文件每被#include一次，该文头文件中的变量就会被声明定义一次。

2)如果将静态变量定义在A.cpp文件中呢

在A.h中：

#pragma once

在A.cpp中：

1 #include "A.h"
2 static int a = 5;

在main.cpp中：

1 #include <IOSTREAM>
2 #include "A.h"
3 using namespace std;
4  
5 int main(void)
6 {
7     cout<<a<<endl;    
8     return 0;
9 }

此时编译会报错，即静态变量只可以在本cpp文件中使用，不可以被其他的cpp文件使用。

那么在A.cpp中的文件非得main.cpp中使用呢？方法是去掉static，加上extern

A.h:

1 #pragma once

A.cpp

1 #include "A.h"
2 int a = 5;

B.h

1 #ifndef _B_H
2 #define _B_H
3 void Bfun(void);
4 #endif

B.cpp

 1 #include "B.h"
 2 #include "A.h"
 3 #include <IOSTREAM>
 4 using namespace std;
 5 extern int a;                       //表示使用其余cpp文件中的a变量
 6 void Bfun(void)
 7 {
 8     a++;
 9     cout<<"Bfun: a="<<a<<",addr="<<&a<<endl;
10 }

main.cpp

 1 #include <iostream>
 2 #include "A.h"
 3 #include "B.h"
 4 using namespace std;
 5 extern int a;                      //表示使用其余文件中的a变量
 6 int main(void)
 7 {
 8     Bfun();
 9     cout<<"main: a="<<a<<",addr="<<&a<<endl;
10     return 0;
11 }

(3)数组、字符串赋值相关

1 char s1[3]={'a','b','c'};        //正确,但此时s1是一个字符数组
2 char s2[4]={'a','b','c',''};   //正确,但此时s2是一个字符串,显式的包含了空字符,需要注意的是这里必须是s2[4],即字符个数+一个空字符
3 char s3[4]="abc";                //正确,s3是一个字符串,隐式的包含了空字符,需要注意的是这里必须是s3[4],即字符个数+一个空字符
4 char* s; s="abc";                //正确,s执行字符串abc的首地址

Last、遇到的坑

1、string对象不可以像数组那样随便赋值 Last1

1 ...
2 string str1 = "Hello-67aa";
3 string str2;
4 for(int i=0; i<str1.size();i++)
5     str2[i] = str1[i];
6 
7 这样的赋值操作是不对的，str将始终为空！！
8 直接使用str2 = str`就好了

string对象赋值的问题

https://leetcode-cn.com/problems/longest-palindrome/

笔试练习

目录

1、完成find函数---在一个二维数组(vector对象)中查找有无一个数字，难点在于我不知道如何获取该二维数组的行数和列数

2、补充：关于C++中vector<vector<int>> A的使用

3、替换空格为其他字符题

4、将字符串或数组元素反转(使用reverse()函数)

5、旋转数组查找最小值

6、指针练习（选择题）

7、数组的简单操作(使用vector将一个数组中的奇数和偶数分开)

8、回文数组

9、斐波那契数列基本实现与优化

10、n级台阶问题：每次只能上一个台阶或上两个台阶，此类问题试剂上就是斐波那契数列问题

11、删除相同的字符串，string变量是不能像数组那样赋值的！！！

12、使用两个栈实现一个队列

13、已排序好的队列移动几个数字，求移动数字的个数(队列最小修改)

15、字符反转(使用reverse()函数)

16、二叉树深度相关

(1)二叉树最小深度

(2)二叉树最大深度或者是二叉树深度

(3)判断一棵树是否为平衡二叉树

17、十六进制字符串转换为十进制，并求连续的十六进制最大值

(1)十六进制转换为十进制方法二(使用cmath头文件中的pow()函数)

18、环形路上有n个加油站

题目描述

19、糖果分配问题

20、使用map容器查找一个字符串中每个字符出现的次数

21、使用map容器找到一个vector<string>中灭个字符串出现的次数

22、华为牛客网机试练习

(1)计算字符串最后一个单词的长度

(2)明明的随机数(多个数字连续输入) 使用set容器，set容器可以自动排序

(3)求质子数

(4)蛇形矩阵

(5)提取不重复的数字

(6)合并表记录(使用map,将键相同的对应的值相加)

(7)字符个数统计(不包括重复字符),注意字符范围表示方法,使用map容器

(8)float型数据十进制转二进制

23、剑指offer

(1)一只青蛙一次可以跳1级台阶、2级台阶、3级台阶、...、n级台阶

(2)矩形覆盖问题，依旧是斐波那契数列问题

题目描述

(3)使用位操作计算一个整数二进制包含1的个数(整数包括正整数、负整数和0)

(4)pow()函数实现

24、笔试

(1)快速幂+取余 快速幂即上面的pow()函数实现

(2)计算算数表达式字符串中匹配的字符串个数、不匹配的左括号个数、不匹配的右括号个数

(3)完美幂,例如39=3^3+3^2+3^1中的[3 2 1]是39的完美幂,而33=3^3+3^1+3^1中幂有重复的1则不是完美幂

(4)受到疫情的影响，某手员工工位问题

(5)智能手机产能

(6)数位之积

(7)字符串压缩后展开

(9)工作休息or体育馆

(10)输入n组已经排序好的数据,输出这n组中前K大的数据

(11)一个满二叉树,第一层结点编号为1，第二层结点编号为2、3... 求编号为x在第k层的祖先

(12)已知Q，求使n!含有Q个0的最小正整数n

(13)写出求a和b最大公约数的函数gcd() -----> 求数组中最简真分数的个数

(14)求一个n进制的数除以m(十进制)的余数---乐鑫科技秋招提前批---因为一个getchar()整道题没有AC

(15)求一组数中选出四组数字，该四组数作为平行四边形的四条边，然后求该平行四边形的最大面积

(5)单调栈结构

(16)20200907中兴笔试

(17)20201011字节笔试

(18)20201012百度测试笔试

25、leetcode

(1)整数反转(涉及到int型变量溢出的问题)

(2)判断回文数

(3)判断回文字符串

最长回文串

(4)计算完全二叉树结点的个数(使用层序遍历即可)

5)无重复字符的最长字串

(6)字符串转数字atoi()函数的实现

(7)寻找两个有序数组的中位数 涉及到不同数据类型相除先进行转换的问题

(9)n!含有0的个数

(10)字母异位词分组 使用的数据结构为map<string,vector<string>> mp;

(11)比较含退格的字符串---使用栈stack,需要注意的是stac<char> sta; 不可以使用sta[1]访问栈中的元素,要使用sta.top();

string对象中添加字符或者是字符串的方法

(12)Z型字符串

(13)单词规律

(14)24点游戏：输入4个数执行加减乘除操作后是否可以得到24

(15)删除字符串中出现次数最少的字符

(16)岛屿数量(dfs深度优先搜索解决)

岛屿数量(bfs广度优先搜索解决)

(1)快速幂+取余快速幂即上面的pow()函数实现

(7)寻找两个有序数组的中位数涉及到不同数据类型相除先进行转换的问题

(10)字母异位词分组使用的数据结构为map<string,vector<string>> mp;