目錄
- 1.合并兩個有序陣列
- 代碼實作：
- 1.采用三指標解法
- 思路：
- 2.采用暴力破解
- 思路：
- 代碼實作：
- 2.楊輝三角（一）
- 思路：
- 代碼實作：
1.合并兩個有序陣列
給你兩個有序整數陣列 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個有序陣列，
說明:
初始化 nums1 和 nums2 的元素數量分別為 m 和 n ，
你可以假設 nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素，
示例:
輸入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
輸出: [1,2,2,3,5,6]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-sorted-array
代碼實作：
1.采用三指標解法
思路：
? 1.因為最終排序結果存在nums1中，所以定義一個陣列nums用來作為nums1的備份（從而實作比較和賦值功能）
? 2.當有一方先遍歷完畢，則把另一方剩余部分合并至nums1陣列后
? ps:針對arraycopy（nums2,j,nums1,i+j,m+n-i-j）方法解釋:將nums2陣列中從j及以后的部分復制到nums1陣列下標為i+j開始的位置，長度為m+n-i-j
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// two pointer for nums and nums2
int i = 0;
int j = 0;
// Set pointer for nums1
int p = 0;
int[] nums = new int[m];
System.arraycopy(nums1,0,nums,0,m);
while ((i<m)&&(j<n)){
if (nums[i]>=nums2[j]){
nums1[p++] = nums2[j++];
}else {
nums1[p++] = nums[i++];
}
}
if (j<n){
System.arraycopy(nums2,j,nums1,i+j,m+n-i-j);
}
if (i<m){
System.arraycopy(nums,i,nums1,i+j,m+n-i-j);
}
}
}
2.采用暴力破解
思路：
? 由題意不難想象到它可以先合并再排序，有現成的呼叫方法arraycopy() 和 sort()
class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
System.arraycopy(nums2,0,nums1,m,n);
Arrays.sort(nums1);
}
}
2.楊輝三角（一）
給定一個非負整數 numRows，生成楊輝三角的前 numRows 行，
在楊輝三角中，每個數是它左上方和右上方的數的和，
示例:
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/pascals-triangle
思路：
? 1.初始化第0行，[ [1] ]
2. 從第一行開始回圈：每一行的第一列都為1，最后一個也為1 3. 中間資料為 ：上一行值+上一行值的左邊值
代碼實作：
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
// first base case: if user requests zero rows,they get zero rows;
if (numRows == 0){
return triangle;
}
// Second base case:first row is always [1]
triangle.add(new ArrayList<>());
triangle.get(0).add(1);
// 從第一行開始(0行已經賦值)
for (int i=1;i<numRows;i++){
// 定義當前行:為list集合，需初始化
List<Integer> row = new ArrayList();
// 定義前一行: 取值
List<Integer> pre = triangle.get(i-1);
// 每一行的第一個值為1
row.add(1);
// 每一行后面的值為: 上一行值+上一行值的左邊值
for (int j=1;j<i;j++){
row.add(pre.get(j) + pre.get(j-1));
}
// 每一行最后一個值為1
row.add(1);
// 將每一行添加到triangle中
triangle.add(row);
}
return triangle;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/159870.html
標籤：其他
上一篇：二叉樹的鏡像