algorithm001 · lcfgrn · Apr 20, 2019 · Apr 20, 2019 · Apr 20, 2019 · Apr 20, 2019
diff --git a/Week_01/id_20/LeetCode_21_递归实现 b/Week_01/id_20/LeetCode_21_递归实现
@@ -0,0 +1,36 @@
+/**
+ * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
+ * 
+ *  示例：
+ * 
+ *  输入：1->2->4, 1->3->4
+ *  输出：1->1->2->3->4->4
+ *
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+    	if(l1 == null) {
+    		return l2;
+    	}
+    	if(l2 == null) {
+    		return l1;
+    	}
+    	ListNode head = null;
+
+    	if(l1.val < l2.val) {
+    		head = l1;
+    		head.next = mergeTwoLists(l1.next,l2);
+    	} else {
+    		head = l2;
+    		head.next = mergeTwoLists(l1,l2.next);
+    	}
+    	return head;
+
+    }
+}
diff --git a/Week_01/id_20/LeetCode_21_链表实现 b/Week_01/id_20/LeetCode_21_链表实现
@@ -0,0 +1,59 @@
+/**
+ * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
+ * 
+ *  示例：
+ * 
+ *  输入：1->2->4, 1->3->4
+ *  输出：1->1->2->3->4->4
+ *
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+        if(l1 == null) {
+            return l2;
+        }
+        if(l2 == null) {
+            return l1;
+        }
+        ListNode head = null;
+        //用于扫描l1
+        ListNode p1 = l1;
+        //用于扫描l2
+        ListNode p2 = l2;
+        if(l1.val < l2.val) {
+            head = l1;
+            p1 = l1.next;
+        } else {
+            head = l2;
+            p2 = l2.next;
+        }
+        ListNode p = head;//p指向合并列表的最新节点
+        while(p1 !=null && p2 != null) {
+            //比较插入2个链表中元素的大小
+            if(p1.val < p2.val) {
+                //p1插入p后面
+                p.next = p1;
+                p1 = p1.next;
+            } else {
+                //p2插入p后面
+                p.next = p2;
+                p2 = p2.next;
+            }
+            p = p.next;
+        } 
+
+        if(p1 != null) {
+            p.next = p1;
+        } else if(p2 != null){
+            p.next = p2;
+        }
+        return head;
+
+    }
+}
diff --git a/Week_01/id_20/LeetCode_24_020.java b/Week_01/id_20/LeetCode_24_020.java
@@ -0,0 +1,35 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next; 
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode swapPairs(ListNode head) {
+        ListNode dummy = new ListNode(0);
+        dummy.next = head;
+        ListNode p = dummy;
+        ListNode h = head;
+
+        while (h != null) {
+            if (h != null && h.next != null) {
+                ListNode tmp = h.next;
+                //p指向两个节点中的第二个节点
+                p.next = tmp;
+                //交换位置
+                h.next = h.next.next;
+                tmp.next = h;
+
+                //继续遍历
+                p = p.next.next;
+                h = h.next;
+            } else {
+                p.next = h;
+                h = h.next;
+            }
+        }
+        return dummy.next;
+    }
+}
diff --git a/Week_01/id_20/LeetCode_441_二分渐进 b/Week_01/id_20/LeetCode_441_二分渐进
@@ -0,0 +1,19 @@
+class Solution {
+    public int arrangeCoins(int n) {
+        if(n == 1){
+            return 1;
+        }
+
+        int start = 0, end = n;
+        while(start + 1 < end){
+            int mid = (end + start)>>1;
+            if((long)mid*(mid+1) <= (long)2*n){
+                start = mid;
+            }
+            else{
+                end = mid;
+            }
+        }
+        return start;
+    }
+}
diff --git a/Week_01/id_20/LeetCode_441_数学公式 b/Week_01/id_20/LeetCode_441_数学公式
@@ -0,0 +1,35 @@
+/**
+ * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
+ * 
+ * 给定一个数字 n，找出可形成完整阶梯行的总行数。
+ * 
+ * n 是一个非负整数，并且在32位有符号整型的范围内。
+ * 
+ * 示例 1:
+ * 
+ * n = 5
+ * 
+ * 硬币可排列成以下几行:
+ * ¤
+ * ¤ ¤
+ * ¤ ¤
+ * 
+ * 因为第三行不完整，所以返回2.
+ * 示例 2:
+ * 
+ * n = 8
+ * 
+ * 硬币可排列成以下几行:
+ * ¤
+ * ¤ ¤
+ * ¤ ¤ ¤
+ * ¤ ¤
+ * 
+ * 因为第四行不完整，所以返回3.
+**/
+class Solution {
+    public int arrangeCoins(int n) {
+    	double k = -0.5d + Math.sqrt(0.25d+2*(double)n);
+    	return (int)Math.floor(k);
+    }
+}
diff --git a/Week_01/id_20/LeetCode_441_简单实现 b/Week_01/id_20/LeetCode_441_简单实现
@@ -0,0 +1,44 @@
+/**
+ * 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
+ * 
+ * 给定一个数字 n，找出可形成完整阶梯行的总行数。
+ * 
+ * n 是一个非负整数，并且在32位有符号整型的范围内。
+ * 
+ * 示例 1:
+ * 
+ * n = 5
+ * 
+ * 硬币可排列成以下几行:
+ * ¤
+ * ¤ ¤
+ * ¤ ¤
+ * 
+ * 因为第三行不完整，所以返回2.
+ * 示例 2:
+ * 
+ * n = 8
+ * 
+ * 硬币可排列成以下几行:
+ * ¤
+ * ¤ ¤
+ * ¤ ¤ ¤
+ * ¤ ¤
+ * 
+ * 因为第四行不完整，所以返回3.
+**/
+ class Solution {
+    public int arrangeCoins(int n) {
+    	int sum = 0;
+    	int k = 0;
+        if(n == 0)
+        	return 0;
+        if(n == 1)
+        	return 1;
+        while(sum - n < 0){
+        	k++;
+        	sum +=k;
+        }
+        return k-1;
+    }
+}
diff --git a/Week_01/id_20/LeetCode_81_020.java b/Week_01/id_20/LeetCode_81_020.java
@@ -0,0 +1,29 @@
+class Solution {
+    public boolean search(int[] nums, int target) {
+        int low = 0, high = nums.length - 1;
+        while (low <= high) {
+            int mid = low + (high - low) / 2;
+            if (nums[mid] == target) {
+                return true;
+            }
+            if (nums[mid] > nums[low]) {
+                if (target >= nums[low] && target <= nums[mid]) {
+                    high = mid - 1;
+                } else {
+                    low = mid + 1;
+                }
+            } else if (nums[mid] < nums[high]) {
+                if (target >= nums[mid] && target <= nums[high]) {
+                    low = mid + 1;
+                } else {
+                    high = mid - 1;
+                }
+            } else if (nums[low] == nums[mid]) {
+                low++;
+            } else {
+                high--;
+            }
+        }
+        return false;
+    }
+}
diff --git a/Week_01/合并2个有序列表（普通链表操作） b/Week_01/合并2个有序列表（普通链表操作）
@@ -0,0 +1,59 @@
+/**
+ * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
+ * 
+ *  示例：
+ * 
+ *  输入：1->2->4, 1->3->4
+ *  输出：1->1->2->3->4->4
+ *
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+        if(l1 == null) {
+            return l2;
+        }
+        if(l2 == null) {
+            return l1;
+        }
+        ListNode head = null;
+        //用于扫描l1
+        ListNode p1 = l1;
+        //用于扫描l2
+        ListNode p2 = l2;
+        if(l1.val < l2.val) {
+            head = l1;
+            p1 = l1.next;
+        } else {
+            head = l2;
+            p2 = l2.next;
+        }
+        ListNode p = head;//p指向合并列表的最新节点
+        while(p1 !=null && p2 != null) {
+            //比较插入2个链表中元素的大小
+            if(p1.val < p2.val) {
+                //p1插入p后面
+                p.next = p1;
+                p1 = p1.next;
+            } else {
+                //p2插入p后面
+                p.next = p2;
+                p2 = p2.next;
+            }
+            p = p.next;
+        } 
+
+        if(p1 != null) {
+            p.next = p1;
+        } else if(p2 != null){
+            p.next = p2;
+        }
+        return head;
+
+    }
+}
diff --git a/Week_01/合并2个有序链表（递归实现） b/Week_01/合并2个有序链表（递归实现）
@@ -0,0 +1,36 @@
+/**
+ * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
+ * 
+ *  示例：
+ * 
+ *  输入：1->2->4, 1->3->4
+ *  输出：1->1->2->3->4->4
+ *
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+    	if(l1 == null) {
+    		return l2;
+    	}
+    	if(l2 == null) {
+    		return l1;
+    	}
+    	ListNode head = null;
+
+    	if(l1.val < l2.val) {
+    		head = l1;
+    		head.next = mergeTwoLists(l1.next,l2);
+    	} else {
+    		head = l2;
+    		head.next = mergeTwoLists(l1,l2.next);
+    	}
+    	return head;
+
+    }
+}