class Solution {
private:
string recConv(int threshold[], string digit[], int num)
{
int i, upper, lower;
for(i=0; num<threshold[i];++i);
upper = num / threshold[i];
lower = num % threshold[i];
return (i<4? recConv(threshold, digit,upper)+" ":"") // if the upper part is billion, million, thousand, hundred, we still need to do recursive conversion, otherwise upper=1 and no need to output
+ digit[i] + (lower? " " + recConv(threshold, digit,lower):""); // if the lower part is non zero, need to do recursive conversion
}
public:
string numberToWords(int num) {
int threshold[] = {1000000000, 1000000, 1000, 100, 90, 80, 70, 60,50, 40,30,20,19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
string digit[] = {"Billion", "Million", "Thousand", "Hundred", "Ninety","Eighty", "Seventy","Sixty", "Fifty", "Forty", "Thirty", "Twenty", "Nineteen", "Eighteen", "Seventeen", "Sixteen", "Fifteen", "Fourteen", "Thirteen", "Twelve","Eleven", "Ten","Nine", "Eight", "Seven", "Six", "Five", "Four", "Three","Two", "One"};
if(!num) return "Zero";
return recConv(threshold, digit, num);
}
};
dong.wang.1694
@dong.wang.1694
Posts made by dong.wang.1694

Simple recursive C++ solution (use a lookup table)

My short c++ solution
It is a typical DP question. The only trick is that we need to do search from the bottom right to the top left corner. The reason is that: if we do search in a normal topleft to bottomright way, then at a middle point (i,j), we can not do local "greedy" decision (i.e. only keep the local optimal path and discard all the other paths) since there are two metrics here: one is the minimum points needed to reach the current point from the topleft corner and the other is the current left points that can be used for future move. We have to consider both to define "optimal path". However, if we do search in a reverse order, we only need to consider only one metric, which is the minimum points needed at (i,j) that enables us to move to the destination. We don't care how many points left at (i,j) when it moves from the topleft point, >=1 is enough.
The recursion relationship is dp[i][j] = max(1, min(dp[i1][j], dp[i][j+1])  dungeon[i][j]) (here max(1,) is to guarantee that at least 1 point left when entering into [i][j]). Since dp[i][j] is only related to dp[i1][j] and dp[i][j+1], so we can reduce dp to a onedimensional array and do the recursion in a reverse order.class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int row = dungeon.size(), col= dungeon[0].size(), i, j; vector<int> dp(col+1,INT_MAX); for(i=row1, dp[col1] = 1; i>=0;i) for(j=col1; j>=0; j) dp[j] = max(1, min(dp[j], dp[j+1])  dungeon[i][j]); return dp[0]; } };

Simple twostep C++ solution
class Solution { public: void reverseWords(string &s) { int len = s.size()+1, i=0, head=1, tail = 0, wrt=0; s.push_back(' '); // add an extra space to make sure the last word is reversed in the first step //twostep method, first reverse each word and clean the extra white spaces while(i<len) { if(isspace(s[i])) { if(head>=0) // currently search the end of a new word { // which means, this is the end of a new word tail = wrt1; while(head<tail) swap(s[tail], s[head++]); // reverse the new word s[wrt++] = ' '; head = 1; // indicate in search of the begin of a new word } ++i; //skip the space } else{ // if it is not a space character if(head<0) head = wrt; // if it is a new word, save head; s[wrt++] = s[i++]; // remove extra space } } //second step: reverse the whole string len = wrt==0?0:wrt; // be careful about the corner case, all space string for(tail = wrt, head =0; head<tail; ++head, tail) swap(s[head], s[tail]); s.resize(len); } };

My 24ms C++ solution (one trick explained)
The insertion sorting is quite trivial: starting from head, insert each node to the new sorted linked list.
Step 1) find the inserting position (i.e. move cur to the position just before head)
Step 2) insert head node in between of cur and cur>next;
Step 3) move head to the next one
Here, we use a dummy node to track the head of the sorted list.class Solution { public: ListNode* insertionSortList(ListNode* head) { ListNode dummy(INT_MIN), *cur=&dummy, *temp; while(head) { //go through each node in the list for(cur = &dummy; cur>next && cur>next>val<head>val; ) cur = cur>next; //step 1 temp = head>next; head>next = cur>next; cur>next =head; //step 2 head = temp; //step 3 } return dummy.next; } };
The above one has ~80ms performance. One trick to optimize it is that: in the above version, every time we insert a new node, we always search the inserting position from the beginning of the sorted list (i.e. in step1 for(cur = &dummy;...) and that is not neccessary. If the new tobeinserted node has a value larger than the value of the last inserted node, then that means the inserting position is after the inserting position found in the previous iteration, so we can use cur from the previous iteration directly. So we include
if(cur>val>head>val) cur = &dummy; // trick, reset cur only when needed
to reset cur to the start of the sorted list only when needed. This speeds up the algorithm to 24ms.
class Solution { public: ListNode* insertionSortList(ListNode* head) { ListNode dummy(INT_MIN), *cur=&dummy, *temp; while(head) { if(cur>val>head>val) cur = &dummy; // trick, reset cur only when needed for(; cur>next && cur>next>val<head>val; ) cur = cur>next; temp = head>next; head>next = cur>next; cur>next =head; head = temp; } return dummy.next; } };