编程题整理

1 最int 型数组,子数组的最大和

#get max array
#得到 最大 子数组
def getmaxarray(arraylist):
    
    currentsum = arraylist[1]
    currentsumlist = [arraylist[1]]
    maxsum = arraylist[1]
    maxsumlist = [arraylist[1]]

    for i in range(len(arraylist)):
        # 如果加入后面的数据大于当前的sum
        if( (currentsum +  arraylist[i]) >  currentsum):
            # 更新当前的currentsum 数据
            currentsum += arraylist[i]
            # 更新当前的currentsumlist 列表
            currentsumlist.append(arraylist[i])

            # 如果当前的sum 大于最大sum  更新最大sum
            if(currentsum >= maxsum):
                maxsum = currentsum
                maxsumlist = currentsumlist
        else:
            currentsum = arraylist[i]
            currentsumlist= []
            currentsumlist.append(arraylist[i])
            # 如果当前的sum 大于最大sum  更新最大sum
            if(currentsum >= maxsum):
                maxsum = currentsum
                maxsumlist = currentsumlist
    return maxsumlist


print(getmaxarray([-1,-3,-10,-5]))
print(getmaxarray([-1,-3,-0,-10,-5]))
print(getmaxarray([1,-3,0,10,-5]))
print(getmaxarray([1,3,0,10,5]))

 

最大连通区域

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;

const int maxn = 100 + 5;
int m, n, idx[maxn][maxn];
char pic[maxn][maxn];


void dfs(int i, int j, int count)
{
    if(i < 0 || i >=m || j < 0 || j >= n)  return;
    if(idx[i][j] > 0 || pic[i][j] != '@')   return;

    idx[i][j] = count;

    for(int dr = -1; dr < 2; dr++){
        for(int dc = -1; dc < 2; dc++){
            if(dr != 0 || dc != 0){
                dfs(i+dr, j+dc, count);
            }
        }
    }
}

int main()
{
    while(scanf("%d%d", &m, &n) == 2){
        for(int i = 0; i < m; i++){
            scanf("%s", pic[i]);
        }

        memset(idx, 0, sizeof(idx));
        int cnt = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(idx[i][j] == 0 && pic[i][j] == '@')  dfs(i, j, ++cnt);
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

 

最长回文判定

#求最长回文串类
class LPS:                    
    #初始化,需要提供一个字符串  
    def __init__(self,string):
        self.string = string
        self.lens = len(self.string)
    
    #暴力枚举:作为算法效率参照
    def brute_force(self):
        maxcount = 0
        for j in range(self.lens):                      
            for k in range(j,self.lens):
                count = 0
                l,m = j,k
                while m>=l:
                    if self.string[l]==self.string[m]:
                        l,m = l+1,m-1
                    else:
                        break
                if m<l:
                    count = k-j+1
                if count>maxcount :
                    maxcount = count
        return maxcount
    
    #优化版:枚举子串中心
    def brute_force_opti(self):
        maxcount = 0
        if self.lens == 1:                              #只有一个字符直接返回1
            return 1
        for j in range(self.lens-1):                    #枚举中心
            count,u = 1,j                                   
            if self.string[j]==self.string[j+1]:        #处理偶数子串,将两个相邻相同元素作为整体
                u,count= j+1,2
            for k in range(1,j+1):                      #两边扩展
                l,m = u+k,j-k
                if (m>=0)&(l<self.lens):
                    if(self.string[l]==self.string[m]):
                        count += 2
                    else:
                        break
            if count>maxcount :                         #更新回文子串最长长度
                maxcount = count
        return maxcount
        
    #manacher算法
    def manacher(self):
        s = '#'+'#'.join(self.string)+'#'               #字符串处理,用特殊字符隔离字符串,方便处理偶数子串
        lens = len(s)
        f = []                                          #辅助列表:f[i]表示i作中心的最长回文子串的长度
        maxj = 0                                        #记录对i右边影响最大的字符位置j
        maxl = 0                                        #记录j影响范围的右边界
        maxd = 0                                        #记录最长的回文子串长度
        for i in range(lens):                           #遍历字符串
            if maxl>i:                                  
                count = min(maxl-i,int(f[2*maxj-i]/2)+1)#这里为了方便后续计算使用count,其表示当前字符到其影响范围的右边界的距离
            else :                                      
                count = 1
            while i-count>=0 and i+count<lens and s[i-count]==s[i+count]:#两边扩展
                count +=1
            if(i-1+count)>maxl:                         #更新影响范围最大的字符j及其右边界
                    maxl,maxj = i-1+count,i                                                        
            f.append(count*2-1)
            maxd = max(maxd,f[i])                       #更新回文子串最长长度
        return int((maxd+1)/2)-1                        #去除特殊字符

 

 

树操作:

#-*-coding:utf-8-*-
'''
created by zwg in 2016-10-7
'''
import copy
class node:
    def __init__(self,name,data):
        self.data=data
        self.name=name
        self.Rchild=None
        self.Lchild=None
        self.child_number=0
        self.parent=None
    def add_Rchild(self,node):
        if self.Rchild is not None:
            self.Rchild=node
        else:
            self.Rchild=node
            self.child_number+=1
        node.set_parent(self)
    def drop_Rchild(self):
        self.Rchild=None
        self.child_number-=1
    def set_parent(self,node):
        self.parent=node
    def add_Lchild(self,node):
        if self.Lchild is not None:
            self.Lchild=node
        else:
            self.Lchild=node
            self.child_number+=1
        node.set_parent(self)
    def drop_Lchild(self):
        self.Lchild=None
        self.child_number-=1

class tree:
    def __init__(self,node):
        '''
        初始化
        可使用一个无子节点的作为树的根
        也可使用一个本身就包含了多层树结构的节点来构建树
        每个节点包含名称和数据两个主要属性,以及两个节点
        all_node为所用节点
        enable_node为可插节点
        '''
        self.parent=node
        self.depth=1
        self.all_node={node.name:node}
        self.enable_node={node.name:node}
        c1=node.Rchild
        c2=node.Lchild
        C=[c1,c2]
        B=[i for i in C if i is not None]
        if len(B)==2:
            del self.enable_node[node.name]
        while len(B)!=0:
            self.depth+=1
            C=copy.copy(B)
            for i in B:
                C.remove(i)
                self.all_node[i.name]=i
                if i.child_number!=2:
                    self.enable_node[i.name]=i
                if i.Rchild is not None:
                    C.append(i.Rchild)
                if i.Lchild is not None:
                    C.append(i.Lchild)
            B=copy.copy(C)
    def get_depth(self):
        '''
        计算树的深度
        '''
        depth=1
        node=self.parent
        c1=node.Rchild
        c2=node.Lchild
        C=[c1,c2]
        B=[i for i in C if i is not None]
        while len(B)!=0:
            depth+=1
            C=copy.copy(B)
            for i in B:
                C.remove(i)
                if i.Rchild is not None:
                    C.append(i.Rchild)
                if i.Lchild is not None:
                    C.append(i.Lchild)
            B=copy.copy(C)
        return depth
    def show(self):
        '''
        打印树结构
        '''
        a=[copy.deepcopy(self.parent)]
        n=copy.deepcopy(self.depth)
        m=copy.copy(n)
        print(self.parent.name.center(2**n*m))
        while n>=1:
            b=[]
            n-=1
            for i in a:
                if i is not None:
                    c1=i.Lchild
                    b.append(c1)
                    if c1 is not None:
                        print(c1.name.center(2**n*m))
                    else:
                        print (''.center(2**n*m))
                    c2=i.Rchild
                    b.append(c2)
                    if c2 is not None:
                        print(c2.name.center(2**n*m))
                    else:
                        print (''.center(2**n*m))
                else:
                    print (''.center(2**n*m))
                    print (''.center(2**n*m))
            a=copy.deepcopy(b)
        #del a,n,b
    def generate_childtree(self,child_name):
        '''
        选取child_name这个节点生成子树,
        子树的根节点为child_node
        '''
        child_node=self.all_node[child_name]
        child_tree=tree(child_node)
        return child_tree
    def add_child_tree(self,parent_name,child_tree,RL='right'):
        '''
        增加子树
        子树可以是单节点树,也可以是多层节点的树
        '''
        L1=child_tree.all_node
        L2=child_tree.enable_node
        L4=child_tree.parent
        parent_node=self.all_node[parent_name]
        if RL=='right':
            parent_node.add_Rchild(L4)
        if RL=='left':
            parent_node.add_Lchild(L4)
        for i in L1.keys():
            self.all_node[i]=L1[i]
        for i in L2.keys():
            self.enable_node[i]=L2[i]
        if parent_node.child_number==2:
            self.enable_node.pop(parent_node)
        self.depth=self.get_depth()
    def drop_child_tree(self,child_name):
        '''
        删除子树,child_name为删除的所在节点名
        该节点及其后面所有子节点一并删除
        '''
        child_node=self.all_node[child_name]
        child_tree=tree(child_node)
        L1=child_tree.all_node
        L2=child_tree.enable_node
        parent_node=child_node.parent
        if parent_node.Rchild==child_node:
            parent_node.drop_Rchild()
        else:
            parent_node.drop_Lchild()
        for i in L1.keys():
            self.all_node.pop(L1[i].name)
        for i in L2:
            self.enable_node.pop(L1[i].name)
        if not parent_node.name not in self.enable_node:
            self.enable_node[parent_node.name]=parent_node
        self.depth=self.get_depth()
        
        
            


if __name__=='__main__':
    a=node('a',1)
    a1=node('a1',2)
    a2=node('a2',2)
    a11=node('a11',3)
    a12=node('a12',3)
    a21=node('a21',3)
    a111=node('a111',4)
    a112=node('a112',4)
    a211=node('a211',4)
    a212=node('a212',4)
    a11.add_Lchild(a111)
    a11.add_Rchild(a112)
    a21.add_Lchild(a211)
    a21.add_Rchild(a212)
    a.add_Lchild(a1)
    a.add_Rchild(a2)
    a1.add_Rchild(a11)
    a1.add_Lchild(a12)
    a2.add_Rchild(a21)
    '''
    验证node的属性及方法是否正确
    print a.Lchild.name
    print a.Rchild.name
    print a.child_number
    print a.parent
    print a1.Rchild.name
    print a.Rchild.Rchild.name
    '''
    

    #生成node关于a的树,a有4层
    T=tree(a)
    print (T.depth)
    print (T.all_node.keys())
    print (T.enable_node.keys())
    #T.show()#打印树
    
    #生成node关于b的树,a有两层
    b=node('b',5);b1=node('b1',6);b2=node('b2',6)
    b.add_Lchild(b1);b.add_Rchild(b2)
    b_tree=tree(b)
    #b_tree.show()#打印树
    
    #生成树T的子树,以a1为节点,a1的深度为3
    t1=T.generate_childtree('a1')
    print (t1.depth)
    print (t1.all_node.keys())
    print (t1.enable_node.keys())
    #t1.show()#打印树
    
    
    #增加子树,在a111后面加上子树b_tree,这时树的高度为6
    T.add_child_tree('a111',b_tree,'left')
    print (T.depth)
    print (T.enable_node.keys())
    print (T.all_node.keys())
    #T.show()#打印树
    
    #删除以节点b开始的子树,还原为原来的样子
    T.drop_child_tree('b')
    print (T.depth)
    print (T.enable_node.keys())
    print (T.all_node.keys())
    #T.show()#打印树

 

 

二分查找

private static int binarySearch(int a[], int target) {
    if (a == null || a.length == 0) return -1;
    int left = 0, right = a.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

 

KMP

private static int[] getNext(char[] pattern) {
    int[] next = new int[pattern.length + 1];
    int i = 0, j = -1, len = pattern.length;
    next[0] = -1;
    while (i < len) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

private static int kmp(char[] text, char[] pattern) {
    if (text == null || text.length == 0
            || pattern == null || pattern.length == 0) return -1;
    int[] next = getNext(pattern);
    int i = 0, j = 0, len1 = text.length, len2 = pattern.length;
    while (i < len1 && j < len2) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        if (j == len2) {
            // 返回出现模式串位置
            return i - len2 + 1;
            // 统计出现的次数
            // j=next[j];
            // ans++;
        }
    }
    return -1;
}

 

堆排序

private static void swap(int a[], int x, int y) {
    int tmp = a[x];
    a[x] = a[y];
    a[y] = tmp;
}

private static void sift(int a[], int root, int hight) {
    if (root >= hight) return;
    int left = root * 2, right = left + 1;
    if (left < hight && a[root] < a[left]) {
        swap(a, root, left);
        sift(a, left, hight);
    }
    if (right < hight && a[root] < a[right]) {
        swap(a, root, right);
        sift(a, right, hight);
    }
}

private static void heapSort(int a[]) {
    if (a == null || a.length == 0) return;
    // init
    int b[] = new int[a.length + 1];
    for (int i = 1, len = b.length; i < len; i++) {
        b[i] = a[i - 1];
    }
    // build max heap
    for (int i = b.length / 2; i >= 1; i--) {
        sift(b, i, b.length);
    }
    // sort
    for (int i = 1, len = b.length; i < len; i++) {
        swap(b, 1, len - i);
        a[i-1] = b[len - i];
        sift(b, 1, len - i);
    }
}

 

快速排序

private static void swap(int a[], int x, int y) {
    int tmp = a[x];
    a[x] = a[y];
    a[y] = tmp;
}

private static void quickSort(int[] a) {
    if (a == null || a.length == 0) return;
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int left, int right) {
    if (left < right) {
        int i = left, j = right;
        int key = a[left];
        while (i < j) {
            while (i < j && a[j] >= key) {
                j--;
            }
            if (i < j) {
                swap(a, i, j);
                i++;
            }
            while (i < j && a[i] <= key) {
                i++;
            }
            if (i < j) {
                swap(a, i, j);
                j--;
            }
        }
        a[i] = key;
        quickSort(a, left, i - 1);
        quickSort(a, i + 1, right);
    }
}

private void quickSort(int a[]) {
    if (a == null || a.length == 0) return;
    quickSort(a, 0, a.length - 1);
}

快速排序非递归版

private static void swap(int a[], int x, int y) {
        int tmp = a[x];
        a[x] = a[y];
        a[y] = tmp;
    }

    private static int quickSort(int[] a, int left, int right) {
        int i = left, j = right;
        int key = a[left];
        while (i < j) {
            while (i < j && a[j] >= key) {
                j--;
            }
            if (i < j) {
                swap(a, i, j);
                i++;
            }
            while (i < j && a[i] <= key) {
                i++;
            }
            if (i < j) {
                swap(a, i, j);
                j--;
            }
        }
        a[i] = key;
        return i;
    }

    private static class Status {
        int left, right;

        public Status(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public int getLeft() {
            return left;
        }

        public int getRight() {
            return right;
        }
    }

    private static void quickSort(int a[]) {
        if (a == null || a.length == 0) return;
        Stack<Status> stack = new Stack<>();
        int left = 0, right = a.length - 1;
        stack.push(new Status(left, right));
        while (!stack.empty()) {
            Status currStatus = stack.pop();
            int partitionPos = -1;
            if (currStatus.getLeft() >= currStatus.getRight()) continue;
            partitionPos = quickSort(a, currStatus.getLeft(), currStatus.getRight());
            if (partitionPos == -1) continue;
            if (currStatus.getLeft() < partitionPos - 1) {
                stack.push(new Status(currStatus.getLeft(), partitionPos - 1));
            }
            if (partitionPos + 1 < currStatus.getRight()) {
                stack.push(new Status(partitionPos + 1, currStatus.getRight()));
            }
        }
    }

Dijkstra

private static int Dijkstra(int map[][], int start, int end) {
    if (map == null || map.length == 0 || map[0].length == 0) return -1;
    int dis[] = new int[map.length];
    boolean vis[] = new boolean[map.length];
    for (int i = 0, len = map.length; i < len; i++) {
        dis[i] = map[start][i];
        vis[i] = false;
    }
    for (int i = 0, len = map.length; i < len - 1; i++) {
        int minx = Integer.MAX_VALUE, k = -1;
        for (int j = 0; j < len; j++) {
            if (!vis[j] && dis[j] < minx) {
                minx = dis[j];
                k = j;
            }
        }
        if (k == -1) return -1;
        else {
            vis[k] = true;
            for (int j = 0; j < len; j++) {
                if (!vis[j] && dis[j] < dis[k] + map[k][j]) {
                    dis[j] = dis[k] + map[k][j];
                }
            }
        }
    }
    return dis[end] == Integer.MAX_VALUE ? -1 : dis[end];
}

 

Floyd

 private static int Floyd(int map[][], int start, int end) {
    if (map == null || map.length == 0 || map[0].length == 0) return -1;
    int dp[][] = new int[map.length][map[0].length];
    for (int i = 0, len = map.length; i < len; i++) {
        for (int j = i; j < len; j++) {
            dp[i][j] = map[i][j] == -1 ? Integer.MAX_VALUE : map[i][j];
        }
    }
    for (int k = 0, len = map.length; k < len; k++) {
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    return dp[start][end];
}

 

最长公共子序列

private static int LCS(String a, String b) {
    if (a == null || b == null || "".equals(a) || "".equals(b)) return -1;
    int dp[][] = new int[a.length()][b.length()];
    for (int i = 1, lena = a.length(); i <= lena; i++) {
        for (int j = 1, lenb = b.length(); j <= lenb; j++) {
            char cha = a.charAt(i - 1);
            char chb = b.charAt(j - 1);
            if (cha == chb) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[a.length()][b.length()];
}

 

最小编辑距离

private static int Levenshtein(String a, String b) {
        if (a == null || b == null || "".equals(a) || "".equals(b)) return -1;
        int dp[][] = new int[a.length()][b.length()];
        for (int i = 0, lena = a.length(); i < lena; i++) {
            dp[i][0] = i;
        }
        for (int i = 0, lenb = b.length(); i < lenb; i++) {
            dp[0][i] = i;
        }
        for (int i = 1, lena = a.length(); i <= lena; i++) {
            for (int j = 1, lenb = b.length(); j <= lenb; j++) {
                char cha = a.charAt(i - 1);
                char chb = b.charAt(j - 1);
                int cost = 1;
                if (cha == chb) {
                    cost = 0;
                }
                dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost);
            }
        }
        return dp[a.length()][b.length()];
    }

 

最长回文子串

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        boolean isPalindrome[][] = new boolean[n][n];
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            isPalindrome[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (j == i + 1) {
                    isPalindrome[i][j] = A.charAt(i) == A.charAt(j);
                } else {
                    isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && A.charAt(i) == A.charAt(j);
                }
                if (isPalindrome[i][j]) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
}

 

最长递增子序列

private static int solve(int a[]) {
        int dp[] = new int[a.length];
        for (int i = 0, len = a.length; i < len; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int ans = 0;
        for (int i = 0, len = a.length; i < len; i++) {
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }

 

最长公共子序列

public class LCS {
    public int findLCS(String A, int n, String B, int m) {
        // write code here
        int dp[][] = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
}

6、寻找迷宫的一条出路,o:通路; X:障碍。(大家经常谈到的一个小算法题)

#define MAX_SIZE  8
int H[4] = {0, 1, 0, -1};
int V[4] = {-1, 0, 1, 0};          
char Maze[MAX_SIZE][MAX_SIZE] = {{'X','X','X','X','X','X','X','X'},
                                 {'o','o','o','o','o','X','X','X'},
                                 {'X','o','X','X','o','o','o','X'},
                                 {'X','o','X','X','o','X','X','o'},
                                 {'X','o','X','X','X','X','X','X'},
{'X','o','X','X','o','o','o','X'},
                                 {'X','o','o','o','o','X','o','o'},
                                 {'X','X','X','X','X','X','X','X'}};
void FindPath(int X, int Y) {
    if(X == MAX_SIZE || Y == MAX_SIZE) {
         for(int i = 0; i < MAX_SIZE; i++)
for(int j = 0; j < MAX_SIZE; j++)
                  printf("%c%c", Maze[i][j], j < MAX_SIZE-1 ? ' ' : '/n');
}else for(int k = 0; k < 4; k++)
if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X < MAX_SIZE && 'o' == Maze[X][Y]) {
                  Maze[X][Y] = ' ';
                  FindPath(X+V[k], Y+H[k]);
                  Maze[X][Y] ='o';
}
}
int main(int argc, char* argv[]) {
    FindPath(1,0);
}

 

8、求网格中的黑点分布。现有6*7的网格,在某些格子中有黑点,已知各行与各列中有黑点的点数之和,请在这张网格中画出黑点的位置。(这是一网友提出的题目,说是他笔试时遇到算法题)

#define ROWS 6
#define COLS 7
int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0};           // 各行黑点数和的情况
int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1};        // 各列黑点数和的情况
int iCount, iFound;
int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS];
 
int Set(int iRowNo) {
if(iRowNo == ROWS) {
        for(int iColNo=0; iColNo < COLS && iSumC[iColNo]==iPointsC[iColNo]; iColNo++)
           if(iColNo == COLS-1) {
               printf("/nNo.%d:/n", ++iCount);
               for(int i=0; i < ROWS; i++)
                  for(int j=0; j < COLS; j++)
                      printf("%d%c", Grid[i][j], (j+1) % COLS ? ' ' : '/n');
               iFound = 1;  // iFound = 1,有解
           }
    } else {
        for(int iColNo=0; iColNo < COLS; iColNo++) {
            if(iPointsR[iRowNo] == 0) {
                Set(iRowNo + 1);
   } else if(Grid[iRowNo][iColNo]==0) {
Grid[iRowNo][iColNo] = 1;
iSumR[iRowNo]++; iSumC[iColNo]++;                                  if(iSumR[iRowNo]<iPointsR[iRowNo] && iSumC[iColNo]<=iPointsC[iColNo])
                     Set(iRowNo);
else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)
                     Set(iRowNo + 1);
                Grid[iRowNo][iColNo] = 0;
                iSumR[iRowNo]--;
iSumC[iColNo]--;
            }
        }
    }
return iFound;          // 用于判断是否有解
}
int main(int argc, char* argv[]) {
    if(!Set(0))
        printf("Failure!");
}

 

12、四个工人,四个任务,每个人做不同的任务需要的时间不同,求任务分配的最优方案。(2005529日全国计算机软件资格水平考试——软件设计师的算法题)。

#include "stdafx.h"
#define N 4
int  Cost[N][N] = { {2, 12, 5, 32},       // 行号:任务序号,列号:工人序号
                    {8, 15, 7, 11},       // 每行元素值表示这个任务由不同工人完成所需要的时间
                    {24, 18, 9, 6},
                    {21, 1, 8, 28}};
int MinCost=1000;
int Task[N], TempTask[N], Worker[N];
void Assign(int k, int cost) {
     if(k == N) {
         MinCost = cost;   
         for(int i=0; i<N; i++)
              TempTask[i] = Task[i];
     } else {
         for(int i=0; i<N; i++) {   
              if(Worker[i]==0 && cost+Cost[k][i] < MinCost) {    // 为提高效率而进行剪枝
                   Worker[i] = 1;     Task[k] = i;
                   Assign(k+1, cost+Cost[k][i]);
                   Worker[i] = 0; Task[k] = 0;
              }
         }
     }
}
int main(int argc, char* argv[]) {
     Assign(0, 0);
     printf("最佳方案总费用=%d/n", MinCost);
     for(int i=0; i<N; i++)      /* 输出最佳方案 */
         printf("/t任务%d由工人%d来做:%d/n", i, TempTask[i], Cost[i][TempTask[i]]);
}

 

13、八皇后问题,输出了所有情况,不过有些结果只是旋转了90度而已。(回溯算法的典型例题,是数据结构书上算法的具体实现,大家都亲自动手写过这个程序吗?)

#define N 8
int Board[N][N];
int Valid(int i, int j) {        // 判断下棋位置是否有效
     int k = 1;
     for(k=1; i>=k && j>=k;k++)
         if(Board[i-k][j-k])    return 0;
     for(k=1; i>=k;k++)
         if(Board[i-k][j])      return 0;
     for(k=1; i>=k && j+k<N;k++)
         if(Board[i-k][j+k])    return 0;
     return 1;
}
 
void Trial(int i, int n) {       // 寻找合适下棋位置
     if(i == n) {
         for(int k=0; k<n; k++) {
              for(int m=0; m<n; m++)
                   printf("%d ", Board[k][m]);
              printf("/n");
         }
         printf("/n");
     } else {
         for(int j=0; j<n; j++) {
              Board[i][j] = 1;
              if(Valid(i,j))
                   Trial(i+1, n);
              Board[i][j] = 0;
         }
     }
}
 
int main(int argc, char* argv[]) {
     Trial(0, N);
}

 

链表的逆转

 

#include "stdafx.h"
typedef char eleType;       // 定义链表中的数据类型
typedef struct listnode {   // 定义单链表结构
     eleType data;
     struct listnode *next;
}node;
 
node *create(int n) {       // 创建单链表,n为节点个数
     node *p = (node *)malloc(sizeof(node));  
     node *head = p;    head->data = 'A';
     for(int i='B'; i<'A'+n; i++) {                
         p = (p->next = (node *)malloc(sizeof(node)));
         p->data = i;
         p->next = NULL;       
     }
     return head;
}
 
void print(node *head) {    // 按链表顺序输出链表中元素
     for(; head; head = head->next)
         printf("%c ", head->data); 
     printf("/n");
}
 
node *reverse(node *head, node *pre) {    // 逆转单链表函数。这是笔试时需要写的最主要函数
     node *p=head->next;
     head->next = pre;
     if(p)    return reverse(p, head);
     else     return head;
}
 
int main(int argc, char* argv[]) {
     node *head = create(6);
     print(head);
     head = reverse(head, NULL);
     print(head);
}

 

最大公共字符串

 

#include "stdafx.h"
char *MaxSubString(char *str1, char *str2) {
     int i, j, k, index, max=0;
     for(i=0; str1[i]; i++)
         for(j=0; str2[j]; j++) {
              for(k=0; str1[i+k]==str2[j+k] && (str2[i+k] || str1[i+k]); k++);
              if(k>max) {        // 出现大于当前子串长度的子串,则替换子串位置和程度
                   index = j;    max = k;
              }
         }
     char *strResult = (char *)calloc(sizeof(char), max+1);
     for(i=0; i<max; i++)       
         strResult[i] = str2[index++];
     return strResult;
}
 
int main(int argc, char* argv[]) {
     char str1[] = "abractyeyt", str2[] = "dgdsaeactyey";
     char *strResult = MaxSubString(str1, str2);
     printf("str1=%s/nstr2=%s/nMaxSubString=%s/n", str1, str2, strResult);
}

 

26、判断单链表中是否存在环(网上说的笔试题)

#include "stdafx.h"
typedef char eleType;                // 定义链表中的数据类型
typedef struct listnode {            // 定义单链表结构
     eleType data;
     struct listnode *next;
}node;
 
node *create(int n) {                 // 创建单链表,n为节点个数
     node *p = (node *)malloc(sizeof(node));  
     node *head = p;    head->data = 'A';
     for(int i='B'; i<'A'+n; i++) {
         p = (p->next = (node *)malloc(sizeof(node)));
         p->data = i;
         p->next = NULL;
     }
     return head;
}
 
void addCircle(node *head, int n) {  // 增加环,将链尾指向链中第n个节点
     node *q, *p = head;
     for(int i=1; p->next; i++) {
         if(i==n) q = p;
          p = p->next;
     }
     p->next = q;
}
 
int isCircle(node *head) {           // 这是笔试时需要写的最主要函数,其他函数可以不写
     node *p=head,*q=head;
     while( p->next && q->next) {
         p = p->next;
         if (NULL == (q=q->next->next))   return 0;
         if (p == q)   return 1;
     }
     return 0;
}
 
int main(int argc, char* argv[]) {
     node *head = create(12);
     addCircle(head, 8);              // 注释掉此行,连表就没有环了
     printf("%d/n", isCircle(head));
}

 

http://blog.csdn.net/iamfranter/article/details/6828341

Leave a Reply

Your email address will not be published. Required fields are marked *