Gunther的博客

一个人可以非常清贫、困顿、低微，但是不可以没有梦想。只要梦想一天，只要梦想存在一天，就可以改变自己的处境。——奥普拉

原创单向链表逆序输出

递归------ 消耗内存空间-栈,空间复杂度O(n)// 直接递归实现核心代码片段public void reverse(head){ // 递归终止条件 if(head.next == null){ print(head); return; } // 下一层需要做的事儿 reverse(head.next); // 本层需要做的事儿 print(head);}...

2020-02-15 21:46:53 647

原创安卓语音合成,上传文本到服务器，接受服务器返回字段进行处理。

实习的时候，上面先给我一个小任务。在安卓上先测试是否能建立到后端的http的post请求。后端的服务器开发者给我的接口是只接受三个字段，分别是{“src_text”:“水水水水水水水水水水水水水水水水水水”,“VerifyValue”:“36”,“Id”:“fs13a2ztDd2gK1UHqXZa”}我准备在安卓上，当点击提交按钮的时候，exitview上面的内容即文本内容srctext。后面...

2019-04-19 17:45:34 437 2

原创 Java多线程系列-- join()

join() 定义在Thread.java中。join() 的作用：让“主线程”等待“子线程”结束之后才能继续运行。这句话可能有点晦涩，我们还是通过例子去理解：首先写三个类：DataSourcesLoad.javapackage tast;import java.util.Date;import java.util.concurrent.TimeUnit;public class...

2019-04-07 10:22:00 338

原创华为机试2020年机试第二题，小蜜蜂采蜜最短路径

奇怪思路是对的，就是没通过#include<iostream>#include<string>#include<algorithm>#include<vector>#include<map>#include<set>#include<sstream>#include<assert.h>...

2019-03-27 23:46:51 7725

原创华为机试笔记

只记录没第一次做出来的。1.质数因子先学习了一下如何c++ 数字与字符串的相互转换首先推荐用用C++的stringstream。主要原因是操作简单。数字转字符串，int float类型同理#include <string>#include <sstream>int main(){ double a = 123.32; string res...

2019-03-27 09:33:51 636

原创华为 c++ 最高分是多少，简单错误记录，解数独，2020模拟题,.....

max_element函数#include<iostream>#include<string>#include<algorithm>#include<vector>#include<map>#include<stack>#include<sstream>#include<assert.h&g...

2019-03-24 10:32:45 336

原创 [笔试题]找数组中最长和为0连续子序列

1、暴力求解法很容易想到，用两个下标i，j来遍历数组，然后将i和j之间的元素求和，这样的方法比较简单，因为下标i和j都遍历了数组，所以时间复杂度有O（n2）O（n^2）O（n2），加上求和，所以总的时间复杂度是O(n3)O(n^3)O(n3)，而空间存储只需要保留i和j还有一个最大长度的变量，所以空间复杂度为O（1）O（1）O（1）.2、动态规划法上面方法耗时主要在求和，如果可以将部分求和的...

2019-03-21 17:52:25 2180

原创链表反转

//第一种方法是：非递归方法/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* ReverseList(ListN...

2019-02-28 21:21:42 154

原创 leetcode300 最长上升子序列

广场上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，请你帮忙找出身高依次递增的子序列。例如队伍的身高数据是（1、7、3、5、9、4、8），其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。输入描述:输入包含多组数据，每组数据第一行包含一个正整数n（1≤n≤1000）。紧接着第二行包含n个正整数m（1≤n≤10000），代...

2019-02-28 19:46:00 225

原创最小的K个数

最小的K个数:class Solution {public: int partition_k(vector<int> &input, int begin,int end) { int pivot = input[begin]; while (begin<end) { while (...

2019-02-25 20:39:30 158

原创寻找和为定值的多个数

题目：输入两个整数 n 和 m，从数列1，2，3…n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。code: 1 #include&lt;list&gt; 2 #include&lt;iostream&gt; 3 using namespace std; 4 5 list&lt;int&gt;list1; 6 void find_fact.

2019-02-25 20:20:45 521

原创寻找两个字符串间的相同子串c++

寻找两个字符串间的相同子串c++://思路：动态规划经典问题，加一个start标记即可,注意将较短子串最先出现的那个输出#include&lt;iostream&gt;#include&lt;vector&gt;#include&lt;string&gt;using namespace std;void findMaxCommonStr(string s1,string s2){

2019-02-25 12:47:24 7519

原创排序总结

快速排序：int partition(int arr[], int left, int right) { int i = left, j = right; int tmp = arr[left]; while (i &lt; j) { while (i &lt; j &amp;&amp; arr[j] &gt; tmp) j--;...

2019-02-15 10:42:38 165

原创 100. 相同的树

100. 相同的树class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p == nullptr&&q == nullptr)return true; if ((!p&&q)||(!q&&p)||(q->val != p->va...

2019-01-25 00:10:07 123

原创 98. 验证二叉搜索树

98. 验证二叉搜索树分析这道验证二叉搜索树有很多种解法，可以利用它本身的性质来做，即左<根<右，也可以通过利用中序遍历结果为有序数列来做，下面我们先来看最简单的一种，就是利用其本身性质来做，初始化时带入系统最大值和最小值，在递归过程中换成它们自己的节点值，用long代替int就是为了包括int的边界条件，代码如下：递归的：class Solution { public:...

2019-01-24 16:36:12 160

原创 96. 不同的二叉搜索树/95. 不同的二叉搜索树II

95. 不同的二叉搜索树II给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例:输入: 3输出:[[1,null,3,2],[3,2,null,1],[3,1,null,null,2],[2,1,3],[1,null,2,null,3]]解释:以上的输出对应以下 5 种不同结构的二叉搜索树：正好按照顺序，左边比i小，右边比i大。划分左右子树，递...

2019-01-24 13:25:37 333

原创 94. 二叉树的中序遍历/144. 二叉树的前序遍历/145. 二叉树的后序遍历

94. 二叉树的中序遍历递归版本 class Solution { public: vector&amp;lt;int&amp;gt;res; vector&amp;lt;int&amp;gt; inorderTraversal(TreeNode* root) { if(root==nullptr) return res; inorderTraversal(root-&amp;gt;le

2019-01-23 23:58:46 172

原创 93. 复原IP地址

93. 复原IP地址分析：为便于使用，常以XXX.XXX.XXX.XXX形式表现，每组XXX代表小于或等于255的10进制数。所以说IP地址总共有四段，每一段可能有一位，两位或者三位，范围是[0, 255]，题目明确指出输入字符串只含有数字，所以当某段是三位时，我们要判断其是否越界（>255)，还有一点很重要的是，当只有一位时，0可以成某一段，如果有两位或三位时，像 00， 01， 00...

2019-01-23 19:53:08 193

原创 92. 反转链表 II

就用1，2，3，4，5 画个图就行。class Solution {public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (m &gt; n || m &lt; 0)return nullptr; ListNode *dummy = new ListNode(0); dummy-&gt;next =...

2019-01-21 20:58:04 175

原创 91. 解码方法

91. 解码方法题目：一条包含字母 A-Z 的消息通过以下方式进行了编码：‘A’ -> 1‘B’ -> 2…‘Z’ -> 26给定一个只包含数字的非空字符串，请计算解码方法的总数。示例 1:输入: “12”输出: 2解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。示例 2:输入: “226”输出: 3解释: 它可以解码为 “B...

2019-01-21 15:00:16 739

原创 89. 格雷编码

摘自[1][2][3]:G：格雷码 B：二进制码 n：正在计算的位根据格雷码的定义可得：G(n) = B(n+1) XOR B(n)AC code:// Binary to grey code class Solution { public: vector<int> grayCode(int n) { vector<int>res; for ...

2019-01-19 22:20:09 548

原创 88. 合并两个有序数组

88. 合并两个有序数组4 ms:class Solution {public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i =m; int j=0; while(j<n)...

2019-01-19 20:44:22 802

原创 87. 扰乱字符串

87. 扰乱字符串简单的说，就是s1和s2是scramble的话，那么必然存在一个在s1上的长度l1，将s1分成s11和s12两段，同样有s21和s22.那么要么s11和s21是scramble的并且s12和s22是scramble的；要么s11和s22是scramble的并且s12和s21是scramble的。hard.4ms 暴力递归ac。class Solution { publi...

2019-01-19 14:48:22 480

原创 86. 分隔链表

86. 分隔链表[1]思路：从前向后遍历链表，将结点值小于 x 的结点放入到新链表 1 中，将结点值大于等于 x 的结点放入新链表 2 中。最后，将新链表 2 拼接在新链表 1 后面即可。注意的几点：常见的 ListNode *pHead=new ListNode(0);//新建辅助节点收尾操作置空4ms: class Solution { public: ListNode...

2019-01-19 10:42:23 188

原创 85. 最大矩形

85. 最大矩形hard[1]分析：此题是之前那道的 84.直方图中最大的矩形的扩展，这道题的二维矩阵每一层向上都可以看做一个直方图，输入矩阵有多少行，就可以形成多少个直方图，对每个直方图都调用 84.直方图中最大的矩形中的方法，就可以得到最大的矩形面积。那么这道题唯一要做的就是将每一层构成直方图，由于题目限定了输入矩阵的字符只有 ‘0’ 和 ‘1’ 两种，所以处理起来也相对简单。方法...

2019-01-18 23:10:17 124

原创 84.直方图中最大的矩形

直方图中最大的矩形分析：遍历数组，每找到一个局部峰值，然后向前遍历所有的值，算出共同的矩形面积，每次对比保留最大值，代码如下：class Solution { public: int largestRectangleArea(vector<int> &height) { int res = 0; for (int i = 0; i < heig...

2019-01-18 22:41:09 558

原创 82. 删除排序链表中的重复元素 II/83. 删除排序链表中的重复元素

82. 删除排序链表中的重复元素 II示例 1:输入: 1->1->2输出: 2直接写过这题在剑指offer，详细解释 class Solution { public: //新建一个头节点，两个辅助指针 ListNode* deleteDuplicates(ListNode* head) { ListNode *p = new ListNode(0...

2019-01-18 17:27:45 144

原创矩阵中的路径/79. 单词搜索

回溯法class Solution {public: bool hasPath(char* matrix, int rows, int cols, char* str) { if (!matrix || rows &amp;amp;lt;= 0 || cols &amp;amp;lt;= 0 || !str)return false; int *visited = new int[rows*cols]; me...

2019-01-17 22:45:04 337 1

原创 77. 组合/78.子集/90. 子集 II

77. 组合 class Solution { public: void help(vector&amp;amp;amp;amp;amp;amp;amp;amp;lt;vector&amp;amp;amp;amp;amp;amp;amp;amp;lt;int&amp;amp;amp;amp;amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;amp;amp;amp;gt;&amp;a

2019-01-17 15:21:33 233

原创 76. 最小覆盖子串

76. 最小覆盖子串分析：[1]采用滑动窗口，窗口有左右边界，先通过扩展右边界找出一个包含T中所有字符的子串，然后收缩左边界，直到不能再收缩。记录此时的子串。然后收缩左边界，继续扩展右边界，直到再找到满足要求的子串，和上次的进行比较，保存更小的子串。返回执行，直到右边界到达S串尾，且左边界不能再收缩。code： class Solution { public: string minW...

2019-01-17 14:08:56 213

原创 Leetcode 75. 颜色分类

Leetcode 75. 颜色分类分析[1]：采用两个指针，是0就和左边的数据交换，是2就和右边的数据交换。因为交换过来的元素仍可能为2，所以再次对此元素进行判断8 ms: class Solution { public: void sortColors(vector<int>& nums) { if (nums.empty())return; int...

2019-01-17 10:11:18 123

原创二维数组的查找，74. 搜索二维矩阵/240. 搜索二维矩阵 II

74. 搜索二维矩阵/二维数组的查找 class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty())return false; //二分查找从左下角或右上角 int m = matrix...

2019-01-16 22:57:45 227

原创 73. 矩阵置零

方法1：赋值另存一个m*n的矩阵，在原矩阵为零的值相应置新的矩阵行和列为零。额外空间为O(m∗n)O(m*n)O(m∗n).方法2：两个数组，bool[m] 和 bool[n] 分别存某行有零，后者某列有零。之后根据数组值将原矩阵相应位置置零。额外空间O(m+n)O(m + n)O(m+n)。方法3：看来许久才明白。先对矩阵进行扫描，标记要进行置0的行和列，对要进行置0的行进行标。同时...

2019-01-16 21:36:56 247

原创 71. 简化路径

71. 简化路径总结出规律:这样我们就可以知道中间是"."的情况直接去掉，是"…"时删掉它上面挨着的一个路径，而下面的边界条件给的一些情况中可以得知，如果是空的话返回"/"，如果有多个"/"只保留一个。那么我们可以把路径看做是由一个或多个"/"分割开的众多子字符串，把它们分别提取出来一一处理即可，class Solution { public: string simplif...

2019-01-16 11:03:20 127

原创跳台阶/70. 爬楼梯/变态跳台阶

跳台阶/70. 爬楼梯class Solution {public: int jumpFloor(int number) { if(number==0) return 0; if(number==1) return 1; if(number==2) return 2; int f1=1; int f2=2;...

2019-01-15 21:46:39 459

原创 69. x 的平方根

69. x 的平方根官网上Ac,并不是考察点。 class Solution { public: int mySqrt(int x) { return sqrt(x); } };二分法分析：对于一个非负数n，它的平方根不会大于（n/2+1）,画个图y=xy=\sqrt{x}y=x和y=12xy=\frac{1}{2}xy=21x就知道切点是（1，1）。在[0, n/...

2019-01-15 20:52:44 278

原创 66.加一/67.二进制求和

解析：两种方法都有就是在数组必要时（如999）进行插入操作。方法一： class Solution { public: vector&amp;amp;lt;int&amp;amp;gt; plusOne(vector&amp;amp;lt;int&amp;amp;gt;&amp;amp;amp; digits) { for (int i = digits.size() - 1; i &a

2019-01-15 15:57:00 220

原创 65. 有效数字

65. 有效数字 class Solution { public: //考察全面性 bool isNumber(string s) { int len = s.length(); if (len == 0)return false; int i = 0; while (i < len&&s[i] == ' ')i++;//skip ...

2019-01-15 14:03:55 320

原创 62.不同路径/63. 不同路径 II/64. 最小路径和

62.不同路径Title:有一个机器人的位于一个M×N个网格左上角（下图中标记为’Start’）。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角（下图中标记为’Finish’）。问有多少条不同的路径？注意事项n和m均不超过100Analysis:典型的动态规划问题容易分析出状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1];初...

2019-01-13 22:34:49 157

原创 61. 旋转链表

第一次写出提交这么慢的code 5232ms： class Solution { public: //利用相隔k的两个指针 ListNode* rotateRight(ListNode* head, int k) { if (head == nullptr||k&lt;0)return nullptr; int kStep = 0; ListNode *p...

2019-01-13 20:17:06 115