1. 題目

2. 解答

此題目為 今日頭條 2018 AI Camp 5 月 26 日在線筆試編程題第二道——最小分割分數(shù)。

class Solution { public:// 若分割數(shù)組的最大值為 value，判斷能否進行劃分bool cansplit(vector<int>& nums, int value, int m){ int len = nums.size();int i = 0;int sum = 0;int split_count = 0; // 分割次數(shù)// 依次往后求和，若和小于等于 value，則繼續(xù)加；// 若和大于 value，則分割次數(shù)加 1，從當前位置開始將和清零，重新開始for (i = 0; i < len; i++){if (sum + nums[i] <= value){sum += nums[i];}else{split_count++;sum = nums[i];}if (split_count == m) // 分割次數(shù)超出 m, 不滿足劃分{return false;}}return true; }int splitArray(vector<int>& nums, int m) {int len = nums.size();int i = 0; // 分割數(shù)組的最大值介于數(shù)組的最大元素和數(shù)組所有元素的和之間int max = nums[0];int sum = 0;for (i = 0; i < len; i++){if (nums[i] > max){max = nums[i];}sum += nums[i];}int left = max;int right = sum;int mid = 0;while(left < right){mid = left + (right - left) / 2;if (cansplit(nums, mid, m)) // 能劃分，繼續(xù)找有沒有更小的值{right = mid; //不減是因為無法確保減一之后的數(shù)是否滿足劃分} else // 不能劃分，增大數(shù)值繼續(xù)尋找{left = mid + 1;}}return left; // 最終 left = right 結束，left 值就是所求} };復制代碼

獲取更多精彩，請關注「seniusen」!

總結

以上是生活随笔為你收集整理的LeetCode 410——分割数组的最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。