剑指offer（十）

发表于 | 分类于 | 阅读数 次
字数统计: 2.7k 字 | 阅读时长 ≈ 12 分钟

剑指Offer刷题（二十六）

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路

首先我们可以知道二叉搜索树的特点是:左子节点<根节点<右子节点,则显然有该树的中序遍历即为排序.然后对每个节点进行重新构造连接.

C++

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
56
57
58
59
60
61
#include<iostream>
#include<vector>
using namespace std;
struct TreeNode{
    TreeNode * left;
    TreeNode * right;
    int val;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};

class Solution{

public:
    void middlesort(TreeNode * root){
        if(root->left==NULL && root->right==NULL)
        {
            arr.push_back(root);
            num++;
            return ;
        }
        if(root->left!=NULL)
            middlesort(root->left);
        arr.push_back(root);
        num++;
        if(root->right!=NULL)
            middlesort(root->right);
    }
    Solution(){num=0;}

    TreeNode * Bi_ListNode(TreeNode *root){
        middlesort(root);
        for(int i=0;i<num;i++){
            if(i==0){
                arr[i]->left=NULL;
                arr[i]->right=arr[i+1];
            }
            else if(i==num-1){
                arr[i]->left=arr[i-1];
                arr[i]->right=NULL;
            }
            else{
                arr[i]->left=arr[i-1];
                arr[i]->right=arr[i+1];
            }

        }
        return arr[0];




    }
private:
    vector<TreeNode *>arr;
    int num;
};

int main()
{
    return 0;
}

剑指Offer刷题（二十七）

题目：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路:

递归的思想.将一个头和各种其他元素进行对换，递归地调用该方法使得整个字符串的permutation是字符串头+后续元素的permutation

C++

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
#include<iostream>
#include<string>
using namespace std;

class Solution{

public:
    void Permutation(string str){
        if(str.length()==0){
            cout<<"No string"<<endl;
            return ;
        }
        method(str,0);

        return ;
    }
private:
    void method(string str,int begin0){

        if(begin0==str.length())
        {

            cout<<str<<endl;
            return ;
        }
        for(int i=begin0;i<str.length();i++){

            if(i!=begin0 && str[i]==str[begin0])
            {
                continue;
            }
            swap(str[begin0],str[i]);
            method(str,begin0+1);

        }



    }



};

剑指Offer刷题（二十八）

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0

思路

数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。(网上思路)
我的想法，从左至右开始遍历.从第一个元素开始,它的次数为1.如果第二个元素不和它相同,它减1表示,表示其它元素和它的其中一个元素相抵消,显然如果现在遍历到的位置次数大于零,说明目标元素在这个子序列中个数超过了子序列的一半.如果等于0说明这个子序列中目标元素只占了刚好一半,并没有超过.显然,要想使该目标元素在整个序列中超过一半则只需要剩下的后续序列的该目标元素超过一半即可.则不用考虑,这个子序列了,直接找后续序列的最大个数元素。

C++

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
56
57
58
59
60
61
62
63
#include<iostream>
#include<vector>
using namespace std;

class Solution{
public:

    void print(vector<int> data){

        if(data.size()==0){
            cout<<"0"<<endl;
        }
        else{
            int result=MorethanHalf(data,0);
            int num=0;
            for(int i=0;i<data.size();i++){
                if(data[i]==result){
                    num++;
                }
            }
            if(num>data.size()/2){
                cout<<result;
            }
            else{
                cout<<"0";
            }
        }

    }





    int MorethanHalf(vector<int> data,int position){
        int target=data[position];
        int num=1;
        int i=1;
        while(num!=0){
            if(position+i!=data.size()){
                if(data[position+i]==target){
                    num++;
                }
                else{
                    num--;
                }

                i++;
            }
            else{
                break;
            }
        }
        if(position+i<data.size()-1)
            return MorethanHalf(data,position+i);
        else if(position+i==data.size()){
            return target;
        }
        else{
            return 0;
        }
    }
};

剑指Offer刷题（二十九）

题目

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

1
2
3
4
5
6
7
8
9
10
11
class Solution{
public:
    vector<int> getMin(vector<int>nums,int k){
        sort(nums.begin(),nums.end(),cmp);
        vector<int> a;
        for(int i=0;i<k;i++){
            a.push_back(nums[i]);
        }
        return a;
    }
};

剑指Offer刷题（三十）

题目

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

思考

C++

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
using namespace std;

class Solution{
public:
    int maxseq(vector<int> nums){
        int end1=nums.size()-1;
        int start=0;
        int sumleft=0;
        int sumright=0;
        int i=0;
        int j=nums.size()-1;
        while(i<j){
            sumleft+=nums[i];
            if(sumleft<0){
                start=i+1;
                sumleft=0;
                i=i+1;
            }
            else{
                i=i+1;
            }
            sumright+=nums[j];
            if(sumright<0){
                end1=j-1;
                sumright=0;
                j=j-1;
            }
            else{
                j=j-1;
            }
        }
        int sum=0;
        for(int k=start;k<=end1;k++){
            sum+=nums[k];
        }
        return sum;
    }


};


int main(){
    vector<int> nums;
    int a[]={1,-2,3,10,-4,7,2,-5};
    for(int i=0;i<8;i++){
        nums.push_back(a[i]);
    }
    Solution s;
    int n=s.maxseq(nums);
    cout<<n<<endl;


}

剑指Offer刷题（三十一）

题目

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次。

C++

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
#include<iostream>
#include<vector>
using namespace std;

class Solution{
public:
    int numsof1(int n){
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=getnumof1(i);
        }
        return sum;
    }
    int getnumof1(int num){
        int number=0;
        while(num!=0){
            int val=num%10;
            if(val==1){
                number++;
            }
            num=num/10;
        }
        return number;


    }




};

int main()
{
    int n=12;
    Solution s;
    cout<<s.numsof1(n)<<endl;

}

剑指Offer刷题（三十二）

题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路

遇到这个题，全排列当然可以做，但是时间复杂度为O(n!)。在这里我们自己定义一个规则，对拼接后的字符串进行比较。

排序规则如下：

若ab > ba 则 a 大于 b，
若ab < ba 则 a 小于 b，
若ab = ba 则 a 等于 b；
根据上述规则，我们需要先将数字转换成字符串再进行比较，因为需要串起来进行比较。比较完之后，按顺序输出即可。
(网上解答)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        int length = numbers.size();
        if(length == 0){
            return "";
        }
        sort(numbers.begin(), numbers.end(), cmp);
        string res;
        for(int i = 0; i <　length; i++){
            res += to_string(numbers[i]);
        }
        return res;
    }
private:
    // 升序排序
    static bool cmp(int a, int b){
        string A = to_string(a) + to_string(b);
        string B = to_string(b) + to_string(a);
        return A < B;
    }
};

剑指Offer刷题（三十三）

题目

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路

原理是丑数除以2,3或5仍为一个丑数.
但我下面的方法可能空间复杂度比较高到时候再思考一下别的方法.

C++

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
#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
    int getNugly(int n){
        vector<bool> tag;
        tag.push_back(false);//0
        tag.push_back(true);//1
        int i=2;
        int j=1;
        while(j<n){
            tag.push_back(judge(tag,i));
            if(tag[i]){
                j++;
            }
            i++;
        }
        return i-1;




    }
    bool judge(vector<bool> tag,int i){
        if(i%2==0&&tag[i/2]){
            return true;
        }
        if(i%3==0&&tag[i/3]){
            return true;
        }
        if(i%5==0&&tag[i/5]){
            return true;
        }
        return false;


    }

};

int main(){
Solution s;

cout<<s.getNugly(100);


}

网上代码：

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
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index < 7){
            return index;
        }
        vector<int> res(index);
        for(int i = 0; i < 6; i++){
            res[i] = i + 1;
        }
        int t2 = 3, t3 = 2, t5 = 1;
        for(int i = 6; i < index; i++){
            res[i] = min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5));
            while(res[i] >= res[t2] * 2){
                t2++;
            }
            while(res[i] >= res[t3] * 3){
                t3++;
            }
            while(res[i] >= res[t5] * 5){
                t5++;
            }
        }
        return res[index - 1];
    }
};

剑指Offer刷题（三十四）：第一个只出现一次的字符

题目

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。

思路

创建一个Hashtable,用来存储字符的个数的。然后再遍历一遍,找到第一个字符个数为1的位置.

C++

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
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;

class Solution{
public:
    int pos(string str){
        if(str.size()<1){
            return -1;
        }

        map<char,int> table;
        for(int i=0;i<str.size();i++){
            table[str[i]]++;
        }
        for(int i=0;i<str.size();i++){
            if(table[str[i]]==1)
            {
                return i;

            }
        }
        return -1;
    }
};

int main(){
    string a="dsdsaakjjkjshdgfiu";
    Solution s;
    cout<<s.pos(a)<<endl;

}
-------------本文结束感谢您的阅读-------------