leetcode-javascript/leader_problems.js at codility_js · ruilinlin/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// dominator
function solution(A){
  // 找到候选者
  let stack = [];
  for(let i =  0; i < A.length; i++){
    if(stack.length === 0 || stack[stack.length -1] === A[i]){
      stack.push(A[i]);
    }else{
      stack.pop();
    }
  }
  // 没有候选者
  if(stack.length === 0)
    return -1;

  // 验证候选者
  const candidate = stack[0];
  let count = 0;
  for(let nums of A){
    if (nums === candidate)
      count++;
  }
  if(count > A.length / 2)
    return A.indexOf(candidate);
  return -1;

}

// equileader
function solution(A){
  let stack = [];
  // 找到候选者
  for(let i = 0; i < A.length; i++){
    if(stack.length === 0 || stack[stack.length -1] === A[i]){
      stack.push(A[i]);
    }else{
      stack.pop();
    }
  }
  if(stack.length === 0)
    return 0;
//  验证候选者
  const candidate = stack[0];
  let count = 0;
  for(let nums of A){
    if(nums === candidate)
      count++;
  }
  if(count <= A.length / 2)
    return 0;
// 计算等分点
  let equileader = 0;
  let leftLeader = 0;
  for(let i = 0; i < A.length; i++){
    if(A[i] === candidate)
      leftLeader++;
    if(leftLeader > (i + 1) / 2 && count - leftLeader > (A.length - i - 1) / 2)
      equileader++;
  }
  return equileader;
}