OneAway
Problem
There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.
How to solve
Implement three method testing whether the array can be edited by each way. I can check the possibility of each edit by the following way.
Insert and Remove This means if we compared the strings they would be identical except for one character and the difference of the length is one.
Replace This means that two strings are different only in one place
Code
SortedMerge
problem
You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method B into A in sorted order.
how to solve
In this problem, I can use array A which has a large enough buffer at the end to hold B. So I insert elements into the back of the array in greedy.
code
Queue via Stacks
problem
Implement a MyQueue class which implements a queue using two stacks
how to solve
I implement two functions pop and push. The first one is getting and removing the oldest element in MyQueue. The second one is adding the element into MyQueue
Firstly, I implement push function in the same way as a stack.
Secondly, I implement pop function by using second list.
I can use the second stack to reverse the order of the elements in first stack. I push the elements of stack into the second stack
until the stack become to be an empty and then I can get the reverse order stack. Next, I pop the second stack and I add the elements of the remainder of the second stack into the first stack. I can get the stack which of the oldest element is deleted.
code
Linear Regression Models with Logarithmic Transformations
Abstract
一言でいうと、線形回帰モデルを扱う際に、特徴量の尺度をそろえる方法として、 logを取ってあげるとうまくいくらしい。
http://www.kenbenoit.net/courses/ME104/logmodels2.pdf
そうなる理由は↑を詳しくは参照
もとはといえば、kaggleの物件情報から物件価格を予測するコンペのディスカッションにてこの手法を発見
https://www.kaggle.com/apapiu/house-prices-advanced-regression-techniques/regularized-linear-models
I log transformed certain features for which the skew was > 0.75. This will make the feature more normally distributed and this makes linear regression perform better - since linear regression is sensitive to outliers. Note that if I used a tree-based model I wouldn't need to transform the variables.
上記リンク先のコメントの抜粋だが、日本語で要約すると次のことをいってるみたい。
良くなる理由としては、logを取ることで、外れ値の影響を受けやすい、線形回帰モデルにおいて、特徴量が正規分布に近づくことで、パフォーマンスが上がるとのこと。
how to
具体的にどういう風に前処理をするかは、以下リンクより引用
https://www.kaggle.com/apapiu/house-prices-advanced-regression-techniques/regularized-linear-models
Data preprocessing:
We're not going to do anything fancy here:
- First I'll transform the skewed numeric features by taking log(feature + 1) - this will make the features more normal
- Create Dummy variables for the categorical features
- Replace the numeric missing values (NaN's) with the mean of their respective columns
忘れないようにメモ。
srm705 SuperUserDo
Problem Statement
Fox Ciel just used the command "sudo" (super-user do) to gain administrative privileges in the UNIX-based operating system on her computer. She now wants to install several new programs. Each program has some dependencies: in addition to the program, the package manager has to install some libraries used by the program. The package repository contains exactly 1000 libraries. For simplicity, we will number them from 1 to 1000, inclusive. You are given the information about the dependencies of the programs Fox Ciel wants to install. More precisely, you are given the s A and B, both containing the same number of elements. For each valid i, one of the programs needs all libraries that have numbers between A[i] and B[i], inclusive. Note that the programs may have overlapping dependences: multiple programs may require the same library to be installed. Of course, in such cases it is sufficient to install such a library once. Calculate and return the total number of libraries that need to be installed.
how to solve
I use "imosu-ho"
code
276. Paint Fence (Google, LeetCode)
Problem
There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.
Note: n and k are non-negative integers.
How to solve
Firstly, I think this is the easy math problem, but actually this is dynamic programming. I have to clarify on "no more than two adjacent fence posts" There can be multiple 2 adjacent posts have same colors--a more clear way to put it is "no 3 adjacent posts have the same color"
for 4 post 2 color case (0 for black, 1 for red) 0011 is a valid solution, 0001 is not
code
57. Insert Interval(Google, LeetCode)
# Problem
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
# How to solve
I can solve this problem by using blute force searching. If I can find the interval which can be merge with newInterval, I update the newInterval and delete the interval. Then I insert the newInterval into the propare position and I can get solution by O(n).
# Code
<script src="https://gist.github.com/TakefumiYamamura/4431e039a1e49731a79e30c9d94456f6.js"></script>
