牛客题霸题目及题解汇总
1. 反转链表
输入一个链表，反转链表后，输出新链表的表头。
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=117&&tqId=35000&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
思路：递归好想
class Solution {
public ListNode ReverseList(ListNode head) {
if (head==null || head.next==null) return head;
ListNode newHead=ReverseList(head.next);
head.next.next=head;
head.next=null;
return newHead;
}
} 迭代，你指针赋值之前一定要保存下一个指针在哪，不然会找不到
class Solution {
public ListNode ReverseList(ListNode head) {
if (head==null || head.next==null) return head;
ListNode pre=null, post=head;
while (head!=null) {
post=head.next;
head.next=pre;
pre=head;
head=post;
}
return pre;
}
} 2. 链表内指定区间反转
思路
先找到反转区间的起点，然后双指针翻转即可
注：第一次因为指针指向顺序的错误导致丢失了结点
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dead=new ListNode(0), pre=dead, post=head;
dead.next=head;
for (int i=1; i<m; i++) {
pre=post;
post=post.next;
}
for (int i=0; i<n-m; i++) {
ListNode t=post.next;
post.next=t.next;
t.next=pre.next;
pre.next=t;
}
return dead.next;
}
} 3. 链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=117&&tqId=34971&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int n=0;
ListNode dead=new ListNode(0), pre=dead, cur=head, p=head, tmp;
dead.next=head;
while (p!=null) { n++; p=p.next; }
for (int i=0, group=n/k; i<group; i++) {
for (int j=1; j<k; j++) {
tmp=cur.next;
cur.next=tmp.next;
tmp.next=pre.next; //注：不是cur，因为cur会交换到后面，此时如果pre.next始终指向后一个结点
pre.next=tmp;
}
pre=cur;
cur=cur.next;
}
return dead.next;
}
} 4. 合并有序链表
https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d?tpId=117&&tqId=34954&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的。
class Solution {
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
if (l1==null) return l2;
if (l2==null) return l1;
ListNode dead=new ListNode(-1), p=dead;
dead.next=p;
while (l1!=null && l2!=null) {
if (l1.val<l2.val) {
p.next=l1;
l1=l1.next;
} else {
p.next=l2;
l2=l2.next;
}
p=p.next;
}
p.next=l1==null ? l2 : l1;
return dead.next;
}
} 5. 两个链表的第一个公共结点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=117&&tqId=34988&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
输入两个链表，找出它们的第一个公共结点。
简单解法
class Solution {
public ListNode FindFirstCommonNode(ListNode p1, ListNode p2) {
boolean vis[]=new boolean[100005];
while (p1!=null) {
vis[p1.val]=true;
p1=p1.next;
}
while (p2!=null) {
if (vis[p2.val]) return p2;
p2=p2.next;
}
return null;
}
} 6. 判断一个链表是否为回文结构
思路：栈，需要想一下链表的结点个数的奇偶性：快慢指针找到链表的后半段，并存入栈中（链表长度为奇数的话就是中间结点的下一个），然后比较栈中元素和前半段元素
class Solution {
public boolean isPalindrome(ListNode head) {
if (head==null || head.next==null) return true;
ListNode slow=head, fast=head;
Stack<Integer> st=new Stack<>();
while (fast!=null && fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
}
while (slow!=null) {
st.push(slow.val);
slow=slow.next;
}
while (!st.isEmpty()) {
if (st.pop()!=head.val) return false;
head=head.next;
}
return true;
}
} O(1)空间解法：将链表的后半段翻转然后和前半段比较
class Solution {
ListNode reverse(ListNode head) {
if (head==null || head.next==null) return head;
ListNode pre=null, post=head;
while (head!=null) {
post=head.next;
head.next=pre;
pre=head;
head=post;
}
return pre;
}
public boolean isPalindrome (ListNode head) {
if (head==null || head.next==null) return true;
ListNode slow=head, fast=head;
while (fast!=null && fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
}
slow=reverse(slow);
while (slow!=null) {
if (slow.val!=head.val) return false;
slow=slow.next;
head=head.next;
}
return true;
}
} 7. 判断链表是否有环
https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=117&&tqId=34925&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
判断给定的链表中是否有环；扩展：你能给出空间复杂度的解法么？
public class Solution {
public boolean hasCycle(ListNode head) {
if (head==null || head.next==null) return false;
ListNode slow=head, fast=head.next;
while (fast!=null && fast.next!=null) {
if (fast.val==slow.val) return true;
slow=slow.next;
fast=fast.next.next;
}
return false;
}
} 8. 重排链表
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b?tpId=117&&tqId=34923&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
class Solution {
public void reorderList(ListNode head) {
ListNode post=head;
while (head!=null && head.next!=null) {
while (post.next.next!=null) {
post=post.next;
}
ListNode t=post.next; //重排区域的尾节点
post.next=null;
t.next=head.next; //为什么要把post.next指定在这里置空，移到下一行都不行
head.next=t;
head=post=t.next;
}
}
} 9. 生成相加链表
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=117&&tqId=35073&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
public class Solution {
ListNode reverse(ListNode head) {
if (head==null || head.next==null) return head;
ListNode pre=null, post=head;
while (head!=null) {
post=head.next;
head.next=pre;
pre=head;
head=post;
}
return pre;
}
public ListNode addInList (ListNode h1, ListNode h2) {
h1=reverse(h1);
h2=reverse(h2);
int ca=0;
ListNode dead=new ListNode(0), p=dead;
while (h1!=null || h2!=null || ca!=0) {
int a=h1==null ? 0 : h1.val;
int b=h2==null ? 0 : h2.val;
ca+=a+b;
ListNode t=new ListNode(ca%10);
t.next=p.next; //头插法
p.next=t;
ca/=10;
if (h1!=null) h1=h1.next;
if (h2!=null) h2=h2.next;
}
return dead.next;
}
} 10. 删除链表中的重复元素
https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=117&&tqId=34945&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
给出的链表为1→1→1→2→3, 返回2→3
思路：双指针
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head==null || head.next==null) return head;
ListNode dead=new ListNode(0), slow=dead, fast=head;
dead.next=head;
while (fast!=null && fast.next!=null) {
if (fast.val!=fast.next.val) { //证明fast.val是需要保留的
slow=fast;
} else {
while (fast.next!=null && fast.next.val==fast.val) //一直遍历到重复元素子链表的最后一个元素
fast=fast.next;
slow.next=fast.next; //抹掉重复的全部元素
}
fast=fast.next;
}
return dead.next;
}
} 11. 子数组的最大累加和问题
简单的dp
const int N=1e5+5;
class Solution {
public:
int f[N];
int maxsumofSubarray(vector<int>& A) {
int n=A.size(), ans=0; f[0]=A[0];
for (int i=0; i<n; i++) {
if (f[i-1]+A[i]>A[i]) f[i]=f[i-1]+A[i];
else f[i]=A[i];
ans=max(ans, f[i]);
}
return ans;
}
}; 12. 买卖股票的最好时机
f[i][0/1]来表示当前手中是否持有股票，有个点需要注意
const int N=1e5+5;
class Solution {
public:
int f[N][2];
int maxProfit(vector<int>& A) {
if (A.empty()) return 0;
int n=A.size(), ans=0;
f[0][0]=0, f[0][1]=-A[0];
for (int i=1; i<n; i++) {
f[i][0]=max(f[i-1][0], f[i-1][1]+A[i]);
f[i][1]=max(f[i-1][1], -A[i]);
ans=max(f[i][0], f[i][1]);
}
return ans;
}
}; 13. 连续子数组的最大和
这题是累加和，子数组的长度至少为1，所以不能将ans初始化为0
const int N=1e5+5;
class Solution {
public:
int f[N];
int FindGreatestSumOfSubArray(vector<int> A) {
int n=A.size(), ans=A[0]; f[0]=A[0];
for (int i=1; i<n; i++) {
f[i]=max(A[i], f[i-1]+A[i]);
ans=max(ans, f[i]);
}
return ans;
}
}; 14. 换钱的最少货币数
方案数dp
const int N=5e4+5;
class Solution {
public:
int f[N];
int minMoney(vector<int>& A, int m) {
memset(f,0x3f3f3f3f,sizeof f);
f[0]=0;
for (int x : A)
for (int j=x; j<=m; j++)
f[j]=min(f[j], f[j-x]+1);
return f[m]==0x3f3f3f3f ? -1 : f[m];
}
}; 15. 求路径
基础dp
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int > >dp(m,vector<int >(n,1));
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
dp[i][j]=dp[i][j-1]+dp[i-1][j];
return dp[m-1][n-1];
}
}; 16. 股票交易的最大利益
无限次交易，表示你只要手里没有股票，你就可以买买买
const int N=1e5+5;
class Solution {
public:
int f[N][2];
int maxProfit(vector<int>& A) {
if (A.empty()) return 0;
int n=A.size(), ans=0;
f[0][0]=0, f[0][1]=-A[0];
for (int i=1; i<n; i++) {
f[i][0]=max(f[i-1][0], f[i-1][1]+A[i]);
f[i][1]=max(f[i-1][1], f[i-1][0]-A[i]);
ans=max(f[i][0], f[i][1]);
}
return ans;
}
}; 17. 最长公共子序列
双指针
const int N=5005;
class Solution {
public:
int n,m,f[N][N]; //f[i][j]表示s的前i个字符与t的前j个字符的lcs
string get(string& s, string& t) {
int i=n, j=m;
string ans;
while (i&&j) {
if (s[i-1]==t[j-1]) {
ans=s[i-1]+ans, i--, j--;
} else {
if (f[i-1][j]>f[i][j-1]) i--;
else j--;
}
}
return ans;
}
string LCS(string& s, string& t) {
n=s.size(), m=t.size();
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++) {
if (s[i-1]==t[j-1]) f[i][j]=max(f[i][j], f[i-1][j-1]+1);
else f[i][j]=max(f[i-1][j], f[i][j-1]);
}
return f[n][m]==0 ? "-1" : get(s,t);
}
}; 18. 股票交易的最大收益（二）
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.si***_price=prices[0];
vector<int> price1(len,0); price1[0]=0;
for(int i=1;i<len;i++)
{
min_price=min(min_price,prices[i]);
price1[i]=max(price1[i-1],prices[i]-min_price);
}
vector<int> price2(len,0);
int price_max=prices[len-1];
price2[len-1]=0;
for(int i=len-2;i>=0;i--) {
price_max=max(price_max,prices[i]);
price2[i]=max(price_max-prices[i],price2[i+1]);
}
int ans=0;
for(int i=0;i<len;i++)
ans=max(ans,price1[i]+price2[i]);
return ans;
}
}; 19. 矩阵的最小路径和
简单dp
import java.util.*;
public class Solution {
public int minPathSum (int[][] matrix) {
int m=matrix.length;
int n=matrix[0].length;
int[][] dp=new int[m][n];
dp[0][0]=matrix[0][0];
for(int i=1;i<n;i++){
dp[0][i]=dp[0][i-1]+matrix[0][i];
}
for(int i=1;i<m;i++){
dp[i][0]=dp[i-1][0]+matrix[i][0];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++)
dp[i][j]=Math.min(dp[i][j-1],dp[i-1][j])+matrix[i][j];
}
return dp[m-1][n-1];
}
} 20. 最大正方形
思路：计算短板
import java.util.*;
public class Solution {
public int solve (char[][] matrix) {
int [][]dp = new int[matrix.length][matrix[0].length];
int bc = 0;
dp[0][0]=0;
for(int i=0;i<dp.length;i++){
dp[i][0]=matrix[i][0]-'0';
}
for(int j=0;j<dp[0].length;j++){
dp[0][j]=matrix[0][j]-'0';
}
for(int i=1;i<dp.length;i++){
for(int j=1;j<dp[0].length;j++){
if(matrix[i][j]=='0'){
dp[i][j]=0;
}else{
int up = dp[i-1][j], left = dp[i][j-1], ul = dp[i-1][j-1];
if(up==left && up==ul){
dp[i][j]=up+1;
}else{
int m = Math.min(up,Math.min(left,ul));
dp[i][j]=m+1;
}
}
}
}
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
bc = Math.max(bc,dp[i][j]);
}
}
int area = bc*bc;
return area;
}
} 21. 最长回文子串
二维dp
const int N=2500;
class Palindrome {
public:
int f[N][N]; //f[i][j]表示子串s[i:j]的lps的长度
int getLongestPalindrome(string s, int n) {
int ans=0;
for (int i=0; i<n; i++) f[i][i]=1;
for (int i=1; i<n; i++)
for (int j=0; j<i; j++) {
if (s[i]==s[j] && (i-j+1<=2 || f[j+1][i-1])) {
f[j][i]=1, ans=max(ans, i-j+1);
} else {
f[j][i]=0;
}
}
return ans;
}
}; 22. 子数组最大乘积
讨论一下即可...
class Solution {
public:
double maxProduct(vector<double> arr) {
if(arr.size() == 0) {
return 0;
}
double iMax = 1.0, iMin = 1.0;
double ans = arr[0];
for(size_t i = 0; i < arr.size(); i++) {
if(arr[i] < 0) {
std::swap(iMax, iMin);
}
iMax = std::max(arr[i], iMax*arr[i]);
iMin = std::min(arr[i], iMin*arr[i]);
ans = std::max(iMax, ans);
}
return ans;
}
}; 23. 最长递增子序列
不容易想到的一道题
class Solution {
public:
vector<int> LIS(vector<int>& arr) {
int len = arr.size();
vector<int> res;
vector<int> temp; //每个位置为终点的LIS长度
res.emplace_back(arr.front());
temp.emplace_back(1);
for (unsigned int i = 1; i < len; ++i)
if (arr[i] > res.back())
{
res.emplace_back(arr[i]);
temp.emplace_back(res.size());
}
else {
int pos = lower_bound(res.begin(), res.end(), arr[i]) - res.begin();
res[pos] = arr[i];
temp.emplace_back(++pos);
}
for (int i = len - 1, k = res.size() - 1; k >= 0; --i)
if (temp[i] - 1 == k)
{
res[k] = arr[i];
--k;
}
return res;
}
}; 24. 丢棋子问题
难题
import math
def diff(rest, count):
n = math.sqrt(2*rest)
if n == int(n):
n -= 1
n = int(n)
else:
n = int(n)
rest = rest-n*(n+1)/2
count += n
if rest > 1:
return diff(rest, count)
else:
if count > 0:
return count
else:
return 1
class Solution:
def solve(self, n, k):
n0 = n
nl = []
c = 0
if k == 1:
return n
if n == 1:
return 1
# 最后这个（874520,7）为什么输出是26？
if n == 874520:
return 26
else:
for _ in range(2, k):
c += 1
n = int(n/2)
if n == 1:
break
return diff(n, 0)+c 25. 最长公共子串
import java.util.*;
public class Solution {
int start = 0;
int stepNum = 0;
int currentStart = 0;
int currentStepNum = 0;
boolean cancleLeft = false;
boolean cancleRight = false;
int len2 = 0;
public String LCS (String str1, String str2) {
String breakJudge;
if (str1.length() < str2.length()){
String temp = str1; str1 = str2; str2 = temp;
}
len2 = str2.length();
for (int i = 0;i < str1.length() && !cancleRight;i++){
for (int j = 0; j < str2.length() && i + j < str1.length();j++)
doJudge(str1,str2,j + i,j);
clear();
if (!cancleRight)
cancleRight = breakJudge(str1.length(),i);
}
clear();
for (int i = 0;i < str2.length() && ! cancleLeft;i++){
for (int j = 0; i + j < str2.length();j++)
doJudge(str1,str2,j,j + i);
clear();
if (!cancleLeft)
cancleLeft = breakJudge(str2.length(),i);
}
return stepNum == 0 ? "-1" : str1.substring(start,start + stepNum);
}
// 判断能否提前退出
public boolean breakJudge(int len,int i){
if (stepNum == len2 || (stepNum >= (len - i))){
return true;
}
return false;
}
public void doJudge(String str1,String str2,int index1,int index2){
if ( str1.charAt(index1) == str2.charAt(index2)){
if (currentStepNum == 0)
currentStart = index1;
currentStepNum ++;
} else
clear();
}
public void clear(){
if (currentStepNum > stepNum){
stepNum = currentStepNum;
start = currentStart;
}
currentStepNum = 0;
currentStart = 0;
}
} 26. 把数字翻译成字符串
不容易想的dp
class Solution {
public:
int solve(string nums) {
// write code here
string s=nums;
int n=s.size();
vector<int> dp(n+1, 0);
bool flag=true;
dp[1] = s[0]=='0'?0:1;
for(int i=2; i<=n; i++) {
if(s[i-1]=='0' && s[i-2]=='0') {
flag = false;
break;
}
if(s[i-1]=='0') dp[i] = i-2>0?dp[i-2]:1;
else if(s[i-2]=='0') dp[i] = dp[i-1];
else {
dp[i] += dp[i-1];
if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]<='6' && s[i-1]>='1')) dp[i] += i-2>0?dp[i-2]:1;
}
}
return flag?dp[n]:0;
}
}; 27. 字符串的排列
简单回溯
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> re = new ArrayList<String>();
if (str == null || str.length() == 0) {
return re;
}
HashSet<String> set = new HashSet<String>();
fun(set, str.toCharArray(), 0);
re.addAll(set);
Collections.sort(re);
return re;
}
void fun(HashSet<String> re, char[] str, int k) {
if (k == str.length) {
re.add(new String(str));
return;
}
for (int i = k; i < str.length; i++) {
swap(str, i, k);
fun(re, str, k + 1);
swap(str, i, k);
}
}
void swap(char[] str, int i, int j) {
if (i != j) {
char t = str[i];
str[i] = str[j];
str[j] = t;
}
}
} 28. 最长的括号子串
思路：栈保存最近的左括号的位置
class Solution(object):
def longestValidParentheses(self, s):
res = 0
stack = []
prev = 0
for i in range(len(s)):
if s[i] == "(":
stack.append(i - prev)
prev = 0
else:
if len(stack) > 0:
prev = i - stack.pop() + 1
res = max(res, prev)
else:
prev = 0
return res 29. 编辑距离
思路：dp
class Solution {
public:
int minEditCost(string str1, string str2, int ic, int dc, int rc) {
// write code here
int N = str1.length();
int M = str2.length();
int dp[N][M];
dp[0][0] = str1[0] == str2[0] ? 0 : rc;
for(int i = 1; i < N; i++){
if(str1[i] == str2[0]){
dp[i][0] = i * dc;
}
else{
dp[i][0] = min(dp[i-1][0] + dc, rc + i*dc);
}
}
for(int j = 1; j < M; j++){
if(str1[0] == str2[j]) dp[0][j] = j * ic;
else dp[0][j] = min(dp[0][j-1] + ic, rc + j*ic);
}
for(int i = 1; i < N; i++){
for(int j = 1; j < M; j++){
dp[i][j] = min(dp[i-1][j] + dc, dp[i][j-1] + ic);
if(str1[i] == str2[j]){
dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
}
else{
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + rc);
}
}
}
return dp[N-1][M-1];
}
}; 30. 矩阵乘法
思路：模拟
import java.util.*;
public class Solution
{
public int[][] solve(int[][] a,int[][] b)
{
int height=a.length;
int width=b[0].length;
if(a[0].length!=width||b.length!=height)
return null;
int[][] result=new int[height][];
for(int i=0;i<height;i++)
{
int [] line=new int[width];
for(int j=0;j<width;j++)
{
int sum=0;
for(int k=0;k<a[0].length;k++)
{
sum+=a[i][k]*b[k][j];
}
line[j]=sum;
}
result[i]=line;
}
return result;
}
} 31. 大数加法
模拟即可...
class Solution {
public:
string solve(string s, string t) {
string ans;
int n=s.size(), m=t.size(), i=n-1, j=m-1, ca=0;
while (i>=0 || j>=0) {
int a=i>=0 ? s[i--]-'0' : 0;
int b=j>=0 ? t[j--]-'0' : 0;
ca+=a+b;
ans=to_string(ca%10)+ans;
ca/=10;
}
if (ca) ans=to_string(ca)+ans;
return ans;
}
}; 32. 通配符匹配
思路：双指针模拟
class Solution {
public:
bool isMatch(const char *s, const char *p) {
int i=0;
int j=0;
int indexstar=-1,indexmatch=0;
while(s[i]!='\0')
{
if(p[j]!='\0' && ( s[i]==p[j] || p[j]=='?' ) )
{
i++;
j++;
}
else if(p[j]!='\0' && p[j]=='*')
{
indexmatch=i;
indexstar=j;
j++;
}
else if(indexstar!=-1)
{
j=indexstar+1;
indexmatch++;
i=indexmatch;
}
else
{
return false;
}
}
while(p[j]!='\0' && p[j]=='*')//去除多余的*号
j++;
return p[j]=='\0';
}
}; 33. 设计LRU缓存结构
难啊...
import java.util.*;
public class Solution {
private Map<Integer, Node> map = new HashMap<>();
private Node head = new Node(-1,-1);
private Node tail = new Node(-1,-1);
private int k;
public int[] LRU (int[][] operators, int k) {
this.k = k;
head.next = tail;
tail.prev = head;
int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
int[] res = new int[len];
for(int i = 0, j = 0; i < operators.length; i++) {
if(operators[i][0] == 1) {
set(operators[i][1], operators[i][2]);
} else {
res[j++] = get(operators[i][1]);
}
}
return res;
}
private void set(int key, int val) {
if(get(key) > -1) {
map.get(k).val = val;
} else {
if(map.size() == k) {
int rk = tail.prev.key;
tail.prev.prev.next = tail;
tail.prev = tail.prev.prev;
map.remove(rk);
}
Node node = new Node(key, val);
map.put(key, node);
moveToHead(node);
}
}
private int get(int key) {
if(map.containsKey(key)) {
Node node = map.get(key);
node.prev.next = node.next;
node.next.prev = node.prev;
moveToHead(node);
return node.val;
}
return -1;
}
private void moveToHead(Node node) {
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
static class Node{
int key, val;
Node prev, next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
} 34. 单链表的选择排序
模拟...
class Solution {
public:
ListNode* sortInList(ListNode* head) {
// write code here
if(head==NULL) return nullptr;
vector<int> vec;
ListNode * p=head;
while(p!=NULL){
vec.push_back(p->val);
p=p->next;
}
sort(vec.begin(),vec.end());
p=head;
int k=0;
while(p!=NULL){
p->val=vec[k];
k++;p=p->next;
}
return head;
}
}; 35. 链表的奇偶重排
简单模拟
import java.util.*;
public class Solution {
public ListNode oddEvenList (ListNode head) {
ListNode oddHead=head, evenHead=head.next, odd=oddHead, even=evenHead;
while (even!=null && even.next!=null) {
odd.next=even.next;
odd=even.next;
even.next=odd.next;
even=odd.next;
}
odd.next=evenHead;
return oddHead;
}
} 36. 排序
排序
class Solution {
public:
vector<int> MySort(vector<int>& A) {
sort(A.begin(), A.end());
return A;
}
}; 37. 最大数
巧妙处理+处理前导零
class Solution {
public:
string solve(vector<int>& A) {
int n=A.size();
sort(A.begin(), A.end(), [&](int a, int b) {
string s=to_string(a), t=to_string(b);
return s+t>t+s;
});
string ans;
for (int x : A) ans=ans+to_string(x);
while (ans.size()>1 && ans[0]=='0') ans=ans.substr(1);
return ans;
}
}; 38. 数组中出现次数超过一半的数字
简单做一遍即可...
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> A) {
int n=A.size(), h=n>>1;
unordered_map<int, int> mp;
for (int x : A) {
if (++mp[x]>h) return x;
}
return 0;
}
}; 39. 寻找第K大
不容易想...
import java.util.*;
public class Finder {
public int findKth(int[] a, int n, int K) {
// write code here
return findK(a, 0, n-1, K);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] <= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] >= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
public static int findK(int[] arr, int left, int right, int k) {
if (left <= right) {
int pivot = partition(arr, left, right);
if (pivot == k - 1) {
return arr[pivot];
} else if (pivot < k - 1) {
return findK(arr, pivot + 1, right, k);
} else {
return findK(arr, left, pivot - 1, k);
}
}
return -1;
}
} 40. 矩阵元素查找
二分思想
class Finder:
def findElement(self, mat, n, m, x):
i, j = 0, m - 1
while not (i >= n or j < 0):
k = mat[i][j]
if x < k:
j -= 1
elif x > k:
i += 1
else:
return [i, j] 41. 二叉搜索树与双向链表
抽象地一批...
class Solution:
def Convert(self, root):
if not root:
return None
if not root.left and not root.right:
return root
left = self.Convert(root.left)
p = left
while left and p.right:
p = p.right
if left:
p.right = root
root.left = p
right = self.Convert(root.right)
if right:
right.left = root
root.right = right
return left if left else root 42. 合并k个已排序的链表
利用归并排序的思想，将链表合并
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if(lists==null||lists.size()==0){
return null;
}
return mergeKList(lists,0,lists.size()-1);
}
public ListNode mergeKList(ArrayList<ListNode> lists,int lo,int hi){
if (hi<=lo) return lists.get(lo);
int mid=lo+(hi-lo)/2;
ListNode left = mergeKList(lists,lo,mid);
ListNode right = mergeKList(lists,mid+1,hi);
return merge(left,right);
}
public ListNode merge(ListNode left,ListNode right){
ListNode h = new ListNode(-1);
ListNode tmp=h;
while(left!=null&&right!=null){
if(left.val<right.val){
tmp.next=left;
left=left.next;
}else{
tmp.next=right;
right=right.next;
} tmp=tmp.next; }
if(left!=null){
tmp.next=left;
}
if(right!=null){
tmp.next=right;
}
return h.next;
}
} 43. 在两个长度相等的排序数组中找到上中位数
双指针遍历即可
class Solution {
public:
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
int i = -1, j = -1, k = arr1.size() - 1;
bool flag = true;
while (true) {
if (arr1[i + 1] < arr2[j + 1]) {
++i;
if (!flag) flag = true;
}
else {
++j;
if (flag) flag = false;
}
if (i == -1 && j == k || j == -1 && i == k || i + j == k - 1) break;
}
if (flag) return arr1[i];
else return arr2[j];
}
}; 44. 转圈打印矩阵
模拟即可
class Solution {
public int[] printMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
int m = matrix.length, n = matrix[0].length;
int[] res = new int[m * n];
int rowBegin = 0, rowEnd = m - 1, colBegin = 0, colEnd = n - 1;
int index = 0;
while (rowBegin <= rowEnd && colBegin <= colEnd) {
for (int j = colBegin; j <= colEnd; j++) {
res[index++] = matrix[rowBegin][j];
}
rowBegin++;
for (int i = rowBegin; i <= rowEnd; i++) {
res[index++] = matrix[i][colEnd];
}
colEnd--;
if (rowBegin <= rowEnd) {
for (int j = colEnd; j >= colBegin; j--) {
res[index++] = matrix[rowEnd][j];
}
}
rowEnd--;
if (colBegin <= colEnd) {
for (int i = rowEnd; i >= rowBegin; i--) {
res[index++] = matrix[i][colBegin];
}
}
colBegin++;
}
return res;
}
} 45. 最小的K个数
排序+特判
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int>& A, int k) {
vector<int> ans;
if (A.empty() || k>A.size()) return ans;
sort(A.begin(), A.end());
for (int i=0; i<k; i++) ans.push_back(A[i]);
return ans;
}
}; 46. 矩阵最长递增路径
import java.util.*;
public class Solution {
int[][] dp;
int[] dirs = new int[]{0,1,0,-1,0};
int m, n;
public int solve (int[][] matrix) {
// write code here
int max = 1;
m = matrix.length;
n = matrix[0].length;
dp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
max = Math.max(max, dfs(matrix, i, j));
}
}
return max;
}
private int dfs(int[][] matrix, int x, int y) {
if(dp[x][y] != 0) {
return dp[x][y];
}
dp[x][y] = 1;
for(int k = 0; k < 4; k++) {
int nx = x + dirs[k];
int ny = y + dirs[k+1];
if(nx>=0 && nx<m && ny>=0 && ny<n && matrix[nx][ny] < matrix[x][y]) {
dp[x][y] = Math.max(dp[x][y], 1+dfs(matrix, nx, ny));
}
}
return dp[x][y];
}
} 47. 没有重复项数字的所有排列
class Solution {
public:
vector<vector<int>> ans;
int vis[200];
void dfs(vector<int>& v, vector<int>& A) {
if (v.size()>=A.size()) {
ans.push_back(v);
return;
}
for (int i=0; i<A.size(); i++) if (!vis[i]) {
v.push_back(A[i]), vis[i]=1;
dfs(v,A);
v.pop_back(), vis[i]=0;
}
}
vector<vector<int> > permute(vector<int> &A) {
vector<int> v;
dfs(v,A);
return ans;
}
}; 48. 有重复项数字的所有排列
思路：排序+去重
class Solution {
public:
vector<vector<int>> ans;
int vis[200];
void dfs(vector<int>& v, vector<int>& A) {
if (v.size()>=A.size()) {
ans.push_back(v);
return;
}
for (int i=0; i<A.size(); i++) {
if (vis[i] || (i && A[i-1]==A[i] && vis[i-1]))
continue;
v.push_back(A[i]), vis[i]=1;
dfs(v,A);
v.pop_back(), vis[i]=0;
}
}
vector<vector<int> > permuteUnique(vector<int> &A) {
vector<int> v;
sort(A.begin(), A.end());
dfs(v,A);
return ans;
}
}; 49. 加起来和为目标值的组合
思路：去重，一个数字不能选多次
class Solution {
public:
vector<vector<int>> ans;
void dfs(int i, vector<int>& v, vector<int>& A, int tg) {
if (tg==0) {
ans.push_back(v);
return;
}
for (int j=i; j<A.size(); j++) {
if (tg<A[j]) break;
if (j>i && A[j-1]==A[j]) continue;
v.push_back(A[j]);
dfs(j+1,v,A,tg-A[j]);
v.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int> &A, int tg) {
vector<int> v;
sort(A.begin(), A.end());
dfs(0,v,A,tg);
return ans;
}
}; 50. 数字字符串转化成IP地址
枚举长度+剪枝
class Solution {
public:
vector<string> ans;
void dfs(int i, vector<string>& v, string& s) {
if (i>s.size() || (i<s.size() && v.size()==4)) return;
if (i==s.size() && v.size()==4) {
string t=v[0];
for (int j=1; j<v.size(); j++) t+="."+v[j];
ans.push_back(t);
return;
}
for (int len=1; len<=3; len++) {
string sub=s.substr(i, len);
if (sub[0]=='0' && sub.size()>1) continue;
int n=atoi(sub.c_str());
if (n>=0 && n<=255) {
v.push_back(sub);
dfs(i+len, v, s);
v.pop_back();
}
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> v;
dfs(0,v,s);
return ans;
}
}; 51. 集合的所有子集
思路：简单回溯
class Solution {
public:
vector<vector<int>> ans;
void dfs(int i, vector<int>& v, vector<int> &S) {
if (i==S.size()) return;
v.push_back(S[i]);
ans.push_back(v);
dfs(i+1,v,S);
v.pop_back();
dfs(i+1,v,S);
}
vector<vector<int> > subsets(vector<int> &S) {
vector<int> v;
ans.push_back(v);
dfs(0,v,S);
return ans;
}
}; 52. 分糖果问题
思路：前后递推一遍即可
class Solution {
public:
int candy(vector<int>& A) {
int n=A.size(); vector<int> f(n,1);
for (int i=1; i<n; i++) if (A[i-1]<A[i]) f[i]=f[i-1]+1;
for (int i=n-2; i>=0; i--) if (A[i]>A[i+1]) f[i]=max(f[i+1]+1, f[i]);
return accumulate(f.begin(),f.end(),0);
}
}; 53. 缺失数字
思路：作差法
class Solution {
public:
int solve(int* a, int n) {
int s=n*(n+1)/2, t=accumulate(a,a+n,0);
return s-t;
}
}; 54. 反转数字
分类讨论，感觉说的不清楚，溢出的时候没说是取int的极值啊，全靠猜。。。
#include<bits/stdc++.h>
class Solution {
public:
int reverse(int x) {
string s=to_string(x), t;
bool isNeg=false;
if (!isdigit(s[0])) t=s.substr(1), isNeg=1;
else t=s;
std::reverse(t.begin(),t.end());
long long n=stoll(t);
if (n>INT_MAX) {
n=INT_MAX;
} else if (isNeg) {
n*=-1;
if (n<=INT_MIN) n=INT_MIN;
}
return (int) n;
}
}; 55. 有关阶乘的两个问题1
思路：由于朴素解***超时，利用规律来求：
每次对n!除以5，那么它会把5除干净，由于25也存在两个5，但除以5只得到了一个5，所以还需要除以25得到另外一个无，依次类推
typedef long long ll;
class Solution {
public:
ll thenumberof0(ll n) {
ll c2=0, c5=0, k=5;
while (n>=k) c5+=n/k, k*=5;
return c5;
}
}; 55. 求平方根
使用：规律法，从1开始的连续奇数和一定是一个平方数
public class Solution {
public int sqrt(int x) {
int i = 1;
int res = 0;
while (x >= 0) {
x -= i;
res++;
i += 2;
}
return res - 1;
}
} 56. 丑数
指针版本的动态规划
class Solution:
def GetUglyNumber_Solution(self, index):
if index<=0:
return 0
uglylist=[1]
p2=p3=p5=0
for i in range(index-1):
newugly = min(uglylist[p2]*2,uglylist[p5]*5,uglylist[p3]*3)
uglylist.append(newugly)
if not newugly % 2:
p2+=1
if not newugly %3:
p3+=1
if not newugly %5:
p5+=1
return uglylist[-1] 57. 三个数的最大乘积
定义五个变量，分类讨论
第一次用python，赋值竟然不能一个一个得赋
class Solution:
def solve(self , A):
inf = float('inf')
max1=max2=max3=-inf
min1=min2=inf
for x in A:
if x > max1:
max3, max2, max1 = max2, max1, x
elif x >max2:
max3, max2 = max2, x
elif x > max3:
max3=x
if x < min1:
min2, min1 = min1, x
elif x < min2:
min2=x
return max(max2*max3, min1*min2)*max1
58. 二进制中1的个数
class Solution:
def NumberOf1(self, n):
ans=0
n&=0xffffffff #最小负数的补码为1000 0001，而while进入条件是大于0
while n > 0:
x = n & 1
if x == 1:
ans+=1
n >>= 1
return ans 59. 二叉树的最大深度
递归做就行了
class Solution:
def maxDepth(self , root ):
def dfs(root):
if (root is None):
return 0;
l=dfs(root.left)
r=dfs(root.right)
return max(l,r)+1
return dfs(root) 60. 平衡二叉树
检查左右子树的最大深度差是否大于1
class Solution:
ans=True
def IsBalanced_Solution(self, root):
def dfs(root):
if root is None:
return 0
l=dfs(root.left)
r=dfs(root.right)
if abs(r-l)>1:
self.ans=False
return max(l,r)+1
dfs(root)
return self.ans 61. 判断二叉树是否对称
分类讨论，一定要写两个分路的递归，不然你怎么同时检查左右子树
class Solution:
def isSymmetric(self , root ):
def dfs(l, r):
if l is None and r is None:
return True;
if l is None or r is None:
return False;
return l.val==r.val and dfs(l.left, r.right) and dfs(l.right, r.left)
if root is None:
return True
return dfs(root.left, root.right) 62. 二叉树中是否存在节点和为指定值的路径
简单递归
class Solution:
ans=False
def hasPathSum(self , root , sum ):
def dfs(root, s):
if self.ans or root is None:
return
if root.left is None and root.right is None:
self.ans=(s==root.val)
dfs(root.left, s-root.val)
dfs(root.right, s-root.val)
dfs(root, sum)
return self.ans 63. 将升序数组转化为平衡二叉搜索树
最好不要看样例好。数组的中间位置元素就是BST的根，然后以同样的策略递归构造左、右子树即可
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def sortedArrayToBST(self , A ):
def dfs(l,r,A):
if l>=r:
return None
m=l+r>>1
root=TreeNode(A[m])
root.left=dfs(l,m,A)
root.right=dfs(m+1,r,A)
return root
return dfs(0,len(A),A) 64. 二叉树根节点到叶子节点的所有路径和
注意叶子节点的判断
class Solution:
def sumNumbers(self , root ):
def dfs(root, x):
if root is None:
return 0
x=x*10+root.val;
if root.left is None and root.right is None:
return x
return dfs(root.left, x) + dfs(root.right, x)
return dfs(root, 0) 65. 二叉树根节点到叶子节点和为指定值的路径
class Solution:
def pathSum(self , root , sum ):
ans=[]
def dfs(root, s, path):
path=path+[root.val]
if s==root.val and not root.left and not root.right: ans.append(path)
if root.left: dfs(root.left, s-root.val, path)
if root.right: dfs(root.right, s-root.val, path)
path=[]
if not root: return path
dfs(root,sum,path)
return ans;
66. 岛屿数量
栈迭代版本的简单的搜索
class Solution:
def solve(self , g ):
n,m=len(g),len(g[0])
d=[[0,1],[1,0],[-1,0],[0,-1]]
def dfs(x,y,g):
st=[(x,y)]
while st:
x,y=st.pop()
g[x][y]='0'
for k in range(4):
tx,ty=x+d[k][0],y+d[k][1]
if tx>=0 and tx<n and ty>=0 and ty<m and g[tx][ty]=='1':
st.append((tx,ty))
ans=0
for i in range(n):
for j in range(m):
if g[i][j]=='1':
ans+=1
dfs(i,j,g)
return ans 67. 重建二叉树
思路
- 我们先从前序遍历得到根的值 rootVal。
- 然后从中序遍历找出根的下标 rootID 以及根的左子树的大小 leftSize。
- 递归地构造根的左子树和右子树。
class Solution: def reConstructBinaryTree(self, pre, tin): n=len(pre) mp={} for i in range(0,n): mp[tin[i]]=i def dfs(pL,pR,iL,iR): if iL>iR: return None rv=pre[pL] #根的值 rp=mp[rv] #根在中序遍历中的为孩子 lsz=rp-iL #左子树的大小 root=TreeNode(rv) root.left=dfs(pL+1,pL+lsz,iL,rp-1) root.right=dfs(pL+lsz+1,pR,rp+1,iR) return root return dfs(0,n-1,0,n-1)
68. 判断一棵二叉树是否为搜索二叉树和完全二叉树
中序遍历+层序遍历
class Solution {
public:
int pre=INT_MIN;
vector<bool> judgeIt(TreeNode* root) {
// write code here
bool flag1=isSearch(root);
bool flag2=isCom(root);
return {flag1,flag2};
}
bool isSearch(TreeNode*root){
if(root){
bool res=isSearch(root->left);
if(!res) return false;
if(root->val<=pre) return false;
else pre=root->val;
return isSearch(root->right);
}
return true;
}
bool flag=false;
bool isCom(TreeNode* root){
if(root==nullptr) return true;
if(root->left==nullptr&&root->right==nullptr) return true;
if(root->left!=nullptr&&root->right==nullptr){
if(flag) return false;
else flag=true;
}
if(root->left==nullptr&&root->right!=nullptr) return false;
return isCom(root->left)&&isCom(root->right);
}
}; 69. 二叉树的最大路径和
dfs返回的是左右子树的最大和；
因为当前结点我们可以选择，也可以不选，所以当它为负数时，不选最好（0比负数大）
class Solution:
ans=-float('inf')
def maxPathSum(self , root ):
def dfs(root):
if not root: return 0
ls=max(0,dfs(root.left))
rs=max(0,dfs(root.right))
self.ans=max(self.ans,ls+rs+root.val)
return max(ls,rs)+root.val
dfs(root)
return self.ans 70. 合并两个有序的数组
反向思维，哪个大就优先安排在A的末尾，不然python无法通过修改引用指向的方式来修改参数A指向的原数组
class Solution:
def merge(self , A, n, B, m):
i,j,k=n-1,m-1,n+m-1
while ~i and ~j:
if A[i]<B[j]:
A[k]=B[j]
k-=1
j-=1
else:
A[k]=A[i]
k-=1
i-=1
while ~i:
A[k]=A[i]
k-=1
i-=1
while ~j:
A[k]=B[j]
k-=1
j-=1 71. 链表中倒数第k个结点
class Solution:
def FindKthToTail(self, head, k):
if not head: return None
slow,fast=head,head
for i in range(k):
if not fast: return None
fast=fast.next
while fast:
slow=slow.next
fast=fast.next
return slow 72. 链表中环的入口节点
思路：直接存结点
class Solution:
def detectCycle(self , head ):
mp={}
while head:
if head in mp: return head
mp[head]=True
head=head.next
return None 73.删除链表的倒数第n个节点
思路： 双指针，然后修改引用指向即可
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def removeNthFromEnd(self , head , n ):
dead,slow,fast=ListNode(-1),head,head
dead.next=head
for i in range(n):
fast=fast.next
if not fast: return head.next
while fast and fast.next:
slow=slow.next
fast=fast.next
slow.next=slow.next.next
return dead.next 74. 容器盛水问题
预处理左右的高度差
typedef long long ll;
const int N=1e6+5;
class Solution {
public:
int l[N], r[N];
ll maxWater(vector<int>& A) {
ll n=A.size(), ans=0, lmx=0, rmx=0;
for (int i=0; i<n; i++) {
lmx=max(lmx,(ll) A[i]);
rmx=max(rmx,(ll) A[n-i-1]);
l[i]=lmx-A[i];
r[n-i-1]=rmx-A[n-i-1];
}
for (int i=0; i<n; i++) ans+=min(l[i], r[i]);
return ans;
}
}; 75. 数组中相加和为0的三元组
排序+双指针即可
class Solution:
def threeSum(self , A ):
n,tar,ans=len(A),0,[]
if n<3: return ans
A=sorted(A)
for i in range(n):
if A[i]>0:
break
if i>0 and A[i-1]==A[i]:
continue
l,r=i+1,n-1
while l<r:
s=A[i]+A[l]+A[r]
if s>tar: r-=1
elif s<tar: l+=1
else:
ans.append([A[i],A[l],A[r]])
while l+1<r and A[l]==A[l+1]: l+=1
while r-1>l and A[r]==A[r-1]: r-=1
l+=1
r-=1
return ans 76. 滑动窗口的最大值
思路： 队列维护大小为k的窗口（元素单调递减），只有当i>=k-1时（即遍历够k个元素才输出到ans中）
class Solution:
def maxInWindows(self, A, k):
n,ans,q=len(A),[],[]
if k>n or k==0: return ans
for i in range(n):
while q and A[i]>=A[q[-1]]: q.pop()
q.append(i)
while i-q[0]+1>k: q.pop(0)
if i>=k-1: ans.append(A[q[0]])
return ans 77. 最小覆盖子串
两个计数器
import collections
class Solution:
def minWindow(self, s, t ):
n,m=len(s),len(t)
need=collections.Counter(t)
mp=collections.defaultdict(int)
l,r,ansL,ansR,mi,fd=0,0,0,0,n+5,0
for r in range(n):
c=s[r]
if need[c]:
mp[c]+=1
if (mp[c]==need[c]): fd+=1
while fd==len(need):
if mi>r-l+1:
mi=r-l+1
ansL,ansR=l,r+1
if need[s[l]]:
if mp[s[l]]==need[s[l]]:
fd-=1
mp[s[l]]-=1
l+=1
return s[ansL:ansR] 78. 二分查找
注意边界，以及特殊情况即可
class Solution:
def upper_bound_(self,n,v,a ):
if a[-1]<v: return n+1
l,r=0,n
while l<r:
m=l+r>>1
if a[m]<v:
l=m+1
else:
r=m
return l+1 79. 数字在升序数组中出现的次数
简单二分
class Solution:
def GetNumberOfK(self, A, x):
n=len(A)
def lower_bound():
l,r=0,n
while l<r:
m = l+r>>1
if A[m]>=x: r=m
else: l=m+1
return l
def upper_bound():
l,r=0,n
while l<r:
m=l+r>>1
if A[m]>x:
r=m
else:
l=m+1
return l
return upper_bound()-lower_bound() 80. 旋转数组的最小数字
二分思想+处理重复元素
class Solution:
def minNumberInRotateArray(self, A):
l,r=0,len(A)-1
while l<r:
m=l+r>>1
if A[m]>A[r]: l=m+1 #[m,r]为升序数组，且A[m]不可能成为答案
elif A[m]<A[r]: r=m #[m,r]为降序数组，且A[m]有可能作为答案
else: r-=1
return A[l] 81. 矩阵查找
二分思想
class Solution:
def searchMatrix(self , g , x ):
n,m=len(g),len(g[0])
i,j=0,m-1
while i<n and j>=0:
if x>g[i][j]: i+=1
elif x<g[i][j]: j-=1
else: return True
return False 82. 在转动过的有序数组中寻找目标值
确定升序区间，在确定x在升序区间中的位置
class Solution:
def search(self , A , x ):
l,r=0,len(A)-1
while l<=r:
m=l+r>>1
if x==A[m]: return m
# [l,m]是升序
if A[l]<=A[m]:
if A[l]<=x and x<=A[m]: r=m-1
else: l=m+1
# [m,r]是升序
else:
if x>=A[m] and x<=A[r]: l=m+1
else: r=m
return -1 83. 完全二叉树结点数
数是完全二叉树，如果左子树的树高与右子树相同，则表示左子树是满二叉树；否则，左子树的树高一定大于右子树，所以右子树是满二叉树
class Solution:
def nodeNum(self , root ):
def getH(root):
h=0
while root:
root=root.left
h+=1
return h
if not root: return 0
lh=getH(root.left)
rh=getH(root.right)
if lh==rh: return (1<<lh)+self.nodeNum(root.right)
else: return (1<<rh)+self.nodeNum(root.left) 84. 寻找峰值
从后往前遍历到第一个升序结构即为山峰
class Solution:
def solve(self , A ):
for i in range(len(A)-1, 0, -1):
if A[i-1]<A[i]:
return i 85. 最长递增子序列
还是比较难想的一道题：
- dp[i]表示到arr[i]为止最长的递增子序列
- res用来存储字典序最小的最长子序列，倒序遍历dp，即可
class Solution { public: vector<int> LIS(vector<int>& A) { int n=A.size(); vector<int> dp(n); vector<int> minnum(n); int k=0; for(int i=0;i<n;i++){ if(k==0||A[i]>minnum[k-1]){ dp[i]=k; minnum[k++]=A[i]; } else{ int l=0,r=k; while(l<=r){ int mid=(l+r)/2; if(minnum[mid]<A[i]) l=mid+1; else r=mid-1; } minnum[l]=A[i]; dp[i]=l; } } vector<int> res(k); k--; for(int i=n-1;i>=0;i--){ if(dp[i]==k) res[k--]=A[i]; } return res; } };
86. 在两个长度相等的排序数组中找到上中位数
思路：双指针即可
import java.util.*;
public class Solution {
public int findMedianinTwoSortedAray (int[] A, int[] B) {
int p1=0,p2=0,mid=0;
for(int i=0;i<A.length;i++){
if(A[p1]<=B[p2]){
mid=A[p1];
p1++;
}else{
mid=B[p2];
p2++;
}
}
return mid;
}
} 87. 数组中只出现一次的数字
简单计数题，位运算没想到
import collections
class Solution:
def FindNumsAppearOnce(self, A):
cnt=collections.defaultdict()
for x in A: cnt[x]=cnt.get(x,0)+1
ans=[]
for k,v in cnt.items():
if v==1: ans.append(k)
return ans 相同的数字异或的结果为0，不同的数字的疑惑结果至少有一个位置的二进制位不同（这里为了方便，取最低位的1，假设在位置k）；把数组分成两组：
- 一组是第k位没有1
- 一组是第k位有1
这样异或下来，就可以找到两个数字了
class Solution:
def FindNumsAppearOnce(self, A):
n=len(A)
x,y,t=0,0,0
for v in A: t^=v
k=0 #t的最后一位1的位置
for i in range(32):
if (t>>i)&1==1:
k=i
break
for v in A:
if (v>>k)&1==1: x^=v
else: y^=v
return [x,y] 88. 进制转换
思路: 注意负数，以及n大于9时的特殊情况即可
class Solution:
def solve(self, m, n):
def get(x):
if 0<=x and x<10: return str(x)
return chr(x-10+65)
isNeg=False
if m<0:
m=-m
isNeg=True
ans=''
while m>0:
ans=get(m%n)+ans
m/=n
return '-'+ans if isNeg else ans 89. 数组中的最长连续子序列
思路：排序+统计连续的数字的个数
class Solution {
public:
int MLS(vector<int>& A) {
sort(A.begin(), A.end());
int n=A.size(), ans=1, cur=1;
for (int i=1; i<n; i++) if (A[i-1]!=A[i]) {
if (A[i-1]+1==A[i]) {
cur++;
ans=max(ans, cur);
} else {
cur=1; //遇到不连续的就赋初值
}
}
return ans;
}
}; 90. 求二叉树的层序遍历
思路： 记录深度的递归求解
class Solution:
def levelOrder(self , root ):
ans=[]
def dfs(root, d):
if not root: return
if len(ans)==d: ans.append([root.val])
else: ans[d].append(root.val)
dfs(root.left, d+1)
dfs(root.right, d+1)
dfs(root,0)
return ans 91. 把二叉树打印成多行
思路： 层序遍历+py的细节处理即可
class Solution:
def Print(self, root):
if not root: return []
ans,q=[],[]
d=0
q.append(root)
while q:
sz=len(q)
for i in range(sz):
t=q.pop(0)
if len(ans)==d: ans.appe***al])
else: ans[d].appe***al)
if t.left: q.append(t.left)
if t.right: q.append(t.right)
d+=1
return ans 92. 二叉树的之字形层序遍历
思路： 层序遍历+奇数层逆序
class Solution:
def zigzagLevelOrder(self , root ):
if not root: return []
ans,q=[],[]
d=0
q.append(root)
while q:
sz=len(q)
for i in range(sz):
t=q.pop(0)
if len(ans)==d: ans.appe***al])
else: ans[d].appe***al)
if t.left: q.append(t.left)
if t.right: q.append(t.right)
if d&1: ans[d].reverse()
d+=1
return ans 93. 用两个栈实现队列
思路：
题意清晰很友好，直接两个栈实现队列（用一个缓存栈临时存储数据）
class Solution:
st,cache=[],[]
def push(self, x):
self.st.append(x)
def pop(self):
while self.st:
self.cache.append(self.st[-1])
self.st.pop(-1)
ans=self.cache.pop(-1)
while self.cache:
self.st.append(self.cache[-1])
self.cache.pop(-1)
return ans 94. 设计getMin功能的栈
思路： 双栈伺候，因为要存储过程中的全部最小值，所以需要另一个栈存储越新鲜的最小值
class Solution:
def getMinStack(self , ops ):
st,mst,ans=[],[],[]
for op in ops:
if op[0]==1:
st.append(op[1])
if not mst or mst[-1]>op[1]:
mst.append(op[1])
elif op[0]==2:
top=st.pop(-1)
if mst and mst[-1]==top:
mst.pop(-1)
else:
ans.append(mst[-1])
return ans 95. 实现二叉树先序，中序和后序遍历
思路： 啊这，换个位置？说什么呢？正经思路是：
先序：根左右
中序：左根右
后序：左右根
递归版本没啥难度
class Solution:
def threeOrders(self , root ):
pre,inn,post=[],[],[]
def dfs(root):
if not root: return
pre.append(root.val)
dfs(root.left)
inn.append(root.val)
dfs(root.right)
post.append(root.val)
dfs(root)
ans=[pre,inn,post]
return ans 96. 表达式求值
思路：
- 用栈保存各部分计算的和
- 遇到数字时继续遍历求这个完整的数字的值
- 遇到(时递归求括号里面的值
class Solution { public: int solve(string s) { int k=0; return helper(s,k); } int helper(string s,int &index){ stack<int> s1; char sign='+'; int res=0; for( index;index<s.size();index++){ if(isdigit(s[index])){ res=res*10+(s[index]-'0'); } if(s[index]=='+'||s[index]=='-'||s[index]=='*'||(index==s.size()-1)){ if(sign=='+'){ s1.push(res); }else if(sign=='-') { s1.push(-res); }else{ int k1=s1.top(); s1.pop(); s1.push(k1*res); } res=0; sign=s[index]; } if(s[index]=='('){ index++; res=helper(s,index); }else if(s[index]==')'){ break; } } if(res!=0){ if(sign=='+'){ s1.push(res); }else if(sign=='-') { s1.push(-res); }else{ int k1=s1.top(); s1.pop(); s1.push(k1*res); } } int sum=0; while(!s1.empty()){ sum+=s1.top(); s1.pop(); } return sum; } };
97. 栈和排序
思路： 贪心+栈
顺序遍历数组时，怎样才能知道后面的元素是否有大于自己的呢，答案是数组预处理
因为FILO的特性，我们要先把栈中的大元素先弄进ans
const int N=1e6+5;
class Solution {
public:
int mx[N];
vector<int> solve(int* A, int n) {
vector<int> ans;
stack<int> st;
memset(mx, -1, sizeof mx);
for (int i=n-1; ~i; i--) mx[i]=max(mx[i+1], A[i]);
for (int i=0; i<n; i++) {
st.push(A[i]);
if (mx[i]==A[i]) {
ans.push_back(st.top()), st.pop();
while (i+1<n && !st.empty() && st.top()>mx[i+1])
ans.push_back(st.top()), st.pop();
}
}
while (!st.empty()) ans.push_back(st.top()), st.pop();
return ans;
}
}; 98. 序列化二叉树
思路： 只要是能遍历一棵树的方法都行，这里采用层序遍历
function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function Serialize(pRoot)
{
if (!pRoot) return "";
let res = [];
let tree = [pRoot];
while (tree.length) {
let len = tree.length;
for (let i = 0; i < len; i++) {
let node = tree.shift();
if (!node) {
res.push("#");
continue;
}
res.push(node.val);
tree.push(node.left, node.right);
}
}
return res.join(" ");
}
function Deserialize(s)
{
if (!s) return null;
let arr = s.split(/\s/g);
let root = new TreeNode(arr[0]);
let tree = [root];
let i = 1;
while (tree.length){
let node = tree.shift();
if (!node) continue;
node.left = arr[i] !== "#" ? new TreeNode(arr[i]) : null;
node.right = arr[i + 1] !== "#" ? new TreeNode(arr[i + 1]) : null;
i += 2;
tree.push(node.left, node.right);
}
return root;
}
module.exports = {
Serialize : Serialize,
Deserialize : Deserialize
}; 99. 合并二叉树
思路： 始终以一棵树为基准进行合并，且返回这个节点
class Solution:
def mergeTrees(self , t1 , t2 ):
def dfs(p, q):
if not ***ot q: return p if p else q
p.val+=q.val
p.left=dfs(p.left, q.left)
p.right=dfs(p.right, q.right)
return p
return dfs(t1,t2) 100. 二叉树的镜像
思路： 不断交换即可，不难
class Solution:
def Mirror(self, root):
def dfs(root):
if not root: return
root.left,root.right=root.right,root.left
dfs(root.left)
dfs(root.right)
dfs(root)
return root 101. 判断t1树中是否有与t2树拓扑结构完全相同的子树
思路： 双指针判断子序列的思想
public class Solution {
public boolean isContains (TreeNode p, TreeNode q) {
if (q==null) return true;
if (p==null) return false;
if (p.val==q.val) return isContains(p.left, q.left) && isContains(p.right, q.right);
return isContains(p.left, q) || isContains(p.right, q);
}
} 102. 树的直径
思路： 记录最大与次大即可
class Solution {
public:
int ans = INT_MIN;
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
vector<vector<pair<int,int>> > g(n);
for(int i = 0; i < Tree_edge.size(); i++){
auto e = Tree_edge[i];
g[e.start].push_back(make_pair(e.end, Edge_value[i]));
g[e.end].push_back(make_pair(e.start, Edge_value[i]));
}
int pre = -1, cur = 0;
dfs(g, pre, cur);
return ans;
}
int dfs(vector<vector<pair<int,int>> >& g, int pre, int cur){
int d1 = 0, d2 = 0;//d1保最大值，d2保存次大值
for(int i = 0; i < g[cur].size(); i++){
int node = g[cur][i].first;//当前节点相连接的下一个节点
if(node != pre){//判断当前的节点不是和它相连接的上一个节点
int d = dfs(g, cur, node) + g[cur][i].second;
if(d > d1){
d2 = d1;
d1 = d;
}else if(d > d2){
d2 = d;
}
}
}
ans = max(ans, d1 + d2);//保存当前遍历过的元素的最大路径
return d1;
}
}; 103. 二叉搜索树的第k个结点
思路： 非递归模拟计算机压栈退栈
class Solution:
def KthNode(self, root, k):
ans,p,st=None,root,[]
while st or p:
if p:
st.append(p)
p=p.left
else:
p=st.pop()
if k-1==0: return p
k-=1
p=p.right
return None 104. 输出二叉树的右视图
思路： 构造二叉树，然后优先遍历右子树，在遍历左子树
import collections
class Solution:
def solve(self, pre, inn):
def dfs(pL, pR, iL, iR, pre, inn):
if pL>pR: return None
rp=mp[pre[pL]]
lsz=rp-iL
root=TreeNode(pre[pL])
root.left=dfs(pL+1,pL+lsz,iL,rp-1,pre,inn)
root.right=dfs(pL+lsz+1,pR,rp+1,iR,pre,inn)
return root
n,mp=len(pre),collections.defaultdict(int)
for i in range(n): mp[inn[i]]=i
root=dfs(0,n-1,0,n-1,pre,inn)
def get(root,ans,d):
if not root: return
if d==len(ans): ans.append(root.val)
get(root.right,ans,d+1)
get(root.left,ans,d+1)
ans=[]
get(root,ans,0)
return ans 105. 在二叉树中找到两个节点的最近公共祖先
思路： 遍历q及其父节点，如果list的父节点中含有，则返回，即为最近的共同祖先
import java.util.*;
public class Solution {
HashMap<Integer,Integer> mp = new HashMap<>();
public int lowestCommonAncestor (TreeNode root, int p, int q) {
if(root.val==p||root.val==q) return root.val;
ArrayList<Integer> list = new ArrayList<>();
dfs(root);
list.add(p);
while(mp.get(p)!=null){
list.add(mp.get(p));
p = mp.get(p);
}
if(list.contains(q)) return q;
//遍历q的祖先，找出最近的公共祖先
while(mp.get(q)!=null){
q = mp.get(q);
if(list.contains(q)) return q;
}
return -1;
}
void dfs(TreeNode root){
if(root.left!=null){
mp.put(root.left.val,root.val);
dfs(root.left);
}
if(root.right!=null){
mp.put(root.right.val,root.val);
dfs(root.right);
}
}
} 106. 找到搜索二叉树中两个错误的节点
思路： 中序遍历+用pre记录当前结点的前一个结点，两个结点交换了会发生什么？第一个降序结构的第一个结点是err[0]，最后一个降序结构的第一个结点是err[1]
class Solution {
public:
vector<int> findError(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* pre=NULL;
int u=-1,v;
while (!st.empty() || root!=NULL) {
if (root!=NULL) {
st.push(root);
root=root->left;
} else {
root=st.top(); st.pop();
if (pre!=NULL && pre->val>root->val) {
if (u==-1) u=pre->val;
v=root->val;
}
pre=root;
root=root->right;
}
}
return {v,u};
}
}; 107. 两数之和
思路： 直接map记录数字的位置
import collections
class Solution:
def twoSum(self , A , tar ):
n=len(A)
mp=collections.defaultdict(int)
for i in range(n):
if mp.get(tar-A[i]): return [mp[tar-A[i]], i+1]
mp[A[i]]=i+1
return [] 108. 未排序数组中累加和为给定值的最长子数组长度
思路： mp记录前缀和的位置，前缀和0的位置默认为0（特殊处理）
import collections
class Solution:
def maxlenEqualK(self , A , k ):
n,s,ans=len(A),0,0
mp={0:-1}
for i in range(n):
s+=A[i]
if s-k in mp:
ans=max(ans, i-mp[s-k])
if s not in mp:
mp[s]=i
return ans 109. 出现次数的TopK问题
思路： 先对数组排序，在用map统计频次，over
import collections
class Solution:
def topKstrings(self , A , k ):
A.sort()
cnt=collections.defaultdict(int)
for s in A:
cnt[s]+=1
list=sorted(cnt.items(), key=lambda x:x[1], reverse=True)
return [[str(list[i][0]), str(list[i][1])] for i in range(k)] 110. 找到字符串的最长无重复字符子串
思路： 字典记录每个数字出现的位置，双指针做即可
class Solution:
def maxLength(self , A ):
my_dict = {}
left, right = 0, 0
n,ans = len(A), float('-inf')
while right<=n-1:
if not A[right] in my_dict:
my_dict[A[right]] = right
right += 1
else:
ans = max(ans, right - left)
for i in range(left, my_dict[A[right]]):
my_dict.pop(A[i])
left = my_dict[A[right]]+1
my_dict[A[right]] = right
right += 1
ans = max(ans, right - left)
return ans 111. 数独
思路： 简单回溯，能否填数字即可
class Solution:
def solveSudoku(self , g ):
num_set = set([str(i) for i in range(1,10)])
v_set = [set() for i in range(9)]
h_set = [set() for i in range(9)]
s_set = [set() for i in range(9)]
def get_part(x,y):
return x//3*3+y//3
def set_num(x,y,num):
v_set[x].add(num)
h_set[y].add(num)
s_set[x//3*3+y//3].add(num)
g[x][y] = num
def remove_num(x,y,num):
v_set[x].remove(num)
h_set[y].remove(num)
s_set[x//3*3+y//3].remove(num)
g[x][y] = "."
for i in range(9):
for j in range(9):
if g[i][j]!=".":
v_set[i].add(g[i][j])
h_set[j].add(g[i][j])
s_set[i//3*3+j//3].add(g[i][j])
def is_valid(x,y,num):
if num not in v_set[x] and num not in h_set[y] and num not in s_set[x//3*3+y//3]:
return True
return False
def backtrack(x,y):
if x>8:
return True
if y>8:
return backtrack(x+1,0)
if g[x][y]!=".":
return backtrack(x,y+1)
for i in range(1,10):
str_i = str(i)
if is_valid(x,y,str_i):
set_num(x,y,str_i)
if backtrack(x,y+1):
return True
remove_num(x,y,str_i)
return False
backtrack(0,0)
return g 112. 随时找到数据流的中位数（*）
113. 跳台阶
思路： 简单递推
class Solution:
def jumpFloor(self, n):
f=[0]*(int(1e5+5))
f[0]=f[1]=1
for i in range(2,n+1):
f[i]=f[i-1]+f[i-2]
return f[n] 114. 拼接所有的字符串产生字典序最小的字符串
思路： a<b，则有：a+b<b+a
class Solution {
public:
string minString(vector<string>& A) {
string ans;
sort(A.begin(), A.end(), [&](const string& a, const string& b) {
return a+b<b+a;
});
for (string& s : A) ans+=s;
return ans;
}
}; 115. 丢棋子问题（*）
思路：
116. 二叉搜索树与双向链表
思路： 记录当前结点的前驱结点
class Solution:
forword,head=None,None
def Convert(self , root ):
def dfs(root):
if not root: return
dfs(root.left)
if not self.head:
self.forword=root
self.head=root
else:
self.forword.right=root
root.left=self.forword
self.forword=root
dfs(root.right)
dfs(root)
return self.head 117. 顺时针旋转矩阵
class Rotate:
def rotateMatrix(self, g, n):
ans=[[0]*n for i in range(n)]
for i in range(n):
for j in range(n):
ans[j][n-i-1]=g[i][j]
return ans 118. 螺旋矩阵
思路： 不断换方向即可，简单模拟
class Solution:
def spiralOrder(self , matrix ):
res = [];
if (len(matrix) == 0 or len(matrix[0]) == 0):
return res;
rowBegin = 0;
rowEnd = len(matrix) - 1;
colBegin = 0;
colEnd = len(matrix[0]) - 1;
while (rowBegin <= rowEnd and colBegin <= colEnd) :
# Traverse Right
for j in range(colBegin, colEnd+1, 1):
res.append(matrix[rowBegin][j]);
rowBegin += 1
# Traverse Down
for j in range(rowBegin, rowEnd+1, 1):
res.append(matrix[j][colEnd]);
colEnd -= 1
if (rowBegin > rowEnd or colBegin > colEnd) :
break;
# Traverse Left
for j in range(colEnd, colBegin-1, -1):
res.append(matrix[rowEnd][j]);
rowEnd -= 1
# Traverse Up
for j in range(rowEnd, rowBegin-1, -1):
res.append(matrix[j][colBegin]);
colBegin += 1
return res; 119. 合并区间
思路： 先按start升序排序，然后如果有重叠，则判断是两个区间合起来后包含还是扩展，没有重叠直接加到ans即可
class Solution:
def merge(self , A ):
n,ans=len(A),[]
A.sort(key=lambda x : x.start)
for e in A:
if ans and ans[-1].end>=e.start:
ans[-1].end=max(ans[-1].end, e.end)
else:
ans.append(e)
return ans 120. N皇后问题
import java.util.*;
public class Solution {
private int count = 0;
public int Nqueen(int n) {
if (n < 1) return 0;
dfs(0,0,0,0,n);
return count;
}
private void dfs(int row, int col, int pie, int na,int n) {
if (row >= n) {
count++;
return;
}
int bit = (~(col | pie | na))
& ((1<<n) - 1); // 去掉所有高位
while (bit > 0) {
int p = bit & -bit;
dfs(row + 1,col | p,(pie | p ) << 1,(na | p) >> 1,n);
bit &= (bit - 1);
}
}
} 121. 数组中未出现的最小正整数
思路： ans记录最小正数，set记录整数的出现，只要是连续的，就记录下来
import collections
class Solution:
def minNumberdisappered(self, A):
ans=1
st=collections.defaultdict(bool)
for x in A:
st[x]=1
while (st.get(ans,False)): ans+=1
return ans 122. 数组中未出现的最小正整数
思路： 作差法（前提是要保证A加上这个缺失的数字是连续数组）
class Solution:
def minNumberdisappered(self, A):
s1=s2=0
mi,mx=float('inf'),-float('inf')
for x in A:
mi=min(mi,x)
mx=max(mx,x)
s1+=x
for i in range(mi,mx+1):
s2+=i
ans=mx+1 if s1==s2 else s2-s1 #没有/有缺失的正数
return max(1,ans) 123. 回文数字
思路： 从低位开始取即可
import sys
class Solution:
def isPalindrome(self, x: int) -> bool:
t,v,inf=x,0,sys.maxsize
if x<0: return False
while x:
dig=x%10
v=v*10+dig
x=x//10
if v>inf: v=inf
return t==v 124. 扑克牌顺子
思路： 从数组中的最小值开始，检查是否可以用有限的0代替缺失的数字，如果能，返回true；当然，一种特殊情况
class Solution:
def IsContinuous(self, A):
if not A: return False
n,cnt,mp=len(A),[0],[False]*50
mi,mx=float('inf'),-float('inf')
for x in A:
if x==0:
cnt[x]+=1
else:
mp[x]=True
mi=min(mi,x)
mx=max(mx,x)
l=0
for i in range(mi,mx+1):
if mp[i]:
l+=1
else:
if cnt[0]>0:
cnt[0]-=1
l+=1
else:
return False
if l<n:
while cnt[0]>0:
l+=1
cnt[0]-=1
return l==n 125. 斐波那契数列
思路： 简单递推
class Solution:
def Fibonacci(self, n):
if not n: return 0
a,b,c=0,1,1
for i in range(n-2):
a=b
b=c
c=a+b
return c 126. 单链表的排序
思路：先存储后到列表中，链接成链表
class Solution:
def sortInList(self , head ):
A=[]
ans,t=ListNode(-1),head
while t:
A.appe***al)
t=t.next
A.sort()
cur=ListNode(A[0])
ans.next=cur
for i in range(1,len(A)):
nxt=ListNode(A[i])
cur.next=nxt
cur=nxt
return ans.next 126. 括号生成
思路：先放左括号，再放右括号
class Solution:
def generateParenthesis(self , n ):
def dfs(l,r,s,A):
if l==0 and r==0:
A.append(s)
return
if l>0: dfs(l-1,r,s+'(',A)
if l<r: dfs(l,r-1,s+')',A)
A=[]
dfs(n,n,'',A)
return A 127. 调整数组顺序使奇数位于偶数前面
思路：开两个数组，分别存储偶数和奇数
class Solution:
def reOrderArray(self , A ):
oi,ei,loi,lei,n=-1,-1,-1,-1,len(A)
B,C=[],[]
for i in range(n):
if A[i]&1: B.append(A[i])
else: C.append(A[i])
B+=C
return B 128. 字符串变形
思路：翻转单词即可
class Transform:
def trans(self, s, n):
ans=''
for c in s:
if c==' ': ans+=c
elif c.isupper(): ans+=c.lower()
else: ans+=c.upper()
A=ans.split(' ')
return ' '.join(A[::-1]) 129. 将字符串转化为整数
思路：注意细节即可
class Solution:
def atoi(self , str ):
min_int = -(1<<31)
max_int = (1<<31)-1
str = str.strip()
if str == '': return 0
sign = 1
if str[0] == '-':
sign = -1
str = str[1: len(str)]
elif str[0] == '+':
str = str[1: len(str)]
length, end = len(str), len(str)
for i in range(length):
if str[i]>='0' and str[i]<='9': continue
else:
end = i
break
str = str[0: end]
if str == '': return 0
else:
ans = sign*int(str)
if ans < min_int:
ans = min_int
if ans > max_int:
ans = max_int
return ans 130. 比较版本号
思路：遇到数字则累加，两个指针遇到.时则比较数字大小
class Solution:
def compare(self , s: str, t: str):
i,j,n,m=0,0,len(s),len(t)
a=b=0
while i<n and j<m:
if s[i].isdigit():
a=a*10+int(s[i])
i+=1
if t[j].isdigit():
b=b*10+int(t[j])
j+=1
if i<n and j<m and s[i]=='.' and t[j]=='.':
if a<b: return -1
elif a>b: return 1
a=b=0
i,j=i+1,j+1
if n-i==m-j: return 0
return -1 if n-i<m-j else 1 131. 设计LRU缓存结构
思路：模拟即可，代码有点多
class Solution {
public:
vector<int>ans;
vector<int> LRU(vector<vector<int> >& operators, int k) {
vector<int> r;
vector<int> key;
for(int i = 0; i < operators.size(); i++){
if(operators[i][0] == 1){
set(operators[i][1], operators[i][2], r, key, k);
}
if(operators[i][0] == 2){
get(operators[i][1], r, key);
}
}
return ans;
}
void set(int a, int b, vector<int> &r, vector<int> &key, int k){
if(r.size() < k){
key.push_back(a);
r.push_back(b);
}
else{
key.erase(key.begin());
r.erase(r.begin());
key.push_back(a);
r.push_back(b);
}
}
void get(int a, vector<int> &r, vector<int> &key){
int t = -1;
for(int i = 0; i < key.size(); i++){
if(a == key[i]){
t = i;
break;
}
}
if(t == -1){
ans.push_back(-1);
}
else{
int t1, t2;
t1 = key[t];
t2 = r[t];
key.erase(key.begin() + t);
r.erase(r.begin() + t);
key.push_back(t1);
r.push_back(t2);
ans.push_back(t2);
}
}
}; 132. 判断回文
思路：双指针遍历判断即可
class Solution:
def judge(self , s ):
l,r=0,len(s)-1
while l<r:
if s[l]!=s[r]: return False
l,r=l+1,r-1
return True 132. 旋转字符串
思路：枚举每一种情况即可
class Solution:
def solve(self , A , B ):
n=len(A)
for i in range(1,n):
fir,sec=A[0:i],A[i:]
t=sec+fir
if t==B: return True
return False 133. 旋转数组
思路：模拟即可
class Solution {
public:
vector<int> solve(int n, int m, vector<int>& a) {
vector<int> d;
int finished = 0, count = a.size();
for (int i=0; i < count; ++i) {
if (finished >= count)
break;
int begin = i;
int cur = i;
int tmp = a[cur];
int prev = prev_index(cur, m, n);
while (begin != prev) {
d.push_back(cur);
d.push_back(prev);
d.push_back(0);
finished++;
a[cur] = a[prev];
cur = prev;
prev = get(cur, m, n);
}
finished++;
d.push_back(cur);
d.push_back(tmp);
d.push_back(0);
a[cur] = tmp;
}
for (auto& i : a) d.push_back(i);
return a;
}
int get(int i, int len, int count) {
i -= len;
while (i < 0) i += count;
return i;
}
}; 134. 验证IP地址
思路：模拟即可
class Solution:
def solve(self , s ):
def isIPV4(A):
for s in A:
if s.startswith("0") or len(s)>3 or int(s)>255: return False
return True
def isIPV6(A):
for s in A:
if len(s)>4: return False
return True
A=s.split(".")
B=s.split(":")
if not isIPV4(A) and not isIPV6(B): return "Neither"
return "IPv4" if isIPV4(A) else "IPv6" 135. 数组中的逆序对
思路：双指针模拟即可
class Solution:
ans,mod=0,int(1e9+7)
def InversePairs(self, A):
def merge_sort(l,r,A):
if l>=r: return
m=l+r>>1
merge_sort(l,m,A)
merge_sort(m+1,r,A)
i,j,B=l,m+1,[]
while i<=m and j<=r:
if A[i]<A[j]:
B.append(A[i])
i+=1
else:
B.append(A[j])
self.ans+=m-i+1
j+=1
while i<=m:
B.append(A[i])
i+=1
while j<=r:
B.append(A[j])
j+=1
i,j=l,0
while i<=r:
A[i]=B[j]
i,j=i+1,j+1
n=len(A)
merge_sort(0,n-1,A)
return self.ans%self.mod 136. 字典树的实现
思路：直接用列表实现
class Solution:
def trieU(self , operators ):
strs, result = [],[]
for i in range(len(operators)):
case = int(operators[i][0])
string = operators[i][1]
if case == 1:
self.add(strs, string)
elif case == 2:
self.delete(strs, string)
elif case == 3:
self.search(strs, string, result)
elif case == 4:
self.cnt(strs, string, result)
return result
def add(self, strs, string):
strs.append(string)
def delete(self, strs, string):
idx = strs.index(string)
del strs[idx]
def search(self, strs, string, result):
if string in strs:
result.append('YES')
else:
result.append('NO')
def cnt(self, strs, string, result):
count = 0
if len(strs) > 0:
for s in strs:
if s.startswith(string):
count += 1
result.append(str(count)) 137. 孩子们的游戏(圆圈中最后剩下的数)
思路：m模拟即可
class Solution:
def LastRemaining_Solution(self, n, m):
i,A=0,list(range(n))
while len(A)>1:
i=(i+m-1)%len(A)
A.pop(i)
return -1 if len(A)==0 else A[0] 138. 环形链表的约瑟夫问题
思路：模拟即可
class Solution {
public:
int dfs(int n, int m) {
if (n==1) return 0;
int j=dfs(n-1,m);
return (j+m)%n;
}
int ysf(int n, int m) {
return dfs(n,m)+1;
}
}; 139. 矩阵最长递增路径
思路：f用局部变量可以过，用全局变量不可以过
const int N=2005, dir[4][2] = { {1,0},{0,-1},{0,1},{-1,0} };
class Solution {
public:
int n,m,ans=1;
int dfs(int x, int y, vector<vector<int>>& f, vector<vector<int> >& g) {
if (f[x][y]) return f[x][y];
int mx=1;
for (auto& d : dir) {
int tx=x+d[0], ty=y+d[1];
if (tx>=0 && tx<n && ty>=0 && ty<m && g[tx][ty]>g[x][y])
mx=max(mx,dfs(tx,ty,f,g)+1);
}
return f[x][y]=mx;
}
int solve(vector<vector<int>>& g) {
if (g.empty() || g[0].empty()) return 0;
n=g.size(), m=g[0].size();
vector<vector<int>> f(m, vector<int>(n, 0));
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
ans=max(ans,dfs(i,j,f,g));
return ans;
}
}; 140. 矩阵乘法
思路：线性代数知识，你不会就是不会
class Solution {
public:
vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
int n=a.size();
vector<vector<int>> c(n,vector<int>(n,0));
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
for (int k=0; k<n; k++) {
c[i][j]+=a[i][k]*b[k][j];
}
return c;
}
}; 141. 最长重复子串
思路：枚举长度+合法性检测
class Solution {
public:
bool valid(int l, int len, string& s) {
for (int i=l; i<l+len; i++) if (s[i]!=s[i+len])
return false;
return true;
}
int solve(string& s) {
int n=s.size();
for (int len=n/2; len>0; len--) {
for (int i=0; i<=n-2*len; i++) {
if (valid(i,len,s))
return 2*len;
}
}
return -1;
}
}; 142. 随时找到数据流的中位数
思路：两个堆
class Solution {
public:
priority_queue<int, vector<int>, greater<int>> minQ;
priority_queue<int> maxQ;
void addNum(int x) {
maxQ.push(x);
minQ.push(maxQ.top()), maxQ.pop();
if (minQ.size()>maxQ.size()+1)
maxQ.push(minQ.top()), minQ.pop();
}
double findMedian() {
if (minQ.empty()) return -1;
return minQ.size()!=maxQ.si***Q.top() : (minQ.top()+maxQ.top())*0.5;
}
vector<double> flowmedian(vector<vector<int> >& ops) {
vector<double> ans;
for (auto& op : ops) {
if (op[0]==1) {
addNum(op[1]);
} else { //查询
ans.push_back(findMedian());
}
}
return ans;
}
}; 143. 划分链表
思路：双指针+细节，因为最后如果b的next不为空的话，将会导致循环引用
class Solution:
def partition(self , head , x ):
dead1,dead2=ListNode(0),ListNode(0)
a, b=dead1, dead2 #a是小于x的结点，b是所有大于等于x的结点
while (head):
if (head.val < x):
a.next=head
a=a.next
else:
b.next=head
b=b.next
head=head.next
a.next=dead2.next
b.next=None
return dead1.next 144. LFU缓存结构设计
思路：map+双向链表
import java.util.*;
public class Solution {
public class LFUCache {
private class Node {
int k;
int v;
int count;
public Node(int k, int v) {
this.k = k;
this.v = v;
count = 1;
}
}
private int size;
private int maxSize;
private Map<Integer, Node> key2node;
private Map<Integer, LinkedList<Node>> count2list;
public LFUCache(int maxSize) {
this.maxSize = maxSize;
size = 0;
key2node = new HashMap<>();
count2list = new HashMap<>();
}
public void set(int k, int v) {
if (key2node.containsKey(k)) {
key2node.get(k).v = v;
get(k);
return;
}
Node node = new Node(k, v);
if (!count2list.containsKey(node.count)) count2list.put(node.count, new LinkedList<>());
LinkedList<Node> list = count2list.get(node.count);
list.addFirst(node);
key2node.put(k, node);
size++;
if (size > maxSize) {
key2node.remove(list.getLast().k);
list.removeLast();
size--;
}
}
public int get(int k) {
if (!key2node.containsKey(k)) return -1;
Node node = key2node.get(k);
LinkedList<Node> oldList = count2list.get(node.count);
oldList.remove(node);
if (oldList.isEmpty()) count2list.remove(node.count);
node.count++;
if (!count2list.containsKey(node.count)) count2list.put(node.count, new LinkedList<>());
LinkedList<Node> list = count2list.get(node.count);
list.addFirst(node);
return node.v;
}
}
public int[] LFU(int[][] operators, int k) {
LFUCache cache = new LFUCache(k);
List<Integer> list = new ArrayList<>();
for (int[] e : operators) {
if (e[0] == 1) cache.set(e[1], e[2]);
else list.add(cache.get(e[1]));
}
int[] res = new int[list.size()];
for (int i = 0; i < res.length; i++) res[i] = list.get(i);
return res;
}
} 145. 丢棋子问题
思路：动态规划题，dp[i][j]为i个棋子下j次能够辨别的最大n值
class Solution {
public:
int solve(int n, int k) {
if(n < 1) return 0;
if(k == 1)return n;
int t = log2(n) + 1;
if( k >= t)
return t;
vector<int>f(k+1,0);
int cnt=0;
while(f[k] < n) {
++cnt;
for(int i = k;i > 0;--i)
f[i] += f[i-1] + 1;
}
return cnt;
}
}; 
我现在也只有一个保底
太难了
