全排列
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arrM = [NSMutableArray arrayWithObjects:@3,@2,@3, nil];
[self testFunc:arrM index:0 num:(int)arrM.count];
}
//数组全排列
- (void)testFunc:(NSMutableArray *)array index:(int)index num:(int)num{
if(index == num - 1){
NSLog(@"%@",array);
}else{
for (int i = index; i<num; i++) {
if([self needSwap:array index:i len:num]){//如果数组中没有重复数字这一步判断可以省略
//将第i个元素交换至当前index下标处
[array exchangeObjectAtIndex:index withObjectAtIndex:i];
//以递归的方式对剩下元素进行全排列
[self testFunc:array index:index +1 num:num];
//将第i个元素交换回原处
[array exchangeObjectAtIndex:index withObjectAtIndex:i];
}
}
}
}
//去重，防止数组中有重复数字
- (BOOL)needSwap:(NSMutableArray *)array index:(int)index len:(int)len{
for (int i = index +1; i<len; i++) {
if(array[index] == array[I]){
return NO;
}
}
return YES;
}
//给定正整数n,计算出n个元素的集合{1,2，....，n}能够划分为多少个不同的非空集合
int Func(int n,int m){
if(n<=2 || m==n || m==1){
return 1;
}else{
return Func(n-1,m-1) + m*Func(n-1,m)
}
}
//调用
int n;
int result;
for(int i = 1,i<n,i++){
result = result +Func(n,i);
}
重建二叉树
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
return root;
}
//前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
if(startPre>endPre||startIn>endIn)
return null;
TreeNode root=new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++)
if(in[i]==pre[startPre]){
root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
break;
}
return root;
}
}
快排
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view.
NSMutableArray *sortArray = [NSMutableArray arrayWithObjects:@2,@1,@3,@5,@2,@9, nil];
[self quickSortTest:sortArray leftIndex:0 rightIndex:sortArray.count-1];
NSLog(@"%@",sortArray);
}
- (void)quickSortTest:(NSMutableArray *)array leftIndex:(NSInteger)leftIndex rightIndex:(NSInteger)rightIndex{
if(leftIndex>=rightIndex){
return;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
NSInteger key = [array[leftIndex] integerValue];
while (i<j) {
while (i<j && key<=[array[j] integerValue]) {
j--;
}
if(i!=j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
}
while (i<j && key>=[array[i] integerValue]) {
I++;
}
if(i!=j){
[array exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
[self quickSortTest:array leftIndex:leftIndex rightIndex:i-1];
[self quickSortTest:array leftIndex:i+1 rightIndex:rightIndex];
}
链表反转
struct Node{
int data;
struct Node *next;
};
@interface ViewController ()
@end
@implementation ViewController
- (void)viewDidLoad {
[super viewDidLoad];
}
struct Node *reverseList(struct Node *head){
struct Node *p = head;
struct Node *newH = NULL;
while (p != NULL) {
struct Node *temp = p->next;
p->next = newH;
newH = p;
p = temp;
}
return newH;
}
有序链表的合并
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//递归
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
ListNode *mergeNode = NULL;
if (l1->val < l2->val) {
mergeNode = l1;
mergeNode->next = mergeTwoLists(l1->next, l2);
} else {
mergeNode = l2;
mergeNode->next = mergeTwoLists(l1, l2->next);
}
return mergeNode;
}
//循环
public class Solution {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(l1 != null&& l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else{
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
if(l1 != null) {
cur.next = l1;
}
if(l2 != null) {
cur.next = l2;
}
return dummy.next;
}
二叉树的反转
步骤简述为：
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
invertTree(root.left);
invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
字符串转数组
java
661615293221_.pic_hd.jpg
