java常见算法

欢迎各位关注我的公众号，会继续更新算法知识与前后端知识

1.题目:

给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

数字排序后进行匹配，不需要对n里的数字进行不断排序，可以判断n与2次方的数（同样长度）进行sort排序后n是否包含在这些被排序后的2次方的数里面

class Solution {    public boolean reorderedPowerOf2(int n) { Set set = new HashSet(); for(int i = 1;i > 0;i <<= 1) {     set.add(isS(i)); } return set.contains(isS(n));    }    public String isS(int x) { char[] arr = String.valueOf(x).toCharArray(); Arrays.sort(arr); return new String(arr);    }}

2.题目：

我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。

请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。

示例：输出：low = 100, high = 300

输出：[123,234]

暴力枚举超时

dfs：

class Solution {    public List sequentialDigits(int low, int high) { List list = new ArrayList(); for(int i = 1;i  high)  return; //往集合里面添加符合条件的数字 if(a >= low) list.add(a); //在符合条件的数字中，9是数字最后一位的最大值 if(c == 9) return; dfs(list,a * 10 + c + 1,c+1,low,high);    }}

3.题目

把符合下列属性的数组 arr 称为 山脉数组 ：arr.length >= 3

存在下标 i（0 < i < arr.length - 1），满足

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

示例 ：

输入：arr = [2,1,4,7,3,2,5]

输出：5

解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。

pass：一开始的思路是定义2个常量为0，因为只能一次升一次降，而且必须先升才能降，所以必须升的那个常量++才能降，但不实在

class Solution {    public int longestMountain(int[] arr) { int len = arr.length; int count = 0; for(int i = 1;i  arr[i-1] && arr[i] > arr[i+1]) {  int j = i - 1;  int x = i + 1;  while(j > 0) {      if(arr[j] > arr[j-1]) {   j--;      }else {    break;      }  }while(x  arr[x+1]) { x++;      }else {   break;      }  }  count = Math.max(count,x-j+1);     } }return count;    }}

4.题目：跳跃游戏1

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：可以不断更新能达到的最远距离，用一个for循环从第一个元素开始便利，前提是能走到。

示例 1：

输入：nums = [2,3,1,1,4]

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

class Solution {    public boolean canJump(int[] nums) { int len = nums.length; //记录能到达的最远的地方 int max = 0; //i记录的是目前在第几个元素 for(int i = 0;i < len;i++) {     //只有满足i<=max才合理     //已知目前能去到的最远地方为max，则max之前的地方都能达到     if(i = len - 1)  return true;     } } return false;    }}

5.题目：跳跃游戏2

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

思路：我们可以从反方向开始，判断当前位置能否到达终点（从第一个开始遍历，这样能、用最少的步数走最大的距离）。

示例 1:

输入: nums = [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

class Solution {    public int jump(int[] nums) { int len = nums.length; int posi = len - 1; int step = 0; while(posi > 0) {     for(int i = 0;i = posi) {      step++;      //已经能去到终点了，现在只需要去到当前i位置      posi = i;      break;  }     } } return step;    }}

6.题目：

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

递归

class Solution {    public boolean PredictTheWinner(int[] nums) { int len = nums.length; return getBoo(nums,0,len-1,1) >= 0;    }    public int getBoo(int[] nums,int left,int right,int player) { //递归出口 if(left == right) return player * nums[left]; //先选左边的情况 int startLeft = nums[left] * player + getBoo(nums,left + 1,right,-player); //先选右边的情况 int startRight = nums[right] * player + getBoo(nums,left,right - 1,-player); if(player == 1){     //玩家一要最大的     return Math.max(scoreStart ,scoreEnd ); }else{     //玩家二要最小的     return Math.min(scoreStart ,scoreEnd ); }    }}