30 Nov 2019
Course Schedule
Description
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Explain
This is a topological sort problem. You can first construct the graph using each edges. And calculate indegree for each course. Once it is finished. You can push all 0-indegree courses into a queue. Keep poll the queue, and find all the related courses for this course, –indegree. Increase the count, And put the 0-indegree course into it.
25 Nov 2019
Integer to Roman
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
String[] roman = new String[]{“M”, “CM”, “D”,”CD”,”C”, “XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”};
int[] numerial = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
Convert an int to Roman format; Like 4 -> IV, 5->V;
The hardest part of this problem is that you need to list all unseen situation. Like 4 is IV, not IIII, 900 is CM, not DCCCC.
The best way to tackle this is to list all posiblle minimum unit of roman number, and then the problem is easy. Just substrsct the number with the largest unit of Roman, when it is larger/equal then 0, continue going.
public String intToRoman(int num) {
String[] roman = new String[]{"M", "CM", "D","CD","C", "XC","L","XL","X","IX","V","IV","I"};
int[] numerial = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
int i=0;
StringBuilder sb = new StringBuider();
while(num > 0) {
if(num-numerial[i] >= 0) {
num -= numerial[i];
sb.append(roman[i]);
} else {
i++;
}
}
return sb.toString();
}
23 Nov 2019
#ZigZag Conversion
Intro
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Idea
The description of the problem is misleading. This is just a way to output the string s;
And the rule is, give you a number n(NumRows), you start to scan the string. When i < n, keep i increasing, and when i reached n, then keep i decreasing.
Code
public String convert(String s, int numRows) {
int index = 0;
StringBuilder[] sb = new StringBuilder[numRows];
for(int i=0; i<numRows; i++) {
sb[i] = new StringBuilder();
}
while(index < s.length()) {
// first increse i from 0 -> n-1;
for(int i=0; i<numRows && index < s.length(); i++) {
sb[i].append(s.charAt(index));
index++;
}
// then decrease i fron n-2 -> 1;
for(int i=numRows-2; i>0 && index < s.length(); i--) {
sb[i].append(s.charAt(index));
index++;
}
}
StringBuilder ans = new StringBuilder();
for(StringBuilder ss : sb) {
ans.append(ss);
}
return ans.toString();
}
22 Nov 2019
The idea is simple, you need to put all 0 in the left, and all 2 on right, and leave 1 in the middle;
So we could do this with one 0-pointer, and one 2-pointer, which in general case, can be called: p_min, p_max;
Ok, we could start iterate the nums, and what we need to do is keep 0 on left and 2 on right;
public void sortColors(int[] nums) {
int p_min = 0;
int p_max = nums.length-1;
int i = 0;
// continue increase i, when we are not out of boundery;
while(i<=p_max) {
if(nums[i] == 0) {
// if we found min, we just swap it with the current index, and keep going
swap(nums, i, p_min);
i++;
p_min++;
} else if (nums[i] == 1) {
// if we found i, just leave it there and continue;
i++;
} else {
// if we found 2, let`s swap it to the end of the array, and update the p_max index smaller( cuz the last position is already the biggest, we need to find next one to swap);
swap(nums, i, p_max);
p_max--;
}
}
}
// normal swap procedure
private void swap(int[] n, int i, int j) {
int temp = n[i];
n[i] = n[j];
n[j] = temp;
}
}
10 Nov 2019
Word Ladder
This is a simple BFS problem, if you have defined what the problem acctually is:
You need to find a path from wordA -> wordB, and the only pathway is the words in dictList.
Try to image you want to travel from city A to cityB, there are a list of cities among A and B, you could only go to one of these city which are adjacent in one day, calculate how many days you need to spend to get the city B.
If the question is clear, now is the solution.
- Get all possible words you could move from wordA
- Use BFS search Everytime when you decide which city to move
- Record answer+=1 everytime you find a valid pathway.
- Only return when you reached into the destination. Otherwise return 0
Here comes the code part:
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
/* convert the List into Set first, become the operation
List.contains(sth) is O(n) complexity,
Set.contains(sth) is O(1) complexity.
*/
Set<String> dict = new HashSet<>(wordList);
if (wordList == null) return 0;
if(beginWord == endWord) return 1;
wordList.add(beginWord);
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(beginWord);
visited.add(beginWord);
int ans = 1;
while(!queue.isEmpty()) {
ans++;
int size = queue.size();
for(int i=0; i<size; i++) {
String curr = queue.poll();
for(String word : nextSteps(curr, dict)) {
if(visited.contains(word)) continue;
if(word.equals(endWord)) return ans;
queue.add(word);
visited.add(word);
}
}
}
return 0;
}
private List<String> nextSteps(String word, Set<String> wordList) {
// find all possible trans, and check if they are valid, all valid string are their possible
// next steps
List<String> steps = new ArrayList<>();
for(int i=0; i<word.length(); i++) {
for(char j='a'; j<='z'; j++) {
if (j == word.charAt(i)) continue;
String newWord = replace(word, i, j);
if(wordList.contains(newWord)) steps.add(newWord);
}
}
return steps;
}
private String replace(String word, int index, Character chara) {
StringBuilder sb = new StringBuilder();
char[] temp = word.toCharArray();
temp[index] = chara;
for(char c : temp) {
sb.append(c);
}
return sb.toString();
}
}