今日は面接で根本的にアルゴリズム問題とは言えないアルゴリズム問題に 2 つ出会い、どちらも解けませんでした。恥ずかしくて言えないです。
今日は面接で根本的にアルゴリズム問題とは言えないアルゴリズム問題に 2 つ出会い、どちらも解けませんでした。恥ずかしくて言えないです。この分野の基礎があまりにも薄弱です。学習会のアルゴリズム問題を記録するためにブログを書きます。以前、いくつかの LeetCode を学びました。その時は自分が理解できたと思いましたが、今はすっかり忘れてしまいました。動的計画法などについて。
削除配列の指定要素#
これすら解けなかった
{1,2,3,4} から 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;
}
}
リンクリストを反転#
1>2>3>4 が 4>3>2>1 に変わる
public Node reverse(Node head){
if(head==null||head.next==null){
return head;
}
Node temp= head.next;//倒数第二のhead=3、temp=4に到達
Node newHead = reversr(head.next); //newHead=4
temp.next=head;//現在の3を4の次に設定
head.next=null;//最後の要素をnullに設定
return newHead;
}
頭結点挿入法：
public static Node reverseListByIteration(Node head){
Node temp;
Node result = new Node(-1);
while(head!=null){
temp=head.next;//headの次を保存してループするため、headが変わるので。
head.next=result.next;//resultの次、つまり-1の後ろをheadの次に設定、これで以前resultの後ろにあったものを新しい後ろに移動。
result.next=head;//次にheadをresultの後ろに接続
head=temp;//ループ用。
}
return result.next;
}
その場で反転法：
emmmm
中間順遍歴#
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list= new ArrayList<>();//これを外に置くべき
if(root.left!=null){
inorderTraversal(root.left);
}
list.add(root.val);
if(root.right!=null){
inorderTraversal(root.right);
}
return list;
}
前順遍歴#
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;
}
後順遍歴#
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;
}
単方向リストの倒数第 x 個を削除#
public static Node deleValue(Node head ,int x){
Node fast = head;//速いポインタ
Node slow = head;//遅いポインタ
for(int j =0;j<x-1;j++){//速いポインタが先に進むステップ数、図を描くとx-1であることがわかる。
fast=fast.next;
}
while(fast.next!=null){//速いポインタが末尾に到達したとき、遅いポインタが削除すべきノードを指す
fast=fast.next;
slow=slow.next;
}
slow.val=slow.next.val;//遅いポインタが指す次の値を現在の値に設定、
slow.next=slow.next.next;//次の値を現在の値に設定
return head; //頭結点を返す
}