Just don’t laugh.
I am an Artist, Mathematics Enthusiast, and Code Geek. But not a Nerd 🙂
Selected post for public viewing
Just don’t laugh.
A sliding window is an abstract concept commonly used in array/string problems. It is effective to solve problems like finding the Longest subarray/substring following a certain pattern. It uses 2 indices i and j to keep track of start and end of the window respectively.
Array sequence: 1,2,3,4,5,6,7. a window of [3,4,5,6] can be indicated by i-> 2; j-> 5;
Here is an example of using this concept:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb"
, the answer is "abc"
, which the length is 3.
Given "bbbbb"
, the answer is "b"
, with the length of 1.
Given "pwwkew"
, the answer is "wke"
, with the length of 3. Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<Character>(); int i = 0; int j = 0; int max_len = 0; while (i < s.length() && j < s.length()){ if(!set.contains(s.charAt(j))){ set.add(s.charAt(j)); j++; max_len = max_len>(j-i)? max_len : (j-i); }else{ set.remove(s.charAt(i)); i++; } } return max_len; } }
We need to write a function that takes a binary tree and returns true if it is a binary search tree, and false if not.
Review the definition of BST:
For a node, , every data value stored in the subtree rooted at
is less than
and every data value stored in the subtree rooted at
is greater than
. An example of a BinarySearchTree is shown in Figure 6.5.
The Wrong Way:
A common way of thinking this problem is: in each node check if (u.left < u < u.right).
u / \ left right
However, this does not cover all the BST cases. such as this one:
head => 4 / \ 1 5 /\ / \ 0 2 3 6
In the above case, every node u satisfies (u.left < u < u.right). However, according to the definition, it is not a BST as node “3” is on the right-hand side of node “4”.
The Correct Way:
Every value of node u, must be within the upper and lower value limit, if they exist. From above example, Node 4 is the head and has no upper or lower bound, so at this stage, it is still a valid node. Node 2 is between node 1(lower bound) and node 4(upper bound), so it is also a valid node. However, Node 3 is not between Node 4 and Node 5.
The question is how do we keep track of the lower and upper bound? 2 Rules:
So the recursive method is like this:
class TreeNode { int value; Node left; Node right; } public static boolean isBST(TreeNode node) { return isBSTHelper(node, null, null); } public static boolean isBSTHelper(TreeNode node, Integer lower, Integer upper){ if (lower!=null && node.value<lower) return false; if (upper!=null && node.value>upper) return false; boolean isLeftBST = true; boolean isRightBST = true; if (node.left!=null){ isLeftBST = isBSTHelper(node.left, lower, node.value); } if (node.right!=null){ isRightBST = isBSTHelper(node.right, node.value, upper); } return isLeftBST && isRightBST; }
Implement a function that finds the nth node in a linked list, counting from the end.
Examples:
head = 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null / None)
The third element of head counting from the end is 3.
head2 = 1 -> 2 -> 3 -> 4 -> (null / None)
The fourth element of head2 counting from the end is 1.
If the given n is larger than the number of nodes in the list, return null / None.
Solution 1 (two passes):
Find the link list length first using a function list_len(Node head), then calculate how many positions needs to be moved to the right from the head node.
public static Node nthFromLast(Node head, int n) {
int len = list_len(head);
System.out.println(len);
Node cur = head;
if(n>len || len<=0){
return null;
}
while(len>n){
len--;
cur=cur.child;
}
return cur;
}
public static int list_len(Node head){
int count=0;
Node cur = head;
while(cur!=null){
count++;
cur= cur.child;
}
return count;
}
This above solution need to iterate the link list twice, the worst running time is O(2n), n is the number of elements in the link list
Solution 2 (one pass):
Create 2 pointers p1 and p2, p2 is the nth position to the right of p1. move p1 and p2 together until p2 reaches the last null, then p1 points to the expected element.
public static Node nthFromLast(Node head, int n) {
Node p1 = head;
Node p2 = head;
int shift =n;
if (p2==null){
return null;
}
// shift p2 n positions to the right
while(shift>0){
if (p2==null){
return null;
}
shift--;
p2=p2.child;
}
//shift p2 and p1 together untill p2 reaches null
while(p2!=null){
p1=p1.child;
p2=p2.child;
}
return p1;
}
This above solution needs to iterate the link list only once, the worst running time is O(n), n is the number of elements in the link list.
To delete the found Nth Node from the End of the Linked List:
Given a linked list, remove the nth node from the end of a list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
We know how to find p1. To delete p1, we connect p1’s previous node to p1’s next node and we must keep track of p1’s previous node. Because given n is always valid, there is one corner case we must consider: After shifting p2, now p1 points to the head and p2 points to null:
1->2->3->Null (n = 3) 1->2->Null (n = 2) 1->Null (n = 1)
In above case, we just return head.next;
For other cases, we can just shift p2 one more position right, so that when p2 shifts to null, p1 is pointing to the previous node of the one needs to be deleted. The answer is accepted by Leetcode.
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p1 = head;
ListNode p2 = head;
int count = n;
while (count>0){
p2 = p2.next;
count--;
}
// corner case.
if (p2==null){
return head.next;
}
// shift p2 one more position
p2=p2.next;
while (p2!=null){
p1=p1.next;
p2=p2.next;
}
p1.next = p1.next.next;
return head;
}
Implement a function that takes a square 2D array (# columns = # rows = n) and rotates it by 90 degrees. Do not create a separate 2D array for the rotation, it rotates in the 2D array.
Example:
int a1[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
// rotate(a1, 3) should return:
// [[7, 4, 1],
// [8, 5, 2],
// [9, 6, 3]]
Example:
int a2[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
// rotate(a2, 4) should return:
// [[13, 9, 5, 1],
// [14, 10, 6, 2],
// [15, 11, 7, 3],
// [16, 12, 8, 4]]
To understand this problem, we need to analyze what is really going on in the rotation.
a. each element in the rotation is changing position with 3 other elements in the 2D array: a->b, b->c, c->d, d->a
[?, a, ?, ?] [?, ?, ?, b] [d, ?, ?, ?] [?, ?, c, ?]
If a={i,j}, then b={j,n-1-i}, c={n-1-i, n-1-j},d={n-1-j,i}
b. In each rotation happens in a “ring” (example, a1, a2, a2, b1, b2 ….d2, d2), we only swap the positions of n-2 elements in the first row. We do not swape n-1th element again because it is a duplicate (We swapped a1 with b1, and b1 does not need to be swapped again. So we only swap a1, a2, a3. ).
[a1, a2, a3, b1] [d3, ??, ??, b2] [d2, ??, ??, b3] [d1, c3, c2, c1]
So the outer loop should be for (int i=0; i < n-1; i++):
c. We swap the positions from the outside ring (1’s) to the inner rings (2’s). Each time the iteration decrements by 2 elements. At ith row, we swap from ith element to n-2-i th elements.
[1, 1, 1, 1] [1, 2, 2, 1] [1, 2, 2, 1] [1, 1, 1, 1]
So the inner loop is for (int j=i; j<n-1-i; j++)
Put everything together:
public static int[][] rotate(int[][] a, int n) { for (int i=0; i< n-1; i++){ for (int j=i; j<n-1-i; j++){ int temp = a[i][j]; a[i][j] = a[n-1-j][i]; a[n-1-j][i] = a[n-1-i][n-1-j]; a[n-1-i][n-1-j] = a[j][n-1-i]; a[j][n-1-i] = temp; } } return a; } }
Pop Efficient:
Push Efficient:
RoccoW_-07-_Fuck_Sidechain_Compression_on_Gameboy.mp3
ロッコ by RoccoW is licensed under a Attribution-ShareAlike License.
Based on a work athttps://roccow.bandcamp.com/album/-
Permissions beyond the scope of this license may be available atwww.soundcloud.com/roccowor contact artist via email.
1 st method (very inefficient):
get value for an number n
if n =2, output “It is a prime number”
set the value i =2;
set the value isPrime = True;
if i if n % i == 0, isPrime=False;
else i + 1;
output “It is a prime number” if isPrime is true
output “It is a not prime number” if isPrime is False.
The above method is inefficient. If the input is a very big prime number, it will make division from 2 all the way to n-1.
2nd method (slightly faster):
If :
an integer x < another integer n,
√n % x != 0 (n is not divisible by x )
then: n² % x !=0 (n² is not divisible by x)
Vise versa, n % x == 0, then n² % x ==0 ;
So, we can implement the 1st method, by looping only from 2 to n. we just have to modify the above algorithm “i<n” into “i<√n”. it optimized (n ) algorithm into (√n) algorithm.
3rd method (Sieve of Eratosthene):
This method works when given a number n and get all the prime numbers that is smaller than n. It filters out all the composite numbers, and left the prime number.
It works in this way:
The pseudo code would be:
if IsPrime[i] == true:
set IsPrime[ i2, i2+i, i2+2i, i2+3i, …] to False (not exceeding n)
4.output the indices in IsPrime[] ‘s item that is true.
I used CodeSkuptor. It allows Python scripts to run on the commonly used browser. Click the upper left “Run” button to start the games. ( CodeSkulptor runs in Chrome 18+, Firefox 11+, and Safari 6+)
——————————————————————
——————————————————————
Maya Batch Render doesn’t allow user to render multiple shots with one click. What if I want to let the computer create a render queue and automate the rendering process? You may install backburner to solve this. or there is another simple way of doing so without setting up the Manager and Server.
First of all, create a .bat file from Windows desktop.
The Template is like this:
C:\Progra~1\Autodesk\Maya2014\bin\render -r file -s <starting_frame> -e <ending_frame> -cam <camera> -rd “<render_location>” “<maya_file_directory>”
here under are the possible settings that you can modify
-r file: render from scene setting.
-s : starting frame
-e: ending frame
-cam: camera Name
-rd: where you want to save rendered image / where is the maya file.
For more info for rendering command, refer to this link.