codetop几道算法题
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
O(n)空间复杂度
class Solution {
public int firstMissingPositive(int[] nums) {
boolean[] exists = new boolean[nums.length+1];
for(int n:nums) {
if(n>nums.length||n<=0) {
continue;
}
exists[n] = true;
}
for(int i=1;i<=nums.length;i++) {
if(!exists[i]) return i;
}
return nums.length+1;
}
}
但是要求常数级别复杂度，就只能原地那种了。
原地
class Solution {
public int firstMissingPositive(int[] nums) {
// 答案最多是n+1，
for(int i=0;i<nums.length;i++) {
int cur = i;
int curNum = nums[cur];
while(curNum!=cur+1) {
int nextPos = curNum-1;
if(nextPos>=nums.length||nextPos<0) break;
int nextPosNum = nums[nextPos];
nums[nextPos] = curNum;
cur =nextPos;
curNum = nextPosNum;
}
}
for(int i=0;i<nums.length;i++) {
if(nums[i]!=i+1) return i+1;
}
return nums.length+1;
}
}
不要想着一开始就写最优代码，先能跑再优化。
98. 验证二叉搜索树
验证中序遍历
/**
* 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 {
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
int lastNodeValue = Integer.MIN_VALUE;
Deque<TreeNode> stack = new LinkedList<>();
stack.addLast(root);
TreeNode cur = root;
boolean firstMeet = true;
while(!stack.isEmpty()) {
if(cur.left!=null) {
stack.addLast(cur.left);
cur = cur.left;
continue;
}
do {
if(stack.isEmpty()) return true;
cur = stack.pollLast();
if(cur.val>lastNodeValue) {
lastNodeValue = cur.val;
} else if(cur.val==lastNodeValue) {
if(!firstMeet) {
return false;
}
} else {
return false;
}
firstMeet = false;
} while(cur.right==null);
stack.addLast(cur.right);
cur = cur.right;
}
return true;
}
}
递归出神入化写法
我是想不出来。
class Solution {
private long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if(root==null) return true;
if(!isValidBST(root.left)) {
return false;
}
if(root.val<=pre) {
return false;
}
pre = root.val;
if(!isValidBST(root.right)) {
return false;
}
return true;
}
}
3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] count = new int[128];
int left = 0;
int maxLen = -1;
for(int i=0;i<s.length();i++) {
if(count[s.charAt(i)]==0) {
count[s.charAt(i)]++;
} else {
maxLen = Math.max(maxLen,i-left);
while(left<i) {
count[s.charAt(left)]--;
left++;
if(count[s.charAt(i)]==0) {
break;
}
}
count[s.charAt(i)]=1;
}
}
maxLen = Math.max(maxLen,s.length()-left);
return maxLen;
}
}
139. 单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
int cur;
for(int i=0;i<s.length();i++) {
cur = i+1;
for(String word:wordDict) {
if(cur-word.length()<0) continue;
if(s.substring(cur-word.length(),cur).equals(word)) {
dp[cur] |= dp[cur-word.length()];
} else {
dp[cur] |= false;
}
}
}
//System.out.println(Arrays.toString(dp));
return dp[s.length()];
}
}
209. 长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
for(int i=0;i<nums.length;i++) {
sum += nums[i];
while(sum>=target) {
minLen = Math.min(minLen,i-left+1);
sum-=nums[left];
left++;
}
}
return minLen==Integer.MAX_VALUE?0:minLen;
}
}
224. 基本计算器
class Solution {
public int calculate(String s) {
s = s.trim();
if(s.length()==0) return 0;
int i = s.length()-1;
for(;i>=0;i--) {
if(s.charAt(i)=='(') break;
}
int left = i;
i = Math.max(left,0);
for(;i<s.length();i++) {
if(s.charAt(i)==')') break;
}
int right = i;
int n = s.length();
int sig = 1;
int cur = 0;
int result = 0;
if(left==-1&&right==n) {
for(i=0;i<s.length();i++) {
if(s.charAt(i)==' ') continue;
if(s.charAt(i)>='0'&&s.charAt(i)<='9') cur = cur*10+s.charAt(i)-'0';
else {
result += sig*cur;
cur = 0;
sig = s.charAt(i)=='+'?1:-1;
}
}
result += sig*cur;
return result;
}
int mm = calculate(s.substring(left+1,right));
if(mm>=0) return calculate(s.substring(0,left)+String.valueOf(mm)+s.substring(right+1,s.length()));
else {
String le = s.substring(0,left).trim();
String ri = s.substring(right+1,s.length());
if(ri.length()==0) ri="+0";
if(le.length()==0) le="0+";
char cc = le.charAt(le.length()-1);
le = le.substring(0,le.length()-1);
if(cc=='-') {
return calculate(le+"+"+String.valueOf(0-mm)+ri);
} else {
return calculate(le+String.valueOf(mm)+ri);
}
}
}
}
166. 分数到小数
import java.util.HashMap;
import java.util.Map;
class Solution {
public String fractionToDecimal(long numerator, long denominator) {
if(numerator==0) return "0";
if(numerator<0&&denominator<0) return fractionToDecimal(-numerator,-denominator);
if(numerator<0) return "-"+fractionToDecimal(-numerator,denominator);
if(denominator<0) return "-"+fractionToDecimal(numerator,-denominator);
String result = "0.";
if(numerator%denominator==0) return String.valueOf(numerator/denominator);
if(numerator>denominator) result= numerator / denominator +".";
numerator = numerator%denominator;
long oriNumerator = numerator;
Map<Long,Integer> pos = new HashMap<>();
pos.put(oriNumerator,result.length());
numerator*=10;
while(numerator<denominator) {
result+="0";
numerator*=10;
}
while(true) {
result+=String.valueOf(numerator/denominator);
numerator = numerator%denominator;
if(numerator==0) return result;
if(pos.containsKey(numerator)) {
//if(numerator==oriNumerator) {
int dotPos = result.lastIndexOf('.');
return result.substring(0,dotPos+1)+result.substring(dotPos+1,pos.get(numerator))+"(" +result.substring(pos.get(numerator),result.length())+")";
}
pos.put(numerator,result.length());
numerator*=10;
while(numerator<denominator) {
result+="0";
numerator*=10;
}
}
}
public static void main(String[] args) {
//System.out.println(new Solution().fractionToDecimal(4,2));
System.out.println(new Solution().fractionToDecimal(12,6));
System.out.println(new Solution().fractionToDecimal(4,123));
}
}
121. 买卖股票的最佳时机
class Solution {
public int maxProfit(int[] prices) {
int[] rightMax = new int[prices.length];
int m = 0;
for(int i=prices.length-1;i>=0;i--) {
m = Math.max(m,prices[i]);
rightMax[i] = m;
}
int[] leftMin = new int[prices.length];
int n = 10001;
for(int i=0;i<prices.length;i++) {
n = Math.min(n,prices[i]);
leftMin[i] = n;
}
int result = 0;
for(int i=0;i<prices.length;i++) {
result = Math.max(result,rightMax[i]-leftMin[i]);
}
return result;
}
}
1049. 最后一块石头的重量 II
该题可以抽象为将n块石头分为两堆，而后求两堆石头重量总和的最小差值。因此便可看为01背包问题，背包最大容量为这n块石头总重量的一半。那么理想情况下，如果可以刚好装满背包，两堆石头重量总和的最小差值便可为零。
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int stone:stones) {
sum+=stone;
}
int target = sum/2;
// dp[i][j] j块石头，容量为i最多能放
// dp[i][j]: max(dp[i][j],dp[i-stone][j]+stone)
int[][] dp = new int[target+1][stones.length+1];
dp[0][0] = 0;
for(int i=1;i<=target;i++) {
for(int j=1;j<=stones.length;j++) {
if(i>=stones[j-1]) dp[i][j] = Math.max(dp[i][j-1],dp[i-stones[j-1]][j-1]+stones[j-1]);
else dp[i][j]=dp[i][j-1];
}
}
return sum-2*dp[target][stones.length];
}
}
二维、一维。
