600-700
605. 种花问题
(https://leetcode-cn.com/problems/can-place-flowers/)
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int[] tmp = new int[flowerbed.length+2]; //扩展前后位
tmp[0] = 0;
for(int i= 0; i< flowerbed.length; i++){
tmp[i+1] = flowerbed[i];
}
tmp[flowerbed.length+1] = 0;
for (int i = 1; i < tmp.length-1; i++){ // 遍历访问是够连续三个位置都为0
if(tmp[i-1] == 0 && tmp[i]==0 && tmp[i+1] == 0){
tmp[i] = 1;
n--;
}
}
if(n <= 0) return true;
return false;
}
}
628. 三个数的最大乘积
(https://leetcode-cn.com/problems/maximum-product-of-three-numbers/)
class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int length = nums.length-1;
return Math.max(nums[0]*nums[1]*nums[length], nums[length-2]*nums[length-1]*nums[length]);
}
}
637. 二叉树的层平均值
(https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 二叉树的层序遍历
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();// 新建一个队列，进行层序遍历
queue.add(root);
while(queue.size()!= 0){ // 队列不空
int len = queue.size();
double sum = 0;
for(int i = 0; i < len; i++){
TreeNode node = queue.poll(); // 队首出队
sum += node.val; // 同一层的数字相加
if(node.left!= null) queue.add(node.left); // 左右子树进队
if(node.right!=null) queue.add(node.right);
}
res.add(sum/len);
}
return res;
}
}
617. 合并二叉树
(https://leetcode-cn.com/problems/merge-two-binary-trees/)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null) return root2;
if(root2== null) return root1;
root1.val += root2.val;// 对应位置元素相加
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}
643. 子数组最大平均数 I
(https://leetcode-cn.com/problems/maximum-average-subarray-i/)
class Solution {
public double findMaxAverage(int[] nums, int k) {
double sum = 0;
double max = 0;
// 动态规划
for(int i= 0; i < k; i++){ // 先计算前k个数的和
sum += nums[i];
}
max = sum; // 假设前k个数为目前的最大和
for(int i = k; i < nums.length; i++){
sum = sum-nums[i-k]+nums[i]; // 依次减去第一个数，加上新遍历的数
max = Math.max(max, sum); // 更新最大值
}
return (double)(max/k);
}
}
645. 错误的集合
(https://leetcode-cn.com/problems/set-mismatch/)
class Solution {
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
int[] temp = new int[nums.length+1]; // 存储标记数字
for(int i: nums){ // 以元素值作为下标标记
temp[i]++;
}
for(int i = 1 ; i< temp.length; i++){
if(temp[i] > 1){
res[0] = i;
}
if(temp[i] == 0){
res[1] = i;
}
}
return res;
}
}
653. 两数之和 IV - 输入 BST
(https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
if(root == null) return false;
List<Integer> list = new ArrayList<>();
inOrder(root, list); // 中序遍历得到递增数组
int left = 0;
int right = list.size()-1;
int sum = 0;
while(left < right){ // 利用递增数组的性质，进行左右遍历
sum = list.get(left) + list.get(right);
if(sum == k){
return true;
}
else if(sum > k){
right--;
}
else{
left++;
}
}
return false;
}
// 中序遍历得到递增数组
public void inOrder(TreeNode root, List<Integer> list){
if(root!= null){
inOrder(root.left, list);
list.add(root.val);
inOrder(root.right, list);
}
}
}
657. 机器人能否返回原点
(https://leetcode-cn.com/problems/robot-return-to-origin/)
class Solution {
public boolean judgeCircle(String moves) {
int x = 0;
int y = 0;
for (int i = 0; i < moves.length(); i++){
char c = moves.charAt(i);
if(c =='U') y++;
else if(c=='D') y--;
else if(c=='R') x++;
else if(c=='L') x--;
}
if(x == 0 && y == 0) return true;
return false;
}
}
671. 二叉树中第二小的节点
(https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int findSecondMinimumValue(TreeNode root) {
return traversal(root, root.val);
}
// 求左右子树的最小值
public int traversal(TreeNode root, int value){
if(root == null) return -1;
if(root.val > value){ // 如果根节点的值大于value直接返回
return root.val;
}
int l = traversal(root.left, value); // 求出左子树的最小值
int r = traversal(root.right,value); // 求出右子树的最小值
if(l >=0 && r >= 0){
return Math.min(l, r);
}
return Math.max(l, r);
}
// 寻找一颗树的最小值
public int findMin(TreeNode root){
if(root == null) return -1;
int min = root.val;
min = Math.min(root.val,min);
findMin(root.left);
findMin(root.right);
return min;
}
}
674. 最长连续递增序列
(https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/)
class Solution {
public int findLengthOfLCIS(int[] nums) {
int length = 1;
int max = 1;
if(nums.length == 1) return 1; // 数组长度为1，直接返回
for (int i = 1 ; i < nums.length; i++){
if(nums[i] > nums [i-1]){ // 如果是递增，则length加1
length++;
max = Math.max(length, max); // 更新最大长度的值
}else{
length = 1; // 如果不是递增，则重置length
}
}
return max;
}
}
682. 棒球比赛
(https://leetcode-cn.com/problems/baseball-game/)
class Solution {
public int calPoints(String[] ops) {
List<Integer> list = new ArrayList<>(); // 记录分数的数组
int cnt = 0;
for (int i =0; i < ops.length; i++){
int num = list.size()-1; // 记录当前结果数组的长度
if(ops[i].equals("C")){
list.remove(num);
}
else if(ops[i].equals("D")){
list.add(list.get(num)*2);
}
else if(ops[i].equals("+")){
list.add(list.get(num) + list.get(num-1));
}else {
list.add(Integer.parseInt(ops[i]));
}
}
for(int i : list){
cnt += i;
}
return cnt;
}
}
693. 交替位二进制数
(https://leetcode-cn.com/problems/binary-number-with-alternating-bits/)
class Solution {
public boolean hasAlternatingBits(int n) {
int flag = n % 2;
n /= 2;
while(n > 0){
if(n %2 == flag){
return false;
}
else {
flag = n % 2;
n /= 2;
}
}
return true;
}
// 方法二： 用异或
// int m = n ^(n>>1)
// return (m & (m+1)) == 0
}
696. 计数二进制子串
(https://leetcode-cn.com/problems/count-binary-substrings/)
697. 数组的度
(https://leetcode-cn.com/problems/degree-of-an-array/)
class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
// 用hash来存储元素及记录其出现的次数
for(int i = 0; i <nums.length; i++){
if(!map.containsKey(nums[i])){
map.put(nums[i], 1);
}
else{
int value = map.get(nums[i]);
map.put(nums[i], value+1);
}
}
int max = 0; // 求出众数
List<Integer> list = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
int value= map.get(nums[i]);
if(max < value ){ // 如果遇到新的众数， 更新list数组
list.clear();
max = value;
list.add(nums[i]);
}else if(max == value){ // 如果两个数个数相同，则加入list
list.add(nums[i]);
}
}
int minLength = nums.length; // 让最短数组的为原数组场
int temp = 0;
for(int i = 0; i < list.size(); i++){
int n = list.get(i);
int left = 0;
int right = nums.length-1;
while(left <= right){ // 找出左右第一个元素位置
if(nums[left] == n){
break;
}else{
left++;
}
}
while(right >= 0){
if(nums[right] == n){
break;
}else{
right--;
}
}
temp = right - left; // 两个元素位置的距离
minLength = Math.min(minLength, temp); // 更新最小距离
}
return minLength+1;
}
}
700-800
704. 二分查找
(https://leetcode-cn.com/problems/binary-search/)
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
int mid = 0;
while(left <= right){
mid = left + (right - left)/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid -1;
}else {
left = mid + 1;
}
}
return -1;
}
}
709. 转换成小写字母
(https://leetcode-cn.com/problems/to-lower-case/)
class Solution {
public String toLowerCase(String s) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'){
sb.append((char)(s.charAt(i)+32));
}
else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
717. 1比特与2比特字符
(https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/)
class Solution {
public boolean isOneBitCharacter(int[] bits) {
int i = 0;
while(i < bits.length){
if(bits[i] == 1){ // 1后面是0或1无所谓只需要看最后一个数
// 只要遇到1，就跳过下一个数
i = i + 2;
}
else{ // 如果遍历到最后一位，为0且只有一位，则返回true
if(i == bits.length-1 && bits[i] == 0){
return true;
}
// 遇到0 ，则移动一位下标
i++;
}
}
return false;
}
}
744. 寻找比目标字母大的最小字母
(https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/)
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
if(target == 'z'){ // 因为数组有序，所以如果为z，则可以直接返回第一个元素
return letters[0];
}
for(int i = 1; i <letters.length; i++){ // 依次遍历大于target的最小字母
if(letters[i] > target && letters[i-1] <= target){
return letters[i];
}
}
return letters[0];
}
}
746. 使用最小花费爬楼梯
(https://leetcode-cn.com/problems/min-cost-climbing-stairs/)
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length +1];
dp[1] = cost[0]; // 从第0个台阶开始
dp[2] = cost[1]; // 第1个台阶
for(int i = 3; i < dp.length; i++){
// 决定是迈一个台阶还是迈两个台阶
dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-1]);
}
return Math.min(dp[cost.length], dp[cost.length-1]);
}
}
747. 至少是其他数字两倍的最大数
(https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others/)
class Solution {
public int dominantIndex(int[] nums) {
int index = 0; // 标记最大数的下标
if(nums.length <= 1) return index;
for(int i = 0; i <nums.length; i++){ // 求出最大数
if(nums[index] < nums[i]){
index = i;
}
}
for(int i = 0; i < nums.length; i++){ // 比较最大数是否大于其中每个数的两倍
if(i != index && nums[index] < nums[i]*2){
return -1;
}
}
return index;
}
}
748. 最短补全词
(https://leetcode-cn.com/problems/shortest-completing-word/)
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
// Arrays.sort(words); // 单词进行排序
licensePlate = licensePlate.toLowerCase();
Map<Character, Integer> map = new HashMap<>(); // map来存储字符以及出现的次数
for(int i = 0; i < licensePlate.length(); i++){
char c = licensePlate.charAt(i);
if(c >= 'A' && c <= 'z'){
if(!map.containsKey(c) ){
map.put(c,1);
}else{
map.replace(c,map.get(c)+1);
}
}
}
int index = 0;
int min = Integer.MAX_VALUE; // 最短字符串长度标记
for(int i= 0; i < words.length; i++){
int temp = search(words[i], map); // 求出最短字符串
if( temp != -1 && temp < min ){
min = temp;
index = i;
}
}
return words[index]; // 返回最短字符串
}
// 查找该字符串是否包含所有的字符，并返回字符串的长度
public int search(String str, Map<Character, Integer> map1){
Map<Character, Integer> map = new HashMap<>(map1); // 必须新建一个map,不然会改变原来map的值
for(int i = 0; i < str.length(); i++){
if(map.containsKey(str.charAt(i))){
int value = map.get(str.charAt(i));
map.put(str.charAt(i), value-1);
}
}
for (Integer val : map.values()) { // 如果有值大于1，表示该字符串不能完全表示
if(val > 0) return -1;
}
return str.length();
}
}
762. 二进制表示中质数个计算置位
(https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/)
class Solution {
public int countPrimeSetBits(int left, int right) {
int cnt = 0;
int index = 0;
for(int i = left; i <= right; i++){
index = countOneBits(i);
if(isPrime(index)){
cnt++;
}
}
return cnt;
}
// 求出该数的二进制数有多少个1
public int countOneBits(int num){
int cnt = 0;
while(num > 0){
if(num % 2 == 1){
cnt++;
}
num /= 2;
}
return cnt;
}
// 求该数是否是质数
public boolean isPrime(int num){
if(num == 1) return false;
if (num == 2 || num == 3) return true;
for(int i =2; i <= Math.sqrt(num); i++){
if(num % i == 0){
return false;
}
}
return true;
}
}
766. 托普利茨矩阵
(https://leetcode-cn.com/problems/toeplitz-matrix/)
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
int row = matrix.length; // 矩阵的行
int col = matrix[0].length; // 矩阵的列
if(row == 1 || col == 1) return true; // 如果只有一行或者一列，则直接返回true
for(int i = 1; i < row; i++){
for(int j = 1; j < col; j++){ // 从(m-1)(n-1)开始计算
if(matrix[i][j] != matrix[i-1][j-1]){
return false;
}
}
}
return true;
}
}
771. 宝石与石头
(https://leetcode-cn.com/problems/jewels-and-stones/)
class Solution {
public int numJewelsInStones(String jewels, String stones) {
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < jewels.length(); i++){
if(!map.containsKey(jewels.charAt(i))){
map.put(jewels.charAt(i), i);
}
}
int res = 0;
// 如果是jewels中的字符，则视为宝石
for(int i= 0; i < stones.length(); i++){
if(map.containsKey(stones.charAt(i))){
res++;
}
}
return res;
}
}
783. 二叉搜索树节点最小距离
(https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 二叉搜索树，中序遍历是一个递增序列
public int minDiffInBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root != null){
inorder(root, list);
}
int min = list.get(1)-list.get(0);
// 遍历查找最数组差值最小的两个数的差
for(int i = 1; i < list.size(); i++){
if(min > (list.get(i) - list.get(i-1))){
min = list.get(i) - list.get(i-1);
}
}
return min;
}
// 中序遍历得到递增数组
public void inorder(TreeNode root, List<Integer> list){
if(root!= null){
inorder(root.left, list);
list.add(root.val);
inorder(root.right,list);
}
}
}
796. 旋转字符串
(https://leetcode-cn.com/problems/rotate-string/)
class Solution {
public boolean rotateString(String s, String goal) {
StringBuilder sb = new StringBuilder();
sb.append(s+s); // 两倍s的字符串，其包含其循环的所有可能
// 如果两个字符串长度相等，且sb包含其goal的字符串，则返回true
if(s.length() == goal.length() && sb.indexOf(goal) >= 0){
return true;
}
return false;
}
}