面试涉及到的一些算法题

发表于 | 分类于

数组a,先单调递增再单调递减，输出数组中不同元素个数。要求：O(1)空间复杂度，不能改变原数组

我的思路的话就是从两头往中间走，i = 0，j = len-1，比较两个数，保证大的那个数不动小的数往中间走，每次比较看数值是否相等，如果相等 i++，j–，否则根据两个值大小确定是 i++ 还是 j–。

House Robber 打家劫舍

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

1
2
3
4
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

维护一个一位数组 dp，其中 dp[i] 表示 [0, i] 区间可以抢夺的最大值，对当前i来说，有抢和不抢两种互斥的选择，不抢即为 dp[i-1]（等价于去掉 nums[i] 只抢 [0, i-1] 区间最大值），抢即为 dp[i-2] + nums[i]（等价于去掉 nums[i-1]）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int rob(vector<int> &num) {
        if (num.size() <= 1) return num.empty() ? 0 : num[0];
        vector<int> dp = {num[0], max(num[0], num[1])};
        for (int i = 2; i < num.size(); ++i) {
            dp.push_back(max(num[i] + dp[i - 2], dp[i - 1]));
        }
        return dp.back();
    }
};

拓扑排序

有向无环图该序列必须满足下面两个条件每个顶点出现且只出现一次。若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。当然有向无环图（DAG）才有拓扑排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>

#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const int maxn=100005;
int n,m;
int a,b;
vector<int>v[maxn];
int indrgee[maxn];
int order[maxn];
queue<int>q;

void toposort()
{
    for(int i=1;i<=n;i++)//找到初始情况下入度为0的点
    {
        if(indrgee[i]==0)
            q.push(i);
    }
    int cnt=0;
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        order[cnt++]=temp;
        int len=v[temp].size();
        for(int i=0;i<len;i++)
        {
            indrgee[v[temp][i]]--;
//每次删去该顶点和所有以它为起点的有向边故对应点的入度减一，如果为0，就放入队列
            if(indrgee[v[temp][i]]==0)
                q.push(v[temp][i]);
        }
    }
    printf("%d",order[0]);
    for(int i=1;i<cnt;i++)
        printf(" %d",order[i]);
    printf("\n");
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)
            break;
        while(!q.empty())
            q.pop();
        for(int i=0;i<=n;i++)
        {
            v[i].clear();
            indrgee[i]=0;
        }
        while(m--)
        {
            scanf("%d %d",&a,&b);
            v[a].push_back(b);
            indrgee[b]++;//对应的入度加1.
        }
        toposort();
    }
    return 0;
}

有多个集合，有交集的就合并，输出合并后的结果。

思路很简单，就是对于多个集合进行排序，x 相同 y 小的放前面，否则 x 小的放前面。

然后一遍遍历，我维护当前集合的最右边的值 tempy，如果 tempy 大于下一个集合的初始点的值说明这两个集合有交集，更新 tempy 的值，否则更新 tempy 值为下一个集合的最右边的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 10005;
struct Node {
    int x, y;
};
Node node[maxn];
vector<Node>v;
bool cmp(Node a, Node b) {
    if (a.x == b.x) {
        return a.y < b.y;
    }
    else {
        return a.x < b.x;
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &node[i].x, &node[i].y);
    }
    sort(node, node + n, cmp);
    for (int i = 0; i < n; i++) {
        printf("%d %d\n", node[i].x, node[i].y);
    }
    int tempx = node[0].x;
    int tempy = node[0].y;
    for (int i = 1; i < n; i++) {
        if (tempy > node[i].x) {
            tempy = node[i].y;
            continue;
        }
        else {
            Node temp;
            temp.x = tempx;
            temp.y = tempy;
            v.push_back(temp);
            tempx = node[i].x;
            tempy = node[i].y;
        }
    }
    Node temp;
    temp.x = tempx;
    temp.y = tempy;
    v.push_back(temp);
    int len = v.size();
    for (int i = 0; i < len; i++) {
        printf("%d %d\n", v[i].x, v[i].y);
    }
}

给一个词典的集合，一组不重复字母，问这些字母可以组成几个词语

先 Hash 一下字母，然后遍历和这个词典的集合，对于每个词语去 Hash 里面查一下，都有就能组成。

时间复杂度是O(集合的词语的长度之和)

有序的数组中找到某一目标值首次出现的下标

给定一个升序的数组，这个数组中可能含有相同的元素，并且给定一个目标值。要求找出目标值在数组中首次出现的下标。
思想：题目给出有序数组，应该想到利用二分查找来做。找到左邻居，使其值加一。利用二分查找，算法复杂度为O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
using namespace std;
int findsearch(int *p, int length, int target)
{
    int left = 0;
    int right = length-1 ;
    if (p[right - 1] < target&&length<0&&p==NULL)
        return - 1;
    while (left < right)
    {
        int mid = (left + right) / 2;
        if (p[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    if (p[left] == target)
        return left;
    else
        return -1;
}
int main()
{
    int p[] = { 4,6,6,6,6 };
    int length = 5;
    int target =6;
    int index = findsearch(p, length, target);
    cout << index << endl;
}

找到有序数组中某一目标值在数组中的开始下标以及终止下标以及目标值出现的次数，也是同样的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
//查找指定数字在有序数组中出现的次数，isLeft标记最左和最右
int FindCntofNum(int a[], int len, int num, bool isLeft)
{
    int left = 0, right = len - 1;
    int pos, mid;
    while (left <= right)//二分查找
    {
        mid = (left + right) / 2;
        if (a[mid] < num)
            left = mid + 1;
        else if (a[mid] > num)
            right = mid - 1;
        else
        {
            pos = mid;
            if (isLeft)//查找最左值
                right = mid - 1;
            else//查找最右值
                left = mid + 1;
        }
    }
    return pos;//返回最终查找到的位置
}
int main()
{
    int a[7] = { 1, 2, 3, 4, 4, 5 ,6};
    int left, right, dst;
    left = FindCntofNum(a, 7, 4, true);
    right = FindCntofNum(a, 7, 4, false);
    dst = right - left + 1;
    cout<< dst<<endl;
    return 0;
}

判断回文字符串

将这串数字逆序，然后判断逆序后的数字是否和正序后的数字完全一样，如果完全一样，就是回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool palindrome(char *s)
{
	int n=strlen(s);
	int i, j,count=0;
	for (i = 0, j = n - 1; i < n, j >= 0; i++, j--)
	{
		if (*(s + i) == *(s + j))
		{
			count++;
		}
	}
	if (count == n)
		return true;
}

判断一个链表是不是回文数

使用 2 个指针，快慢指针各一个，每次慢指针移动一个，快指针移动两个。

当快指针不为 NULL 时候，将慢指针 push 到栈中。

当快指针等于 NULL 时候，说明链表前半部分已经被压入栈中。

每次栈 Top 元素与当前慢指针元素比较，如果不相等则返回 false。如果相等，则栈 Pop，慢指针 ++。

链表奇数或者偶数节点需要判断（如果为奇数那么就删除最后的栈顶）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//判断单链表是不是回文链表
bool isPalindrome(LinkedList *head)
{
    stack<int> sk;
    LinkedList *fast = head->next;
    LinkedList *slow = head->next;
    int flag = 0;
    while(fast !=NULL){
        sk.push(slow->data);
        slow = slow->next;
        fast = fast->next;
        if(fast != NULL){
            fast = fast->next;
        }else{
            flag = 1;
        }
    }
    if(flag == 1){
        sk.pop();
    }
    while(!sk.empty()){
        if(sk.top() == slow->data){
            sk.pop();
            slow = slow->next;
        }
        else
            return false;
    }
    return true;
}

最长回文序列

回文子序列，因为是不连续的肯定是不能直接枚举，那么利用动态规划

我们知道对于任意字符串，如果头尾字符相同，那么字符串的最长子序列等于去掉首尾的字符串的最长子序列加上首尾；如果首尾字符不同，则最长子序列等于去掉头的字符串的最长子序列和去掉尾的字符串的最长子序列的较大者。那么转移方程：

dp[i][j]=dp[i+1][j-1] + 2 if（s[i] == s[j]）

dp[i][j]=max(dp[i+1][j],dp[i][j-1]) if （s[i] != s[j]）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=1005;
char s[maxn];
int dp[maxn][maxn];
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    for(int i=len-1;i>=0;i--)
    {
        dp[i][i]=1;
        for(int j=i+1;j<=len;j++)
        {
            if(s[i]==s[j])
                dp[i][j]=dp[i+1][j-1]+2;
            else
                dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
        }
    }
    printf("%d\n",dp[0][len-1]);
    return 0;
}

最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
string longestPalindrome(string s)
{
    if (s.empty()) return "";
    int len = s.size();
    if (len == 1)return s;
    int longest = 1;
    int start=0;
    vector<vector<int> > dp(len,vector<int>(len));
    for (int i = 0; i < len; i++)
    {
        dp[i][i] = 1;
        if(i<len-1)
        {
            if (s[i] == s[i + 1])
            {
                dp[i][i + 1] = 1;
                start=i;
                longest=2;
            }
        }
    }
    for (int l = 3; l <= len; l++)//子串长度
    {
        for (int i = 0; i+l-1 < len; i++)//枚举子串的起始点
        {
            int j=l+i-1;//终点
            if (s[i] == s[j] && dp[i+1][j-1]==1)
            {
                dp[i][j] = 1;
                start=i;
                longest = l;
            }
        }
    }
    return s.substr(start,longest);
}

二叉树的遍历

先序遍历

根节点—>左子树—>右字树

递归遍历

1
2
3
4
5
6
7
8
void PreOrder(Tnode*  root)
{
    if(root==NULL)
        return ;
    cout<<root->val<<endl;
    Preorder(root->lchild);
    Preorder(root->rchild);
}

非递归遍历

先序遍历时，每当我们压入一个结点，我们压入结点前对其进行访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void PreOrder(Tnode *root)
{
    if(root==NULL)
        return ;
    stack<Tnode *>s;
    Tnode *now=root;
    while(!s.empty() || now)
    {
        while(now)
        {
            cout<<now->val<<"->";
            s.push(now);
            now=now->lchild;
        }
        now=s.top();
        s.pop();
        now=now->rchild;　　
    }
    cout<<endl;
}

中序遍历

左子树—>根节点—>右字树

递归遍历

1
2
3
4
5
6
7
8
void InOrder(Tnode*  root)
{
    if(root==NULL)
        return ;
    Preorder(root->lchild);
    cout<<root->val<<endl;
    Preorder(root->rchild);
}

非递归遍历

中序时我们需要在遍历完左子树后访问根节点，再去遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InOrder(Tnode *root)
{
    if(root==NULL)
        return ;
    stack<Tnode *>s;
    Tnode *now=root;
    while(!s.empty() || now)
    {
        while(now)
        {
            s.push(now);
            now=now->lchild;
        }
        now=s.top();
        cout<<now->val<<"->";
        s.pop();
        now=now->rchild;　　
    }
    cout<<endl;
}

后序遍历

左子树—>右字树—>根节点

递归遍历

1
2
3
4
5
6
7
8
void PostOrder(Tnode*  root)
{
    if(root==NULL)
        return ;
    Preorder(root->lchild);
    Preorder(root->rchild);
    cout<<root->val<<endl;
}

非递归遍历

后序遍历时由于访问完左右子树后才能访问根结点，因此需要将根结点在栈内保留到左右子树被访问后，但同时会出现一个问题，当右子树弹出后遇到根结点又会将右子树结点压入栈中，造成死循环，因此我们需要在定义一个变量last代表最后一个访问的结点，当last与栈顶结点的右子树结点相同时，则不再将右子树结点压入栈中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void PostOrder(Tnode *root)
{
    if(root==NULL)
        return ;
    stack<Tnode *>s;
    Tnode *now=root;
    Tnode *last=NULL;
    while(!s.empty() || now)
    {
        while(now)
        {
            s.push(now);
            now=now->lchild;
        }
        now=s.top();
        if(now->rchild && last!=now->rchild)
            now=now->rchild;
        else if(now->rchild ==NULL || last ==now->rchild)
        {
            cout<<<now->val<<"->";
            last=now;
            s.pop();
            now=NULL;
        }
    }
}

给定中序和前序求层序或者后序

不管是求层序还是后序，主要过程都是一样的都是建树。

首先我们在上面介绍了前序，中序，后序遍历的特性。所以我们基本的思路就是先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。给个例子介绍一下：

前序遍历：GDAFEMHZ

中序遍历：ADEFGHMZ

画树求法：

  • 根据前序遍历的特点，我们知道根结点为G
  • 观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。
  • 观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。
  • 同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int maxn=50;
int n,m,s,d;
int a[maxn],b[maxn];
struct Node
{
    int l,r;
}node[maxn];
int buildtree(int la,int ra,int lb,int rb)
{
    if(la>ra)
        return 0;
    int root=b[lb];
    int len1,len2;
    len1=la;
    while(a[len1]!=root)
        len1++;
    len2=len1-la;
    node[root].l=buildtree(la,len1-1,lb+1,lb+len2);
    node[root].r=buildtree(len1+1,ra,lb+len2+1,rb);
    return root;
}
void bfs(int root)
{
    queue<int>q;
    vector<int>v;
    q.push(root);
    while(!q.empty())
    {
        int w=q.front();
        q.pop();
        if(w==0)
            break;
        v.push_back(w);
        if(node[w].l!=0)
            q.push(node[w].l);
        if(node[w].r!=0)
            q.push(node[w].r);
    }
    int len=v.size();
    for(int i=0;i<len;i++)
        printf("%d%c",v[i],i==len-1?'\n':' ');
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&b[i]);
    buildtree(0,n-1,0,n-1);
    int root=b[0];
    bfs(root);
    return 0;
}

给定二叉树，给出S型打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void S_LevelOrderPrint(TreeNode t)
{
    stack<TreeNode> s1;
    stack<TreeNode> s2;
    s1.push(t);
    while(!s1.empty() || !s2.empty())
    {
        if(!s1.empty())
        {
            while(!s1.empty())
            {
                TreeNode tn = s1.top();
                cout<<tn.val<<"";
                s1.pop();
                if(tn.right != null)
                    s2.push(tn.right);
                if(tn.left != null)
                    s2.push(tn.left);
            }
        }
        else
        {
            while(!s2.empty())
            {
                TreeNode tn = s2.top();
                cout<<tn.val<<" ";
                s2.pop();
                if(tn.left != null)
                    s1.push(tn.left);
                if(tn.right != null)
                    s1.push(tn.right);
            }
        }
    }
}

N 阶乘末尾0的个数。

要判断末尾有几个0就是判断可以整除几次10。10的因子有5和2，而在0~9之间5的倍数只有一个，2的倍数相对较多，所以本题也就转换成了求N阶乘中有几个5的倍数。
也就是每多出来一个5，阶乘末尾就会多出来一个0，这样n / 5就能统计完第一层5的个数，依次处理，就能统计出来所有5的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int count = 0;
    while(n) {
        n /= 5;     //算出当前数字中可以匹配5（5和5的倍数）的个数
        count += n; //累加之
    }
    cout<<count;
    return 0;
}

给定数组，从数组中取出n个不复用的数的和为sum

深搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void findd(vector<int>&vr,int pos,int sum,int m,int& res){
    if(sum==m){
        res++;
        return;
    }
    else if(sum>m){
        return;
    }else{
        if(pos<vr.size()){
            sum+=vr[pos];
            findd(vr,pos+1,sum,m,res);
            sum-=vr[pos];
            findd(vr,pos+1,sum,m,res);
        }
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main(){
    int n=0;
    int m=0;
    while(cin>>n>>m){
        vector<int> vr(n);
        for(int i=0;i<n;++i){
            cin>>vr[i];
        }
        sort(vr.begin(),vr.end(),greater<int>());
        vector<vector<long long int>>dp(n,vector<long long int>(m+1,0));
        for(int i=0;i<n;++i){
            dp[i][0]=1;
        }
        for(int i=1;i<=m;i++){
            if(vr[0]>m)//过滤
                break;
            if(vr[0]==i)
                dp[0][i]=1;
            else
                dp[0][i]=0;
        }
        for(int i=1;i<n;++i){
            if(vr[i]>m)  //过滤
                continue;
            for(int j=1;j<=m;++j){
                if(j-vr[i]>=0)
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-vr[i]];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[n-1][m]<<endl;
    }
    return 0;
}

求一个无序数组的中位数

利用快排的思想。任意挑一个元素，以该元素为支点，划分集合为两部分，如果左侧集合长度恰为 (n-1)/2，那么支点恰为中位数。如果左侧长度 <(n-1)/2, 那么中位点在右侧，反之，中位数在左侧。 进入相应的一侧继续寻找中位点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//快排方法，分治思想
int PartSort(int arr[], int left,int right)
{
    int key = arr[right];
    while (left < right)
    {
        //key右边，先从左找比key值大
        while (left < right && arr[left] <= key)
            ++left;
        if (left < right)
        {
            arr[right] = arr[left];
            --right;
        }
        //从右找比key小
        while (left < right && arr[right] >= key)
            --right;
        if (left < right)
        {
            arr[left] = arr[right];
            ++left;
        }           
    }
    arr[left] = key;
    return left;
}
void GetMid3(int arr[],int size)
{
    int left = 0;
    int right = size - 1;
    int mid = size / 2;
    int div = PartSort(arr, left, right);
    while (div != mid)
    {
        if (div < mid)//右半区间
            div = PartSort(arr, div + 1, right);
        else 
            div = PartSort(arr, left, div - 1);
    }
    cout << "中位数" << arr[div] << endl;
}

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=1000005;
int n,m;
int a[maxn];
void perm(int s,int e)
{
    if(s==e)
    {
        for(int i=0;i<=e;i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    else
    {
        for(int i=s;i<=e;i++)
        {
            swap(a[i],a[s]);
            perm(s+1,e);
            swap(a[i],a[s]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    perm(0,n-1);
    return 0;
}

36进制加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package collection;

public class Main {

    private static final String chars = "0123456789abcdefghijklmnopqrstuvwxyz";

    public static void main(String[] args) {
        System.out.println(add_36("1b", "10"));
    }
    public static String add_36(String a, String b) {
        int alength = a.length();
        int blength = b.length();
        int m = Math.max(alength, blength);
        int inc = 0;
        int clength = chars.length();
        String result = "";
        for (int i = 0; i < m; i++) {
            int ia = i < alength ? chars.indexOf(a.charAt(alength - i - 1)) : 0;
            int ib = i < blength ? chars.indexOf(b.charAt(blength - i - 1)) : 0;
            int add = ia + ib + inc;
            if (add > clength) {
                inc = add / clength;
            }
            result = chars.charAt(add % clength) + result;
        }
        if (inc > 0) {
            result = chars.charAt(inc) + result;
        }
        return result;
    }
}

n条直线最多把平面分割成几部分?

n条直线最多把平面分成An部分，于是A0=1 A1=2 A2=4

对于已经有n条直线 将平面分成了最多的An块

那么加一条直线 他最多与前n条直线有n个交点 于是被它穿过的区域都被一分为二 那么增加的区域数就是穿过的区域

数 也就是这条直线自身被分成的段数 就是n+1 故 A(n+1) = A(n)+n+1

An = n+(n-1)+...+2+A1 = n(n+1)/2 +1

n条折线分割平面

根据直线分平面可知，由交点决定了射线和线段的条数，进而决定了新增的区域数。当n-1条折线时，区域数为f（n-1）。为了使增加的区域最多，则折线的两边的线段要和n-1条折线的边，即2*（n-1）条线段相交。那么新增的线段数为4*（n-1），射线数为2。但要注意的是，折线本身相邻的两线段只能增加一个区域。

1
2
3
4
5
6
f(n)=f(n-1)+4(n-1)+2-1
=f(n-1)+4(n-1)+1
=f(n-2)+4(n-2)+4(n-1)+2
……
=f(1)+4+4*2+……+4(n-1)+(n-1)   
=2n^2-n+1

n个平面分割空间

n个平面最多把空间分成bn个部分

于是b0=1 b1=2 b2=4

对于已经有n个平面 将空间分成了最多的bn块

那么加入一个平面 它最多与每个平面相交 在它的上面就会得到至多n条交线

同时被它穿过的空间区域也被它一分为二 那么增加的区域数仍旧是它穿过的区域数 也就是这个平面自身被直线分割成的块数 就是an于是b(n+1)=bn+an

1
2
3
4
5
6
bn=a(n-1)+b(n-1)=...=a(n-1)+a(n-2)+...+a1+b1
=(n-1)n/2 +(n-2)(n-1)/2+...+1*(1+1)/2+n+2
=求和[1方到(n-1)方]/2 + 求和[1到(n-1)]/2 +n+1
=n(n-1)(2n-1)/12 +n(n-1)/4 +n+1
=n(n+1)(n-1)/6 +n+1
=(n^3+5n+6)/6

数组中唯一出现过一次的数

利用异或的特性：x ^ y ^ x = y ^ x ^ x = y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int len=15;
int a[7]={2,4,3,3,2,5,5};
int main()
{
    int ans=a[0];
    for(int i=1;i<7;i++)
    {
        ans^=a[i];
    }
    printf("%d\n",ans);
    return 0;
}

一个数组里除了一个数字之外，其他数字出现了n次

我们把这个数分解成二进制，计算出每一位出现1的个数，我们知道如果多次出现的话，1的个数是能够整除这个n，如果发现这个n不能够被 整除的时候，我们就知道那个唯一的数字转换为二进制的时候在这一位上会分解到，我们把这个再转换为十进制的数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int len=15;
int a[7]={2,3,3,3,4,4,4};
int b[32];
int main()
{
    for(int i=0;i<=6;i++)
    {
        for(int j=0;j<32;j++)
        {
            b[j]+=((a[i]>>j)&1);
        }
    }
    int ans=0;
    for(int i=0;i<32;i++)
    {
        if(b[i]%3!=0)
        {
            ans+=(1<<i);
        }
    }
    printf("%d\n",ans);
    return 0;
}

找1到n中缺失的数字

数组有序

直接二分时间复杂度为O(logN)。如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，这意味着这个中间的数字正好是第一个值和下标不相等的元素，它的下标就是在数组中不存在的数字；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标不相等，这意味着下一轮查找我们只需要在左半边查找即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
int getLoseNum(int a[], int left, int right)
{
    int mid;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(a[mid] == mid + 2) //缺失的数据在后半部分
            right = mid - 1;
        else if(a[mid] == mid + 1)  //缺失的数据在前半部分
            left = mid + 1;
    }
    return left + 1;
}

数组无序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*利用异或运算， 
任何数异或自己都等于0，x^x=0，任何数异或0都等于他自己x^0=x； 
假如缺的为3。result = 1^2^4^5^N 
第二次异或后 result = 1^2^4^5^N ^1^2^3^4^5^N = 0^3 = 3 
时间复杂度：O(n) 空间复杂度：O(1) 
异或方法，n：最大元素的值*/
int getLose(int a[], int n)
{
    int t = 0;
    for(int i =1; i<=n; i++)
        t = t ^ i;
    //最大值为n，缺失一个元素，则元素个数为n-2
    for(int i=0; i<n-1; i++)
        t = t ^ a[i];
    return t;
}
/*用1+2+…+n减去当前输入数据的总和，则所得的差就是缺失的那个数。 
时间复杂度：O(n) 空间复杂度：O(1)
*/
//n：最大元素的值而不是元素的个数
int getNum(int a[], int n)
{
    int sum = n*(n+1)/2;
    int t;
    for(int i=0; i<n-1; i++)
    {
        sum = sum - a[i];
    }
    return sum;
}
/*对输入数据进行Hash，然后从头到尾遍历一次。时间复杂度O(n) 空间复杂度O(n) */
int getMiss(int a[], int max)
{
    //hash表的长度比max大1
    int *tmp = new int[max+1];
    //数组的值从1开始，因此hash表的0位不用
    for(int i=1; i<=max; i++)
        tmp[i] = 0;
    //对数组遍历，缺失一个数，数组的长度为max-2
    for(int i=0; i<max-1; i++)
    {
        tmp[a[i]]++;
    }
    for(int i=1; i<=max; i++)
        if(tmp[i] == 0)
            return i;
}

找1到n中缺失的两个数字

也是采用异或。假设，缺失的数为s1和s2。则s1^s2=1^2^3.....^n^a[0]^a[1]^....a[n-3]。这个式子一目了然，无需多解释。

问题是如何通过这个式子求出s1与s2的值。只要能求出一个值，比如说s1，则s2=s1^(s1^s2)。

s1^s2的值必然不为0，则必然存在一位，s1与s2在此对应位不同。我们就可以按照此对应位是0或者1，将1-n分为两堆，将a[0]-a[n-3]分为两堆。将该为为1的两堆数相异或就能求出缺失的一个数。

举个例子。1-7中缺失3,4。转化为二进制位：011和100。三位都不同，我们用最后一位来判别，将1-n和数组非为两堆。则结果为：

标志位(最后一位） 1 0
1-n 1、3、5、7 2、4、6
a[0]-a[n-3] 1、5、7 2、6

用标志位为1的数进行异或

1^3^5^7^1^5^7=3。这样就求出了一个缺失数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void find_missing_number2 (int a[], int size, int& miss1, int& miss2)
{
    miss1 = 0;
    miss2 = 0;
    int number=0;
    for (int i=0;i<size;i++)
        number ^= ((i+1)^a[i]);
    number ^= (size+1);
    number ^= (size+2);    
    int k = number - (number&(number-1));
    for (int i=0;i<size;i++) {
        if ( (i+1)&k )
            miss1 ^= (i+1);
        if ( a[i]&k )
            miss1 ^= a[i];
    }
    if ( (size+1) & k )
        miss1 ^= size+1;
    if ( (size+2) & k )
        miss1 ^= size+2;
    miss2 = number ^ miss1;
}

下一个最大数系列

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

在遍历数组的过程中，如果是往后遇到大的数，那就是第一个更大的数，如果一直遇到不断小的数，才会一直找不到，我们可以用一个栈来记录，遇到比栈顶小的数字就放入栈中，遇到比栈顶大的数字就说明这是栈顶数字的下一个更大的数，就将其放在结果数组的对应位置上，栈顶的元素出栈，继续比较新的栈顶的数，如果还是大，那么继续记录，出栈，直到栈顶的数比新数要小，那么就可以将新数入栈了。因为我们要将找到的更大的数放在对应位置上，所以栈中记录的应该是元素位置，而不是具体的数字，但比较的时候还是比较原来的数组中这个位置的数字，此外，因为会出现循环寻找的情况，所以数组我们可能遍历两次。算法的时间复杂度是O(n)，空间复杂度也是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        const int N = nums.size();
        vector<int> res(N, -1);
        stack<int> stack;
        for (int i = 0; i < N * 2; i++) {
            while (!stack.empty() && nums[stack.top()] < nums[i % N]) {
                res[stack.top()] = nums[i % N];
                stack.pop();
            }
            if (i < N)
                stack.push(i);
        }
        return res;
    }
};

输入一个数组，代表每天的温度，求解每天需要经过几天会升温，即需找数组每个元素右边第一个比自己大的数。

利用单调栈性质创建单调递减栈，遍历数组入栈，当将要入栈元素小于栈顶元素时入栈，若要入栈元素大于栈顶元素时，表示入栈元素为所求元素，记录索引，弹出栈顶元素，将此元素压栈，重新比较，一次循环时间复杂度O(n)。

样例输入：[73, 74, 75, 71, 69, 72, 76, 73]

样例输出： [1, 1, 4, 2, 1, 1, 0, 0].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
样例解析：
73入栈，74>73，73出栈，74入栈，74使得73出栈，所以73需要等待1-0=1天 ，栈内元素74.
75入栈，75>74, 74出栈，75入栈，75使得74出栈，所以74需要等待2-1=1天，栈内元素75.
71入栈，71<75，直接入栈，栈内元素 75,71
69直接入栈，栈内元素75,71,69
72入栈，72>69,69出栈，72使69出栈，所以69需要等待5-4=1天，此时栈内元素75,71，由与72>71,任不满足单调栈性质，71出栈，72使71出栈，所以71需要等待5-3=2天，站内元素75,75>72,72直接入栈，栈内元素为：75,72.
*/
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> s = new Stack<Integer>();
        int[] res = new int[temperatures.length];
        for(int i=0;i<temperatures.length;i++){
        	if(s.isEmpty()||temperatures[i]<temperatures[s.peek()]){
        		s.push(i);
        	}
        	else {
        		while(!s.isEmpty()&&temperatures[s.peek()]<temperatures[i]){
        			int index = s.pop();
        			res[index] = i-index;
        		}
        		s.push(i);
        	} 
        }
        return res;
    }
}

链表中的下一个更大节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) 
    {
        vector<int> res;
        ListNode* p=head;
        while(p)
        {
            res.push_back(p->val);
            p=p->next;
        }
        int n=res.size();
        stack<int> tmp;
        vector<int> ans(n);
        for(int i=n-1;i>=0;i--)
        {
            while(!tmp.empty() && tmp.top()<=res[i])
            {
                tmp.pop();
            }
            if(!tmp.empty())
            {
                ans[i]=tmp.top();
            }
            else
            {
                ans[i]=0;
            }
            tmp.push(res[i]);
        }
        return ans;
    }
};

未排序的数组第 k 大的数

第一种解法，利用优先队列，维护一个 size == k 的优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) {
            /** priority_queue<int, vector<int>, less<int>> q; **/
            priority_queue<int, vector<int>> q;
            int len=nums.size();
            for(int val:nums){
                q.push(val);
            }
            while(q.size() > len-k+1){
                q.pop();
            }
            return q.top();
        }
};

第二种解法：利用快排的思想，就跟无序数组中找中位数一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int high = nums.size();
        int low = 0;
        while (low < high) {
            int i = low;
            int j = high-1;
            int pivot = nums[low];
            while (i <= j) {
                while (i <= j && nums[i] >= pivot)
                    i++;
                while (i <= j && nums[j] < pivot)
                    j--;
                if (i < j)
                    swap(nums[i++],nums[j--]);
            }
            swap(nums[low],nums[j]);

            if (j == k-1)
                return nums[j];
            else if (j < k-1)
                low = j+1;
            else
                high = j;
        }
    }
};

计算数字 n 有多少个二进制 1

利用 n&(n-1) 清除最右边的 1，记录 1 的个数就可以了。

因为从二进制的角度讲，n 相当于在 n - 1 的最低位加上 1。举个例子，8（1000）= 7（0111）+ 1（0001），所以 8 & 7 = （1000）&（0111）= 0（0000），清除了 8 最右边的 1（其实就是最高位的 1，因为 8 的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的 1（也就是最低位的 1）

1
2
3
4
5
6
7
8
9
int BitCount2(unsigned int n)
{
    unsigned int c =0 ;
    for (c =0; n; ++c)
    {
        n &= (n -1) ; // 清除最低位的1
    }
    return c ;
}

由上面的解法，我们可以判断一个数是 2 的幂数的最快方法是

1
2
3
4
5
6
7
if(n&(n-1)) 
	then n不是2的幂数;
else 
	n是2的幂数;
因为如果n=2^K,那么n = 1000...0(k个0）,则n-1 = 111...0(k个1);相与之后则为0

如果 n!=2^k，那么n跟（n-1)第一位都为1，则相与这后然后第一位为1，则不为0.

1-n 中有多少个二进制 1

我觉得 for 一遍循环，就很快了差不多 O(n) 的时间复杂度。

找出只由 a,b,c 组成的字符串中包含 abc 的个数

给个样例，abccc 可以找到 3 个 abc。

思路就是

一个数组中只有0,1,2三个元素，进行排序，要求时间复杂度为O(n)

设置三个标记指针，pos0，pos2，cur ，令 pos0 从前往后遍历，指向第一个非 0 的位置，pos2 从后往前遍历，指向第一个非 2 的位置
然后 cur 从 pos0 开始往后遍历：
遇到 0 就和pos0交换，pos0++;
遇到 1 什么也不做;
遇到 2 就和 pos2 交换，pos2 向前滑动到下一个非2的位置，交换后还要重新检查 cur 的值；
直到 cur 与 pos2 相遇。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
nt main(){ 
    int arr[14] = {0,1,2,1,2,0,2,0,1,2,2,2,1,2};
    int pos0=0, pos2=sizeof(arr)/4 -1, pcur=0;
    while(0 == arr[pos0])
        ++pos0;
    while(2 == arr[pos2])
        --pos2;
    pcur = pos0;
    while(pcur <= pos2){        
        if(0 == arr[pcur]){
            swap(arr[pcur], arr[pos0]);
            ++pos0;
        }
        else if(2 == arr[pcur]){            
            swap(arr[pcur], arr[pos2]);
            if(0 == arr[pcur]){//若交换之后，pcur当前指向的元素为0，则继续将pcur指向的元素和pos0指向的元素进行交换
                swap(arr[pcur], arr[pos0]); 
                ++pos0;//交换之后，将pos0向前移动一位
            }           
            --pos2;//pos2向后移动一位
            while(arr[pos2] == 2)//若移动之后指向的元素还是2，则继续向前移动，直到指向第一个非2的元素
                --pos2;
        }   
        ++pcur;//将pcur向前移动
    }   
    //将原数组打印出来
    for(int i =0;i < sizeof(arr)/4;++i)
        cout<<arr[i]<<"  ";
    cout<<endl;
    return 0;
}

输出一个递增排序数组的旋转数组中的最小元素 或者 下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int find_min_num(const int *arr, size_t n)
{
    int left = 0;
    int right = n-1;
    int mid = (right-left)/2;
    while(left < right)
    {   
        if((arr[left] <= arr[mid]) && (arr[mid] <= arr[right]))
        {
            break;//当数组区间为递增时，最小值就为最左值
        }
        else if((arr[mid-1] > arr[mid]) && (arr[mid+1] > arr[mid]))
        {
            return arr[mid];//当取到的中间值就为旋转点时，最小值就为中间值
        }
        else if((arr[left] <= arr[mid]) && (arr[mid] >= arr[right]))
        {
            left = mid + 1;//当中间值比左边大且比右边大时
        }
        else
        {
            right = mid - 1;//除去上面的三种情况就只剩一种了，那就是中间值比左线小且比右边小
        }

        mid = (right-left)/2 + left;
    }   
    return arr[left];
    // return left;
}

求二叉树中节点的差的最大值

其实就是求出二叉树中结点的最大值和最小值，相减就是结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef struct node{
int value;
	struct node *lchild;
	struct node *rchild;
}binarytree;
void preorder(binarytree *p, int &max, int &min)//先序遍历
{
	if (NULL==p)
		return;
	if(p->value>max)
		max=p->value;
	if(p->value<min)
		min=p->value;
	preorder(head->lchild, max, min);
	preorder(head->rchild, max, min);
	return;
}
int chazhi_max(binarytree *head)//返回最大差值
{
	if(NULL==head)
		return -1;
	int max, min;
	max = min = head->value;
	preorder(head, max, min);
	return max-min;
}

实现pow函数求x的y次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    //分治法：分而治之
    double pow(double x, int n) {
        if (n < 0)
            return 1.0/power(x, -n);
        else
            return power(x, n);
    }
    double power(double x, int n) {
        if (n == 0)
            return 1;
        double result = 0;
        double temp = pow(x, n/2);//递归的处理相乘的幂，重复利用已经的出来的值。
        if (n%2 == 1)
            result = x * temp * temp;//当幂为奇数的时候，多乘一个就变为偶数问题了。
        else
            result = temp * temp;//当幂为偶数的时候，
        return result;
    }
};

x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1
2
3
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 0, right = x;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x / mid >= mid) left = mid + 1;
            else right = mid;
        }
        return right - 1;
    }
};

二维坐标系，有一组点，若一个点的x y都小于某个点，那么这个点就包含它，它的价值是它包含的点的个数，求最大价值的点的价值？ (提示可以先排序)

一个模拟Windows窗体管理的类，(x1,y1)和(x2,y2)分别是窗体左上角和右下角像素点座标有很多个矩形，求覆盖的总面积

Java 判断字符串是否是网址

1
2
3
4
5
6
7
8
9
10
11
12
13
public static boolean isHttpUrl(String urls) {
    boolean isurl = false;
    String regex = "(((https|http)?://)?([a-z0-9]+[.])|(www.))"
            + "\\w+[.|\\/]([a-z0-9]{0,})?[[.]([a-z0-9]{0,})]+((/[\\S&&[^,;\u4E00-\u9FA5]]+)+)?([.][a-z0-9]{0,}+|/?)";//设置正则表达式

    Pattern pat = Pattern.compile(regex.trim());//比对
    Matcher mat = pat.matcher(urls.trim());
    isurl = mat.matches();//判断是否匹配
    if (isurl) {
        isurl = true;
    }
    return isurl;
}

3个线程顺序打印数字

问题：启动3个线程A、B、C，使A打印0，然后B打印1，然后C打印2，A打印3，B打印4，C打印5，依次类推。

思路：每个线程给定一个编号，每个线程判断当前是否已经轮到自己打印：如果没轮到，就wait等待；如果轮到，则打印当前数字，并唤醒其他线程。

判断是否已经轮到自己打印：

每个线程给定一个编号N，N从0开始；

使用一个全局变量记录当前需要打印的数字C，C从0开始，每次打印之后加1；

线程数量M；

判断逻辑：C%M ==N

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class PrintSequenceThread implements Runnable {
    private static final Object LOCK = new Object();
    /**
     * 当前即将打印的数字
     */
    private static int current = 0;
 
    /**
     * 当前线程编号，从0开始
     */
    private int threadNo;
    /**
     * 线程数量
     */
    private int threadCount;
 
    /**
     * 打印的最大数值
     */
    private int max;
 
    public PrintSequenceThread(int threadNo, int threadCount, int max) {
        this.threadNo = threadNo;
        this.threadCount = threadCount;
        this.max = max;
    }
 
    @Override
    public void run() {
        while(true) {
            synchronized (LOCK) {
                // 判断是否轮到当前线程执行
                while (current % threadCount != threadNo) {
                    if (current > max) {
                        break;
                    }
                    try {
                        // 如果不是，则当前线程进入wait
                        LOCK.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                // 最大值跳出循环
                if (current > max) {
                    break;
                }
                System.out.println("thread-" + threadNo + " : " + current);
                current++;
                // 唤醒其他wait线程
                LOCK.notifyAll();
            }
        }
    }
 
    public static void main(String[] args) {
        int threadCount = 3;
        int max = 10;
        for(int i=0;i<threadCount;i++) {
            new Thread(new PrintSequenceThread(i,threadCount, max)).start();
        }
    }
}

从左（右）边看二叉树

二叉树的层次遍历，每层按照从左向右的顺序依次访问节点（每一层取最（左）右边的节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> views;
        scan(root, 0, views);
        return views;
     }
private:
    void scan(TreeNode* root, int h, vector<int>& views)
    {
        if(!root)   return;
        if(h >= views.size())
            views.emplace_back(root->val);
        /* 先遍历右侧，这样就可以先选择右边的元素 */
        scan(root->right, h + 1, views);
        scan(root->left, h + 1, views);
    }
};
//  如果是左边的话就先遍历左边

给定一个数组，与数字m最接近的k个数

在排序数组中找最接近的K个数

Java List转Tree

细节实现看：

1
https://blog.csdn.net/MassiveStars/article/details/53911620

字符串排序，要求O(n)

我们知道字符 char 的范围是 -128-127，开一个 255 大小的数组排序。一次遍历字符串，对应的数组位置值 ++

然后一遍遍历输出即可。

不相邻和最大

对于一个给定的数组，在其中选取其子数组，要求相邻的元素不能选取，且要保证选出的子数组元素和最大。输入数组长度及其元素，输出所选子数组的和。

1
2
3
4
5
测试输入
7
4 2 6 1 3 5 8
测试输出
21

为了让子数组和最大，应该尽可能让它包含更多的元素，并且相邻元素不能选取，所以选取的任意两个数字之间最多间隔两个数，因为假设如果间隔了三个而子数组和最大，那么最中间的那个数一定可以选中，此时子数组和也一定比之前更大，产生矛盾。由此可见，本题只需要分析连续的三个元素的关系即可。
按照第 i 个元素是否被选取，前 i 个元素的和要么与前 i−1 个元素的和相同(不选取)，要么是前 i−2 个元素的和加上此第 i 个元素(选取)，这两种情况取最大。这很容易通过递归实现出来，也可以使用动态规划实现。要用动态规划，子问题的选取需要具有无后效性，即前 i 个元素的选取只能和之前的选取有关，和未来的情况无关。对于数组array[i]，i=0∼n−1，定义 s[i] 表示前 i 个元素的最大和，则递归式为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Scanner;

public class NotAdjacentLine {
    static int solution(int[] array, int n) {
        if (n < 1) return 0;
        if (n == 1) return array[0];
        return Math.max(solution(array, n - 1), 
                        solution(array, n - 2) + array[n - 1]);
    }

    static int solution2(int[] array, int n) {
        int[] s = new int[n + 1];
        s[0] = 0;
        s[1] = array[0];
        for (int i = 2; i < n + 1; i++) {
            int takei = s[i - 2] + array[i - 1];
            int skipi = s[i - 1];
            s[i] = Math.max(takei, skipi);
        }
        return s[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        System.out.println(solution2(array, n));
    }
}

那如果是在一个环上呢：看解析

一个环路加油站，是否能走一圈

城市的环形路有n个加油站，第i个加油站的油量用gas[i]来表示，你有如下的一辆车：

它的油缸是无限量的，初始是空的

它从第i个加油站到第i+1个加油站消耗油量为cost[i]

现在你可以从任意加油站开始，路过加油站可以不断的加油，问是否能够走完环形路。如果可以返回开始加油站的编号，如果不可以返回-1。

思路：假设起始的加油站是src，最后一个加油站是dst，在从src出发达到下一个加油站的油剩下sum。那么需要能够从src到dst中的每个点的油剩余量都有>=0。

假设从src出发，某点的油量sum<0，那么我们就从src-1站出发，此时达到这个“某点”的油量剩余就是sum += gas[src-1]-cost[src-1]，此时的dst将是src -1 再 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int src = 0;
        int dst = (src-1+gas.size())%gas.size();;
        int sum = 0;
        int i = src;
        while(i != dst +1){
            if(sum<0){
                src = (src-1+gas.size())%gas.size();
                dst = (src-1+gas.size())%gas.size();
                sum+=gas[src] - cost[src];
            }
            else {
                sum += gas[i] - cost[i];
                i++;
            }
        }
       
        if(sum>=0) return src;
        else return -1;
    }
};

堆的中位数算法

看解析

桌子上有一副牌，循环进行以下操作：（1）将顶部的牌放到桌上 （2）再将当前顶部的牌放入底部，循环到所有牌都放到桌上，假设最后放到桌子上的牌顺序是 13 12 11 …. 1，问初始的牌堆是怎么放的

找到数组中的两个数 A 和 B，要求将 A 和 B 交换之后自区间和是最大的，输出 A、B 和 最大自区间和

LeetCode 4 两个排序数组的中位数(数组、二分查找、分治法)

Leetcode 400 找到第 N 位

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

1
2
3
4
5
Input:
3

Output:
3

Example 2:

1
2
3
4
5
Input:
11

Output:
0

自然数序列看成一个长字符串，问我们第N位上的数字是什么。那么我们首先来分析自然数序列和其位数的关系，前九个数都是1位的，然后10到99总共90个数字都是两位的，100到999这900个数都是三位的，那么这就很有规律了，我们可以定义个变量cnt，初始化为9，然后每次循环扩大10倍，再用一个变量len记录当前循环区间数字的位数，另外再需要一个变量start用来记录当前循环区间的第一个数字，我们n每次循环都减去len*cnt (区间总位数)，当n落到某一个确定的区间里了，那么(n-1)/len就是目标数字在该区间里的坐标，加上start就是得到了目标数字，然后我们将目标数字start转为字符串，(n-1)%len就是所要求的目标位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findNthDigit(int n) {
        long long len = 1, cnt = 9, start = 1;
        // 找到n是几位数
        while (n > len * cnt) {
            n -= len * cnt;
            ++len;
            cnt *= 10;
            start *= 10;
        }
        // 找到n应该落在哪个自然数上
        start += (n - 1) / len;
        string t = to_string(start);
        // 求这个自然数会落在自然数的那一位上
        return t[(n - 1) % len] - '0';
    }
};

Reverse Nodes in k-Group 每k个一组翻转链表

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

1
2
3
4
5
6
7
Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

实际上是把原链表分成若干小段，然后分别对其进行翻转，那么肯定总共需要两个函数，一个是用来分段的，一个是用来翻转的。

pre 和 next 分别指向要翻转的链表的前后的位置，然后翻转后 pre 的位置更新到如下新的位置

以此类推，只要 cur 走过k个节点，那么 next 就是 cur->next，就可以调用翻转函数来进行局部翻转了，注意翻转之后新的 cur 和 pre 的位置都不同了，那么翻转之后，cur 应该更新为 pre->next，而如果不需要翻转的话，cur 更新为 cur->next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;
        ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = head;
        dummy->next = head;
        for (int i = 1; cur; ++i) {
            if (i % k == 0) {
                pre = reverseOneGroup(pre, cur->next);
                cur = pre->next;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
    ListNode* reverseOneGroup(ListNode* pre, ListNode* next) {
        ListNode *last = pre->next, *cur = last->next;
        while(cur != next) {
            last->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = last->next;
        }
        return last;
    }
};

矩阵中的最长递增路径

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

1
2
3
4
5
6
7
8
9
示例 1:
输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

引入动态规划思想，记忆化搜索，用一个数组 len[][] 记录任意点的递增路径长度，再利用一个 visited[][] 数组记录当前位置是否遍历过，如果已经处理过该点，那么直接返回该点对应的路径长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {

    private int[] row = {-1,1,0,0};
    private int[] col = {0,0,-1,1};

    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length ==0 || matrix[0].length == 0)
            return 0;
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        int[][] len = new int[matrix.length][matrix[0].length];
        int max = 0;

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                max = Math.max(max,find(matrix,visited,len,i,j));
            }
        }
        return max;
    }
    private int find(int[][] matrix,boolean[][] visited,int[][] len,int x,int y){
        if(visited[x][y])
            return len[x][y];
        len[x][y] = 1;
        for(int i=0;i<4;i++){
            int curX = x + row[i];
            int curY = y + col[i];
            if(curX >=0 && curX < matrix.length && curY >=0 && curY<matrix[0].length && matrix[curX][curY] < matrix[x][y]){
                len[x][y] = Math.max(len[x][y],find(matrix,visited,len,curX,curY)+1);
            }
        }
        visited[x][y] = true;
        return len[x][y];
    }
}

求数组中区间中最小数*区间所有数和的最大值

给定一段数组，求每个区间的最小值乘这段区间的和，输出每个区间得到的最大值。

1
2
3
4
5
6
7
8
样例输入：[1 2 6]，可能有以下几种情况：
[1]：结果为1*1=1；
[2]：结果为2*2=4；
[6]：结果为6*6=36；
[1,2]：结果为1*(1+2)=3;
[2,6]：结果为2*(2+6)=16;
[1,2,6]：结果为1*(1+2+6)=9;
最大值为36，输出36即可。

以数组中每一个值为最小值，假设这个最小值为num[k], 分别找到以该值num[k]为最小值，数组最左边的小于该值的下标i，和数组最右边的小于该值的下标j, 则区间num[i+1,j-1]为以num[k]为最小值所能达到的最大区间，则此区间能达到的最大值为 num[k]*Sum(i+1,j-1)，其中 Sum 函数为数组中区间[i+1,j+1]的所有数的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class test {
    public static int function(int[] arr) {
        int len = arr.length;
        int[] sum = new int[len];
        int ans = 0;
        for (int i = 0; i < len; i++) {
            //右边界
            sum[i] = arr[i];
            for (int j = i+1; j < len; j++) {
                if (arr[j] >= arr[i]) {
                    sum[i] += arr[j];
                } else {
                    break;
                }
            }
            //左边界
            for (int j = i-1; j >= 0;j--) {
                if (arr[j] >= arr[i]) {
                    sum[i] += arr[j];
                } else {
                    break;
                }
            }
            ans = Math.max(ans,sum[i]*arr[i]);
        }
        return ans;
    }
}

LeetCode 31. 下一个排列

实现获取下一个排列函数，这个算法需要将数字重新排列成字典序中数字更大的排列。

如果不存在更大的排列，则重新将数字排列成最小的排列（即升序排列）

以一个例子来分析，给定325421，求其下一个比它大的数，怎么办呢？我们应该从最低位开始，1->2->4->5,这一段是升序的，也就是5421已经是最大数，不存在比它大的组合，我们继续找，1->2->4->5->2，出现降序这个位置就是我们要找的关键点，只需要将2与其后的数字中的（1,2,4,5）比它大的最小数，也就4替换，然后再将后面的数（1,2,2,5）升序排列便可得到下一个数，过程为：325421->345221->345122

解法：从后往前遍历数组，找到当前节点右侧第一个比当前节点大的数，交换他们，然后使当前右侧有序即可。
假设数组nums长度为n（从0开始编号），数组中nums[i]到第nums[n-1]逆序（降序排列），且nums[i-1]<nums[i]，则下一个全排列时只需要考虑nums[i-1]到nums[n-1]即可，在i-1 右侧找到第一个大于nums[i-1] 的数，交换他们顺序，则后面升序排列就是最小的数，即下一个全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len=nums.size();
        for(int i=len-1;i>=0;i--){
            for(int j=len-1;j>i;j--){
                if(nums[i]<nums[j]){
                    swap(nums[i],nums[j]);
                    sort(nums.begin()+i+1,nums.end());
                    return ;
                }
            }
        }
        reverse(nums.begin(),nums.end());
    }
};

划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

1
2
3
4
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

先求出平均数avg，假如平均数avg不为整数，也就是说数组的数字总和不能平均的分为k份，那么直接返回false。

创建一个布尔数组flag，来记录nums数组中数字的状态（已用还是未用）， temp 初始为avg ，temp的作用为记录当前子集的数字总和，当temp等于0时，当前这个子集也就可以确定。index是用来记录遍历数组时从哪个位置开始遍历，以防将前面的数字重新计算。

当k个子集全部求解完，返回true，如果一直求解不出，则返回false。当temp = 0 的时候，也就是新一个子集求解完，那么继续求解下一个子集，k-1，temp重新置为avg；当temp ！= 0 时，就是子集还未求解完，那么继续求解子集，继续从数组中取数字，递归求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) 
            sum += nums[i];
        if(sum % k != 0 ) return false;
        int avg = sum / k;
        boolean[] flag = new boolean[len];
        return help(nums,flag,avg,k,avg,0);
    }
    public static boolean help(int[] nums, boolean[] flag, int avg, int k, int temp, int index ){

        if (k == 0 ) return true;
        if (temp == 0)
            return help(nums,flag,avg,k-1,avg,0);
        for (int i = index; i < nums.length; i++) {
            if (flag[i] == true) continue;
 
            flag[i] = true;
            if(temp-nums[i]>=0 && help(nums,flag,avg,k,temp-nums[i],index+1)){
                return true;
            }
            flag[i] = false;
        }
        return false;
    }
}