leetcode解题思路分析（四十八）410 - 419 题

「爱情、让人受尽委屈。」 2022-11-21 11:54 116阅读 0赞

1.  分割数组的最大值  
    给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

**先思考最简单的情况，如果分成两个子数组，那肯定是让二者值接近为佳。如果分成m个，那肯定是让m个值接近为佳。所以可以采取类似二分的思想，先去一个近似值，然后检查是否满足要求，不满足则再减少，满足则再增加，直至找到最合适的值**

class Solution { 
    public:
        bool check(vector<int>& nums, int x, int m) { 
            long long sum = 0;
            int cnt = 1;
            for (int i = 0; i < nums.size(); i++) { 
                if (sum + nums[i] > x) { 
                    cnt++;
                    sum = nums[i];
                } else { 
                    sum += nums[i];
                }
            }
            return cnt <= m;
        }
    
        int splitArray(vector<int>& nums, int m) { 
            long long left = 0, right = 0;
            for (int i = 0; i < nums.size(); i++) { 
                right += nums[i];
                if (left < nums[i]) { 
                    left = nums[i];
                }
            }
            while (left < right) { 
                long long mid = (left + right) >> 1;
                if (check(nums, mid, m)) { 
                    right = mid;
                } else { 
                    left = mid + 1;
                }
            }
            return left;
        }
    };

1.  Fizz Buzz

**很无聊的一道题，浪费时间**

class Solution { 
    public:
         vector<string> fizzBuzz(int n) { 
            vector<string> res;
            int i = 1;
            while (i <= n)
            { 
                if (i % 15 == 0)
                    res.push_back("FizzBuzz");
                else if (i % 5 == 0)
                    res.push_back("Buzz");
                else if (i % 3 == 0)
                    res.push_back("Fizz");
                else
                    res.push_back(to_string(i));
                ++i;   
            }
            return res;
        }
    };

1.  等差数列划分  
    返回数组 A 中所有为等差数组的子数组个数。

**先设计动态规划，然后降维省空间。原理就是如果第i为满足等差，则dp\[i\] = dp\[i - 1\] + 1。如果前面的可以组成，那么该位就能组成比前面多一种，如果前面是0，则为1.**

class Solution { 
    public:
        int numberOfArithmeticSlices(vector<int>& A) { 
            int sum = 0;
            int now = 0;
            for (int i = 2; i < A.size(); i++)
            { 
                if (A[i] - A[i - 1] == A[i - 1] - A[i - 2])
                { 
                    now++;
                    sum += now;
                }
                else
                { 
                    now = 0;
                }
            }
            return sum;
        }
    };

1.  第三大的数  
    给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

**类似堆的思想遍历一遍解决即可**

class Solution { 
    public:
        int thirdMax(vector<int>& nums) { 
            long long  m1 = -3e9, m2 = -3e9, m3 = -3e9;
            for (auto x : nums) { 
                if (x == m1 || x == m2 || x == m3) continue;
                if (x > m1) { 
                    m3 = m2;
                    m2 = m1;
                    m1 = x;
                } else if (x > m2) { 
                    m3 = m2;
                    m2 = x;
                } else if (x > m3) 
                    m3 = x;
            }
            if (m3 == -3e9) return m1;
            else return m3;
        }
    };

1.  字符串相加  
    给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

**逐位计算即可**

class Solution { 
    public:
        string addStrings(string num1, string num2) 
        { 
            int i = num1.length() - 1, j = num2.length() - 1, add = 0;
            string ans = "";
            while (i >= 0 || j >= 0 || add != 0) 
            { 
                int x = i >= 0 ? num1[i] - '0' : 0;
                int y = j >= 0 ? num2[j] - '0' : 0;
                int result = x + y + add;
                ans.push_back('0' + result % 10);
                add = result / 10;
                i--;
                j--;
            }
            // 计算完以后的答案需要翻转过来
            reverse(ans.begin(), ans.end());
            return ans;
        }
    };

1.  分割等和子集  
    给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

**主要是写出dp方程，dp\[i\]\[j\]表示\[0, i\]范围的数组可以取得子数组和为j**

class Solution { 
    public:
        bool canPartition(vector<int>& nums) { 
            int n = nums.size();
            if (n < 2) { 
                return false;
            }
            int sum = 0, maxNum = 0;
            for (auto& num : nums) { 
                sum += num;
                maxNum = max(maxNum, num);
            }
            if (sum & 1) { 
                return false;
            }
            int target = sum / 2;
            if (maxNum > target) { 
                return false;
            }
            vector<int> dp(target + 1, 0);
            dp[0] = true;
            for (int i = 0; i < n; i++) 
            { 
                int num = nums[i];
                for (int j = target; j >= num; --j) 
                { 
                    dp[j] |= dp[j - num];
                }
            }
            return dp[target];
        }
    };

1.  太平洋大西洋水流问题  
    给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标

**采用DFS或者BFS均可，找到同时满足二者的点，加入返回点集合即可**

class Solution { 
    private:
    	vector<vector<int>> res;
    	int m, n;
    	int dis[4][2] = {  { 1,0},{ 0,1},{ -1,0},{ 0,-1} };
    public:
    	vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) { 
    		if (matrix.empty() || matrix[0].empty()) return { };
    
    		m = matrix.size(), n = matrix[0].size();
    		vector<vector<bool>> pacific(m, vector<bool>(n, false));
    		vector<vector<bool>> atlantic(m, vector<bool>(n, false));
    		for (int i = 0; i < m; ++i) { 
    			dfs(matrix, pacific, INT_MIN, i, 0);
    			dfs(matrix, atlantic, INT_MIN, i, n - 1);
    		}
    		for (int i = 0; i < n; ++i) { 
    			dfs(matrix, pacific, INT_MIN, 0, i);
    			dfs(matrix, atlantic, INT_MIN, m - 1, i);
    		}
    		for (int i = 0; i < m; ++i) { 
    			for (int j = 0; j < n; ++j) { 
    				if (pacific[i][j] && atlantic[i][j]) { 
    					res.push_back({ i, j});
    				}
    			}
    		}
    		return res;
    	}
    	void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int pre, int i, int j) { 
    		if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || matrix[i][j] < pre) return;//规定水流只能从高到低或者在同等高度上流动。
    		visited[i][j] = true;
    		for (int k = 0; k < 4; k++) { 
    			int newx = i + dis[k][0];
    			int newy = j + dis[k][1];
    			dfs(matrix, visited, matrix[i][j], newx, newy);
    		}
    	}
    };

1.  甲板上的战舰  
    给定一个二维的甲板， 请计算其中有多少艘战舰。

**理解题意后，从左上角出发遍历一遍即可**

class Solution { 
    public:
        int countBattleships(vector<vector<char>>& board) { 
            int R = board.size(), C = board[0].size(), res = 0;
            for (int i = 0; i < R; ++i)
                for (int j = 0; j < C; ++j)
                    if (board[i][j] == 'X' && 
                        (!i || board[i - 1][j] == '.') && (!j || board[i][j - 1] == '.'))
                        ++res;
            return res;
        }
    };