Today in the interview, I encountered two algorithm questions that really can't be considered algorithm questions, and I couldn't write them out. I feel embarrassed to even mention it.
Today in the interview, I encountered two algorithm questions that really can't be considered algorithm questions, and I couldn't write them out. I feel embarrassed to even mention it. My foundation in this area is too weak. I will write a blog to record the algorithm questions from the study session; I had learned a few LeetCode problems before. At that time, I thought I had learned them, but now I have forgotten them all. Things like dynamic programming.
Delete specified elements from array#
I actually couldn't write this out
{1,2,3,4} delete 4
public class DeleArrayValue{
public static void main(String[] args){
Integer[] arr = {1,2,3,4};
arr=deleValue(arr,3);
System.out.print(arr.toString);
}
public static Integer[] deleValue(Integer[] array,Integer value){
int i=0
for(; i<array.length;i++){
if(array[i]==value) break;
}
if(i+1<array.length){
System.arraycopy(array,i+1,array,i,array.length-i-1);
}
array[array.length-1]=null;
return array;
}
}
Reverse linked list#
1>2>3>4 becomes 4>3>2>1
public Node reverse(Node head){
if(head==null||head.next==null){
return head;
}
Node temp= head.next;//When reaching the second to last, head=3, temp=4
Node newHead = reversr(head.next); //newHead=4
temp.next=head;//Set the current 3 to be the next of 4
head.next=null;//The last one points to null
return newHead;
}
Head insertion method:
public static Node reverseListByIteration(Node head){
Node temp;
Node result = new Node(-1);
while(head!=null){
temp=head.next;//Save the next of head for looping, because head changes.
head.next=result.next;//Set the next of result, which is after -1, to head's next, thus moving what was previously after result to the new back.
result.next=head;//Then attach head to the back of result
head=temp;//For traversal.
}
return result.next;
}
In-place reversal method:
emmmm
Inorder traversal#
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list= new ArrayList<>();//Just tested this should be placed outside
if(root.left!=null){
inorderTraversal(root.left);
}
list.add(root.val);
if(root.right!=null){
inorderTraversal(root.right);
}
return list;
}
Preorder traversal#
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list= new ArrayList<>();
list.add(root.val);
if(root.left!=null)
inorderTraversal(root.left);
if(root.right!=null)
inorderTraversal(root.right);
return list;
}
Postorder traversal#
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list= new ArrayList<>();
if(root.left!=null)
inorderTraversal(root.left);
if(root.right!=null)
inorderTraversal(root.right);
list.add(root.val);
return list;
}
Delete the x-th node from the end of a singly linked list#
public static Node deleValue(Node head ,int x){
Node fast = head;//Fast pointer
Node slow = head;//Slow pointer
for(int j =0;j<x-1;j++){//Fast pointer takes x-1 steps first, drawing a diagram shows this is x-1.
fast=fast.next;
}
while(fast.next!=null){//When the fast pointer reaches the end, the slow pointer points to the one to be deleted
fast=fast.next;
slow=slow.next;
}
slow.val=slow.next.val;//Set the value of the next pointed by the slow pointer to the current one,
slow.next=slow.next.next;//Then set the next pointed value to the current one
return head; //Return the head node
}