JZ1 二維陣列中的查找(查找, 陣列)
題目描述
在一個二維陣列中（每個一維陣列的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，
解1
對每一個一維陣列進行二分查找，設二維陣列的尺寸是m * n，那么復雜度為O(mlogn)，
public class Solution {
public boolean Find(int target, int [][] array) {
int level = 0, maxLevel = array.length, n = array[0].length - 1;
if(n <= 0 || maxLevel <= 0) return false;
int j = 0, k = n, l = 0;
for(int i = 0; i < maxLevel; i++) {
while(j < k) {
l = (j + k) / 2;
if(array[i][l] == target) {
return true;
} else if(array[i][l] > target) {
k = l - 1;
} else {
j = l + 1;
}
}
if(array[i][j] == target)
return true;
else if(array[i][j] < target)
k = n;
else
j = 0;
}
return false;
}
}
解2
對于這一陣列，從最左下角出發，向上數字減小，向右數字增大，該方法的時間復雜度為O(m+n)，
因此，若當前數字大于待查找整數，則向上查找，若當前數字小于待查找整數，則向右查找，可能存在的問題是“為什么在當前數字大于待查找整數時，不需要考慮向左查找”，對于這一問題，可以對“上一步操作”進行分情況討論，
- 上一步的操作是向右查找，那么這種情況必然不用考慮向左查找（走回頭路）
- 上一步的操作是向上查找，此時可以再次分情況討論，如果之前此時的所有操作都不包括“向右查找”，那么此時當前位置位于陣列的最左側，無法繼續向左查找，
- 如果上一步的操作是向上查找，且之前的所有操作至少包含一次向右查找，記最近一次進行向右查找時的整數為
a[i][j]，可以得知待查找整數必定比a[i][j]大，而二維陣列向上時數字遞減，則可知待查找整數比a[i][0] ~ a[i][j]都大，進而可知待查找整數a[i][0] ~ a[i][j]左側的所有整數都大，因此不需要進行向左查找，
public class Solution {
public boolean Find(int target, int [][] array) {
int level = 0, m = array.length, n = array[0].length;
if(n <= 0 || m <= 0) return false;
int i = m - 1, j = 0;
while(i >= 0 && j < n) {
if(array[i][j] > target) {
i--;
} else if(array[i][j] < target) {
j++;
} else {
return true;
}
}
return false;
}
}
JZ2 替換空格(字串)
題目描述
請實作一個函式，將一個字串中的每個空格替換成“%20”，例如，當字串為We Are Happy.則經過替換之后的字串為We%20Are%20Happy，
解
沒啥好說的字串題，注意從后往前進行替換就行，
public class Solution {
public String replaceSpace(StringBuffer str) {
// 不使用額外存盤空間
// 從后往前移動更有效率
// 首先計算空格數
int spaceNum = 0;
int oldLength = str.length();
for(int i = 0; i < oldLength; i++) {
if(str.charAt(i) == ' ')
spaceNum++;
}
// 根據空格數擴大字串
str.setLength(str.length() + spaceNum * 2);
// 從尾部開始替換較容易計算移動
for(int i = oldLength - 1; i >= 0; i--) {
if(str.charAt(i) != ' ') {
str.setCharAt(i + spaceNum * 2, str.charAt(i));
} else {
str.replace(i + spaceNum * 2 - 2, i + spaceNum * 2 + 1, "%20");
spaceNum--;
}
}
return str.toString();
}
}
JZ3 從尾到頭列印鏈表(鏈表)
題目描述
輸入一個鏈表，按鏈表從尾到頭的順序回傳一個ArrayList，
解
原地反轉鏈表后輸出，基本功，
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
// 反轉鏈表之后就能順序輸出了
ListNode newHead = null, p = listNode, q;
ArrayList<Integer> res = new ArrayList<Integer>();
while(p != null) {
q = p;
p = p.next;
q.next = newHead;
newHead = q;
}
p = newHead;
while(p != null) {
res.add(p.val);
p = p.next;
}
return res;
}
}
JZ4 重建二叉樹(樹，陣列，DFS)
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并回傳，
解
利用遞回，將遞回的每一步歸納為“找到根并確定左右子樹的前序序列和中序序列”的程序，假設左右子樹都已經構建好了，那么把左右子樹連接到根節點上即可，
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length <= 0 || in.length <= 0) return null;
TreeNode res = reconstruct(pre, in, 0, pre.length - 1, 0, in.length - 1);
return res;
}
// 遞回
public TreeNode reconstruct(int [] pre, int [] in, int preMin, int preMax, int inMin, int inMax) {
if(preMin > preMax || inMin > inMax) return null;
// 構造根
TreeNode root = new TreeNode(pre[preMin]);
int leftCount = 0, rightCount = 0, i = inMin;
while(in[i++] != pre[preMin]) {
leftCount++;
}
rightCount = inMax - leftCount - 1;
root.left = reconstruct(pre, in, preMin + 1, preMin + leftCount, inMin, inMin + leftCount - 1);
root.right = reconstruct(pre, in, preMin + leftCount + 1, preMax, inMin + leftCount + 1, inMax);
return root;
}
}
JZ5 用兩個堆疊實作佇列(堆疊)
題目描述
用兩個堆疊來實作一個佇列，完成佇列的Push和Pop操作， 佇列中的元素為int型別，
解
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.isEmpty() && stack2.isEmpty())
throw new RuntimeException("Stack is Empty");
if(stack2.isEmpty()) {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
JZ6 旋轉陣列的最小數字(二分，陣列)
題目描述
把一個陣列最開始的若干個元素搬到陣列的末尾，我們稱之為陣列的旋轉，
輸入一個非遞減排序的陣列的一個旋轉，輸出旋轉陣列的最小元素，
例如陣列[3,4,5,1,2]為[1,2,3,4,5]的一個旋轉，該陣列的最小值為1，
NOTE：給出的所有元素都大于0，若陣列大小為0，請回傳0，
解
旋轉后的陣列可以看作一前一后兩個非遞減序列，找到最小數字即找到第二個非遞減序列的起點，可以考慮使用二分查找，如果不考慮相同數字，設陣列array的查找起點為min，終點為max：
- 令
mid = (min + max) / 2，若array[min] <= array[mid] && array[max] <= array[mid]，可知此時mid落在了前一個非遞減序列，進而可知最小值點在mid之后， - 若
array[mid] <= array[min] && array[mid] <= array[max]，可知此時mid落在了后一個非遞減序列，進而可知最小值點在mid之前， - 若
array在區間[min, max]上非遞減，則已經定位到了第二個非遞減序列，直接取array[min]即為整個陣列的最小值
在此基礎上考慮相同數字，如果array在min, max, mid三個位置的值都相等，則難以判斷此時mid落在了哪一個非遞減序列，此時只能順序查找（牛客上的測驗用例不夠強，不考慮這一點也能AC），
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length <= 0) {
return 0;
}
int min = 0, max = array.length - 1;
while(min < max) {
int mid = (min + max) / 2;
if(array[min] == array[mid] && array[mid] == array[max]) {
// find by order
int res = array[min];
while(min < max) {
if(array[min] < res) {
res = array[min];
}
min++;
}
}
if(array[min] <= array[mid] && array[mid] <= array[max]) {
return array[min];
} else if(array[min] <= array[mid] && array[mid] >= array[max]){
min = mid + 1;
} else {
max = mid;
min++;
}
}
return array[min];
}
}
JZ7 斐波那契數列
題目描述
大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0，第1項是1），
n<=39
解
非常的簡單，不過這算不算有一點DP的思想呢（
public class Solution {
public int Fibonacci(int n) {
if(n == 0 || n == 1) return n;
int res = 1, pre = 1;
n -= 2;
int temp = 0;
while(n-- > 0) {
temp = res + pre;
pre = res;
res = temp;
}
return res;
}
}
JZ8 跳臺階(遞回，動態規劃)
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果），
解
可以先觀察一下n比較小的情況，設N(k)為k級臺階的跳法數：
- 跳0級: 0種跳法
- 跳1級: 1種跳法
- 跳2級: 2種跳法
- 跳3級: N(2) + N(1)
- 跳4級: N(3) + N(2)
進而知道，需要跳n級時，前一步要么跳了1級，要么跳了2級，那么只需要知道跳n-1級和跳n-2級分別有幾種跳法，即可算出N(n) = N(n - 1) + N(n - 2)
需要注意的是，不要認為“跳2級有2種跳法”，進而得到N(n) = N(n - 1) + 2 * N(n - 2)的結論，因為“先跳n - 2級，再跳兩次1級”的情況與“先跳n - 1級，再跳1級”的情況有重復，
本題的非遞回做法比較容易看出，因此使用非遞回做法以節省空間，
public class Solution {
public int JumpFloor(int target) {
if(target >= 0 && target <= 2) return target;
int res = 2, pre = 1, temp = 0;
target -= 2;
while(target-- > 0) {
temp = res + pre;
pre = res;
res = temp;
}
return res;
}
}
JZ9 變態跳臺階(遞回)
題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級，求該青蛙跳上一個n級的臺階總共有多少種跳法，
解
還是可以先觀察一下n比較小的情況，
- 跳0級: 0種跳法
- 跳1級: 1種跳法
- 跳2級: 2種跳法 = N(1) + 1
- 跳3級: 4種跳法 = N(2) + N(1) + 1 = 2 * N(2)
- 跳4級: 8種跳法 = N(3) + N(2) + 1 = 2 * N(3)
需要跳n級時，前一步可以跳0, 1, 2, ..., n - 1級，可知N(n) = 1 + N(1) + N(2) + ... + N(n - 1)，進一步化簡得N(n) = [1 + N(1) + ... + N(n - 2)] + N(n - 1) = 2 * N(n - 1)，轉換為非遞回做法也比較容易，
public class Solution {
public int JumpFloorII(int target) {
if(target == 0 || target == 1) return target;
target -= 2;
int res = 2;
while(target-- > 0) {
res *= 2;
}
return res;
}
}
JZ10 矩形覆寫
題目描述
我們可以用21的小矩形橫著或者豎著去覆寫更大的矩形，請問用n個21的小矩形無重疊地覆寫一個2n的大矩形，總共有多少種方法？
比如n=3時，23的矩形塊有3種覆寫方法
解
2 * n的矩形可以視為由兩種“塊”填滿：
- 豎著擺的2 * 1
- 兩條上下擺放的橫向2 * 1構成的2 * 2塊
需要注意的是沒有第三種，兩條左右擺的縱向2 * 1就變成了兩個第一種塊，
于是本題的做法就和JZ8 跳臺階一樣了，
public class Solution {
public int RectCover(int target) {
if(target >= 0 && target <= 2) return target;
target -= 2;
int res = 2, pre = 1, temp = 0;
while(target-- > 0) {
temp = res + pre;
pre = res;
res = temp;
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/25938.html
標籤：其他