文章目錄
- 題目
- 題目決議
- 解題思維1：
- 代碼
- 附圖
- 解題思維2：
- 附上方法二的代碼
題目
?
題目決議
?
解題思維1：
將 陣列ages 進行排序(升序)，其實就是將這批人 按照年齡 從高到低 進行排序，
此時再使用 兩個 “左右指標” 進行鎖定 x 的交友范圍，
確定好了之后，right - left 就是 符合 x 交友條件的人數，也就是題目中的 x 會向 y 發送請求，
?
代碼
class Solution {
public int numFriendRequests(int[] ages) {
Arrays.sort(ages);
int n = ages.length;
int left = 0,right = 0,result=0;
for(int age : ages){
if( age < 15){
// 不考慮 15歲以下的，這是題目隱藏條件，你不信邪，就加上等于，或者洗掉這個代碼塊
continue;// 后面程式不執行，繼續foreach 回圈 讀取資料，
}
while(ages[left] <= 0.5*age +7){// 太小的，不合適，left++，范圍縮小
left++;
}
while(right+1 < n && ages[right+1] <= age){// 年齡合適
right++;
}
result += right -left;// 累計每個人 發出好友請求
}
return result;// 回傳 所有人 發送好友請求的資訊條數，
}
}
附圖
?
解題思維2：
通過創建一個陣列 cur，容量為 121，陣列下標 等價于 年齡，下標對應的元素大小，就是處在該年齡的人數，
然后在創建一個同樣大小的陣列 prev，每個元素等于 自身前一個元素 加上 在cur中 與 該元素下標對應的元素，
有的朋友可能看不懂這塊代碼，簡單來說 就是累加賦值：將處于 i 年齡段及其 比 i 年齡段小的人的總和，賦予 陣列prev的 i 下標元素，將其值更新為 i 年齡段的人 及其 比 i 小的年齡段的所有人 總和，
?
接下來就是遍歷 cur 陣列，如果 有處在 i 年齡的人，也就說 cur[ i ] > 0的，此時，就需要像第一種方法一樣，計算出 0.5 * i + 7 的值，也就是 處于 i 年齡的人，所不能接受的最小年齡的界限bound，
而且,請注意！ 我們的prev的每個元素，都是對應cur 某一年齡及其以下的人數總和，
此時用 cur[i] 所對應的 prev[[i]，就是 該年齡及其以下的人數總和，減去 計算出 0.5 * i + 7 的值，也就是 處于 i 年齡的人，所不能接受的最小年齡的界限bound，
用 prev[ i ] - prev[bound] 的結果：就是 處于 【0.5 * i + 7 < age[y] <= i 】的人數總和，也就是減去的結果都是 比 0.5 * i + 7 的結果 大，也就是說 所有人，都是 i 年齡人 的 交朋友物件，
當然 除了 自己，（不要問什么！題目要求的）
然后，就是把每個 i 年齡的人申請資訊條數的一個累加，
最后回傳這個累加的結果，
?
附上方法二的代碼
class Solution {
public int numFriendRequests(int[] ages) {
// 統計每個年齡的人數，將其陣列元素化
int[] cur = new int[121];
for(int age : ages){
cur[age]++;
}
//統計每個年齡及其以下的人數總和，將其陣列元素化
int[] prev = new int[121];
for(int i = 1; i < 121;i++){
prev[i] = prev[i-1] + cur[i];
}
int result = 0;// 記錄最終結果
// 15歲以下不考慮，題目說的，從下標15 開始遍歷陣列 cur
for(int i = 15; i < 121; i++){
if(cur[i]>0){// 如果有處在 i 年齡的人
int bound = (int)(0.5*i +7);// 計算他們所能接受最小年齡界限
result += cur[i] * (prev[i] - prev[bound]-1);
// 按照題目要求， i 年齡的人，所能接受的最小年齡，至少大于 界限 bound，
// 用 目前 i 年齡及其以下的人數總和 減去 界限 bound的人數總和
// 剩下就都是 比 bound 年齡大的人，且 最大年齡不超過 i 的人
// 再根據題目要求，減去自己，剩下的人就是都 好友申請物件了，
// 當然 處于 i 年齡的人，可能不止一個，所以要乘以一個 cur[i]，
// 即： 每個 處于 i 年齡的人，都可以向除了自己以外的人，發出好友申請，
// 最后，將其每個 i 年齡，所申請的資訊條數累加，
}
}
return result;// 最侄訓傳它，
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/396188.html
標籤：java