OJ每日练习（13）

Posted on | In

题目名称

  1. 二叉搜索树的第k大节点（剑指offer #54）
  2. 二叉树的深度（剑指offer #55）
  3. 数组中数字出现的次数（剑指offer #56)
  4. 和为s的数字（剑指offer #57)
  5. 翻转字符串（剑指offer #58)
  6. 队列的最大值（剑指offer #59）
  7. n个骰子的点数（剑指offer #60）
  8. 扑克牌的顺子（剑指offer #61）
  9. 圆圈中最后剩下的数字（剑指offer #62）
  10. 股票的最大利润（剑指offer #63）

二叉搜索树的第k大节点（剑指offer #54）

解题思路

中序遍历二叉搜索树即可。

解题方案

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:
    TreeNode* KthNode(TreeNode* root, int k){
        if(!root)
            return nullptr;
        stack<TreeNode*> temp;
        int count=0;
        while(1){
            if(root){
                temp.push(root);
                root=root->left;
            }
            else if(!temp.empty()){
                ++count;
                root = temp.top();
                temp.pop();
                if(count==k)
                    return root;
                root=root->right;
            }
            else
                break;
        }
        return nullptr;
    }
};

二叉树的深度（剑指offer #55）

解题思路

深度等于左右子树的深度+1，很典型的递归。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int TreeDepth(TreeNode* pRoot){
        return deepth(pRoot);
    }
    
    size_t deepth(TreeNode* pRoot){
        if(!pRoot) 
            return 0;
        else return max(deepth(pRoot->left),deepth(pRoot->right))+1;
    }
};

扩展（判定平衡二叉树）

解题思路

采用递归亦可，但这里需要剪枝才能获取最大效率。在以下写法中，只要获取到一次-1（当前并非二叉平衡），则立即终止，避免无谓计算。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* root) {
        if(!root)
            return true;
        return height(root)>=0;
    }
private:
    int height(TreeNode* root){
        if(!root)
            return 0;
        int left = height(root->left);
        int right = height(root->right);
        if(left<0 || right<0 || abs(left-right)>1)
            return -1;
        return max(left,right)+1;
    }
};

数组中数字出现的次数（剑指offer #56)

解题思路

主要是异或之后得到一个diff，获取diff中最后一个1出现的位置（diff&=-diff)。这两个数在这一位不同，于是再分别异或即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int diff = accumulate(data.cbegin(),data.cend(),0,bit_xor<int>());
        diff&=-diff;
        for(auto i:data){
            if(i&diff)
                *num1^=i;
            else
                *num2^=i;
        }
    }
};

和为s的连续正数序列

解题思路

双指针法，当前序列和若小于sum，++last，大于则++first。若相等则置入,然后++first。

解题方案

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:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        int first=1,last=2;
        while(first<last){
            int cur = (first+last)*(last-first+1)/2;
            if(cur==sum){
                vector<int> temp(last-first+1);
                for(int i=first;i<=last;++i)
                    temp[i-first]=i;
                res.push_back(temp);
                ++first;
            }
            else if(cur>sum)
                ++first;
            else
                ++last;
        }
        return res;
    }
};

翻转字符串（剑指offer #58)

解题思路

首先翻转整个字符串，然后再翻转每一个单词即可

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string ReverseSentence(string str) {
	    if (str.size() <= 1)
		    return str;
	    reverse(str.begin(), str.end());
	    for (auto i = str.rbegin(); i != str.rend();) {
		    while (*i == ' ') ++i;
		    auto j = i;
		    while (j != str.rend() && *j != ' ') ++j;
		    reverse(i, j);
		    i = j;
	    }
	    return str;
    }
};

滑动窗口的最大值（剑指offer #59）

解题思路

既可以从头到尾地暴力遍历，也可以利用队列求解。

解题方案

暴力遍历(查找每一个窗口的最大值）

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:
    vector<int> maxInWindows(const vector<int>& num, unsigned int k){
        if(num.empty()||k==0||k>num.size())
            return vector<int>();
        vector<int> res(num.size()+1-k);
        int maxIndex=-1;
        for(int i=0;i<res.size();++i){
            if(maxIndex<i){
                maxIndex=i;
                for(int j=i+1;j<i+k;++j)
                    if(num[maxIndex]<=num[j])
                        maxIndex=j;
            }
             else
                 if(num[i+k-1]>=num[maxIndex])
                     maxIndex=i+k-1;
             res[i]=num[maxIndex];
        }
        return res;
    }
};

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int k){
        vector<int> res;
        deque<int> s;
        for(size_t i=0;i<num.size();++i){
            while(!s.empty()&&num[s.back()]<=num[i])
                s.pop_back();
            while(!s.empty()&&i-s.front()+1>k)
                s.pop_front();
            s.push_back(i);
            if(k && i+1>=k)// 仅在i大于k时记录
                res.push_back(num[s.front()]);
        }
        return res;
    }
};

n个骰子的点数（剑指offer #60）

解题思路

很显然的动态规划问题。现有f(n,s)表征n个骰子扔出和为s的总有可能排列。那么自然存在状态转移方程为：

f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)
f(n,s)=0 s<n||s>6n
f(1,1)=f(1,2)=f(1,4)=f(1,5)=f(1,6)=1

显然f(n,s)只和f(n-1)..相关，所以没必要存一个二维矩阵，两个一维矩阵足够了。

解题方案

(全文收录剑指offer）

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
void printProbability(int number) {
    if (number < 1)  return;
    int* pProbabilities[2];
    pProbabilities[0] = new int[g_maxValue * number + 1];
    pProbabilities[1] = new int[g_maxValue * number + 1];
    for (int i = 0; i < g_maxValue * number + 1; ++i) {
        pProbabilities[0][i] = 0;
        pProbabilities[1][i] = 0;
    }
    
    int flag = 0;
    for (int i = 1; i <= g_maxValue; ++i) {
        pProbabilities[flag][i] = 1;
    }
    for (int k = 2; k <= number; ++k) {
        for (int i = 0; i < k; ++i) {
            pProbabilities[1-flag][i] = 0;
        }
        for (int i = 1*k; i <= g_maxValue*k; ++i) {
            pProbabilities[1-flag][i] = 0;
            for (int j = 1; j <= i && j <= g_maxValue; ++j) {
                pProbabilities[1-flag][i] += pProbabilities[flag][i-j];
            }
        }
        flag = 1 - flag;
    }
    double total = pow((double)g_maxValue, number);
    for (int i = number; i <= g_maxValue * number; ++i) {
        double ratio = (double)pProbabilities[flag][i]/total;
        cout << ratio;
    }
    delete[] pProbabilities[0];
    delete[] pProbabilities[1];
}

扑克牌的顺子（剑指offer #61）

解题思路

排序，找出里面有几个0以及几个缺位，如果0的个数多于缺位，则为顺子，否则不是。此外，如果5张牌中存在非0重复元素，则必不可能为顺子。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool IsContinuous(vector<int> numbers) {
        if (numbers.empty())
		    return false;
	    sort(numbers.begin(), numbers.end());
	    int count = 0;
	    for (auto i : numbers)
		    if (i == 0) ++count;
		    else break;
	    int block = 0;
	    for (int i = 0; i != numbers.size() - 1; ++i) {
		    if (numbers[i] == 0) continue;
		    else if (numbers[i] == numbers[i + 1])
			    return false;
		    else if (numbers[i] + 1 != numbers[i + 1])
			    block += numbers[i + 1] - numbers[i]-1;
	    }
	    return block <= count;
    }
};

圆圈中最后剩下的数字（剑指offer #62）

（大名鼎鼎的约瑟夫环）

解题思路

环形链表可以求解，但最好的方法还是来自于数学公式：

f(n,m)=0 n==1
f(n,m)=(f(n-1,m)+m)%n n>1

解题方案

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int LastRemaining_Solution(int n, int m){
        if(n<1 || m<1)
            return -1;
        int last=0;
        for(int i=2;i<=n;++i)
            last = (last+m)%i;
        return last;
    }
};

股票的最大利润（剑指offer #63）

解题思路

遍历数组，在遍历的同时记住之前所遇到的最小值，用本次减去最小值得到差额，记录遍历过程中最大的差额（本质上是一种贪心）。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2)
            return 0;
        int profit=0;
        int cur_min=prices[0];
        for(int i=0;i!=prices.size();++i){
            profit=max(profit,prices[i]-cur_min);
            cur_min=min(cur_min,prices[i]);
        }
        return profit;
    }
};