- Jump Game 跳跃游戏
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
class Solution {
public boolean canJump(int[] nums) {
int reach = 0;
int n = nums.length;
for(int i=0; i<n; i++){
if(i>reach || reach >=n-1)
break;
reach = Math.max(reach, i+nums[i]);
}
return reach >= n-1;
}
}
- Jump Game II
返回，能够调到lastIndex的最小跳跃次数
// 解法1： dp 会超时
class Solution {
public int jump(int[] nums) {
int n =nums.length;
// 两次遍历
// 外层遍历：终止节点
int[] sums= new int[nums.length]; // 代表了从开始到这里 消耗的最少步数
sums[0] = 0;
for(int i =1; i < n;i++){
// 内层遍历，上一个跳板节点
for(int j =0;j<i;j++){
if((j ==0 || sums[j]>0) && j+nums[j] >= i){
if(sums[i] > 0){
sums[i] = Math.min(sums[i] , sums[j]+1);
}else{
sums[i] = sums[j]+1;
}
}
}
}
// if(sums[n-1]>0)
return sums[n-1];
}
}
解法2： 贪心算法
以确定当前最远能覆盖的节点，放入curr。然后继续扫描，直到当前的路程超过了上一次算出的覆盖范围，那么更新覆盖范围，同时更新条数，因为我们是经过了多一跳才能继续前进的。
int res = 0, last =0, cur=0;
for(int i=0; i < nums.length; i++){
if(i > last){
res++;
last = cur;
}
cur = Math.max(cur, i + nums[i]);
}
return res;
- gas station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
Note:
If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
我们首先要知道能走完整个环的前提是gas的总量要大于cost的总量，这样才会有起点的存在。假设开始设置起点start = 0, 并从这里出发，如果当前的gas值大于cost值，就可以继续前进，此时到下一个站点，剩余的gas加上当前的gas再减去cost，看是否大于0，若大于0，则继续前进。当到达某一站点时，若这个值小于0了，则说明从起点到这个点中间的任何一个点都不能作为起点，则把起点设为下一个点，继续遍历。当遍历完整个环时，当前保存的起点即为所求。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int cumulate_gas_minus_cost = 0; // 若以当前节点为起点，gas-cost之和
int total_sum = 0; // 用于遍历所有节点，计算全部节点的gas-cost之和
int may_start = 0; // 可能作为起点的节点
for(int i=0; i< cost.length; i++){
cumulate_gas_minus_cost+=(gas[i]- cost[i]);
total_sum+=(gas[i]- cost[i]);
if(cumulate_gas_minus_cost <0){
cumulate_gas_minus_cost =0;
may_start = i+1;
}
}
if(total_sum >=0 && may_start < cost.length)
return may_start;
else return -1;
}
}
- candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] count = new int[n];
int sum = 0;
Arrays.fill(count, 1);
// 从左往右遍历一遍，让右边大于左边的小朋友，获得正确数量的candy
for(int i=1; i<n;i++){
if(ratings[i] > ratings[i-1])
count[i]=count[i-1]+1;
}
// 再从右往左遍历一遍，让左边大于右边的小朋友，获得正确数量的candy
for(int i=n-1; i>=1;i--){
sum += count[i];
if(ratings[i-1] > ratings[i] && count[i-1]<=count[i])
{
count[i-1] = count[i]+1;
}
}
sum += count[0];
return sum;
}
}
- Remove Duplicate Letters——给定一个字符串由小写字符组成，移除多余的字符使得每个字符只出现一次。你必须保证结果是字典序是最小的合法字符串。
class Solution {
public String removeDuplicateLetters(String s) {
// 先计算每个字母出现的次数
int[] counts = new int[26];
for(char ch: s.toCharArray()){
counts[ch-'a'] ++;
}
Stack<Character> stack = new Stack<Character>();
for(char c: s.toCharArray()){
// 如果该元素已经在前面，恰当的安排上了，那这里就忽略
if(stack.contains(c)){
counts[c-'a']--;
continue;
}
// 如果下一个字母比当前下，并且后面还有当前c，则出栈
while(stack.isEmpty()==false && stack.peek() > c && counts[stack.peek()-'a']>1){
char top = stack.pop();
counts[top-'a']--;
}
stack.push(c);
}
StringBuffer sb= new StringBuffer();
while(!stack.isEmpty()){
sb.insert(0,stack.pop());
}
return sb.toString();
}
}
- 从一个数组里挑出k个数字组成最大的数组
新建一个空栈stack
遍历数组 nums
弹出栈顶元素如果栈顶元素比nums[i]小,直到
1、栈空
2、剩余的数组不足以填满栈至 k
如果栈的大小小于 k ，则压入nums[i]
返回栈stack
因为栈的长度知道是k，所以可以用数组来实现这个栈。时间复杂度为O(n)，因为每个元素最多被push和pop一次。
具体是用数组实现的，思想是一样的
public int[] createMax(int[] nums1, int k){
if(k ==0 )
return new int[0];
int[] res = new int[k];
int i=0;// 记录res该插入的位置
for(int j=0;j<nums1.length;j++){ // j是nums遍历的index
while(i>0 && res[i-1] < nums1[j] && nums1.length+i-j>k)
i--;
if(i<k)
res[i++] = nums1[j];
}
return res;
}
- Create Maximum Number
Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m=nums1.length;
int n=nums2.length;
int m_need_max=m>=k?k:m; // 最多可从nums1里取数字个数
int m_need_min=n>=k?0:(k-n); // 最少可从nums1里取数字个数
int[] res=new int[k];
if(m+n<k)
return null;
if(m+n == k)
return merge(nums1,nums2,k);
for(int i=m_need_min;i<=m_need_max;i++){
int[] m_temp = createMax(nums1, i); // 从nums1里取出i个数字，构成最大数组
int[] n_temp = createMax(nums2, k-i);
int[] mix = merge(m_temp, n_temp, k);
res = isGreater(res, 0,mix,0)? res : mix;
}
return res;
}
public int[] createMax(int[] nums1, int k){
if(k ==0 )
return new int[0];
int[] res = new int[k];
int i=0;// 记录res该插入的位置
for(int j=0;j<nums1.length;j++){ // j是nums遍历的index
while(i>0 && res[i-1] < nums1[j] && nums1.length+i-j>k)
i--;
if(i<k)
res[i++] = nums1[j];
}
return res;
}
public int[] merge(int[] nums1, int[] nums2, int k){
int[] res = new int[k];
if(k==0)
return res;
int i=0,j=0;
for(int index=0;index<k;index++){
if(isGreater(nums1, i, nums2, j))
res[index] = nums1[i++];
else
res[index] = nums2[j++];
}
return res;
}
public boolean isGreater(int[] nums1, int i, int[] nums2, int j){
for(;i<nums1.length && j<nums2.length; i++, j++){
if(nums1[i] > nums2[j])
return true;
if(nums1[i] < nums2[j])
return false;
}
return i!=nums1.length;
}
- Patching array——补丁数组
Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example 1:
nums = [1, 5, 10], n = 20
Return 2.
思路：我们定义一个变量miss，用来表示[0,n]之间最小的不能表示的值，那么初始化为1，那么此时我们能表示的范围是[0, miss)，表示此时我们能表示0到miss-1的数，如果此时的num <= miss，那么我们可以把我们能表示数的范围扩大到[0, miss+num)，如果num>miss，那么此时我们需要添加一个数，为了能最大限度的增加表示数范围，我们加上miss它本身，以此类推直至遍历完整个数组，我们可以得到结果。
class Solution {
public int minPatches(int[] nums, int n) {
int patchNum = 0;
long miss =1;
int index =0;
while(miss <= n){
if(index<nums.length && nums[index]<= miss){
miss += nums[index++];
}
else{
miss += miss;
patchNum ++;
}
}
return patchNum;
}
}
- Best Time to Buy and Sell Stock II 买卖股票的最佳时间。可交易无数次
只需要遍历一次数组，用一个变量记录遍历过数中的最小值，然后每次计算当前值和这个最小值之间的差值最为利润，然后每次选较大的利润来更新。当遍历完成后当前利润即为所求，代码如下：
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length <=1)
return 0;
int profit = 0;
for(int i=0;i<prices.length-1; i++){
if(prices[i] < prices[i+1]){
profit+= prices[i+1]-prices[i];
}
}
return profit;
}
}
- Best Time to Buy and Sell StockIII买卖股票的最佳时间。最多可交易两次
数组left[i]记录了price[0..i]的最大profit，
数组right[i]记录了price[i..n]的最大profit。
public static void main(String[] args) {
// int[] prices = {3,3,5,0,0,3,1,4};
int[] prices = {2,1,2,0,1};
System.out.println(maxProfit(prices));
}
// 基本思想是分成两个时间段，然后对于某一天，计算之前的最大值和之后的最大值
public static int maxProfit(int[] prices) {
if(prices.length == 0){
return 0;
}
int max = 0;
// dp数组保存左边和右边的利润最大值
int[] left = new int[prices.length]; // 计算[0,i]区间的最大值
int[] right = new int[prices.length]; // 计算[i,len-1]区间的最大值
process(prices, left, right);
// O(n)找到最大值
for(int i=0; i<prices.length; i++){
max = Math.max(max, left[i]+right[i]);
}
return max;
}
public static void process(int[] prices, int[] left, int[] right){
left[0] = 0;
int min = prices[0]; // 最低买入价
// 左边递推公式
for(int i=1; i<left.length; i++){
left[i] = Math.max(left[i-1], prices[i]-min); // i的最大利润为（i-1的利润）和（当前卖出价和之前买入价之差）的较大那个
min = Math.min(min, prices[i]); // 更新最小买入价
}
right[right.length-1] = 0;
int max = prices[right.length-1]; // 最高卖出价
// 右边递推公式
for(int i=right.length-2; i>=0; i--){
right[i] = Math.max(right[i+1], max-prices[i]); // i的最大利润为（i+1的利润）和（最高卖出价和当前买入价之差）的较大那个
max = Math.max(max, prices[i]); // 更新最高卖出价
}
// System.out.println(Arrays.toString(left));
// System.out.println(Arrays.toString(right));
}
- 摆动序列 · Wiggle Subsequence
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence.
如果连续数字之间的差严格地在正和负之间交替，则这样的数字序列称为摆动序列。 第一个差值（如果存在）可以是正的也可以是负的。 少于两个元素的序列通常是摆动序列。可以删除数字。
例如，[1,7,4,9,2,5]是一个摆动序列，因为连续数字的差(6,-3,5,-7,3)交替为正和负。 相反，[1,4,7,2,5]和[1,7,4,5,5]不是摆动序列，第一个是因为它的前两个连续数字的差是正的，而第二个是因为它的最后一个连续数字的差零。
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums == null || nums.length ==0)
return 0;
int up=1,down =1;
for(int i=1;i< nums.length;i++){
if(nums[i]>nums[i-1]){
up=down+1;
}
else if(nums[i]<nums[i-1])
{
down=up+1;
}
}
return Math.max(up, down);
}
}
- Queue Reconstruction by Height——假设有一队人随机站成一个圈。每个人通过一对整数(h, k)描述，其中h是其身高，k是站在他前面并且身高不低于他的人数。编写算法重构队列。
首先我们给队列先排个序，按照身高高的排前面，如果身高相同，则第二个数小的排前面。然后我们新建一个空的数组，遍历之前排好序的数组，然后根据每个元素的第二个数字，将其插入到res数组中对应的位置
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// TODO Auto-generated method stub
if(o1[0] > o2[0])
return -1;
else if(o1[0] < o2[0])
return 1;
else
if(o1[1] > o2[1]){
return 1;
}else if(o1[1] == o2[1])
return 0;
else {
return -1;
}
}
});
List<int[]> res = new LinkedList<int[]>();
for(int[]cur: people){
res.add(cur[1], cur);
}
return res.toArray(new int[people.length][]);
- Non-overlapping Intervals——非重叠区间
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
You may assume the interval's end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
这个题目与《算法导论》中活动安排的题目非常类似。我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。
public int eraseOverlapIntervals(Interval[] intervals) {
Arrays.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval o1, Interval o2) {
// TODO Auto-generated method stub
if(o1.start > o2.start)
return 1;
else if(o1.start< o2.start)
return -1;
else
{
if(o1.end>o2.end)
return 1;
else if(o1.end == o2.end)
return 0;
else
return -1;
}
}
});
if(intervals.length <=1)
return 0;
int res =0;
int lastKeepIndex=0;
for(int i=1;i< intervals.length; i++){
if(intervals[i].start < intervals[lastKeepIndex].end){ // 当前的start < 上一个保留节点的end
res++;
if(intervals[i].end < intervals[lastKeepIndex].end)
lastKeepIndex = i;
}else{
lastKeepIndex = i;
}
}
return res;
}
- Numbers At Most N Given Digit Set
说明：
we can make:
X |3|^1
XX |3| ^ 2
XXX |3| ^ 3
XXXX |3| ^ 3
1XXXX, |3|^4
2XXXX, |3|^4
we can’t do 8XXXX
Total = (3^1 + 3^2 + 3^3 + 3^4) + 2 * |3|^ 4 = 120 + 162 = 282
N = 52525, D = [1,2,5]
However, if d = N[i], we need to check the next digit…
X |3|^1
XX |3| ^ 2
XXX |3| ^ 3
XXXX |3| ^ 3
1XXXX, |3|^4
2XXXX, |3|^4
5????
51XXX |3|^3
52???
521XX |3|^2
522XX |3|^2
525??
5251X |3|^1
5252?
52521 |3|^0
52522 |3|^0
52525 +1
total = (120) + 2 * |3|^4 + |3|^3 + 2*|3|^2 + |3|^1 + 2 * |3|^0 + 1 = 120 + 213 = 333
if every digit of N is from D, then we also have a valid solution, thus need to + 1.
public int atMostNGivenDigitSet(String[] D, int N) {
List<String> res_list = new ArrayList<String>();
String N_str = "" +N;
int len = N_str.length();
int res = 0;
int D_size = D.length;
for(int i=1;i<len; i++){
res += Math.pow(D_size, i);
}
// 外层：从最高->低 遍历目标数字
for(int i=0; i< len; i++){
boolean prefix=false; // =false 代表当前digit偏小 后面位数随意； =true 代表当前数字撞衫了
// 内层：从小->大 遍历 元素数字
for(String curD: D){
if(curD.charAt(0)<N_str.charAt(i)){
res+= Math.pow(D_size, len-i-1);
}else if(curD.charAt(0) == N_str.charAt(i)){
prefix = true;
break; // 当前数字就已经相等了，后面不用比较了，肯定不合适
}
}
if(prefix==false){
return res;
}
}
return res+1; // 如果每一位 都有撞衫数字，则整体+1
}
网友评论