【剑指offer】题集

13. 找出数组中重复的数字

class Solution {
public:
    int duplicateInArray(vector& nums) {
        if(nums.empty()) return -1;
        unordered_map hash;
        int n = nums.size();
        for(auto x : nums)
            if(x < 0 || x > n) 
                return -1;
            else
            {
                hash[x] ++ ;
            }
         
        bool repeat = false;       
        for(auto x : hash)
        {
            if(x.second > 1) 
            {
                repeat = true;
                return x.first;
            }
        }
        if(!repeat) return -1;
    }
};

15. 二维数组中的查找

枚举右上角

class Solution {
public:
    bool searchArray(vector> array, int target) {
        if(array.empty() || array[0].empty()) return false;

        int i = 0, j = array[0].size() - 1;
        while(i < array.size() && j >= 0)
        {
            int x = array[i][j];
            if(x == target) return true;
            else if(x > target) j -- ;
            else i ++ ;
        }
        return false;
    }
};

作者：Once.
链接：https://www.acwing.com/activity/content/code/content/3252367/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

22. 旋转数组的最小数字

class Solution {
public:
    int findMin(vector& nums) {
        if(nums.empty()) return -1;
        int res = nums[0];
        for(int i = 1; i < nums.size(); i ++ )
        {
            res = min(res, nums[i]);
        }
        return res;
    }
};

62. 丑数

多路归并

class Solution {
public:
    int getUglyNumber(int n) {
        vector q(1, 1);
        int i = 0, j = 0, k = 0;
        while( -- n) // 循环 n - 1 次 
        {
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
            q.push_back(t);
            if(t == q[i] * 2) i ++ ;
            if(t == q[j] * 3) j ++ ;
            if(t == q[k] * 5) k ++ ;
        }
        return q.back();
    }
};

作者：Once.
链接：https://www.acwing.com/activity/content/code/content/3271190/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

LeetCode 263. 丑数

class Solution {
public:
    bool isUgly(int n) {
        if(n < 1) return false;
        while(n % 2 == 0) n /= 2;
        while(n % 3 == 0) n /= 3;
        while(n % 5 == 0) n /= 5;
        return n == 1;
    }
};

68. 0到n-1中缺失的数字

class Solution {
public:
    int getMissingNumber(vector& nums) {
        for(int i = 0; i < nums.size(); i ++ )
            if(i != nums[i]) return i;
        
        return nums.size();
    }
};

69. 数组中数值和下标相等的元素

class Solution {
public:
    int getNumberSameAsIndex(vector& nums) {
        for(int i = 0; i < nums.size(); i ++ )
        {
            if(i == nums[i]) return i;
        }
        return -1;
    }
};

71. 二叉树的深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int treeDepth(TreeNode* root) {
        if(!root) return 0;
        return max(treeDepth(root->left), treeDepth(root->right)) + 1;
    }
};

73. 数组中只出现一次的两个数字

class Solution {
public:
    vector findNumsAppearOnce(vector& nums) {
        unordered_map hash;
        vector res;
        
        for(auto x : nums) 
        {
            hash[x] ++ ;
        }
        
        for(auto x : nums) 
        {
            if(hash[x] == 1) res.push_back(x);
        }
        return res;
    }
};

77. 翻转单词顺序

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        for(int i = 0; i < s.size(); i ++ )
        {
            int j = i + 1;
            while(j < s.size() && s[j] != ' ') j ++ ;
            reverse(s.begin() + i, s.begin() + j);
            i = j;
        }
        return s;
    }
};