leetcode解题思路分析（三十四）268—283题

柔情只为你懂 2023-03-01 10:08 8阅读 0赞

1.  缺失数字  
    给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

**挨个异或一遍，没有出现的即是缺失数字**

class Solution { 
    public:
        int missingNumber(vector<int>& nums) { 
        int res = nums.size();
        for(int i = 0; i < nums.size(); ++i)
            res = res ^ i ^ nums[i];            // a^b^b = a;
        return res ;
        }
    };

1.  整数转换英文表示  
    将非负整数转换为其对应的英文表示

**本题其实不难，就是要罗列出所有的可能并组合起来，还有就是空格的添加**

class Solution { 
    public:
        vector<string>num1 = { "","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten",
                            "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen","Twenty"};
        vector<string>num2 = { "","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
        vector<string>num3 = { "Hundred","Thousand","Million","Billion"};//前面增加空字符串,方便单词数字与下标对应
        
        string numberToWords(int num) { 
            if(num == 0)return "Zero";//单独考虑0
            string res = helper(num); 
            res.erase(0,1);
            return res; 
        }
    
        string helper(int num){ 
            if(num == 0){ 
                return "";
            }
            if(num<20){ 
                return " " + num1[num];
            }
            if(num<100){ 
                return " "+num2[num/10] + helper(num%10);
            }
            if(num < 1000){ 
                return helper(num/100)+" "+num3[0]+helper(num%100);
            }
            for(int i = 1; i <= 3; i++){ 
                if(num < pow(1000,i+1)){ 
                    return helper(num/(int)pow(1000,i))+ " " + num3[i] + helper(num%(int)pow(1000,i));
                }
            }
            return "";
        }
    };

1.  H指数  
    给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。  
    h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）

**按题意，引用量大于N是没有意义的，最大即为N。所以这里可以用计数排序，分装在不同的桶里。我们需要的是h个大于等于h，即后几个桶的总数大于等于桶的编号。**

class Solution { 
    public:
        int hIndex(vector<int>& citations) { 
            int n = citations.size();
            vector<int> bucket(n + 1, 0);
            for (int i = 0; i < n ; i++)
            { 
                if (citations[i] >= n)
                    bucket[n]++;
                else 
                    bucket[citations[i]]++;
            }
            int ret = 0;
            for (int i = n; i >= 0; i--)
            { 
                if (ret < i)
                { 
                    if (ret + bucket[i] < i)
                        ret += bucket[i];
                    else 
                        ret = i;
                }
                else 
                    break;
            }
            return ret;
        }
    };

1.  第一个错误的版本  
    通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

**典型的二分查找，唯一的陷阱是注意mid可能超过数值限制**

// The API isBadVersion is defined for you.
    // bool isBadVersion(int version);
    
    class Solution { 
    public:
        int firstBadVersion(int n) { 
            int left = 1, right = n;
            while (left < right)
            { 
                int mid = left + (right - left) / 2;
                if (isBadVersion(mid))
                    right = mid;
                else left = mid + 1;
            }
            return left;
        }
    };

1.  完全平方数  
    给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

**本题易用动态规划求解：一个数N的最少平方数为组成该数的N\`的平方数 + 1，即对每一个N，观察1到N-1中，谁的解最小，那么N的解就是它+1.但是我们没必要1到N+1中的每一个数都去观察，因为有些组合不满足N = IxI + N’，譬如12 = 2+N’是不需要的，因为2不是某个数的平方。所以我们观察的范围要大大减小。**

class Solution { 
    public:
        int numSquares(int n)
        { 
            vector<int> result(n+1, 0x7FFFFFFF); // 每个数的最优解都存在result数组里
            result[0] = 0;
            for (int i = 1; i <= n; i++){ 
                for(int j = 1; i - j * j >= 0 ; j++) {   // 观察比N小的数，且符合N = IxI + N'的数值
                    result[i] = min(result[i], result[i - j * j] + 1); // 把最优解（最小值）+ 1 写入result
                }
            }
            return result[n];
        }
    };

1.  给表达式添加运算符  
    给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 或 \* ，返回所有能够得到目标值的表达式。

**使用回溯法可解，比较麻烦的在于要考虑很多细节，如乘法优先级高于加减法。一共有四种操作：1、添加加号。2、添加减号。3、添加乘号。4、追加后面一个数字形成更大的操作数。为了能在得出字符串同时立刻计算出表达式的值，需要在算法过程中维护一些中间值。**

typedef long long LL;
    class Solution {
    public:
        vector<string> res;
        string path;
        vector<string> addOperators(string num, int target) {
            if(num == ""){
                return {};
            }
            dfs(0,0,1,num[0] - '0',1,num.size(),target,num);
            return res;
        }
    
        void dfs(int idx,LL pre,LL left,LL operand,int sign,int n,int target,string& num){
            //查看串尾是否运算符来判断当前数字是否操作数的首位
            bool isBeg = path.empty() || path.back() < '0'; 
    
            path += num[idx];
            if(idx == n - 1){
                if(pre + sign * left * operand == target){
                    res.emplace_back(path);
                }
            }else{
                int next_num = num[idx + 1] - '0';
                string old_path = path;
                //追加数字时不能形成有前导0的情况
                if(!(isBeg && num[idx] == '0')){  
                    dfs(idx + 1,pre,left,operand * 10 + next_num,sign,n,target,num);
                    path = old_path;
                }
                path += '+';
                dfs(idx + 1,pre + sign * left * operand,1,next_num,1,n,target,num);
                path = old_path;
    
                path += '-';
                dfs(idx + 1,pre + sign * left * operand,1,next_num,-1,n,target,num);  
                path = old_path;
    
                path += '*';
                dfs(idx + 1,pre,left * operand,next_num,sign,n,target,num);
            }
        }
    };

1.  移动零  
    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

**最简单的做法就是从头到尾遍历，删掉0并且添加在尾部，利用stl可以很轻松的解决。更优秀的做法是采用双指针，当我们遇到一个非零元素时，我们需要交换当前指针和慢速指针指向的元素，然后前进两个指针。如果它是零元素，我们只前进当前指针。**

class Solution {
    public:
        void moveZeroes(vector<int>& nums) {
            int cnt = 0;
            vector<int>::iterator iter = nums.begin();
            while (iter != nums.end())
            {
                if (*iter == 0)
                {
                    cnt++;
                    iter = nums.erase(iter);
                }
                else iter++;
            }
            for (int i = 0; i < cnt; i++)
                nums.push_back(0);
    
            return;
        }
    };

class Solution {
    public:
        void moveZeroes(vector<int>& nums) 
        {
            for (int i = 0, cur = 0; cur < nums.size(); cur++) 
            {
                if (nums[cur] != 0) 
                {
                    swap(nums[i++], nums[cur]);
                }
            }
        }
    };