package com.myapp.jetpackapplication;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
// Scanner scanner = new Scanner(System.in);
// while (scanner.hasNext()) {
// int num = scanner.nextInt();
// int[] array = new int[num];
// for (int i = 0; i < num; i++) {
// array[i] = scanner.nextInt();
// }
// System.out.println(climbStairs(array));
// }
int[] array = {55, 89, 84, 47, 76, 71, 75, 63, 18, 9};
System.out.println(climbStairs(array));
}
private static int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
for (int i = 2; i <= cost.length; i++) {
dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
}
return dp[cost.length];
}
/***
* 给定一个整数数组 cost \cost ，其中 cost[i]\cost[i] 是从楼梯第i \i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
* */
public static int climbStairs(int[] array) {
int cost = 0;
if (array.length == 1) {
return 0;
}
if (array.length == 2) {
return Math.min(array[0], array[1]);
}
int step = array.length - 1;
while (step > 2) {
int c1 = array[step - 2] + array[step];
int c2 = array[step - 2] + array[step - 1];
if (c1 < c2) {
cost += array[step];
step -= 2;
} else {
cost += array[step - 1];
step -= 1;
}
}
return cost;
}
/**
* 猴子爬山进阶版 1 2 3 .。。。number步跳 想跳几步跳几步
**/
public static int jumpFloorII(int number) {
int sum = 0;
if (number == 0) {
return 0;
}
if (number == 1) {
return 1;
}
if (number == 2) {
return 2;
}
sum = sum + 2 * jumpFloorII(number - 1);
return sum;
}
/**
* 给定一个非负整数 num ，生成杨辉三角的前 num 行。
* 杨辉三角中，每个数是左上方和右上方的数之和。
*/
public static int[] getRow(int num) {
// write code here
if (num == 0) {
return new int[]{1};
}
if (num == 1) {
return new int[]{1, 1};
}
int[] array = new int[3];
array[0] = 1;
array[1] = 2;
array[2] = 1;
if (num == 2) {
return array;
}
for (int i = 3; i < num + 1; i++) {
int[] cur = new int[i + 1];
int len = i / 2 + 1;
for (int k = 0; k < len; k++) {
if (k == 0) {
cur[k] = cur[i - k] = 1;
} else {
cur[k] = cur[i - k] = array[k - 1] + array[k];
}
}
array = cur;
}
return array;
}
/**
* 给定一个非负整数 num ，生成杨辉三角的前 num 行。
* 杨辉三角中，每个数是左上方和右上方的数之和。
*/
public static int[][] generate(int num) {
// write code here
int[][] ints = new int[num][];
for (int i = 0; i < num; i++) {
int[] array = new int[i + 1];
if (i == 0) {
array[i] = 1;
} else if (i == 1) {
array[0] = 1;
array[1] = 1;
} else {
int len = i / 2 + 1;
for (int k = 0; k < len; k++) {
if (k == 0) {
array[k] = array[i - k] = 1;
} else {
array[k] = array[i - k] = ints[i - 1][k - 1] + ints[i - 1][k];
}
}
}
ints[i] = array;
}
return ints;
}
/**
* 给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
* 上中位数：假设递增序列长度为n，为第n/2个数
*/
public static int findMedianinTwoSortedAray(int[] arr1, int[] arr2) {
if (arr1.length == 1) {
return Math.min(arr1[0], arr2[0]);
}
int left1 = 0;
int right1 = arr1.length - 1;
int left2 = 0;
int right2 = arr2.length - 1;
while (left1 < right1) {
//1 先找出两个数组的中间索引位置
int middle1 = left1 + (right1 - left1) / 2;
int middle2 = left2 + (right2 - left2) / 2;
// 当前剩余数组总个数为偶数 索引需要向后动一位 保证两个数组剩余个数相同
int fillIn = ((right1 - left1) + 1) % 2 == 0 ? 1 : 0;
if (arr1[middle1] == arr2[middle2]) {
return arr1[middle1];
} else if (arr1[middle1] > arr2[middle2]) {
// arr1剩余的中间位大于array2的剩余中间位 那么中位数只能在 lef1--middle1 middle2 -- right2
right1 = middle1;
left2 = middle2 + fillIn;
} else {
// arr1剩余的中间位小于array2的剩余中间位 那么中位数只能在 middle1--right1 left2 -- middle2
left1 = middle1 + fillIn;
right2 = middle2;
}
}
//最后返回最小的为上中位数
return Math.min(arr1[left1], arr2[left2]);
}
public static int waysToChange(int n) {
int[] coins = {5, 4, 3, 2, 1};
int[] res = new int[n + 1];
res[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= n; i++) {
res[i] = res[i] + res[i - coin];
}
}
return res[n];
}
/**
* 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
*/
public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int l = 1;
int r = 2;
int result = 3;
// sum=9 [2,3,4],[4,5]
while (l < r) {
if (result < sum) {
r++;
result += r;
} else if (result > sum) {
result -= l;
l++;
} else {
ArrayList<Integer> integers = new ArrayList<>();
for (int i = l; i <= r; i++) {
integers.add(i);
}
list.add(integers);
result -= l;
l++;
}
}
return list;
}
/**
* 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度
*/
public static int lengthOfLongestSubstring(String s) {
int l = 0;
int r = 0;
int max = 0;
Set<Character> set = new HashSet<>();
while (r < s.length()) {
if (set.contains(s.charAt(r))) {
set.remove(s.charAt(l));
l++;
} else {
set.add(s.charAt(r));
r++;
}
max = Math.max(max, set.size());
}
return max;
}
/**
* 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
* 注意：
* 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
* 如果 s 中存在这样的子串，我们保证它是唯一的答案。
*/
public static String minWindow(String s, String t) {
int l = 0;
int r = 0;
int min = Integer.MAX_VALUE;
String res = "";
HashMap<Character, Integer> cur = new HashMap<>();
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char a = t.charAt(i);
if (map.containsKey(a)) {
map.put(a, map.get(a) + 1);
} else {
map.put(a, 1);
}
}
while (r < s.length()) {
char c = s.charAt(r);
if (cur.containsKey(c)) {
cur.put(c, cur.get(c) + 1);
} else {
cur.put(c, 1);
}
while (check(cur, map)) {
if (r - l < min) {
min = r - l + 1;
res = s.substring(l, r + 1);
}
char ch = s.charAt(l);
cur.put(ch, cur.get(ch) - 1);
if (cur.get(ch) == 0) {
cur.remove(ch);
}
l++;
}
r++;
}
return res;
}
public static boolean check(HashMap<Character, Integer> cur, HashMap<Character, Integer> map) {
for (char c : map.keySet()) {
if (!cur.containsKey(c) || cur.get(c) < map.get(c)) {
return false;
}
}
return true;
}
/**
* 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
* （注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
*/
public static int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
if (hashMap.containsKey(target - numbers[i])) {
return new int[]{hashMap.get(target - numbers[i]) + 1, i + 1};
} else {
hashMap.put(numbers[i], i);
}
}
return null;
}
/**
* 数组3个数的最大乘积 最大乘积
* 数据范围：
* 10^-4 ≤A[i]≤10^4
* A 10^4>长度>=3
*
* @param A int整型一维数组
* @return long长整型
*/
public static long solve(int[] A) {
// 先排序
Arrays.sort(A);
// 3 个数相乘 结果：
// 1、3个正数 或3个负数 最大的三个数相乘 得到最大积
// 2、2个正数1个负数 说明数组中只有3个元素 再多一个负数 负负得正 其结果为正数
// 3、1个正数和2个负数 负负得正 最小的两个负数相乘得到最大积 或者 最大的三个正数相乘得到的积
int len = A.length;
long a = A[len - 1];
long b = A[len - 2];
long c = A[len - 3];
long m = A[1];
long n = A[0];
return Math.max(a * b * c, a * m * n);
}
/**
* 遍历链表
*/
public static void traverseLinkedList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode cur = head;
while (cur != null) {
if (cur != null)
System.out.println(cur.val);
cur = cur.next;
}
}
/**
* 反转链表重复
*/
public static ListNode ReverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode reHead = null;
ListNode cur = head;
while (cur != null) {
// 1 先保存当前节点 下一节点
ListNode next = cur.next;
// 2 当前节点的 下一个节点指向上一个节点
cur.next = reHead;
// 更新反转节点指针 指向当前节点
reHead = cur;
// 更新当前节点指针
cur = next;
}
return reHead;
}
/**
* 去除链表重复
*/
public static ListNode deleteDuplicates(ListNode head) {
// write code here
if (head == null) {
return null;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
static class ListNode {
public ListNode(int v) {
val = v;
}
int val;
ListNode next = null;
}
/***
* 给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组
*
* 数据范围： 0 \le n,m \le 1000≤n,m≤100，|A_i| <=100∣A
* i
*
* ∣<=100， |B_i| <= 100∣B
* i
*
* ∣<=100
*
* 注意：
* 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
* 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印
* 3. A 数组在[0,m-1]的范围也是有序的
* */
public static void merge(int A[], int m, int B[], int n) {
int a = m - 1;
int b = n - 1;
int c = m + n - 1;
while (c >= 0) {
if (a == -1) {
A[c] = B[b];
b--;
} else if (b == -1) {
break;
} else if (A[a] > B[b]) {
A[c] = A[a];
a--;
} else {
A[c] = B[b];
b--;
}
c--;
}
}
/**
* 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
*/
public static int findGreatestSumOfSubArray(int[] array) {
// 得到当前数组相加结果
int sum = 0;
// 子数组的和的最大值
int max = array[0];
// sIndex 子数组起始位置 初始值0
// eIndex 子数组结束位置 初始值0
for (int i = 0; i < array.length; i++) {
// 若sum+array[i]> array[i]; 则 sum 的值为数组连续相加结果
// 若sum+array[i]<array[i] 大 则sum 的值当前array[i]的值 sIndex 位置指向i
sum = Math.max(sum + array[i], array[i]);
// max>sum 上一次子数组相加结果+array[i] 比最大值自小 eIndex 位置不变
// max<sum 上一次子数组相加结果+array[i] 比最大自值大 eIndex 位置指向i
max = Math.max(sum, max);
}
return max;
}
/**
* 给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
**/
public static ArrayList<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> res = new ArrayList<>();
//先排除特殊情况
if (matrix.length == 0) {
return res;
}
//左边界
int left = 0;
//右边界
int right = matrix[0].length - 1;
//上边界
int up = 0;
//下边界
int down = matrix.length - 1;
//直到边界重合
while (left <= right && up <= down) {
//上边界的从左到右
for (int i = left; i <= right; i++)
res.add(matrix[up][i]);
//上边界向下
up++;
if (up > down)
break;
//右边界的从上到下
for (int i = up; i <= down; i++)
res.add(matrix[i][right]);
//右边界向左
right--;
if (left > right)
break;
//下边界的从右到左
for (int i = right; i >= left; i--)
res.add(matrix[down][i]);
//下边界向上
down--;
if (up > down)
break;
//左边界的从下到上
for (int i = down; i >= up; i--)
res.add(matrix[i][left]);
//左边界向右
left++;
if (left > right)
break;
}
return res;
}
/**
* 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
* 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
* 2.如果不能获取到任何利润，请返回0
* 3.假设买入卖出均无手续费
*/
public int maxProfit(int[] prices) {
// write code here
int len = prices.length;
int minPrices = Integer.MAX_VALUE;
int ans = 0;
for (int i = 0; i < len; i++) {
//寻找最低点
if (prices[i] < minPrices) {
minPrices = prices[i];
} else if (prices[i] - minPrices > ans) {
//更新答案（最大利润）
ans = prices[i] - minPrices;
}
}
return ans;
}
/**
* 某商店规定：三个空汽水瓶可以换一瓶汽水，允许向老板借空汽水瓶（但是必须要归还）。
* 小张手上有n个空汽水瓶，她想知道自己最多可以喝到多少瓶汽水。
**/
public static int getBottle(int n) {
if (n < 2) {
return 0;
}
return n >> 1;
}
/**
* 给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。
* 字符串回文指该字符串正序与其逆序逐字符一致
* 输入：
* "absba"
* 复制
* 返回值：
* true
*
* @param str string字符串 待判断的字符串
* @return bool布尔型
*/
public static boolean judge(String str) {
if (str.length() == 1) {
return true;
}
String s = new StringBuilder(str).reverse().toString();
return s.equals(str);
}
/**
* 求出a、b的最大公约数。
*
* @param a int
* @param b int
* @return int
*/
public int gcd(int a, int b) {
if (b > a) {
int i = b;
b = a;
a = i;
}
return a % b == 0 ? b : gcd(b, a % b);
}
}
2022-06-21
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
