Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Solution. We need to refer to this wiki digital root. Basically, the result is num mod 9. But we need to exclude 2 exceptions:
1. When num is 0, we need to return 0.
2. When mod is 0, we need to return 0.
In this way, easiest one should be 
check my code on github: link
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Follow up: Could you solve it in O(n2) runtime?
Solution. This problem is similar to Number of Triangle. Let’s see we have i, j fixed. As long as nums[i] + nums[j] + nums[k] < target, then all set of (i, j, j + 1), (i, j, j + 2),…, (i, j, k – 1), (i, j, k) are qualified.
By this characteristic, We use i for outer loop from 0 to n – 1. For each loop, we set a left = n + 1, right = n – 1. When sum less than target, we accumulate result and left++. Or we do right–.
Check my code on github: link
leetcode[Single Number III].
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].
Solution. Since there are only 2 numbers which appears 1 time, other number appears 2 times. Let assume the number which appears 1 time are a and b. When we do xor operation on each element in nums[], we get result of xorNum = a xor b.
Now, let’s get the first 1 in the xorNum counting fro right. We can do xorNum & (-xorNum). This skill is used in Indexed Binary Tree.
Let’s loop each num in nums[] for another round. We can divide num in 2 groups. One group has num & xorNum == 0, another group has num & xorNum != 0. In this way, we can get the 2 results.
check my code on github: link
Problem:
There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by a n x k cost matrix. For example,costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.
Solution. This problem is pretty similar to Lowest cost to adjust integer array, adjacencies differ less than k. dp[i][j] is calculated by each value in dp[i – 1] level.
We define dp[][]. Considering we already painted house [0,…,i], dp[i][j] means the minimum price when house i paints with color j.
Let minPos[i] is the color of the lowest price when we paint till house i
min1[i] is the lowest price when we paint till house i.
min2[i] is the second lowest price when we paint till house.
Then we have dp[i][j] = cost[i][j] + {
min1, when j != minPos[i – 1]
min2, when j == minPos[i – 1] }
dp[1][0] = cost[1][0] + min2[0] = 3 + 2
dp[1][1] = cost[1][1] + min1[0] = 2 + 1
No code for this problem because I don’t have premium access to leetcode or test cases.