JZ11 二進制中1的個數(數學，數字的機器表示)
題目描述
輸入一個整數，輸出該數32位二進制表示中1的個數，其中負數用補碼表示，
解
一般情況下整數的機器表示使用補碼，便于實作減法和負數運算，于是直接用位運算元出來就好，
public class Solution {
// 可以稍微看一下java中的>>和>>>的區別
public int NumberOf1(int n) {
int length = 32, mask = 1, count = 0;
while(length-- > 0) {
if((n & mask) == 1) {
count++;
}
n = n >> 1;
}
return count;
}
}
JZ12 數值的整數次方(數學)
題目描述
給定一個double型別的浮點數base和int型別的整數exponent，求base的exponent次方，
保證base和exponent不同時為0
解
基本思路是使用乘法快速冪，注意這題的exponent可以為負數，乘法快速冪的詳解可以查看另一篇文章“演算法中的數學型別題歸集”，
遞回版本
public class Solution {
public double Power(double base, int exponent) {
if(base == 0)
return 0;
double res = absPower(base, exponent);
if(exponent >= 0)
return res;
else
return 1 / res;
}
public double absPower(double base, int exponent) {
if(exponent == 0)
return 1;
double temp = 1;
// exponent絕對值為奇數的時候，對2求模可能為1或-1
// 這么表達更簡潔
if((exponent & 1) == 1) {
temp = base;
}
double ret = absPower(base, exponent / 2);
return ret * ret * temp;
}
}
非遞回版本
class Solution {
public:
double Power(double base, int exponent) {
// 本題是一個簡單的乘法快速冪
// 二進制分解exponent，達到log(exponent)的時間復雜度
if(exponent == 0) return 1;
if(base == 0) return 0;
if(exponent < 0) exponent--;
double res = 1;
int length = sizeof(int) * 8;
while(length--) {
if((exponent & 1) && exponent > 0) {
res *= base;
} else if(!(exponent & 1) && exponent < 0) {
res = res / base;
}
base *= base;
exponent >>= 1;
}
return res;
}
};
JZ13 調整陣列順序使奇數位于偶數前面(陣列)
題目描述
輸入一個整數陣列，實作一個函式來調整該陣列中數字的順序，使得所有的奇數位于陣列的前半部分，所有的偶數位于陣列的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變，
解
因為要保持資料的穩定性，沒辦法借鑒快速排序的想法了，不考慮以空間換時間的話，可以借鑒一下插入排序的思想：先從前往后找到第一個偶數，再從此處開始向后找到第一個奇數，將奇數插入到偶數之前，時間復雜度\(O(n^2)\)，
public class Solution {
public void reOrderArray(int [] array) {
int n = array.length;
for(int i = 0; i < n; ) {
if(array[i] % 2 == 0) {
int j = i + 1;
while(j < n) {
if(array[j] % 2 != 0) {
break;
}
j++;
}
if(j < n) {
int temp = array[j], index = j;
while(j > i) {
array[j] = array[j - 1];
j--;
}
array[i] = temp;
} else {
break;
}
i = j + 1;
} else {
i++;
}
}
}
}
JZ14 鏈表中倒數第k個節點(鏈表)
題目描述
輸入一個鏈表，輸出該鏈表中倒數第k個結點，
解
很樸素的雙指標，
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode p = head, q = head;
while(k > 0 && p != null) {
p = p.next;
k--;
}
if(k > 0)
return null;
while(p != null) {
p = p.next;
q = q.next;
}
return q;
}
}
JZ15 反轉鏈表(鏈表)
題目描述
輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭，
解
個人感覺想成“利用原來串列的所有節點，使用頭插法構造新鏈表”會比較簡單，
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode res = null, p = head;
// 頭插法
while(p != null) {
ListNode q = p;
p = p.next;
q.next = res;
res = q;
}
return res;
}
}
JZ16 合并兩個排序的鏈表(鏈表，分治)
題目描述
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則，
解
每次從兩個鏈表的頭節點中選一個值較小的節點，用尾插法插入結果鏈表中，最后可能會有其中一個鏈表還有節點剩下，直接讓其與結果鏈表相接即可，
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode res = null, p = list1, q = list2, tail = null;
// 對于無頭結點的鏈表題，可以通過手動構造一個頭來避免處理特殊情況
res = new ListNode(-1);
tail = res;
while(p != null && q != null) {
if(p.val <= q.val) {
tail.next = p;
p = p.next;
} else {
tail.next = q;
q = q.next;
}
tail = tail.next;
}
if(p != null)
tail.next = p;
if(q != null)
tail.next = q;
return res.next;
}
}
JZ17 樹的子結構
題目描述
輸入兩棵二叉樹A，B，判斷B是不是A的子結構，（ps：我們約定空樹不是任意一個樹的子結構）
解
首先可以使用遞回的方法實作判斷子結構是否匹配的演算法，然后使用遞回的方法對于A樹的每一個節點使用一次這個演算法，直到找到第一處成功匹配的子結構，（暫時不知道還能不能更快，看到一個思路是想辦法序列化二叉樹，空節點用一個題目中不會出現的節點值來填充，然后使用KMP，不過暫時沒有實作）
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root2 == null || root1 == null) return false;
boolean res = false, lRes = false, rRes = false;
res = ifCurrentNodeEquals(root1, root2);
if(!res) {
// 稍微更快一點：如果此處匹配成功，則不必繼續向下查找是否有匹配的子結構
lRes = HasSubtree(root1.left, root2);
rRes = HasSubtree(root1.right, root2);
}
return res || lRes || rRes;
}
public boolean ifCurrentNodeEquals(TreeNode tree1, TreeNode tree2) {
// 這兩個if和else if的陳述句稍微注意一下，其實對幾種情況進行了合并
if(tree2 == null) {
return true;
} else if(tree1 == null) {
return false;
} else if(tree1.val == tree2.val){
boolean lRes = ifCurrentNodeEquals(tree1.left, tree2.left);
boolean rRes = ifCurrentNodeEquals(tree1.right, tree2.right);
return lRes && rRes;
} else {
return false;
}
}
}
JZ18 二叉樹的鏡像(樹)
題目描述
操作給定的二叉樹，將其變換為源二叉樹的鏡像，
二叉樹的鏡像定義：源二叉樹
8
/ \
6 10
/ \ / \
5 7 9 11
鏡像二叉樹
8
/ \
10 6
/ \ / \
11 9 7 5
解
可以使用遞回，
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null) return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}
非遞回版本：遍歷每個節點并反轉每個節點的左右子樹
import java.util.*;
public class Solution {
public void Mirror(TreeNode root) {
if(root == null) return;
TreeNode p = root;
Stack<TreeNode> s = new Stack<TreeNode>();
while(!s.isEmpty() || p != null) {
if(p != null) {
s.push(p);
// reverse
TreeNode temp = p.left;
p.left = p.right;
p.right = temp;
p = p.left;
} else {
p = s.pop();
p = p.right;
}
}
}
}
JZ19 順時針列印矩陣(陣列)
題目描述
輸入一個矩陣，按照從外向里以順時針的順序依次列印出每一個數字，例如，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次列印出數字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解
個人很不擅長做二維陣列相關的題目，因為比較粗心，邊界條件總是理不清楚，得加強練習，個人解的思路如下：順時針列印時，方向總是遵循“水平-豎直-水平-豎直”的規律，水平方向列印完一條邊后，豎直方向需要列印的元素數會減少一個（避免重復列印角上的元素），反之亦然，重復這一程序，直至某一邊需要列印的元素數變為0，
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
int n = matrix.length;
if(n <= 0) return res;
// 下標j從-1開始計算更好控制
int m = matrix[0].length, i = 0, j = -1;
if(m <= 0) return res;
int direction = 1;
boolean ifHorizontal = true;
// n, m分別代表i, j當前要在對應方向上"前進"的步數
while(n > 0 && m > 0) {
if(ifHorizontal) {
int hLength = m;
while(hLength-- > 0) {
j += direction;
res.add(matrix[i][j]);
}
n--;
} else {
int vLength = n;
while(vLength-- > 0) {
i += direction;
res.add(matrix[i][j]);
}
m--;
direction *= -1;
}
ifHorizontal = !ifHorizontal;
}
return res;
}
}
一次回圈列印一圈的做法代碼會更簡潔，不過邊界條件需要計算好，
JZ20 包含min函式的堆疊(堆疊)
題目描述
定義堆疊的資料結構，請在該型別中實作一個能夠得到堆疊中所含最小元素的min函式（時間復雜度應為O（1）），
解
壓入堆疊中的最小值可能被彈出，因此需要記錄新最小值入堆疊之前的所有最小值，可以使用輔助堆疊來保存當前堆疊中的最小值和之前的最小值，至于在當前最小值之后入堆疊的、比當前最小值大的元素，因為它必將比當前最小值先出堆疊，永遠沒有可能成為某一時刻的最小值，因此不需要記錄這類元素的資訊，
import java.util.Stack;
public class Solution {
// 最小值堆疊的維護：
// 堆疊頂儲存當前堆疊內的最小值
// 如果當前入堆疊元素比堆疊頂元素大，則不理會（肯定會比最小值先出堆疊，沒必要記錄）
// 如果當前入堆疊元素小于等于堆疊頂元素，則將其加入最小值堆疊
Stack<Integer> dataStack = new Stack<>();
Stack<Integer> minStack = new Stack<>();
public void push(int node) {
dataStack.push(node);
if(minStack.isEmpty() || node <= minStack.peek()) {
minStack.push(node);
}
}
public void pop() {
int temp = dataStack.pop();
if(temp == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return dataStack.peek();
}
public int min() {
return minStack.peek();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143513.html
標籤：其他