统计一个数字在排序数组中出现的次数。
1
2
3
| > 输入: nums = [5,7,7,8,8,10], target = 8
> 输出: 2
>
|
想法1：
我的想法，虽然通过了，好像有点麻烦,利用二分查找的思想，找到对应target数字最左边的位置和最右边的位置,
上述例子中即找到第一个8和第二个8的位置。时间效率O(nlogn)，空间效率O(1)，非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| int (vector<int>& nums, int target) {
int length = nums.size();
if(length == 0) return 0;
int left = 0;
int right =length-1;
int targetStart = -1;
int targetend = -1;
int mid;
while(right >= left){
mid = (left + right) >>1;
if(nums[mid] == target){
if(mid == 0){
targetStart = 0;
break;
}
else if(nums[mid-1] < target){
targetStart = mid;
break;
}
}
if(nums[mid] >= target){
right = mid -1;
}
else
left = mid + 1;
}
left = 0;
right = length-1;
while(right >= left){
mid = (left + right) >> 1;
if(nums[mid] == target){
if(mid == length-1){
targetend = length-1;
break;
}
else if(nums[mid+1] > target){
targetend = mid;
break;
}
}
if(nums[mid] > target){
right = mid -1;
}
else
left = mid+1;
}
if(targetStart >= 0 && targetend >=0){
return targetend - targetStart +1;
}
return 0;
}
|
想法2：
利用哈希表
空间效率O(n),时间效率O(n)
1
2
3
4
5
6
7
| int (vector<int>& nums, int target) {
map<int, int> nums_record;
for(size_t i=0;i<nums.size();++i){
nums_record[nums[i]]++;
}
return nums_record[target];
}
|
想法3：剑指Offer上写的递归代码和我想的差不多，就不写出了。
题目53：（2）0-n-1中缺失的数据
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
1
2
3
4
5
| >输入: [0,1,3]
>输出: 2
>输入: [0,1,2,3,4,5,6,7,9]
>输出: 8
>
|
也是上述的思想，没啥大区别。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| int missingNumber(vector<int>& nums) {
int length = nums.size();
if(length == 0) return 0;
int left = 0;
int right = length-1;
int mid;
int missNum = -1;
while(right >= left){
mid = (left + right) >>1;
if(nums[mid] == mid){
if(mid == length-1)
return mid+1;
left = mid +1;
}
if(nums[mid] != mid){
if(mid == 0){
missNum = 0;
break;
}
if(mid > 0 && nums[mid-1] == mid-1){
missNum = mid;
break;
}
right = mid -1;
}
}
return missNum;
}
|
题目53：（3）数组中数值和下标相等的元素
假设一个单调增的数组的每个元素都是整数并且是唯一的。请编写一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{-3,-1,1,3,5}中，数字3和他的下标相等。
思路：也是利用二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int GetNumberSameAsIndex(vector<int>& numbers)
{
int length = numbers.size();
if(length == 0) return 0;
int left = 0;
int right = length-1;
int mid;
while(right >= left){
mid = (left +right) >>1;
if(numbers[mid] ==mid)
return mid;
if(numbers[mid] > mid)
right = mid-1;
if(numbers[mid] < mid)
left = mid +1;
}
return -1;
}
|
题目54：二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
1
2
3
4
5
6
7
| 输入: root = [3,1,4,null,2], k = 1
3
/
1 4
2
输出: 4
|
思路：利用中序遍历的思想，由于要找最大的第k个节点，所以按照从大到小的方式遍历[右根左]，找到第k个出栈的元素就ok;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public:
int kthLargest(TreeNode* root, int k) {
if(root == nullptr) return 0;
stack<TreeNode*> nodes;
int position = 0;
TreeNode* cur = root;
while(cur != nullptr ||!nodes.empty()){
while(cur != nullptr){
nodes.push(cur);
cur = cur -> right;
}
cur = nodes.top();
nodes.pop();
position++;
if(position == k)
return cur-> val;
cur = cur -> left;
}
return 0;
}
int kthLargest(TreeNode* root, int k) {
int res = -1;
if(root != nullptr){
kthLargest(root,k,res);
}
return res;
}
void kthLargest(TreeNode* root,int& k,int& res){
if(root == nullptr) return;
kthLargest(root->right,k,res);
k--;
if(k == 0){
res = root -> val;
return;
}
kthLargest(root->left,k,res);
}
|
题目55：（1）二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3
思路1，利用层序遍历，采用两个队列，一个存节点，一个存深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int maxDepth(TreeNode* root) {
if(root == nullptr)
return 0;
queue<int> DepthCount;
queue<TreeNode*> nodes;
int curDepth = 1;
nodes.push(root);
DepthCount.push(curDepth);
while(!nodes.empty()){
TreeNode * cur = nodes.front();
curDepth = DepthCount.front();
nodes.pop();
DepthCount.pop();
if(cur ->left != nullptr){
nodes.push(cur ->left);
DepthCount.push(curDepth+1);
}
if(cur -> right != nullptr){
nodes.push(cur ->right);
DepthCount.push(curDepth+1);
}
}
return curDepth;
}
|
思路2：看了一下书，利用前序遍历得到最大的深度，深度增加达到根节点为一个支路的最大深度。写完了发现比书上写的麻烦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int TreeDepth(TreeNode* pRoot)
{
int depth = 1;
int maxDepth = 0;
if(pRoot == nullptr) return 0;
TreeDepth(pRoot,depth,maxDepth);
return maxDepth;
}
void TreeDepth(TreeNode* pRoot, int depth, int& maxDepth)
{
if(pRoot -> left == nullptr && pRoot -> right == nullptr){
if(depth > maxDepth)
maxDepth = depth;
return;
}
if(pRoot -> left != nullptr)
TreeDepth(pRoot -> left,depth+1,maxDepth);
if(pRoot -> right != nullptr)
TreeDepth(pRoot -> right,depth+1,maxDepth);
}
|
思路3：看了一下剑指Offer上的代码，简洁，如果一棵树只有一个节点那么他的深度为1.如果节点只有左子树而没有右子树，那么树的深度就是其左子树的深度加1.如果根节点只有右子树没有左子树，那么就是其右子树的深度加1。如果左右子树都有那么就是左右子树深度较大的加1。后序遍历的思想，左右子树深度确定了在求根的深度。
1
2
3
4
5
6
7
8
9
| int TreeDepth(TreeNode* pRoot)
{
if(pRoot == nullptr)
return 0;
int nleft = TreeDepth(pRoot -> left);
int nright = TreeDepth(pRoot -> right);
return (nleft > nright)? (nleft+1):(nright +1);
}
|
题目55：（2）平衡二差树
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
给定二叉树 [3,9,20,null,null,15,7]
? 3
/
9 20
/
15 7
返回 true 。
思路还是采用上述的思路后序遍历，但是记录比较左右树的深度。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == nullptr)
return true;
bool flag = true;
int length = IsBalanced_Solution(pRoot,flag);
return flag;
}
int IsBalanced_Solution(TreeNode* pRoot,bool& flag){
if(pRoot == nullptr){
return 0;
}
int nleft = IsBalanced_Solution(pRoot->left,flag);
int nright = IsBalanced_Solution(pRoot->right,flag);
if(nleft - nright >1 || nright -nleft >1)
flag = false;
return (nleft > nright)? (nleft+1):(nright +1);
}
|
题目56：（1）数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
没思路，看了剑指offer的思路
1，先考虑只有一个只出现一次的数据，其他数据出现两次。我们想到异或的性质：任何一个数异或自己本身都等于0，将一个数组内的元素依次异或就能得到出现一次的元素。
2 ，考虑有两个不一样的元素，将全部元素异或之后，由于有两个元素不一样 ，那么异或出来的数字的二进制表示中一定有一位为1,那么我们找到第一位为1的位置，记录为第n位，那么按照这位的不同将数组分为两组，这样两个出现一次的数据就分开了。
3， 分开之后开始第一步的操作就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| vector<int> singleNumbers(vector<int>& nums) {
vector<int> result(2,0);
int length = nums.size();
if(length == 0 || length < 2) return result;
int ExclusiveOr = 0;
for(int i =0; i < length; ++i){
ExclusiveOr ^= nums[i];
}
int index = findFirstOnePos(ExclusiveOr);
for(int i = 0; i< length;++i){
if(IsBits(nums[i],index)){
result[0] ^= nums[i];
}
else
result[1] ^= nums[i];
}
return result;
}
int findFirstOnePos(int number){
int index = 0;
unsigned int flag = 1;
while((number & flag)==0 ){
flag = flag << 1;
index++;
}
return index;
}
bool IsBits(int number,int index){
number = number >> index;
return (number & 1);
}
|
题目56：（2）数组中唯一只出现一次的数字
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
想到哈希表和排序的方法 空间时间效率O(n),
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int singleNumber(vector<int>& nums) {
unordered_map<int,int> CountMap;
int length = nums.size();
if(length ==0 || length < 2) return 0;
for(int i =0; i< length;++i){
CountMap[nums[i]]++;
}
for(auto iElement = CountMap.begin(); iElement != CountMap.end(); iElement++){
if(iElement -> second == 1){
return iElement -> first;
}
}
return 0;
}
|
剑指Offer提供一种思路空间O(1),时间O(n)
还是分解开来看，一个数字出现三次，那么它的二进制表示的每一个位也出现三次，如果把所有出现三次的数字的二进制表示的每一位都加起来，那么每一位的和可以被3整除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int singleNumber(vector<int>& nums) {
int length = nums.size();
if(length < 3) return 0;
int result[32] = {0};
for(int i =0; i<length;++i){
unsigned int flag = 1;
for(int j = 31; j>=0; --j){
if((nums[i] & flag) != 0)
result[j] += 1;大专栏 剑指Offer-知识迁移能力53-59>
flag = flag << 1;
}
}
int resultNum = 0;
for(int i =0; i< 32; ++i){
resultNum = resultNum << 1;
resultNum |= result[i] % 3;
}
return resultNum;
}
|
题目57：（1）和为s的数字
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
1
2
| 输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
|
我的想法1，利用哈希表，时间空间效率为O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<int> twoSum(vector<int>& nums, int target) {
int length = nums.size();
vector<int> result;
if(length < 2) return result;
unordered_map<int,int> CalcuMap;
for(int i =0; i < length;++i){
CalcuMap[nums[i]] = target - nums[i];
}
for(int i =0; i < length;++i){
if(CalcuMap[target - nums[i]] == nums[i]){
result.push_back(nums[i]);
result.push_back(target- nums[i]);
break;
}
}
return result;
}
|
我的想法2, 利用两个指针,空间效率降为O(1),好了很多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| vector<int> twoSum(vector<int>& nums, int target) {
int length = nums.size();
vector<int> result;
if(length < 2) return result;
int left = 0;
int right = length -1;
while(right > left){
int sum = nums[left] + nums[right];
if(sum == target){
result.push_back(nums[left]);
result.push_back(nums[right]);
break;
}
if(sum < target)
left++;
else
right--;
}
return result;
}
|
想法3：既然是排好序的数组那么就利用二分查找的思想，方法不好，一遍二分很可能找不出答案，不好不好
题目57：（2）和为s的连续整数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。利用滑动窗口的方法。效率写的还可以
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> result;
if(target < 3) return result;
int left =1;
int right = 2;
int sum = left + right;
vector<int> v;
for(;right <= target/2+1;){
while(sum != target){
if(sum > target && left >=1){
sum -= left;
left++;
}
if(sum < target && right < target){
right++;
sum += right;
}
if( left < 1 || right > target)
break;
}
if(left >=1 && right < target && right - left >=1){
for(int i = left; i <= right;++i){
v.push_back(i);
}
}
else
break;
result.push_back(v);
v.clear();
right++;
sum += right;
}
return result;
}
|
题目58：（1）翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”
没想到。
思路先整体反转，根据空格在局部反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| string ReverseSentence(string s) {
int length = s.length();
string res;
if(length == 0 || (length ==1 && s[0] ==' '))
return res;
Revers(&s[0],&s[length-1]);
int left = 0;
int right = 0;
while(left <= length-1){
if(s[left] == ' '){
left++;
right++;
}
else if(s[right] == ' ' || right == length){
Revers(&s[left],&s[right-1]);
left = right;
}
else
right++;
}
return s;
}
void Revers(char* begin,char* end)
{
if(begin > end || begin == nullptr || end == nullptr) return;
while(end >= begin){
char tmp = *begin;
*begin = *end;
*end = tmp;
begin++;
end--;
}
return;
}
|
在leetcode上做这道题加了一些限制条件, 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| string reverseWords(string s) {
int length = s.length();
string res;
if(length == 0 || (length ==1 && s[0] ==' '))
return res;
Revers(&s[0],&s[length-1]);
int left = 0;
int right = 0;
while(left <= length-1){
if(s[left] == ' '){
left++;
right++;
}
else if(s[right] == ' ' || right == length){
Revers(&s[left],&s[--right]);
left = ++right;
}
else
right++;
}
left =0;
right = length -1;
while(s[left] == ' ' && left < length){
left++;
}
while(s[right] == ' ' && right >=0){
right--;
}
for(int i =left; i <= right;++i){
if(s[i] != ' '){
res += s[i];
}
else if(s[i-1] != ' ')
res +=s[i];
}
return res;
}
void Revers(char* begin,char* end)
{
if(begin > end || begin == nullptr || end == nullptr) return;
while(end >= begin){
char tmp = *begin;
*begin = *end;
*end = tmp;
begin++;
end--;
}
return;
}
|
看一下网友的思路，一个一个字母处理，读取一个单词放置一个单词,后读出的单词插入放好位置单词的前边
1
2
3
4
5
6
7
8
9
10
| string ReverseSentence(string str) {
string res ="",tmp="";
for(int i =0; i< str.length();++i){
if(str[i] == ' ') res = ' ' + tmp + res,tmp = "";
else tmp += str[i];
}
if(tmp.length()) res = tmp +res;
return res;
}
|
题目58：（2）左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
思路1：把需要放到后边的元素存起来，之后别的字符放完了一插入就齐活了。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
string LeftRotateString(string str, int n) {
string res = "",tmp="";
int length = str.size();
if(n < 0) return res;
n = n % length;
for(int i = 0; i < length; ++i){
if(i < n) tmp += str[i];
else res += str[i];
}
if(tmp.size()) res += tmp;
return res;
}
|
思路2：
将要左移动的一部分和不需要移动的一部分看作两个单词，先将两个单词内的字母反转，在将整个字符串反转就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| string LeftRotateString(string str, int n) {
int length = str.length();
if(length == 0 || n < 0) return "";
n = n % length;
Reverse(&str[0],&str[n-1]);
Reverse(&str[n],&str[length-1]);
Reverse(&str[0],&str[length-1]);
return str;
}
void Reverse(char * left,char * right){
if(left == nullptr || right == nullptr) return;
while(right > left){
char tmp = *left;
*left = *right;
*right = tmp;
right--;
left++;
}
}
void Reverse(char & left,char & right){
while(right > left){
char tmp = left;
left = right;
right = tmp;
right--;
left++;
}
}
|
题目59：（1）滑动窗口最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
想法1：暴力解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int length = nums.size();
vector<int> res;
if(k <0 || k > length || length == 0) return res;
int left= 0;
int max = numeric_limits<int>:: min();
int right = k-1;
while(right < length){
for(int i = left; i <= right;++i){
if(nums[i] > max)
max = nums[i];
}
res.push_back(max);
left++;
right++;
max = numeric_limits<int>:: min();
}
return res;
}
|
想法2：剑指Offer上的思路，自己实在没想到啊
利用一个队列，保持窗口的最大值一直保持在队列的头部。
1,先压入前k个元素，当新元素大于队位的元素时，将队位的元素弹出，将新元素压入，当新元素小于之前的队位元素也继续压入，当最大元素弹出的时候小的元素也可能成为最大的元素
2，压入后边的元素，队列的不能长于窗口的长度。
不能存入数值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> maxHead;
vector<int> res;
int length = nums.size();
if(k < 0 || length <= 0 || k > length) return res;
for(int i = 0; i < k; ++i){
while(!maxHead.empty() && nums[i] >= nums[maxHead.back()])
maxHead.pop_back();
maxHead.push_back(i);
}
for(int i =k; i<length;++i){
res.push_back(nums[maxHead.front()]);
while(!maxHead.empty() && nums[i] >= nums[maxHead.back()])
maxHead.pop_back();
while(!maxHead.empty() && (i - k) >= maxHead.front())
maxHead.pop_front();
maxHead.push_back(i);
}
res.push_back(nums[maxHead.front()]);
return res;
}
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> maxTmp;
vector<int> res;
int length = nums.size();
if(length == 0 || k <= 0 || k > length) return res;
for(int i = 0; i< length;++i){
while(!maxTmp.empty() && nums[i] > nums[maxTmp.back()])
maxTmp.pop_back();
while(!maxTmp.empty() && (i - maxTmp.front() +1 ) > k)
maxTmp.pop_front();
maxTmp.push_back(i);
if(i >= k-1)
res.push_back(nums[maxTmp.front()]);
}
return res;
}
|
题目59：（2）队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。开始也没想到仿照上述思路，如果出现大的数将maxdata中小于他的数字弹出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| MaxQueue() {
}
int max_value() {
return maxdata.size() > 0 ? maxdata.front() : -1;
}
void push_back(int value) {
data.push_back(value);
while(!maxdata.empty() && value > maxdata.back())
maxdata.pop_back();
maxdata.push_back(value);
}
int pop_front() {
if(data.size() == 0)
return -1;
int cur = data.front();
data.pop_front();
if(cur == maxdata.front())
maxdata.pop_front();
return cur;
}
private:
deque<int> data;
deque<int> maxdata;
};
|
剑指Offer-知识迁移能力53-59
原文：https://www.cnblogs.com/lijianming180/p/12402200.html
