This is my first try of nodejs, I just want to develope a small web application, from frontend to backend. The developing way is not smooth, I write this blog to trace the questions I have met and my own understanding. I hope it will be able to help those who are freshmen of nodejs, just as me.

Strucutre of Express4

The reason why I choose Express 4 is that I created a new Express project in WebStorm and WebStorm uses Express 4 as defult version.

From frist touched python, I have met many differeces from Java.
Now, I want to indroduce a new thing I learnt yesterday – *args and **kwargs. In fact, there is no need to confuse about what args and kwargs mean, the names are just conventional. let’s focus our attention on * and **.

We may often see * and ** used as arguments in function definitions, but they have different meanings when used in function calls. In the former case, they perform a pack process, and in the latter case, they perform a unpack process.

In Function Definition

Common Definition

def foo(a, b):
    print a, b

This is a common function definition in python. When we call it, we need to pass exact 2 arguments to it. less or more parameter will cause error.

foo(1, 2)
# output
1 2

foo(1)
# output 
TypeError: foo() takes exactly 2 arguments (1 given)

• 2Sum
• 3Sum
• 4Sum

2Sum

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2.

最开始的思路是比较暴力的解法，设两个嵌套循环，让数组内元素两两相加，直到某两者之和等于目标值，即为所求解，复杂度O(n^2)。

优化：
利用HashMap，只需遍历一次，O(n)。
遍历数组，每次先判断目标值与当前元素的差值，在hash表中是否已存在(表示存在于前面的数组元素中)。
若已存在，则取出对应元素的下标，并输出；若不存在，则将(元素，下标)的键值对存入hash表中。

• Best Time to Buy and Sell Stock
• Best Time to Buy and Sell Stock II
• Best Time to Buy and Sell Stock III
• Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

题目大意是：
有一个数组记录着一支股票的价格变化，第i个元素表示该股票在第i天的价格。
现在你最多只能对这支股票做一次操作(买入和卖出各一次)，设计一个算法使收益最大。
(吐槽一下，一开始都没看懂题目在说什么。)

解题思路：
收益最大的情形是，在最低价时买入，最高价时卖出。
用一个变量记录最小值，收益为当天价格减去最小值，更新最大收益。

1
2
3
4
5
6
7
8
9
10
11
12
13

public int maxProfit(int[] prices) {
       if (prices.length == 0)
           return 0;
       int minStock = prices[0], maxProfit = 0;
       for (int i = 1; i < prices.length; i++) {
           if (prices[i] < minStock)
               minStock = prices[i];
           else
               maxProfit = Math.max(maxProfit, prices[i] - minStock);
       }
       
       return maxProfit;
   }

• Next Permutation
• Permutations
• Permutations II

Next Permutation

#Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

总共分为三步：

1. 倒序遍历数组，直到找到nums[i] < nums[i+1]。 e.g. nums[5] = {1, 3, 5, 4, 2} -> i = 1.
2. 此时可以确保i位后的数都是降序的，再次在(i, N)范围内找到nums[j] > nums[i]，然后交换ij位置的数。 e.g. j = 3 -> nums[5] = {1, 4, 5, 3, 2}.
3. 将i位之后的数重新按升序排列。 e.g. nums[5] = {1, 4, 2, 3, 5}.
   阅读全文 »