删除数字

yingl · yingl · commit bc80328db106 · 2016-08-14T13:49:41.000+08:00
diff --git a/delete_digits.py b/delete_digits.py
@@ -0,0 +1,35 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    """
+    @param A: A positive integer which has N digits, A is a string.
+    @param k: Remove k digits.
+    @return: A string
+    """
+    def DeleteDigits(self, A, k):
+        # write you code here
+        '''
+        既然是删除k个数字，可以理解为保留m个数字，m = len(A) - k.
+        1. 扣掉最后m个数字，从前面找到一个最小数。
+        2. 从前面最小数位置之后开始，扣掉最后m - 1个数字，再找一个最小数。
+        3. 继续。。。
+        '''
+        digits = []
+        start = 0
+        k = len(A) - k
+        while k > 0:
+            min_index = self._min(A, start, k)
+            digits.append(A[min_index])
+            start = min_index + 1
+            k -= 1
+        ret = 0
+        for d in digits:
+            ret = ret * 10 + int(d)
+        return ret
+        
+    def _min(self, A, start, k):  # 找到A[start:len(A) - k]里最小书的索引
+        min_index = start
+        for i in xrange(start + 1, len(A) - k + 1):
+            if A[i] < A[min_index]:
+                min_index = i
+        return min_index
