筆記1
用兩個堆疊實作佇列
1、進堆疊時候進入第一個堆疊內
2、出堆疊時將堆疊1的內容再次壓入堆疊2中，即正向
3、如果堆疊2沒有元素，彈堆疊需要堆疊1進堆疊
4、如果堆疊2有元素，即上一次進堆疊元素沒有全部彈堆疊，直接彈堆疊
package esay.jz9用兩個堆疊實作佇列;
?
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 (stack2.isEmpty()) {
while (stack1.size() != 0) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
旋轉陣列的最小數字
/**
* 二分法實作
*
* @param array
* @return
*/
public static int minNumberInRotateArray(int[] array) {
if (array.length == 0) {
return 0;
}
?
int l = 0;
int r = array.length - 1;
?
while (l < r - 1) {
int mid = (l + r) >> 1;
if (array[l] < array[mid]) {
l = mid; //說明mid是在左邊遞減數列中
} else if (array[r] > array[mid]) {
r = mid; //說明mid是在右邊遞減數列中
} else {
int result = array[0];
for (int i = 0; i < array.length; i++) {
result = Math.min(result, array[i]);
}
return result;
}
}
?
return array[r];
}
二進制中1的個數
package esay.JZ15二進制中1的個數;
?
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().NumberOf1(10));
}
public int NumberOf1(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
if ((n & 1) == 1) {
res++;
}
n >>= 1;
}
return res;
}
}
?
列印從1到最大的n位數
package esay.JZ17列印從1到最大的n位數;
?
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
*
* @param n int整型 最大位數
* @return int整型一維陣列
*/
public int[] printNumbers (int n) {
// write code here
int max = (int) Math.pow(10, n);
int[] result = new int[max -1];
for (int i = 1; i <= max - 1; i++) {
result[i - 1] = i;
}
return result;
}
}
洗掉鏈表的節點
package esay.JZ18洗掉鏈表的節點;
?
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
* @param head ListNode類
* @param val int整型
* @return ListNode類
*/
public ListNode deleteNode(ListNode head, int val) {
// write code here
ListNode p = head;
//判斷是否洗掉的是頭結點
if (p.val == val) {
head = p.next;
return head;
}
//如果不是遍歷洗掉
while (p.next != null) {
if (p.next.val == val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return head;
}
}
?
?
class ListNode {
int val;
ListNode next = null;
?
public ListNode(int val) {
this.val = val;
}
}
鏈表中倒數最后k個結點
1、將節點全部放入list集合中
2、將最后第length - k 個元素輸出即可
package esay.JZ22鏈表中倒數最后k個結點;
?
import java.util.*;
?
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
* @param pHead ListNode類
* @param k int整型
* @return ListNode類
*/
public ListNode FindKthToTail(ListNode pHead, int k) {
// write code here
if (k == 0) {
return null;
}
List<ListNode> list = new ArrayList<>();
while (pHead != null) {
list.add(pHead);
pHead = pHead.next;
}
if (list.size() < k) {
return null;
}
return list.get(list.size() - k);
}
}
?
class ListNode {
int val;
ListNode next = null;
?
public ListNode(int val) {
this.val = val;
}
}
反轉鏈表
1、準備一個list
2、對鏈表遍歷，每個元素都插入list的第一個位置即可實作反轉
-
List -> add(index, element); // 插入特定位置
3、創建一個新的鏈表接收即可
package esay.JZ24反轉鏈表;
?
import java.util.ArrayList;
import java.util.List;
?
class ListNode {
int val;
ListNode next = null;
?
ListNode(int val) {
this.val = val;
}
}
?
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null) {
return null;
}
?
List<ListNode> reverse = new ArrayList<>();
while (head != null) {
reverse.add(0, head);
head = head.next;
}
?
ListNode temp = reverse.get(0);
ListNode result = temp;
for (int i = 1; i < reverse.size(); i++) {
temp.next = reverse.get(i);
temp = temp.next;
}
temp.next = null;
return result;
}
}
?
合并兩個排序的鏈表
1、保證下一個元素不為空，即temp.next = list2; 不能使用temp = list2;
package esay.JZ25合并兩個排序的鏈表;
?
class ListNode {
int val;
ListNode next = null;
?
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null || list2 == null) {
return list1 != null ? list1 : list2;
}
ListNode temp = new ListNode(-1);
ListNode result = temp;
?
while (list1 != null && list2 != null) {
if (list1.val >= list2.val) {
temp.next = list2;
list2 = list2.next;
} else {
temp.next = list1;
list1 = list1.next;
}
temp = temp.next;
}
?
if (list1 != null) {
temp.next = list1;
return result.next;
} else {
temp.next = list2;
return result.next;
}
}
?
public static void main(String[] args) {
ListNode temp = new ListNode(0);
ListNode result = temp;
?
temp.next = new ListNode(1);
temp = temp.next;
temp.next = null;
?
while (result != null) {
System.out.println(result.val);
result = result.next;
}
}
}
二叉樹的鏡像
1、遞回進行
package esay.JZ27二叉樹的鏡像;
?
import java.util.*;
?
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
?
public TreeNode(int val) {
this.val = val;
}
}
?
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
* @param pRoot TreeNode類
* @return TreeNode類
*/
public TreeNode Mirror(TreeNode pRoot) {
// write code here
if (pRoot == null) {
return null;
}
?
TreeNode pLeft = Mirror(pRoot.left);
TreeNode pRight = Mirror(pRoot.right);
?
pRoot.left = pRight;
pRoot.right = pLeft;
?
return pRoot;
}
}
對稱的二叉樹
1、左右不為空，且值相同
package esay.JZ28對稱的二叉樹;
?
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
?
public TreeNode(int val) {
this.val = val;
?
}
?
}
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
return recursion(pRoot, pRoot);
}
?
public boolean recursion(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
?
if (root1 == null || root2 == null || root1.val != root2.val) {
return false;
}
?
return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
}
}
?
順時針列印矩陣
1、從外到內一層一層列印
package esay.JZ29順時針列印矩陣;
?
import javax.management.MBeanRegistration;
import javax.swing.plaf.nimbus.AbstractRegionPainter;
import java.util.ArrayList;
public class Solution {
?
public static void main(String[] args) {
int[][] a = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
System.out.println(new Solution().printMatrix(a));
}
?
public ArrayList<Integer> printMatrix(int [][] matrix) {
if (matrix.length == 0) {
return null;
}
?
ArrayList<Integer> res = new ArrayList<>();
//左邊界
int left = 0;
//右邊界
int right = matrix[0].length - 1;
//上邊界
int up = 0;
//下邊界
int down = matrix.length - 1;
?
while (left <= right && up <= down) {
//左邊界到右邊界
for (int i = left; i <= right; i++) {
res.add(matrix[up][i]);
}
up++;
if (up > down) {
break;
}
for (int i = up; i <= down; i++) {
res.add(matrix[i][right]);
}
right--;
if (left > right) {
break;
}
for (int i = right; i >= left; i--) {
res.add(matrix[down][i]);
}
down--;
if (up > down) {
break;
}
for (int i = down; i >= up ; i--) {
res.add(matrix[i][left]);