[Leetcode] Remove K Digits, Solution

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

[Thoughts]

首先分析一下什么样的数是最小的数。数总是有0~9的数字组成，高位的数字越小，这个数就越小。

所以，在对一个数做删除数字处理的时候，首先要从高位上把大的数字干掉，尽可能保留小的。

举个例子 num = "143219", k = 4

这个数字可以按照递增和递减分成三段 “1”， “4321”， “9”。递减子段上除了最后一个数字，其他的都可以被删除。

如果递减子段都处理完了，还没有删满k个，那就从最右边删（因为剩下的都是递增区间段了。）

[Code]

1:    string removeKdigits(string num, int k) {  
2:      string res = "";  
3:        
4:      for(int i =0; i<num.size(); i++) {  
5:        while(res.size()>0 && res.back() > num[i]&& k>0) {  
6:          res.pop_back();  
7:          k--;  
8:        }  
9:        res.push_back(num[i]);  
10:      }  
11:        
12:      // if k != 0, remove the digit from right  
13:      res.erase(res.size() - k, k);  
14:        
15:      // trim the zero  
16:      int i =0;  
17:      while(res[i] == '0' && i<res.size()-1) i++;  
18:        
19:      res.erase(0, i);  
20:        
21:      return res.size() == 0? "0": res;  
22:    }  

[Leetcode] Task Scheduler, Solution

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

[Thoughts]

这其实是一道数学题。题目已经说了，相同task之间要间隔n个interval，这就意味着任意一个循环子区间的长度是N+1.

这道题就简单了，统计在task表里出现次数最多的task是哪一个，出现了多少次。这里假设是A和C，分别出现了m次。那么我们肯定知道会有 m-1个循环子区间，而每个子区间的长度是N+1（task不够就必须用idle来补上）。而最后一个区间只有A和C各出现一次。

[Code]

1:    int leastInterval(vector<char>& tasks, int n) {  
2:      unordered_map<char, int> mp;  
3:        
4:      int count =0;  
5:      for(auto t : tasks) {  
6:        mp[t]++;  
7:        count = max(count, mp[t]);  
8:      }  
9:        
10:      int ans = (count-1)*(n+1);  
11:      // in case multiple tasks hold the same max count  
12:      for(auto e : mp) {  
13:        if(e.second == count) ans++;  
14:      }  
15:        
16:      return max((int)tasks.size(), ans);  
17:    }  

[Leetcode] Single Number III, Solution

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

[Thought]

关于single number的解法，因为只有一个未知数，比较直观：http://fisherlei.blogspot.com/2013/11/leetcode-single-number-solution.html。

这题有两个未知数，直接做异或肯定是不行的，那么如何通过一些变换把这道题分解开，使得可以应用Single Number的解法来做，才是这个题目有意思的地方。

首先，对于数组A, 假设存在b，c两个数字，在数组中只出现了一次，那么对于整个数组进行异或操作的话，

^[A]   =  b^c ,  因为其他的数因为出现了两次，异或的过程中就被清零了。

但是仅仅通过最后异或出来的值，是没办法求出b和c的值的，但是足以帮我们把b和c划分到不同的子数组中去。

一个整数有32位bit，对于b和c，除非两者是相同的数，否则一定存在第K位bit，两者是不同的。看下面的例子，

当找到这个K以后，就可以按照第K位bit是否等于1，将A数组划分成两个子数组，而这两个子数组分别包含了b和c，那么剩下的就只需要把single number的算法直接应用到这两个子数组上，就可以得到b和c了。

[Code]

1:  class Solution {  
2:  public:  
3:    vector<int> singleNumber(vector<int>& nums) {  
4:      int length = nums.size();  
5:      // get the xor result of the array, b ^ c  
6:      int xor_result = 0;  
7:      for(int i =0; i< length; i++) {  
8:        xor_result ^= nums[i];  
9:      }  
10:      // get the K of first bit, which equals 1  
11:      int first_one_index = 0;  
12:      for(first_one_index =0; first_one_index< 32; first_one_index++) {  
13:        if((xor_result>>first_one_index) & 1 == 1) {  
14:          break;  
15:        }  
16:      }  
17:      // use k to split the array into two part  
18:      // xor the sub array, if the element's Kth bit also equals 1, b  
19:      int xor_twice = 0;  
20:      for(int i =0; i< length; i++) {  
21:        if((nums[i]>>first_one_index) & 1 == 1) {  
22:          xor_twice ^= nums[i];  
23:        }  
24:      }  
25:      // with b, easy to get c by math  
26:      vector<int> result = {xor_twice, xor_result ^ xor_twice };      
27:      return result;  
28:    }  
29:  };  

Git hub: https://github.com/codingtmd/leetcode/blob/master/src/Single_Number_III.cpp

[Leetcode] Ugly Number, Solution

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

[Thoughts]

这题简单。既然已经说了ugly number是{2,3,5}的组合乘积构成的，那么判断逻辑也就简单了，对于任意一个给定的数字，拼命除这三个因子，最后能整除的就是ugly number，否则就不是。

逻辑看code

[Code]

1:  class Solution {  
2:  public:  
3:    bool isUgly(int num) {  
4:      if (num <= 0) return false;  
5:      while (num % 2 == 0) num /= 2;  
6:      while (num % 3 == 0) num /= 3;  
7:      while (num % 5 == 0) num /= 5;  
8:      return num == 1;  
9:    }  
10:  };  

[LeetCode] Linked List Cycle II, Solution

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

[Thoughts]

首先，比较直观的是，先使用Linked List Cycle I的办法，判断是否有cycle。如果有，则从头遍历节点，对于每一个节点，查询是否在环里面，是个O(n^2)的法子。但是仔细想一想，发现这是个数学题。

如下图，假设linked list有环，环长Y，环以外的长度是X。

现在有两个指针，第一个指针，每走一次走一步，第二个指针每走一次走两步，如果他们走了t次之后相遇在K点

那么       指针一  走的路是      t = X + nY + K        ①

             指针二  走的路是     2t = X + mY+ K       ②          m,n为未知数

把等式一代入到等式二中, 有

2X + 2nY + 2K = X + mY + K

=>   X+K  =  (m-2n)Y    ③

这就清晰了，X和K的关系是基于Y互补的。等于说，两个指针相遇以后，再往下走X步就回到Cycle的起点了。这就可以有O(n)的实现了。

 

[Code]

 1     ListNode *detectCycle(ListNode *head) {
 2         ListNode * first = head;
 3         ListNode * second = head;
 4         
 5         while(first != NULL && second != NULL)
 6         {
 7             first = first->next;
 8             second = second->next;
 9             if(second != NULL)
10                 second = second->next;
11             if(first == second)
12                 break;
13         }
14         
15         if(second == NULL) return NULL;
16         
17         // 一起往下走X步，就找到节点了。
18         first = head;
19         while(first!=second)
20         {
21             first = first->next;
22             second = second->next;
23         }
24         
25         return second;
26     }