leetcode解题思路分析（八）50-56题

布满荆棘的人生 2023-07-01 07:29 1阅读 0赞

1.  Pow(x, n)  
    实现 pow(x, n) ，即计算 x 的 n 次幂函数。

**最简单的就是直接连乘**

class Solution { 
    public:
        double myPow(double x, int n) { 
            long long N = n;
            if (N < 0) { 
                x = 1 / x;
                N = -N;
            }
            double ans = 1;
            for (long long i = 0; i < N; i++)
                ans = ans * x;
            return ans;
        }
    };

**对于指数为2n，我们可以分解为两个n相乘，这样可以节省很多的时间，但是需要额外空间存储中间量，通过分治递归可获得最终值**

class Solution { 
    public:
        double fastPow(double x, long long n) { 
            if (n == 0) { 
                return 1.0;
            }
            double half = fastPow(x, n / 2);
            if (n % 2 == 0) { 
                return half * half;
            } else { 
                return half * half * x;
            }
        }
        double myPow(double x, int n) { 
            long long N = n;
            if (N < 0) { 
                x = 1 / x;
                N = -N;
            }
            return fastPow(x, N);
        }
    };

class Solution { 
    public:
        double myPow(double x, int n) { 
            long long N = n;
            if (N < 0) { 
                x = 1 / x;
                N = -N;
            }
            double ans = 1;
            double current_product = x;
            for (long long i = N; i ; i /= 2) { 
                if ((i % 2) == 1) { 
                    ans = ans * current_product;
                }
                current_product = current_product * current_product;
            }
            return ans;
        }
    };

1.  N皇后问题  
    n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。  
    给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。  
    每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

**这种需要逐步考虑，然后一步出错退回上一步的思维方式是典型的回溯法**

class Solution { 
    public:
        void solve(vector<vector<string>>& res, vector<string>& tmp, vector<bool>& cols_, vector<bool>& diag1s_, vector<bool>& diag2s_, int n, int row){ 
            if(row == n){ 
                res.push_back(tmp);
                return;
            }
            for(auto col = 0; col < n; col++){ 
                int ll = row + col;
                int rr = row - col + n - 1;
                if (cols_[col] && diag1s_[ll] && diag2s_[rr]){ 
                    tmp[row][col] = 'Q';
                    cols_[col] = false;
                    diag1s_[ll] = false;
                    diag2s_[rr] = false;
    
                    solve(res, tmp, cols_, diag1s_, diag2s_, n, row+1);
    
                    tmp[row][col] = '.';
                    cols_[col] = true;
                    diag1s_[ll] = true;
                    diag2s_[rr] = true;
                }
            }
        }
        
        vector<vector<string>> solveNQueens(int n) { 
            vector<vector<string>> res;
            vector<string> tmp(n, string(n, '.'));
            vector<bool> cols_(n, true);
            vector<bool> diag1s_(2*n-1, true);
            vector<bool> diag2s_(2*n-1, true);
            solve(res, tmp, cols_, diag1s_, diag2s_, n, 0);
            return res;
        }
        
    };

1.  N皇后 II  
    给定一个整数 n，返回 n 皇后不同的解决方案的数量。

**本题和上题基本类似，只是不用输出所有类型，而只是给出解的数量而已**

class Solution { 
    public:
        int totalNQueens(int n) { 
            int res = 0;
            vector<bool> cols_(n, true);
            vector<bool> diag1s_(2 * n - 1, true);
            vector<bool> diag2s_(2 * n - 1, true);
            solve(&res, cols_, diag1s_, diag2s_, n, 0);
            return res;        
        }
    
        void solve(int *res, vector<bool>& cols_, 
                vector<bool>& diag1s_, vector<bool>& diag2s_, int n, int row)
        { 
            if(row == n)
            { 
                (*res)++;
                return;
            }
            for(auto col = 0; col < n; col++)
            { 
                int ll = row + col;
                int rr = row - col + n - 1;
                if (cols_[col] && diag1s_[ll] && diag2s_[rr])
                { 
                    
                    cols_[col] = false;
                    diag1s_[ll] = false;
                    diag2s_[rr] = false;
    
                    solve(res, cols_, diag1s_, diag2s_, n, row+1);
    
                    cols_[col] = true;
                    diag1s_[ll] = true;
                    diag2s_[rr] = true;
                }
            }
        }
       
    };

1.  最大子序和  
    给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

**本题采用贪心法易解**

class Solution { 
    public:
        int maxSubArray(vector<int>& nums) { 
            int n = nums.size();
            int currSum = nums[0], maxSum = nums[0];
    
            for(int i = 1; i < n; ++i) 
            { 
                currSum = max(nums[i], currSum + nums[i]);
                maxSum = max(maxSum, currSum);
            }
            return maxSum;      
        }
    };

1.  螺旋矩阵  
    给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

**本题采用直接的视觉思维方式实现即可**

class Solution { 
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) { 
            if (matrix.size() == 0)
                return { };
    
            int coloum = matrix[0].size(), line = matrix.size();
            vector<int> ret;
    
            int begin = 0, end = coloum, top = 0, bottom = line;
            while (true)
            { 
                for (int i = begin; i < end; i++)
                { 
                    ret.push_back(matrix[top][i]);
                }
                top++;
                if (top >= bottom) break;
    
                for (int i = top; i < bottom; i++)
                { 
                    ret.push_back(matrix[i][end - 1]);
                }
                end--;
                if (end <= begin) break;
    
                for (int i = end - 1; i >= begin; i--)
                { 
                    ret.push_back(matrix[bottom - 1][i]);
                }
                bottom--;
                if (top >= bottom) break;            
    
                for (int i = bottom - 1; i >= top; i--)
                { 
                    ret.push_back(matrix[i][begin]);
                }
                begin++;
                if (end <= begin) break;           
            }
    
            return ret;
        }
    };

1.  跳跃游戏  
    给定一个非负整数数组，你最初位于数组的第一个位置。  
    数组中的每个元素代表你在该位置可以跳跃的最大长度。  
    判断你是否能够到达最后一个位置。

**本题思路是：一个位置可以到达的最大位置，其左侧的节点也一定可以到达**

class Solution { 
    public:
        bool canJump(vector<int>& nums) { 
            int k = 0;
            for (int i = 0; i < nums.size(); i++)
            { 
                if (i > k) return false;
                k = max(k, i + nums[i]);
                if (k >= nums.size()) return true;
            }
            return true;
        }
    };

1.  合并区间  
    给出一个区间的集合，请合并所有重叠的区间。

**本题有两种思路：第一种是先对区间排序，然后逐个判断；第二种是将所有的区间映射到“线段”上，再输出“线段”即可**

class Solution { 
    public:
        vector<vector<int>> merge(vector<vector<int>>& intervals) { 
            vector<vector<int>> res;
            if(intervals.empty()) return res;
    
            auto cmp = [](vector<int> &a, vector<int> &b) { return a[0] < b[0];};
            sort(intervals.begin(), intervals.end(), cmp);
    
            res.emplace_back(intervals[0]);
            for(int i = 1; i < intervals.size(); i++) { 
                int bk = res.size() - 1;
                if(res[bk][1] >= intervals[i][0]) { 
                    if(res[bk][1] < intervals[i][1]) { 
                        res[bk][1] = intervals[i][1];
                    } 
                } else { 
                    res.emplace_back(intervals[i]);
                }
            }
    
            return res; 
        }
    };