leetcode解题思路分析（三十七）307 - 316题

一时失言乱红尘 2022-11-26 13:59 191阅读 0赞

1.  区域和检索-数组可修改

**很简单的一道题**

class NumArray { 
            vector<int> m_sum;
            vector<int> m_nums;
    public:
        NumArray(vector<int>& nums) { 
            m_nums = nums;
            m_sum = nums;
    
            if (nums.size() == 0) 
                return;
    
            for (int i = 1; i < nums.size(); i++)
            { 
                m_sum[i] += m_sum[i - 1];
            }
        }
        
        void update(int i, int val) { 
            int dif = val - m_nums[i];
            m_nums[i] = val;
    
            for (int j = i; j < m_sum.size(); j++)
            { 
                m_sum[j] += dif;
            }
        }
        
        int sumRange(int i, int j) { 
            if (i == 0)
                return m_sum[j];
            else
                return m_sum[j] - m_sum[i - 1];
        }
    };
    
    /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * obj->update(i,val); * int param_2 = obj->sumRange(i,j); */

1.  最佳买卖股票时机含冷冻期  
    给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。  
    设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:  
    你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。  
    卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)

**经典动态规划运用。首先写出第I天的状态和i-1天的关系，然后再进行降维优化即可**

class Solution { 
    public:
        int maxProfit(vector<int>& prices) { 
            if (prices.empty()) { 
                return 0;
            }
    
            int n = prices.size();
            int f0 = -prices[0];
            int f1 = 0;
            int f2 = 0;
            for (int i = 1; i < n; ++i) { 
                int newf0 = max(f0, f2 - prices[i]);
                int newf1 = f0 + prices[i];
                int newf2 = max(f1, f2);
                f0 = newf0;
                f1 = newf1;
                f2 = newf2;
            }
    
            return max(f1, f2);
        }
    };

1.  最小高度树  
    对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

**本题主要考察点为，最小高度树如果用图的叶子为根则其他点到该叶子至少是1 + 叶子父亲节点。由此可知叶子节点不是我们的选项。从所有的叶子节点向中间靠拢，逐层递归剥离直至相遇，则为距离最短的交点。根据深度的奇偶数可能是1个结果或者2个结果**

class Solution { 
    public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { 
    	if (n == 1)
    		return {  0 };
    	else if (n == 2)
    		return{  0,1 };
    
    	vector<int> indegree(n,0);//入度数组，并初始化
    	vector<int> v;
    	vector<vector<int>> graph(n,v);//图形表示，并初始化
    	for (int i = 0; i < edges.size(); i++)//构造图与入度数组：无向图，两个点都要处理
    	{ 
    		graph[edges[i][0]].push_back(edges[i][1]);
    		graph[edges[i][1]].push_back(edges[i][0]);
    		indegree[edges[i][0]]++;
    		indegree[edges[i][1]]++;
    	}
    	queue<int> myqueue;//装载入度为1的queue
    	for (int i = 0; i < n; i++)
    	{ 
    		if (indegree[i] == 1)
    			myqueue.push(i);
    	}
    	int cnt = myqueue.size();//！！令cnt等于myqueue.size()，一次性将入度为1的点全部删去。
    	while (n>2)
    	{ 
    		n -= cnt;//一次性将入度为一的点全部删去！！不能一个一个删！
    		while (cnt--)
    		{ 
    			int temp = myqueue.front();
    			myqueue.pop();
    			indegree[temp] = 0;
    			//更新temp的邻接点：若temp临接点的入度为1，则将其放入queue中。
    			for (int i = 0; i < graph[temp].size(); i++)
    			{ 
    				if (indegree[graph[temp][i]] != 0)
    				{ 
    					indegree[graph[temp][i]]--;
    					if (indegree[graph[temp][i]] == 1)//放在这里做！只判断邻接点。
    						myqueue.push(graph[temp][i]);
    				}
    				
    			}
    		}
    		cnt = myqueue.size();
    	}
    	vector<int> result;
    	while (!myqueue.empty())
    	{ 
    		result.push_back(myqueue.front());
    		myqueue.pop();
    	}
    	return result;
    }
    };

1.  戳气球  
    有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums\[left\] \* nums\[i\] \* nums\[right\] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。  
求所能获得硬币的最大数量。

**经典动态规划题，可以采用自顶向下或者自底向上的思想解。核心思想：如果是戳气球那就先戳每次内部最小气球，最后戳边缘。如果是加气球就从大的开始加**

class Solution { 
    public:
        int maxCoins(vector<int>& nums) { 
            int n = nums.size();
            vector<vector<int>> rec(n + 2, vector<int>(n + 2));
            vector<int> val(n + 2);
            val[0] = val[n + 1] = 1;
            for (int i = 1; i <= n; i++) { 
                val[i] = nums[i - 1];
            }
            for (int i = n - 1; i >= 0; i--) { 
                for (int j = i + 2; j <= n + 1; j++) { 
                    for (int k = i + 1; k < j; k++) { 
                        int sum = val[i] * val[k] * val[j];
                        sum += rec[i][k] + rec[k][j];
                        rec[i][j] = max(rec[i][j], sum);
                    }
                }
            }
            return rec[0][n + 1];
        }
    };

1.  超级丑数  
    编写一段程序来查找第 n 个超级丑数。  
    超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

**1）队列的元素来源：堆顶元素\*质数列表，将新生成的元素放入队列，弹出的第n个元素就是我们求的超级丑数。但是，弹出的元素不一定是第n个最小的质数，因此我们弹出前需要排序。  
2）第n个质数，则要求队列是有序的，且是从小到大排列的，因此我们取小顶堆**

class Solution { 
    public:
        int nthSuperUglyNumber(int n, vector<int> &primes)
        { 
            priority_queue<long long, vector<long long>, greater<long long>> buff;
            unordered_set<long long> primeset;
    
            buff.push(1);
            primeset.insert(1);
            long long i = 1;
            int count = 0;
            while (count < n) { 
                count++;
                i = buff.top();
                buff.pop();
                for (long long prime : primes) { 
                    long long next = i * prime;
                    if (next<=INT32_MAX && !primeset.count(next)) { 
                        buff.push(next);
                        primeset.insert(next);
                    }
                }
            }
    
            return i;
        }
    };

1.  计算右侧小于当前元素的个数  
    给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts\[i\] 的值是 nums\[i\] 右侧小于 nums\[i\] 的元素的数量。

**本题采用树状数组求解，是一道经典题。可以理解为每个桶存储一个数值的个数，然后累加即可**

class Solution { 
    private:
        int lowbit(int x){ 
            return x & (-x);
        }
        void update(int i, vector<int>&C){ 
            while (i < C.size()) { 
                C[i]++;
                i += lowbit(i);
            }
        }
        void query(int i, int j, vector<int>&C, vector<int>&counts){ 
            while (i >= 1) { 
                counts[j] += C[i];
                i -= lowbit(i);
            }
        }
    public:    
        vector<int> countSmaller(vector<int>& nums) { 
            vector<int>counts(nums.size(), 0);
            if (nums.size() < 1) { 
                return counts;
            }
            
            vector<int>N(nums);
            // Sort and unique
            sort(N.begin(), N.end());
            int slow = 1;
            int fast = 1;
            while(fast< N.size()) { 
                if (N[fast] != N[slow - 1]) { 
                    N[slow] = N[fast];
                    slow++;
                    fast++;
                }else{ 
                    fast++;
                }
            }
            N.resize(slow);
            
            // key: number, value: i
            map<int, int>m;
            for (int j = 1; j < 1 + N.size(); ++j) { 
                m[N[j - 1]] = j;
            }
            
            // traverse
            vector<int>C(N.size() + 1, 0); // C[i] is necessary, but A[i] not
            int i;
            for (int j = nums.size() - 1; j >= 0; --j) { 
                i = m[nums[j]];
                update(i, C);
                if (i != 1) { 
                    query(i - 1, j, C, counts);
                }else{ 
                    counts[j] = 0;
                }
            }
            return counts;
        }
    };

1.  去除重复字母  
    给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

**要想使结果的字典序最小，就应该尽可能地将小的元素留在前面。如果stk栈顶的元素大于当前遍历到的元素，根据上述原则，则应该在条件允许的情况下回避这一情况，根据题目要求（去重）,只有在后续还有这个栈顶元素的情况下才能将这个栈顶元素去掉（减少一个逆序）。如果后续没有这个栈顶元素，则只能将它保留在这儿，即使它大于它的下一个元素。**

class Solution { 
    public:
        string removeDuplicateLetters(string s) { 
            string stk;
            size_t i = 0;
            for(size_t i = 0;i < s.size(); ++i)
            { 
                if(stk.find(s[i]) != string::npos) continue;
                while(!stk.empty()&& stk.back() > s[i]&& 
                    s.find(stk.back(), i) != string::npos)
                    stk.pop_back();
                stk.push_back(s[i]);
            }
            return stk;
        }
    };