2019-05-29

有効な括弧の最大長さ Longest valid Parentheses

Quiz

https://practice.geeksforgeeks.org/problems/longest-valid-parentheses/0

Submission

https://practice.geeksforgeeks.org/viewSol.php?subId=14381873&pid=1247&user=peroon

例

4
(()(
()()((
((()()())))
()(())(

Code

ll maxLen(string s){
  ll L = s.size();
  stack<ll> st;
  st.push(-1);

  ll len = 0;

  FOR(i, 0, L){
    if(s[i]=='('){
      st.push(i);
    }
    else{
      st.pop();

      if(!st.empty()){
        len = max(len, i - st.top());
      }
      else{
        st.push(i);
      }
    }
  }
  return len;
}

感想

DP使いそう、と思わせてスタックでした
解けなかったので解法を見た。スタックの使い方が天才的・・・

2019-05-29

配列からペアでない2つの数字を見つける。XOR

ペアでない数字は2つ(x, y)あるという設定
例

Input: {12, 23, 34, 12, 12, 23, 12, 45}
Output: 34 and 45

ソートすれば O(n log n)
しかしO(n)の解法がある
https://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/

解法

全てのXORを求める。x xor yだけ残る
a = x ^ y とする
LSB (Least Significant Bit) a & -a を求める

a = 01010
-aは反転して1を足したものなので、-a = 10110
LSB = 00010

x = 0
y = 0
の単位元から始めて、LSB & A[i]なものをxにXOR, その他をyにXORする
x, y以外はペアなので打ち消され、x, yそのものだけが残る

x = 0;
y = 0;
for(i = 0; i < size; i++)  
{  
    if(A[i] & LSB){
        x = x ^ A[i];  
    }
    else{
        y = y ^ A[i];  
    }
}

2019-05-28

木で値を探しながら経路(path)も保存するbfs

例

https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

内容

bfsの引数に vector &path も渡して入れていく
奥まで見に行って見つからなかったら path.pop_back() して詰めたものをキャンセルする

2019-05-28

kadane's algorithm ～最大部分和をO(N)～

ライブラリ

用途

負の値も含みうる数値配列にて、隣接した部分和の最大値をO(N)で求める
読み方はカダネではなく、ケイデインズ
最大部分列和(maximum segment sum)と言われる

最大部分和問題

Maximum subarray problem
https://en.wikipedia.org/wiki/Maximum_subarray_problem

例1

1 2 3 -2 5の場合
answer : 9

例2

-2 1 -3 4 -1 2 1 -5 4
answer : 6

例3

-1 -2 -3
answer : -1

参考

https://ark4rk.hatenablog.com/entry/2018/01/08/002508

Quiz

https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0/?ref=self

Submission

https://practice.geeksforgeeks.org/viewSol.php?subId=14333102&pid=106&user=peroon

Code

ll kadanes_algorithm(vector<ll> &A){
    ll ans = A[0];
    ll s = A[0];
    FOR(i, 1, A.size()){
        s = max(s + A[i], A[i]);
        chmax(ans, s);
    }
    return ans;
}