class Solution {
public int balancedStringSplit(String s) {
int count = 0;
int num = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == 'L'){
num++;
}else{
num--;
}
if (num == 0){
count++;
}
}
return count;
}
}
class Solution extends SolBase {
public int rand10() {
int num = rand7();
while (true) {
num = (num-1) * 7 + rand7();
if(num <= 40){
return num % 10 +1;
}
return rand10();
}
}
}
class Solution {
public int fib(int n) {
if (n==0){
return 0;
}
if (n==1){
return 1;
}
int[] res = new int[n+1];
res[0] = 0;
res[1] = 1;
int i = 2;
while ( i <= n ){
res[i] = (res[i-1] + res[i-2]) % 1000000007;
i++;
}
return res[n];
}
}
class Solution {
public int fib(int n) {
if (n==0){
return 0;
}
if (n==1){
return 1;
}
int a = 0;
int b = 1;
int i = 2;
while ( i <= n ){
if (i%2==0){
a = (a+b) % 1000000007;
}else{
b = (a+b) % 1000000007;
}
i++;
}
return n%2==0?a:b;
}
}
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while (left <= right){
int mid = left + ((right-left) >> 1);
if (nums[mid] == target){
return mid;
}
if (nums[mid] < target){
left = mid+1;
}else{
right = mid-1;
}
}
return -1;
}
}
class Solution {
public int countPrimes(int n) {
if (n<2){
return 0;
}
if (n==2){
return 0;
}
List<Integer> list = new ArrayList<>();
list.add(2);
boolean isPrimes = true;
for (int i = 3; i < n ; i++) {
isPrimes = true;
for(int num : list){
if (i % num == 0){
isPrimes = false;
break;
}
}
if (isPrimes){
list.add(i);
}
}
return list.size();
}
}
class Solution {
int[] list;
int listCount = 0;
public int[] smallestK(int[] arr, int k) {
if (k == 0){
return new int[0];
}
list = new int[k];
Arrays.fill(list,Integer.MIN_VALUE);
for (int i = 0; i < arr.length; i++) {
if (listCount < list.length){
//此时list还没满
listAdd(arr[i]);
}else{
listInsert(arr[i]);
}
}
return list;
}
public void listAdd( int num ){
if (listCount == 0){
list[0] = num;
listCount++;
return;
}
//比如
//[1,2,4,5,6]找到4比3大
//[1,2,3,4,5,6]把4、5、6往后挪移一位在4的位置插入
for (int i = 0; i < list.length; i++) {
if (list[i] > num){
System.arraycopy(list,i,list,i+1,listCount-i);
list[i] = num;
listCount++;
return;
}
}
list[listCount] = num;
listCount++;
}
public void listInsert( int num ){
for (int i = 0; i < list.length; i++) {
if (list[i] > num){
System.arraycopy(list,i,list,i+1,list.length-i-1);
list[i] = num;
break;
}
}
}
}
class Solution2 {
public int[] smallestK(int[] arr, int k) {
if (k == 0){
return new int[0];
}
int[] list = new int[k];
Arrays.sort(arr);
System.arraycopy(arr,0,list,0,k);
return list;
}
}
class Solution { HashSet<Integer> hashSet = new HashSet<>(); boolean result = false; public boolean findTarget(TreeNode root, int k) { dfs(root,k); return result; }
private void dfs(TreeNode node, int k){ if (null==node || result)return; dfs(node.left,k); if (!result){ if (hashSet.contains(k-node.val)){ result = true; } } hashSet.add(node.val); dfs(node.right,k); }
