Merge pull request soulmachine#10 from advancedxy/master

soulmachine · soulmachine · commit 94089f56def5 · 2014-01-01T22:22:10.000-08:00
mergeTwoLists算法优化和tex文件中集合符号的修改
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,6 @@
+*.log
+*.toc
+*.aux
+*.idx
+*.out
+leetcode-cpp.pdf
diff --git a/C++/chapBruteforce.tex b/C++/chapBruteforce.tex
@@ -134,7 +134,7 @@ \subsubsection{增量构造法}
 \subsubsection{二进制法}
 本方法的前提是：集合的元素不超过int位数。用一个int整数表示位向量，第$i$位为1，则表示选择$S[i]$，为0则不选择。例如\fn{S=\{A,B,C,D\}}，则\fn{0110=6}表示子集\fn{\{B,C\}}。
 
-这种方法最巧妙。因为它不仅能生成子集，还能方便的表示集合的并、交、差等集合运算。设两个集合的位向量分别为$B_1$和$B_2$，则$B_1|B_2, B_1 \& B_2, B_1 \^ B_2$分别对应集合的并、交、对称差。
+这种方法最巧妙。因为它不仅能生成子集，还能方便的表示集合的并、交、差等集合运算。设两个集合的位向量分别为$B_1$和$B_2$，则$B_1\cup B_2, B_1 \cap B_2, B_1 \triangle B_2$分别对应集合的并、交、对称差。
 
 二进制法，也可以看做是位向量法，只不过更加优化。
 
diff --git a/C++/chapSorting.tex b/C++/chapSorting.tex
@@ -56,23 +56,20 @@ \subsubsection{分析}
 \subsubsection{代码}
 \begin{Code}
 //LeetCode, Merge Two Sorted Lists
-// 时间复杂度O(m+n)，空间复杂度O(1)
+// 时间复杂度O(min(m,n))，空间复杂度O(1)
 class Solution {
 public:
     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
-        ListNode head(-1);
-        for (ListNode* p = &head; l1 != nullptr || l2 != nullptr; p = p->next) {
-            int val1 = l1 == nullptr ? INT_MAX : l1->val;
-            int val2 = l2 == nullptr ? INT_MAX : l2->val;
-            if (val1 <= val2) {
-                p->next = l1;
-                l1 = l1->next;
-            } else {
-                p->next = l2;
-                l2 = l2->next;
-            }
+        if (l1 == nullptr) return l2;
+        if (l2 == nullptr) return l1;
+        ListNode h(-1);
+        ListNode *p = &h;
+        for (; l1 != nullptr && l2 != nullptr; p = p->next) {
+            if (l1->val > l2->val) { p->next = l2; l2 = l2->next; }
+            else { p->next = l1; l1 = l1->next; }
         }
-        return head.next;
+        p->next = l1 != nullptr ? l1 : l2;
+        return h.next;
     }
 };
 \end{Code}
diff --git a/C++/format.cls b/C++/format.cls
@@ -52,8 +52,8 @@ body={390pt,530pt},marginparsep=10pt,marginpar=50pt]{geometry}
 
 \setlength\abovecaptionskip{0pt}
   
-%\setmainfont{Times New Roman}
-\setmainfont{Linux Libertine O}
+\setmainfont{Times New Roman}
+%\setmainfont{Linux Libertine}
 %\setmainfont{TeX Gyre Pagella}
 \newfontfamily\urlfont{PT Sans Narrow}
 %\setmonofont[AutoFakeBold=1.6,AutoFakeSlant=0.17,Mapping=tex-text-tt]{Inconsolata}

-Original file line number
+Diff line change
@@ @@ -0,0 +1,6 @@ @@
 +*.log
 +*.toc
 +*.aux
 +*.idx
 +*.out
 +leetcode-cpp.pdf