興味深いアルゴリズムを知っていますか?

[[428794]]

この記事はWeChatの公開アカウント「WeDoctor Front-end Technology」から転載したもので、著者はSun Lingzhiです。この記事を転載する場合は、WeDoctor フロントエンドテクノロジーパブリックアカウントにお問い合わせください。

ID番号に基づいて性別と年齢を計算します

1. IDカード番号の国家標準

1. 範囲

「公民身分番号」（GB11643-1999）この標準は、公民身分番号のコード化オブジェクト、番号構造、および表現形式を規定し、各コード化オブジェクトが一意かつ不変の法的番号を取得するようにします。

2. 数値構造

国民識別番号は、17 桁のボディコードとチェックコードで構成される特徴的な組み合わせコードです。配列順序は、左から右へ、6桁の住所コード、8桁の生年月日コード、3桁のシーケンスコード、1桁のチェックコードです。

2.1 住所コード

コーディング対象が登録されている郡（市、旗、地区）の行政区分コードを示します。

2.2. 生年月日コード

エンコードされたオブジェクトの誕生年、月、日を示します

2.3 シーケンスコード

同じ住所コードで特定される地域内で、同じ年月日に生まれた人に割り当てられた通し番号を表します。通し番号の奇数は男性、偶数は女性に割り当てられます。

2.4. 検証コード

最初の 17 桁に基づいて、ISO 7064:1983.MOD 11-2 のチェックサム計算方法を使用してチェックサムを計算します。

（１）１７桁のボディコードの加重和の式：S = Sum(Ai * Wi)

ID番号	1	1	0	1	0	5	1	9	4	9	1	2	3	1	0	0	2
重み係数	7	9	10	5	8	4	2	1	6	3	7	9	10	5	8	4	2
あい*ウィ	7	9	0	5	0	20

S = 7 + 9 + 0 + 5 + 0 + 20 + 2 + 9 + 24 + 27 + 7 + 18 + 30 + 5 + 0 + 0 + 4 = 167

（２）係数を計算する：Y = mod(S, 11) Y = 167 % 11 => 2

（３）モジュールを通じて対応するチェックコードを取得する

型	0	1	2	3	4	5	6	7	8	9	10
コードを確認する	1	0	バツ	9	8	7	6	5	4	3	2

モジュラスが 2 の場合、チェックコードは X です。

2. コードの実装

1. IDカード番号の正確性を確認する

定数 WEIGHT = [7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2]
定数 MO = [1,0, 'X' ,9,8,7,6,5,4,3,2] 
 
関数isRightId(id){
  定数 arr = id.split( '' )
  const checkNumber = arr.pop() // チェックコードを削除し、popの戻り値をcheckNumberに代入します
  合計を0とする
  arr.forEach((ele,インデックス) => {
合計+= 要素 * 重量[インデックス]
  })
  定数m =合計% 11
  定数結果 = MO[m]
結果を返す+ '' === checkNumber
 } 
 
 console.log(isRightId( '11010519491231002X' )) //真 
 console.log(isRightId( '110105194912310029' )) //偽

2. ID番号で年齢を計算する

関数getAge(id){
  // 1. まずID番号の正しさを確認する
  // 2. 人が生きているかどうかを判断する
  定数年= id.substr(6,4)
  定数月= id.substr(10,2)
  定数日= id.substr(12,2) 
   
  const timeBrth = 新しいDate (`${年}/${月}/${日}`).getTime()
  const timeNow = 新しい日付().getTime()
  定数 longTime = timeNow - timeBrth
  定数日数 = longTime / (1*24*60*60*1000) 
   
  結果 = ''  
  if(日数<31){
  結果 = parseInt(days) + 'days'  
  }そうでない場合(日数<365){
   結果 = `${parseInt(days/30)}か月${parseInt(days%30)}日`
  }それ以外{
   結果 = `${parseInt(days/365)} 年${parseInt(days%365/30)} か月${parseInt(days%365%30)} 日`
  }
結果を返す
}
 console.log(getAge( '11010519491231002X' )) // 71歳8ヶ月16日
console.log(getAge( '11010520210820002X' )) // 6日
console.log(getAge( '11010520210720002X' )) // 1ヶ月と7日

3. ID番号で性別を判別する

関数getSex(id){
  // 1. まずID番号の正しさを確認する
  定数 性別 = id.substr(16,1)
性別%2を返しますか? '男性' : '女性'  
 }
 console.log(getSex( '11010519491231002X' )) // 女性
console.log(getSex( '11010520210820001X' )) // 男性

3. その他

1. 性別適合手術後、ID番号は変更されますか？

トランスジェンダーの人が身分証明書の性別を変更した場合、戸籍を所在する警察署の告示に基づいて身分証明書番号が変更されます。

2. 年齢を計算する前に、まずその人がまだ生きているかどうかを確認する必要があります。

IV. 参考文献

国民識別番号 (GB11643-1999)

動的プログラミング

1. 定義

動的プログラミング (DP) は、意思決定プロセスを最適化するプロセスであるオペレーションズリサーチの分野です。

これは単純に、従来の再帰の最適化として理解できます。 DP の実践では、再帰関係と境界条件が非常に重要です。

2. シンプル：階段を登る

トピック

階段を登っているとします。建物の最上部に到達するまでに n 歩かかります。

一度に1段または2段登ることができます。建物の最上階まで登るには、何通りの方法がありますか?

n は正の整数であることに注意してください。

入力: 2
出力: 2
説明: 建物の最上階に到達するには 2 つの方法があります。
 1. 1次 + 1次
2. 2次

例2:

入力: 3
出力: 3
説明: 屋根に登るには 3 つの方法があります。
 1. 1次 + 1次 + 1次
2. 1次 + 2次
3. 2次 + 1次

コード：

 // 配列内のデータをキャッシュする
var 登る階段 =関数(n) {
    dp = []とする
    0 = 1;
    1 = 1;
 ( i=2;i<=n;i++とします){
      dp[i]=dp[i-1]+dp[i-2];
    }
 dp[n]を返します。
 }; 
 
 // 再帰の使用
var 登る階段 =関数(n) {
    if(n===1) 1を返す
    if(n===2) 2を返す
戻り値:climbStairs(n-1) +climbStairs(n-2)
 };

アイデア:

f(x)=f(_x_?1)+f(x_?2) x_番目のステップに登る方法の数は、x-1番目のステップに登る方法の数とx-2番目のステップに登る方法の数の合計です。

LeetCode の実行結果:

3. 中: 最長回文部分文字列

トピック

文字列 s が与えられた場合、 s 内の最長の回文部分文字列を検索します。

例1:

入力: s = "babad"  
出力: "bab"  
説明: 「aba」も適切な答えです。

例2:

入力: s = "cbbd"  
出力: "bb"

アイデア:

s[i+1 : j-1]が回文であり、sのi番目とj番目の文字が同じである場合、s[i:j]は回文です。

つまり、P(i,j)=P(i+1,j?1)かつ(Si == Sj)です。

境界条件: 部分文字列の長さは 1 または 2 です。長さが 1 の部分文字列の場合、それは明らかに回文です。長さが 2 の部分文字列の場合、2 つの文字が同じであれば回文です。

P(i, i) = 真
P(i, i+1) = (Si == Si+1)

コード：

関数最長回文(s) {
     // まず文字列の長さを判定し、1の場合は直接返す
     len = s.lengthとします
     長さが2未満の場合はsを返す
      
     // 変数を初期化する
     maxLen = 1 とします
     開始= 0 
      
     // dp[i][j]はs[i..j]が回文かどうかを示します
     dp = []とする
     // 初期化: 長さ 1 のすべての部分文字列は回文です
(i = 0; i < len; i++)の場合{
       dp[i] = []
       dp[i][i] =真 
     } 
      
     // 文字列を配列に分割する
     charArray = s.split( '' )とします。 
      
     // 再帰開始
for (let L = 2; L <= len; L++) { // 部分文字列の長さを列挙する
       // 左の境界を列挙します。左の境界の上限はより緩く設定できます
(i = 0; i < len; i++)の場合{
         // 右の境界は L と i によって決定できます。つまり、j - i + 1 = L です。
         j = L + i - 1 とします。
         // 右の境界を越えた場合は、現在のループを終了します
         (j >= len)の場合{
           壊す;
         }
         // 回文かどうかを判定する
         charArray[i] !== charArray[j] の場合 {
           dp[i][j] =偽 
         }それ以外{
           // 部分文字列が回文であり、その長さが 2 より大きい場合、最初と最後の 2 文字を削除した後も回文のままです。
           フラグ = j - i < 3 とする
           dp[i][j] = フラグ ?真: dp[i + 1][j - 1]
         }
         // dp[i][L] == trueの場合、部分文字列 s[i..L] は回文であることを意味します。回文の長さと開始位置を記録します。
         dp[i][j] && j - i + 1 > maxLenの場合{
           最大長さ = j - i + 1;
開始= i;
         }
       }
     }
 s.substring ( begin , begin +maxLen)を返します。
   }
   console.log(longestPalindrome( 'babad' ), 'babad' ) // bab babad
   console.log(longestPalindrome( 'cbbd' ), 'cbbd' ) // bb cbbd

LeetCode の実行結果:

4. 難しさ：雨水の収集

トピック：

幅 1 の各列の高さを表す n 個の非負の整数が与えられた場合、このように配置された列が雨が降った後にどれだけの雨水を受け取ることができるかを計算します。

例1:

入力: 高さ = [0,1,0,2,1,0,1,3,2,1,2,1]
出力: 6
説明: 上記は配列 [0,1,0,2,1,0,1,3,2,1,2,1] で表される高さマップです。この場合、6 単位の雨を受け取ることができます (青い部分が雨を表します)。

例2:

入力: 高さ = [4,2,0,3,2,5]
出力: 9

コード：

関数trap(高さ) {
    // 条件が満たされない場合は直接戻ります
    len = height.length;とします。
    len<=2の場合0を返します。 
 
    let maxLeft = []; // i番目の列の左側にある最も高い列の高さ
    let maxRight = []; // i番目の列の右側にある最も高い列の高さ
 
    最大左[0] = 高さ[0];
 (i=1; i<len; i++)の場合
            maxLeft[i] = Math.max (height[i], maxLeft[i-1]) // 動的転送
    } 
 
    最大右[len-1] = 高さ[len-1];
 (j=len-2; j>=0; j --) {  
            maxRight[j] = Math.max (height[j], maxRight[j+1]) // 動的転送
    } 
 
    合計を0とします。
 (let i=0;i<len;i++)の場合、合計+=Math.min ( maxLeft[i],maxRight[i])-height[i]; 
 
戻る 合計;
 }

アイデア:

各柱が受ける雨水の量は、柱の両側にある最も高い柱の最小値から柱の高さを引いた値になります。

LeetCode の実行結果:

付録: ダブルポインタ方式

コード：

関数trap(高さ) {
   ans=0とします。
 (i=1; i<height.length-1; i++)の場合{
   l_hight = height[i]とします。
   r_hight = height[i]とします。 
 
                           // 列 i の右側にある最も高い列の高さを見つける
(r=i; r<height.length; r++)の場合{
    高さ[r]>r_hightの場合、r_hight=高さ[r];
   } 
 
   // 列 i の左側にある最も高い列の高さを見つける
(l=i; l>=0; l --)の場合{  
    高さ[l]>l_hightの場合、l_hight=高さ[l];
   } 
 
   ans+= Math.min (l_hight,r_hight)-height[i];
   }
回答を返す;
 }

LeetCode の実行結果:

5. 参考文献

出典: LeetCode

https://leetcode-cn.com/problems/階段登り/

https://leetcode-cn.com/problems/longest-palindromic-substring/

https://leetcode-cn.com/problems/traping-rain-water/ （英語）

貪欲アルゴリズム

1. 定義

問題を解決するときは、常にその時点で最善と思われる選択をしてください。

2. クッキーを分ける

あなたが素晴らしい親で、子供たちにクッキーをあげたいとしましょう。ただし、子供一人につき与えられるクッキーは最大で 1 枚のみです。各子供 i には食欲値 g[i] があり、これは子供の食欲を満たすクッキーの最小サイズです。また、各クッキー j にはサイズ s[j] があります。 s[j] >= g[i]の場合、クッキーjを子iに割り当てることができ、子は満足します。あなたの目標は、できるだけ多くの子供たちを満足させ、最大の価値を生み出すことです。

例1: 入力: g = [1,2,3]、s = [1,1] 出力: 1

例2: 入力: g = [1,2]、s = [1,2,3] 出力: 2

関数findContentChildren1(子供、クッキー){
  children = children.sort((a, b) => a - b)
  クッキー = cookies.sort((a, b) => a - b)
  childrenLength = children.length とします。
  CookiesLength = cookies.lengthとします
  カウントを 0 にする
( i = 0、j = 0、i < childrenLength && j < cookiesLength、i++、j++){
    while(j < cookiesLength && children[i] > cookies[j]){
      j++
    }
    if(j < クッキーの長さ){
カウント++
    }
  }
戻る カウント 
 } 
 
 
コンソール.log(findContentChildren1([1,2,3], [1,1])) // 1
コンソール.log(findContentChildren1([1,2], [1,2,3])) // 2
コンソール.log(findContentChildren1([1,2,3], [1,1,3,4])) // 3

中心的なアイデア:

子供たちの食欲とビスケットのサイズを小さいものから大きいものへと分類します。
forループは、子供の食欲children[i]とクッキーcookies[j]のサイズの関係を走査して比較します。現在のクッキーが子供の食欲を満たせない場合は、次のクッキーが比較のために選択されます。
子供の食欲が満たされ、j が範囲内であれば、カウントは 1 増加します。

コードの解釈:

findContentChildren 関数を定義します。この関数は、children: 子供の食欲、cookies: クッキーのサイズという 2 つのパラメータを受け入れます。
子供とクッキーを小さいものから大きいものへと分類します。
子供の食欲を満たすことができる数を定義し、最終的にその数を返します。
プロセスをループし、children[i] > cookies[j]、つまり現在のクッキーが子を満たすことができない場合、j++ は比較のために次のクッキーを選択します。
children[i] <= cookies[j]、つまり現在のクッキーが子の条件を満たし、j が範囲内にある場合、count は 1 増加します。
次のループに入ります (つまり、次の子の満足を試みます)。

3. 株を買う

整数配列 prices が与えられます。ここで、i 番目の要素は i 日目の株価を表し、整数 fee は株式の取引手数料を表します。取引回数に制限はありませんが、取引ごとに手数料を支払う必要があります。すでに株を購入している場合は、売却するまで株を買い続けることはできません。得られた利益の最大値を返します。注: ここでの取引とは、株式の購入、保有、売却の全プロセスを指します。手数料は取引ごとに 1 回のみお支払いいただく必要があります。

例 1: 入力: prices = [1, 3, 2, 8, 4, 9]、 fee = 2、出力: 8

説明する：

達成可能な最大利益:

ここで買う価格[0] = 1 ここで売る価格[3] = 8 ここで買う価格[4] = 4 ここで売る価格[5] = 9 合計利益: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

例 2: 入力: prices = [1,3,7,5,10,3]、 fee = 3 出力: 6

関数maxProfit(リスト, 手数料){
  定数長さ = リスト.長さ
  let buy = list[0] + fee // 仮定: 購入時間は1日目
  利益を0にする
( i = 1 とします; i < 長さ; i++){
    if(list[i]+fee < buy){ // 株価が下がったら購入時間を調整する
      購入 = リスト[i]+手数料
    } else if(list[i] > buy){ // 利益があれば売る
      profit += list[i] - buy // 利益を計算する
      buy = list[i] // 購入タイミングを調整する
    }
  }
利益を返す
} 
 
 console.log(maxProfit([1, 3, 2, 8, 4, 9], 2)) // 8
コンソール.log(maxProfit([1,3,7,5,10,3], 3)) // 6

コードの解釈:

2つのパラメータを受け入れる関数maxProfitを定義します。リストは株価のトレンド、手数料は手数料です。
利益を定義し、最後に利益を返す
仮定: 購入機会は1日目です (つまり: list[0])
株価が下がったら、購入時間を翌日に調整する
利益が出たら売却し、利益を計算して再度購入タイミングを調整する（つまり、ステップ3、4、5をループする）

中心的なアイデア:

仮定: 購入のチャンスは1日目
株価が下がったら、購入時間を翌日に調整する
利益があれば売却して利益を計算する
再び - 仮定: 時間を稼ぐ (ループステップ 1 ～ 3)

4. 手をつなぐカップル

N 組のカップルが 2N 列に並んだ座席に座り、お互いの手をつなぎたいと考えています。各カップルが並んで座れるように、座席交換の最小回数を計算します。一度に 2 人を選んで、立ち上がって席を交換してもらうことができます。人と座席は 0 から 2N-1 までの整数で表され、カップルには順番に番号が付けられ、最初のカップルは (0, 1)、2 番目のカップルは (2, 3)、最後のカップルは (2N-2, 2N-1) となります。

これらのカップルの最初の座席列[i]は、最初にi番目の座席に座る人によって決まります。

例1:

入力: row = [0, 2, 1, 3] 出力: 1 説明: row[1]とrow[2]の位置を交換するだけです。

例2:

入力: row = [3, 2, 0, 1] 出力: 0 説明: 席を交換する必要はなく、すべてのカップルが手をつなぐことができます。

 /**
 * @param {number[]} 行
 * @return {数値}
 */
 var minSwapsCouples =関数(行) {
    hashMap = {}; // {人: 場所}
 (i=0; i<row.length; i++)の場合{
      ハッシュマップ[行[i]] = i
    } 
 
    let ans = 0; // スワップ回数
 
 for (let i=0; i<row.length; i+=2){ // ペアで走査する
        let lover=row[i]^1; // row[i]の恋人
        if(hashMap[lover] !== i+1){ // 隣接していない場合は入れ替える
            答え++;
            hashMap[row[i+1]] = hashMap[lover]; // row[i+1]はloverの添え字を使用します
             // 位置を入れ替える
            [行[i+1], 行[ハッシュマップ[恋人]]] = [行[ハッシュマップ[恋人]], 行[i+1]]
            hashMap[lover]=i+1; // loverの添え字をi+1に変更して隣接させます
        }
    }
回答を返す;
 };