穩紮穩打，可攻可守。沒抓在手裡的成功都是不算的。
1.删除重複的數字
/**
* 給定一個排序連結清單，删除所有重複的元素，使得每個元素隻出現一次。
* <p>
* 示例 1:
* 輸入: 1->1->2
* 輸出: 1->2
* <p>
* 示例 2:
* 輸入: 1->1->2->3->3
* 輸出: 1->2->3
*/
連結清單結構
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
做過類似的題，隻是現在換了一種資料結構。最笨的辦法，取出所有值，存入LinkHashSet,然後由于它沒有下标，還得存入List裡面然後循環拼接
public ListNode method2(ListNode head) {
if (head==null||head.next==null)return head;
LinkedHashSet<Integer> integerHashSet=new LinkedHashSet<>();
while (head != null){
integerHashSet.add(head.val);
head=head.next;
}
ArrayList<ListNode> listNodes=new ArrayList<>();
for (int i:integerHashSet){
listNodes.add(new ListNode(i));
}
ListNode listNode=listNodes.get(0);
ListNode temp=listNode;
for (int i=1;i<listNodes.size();i++){
listNode.next=listNodes.get(i);
listNode=listNode.next;
}
return temp;
}
上面這種寫法真的很惡心，那另一種放法就比較人性化了，如果目前節點的下一個節點等于目前節點，那就讓目前節點的下一個節點等于下下個節點。
public ListNode method1(ListNode head) {
ListNode temp = head;
while (temp != null){
if (temp.next == null){
break;
}
if (temp.next.val == temp.val){
temp.next = temp.next.next;
}else {
temp = temp.next;
}
}
return head;
}
2.合并
/**
*給定兩個有序整數數組 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成為一個有序數組。
*
* 說明:
* 初始化 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]
*/
第一種思路，先把第二個數組并到第一個數組中去，然後使用排序算法進行排序
冒泡排序，比較簡單比較慢
public static void method1(int[] nums1, int m, int[] nums2, int n) {
for (int i:nums2){
nums1[m++]=i;
}
int c;
for (int i=0;i<nums1.length-1;i++){
for (int j=i+1;j<nums1.length;j++){
if (nums1[i]>nums1[j]){
c=nums1[i];
nums1[i]=nums1[j];
nums1[j]=c;
}
}
}
}
快速排序，比較麻煩比較快，數越多顯得越快
public static void method2(int[] nums1, int m, int[] nums2, int n) {
for (int i:nums2){
nums1[m++]=i;
}
if(nums1.length<2)return;
quickSort(nums1,0,nums1.length-1);
}
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基準位
temp = arr[low];
while (i<j) {
//先看右邊，依次往左遞減
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左邊，依次往右遞增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果滿足條件則交換
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最後将基準為與i和j相等位置的數字交換
arr[low] = arr[i];
arr[i] = temp;
//遞歸調用左半數組
quickSort(arr, low, j-1);
//遞歸調用右半數組
quickSort(arr, j+1, high);
}
但是無論快速排序怎麼快，它的複雜度也掉不到N，因為給定的兩個數組都是有序數組且第一個數組的長度可以包含第二個數組，要求排成從小到大的，那我們可以從大到小排列，從數組尾排到數組頭。這樣一遍循環便完事了。
public static void method3(int[] nums1, int m, int[] nums2, int n) {
int i = m-1;
int j = n-1;
int k = m+n-1;
while(i>=0&&j>=0){
if(nums1[i]>nums2[j]){
nums1[k--] = nums1[i--];
}else{
nums1[k--] = nums2[j--];
}
}
while(j>=0){
nums1[k--] = nums2[j--];
}
}
3.相同的樹
/**
* 給定兩個二叉樹，編寫一個函數來檢驗它們是否相同。
*
* 如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。
*
* 示例 1:
*
* 輸入: 1 1
* / \ / \
* 2 3 2 3
*
* [1,2,3], [1,2,3]
*
* 輸出: true
*
* 示例 2:
*
* 輸入: 1 1
* / \
* 2 2
*
* [1,2], [1,null,2]
*
* 輸出: false
*
* 示例 3:
*
* 輸入: 1 1
* / \ / \
* 2 1 1 2
*
* [1,2,1], [1,1,2]
*
* 輸出: false
*/
樹的結構
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
該題我的第一個想法是把兩顆數分别存到兩個數組中，然後比較兩個數組是否相等，但我發現這種方法很難實作而且複雜無比，周遊樹的時候還要添加null節點，然後想到了遞歸，可以使用遞歸解決此問題，不斷比較想同位置上的值，相同繼續比較左右子樹，不同傳回false。
public static boolean method1(TreeNode p,TreeNode q){
if (p == null && q == null) {
return true;
} else if (p == null) {
return false;
} else if (q == null) {
return false;
} else if (p.val != q.val) {
return false;
}
return method1(p.left, q.left) && method1(p.right, q.right);
}
簡化判斷流程
public static boolean method2(TreeNode p,TreeNode q){
if(p==null && q==null){
return true;
}
if(p!=null && q!=null && p.val==q.val ){
return method2(p.left,q.left) && method2(p.right,q.right);
}else {
return false;
}
}
再次簡化
public static boolean method3(TreeNode p,TreeNode q){
if(p == null) return q == null;
if(q == null||p.val!=q.val) return false;
return method3(p.left,q.left)&&method3(p.right,q.right);
}
4.對稱的樹
/**
* 給定一個二叉樹，檢查它是否是鏡像對稱的。
*
* 例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的。
*
* 1
* / \
* 2 2
* / \ / \
* 3 4 4 3
*
* 但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:
*
* 1
* / \
* 2 2
* \ \
* 3 3
*
* 說明:
* 如果你可以運用遞歸和疊代兩種方法解決這個問題，會很加分。
*/
樹的結構
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
思想和上一題一樣，前面做一些判斷，後面遞歸比較對稱位置
public boolean method1(TreeNode root) {
if (root==null)return true;
if (root.left==null) return root.right==null;
if (root.right==null||root.left.val!=root.right.val)return false;
return isSame(root.left,root.right);
}
public static boolean isSame(TreeNode p, TreeNode q){
if(p == null) return q == null;
if(q == null||p.val!=q.val) return false;
return isSame(p.left,q.right)&&isSame(p.right,q.left);
}
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)