学习记录记录【学习】算法小记
ELIX简单 746 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算从底部到楼梯顶部的最低花费。
1
2
3
4
5
| 输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] mincost = new int[cost.length+1];
mincost[0] = 0;
mincost[1] = 0;
for(int i=2;i<cost.length+1;i++){
mincost[i] = mincost[i-1]+cost[i-1]<mincost[i-2]+cost[i-2]?mincost[i-1]+cost[i-1]:mincost[i-2]+cost[i-2];
}
return mincost[cost.length];
}
}
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int last=0,prelast=0,curcost=0;
for(int i=2;i<len+1;i++){
curcost = Math.min(last+cost[i-1],prelast+cost[i-2]);
prelast = last;
last = curcost;
}
return curcost;
}
}
|
中等 198 打家劫舍
你是一个专业的小偷（我不是），计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
1
2
3
4
| 输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution {
public int rob(int[] nums) {
if(nums.length==1)return nums[0];
if(nums.length==2)return Math.max(nums[0],nums[1]);
if(nums.length==3)return Math.max(nums[1],nums[0]+nums[2]);
int q1=nums[0],q2=nums[1],q3=nums[0]+nums[2],q4=Math.max(q1,q2)+nums[3];
for(int i=4;i<nums.length;i++){
q1 = q2;
q2 = q3;
q3 = q4;
q4 = Math.max(q1,q2)+nums[i];
}
return Math.max(q3,q4);
}
}
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if(len==1)return nums[0];
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i = 2;i<len;i++){
dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);
}
return dp[len-1];
}
}
|
中等 62 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m+1][n+1];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0){
dp[0][j]=1;
continue;
}else if(j==0){
dp[i][0]=1;
continue;
}
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
for(int j=0;j<n;j++){
dp[j]=1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[j]+=dp[j-1];
}
}
return dp[n-1];
}
}
|
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 :
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for(String str:strs){
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key,new ArrayList<String>());
list.add(str);
map.put(key,list);
}
return new ArrayList<List<String>>(map.values());
}
}
|
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public void moveZeroes(int[] nums) {
int left=0,right=0,len=nums.length;
while(right<len){
if(nums[right]!=0){
int temp = nums[right];
nums[right]=nums[left];
nums[left]=temp;
left++;
}
right++;
}
}
}
|
