455、分發餅干
class Solution {
public int count;
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
count = 0;
int indexS = 0;
int indexG = 0;
while(indexS < s.length && indexG < g.length){
if(s[indexS] >= g[indexG]){
count++;
indexG++;
indexS++;
}else{
indexS++;
}
}
return count;
}
}
376、擺動序列
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length <= 1){
return nums.length;
}
int pre = 0;
int cur = 0;
int count = 1;
for(int i = 1; i < nums.length; i++){
cur = nums[i] - nums[i - 1];
if((cur > 0 && pre <= 0) || (cur < 0 && pre >= 0)){
count++;
pre = cur;
}
}
return count;
}
}
53、最大子陣列和
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 1){
return nums[0];
}
int count = 0;
int sum = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; i++){
count += nums[i];
sum = Math.max(sum, count);
if(count <= 0){
count = 0;
}
}
return sum;
}
}
122、買賣股票的最佳時機 II
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
for(int i = 1; i < prices.length; i++){
if(prices[i] > prices[i - 1]){
max += prices[i] - prices[i - 1];
}
}
return max;
}
}
55、跳躍游戲
class Solution {
public boolean canJump(int[] nums) {
if(nums.length == 1){
return true;
}
int coverMax = 0;
for(int i = 0; i <= coverMax; i++){//防止中途就出現覆寫范圍中斷
coverMax = Math.max(coverMax, i + nums[i]);
if(coverMax >= nums.length - 1){
return true;
}
}
return false;
}
}
45、跳躍游戲 II
class Solution {
public int jump(int[] nums) {
int count = 0;
if(nums.length == 1){
return count;
}
// 當前覆寫范圍
int coverMax = 0;
// 最大覆寫范圍
int maxCover = 0;
for(int i = 0; i < nums.length; i++){
// 更新在當前覆寫范圍內的最大覆寫范圍（下一步可以跳到的最大范圍）
maxCover = Math.max(nums[i] + i, maxCover);
// 再跳一步就可以到達
if(maxCover >= nums.length - 1){
count++;
break;
}
// 到達當前覆寫范圍最大值，需要下一跳
if(i == coverMax){
count++;
coverMax = maxCover;
}
}
return count;
}
}
1005、K 次取反后最大化的陣列和
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
int index = 0;
for(int i = 0; i < k; i++){
if(i < nums.length - 1 && nums[index] < 0){
nums[index] = -nums[index];
if(nums[index] >= Math.abs(nums[index + 1])){
index++;
}
continue;
}
nums[index] = -nums[index];
}
int sum = 0;
for(int j = 0; j < nums.length; j++){
sum += nums[j];
}
return sum;
}
}
134、加油站
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int[] arr = new int[gas.length];
int sum = 0;
int curSum = 0;
int index = 0;
for(int i = 0; i < arr.length; i++){
arr[i] = gas[i] - cost[i];
sum += arr[i];
curSum += arr[i];
if(curSum < 0){
index = (i + 1)%arr.length;
curSum = 0;
}
}
if(sum >= 0){
return index;
}else{
return -1;
}
}
}
135、分發糖果
class Solution {
public int candy(int[] ratings) {
// 最少糖果數目
int[] arrResult = new int[ratings.length];
arrResult[0] = 1;
for(int i = 1; i < ratings.length; i++){
arrResult[i] = ratings[i] > ratings[i - 1] ? arrResult[i - 1] + 1 : 1;
}
for(int i = ratings.length - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1]){
arrResult[i] = Math.max(arrResult[i],arrResult[i + 1] + 1);
}
}
int sum = 0;
for(int j = 0; j < arrResult.length; j++){
sum += arrResult[j];
}
return sum;
}
}
860、檸檬水找零
class Solution {
public boolean lemonadeChange(int[] bills) {
if(bills[0] != 5){
return false;
}
if(bills.length == 1){
return true;
}
List<Integer> money = new LinkedList<>();
money.add(5);
for(int i = 1; i < bills.length; i++){
if(bills[i] == 5){
money.add(5);
}else if(bills[i] == 10){
if(!money.contains(5)){
return false;
}
money.add(10);
money.remove(new Integer(5));
}else if(bills[i] == 20){
if(money.contains(5) && money.contains(10)){
money.add(20);
money.remove(new Integer(5));
money.remove(new Integer(10));
}else if(money.contains(5)){
for(int j = 0; j < 3; j++){
if(!money.contains(5)){
return false;
}
money.remove(new Integer(5));
}
money.add(20);
}else{
return false;
}
}
}
return true;
}
}
406、根據身高重建佇列
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(a,b)->{
if(a[0]==b[0]) return a[1] - b[1];
return b[0] - a[0];
});
List<int[]> queue = new LinkedList<>();
for(int[] p: people){
queue.add(p[1],p);
}
return queue.toArray(new int[people.length][]);
}
}
452、用最少數量的箭引爆氣球
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int count = 1;
for(int i = 1; i < points.length; i++){
if(points[i][0] > points[i-1][1]){
count++;
}else{
points[i][1] = Math.min(points[i-1][1],points[i][1]);
}
}
return count;
}
}
435、 無重疊區間
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a,b)->{
if(a[0]==b[0])return a[1]-b[1];
return a[0]-b[0];
});
int resultCount = 0;
int right = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] < right){
resultCount++;
if(intervals[i][1] < right){
right = intervals[i][1];
}
}else{
right = intervals[i][1];
}
}
return resultCount;
}
}
763、劃分字母區間
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> result = new ArrayList<>();
char temp;
int right = 0;
int left = 0;
for(int j = 0; j < s.length(); j++){
temp = s.charAt(j);
for(int i = s.length() - 1; i >= 0; i--){
if(temp == s.charAt(i)){
right = Math.max(right,i);
break;
}
}
if(j==right){
result.add(right-left+1);
left = right+1;
}
}
return result;
}
}
56、合并區間
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals,(a,b)->{
if(a[0]==b[0])return a[1]-b[1];
return a[0]-b[0];
});
List<int[]> result = new LinkedList<>();
int right = intervals[0][1];
int left = intervals[0][0];
int count = 1;
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0]<=right){
right = Math.max(right,intervals[i][1]);
}else{
result.add(new int[]{left,right});
left=intervals[i][0];
right=intervals[i][1];
count++;
}
}
result.add(new int[]{left,right});
return result.toArray(new int[count][]);
}
}
738、單調遞增的數字
class Solution {
public int monotoneIncreasingDigits(int n) {
String str = String.valueOf(n);
char[] arr = str.toCharArray();
int start = arr.length;
for(int i = arr.length - 2; i >= 0; i--){
if(arr[i] > arr[i+1]){
arr[i]--;
start = i+1;
}
}
for(int j = start; j<arr.length; j++){
arr[j]='9';
}
return Integer.parseInt(String.valueOf(arr));
}
}
714、買賣股票的最佳時機含手續費
class Solution {
public int maxProfit(int[] prices, int fee) {
if(prices.length==1){
return 0;
}
int index = prices[0]+fee;
int sum=0;
for(int i = 1; i < prices.length; i++){
if(prices[i]>index){
sum+=prices[i]-index;
index=prices[i];
}else if(prices[i]+fee<index){
index=prices[i]+fee;
}
}
return sum;
}
}
968、監控二叉樹
/**
* 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 {
int res=0;
public int minCameraCover(TreeNode root) {
// 對根節點的狀態做檢驗,防止根節點是無覆寫狀態 .
if(minCame(root)==0){
res++;
}
return res;
}
/**
節點的狀態值：
0 表示無覆寫
1 表示 有攝像頭
2 表示有覆寫
后序遍歷，根據左右節點的情況,來判讀 自己的狀態
*/
public int minCame(TreeNode root){
if(root==null){
// 空節點默認為 有覆寫狀態，避免在葉子節點上放攝像頭
return 2;
}
int left=minCame(root.left);
int right=minCame(root.right);
// 如果左右節點都覆寫了的話, 那么本節點的狀態就應該是無覆寫,沒有攝像頭
if(left==2&&right==2){
//(2,2)
return 0;
}else if(left==0||right==0){
// 左右節點都是無覆寫狀態,那 根節點此時應該放一個攝像頭
// (0,0) (0,1) (0,2) (1,0) (2,0)
// 狀態值為 1 攝像頭數 ++;
res++;
return 1;
}else{
// 左右節點的 狀態為 (1,1) (1,2) (2,1) 也就是左右節點至少存在 1個攝像頭，
// 那么本節點就是處于被覆寫狀態
return 2;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540578.html
標籤：Java
上一篇：解讀JVM級別本地快取Caffeine青出于藍的要訣3 —— 講透Caffeine的資料驅逐淘汰機制與用法
下一篇：SpringMVC學習筆記