codetop几道题练习
3. 无重复字符的最长子串
两次遍历
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) return 0;
int[] lastPos = new int[128];
Arrays.fill(lastPos,-1); // -1 not appear before
int c = (int)s.charAt(0);
lastPos[c] = 0;
int left = 0;
int result = 1;
for(int i=1;i<s.length();i++) {
c = (int)s.charAt(i);
int lastC = lastPos[c];
lastPos[c] = i;
if(lastC!=-1) {
int tmp;
while(left<=lastC) {
tmp = (int)s.charAt(left);
if(lastPos[tmp]<=left) {
lastPos[left]= -1;
}
left++;
}
}
//System.out.printf("%d %d\n",left,i);
result = Math.max(result,i-left+1);
}
return result;
}
}
一次遍历
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) return 0;
int[] lastPos = new int[128];
Arrays.fill(lastPos,-1); // -1 not appear before
int c = (int)s.charAt(0);
lastPos[c] = 0;
int left = 0;
int result = 1;
for(int i=1;i<s.length();i++) {
c = (int)s.charAt(i);
if(lastPos[c]!=-1&&left<=lastPos[c]) {
left=lastPos[c]+1;
}
lastPos[c] = i;
//System.out.printf("%d %d\n",left,i);
result = Math.max(result,i-left+1);
}
return result;
}
}
变种:允许最多一个重复字符
需要记录前前一个和前一个字符的位置
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) return 0;
//记录前前一个对应字符的位置,(需要记录前一个字符的位置)
int[] lastPos = new int[128]; //前一个
int[] llPos = new int[128]; //前前一个
Arrays.fill(lastPos,-1); // -1 not appear before
Arrays.fill(llPos,-1);
int c = (int)s.charAt(0);
lastPos[c] = 0;
int left = 0;
int result = 1;
for(int i=1;i<s.length();i++) {
c = (int)s.charAt(i);
if(llPos[c]!=-1&&left<=llPos[c]) {
left=llPos[c]+1;
}
//llPos[c] = i;
llPos[c] = lastPos[c];
lastPos[c] = i;
result = Math.max(result,i-left+1);
}
return result;
}
}
延伸:395. 至少有 K 个重复字符的最长子串
笨方法超时
class Solution {
public int longestSubstring(String s, int cc) {
int n = s.length();
int[][] appearTimes = new int[n+2][128];
int c;
for(int i=0;i<n;i++) {
c = (int)s.charAt(i);
for(int k=0;k<128;k++) {
appearTimes[i+1][k] = appearTimes[i][k];
}
appearTimes[i+1][c]=appearTimes[i][c]+1;
}
for(int k=0;k<128;k++) {
appearTimes[n+1][k] = appearTimes[n][k];
}
//System.out.println(appearTimes[4][(int)'b']);
int result = 0;
for(int i=0;i<=n+1;i++) {
for(int j=0;j<i;j++) {
boolean allGT = true;
for(int k=0;k<128;k++) {
if(appearTimes[i][k]-appearTimes[j][k]<cc&&appearTimes[i][k]-appearTimes[j][k]>0) {
allGT = false;
//System.out.printf("%d %d %c\n",i,j,k);
break;
}
}
if(allGT) {
// System.out.printf("===%d %d\n",i,j);
result = Math.max(result,i==n+1?n-j:i-j);
}
}
}
return result;
}
}
==递归方法==
class Solution {
public int longestSubstring(String s, int k) {
if(s.length()==0||k>s.length()) return 0;
Map<Character,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++) {
map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
}
for(Character c:map.keySet()) {
if(map.get(c)<k) {
int result = 0;
for(String str : s.split(String.valueOf(c)))
result = Math.max(result,longestSubstring(str,k));
return result;
}
}
return s.length();
}
}
41. 缺失的第一个正数
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++) {
if(nums[i]==i+1) continue;
int nextPos = nums[i];
int tmp;
while(nextPos>=1&&nextPos<=n) {
if(nums[nextPos-1]==nextPos) break;
tmp = nums[nextPos-1];
nums[nextPos-1] = nextPos;
nextPos = tmp;
}
}
for(int i=0;i<n;i++) {
if(nums[i]!=i+1) return i+1;
}
return n+1;
}
}
129. 求根节点到叶节点数字之和
递归
递归比较简单。
class Solution {
public int sumNumbers(TreeNode root) {
return sumNumbers(root,0);
}
private int sumNumbers(TreeNode root,int father) {
if(root==null) return father;
if(root.left==null&&root.right==null) return father*10+root.val;
int left = 0;
int right = 0;
if(root.left!=null) left = sumNumbers(root.left,father*10+root.val);
if(root.right!=null) right = sumNumbers(root.right,father*10+root.val);
return left+right;
}
}
非递归
/**
* 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 int sumNumbers(TreeNode root) {
if(root==null) return 0;
Map<TreeNode,Integer> map = new HashMap<>();
Deque<TreeNode> queue = new LinkedList<>();
map.put(root,root.val);
queue.addLast(root);
int result = 0;
while(!queue.isEmpty()) {
int n = queue.size();
for(int i=0;i<n;i++) {
TreeNode cur = queue.pollFirst();
if(cur.left==null&&cur.right==null) {
result+=map.get(cur);
continue;
}
if(cur.left!=null) {
queue.addLast(cur.left);
map.put(cur.left,cur.left.val+map.get(cur)*10);
}
if(cur.right!=null) {
queue.addLast(cur.right);
map.put(cur.right,cur.right.val+map.get(cur)*10);
}
}
}
return result;
}
}
==(再看看)124. 二叉树中的最大路径和
递归,不连父节点向上传递的直接比较大小,传递的时候只能传左孩子、右孩子和父节点,不能同时传,传的时候也要判断小于零拉倒。最后如果是零的话,选一个最大的结点。
/**
* 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 {
private int result;
public int maxPathSum(TreeNode root) {
result = Integer.MIN_VALUE;
maxPathSum0(root);
if(result==0) {
result = Integer.MIN_VALUE;
findLargestNode(root);
}
return result;
}
private void findLargestNode(TreeNode root) {
if(root==null) return;
result = Math.max(result,root.val);
findLargestNode(root.left);
findLargestNode(root.right);
}
private int maxPathSum0(TreeNode root) {
if(root==null) return 0;
int left = maxPathSum0(root.left);
int right = maxPathSum0(root.right);
result = Math.max(result,left);
result = Math.max(result,right);
result = Math.max(result,left+right+root.val);
int tmp = Math.max(Math.max(left+root.val,right+root.val),root.val);
return tmp<0?0:tmp;
}
}
打印路径呢?
在每一个max的地方考虑路径。
402. 移掉 K 位数字
超时需优化
class Solution {
public String removeKdigits(String num, int k) {
//num = "0"+num+"0";
return removeKdigits0(num,k);
}
public String removeKdigits0(String num, int k) {
if(k==0) {
int i=0;
for(;i<num.length();i++) {
if(num.charAt(i)!='0') {
break;
}
}
String result = num.substring(i,num.length());
return result.length()==0?"0":result.substring(0,result.length());
}
int i=1;
for(;i<num.length();i++) {
if(num.charAt(i)>=num.charAt(i-1)) {
continue;
} else {
break;
}
}
String n = num.substring(0,i-1)+num.substring(i,num.length());
return removeKdigits0(n,k-1);
}
}
==避免重复执行:单调栈==
class Solution {
public String removeKdigits(String num, int k) {
//num = "0"+num+"0";
return removeKdigits0(num,k);
}
public String removeKdigits0(String num, int k) {
if(num==null||k>num.length()) return "0";
num = num + "0";
Deque<Character> deque = new LinkedList<>();
deque.addLast(num.charAt(0));
int count = 0;
for(int i=1;i<num.length();) {
if(deque.isEmpty() || num.charAt(i)>=deque.getLast()) {
deque.addLast(num.charAt(i));
i++;
continue;
} else {
//num.charAt(i)<deque.getLast()
deque.pollLast();
count++;
if(count==k) {
StringBuilder result = new StringBuilder();
for(Character c:deque) {
result.append(c);
}
result.append(num.substring(i,num.length()-1));
String ret = result.toString();
int kk = 0;
for(;kk<ret.length();kk++) {
if(ret.charAt(kk)!='0') break;
}
ret = ret.substring(kk,ret.length());
return ret.length()==0?"0":ret;
}
}
}
return "0";
}
}
(刚看到不容易想)31. 下一个排列
从后往前看,如果降序,继续找,直到找到升序或者结束,如果一直降序,排列,返回。否则将第一个升序的值和右边降序序列的最小值交换,排序右边的降序序列,返回。
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n-1;
int j = i;
for(;i>=1;i--) {
j = i;
if(nums[i-1]>=nums[i]) continue;
else {
// nums[i-1]<nums[i]
// 找到右边比nums[i-1]大但是最小的数
for(j=n-1;j>=i;j--) {
if(nums[j]>nums[i-1]) break;
}
break;
}
}
if(i==0) {
Arrays.sort(nums);
return;
}
int tmp = nums[i-1];
nums[i-1] = nums[j];
nums[j] = tmp;
Arrays.sort(nums,i,n);
}
}
反转链表
206. 反转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null) return head;
ListNode pre = null;
ListNode cur = head;
ListNode next;
while(cur!=null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
92. 反转链表 II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode fakeHead = new ListNode();
fakeHead.next = head;
// find node before left node
ListNode before = fakeHead;
for(int i=1;i<left;i++) {
before = before.next;
}
ListNode cur = before.next;
before.next = null;
ListNode revHead = cur;
ListNode pre = null;
ListNode next = cur.next;
for(int i=left;i<=right;i++) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
ListNode revTail = pre;
before.next = revTail;
revHead.next = cur;
return fakeHead.next;
}
}
98. 验证二叉搜索树
递归
判断左右结点是否符合范围,进一步判断左右节点的左右节点是否符合范围。
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST0(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
private boolean isValidBST0(TreeNode root,long min,long max) {
if(root==null) return true;
if(root.val<=min||root.val>=max) {
return false;
}
return isValidBST0(root.left,min,root.val) &&
isValidBST0(root.right,root.val,max);
}
}
151. 颠倒字符串中的单词
先转内部,再转整体。
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
s = s+" ";
char[] chrs = s.toCharArray();
int left = -1;
int right = -1;
for(int i=0;i<chrs.length;i++) {
if(chrs[i]==' ') {
if(left==-1) continue;
else {
right = i-1;
for(int j=right;j>=left;j--) {
sb.append(chrs[j]);
}
sb.append(" ");
left = -1;
right = -1;
}
}
else {
// char
if(left==-1) {
left = i;
}
}
}
sb.deleteCharAt(sb.length()-1);
return sb.reverse().toString();
}
}
或者:
class Solution {
public String reverseWords(String s) {
int n = s.length();
char[] array = s.toCharArray();
// 删除冗余空格
int afterSize = 0;
int cur = 0;
// 删除首部空格
for(;cur<n;cur++) {
if(array[cur]!=' ') {
array[afterSize++] = array[cur];
cur++;
break;
}
}
// 删除其它空格
for(;cur<n;cur++) {
if(array[cur]!=' ') {
array[afterSize++] = array[cur];
}
else {
if(array[afterSize-1]==' ') continue;
else array[afterSize++] = ' ';
}
}
afterSize--;
if(array[afterSize]==' ') afterSize--;
cur = 0;
int left = 0;
for(;cur<afterSize;cur++) {
if(array[cur]==' ') {
reverseChrs(array,left,cur-1);
left=cur+1;
}
}
reverseChrs(array,left,afterSize);
reverseChrs(array,0,afterSize);
return String.valueOf(Arrays.copyOfRange(array,0,afterSize+1));
}
private void reverseChrs(char[] chrs,int start,int end) {
int i=start;
int j=end;
while(i<j) {
char tmp = chrs[i];
chrs[i] = chrs[j];
chrs[j] = tmp;
i++;
j--;
}
}
}
297. 二叉树的序列化与反序列化
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null) return "[]";
StringBuilder sb = new StringBuilder("[");
Deque<TreeNode> cur = new LinkedList<>();
cur.addLast(root);
StringBuilder lastStr = new StringBuilder();
while(!cur.isEmpty()) {
int n = cur.size();
TreeNode node;
boolean isNull = true;
for(int i=0;i<n;i++) {
node = cur.pollFirst();
if(node==null) {
lastStr.append("null,");
continue;
}
sb.append(lastStr);
sb.append(node.val);
lastStr.setLength(0);
sb.append(",");
cur.addLast(node.left);
cur.addLast(node.right);
if(node.left!=null||node.right!=null) {
isNull = false;
}
}
if(isNull) break;
}
sb.deleteCharAt(sb.length()-1);
sb.append("]");
//System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
StringBuilder sb = new StringBuilder(data);
sb.deleteCharAt(0);
sb.deleteCharAt(sb.length()-1);
if(sb.length()==0) return null;
String[] strs = sb.toString().split(",");
TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
Deque<TreeNode> deque = new LinkedList();
deque.addLast(root);
TreeNode cur;
int i = 1;
while(!deque.isEmpty()) {
cur = deque.pollFirst();
if(cur==null) continue;
if(i>=strs.length) break;
if(strs[i].equals("null")) cur.left = null;
else {
cur.left = new TreeNode(Integer.parseInt(strs[i]));
deque.addLast(cur.left);
}
i++;
if(i>=strs.length) break;
if(strs[i].equals("null")) cur.right = null;
else {
cur.right = new TreeNode(Integer.parseInt(strs[i]));
deque.addLast(cur.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
93. 复原 IP 地址
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
Deque<String> deque = new LinkedList<>();
restoreIpAddresses(s,0,3,result,deque);
return result;
}
private void restoreIpAddresses(String s,int start,int times,List<String> result,Deque<String> deque) {
if(times==0) {
String last = s.substring(start,s.length());
if(isLegal(last)) {
deque.add(last);
result.add(String.join(".",new LinkedList(deque)));
deque.pollLast();
}
return;
}
for(int i=start;i<start+3;i++) {
if(i>=s.length()) return;
String str = s.substring(start,i+1);
if(isLegal(str)) {
deque.addLast(str);
restoreIpAddresses(s,i+1,times-1,result,deque);
deque.pollLast();
}
}
}
private boolean isLegal(String str) {
if(str.length()==0||str.length()>3) {
return false;
}
if(str.equals("0")) return true;
if(str.charAt(0)=='0') return false;
for(int i=0;i<str.length();i++) {
if(str.charAt(i)<'0'||str.charAt(i)>'9') return false;
}
return Integer.parseInt(str)<=255;
}
}
139. 单词拆分
动态规划。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n+1];
dp[0] = true;
for(int i=1;i<=n;i++) {
for(String word:wordDict) {
if(i-word.length()<0) continue;
if(!word.equals(s.substring(i-word.length(),i))) continue;
dp[i] |= dp[i-word.length()];
}
}
return dp[n];
}
}
15. 三数之和
排序 - 首尾双指针 - 去重
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int lastP = Integer.MIN_VALUE;
for(int i=0;i<nums.length-2;i++) {
if(nums[i]==lastP) continue;
lastP = nums[i];
int sum = 0-nums[i];
int left = i+1;
int right =nums.length-1;
int lastLeft = Integer.MIN_VALUE;
int lastRight = Integer.MIN_VALUE;
// -1 -1 0 1
while(left<right) {
lastLeft = nums[left];
lastRight = nums[right];
if(nums[left]+nums[right]==sum) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
left++;
while(left<n&&nums[left]==lastLeft) left++;
right--;
while(right>=0&&nums[right]==lastRight) right--;
} else if(nums[left]+nums[right]<sum) {
left++;
while(left<n&&nums[left]==lastLeft) left++;
} else {
right--;
while(right>=0&&nums[right]==lastRight) right--;
}
}
}
return result;
}
}
662. 二叉树最大宽度
层序遍历,记录最左边和最右边的值就可以了。
/**
* 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 {
class NodePos {
TreeNode node;
int pos;
public NodePos(TreeNode n,int p) {
node = n;
pos = p;
}
}
public int widthOfBinaryTree(TreeNode root) {
int result = -1;
Deque<NodePos> deque = new LinkedList<>();
if(root==null) return 0;
deque.addLast(new NodePos(root,1));
NodePos cur;
while(!deque.isEmpty()) {
int left = -1;
int right = -1;
int n = deque.size();
for(int i=0;i<n;i++) {
cur = deque.pollFirst();
if(i==0) {
left = right = cur.pos;
}
if(i==n-1) {
right = cur.pos;
}
if(cur.node.left!=null) deque.addLast(new NodePos(cur.node.left,cur.pos*2));
if(cur.node.right!=null) deque.addLast(new NodePos(cur.node.right,cur.pos*2+1));
}
result = Math.max(result,right-left+1);
}
return result;
}
}