圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
分析:
刚开始是建立了一个链表,把数字都放进链表里模拟整个过程,最后返回,但效率太低, 差点超时.
class Solution {
public int lastRemaining(int n, int m) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
int index = 0;
while (n>1){
index = (index+m-1)%n;
list.remove(index);
n--;
}
return list.get(0);
}
}
后来看了答案, 本题属于约瑟夫环问题.:(当前index + m) % 上一轮剩余数字的个数
这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。 —— 【约瑟夫问题】维基百科
class Solution {
public int lastRemaining(int n, int m) {
int ans = 0;
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}
股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
分析:
动态规划问题. 设dp[i]是以prices[i]结尾时的最大利润, dp[0]=0, dp[i+1] = max(dp[i], prices[i]-当前遍历到的最小数), 最后返回dp[prices.length-1]
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, res = 0;
for (int i = 0; i < prices.length; i++) {
cost = Math.min(cost, prices[i]);
res = Math.max(res, prices[i] - cost);
}
return res;
}
}
求 1+2+…+n
求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
分析:
想到了用递归,但递归中止判断要用if语句,不知道如何替代,最后看了答案,采用的是逻辑运算符的短路效应.
常见的逻辑运算符有三种，即 “与 && ”，“或 ∣∣ ”，“非 ! ” ；而其有重要的短路效应，如下所示：
if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false
if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true
本题需要实现 “当 n = 1时终止递归” 的需求，可通过短路效应实现:
n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ，此时 “短路” ，终止后续递归
class Solution {
public int sumNums(int n) {
boolean x = n > 1 && (n += sumNums(n - 1)) > 0;
return n;
}
}
|