LeetCodeチェーンテーブル類テーマまとめ
3627 ワード
LeetCodeにおけるチェーンテーブルに関する問題のまとめ
1.チェーンテーブル加算add two numbers
1.1問題
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8
1.2考え方
1.2つのノードが空かどうかを判断する.リストが空の場合は、別のリストに戻ります.
2.チェーンテーブルにcarry/10が追加された値carry%10の加算値carryを定義します.
3.加算後、より長いチェーンテーブル部分が直接結果に追加され、主にキャリーすればよいことに注意する.
4.2つの数の加算carryは最大1である.
1.3コード
2.チェーンテーブルの部分反転
1.1問題
1.2考え方
1.3コード
3.並べ替えチェーンテーブルからの重量除去(重複要素のみ削除)
1.1問題
1.2考え方
1.3コード
4.チェーンテーブルの並べ替え(重複要素はすべて削除)
1.1問題
1.2考え方
1.3コード
5.チェーンテーブル区分
1.1問題
1.2考え方
1.3コード
6.単一チェーンテーブル共通ノード問題
1.1問題
1.2考え方
1.3コード
1.チェーンテーブル加算add two numbers
1.1問題
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8
1.2考え方
1.2つのノードが空かどうかを判断する.リストが空の場合は、別のリストに戻ります.
2.チェーンテーブルにcarry/10が追加された値carry%10の加算値carryを定義します.
3.加算後、より長いチェーンテーブル部分が直接結果に追加され、主にキャリーすればよいことに注意する.
4.2つの数の加算carryは最大1である.
1.3コード
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// ----
/*ListNode psum = new ListNode(0);
ListNode ptail = psum;
ListNode pcur;
ListNode p1 = l1;
ListNode p2 = l2;
int carry = 0;
int value;
while(p1 != null && p2 != null){
value = p1.val + p2.val + carry;
carry = value/10;
value = value%10;
pcur = new ListNode(value);
ptail.next = pcur;
ptail = pcur;
p1 = p1.next;
p2 = p2.next;
}
ListNode p = p1 >= p2 ? p1:p2;
while(p != null){
value = p.val + carry;
carry = value/10;
value = value%10;
pcur = new ListNode(value);
ptail.next = pcur;
ptail = pcur;
p = p.next;
}
if(carry!=0){
ptail.next = new ListNode(carry);
}
return psum;
//////////////////////////////////////////
if(l1==null)
return l2;
if(l2==null)
return l1;
ListNode head = new ListNode(0);
ListNode p = head;
int temp = 0;
while(l1!=null||l2!=null||temp!=0){
if(l1!=null){
temp+=l1.val;
l1=l1.next;
}
if(l2!=null){
temp+=l2.val;
l2=l2.next;
}
p.next=new ListNode(temp%10);
p=p.next;
temp/=10;
}
return head.next;*/
if(l1==null)
return l1;
if(l2 == null)
return l2;
ListNode l3 = new ListNode(0);
ListNode p = l3;
int carry = 0;
while(l1!=null || l2!=null){
if(l1!=null){
carry+=l1.val;
l1=l1.next;
}
if(l2!=null){
carry+=l2.val;
l2=l2.next;
}
p.next = new ListNode(carry%10);
carry = carry/10;
p = p.next;
}
if(carry == 1){
p.next = new ListNode(1);
}
return l3.next;
}
}
2.チェーンテーブルの部分反転
1.1問題
1.2考え方
1.3コード
3.並べ替えチェーンテーブルからの重量除去(重複要素のみ削除)
1.1問題
1.2考え方
1.3コード
4.チェーンテーブルの並べ替え(重複要素はすべて削除)
1.1問題
1.2考え方
1.3コード
5.チェーンテーブル区分
1.1問題
1.2考え方
1.3コード
6.単一チェーンテーブル共通ノード問題
1.1問題
1.2考え方
1.3コード