二つのソート済み配列の中央値の効率的な探索
問題概要
二つの昇順にソートされた整数配列 nums1 と nums2 が与えられます。それぞれの配列のサイズは m と n です。これら二つの配列を結合した場合の中央値を求めてください。
このアルゴリズムの時間計算量は O(log (m+n)) である必要があります。
例1:
入力：nums1 = [1,3], nums2 = [2]
出力：2.00000
解説：結合配列 = [1,2,3] 、中央値 2
アプローチ1：マージ ...
5月16日 05:19 投稿
C++プログラミングの重要な注意点とベストプラクティス
1. イテレータとペアの値へのアクセス方法の違い
イテレータを介して値にアクセスする場合と、ループ内で直接ペアオブジェクトにアクセスする場合で、ドット演算子とアロー演算子の使い分けが必要です。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map hash_map;
for(int i = 0; i < ...
5月16日 00:32 投稿
【データ構造とアルゴリズム】(24)高度なデータ構造とアルゴリズム設計：二つのポインタを用いた問題の解法と実装例
4.6 Leetcodeにおける二つのポインタ手法
以下の問題はすべて二つのポインタを用いるものであり、加えて以下のケースも含まれる：
Leetcode3: 最長の重複しない部分文字列（ハッシュテーブルの章で扱った）
ホーソーのクイックソート
二分探索
など
ゼロの移動 - Leetcode 283
public class ZeroMoveLeetcode283 {
static void moveZeros(int[] nums) {
int ...
5月15日 22:47 投稿
競技プログラミングの復習と解法まとめ
7月は主に学校の夏期個人戦に参加し、その他の時間は主に学習やゲームに費やした。
上海大学プログラミングコンテスト 2024
上海地区のコンテストで、結果は芳しくなかった。主に実力不足が原因。
問題E - 無線ソフトウェア日
文字の出現頻度をカウントし、必要な文字数の最小値を求める問題。
#include <bits/stdc++.h>
using namespace std;
int main() {
int ...
5月15日 21:11 投稿
動的計画法による部分列問題の解法
問題1：最長増加部分列
最長増加部分列（Longest Increasing Subsequence, LIS）問題は、与えられた数列から、要素が厳密に増加する順序で並んでいる最長の部分列を見つける問題です。
class Solution {
public:
int lengthOfLIS(vector<int>& arr) {
// 1. DPテーブルの作成
int size = arr.size();
vector<int> dp(size, 1) ...
5月15日 12:10 投稿
素数和组合问题の解法
問題概要
与えられたn個の整数と整数k（k < n）があり、その中からk個の数を選んで和をとったときに、その和が素数になる組み合わせ数を求める問題。
例としてn=4, k=3で、数列が3,7,12,19のとき、選べる組み合わせは4通りある：
3+7+12 = 22
3+7+19 = 29
7+12+19 = 38
3+12+19 = 34
このうち素数は29のみなので、出力は1となる。
入出力形式
入力形式：
4 3 ...
5月14日 23:45 投稿
Pythonでプレイヤーの道徳値を管理するモジュールを実装
このタスクでは、ゲーム「Immaculate Mirage」におけるプレイヤーの道徳値管理モジュールをPythonで実装します。プレイヤーの選択に応じて道徳値（善、中立、悪）を更新し、極端なエンディングのトリガー判定、およびボスマッチ前のキャラクター生成に使用される道徳的傾向の割合を計算する純粋関数を作成します。
関数シグネチャとデータ構造
以下の2つの関数を ...
5月14日 22:02 投稿
線形リストの順序リスト実装（Pythonによる記述）
線形リストは2種類の格納形式に分けられます：順序格納と連結格納
順序格納：
順序格納では、線形リストのノードは論理順に連続したアドレスのメモリ領域に格納されます。この方法で格納された線形リストを順序リストと呼びます。2つの特徴があります：1. 論理順序と物理順序が一致している；2. データ要素間の関係はコンピュータ内での「物理的な位置の隣接」によって表現 ...
5月14日 20:08 投稿
Pythonでフィボナッチ数列を応用した階段の登り方を求解する
問題概要と考察
この問題では、n段の階段を1段または2段ずつ登る場合の、登り方の総数を求める必要があります。各段数における解を観察すると、フィボナッチ数列と同じパターンに従っていることが分かります。
1段：1通り
2段：2通り（1+1 または 2）
3段：3通り（1+1+1、1+2、2+1）
4段：5通り（1+1+1+1、1+1+2、1+2+1、2+1+1、2+2）
つまり、n段目までの登り方の総数 ...
5月14日 19:00 投稿