1. N 阶乘末尾0的个数。
输入为一行，n(1 ≤ n ≤ 1000)输出一个整数,即题目所求
解法：要判断末尾有几个0就是判断可以整除几次10。10的因子有5和2，而在0~9之间5的倍数只有一个，2的倍数相对较多，所以本题也就转换成了求N阶乘中有几个5的倍数。
也就是每多出来一个5，阶乘末尾就会多出来一个0，这样n / 5就能统计完第一层5的个数，依次处理，就能统计出来所有5的个数。同一个思想两种写法。public class Main {
public int calcuZero(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int cur = i;
//如果因数中有一个5那么乘积中就会有一个0，所以计算每一个i中因数5的个数
while (cur % 5 == 0) {
count++;
cur /= 5;
}
}
return count;
}
public static void main(String[] args) {
System.out.println(new Main().calcuZero(30));
}
}
#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;
}
2. 判断一颗二叉树是否为镜像对称
解法：判断一个数是否为镜像对称：先判断根，在判断左右子树。如果左右子树都为空那就是，如果左右子树不是同时为空那就不是
当左右子树都存在的时候，判断他们的值是否相等,如果相等那么久递归的对他们的字节点判断（左边的左=右边的右；左边的右==右边的左）
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if (!root)
return true;
return Symmetric(root->left, root->right);
}
bool Symmetric(TreeNode *left, TreeNode *right){
if (!left && !right)
return true;
if (!left || !right)
return false;
if (left->val == right->val){
return (Symmetric(left->left, right->right) && Symmetric(right->left, left->right));
}
return false;
}
};
3. 给定数组，从数组中取出n个不复用的数的和为sum
深搜，
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
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;
}
4. 给定一个二叉树和其中一个节点，如何找出中序遍历顺序的下一个节点？树中的节点除了有两个分别指向左右子节点的指针以外，还有一个指向父节点的指针.
解法：如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。
如果没有右子树，且它是父节点的左子节点，那么它的下一个节点就是它的父节点。
如果一个节点即没有右子树，并且它还是父节点的右子节点，这种情况比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的下一个节点。
如果一个节点不满足上述所有情况，那么它应该就是中序遍历的最后一个节点。所以返回NULL
struct BinaryTreeNode {
int val;
BinaryTreeNode* parent;
BinaryTreeNode* left;
BinaryTreeNode* right;
};
BinaryTreeNode* GetNext(BinaryTreeNode* root) {
if (root == NULL) return NULL;
BinaryTreeNode* next_node = NULL;
//如果节点有右子树，那么它的下一个节点就是它的右子树中最左边的节点
if (root->right != NULL) {
next_node = root->right;
while (next_node->left != NULL)
next_node = next_node->left;
return next_node;
}
if (root->parent != NULL) {
if (root == root->parent->left) {//当前节点是父节点的左子节点
return root->parent;
} else {
BinaryTreeNode* parent_node = root->parent;
BinaryTreeNode* current_node = root;
while (parent_node != NULL && current_node == parent_node->left) {
current_node = parent_node;
parent_node = parent_node->parent;
}
return parent_node;
}
}
return NULL;
}
5. 求一个无序数组的中位数
求一个无序数组的中位数。
如：{2,5,4,9,3,6,8,7,1}的中位数为5，{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。
解法：利用快排的思想。任意挑一个元素，以改元素为支点，划分集合为两部分，如果左侧集合长度恰为 (n-1)/2，那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧，反之，中位数在左侧。 进入相应的一侧继续寻找中位点。
//快排方法，分治思想
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;
}
6. 有序的数组中找到某一目标值首次出现的下标
给定一个升序的数组，这个数组中可能含有相同的元素，并且给定一个目标值。要求找出目标值在数组中首次出现的下标。
思想：题目给出有序数组，应该想到利用二分查找来做。找到左邻居，使其值加一。利用二分查找，算法复杂度为O(logn)
#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;
}
找到有序数组中某一目标值在数组中的开始下标以及终止下标以及目标值出现的次数。也可以用下面的方法：
#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;
}
7. 给两个链表，每个节点存储一个数字，实现两个节点之间的数字相加，返回相加后的数字链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode l3 = new ListNode(0);
ListNode res = l3;
int value = 0;
int flag = 0;
while (l1 != null || l2 != null || flag == 1) {
int sum = flag;
sum += (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0);
l1 = (l1 != null ? l1.next : null);
l2 = (l2 != null ? l2.next : null);
l3.next = new ListNode(sum % 10);
flag = sum / 10;
l3 = l3.next;
}
return res.next;
}
}
8. 全排列
#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;
}
9. 最大连续和
#include <iostream>
#include <cstdio>
using namespace std;
int a[9]={-2,1,-3,4,-1,2,1,-5,4};
int l,r;
int maxsum(int l,int r)
{
int ans;
if(r==l)
return a[l];
int mid=(l+r)/2;
ans=max(maxsum(l,mid),maxsum(mid+1,r));
int templ=a[mid],t=0;
for(int i=mid;i>=l;i--)
templ=max(templ,t+=a[i]);
int tempr=a[mid+1];t=0;
for(int i=mid+1;i<=r;i++)
tempr=max(tempr,t+=a[i]);
return max(ans,templ+tempr);
}
int main()
{
scanf("%d %d",&l,&r);
printf("%d\n",maxsum(l,r));
return 0;
}
原文：https://www.cnblogs.com/jkzr/p/10766945.html