递归，分治，标记

高颖

算法

发布于：2020年2月2日

打印图案
1. 等腰三角形之字母扩展
2. 空心菱形方法一：两个等腰三角形拼接
3. 空心菱形方法二：对角线相等
4. 杨辉三角
5. 螺旋矩阵
6. 蛇形矩阵 1
7. 蛇形矩阵 2
趣味习题
1. 打印某年某月日历排版
2. 找出最长的单词
3. 颠倒一串英文句子
4. 颠倒一串英文句子 Java版本
5. 生成不重复的随机数
6. 统计班级成绩排名 Java 版本
7. 统计班级成绩排名 C 版本
8. 报数 123，报数 3 的童鞋退出，最后留下的是哪个同学。 Java 版本
9. 报数 123，报数 3 的童鞋退出，最后留下的是哪个同学。 C 语言版本
10. 模拟对象层级树结构
基础排序
1. 插入排序
2. 选择排序
3. 冒泡排序
4. 快速排序
5. 二分法查找
Json 格式的校验

打印图案

等腰三角形之字母扩展

//等腰三角形之字母扩展
void  printThreeCornerRect1()
{
    int i,j,row;
    printf("输入行：");
    scanf("%d",&row);
    int col=2*row-1;
    char words[27]=" ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int center = col/2 + 1;
    printf("center:%d\n",center);
    
    for(i=1;i<=row;i++){
        for(j=1;j<=col;j++){
            
            if(j<=row-i||j>col-(row-i))
                printf(" ");
            else{
                if(j==center && i >1){
                    printf("%c",words[i+1]);
                }else{
                    printf("%c",words[i]);
                }
            }
        }
        printf("\n");
    }
}

打印结果：
输入行：9
        A        
       BCB       
      CCDCC      
     DDDEDDD     
    EEEEFEEEE    
   FFFFFGFFFFF   
  GGGGGGHGGGGGG  
 HHHHHHHIHHHHHHH 
IIIIIIIIJIIIIIIII

思路分析：

根据输入行数，先输出一个矩形如下图所示。
确定每一行字母的个数为 2 n - 1。
每行显示的时候根据条件对显示字母除外的地方挖空，用 * 表示

打印字母取数组对应下标行数的字母。正中间的位置为下标加 1 输出下一个字母。

********A********
*******BCB*******
******CCDCC******
*****DDDEDDD*****
****EEEEFEEEE****
***FFFFFGFFFFF***
**GGGGGGHGGGGGG**
*HHHHHHHIHHHHHHH*
IIIIIIIIJIIIIIIII

空心菱形方法一: 两个等腰三角形拼接

//空心菱形
void printLingxingRect()
{
    int i,j,e,f;
    int c;
    char word[10] = "*";
    printf("请输代表图案:");
    scanf("%s",&word);
    printf("请输入行:");
    scanf("%d",&c);
    printf("\n");
    for(i=1;i<=c;i++)  //打印上半部分
    {
        for(j=1;j<=c+1-i;j++)
        {
            printf(" "); //左边挖空
        }
        for(j=1;j<=(2*i-1);j++)
        {
            if(j>1&&j<(2*i-1))
                printf(" "); //中间挖空
            else printf("%s", word);
        }
        printf("\n");
    }
    for(e=2;e<=c;e++) //打印下半部分
    {
        for(f=1;f<=e;f++)
        {
            printf(" ");
        }
        for(f=1;f<=2*c+1-2*e;f++)
        {
            if(f>1&&f<2*c+1-2*e)
                printf(" ");
            else
                printf("%s",word);
        }
        printf("\n");
    }
}

效果如下：

请输代表图案:*
请输入行:9

         *
        * *
       *   *
      *     *
     *       *
    *         *
   *           *
  *             *
 *               *
  *             *
   *           *
    *         *
     *       *
      *     *
       *   *
        * *
         *

思路分析：

由一个正等腰三角形和倒等腰三角形组成。
对上半部分等腰三角形左边挖空，中间挖空。

对下半部分倒等腰三角形左边挖空，中间挖空。下图为数字 0 替代挖空位置的分析思路。

000000000*
00000000*0*
0000000*000*
000000*00000*
00000*0000000*
0000*000000000*
000*00000000000*
00*0000000000000*
0*000000000000000*
00*0000000000000*
000*00000000000*
0000*000000000*
00000*0000000*
000000*00000*
0000000*000*
00000000*0*
000000000*

空心菱形方法二：对角线相等

void printLingxingRect2()
{
    int r,c,row;
    printf("请输入菱形的对角线的长度:");
    scanf("%d",&row);
    for(r=1;r<=row*2-1;r++)
    {
        for(c=1;c<=row*2-1;c++)
        {
            if((r<=row && (c==row+1-r)) || c==row-1+r)
                printf("*");
            else if((r>=row && (c==r-row+1)) || (c==row+row*2-1-r))
                printf("*");
            else 
                printf(" ");
        }
        printf("\n");
    }
}

思路分析：

根据菱形的对角线相等的数据知识，首先绘制的是一个矩形图案如图所示: 数字 0 为挖空项。
第一个条件先判断上半部分左边和右边星星位置。
第二个条件判断下半部分左边和右边星星的位置。
以上半部分为列 “c == row-1+r” 和左边 “row+1-r” 对称。

请输入菱形的对角线的长度:9
00000000*00000000
0000000*0*0000000
000000*000*000000
00000*00000*00000
0000*0000000*0000
000*000000000*000
00*00000000000*00
0*0000000000000*0
*000000000000000*
0*0000000000000*0
00*00000000000*00
000*000000000*000
0000*0000000*0000
00000*00000*00000
000000*000*000000
0000000*0*0000000
00000000*00000000

杨辉三角

//杨辉三角
void yanghui_Corner()
{
    int arr[15][15];
    int i,j;
    for(i=0;i<10;i++){
        arr[i][0]=1;
        arr[i][i]=1;
    }
    
    //从第三行开始出现规律
    for(i=2;i<10;i++){
        for(j=1;j<i;j++){
            arr[i][j]=arr[i-1][j]+arr[i-1][j-1];
        }
    }
    
    //输出
    for(i=0;i<10;i++){
        
        for(j=0;j<=i;j++){
            printf("%d\t",arr[i][j]);
        }
        printf("\n");
    }
}

1    
1    1    
1    2    1    
1    3    3    1    
1    4    6    4    1    
1    5    10    10    5    1    
1    6    15    20    15    6    1    
1    7    21    35    35    21    7    1    
1    8    28    56    70    56    28    8    1    
1    9    36    84    126    126    84    36    9    1

思路分析：

从图中观察到规律，第二行开始，数字 2 是前一行的对应列和前一个位置相加所得结果。
每一行的第一个位置都是 1，每一行的最后一个位置都是 1。
第一步：建立二维数组。先给每一行的的第一个位置和 n 行的第 n 个位置赋值1。

第二步：从第 3 行开始出现规律可得出 “arr[i][j]=arr[i-1][j]+arr[i-1][j-1]” 表达式。

螺旋矩阵

#define len 9
void luoxuan(){
    int arr[len][len];
    //开始初始化，给数组赋值0
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            arr[i][j] = 0;
        }
    }
    
    arr[0][0] = 1; //顶角确定了，我们可以算出第一行右边的数字
    int circleTimes = len/2 + 1;
    int circelIndex = 0; //圈的数量
    //赋值过程
    while(circleTimes>0){  //测试时候，每一圈结束可以打印出看一下：&& circelIndex <1
        circelIndex ++;
        printf("第%d圈\n",circelIndex);
        for(int column = 1;column <= len-circelIndex; column++){  //往右排列
            if(column >= circelIndex-1){
                arr[circelIndex-1][column] = arr[circelIndex -1][column-1] + 1;
            }
        }
        
        for(int row = circelIndex; row<= len-circelIndex; row++){ //往下排列，从第二行，第X-i 列开始
            arr[row][len-circelIndex] = arr[row-1][len-circelIndex] + 1;
        }
        
        for(int column = len-circelIndex-1; column >= circelIndex-1; column--){ //往左排，下标递减1，值为后一个 + 1
            arr[len-circelIndex][column] = arr[len-circelIndex][column+1] + 1;
        }
        
        for(int row =len-circelIndex-1; row > circelIndex-1; row--){ //往上排列
            arr[row][circelIndex-1] = arr[row+1][circelIndex-1] + 1;
        }
    
        circleTimes--;
    }

    //输出二维数组
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            printf("%d\t",arr[i][j]);
        }
        printf("\n\n");
    }
}

思路分析：
由上图，当我们打印 9 行的时候，列也是 9 列。确定二维数组的长度。为了方便视觉上可以观察出每一次绕圈赋值的效果，可将二维数组每一个位置初始化赋值为 0。根据 9 行，我们确定绕圈数为 circleTimes = 5。确定循环条件之后，为每一次绕圈的二维数组某些位置赋值。依次从向右、向下、向左、向上进行赋值。circleTimes 圈数相对应减 1。

往右排列：列的起始位置为1，条件为 len - circleIndex，值为相同行的前一列的值加 1。赋值的时候还需控制列大于等于 circleIndex 减 1。如图所示控制 32，56，72，80，81 的列起始位置。
往下排列：行的起始位置为第几圈的索引，值为前一行的相同列的值加 1。
往左排列：列起始位置为 len - 第几圈 - 1，值为同行的后一列值加 1。
往上排列：行的起始位置为 len - 第几圈 -1，值为相同列的后一行值加 1。

蛇形矩阵1

/*
    1 3 6 10 15
    2 5 9 14  
    4 8 13  
    7 12  
    11
*/
    
    public static void main(String[] args) {
        Test3 t=new Test3();
        t.test(5);
    }
    
    public void test(int n)  {
        int arr[][]=new int[n][n]; 
        arr[0][0]=1;
        int column=n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < column; j++) {
                if(j==0){
                     if(i>0)
                     arr[i][j]=arr[i-1][j]+i;
                }else{
                    arr[i][j]=arr[i][j-1]+(i+1+j);
                }
            }
           column-=1;
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(arr[i][j]!=0)
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }

思路分析：

第n行第一列值为前一行的第一列值加 n。
其他列赋值为前一列值加行 i 和列 j 再加 1。
控制第二层循环列的范围，列随行变化递减。

蛇形矩阵2

打印结果：
1    2    6    7    15    16    28    29    

3    5    8    14    17    27    30    

4    9    13    18    26    31    

10    12    19    25    32    

11    20    24    33    

21    23    34    

22    35    

36   

    public static void main(String[] args) {
        Test4 t=new Test4();
        t.printData(t.test2(8));
    }
    
    public int[][] test2(int n){
        int arr[][]=new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j=0,c=i;j<=i&&c>=0;j++,c--) {
                if(i%2==0){
                     if(c==i){
                         if(c==0)
                            arr[c][j]=1; //arr[0][0] = 1
                         else
                           arr[c][j]=arr[c-1][j]+1; //前一行加1
                     }
                     else 
                        arr[c][j]=arr[c+1][j-1]+1; //后一行前一列加1
                }else{
                     if(c==i)
                        arr[j][c]=arr[j][c-1]+1; //前一列加1
                     else
                       arr[j][c]=arr[j-1][c+1]+1;//前一行后一列加1
                }
            }
       }
        return arr;
    }

    public void printData(int arr[][]){
        int n=arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {    
                if(arr[i][j]>=10)
                  System.out.print(arr[i][j]+" ");
                else
                  if(arr[i][j]!=0)
                  System.out.print("0"+arr[i][j]+" ");
                
            }
            System.out.println();
        }
    }

思路分析：
根据规律，根据行下标奇偶数拆分赋值。

数字 {02,07,16,29} 为在前一列加 1。数字 {03,08,17,30} 为前一行的后一列加 1。
数字 {05,06,15,28} 为后一行的前一列加 1。数字 4 为前一行加 1。

蛇形矩阵2

/*
   1 
   5     2
   8     6     3
   10    9     7      4
  
   观察
     arr[1][0]  arr[3][3] 
     arr[2][0]  arr[3][2]          
*/
    public static void main(String[] args) {
        Test5 t=new Test5();
        t2.printData(t.test(10));
    }
    
    public int[][] test(int n){
        int arr[][]=new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0,c=i;j<n&&c<n; j++,c++) {
                    if(c==i){
                        if(c==0)
                           arr[c][j]=1; //arr[0][0] = 1
                        else
                           arr[c][0]=arr[n-1][n-c]+1;
                    }
                    else{
                        arr[c][j]=arr[c-1][j-1]+1;
                    }    
            }
        }
        return arr;
    }
}

趣味习题

打印某年某月日历排版

void showDateBookDetail()
{
    int year, month;
    int sumYearDays = 0;  //该变量是统计到现在的总年数天数
    int sumMonthDays = 0; //月份总天数
    int sumDays = 0;//总天数
    int week; //星期
    int y, i;
    int monthArr[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  //12个月的天数
    printf("请输入一个日期(列如 2019-10):");
    scanf("%d-%d", &year, &month);  //年-月-日
    //思路: 1900年1月1日是星期一
    for(y = 1900; y < year; y++)
    {
        if(y % 400 == 0 || (y %  4 == 0 && y % 100 != 0)){
            sumYearDays += 366;     //闰年 加366天
        }
        else
            sumYearDays += 365; //平年 加365天
    }
    //闰年的二月份
    if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0) ){
        monthArr[1] = 29;
    }
    
    //累加今年的月份天数
    for(i=0; i < month-1; i++){
        sumMonthDays += monthArr[i];
    }
    
    sumDays = sumYearDays + sumMonthDays + 1;  //总天数= 年得总天数+月、号得总天数
    
    //求本月的第一天是星期几 余数
    week = sumDays % 7;
    
    printf("日\t一\t二\t三\t四\t五\t六\n\n");
    
    for(i = 0; i < week; i++)
    {
        printf("\t");
    }
    
    for(i = 1; i <= monthArr[month - 1]; i++)
    {
        printf("%d\t" , i);
        if((i + week) % 7 == 0)
            printf("\n\n");
    }
}

请输入一个日期(列如 2020-01):2020-01
日    一    二    三    四    五    六

            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    

Program ended with exit code: 0

思路分析：

打印日历首先要确定某个月的 1 号是星期几。
根据 1900 年 1 月 1 日至某月 1 日的总天数 %7 所得余数就得知某月 1 号是星期几。
循环当月总天数 %7 进行换行，依次打印每一天的排版。

找出最长的单词

#include <string.h>

void countWords(){
    
    char str[100] = "hello, my name is gaogaoProgramer, welcome to come here!";
    int index;
    long len = strlen(str);
    int spaceIndex = 0;  //从第一个下标开始算
    int recordMax = 0; //单词空格之间下标最大差即为最长单词
    int beforeIndex = 0,afterIndex = 0; //定义最长单词的前空格，后空格
    for(index = 0; index < len; index++){
        if(str[index] == 32){ //判断空格
            if(index - spaceIndex > recordMax){
                recordMax = index - spaceIndex;
                
                //记录前下标和后下标。
                beforeIndex = spaceIndex;
                afterIndex = index;
            }
            spaceIndex = index;
        }
    }
    
    printf("原始单词为：%s",str);
    printf("\n单词空格之间下标最大差:%d 前下标:%d,后下标:%d",recordMax,beforeIndex,afterIndex);
    
    //输出找到的单词；
    printf("\n\n找到的最长度单词为：");
    int charIndex;
    for(charIndex = beforeIndex; charIndex< afterIndex ; charIndex++){
        printf("%c",str[charIndex]);
    }
}

思路分析：首先想到的是每个单词的划分简单规定认为是空格分隔即为一个单词。所以我们统计每一个空格的下标，记录空格下标的最大差值。记录起始下标和终止下标。这样就找到了一个最长的单词。

颠倒一串英文句子

void revertString()
{
    int i,start=0;
    char str[4096] = "I am a SoftWare Programer";
    char min1 = str[0];
    char t;
    printf("结果：%d \n",min1);
    
    int len = strlen(str);
    int end = len-1;
    while(start<=end) //颠倒整个字符串
    {
        t=str[start];
        str[start]=str[end];
        str[end]=t;
        start++;
        end--;
    }
    printf("颠倒后的字符串是：%s",str);
    
    start=0;
    for(i=0;i<len;i++)  //颠倒一个单词
    {
        if(str[i]==32||str[i+1]==0)  //如果是空格 或是结尾
        {
            if(i==len-1)  //判断是否最后一个
                end=i;
            else
                end=i-1;
            while(start<=end)  //调换空格与空格之间
            {
                t=str[start];
                str[start]=str[end];
                str[end]=t;
                start++;
                end--;
            }
            start=i+1; //起始位置
        }
    }
    
    printf("\n输出：");
    for(i=0;i<len;i++)
    {
        printf("%c",str[i]);
    }
}

思路分析：C 语言版本首先我们想到的是倒转整个字符串，然后再根据空格分割循环依次再倒转每一个单词，这样就实现了倒转整个句子。

颠倒一串英文句子 Java版本


import java.util.Scanner;
public class reverseString {

    /**
     * 旋转字符串  如： I am a student  
     * 结果为： student a am I 
     * @param arr
     */
    public static void reverse(String arr[])
    {
        int start = 0;
        for (int end = arr.length - 1; start < end; end--)
        {
            String temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
        }
        System.out.println("\n颠倒后的结果为：");
        for (int i = 0; i < arr.length; i++)
     System.out.print((new StringBuilder(String.valueOf(arr[i]))).append(" ").toString());

    }
    
    public static void main(String[] args) {
        System.out.println("请输入一串字符");
        Scanner input=new Scanner(System.in);
        String str=input.nextLine();
        String arr[]=str.split(" ");
         reverse(arr);
    }
}

思路分析：Java 版本的倒转思路比较简单。我们可以直接利用字符窜方法根据空格分割成一个字符窜数组。然后再针对数组元素进行倒转调换位置。

生成不重复的随机数

//标记法
public void randomTest2(){
    Random random = new Random();
    long[] arr =new long[15];
    boolean flag[] = new boolean[15];
    flag[0] = true;
    for(int index=1; index<flag.length; index++){
        flag[index] = false;
    }
    
    for(int i=0; i<arr.length; i++){
        int num = r.nextInt(15);
        if(!flag[num]){ //只需判断标记数组中对应的数字位置存储的状态就可以知道是否产生过该随机数
            arr[i] = num;
            flag[num] = true;
        }else{
            i--;
        }
    }
    
    //输出15个数
}

思路分析：生成不重复的小范围数字，我想到有两种方案。

第一种是每一次生成，要循环去检验已生成的随机数数组中是否包含该数字。
第二种方案是用另外一个数组布尔值来存储，当已生成随机某数时，就把对应的布尔值数组设置随机下标数值为 true。当下次再生成的时候，就可以直接命中无需查找数组元素。这也是借鉴 map 存取数据的方式，直接根据 key 命中数据。key 则相当于那个随机数。

统计班级成绩排名 java版本

import java.util.Arrays;
import java.util.Scanner;

public class SameSCore {
    
    /**
     * 统计同成绩的人数
     * 推断过程： 第一名找出后 ，统计和第一名相等的分数有几个
     * @param args
     */
    public static void main(String[] args) {

        int arr[] = { 65, 70, 80, 50, 70, 80 };
        Arrays.sort(arr); // 升序排列
        int len = arr.length - 1;

        System.out.println("请输入前多少名?");
        Scanner input=new Scanner(System.in);
        int num=input.nextInt();
        
        int count[] = new int[num+1];  //由于第1个不取，所以长度比实际的加1 ，存储第多少名的   数据 
        int score[]=new int[len+1];   //成绩 
        //第几名 多少个同学
        
        for (int k = 1; k <= count.length-1; k++) {
            int hasCount=0;
            for(int j=1;j<=k;j++){
                hasCount+=count[j];   //已经统计的个数
            }
            for (int i = len - hasCount; i >= 0; i--) { //统计第几名重复了几个
                if (arr[i] == arr[len - hasCount]) {
                    score[k]=arr[len - hasCount];  //第几名的分数
                    count[k]++;  //第几名的个数
                }
            }
        }
        
        
        // 结果：
        for (int i = 1; i <count.length; i++) {
            try{
                System.out.println("第" + i + "名,成绩为"+score[i]+"：" + count[i]);
            }catch(ArrayIndexOutOfBoundsException e){
                    System.out.println("第"+i+"名超出范围哦!");
            }
        }        
    }
}

统计班级成绩排名 C 版本

void statisticsScoreDescCount (){

    int arr[10]={20,30,50,60,60,76,85,85,96,96};  //已经升序的数组
    char names[10][20]={"jack","running","lucy","mary","hong","liu","wike","smith","boss","younth"};
    int hasCount=0; //已经统计了的个数
    int count[ScoreSystemArrLen+1]={0};  //第一个num[0]不要，记录第几名的个数。
    int score[10]={0};  //统计成绩  score[1]=96  score[2]=85  记录第几名的成绩
    int k,j,i,c=0;
    
    for(k=1;k<=ScoreSystemArrLen;k++)  //处理过程
    {
        hasCount=0;
        for(j=1;j<=k;j++)
        {
            hasCount+=count[j];  // 统计前面出现的总个数
        }
        for (i = 9-hasCount; i >= 0; i--)
        {
            if (arr[i] == arr[9 - hasCount])
            {
                score[k]=arr[9 - hasCount];  //记录具体第几名的分数
                count[k]++;  //记录具体第几名的个数
            }
        }
    }
    
    //输出
    for (i = 1; i <ScoreSystemArrLen+1; i++)
    {
        hasCount=0;
        for(j=1;j<=i;j++)// 统计前面出现的总个数
        {
            hasCount+=count[j];
        }
        if(count[i] ==0){
            break;
        }
        printf("\n第 %d 名,个数%d,成绩为:%d\n",i,count[i],score[i]);
        for(c=1,k=10-hasCount;c<=count[i];k++,c++)    //count[i] 是 当前第几名的个数
        {
            printf("名字：%s\n",names[k]);
        }
    }
}


第 1 名,个数2,成绩为:96
名字：boss
名字：younth

第 2 名,个数2,成绩为:85
名字：wike
名字：smith

第 3 名,个数1,成绩为:76
名字：liu

第 4 名,个数2,成绩为:60
名字：mary
名字：hong

第 5 名,个数1,成绩为:50
名字：lucy

第 6 名,个数1,成绩为:30
名字：running

第 7 名,个数1,成绩为:20
名字：jack

思路分析：假设有 10 个同学，则大循环 10 次。每次检查，分别将已统计的学生个数 hasCount 计算出来，然后从剩下的同学中取得其成绩标记为下一名的分数。内循环依次判断剩下同学的分数是否和本次名数的分相等，如果相等则为重复分数，记录重复分数的个数 count[k]++ , k 变量为排名。

报数123，报数3的童鞋退出，最后留下的是哪个同学。 Java 版本

import java.util.*;

public class TheLastPerson
{
    public static void main(String args[])
    {
        System.out.println("报数123，报3的同学退出，最后一个留下的同学");
        System.out.println("请输入总共有几个同学");
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();

        boolean bl[] = new boolean[num];
        for (int i = 0; i < bl.length; i++){
            bl[i] = true;
        }
        
        int index = 0;
        int lastnum = num;
        int countNum = 0;
        
        
        while (lastnum > 1)  //最后留下来的人
        {
            if (bl[index] && ++countNum == 3)
            {
                countNum = 0; //报数3后需回归
                bl[index] = false; //将报数为3的人状态标记为false
                lastnum--; //把队列人数减1
            }
            if (++index == num)  //当报数到排在最后一个位置的人，第一个接着最后一个报数
                index = 0;
        }
        
        for (int i = 0; i < num; i++){
            if (bl[i])
                System.out.println((new StringBuilder("最后留下的是第")).append(i + 1).append("个同学").toString());
        }
     } 
}

思路分析：

根据全队员人数定义一个标记布尔类型的数组。标记所有人为 true 都在队列的意思。
当报数 3 的人标记为 false. 人数出队，剩余人数减 1。接着紧邻下一个队员报数 1。每一次报数到最后当前队剩余人数的最后一个人的时候，接着再从下标为 0 的队员报数。直到最后队列剩余人数为 1。
最后再从布尔类型的数组中找出标记为 true 的位置，即可找到是哪一个同学。

报数 123，报数 3 的童鞋退出，最后留下的是哪个同学。 C 语言版本

#define N 28
#define ScoreSystemArrLen 10
#define MaxLen 50

void findStudentWhichAskNumber()
{
    char S1S8[N][15]={
        "廖同学", "吴同学", "陈聪同学", "颜同学", "梅同学", "昌同学",
        "刘同学", "钟同学", "黄同学", "生同学", "伟同学", "平同学",
        "余广同学", "朱宁同学", "陈鸿同学", "王同学", "东同学", "雄同学",
        "张同学", "林同学", "梁同学", "婷同学", "维同学", "英同学",
        "黄同学1", "斌同学", "全同学", "戴同学"};
    printf("【报数游戏】规则：一群同学排队，从规定的第几个同学开始报数1，依次2，3。报数3的同学出队。求最后剩下的人是谁？\n\n");
    char bl[N];
    int i,n;
    int index;     //索引，轮到第几个人了
    int lastnum=N;  //剩余人数
    int countNum=0; //报的数字
    //输出
    for(i=0;i<N;i++)
    {
        printf("%s\t",S1S8[i]);
    }
    
    for(i=0;i<N;i++)
    { bl[i]=1;  } //28个人都参与报数
    
    printf("\r\r请输入从第几个人开始报数：");
    scanf("%d",&n);
    printf("\n从%s开始报数,",S1S8[n-1]);
    index=n-1;
    
    while(lastnum>1)  //如果剩余人数大于1 说明还要继续报数
    {
        if(bl[index]) //表示还没报3的人。
        {
            countNum++;
            if(countNum==3)
            {   countNum=0;
                bl[index]=0; //标记报了3
                lastnum--;  //剩余人数-1
            }
        }
        index++; //下一个人
        if(index==N)  //报到最后，回来继续报数
            index=0;
    }
    
    //输出
    for(i=0;i<N;i++)
    {
        if(bl[i])
            printf("最后留下来的是：%s",S1S8[i]);
    }
}

【报数游戏】规则：一群同学排队，从规定的第几个同学开始报数1，依次2，3。报数3的同学出队。求最后剩下的人是谁？

廖同学    吴同学    陈聪同学    颜同学    梅同学    昌同学    刘同学    钟同学    黄同学    生同学    伟同学    平同学    余广同学    朱宁同学    陈鸿同学    王同学    东同学    雄同学    张同学    林同学    梁同学    婷同学    维同学    英同学    黄同学1    斌同学    全同学    戴同学    

请输入从第几个人开始报数：6

从昌同学开始报数,最后留下来的是：戴同学

Program ended with exit code: 0

模拟对象层级树结构

import java.util.*;

/*
 * 查找树节点
 */
public class LookWord {

    private ArrayList<TreeBean> treeList = new ArrayList<TreeBean>();

    public static void main(String[] args) {
        LookWord lw = new LookWord();
        lw.init();
//      lw.findAll(lw.treeList); //查找所有
        lw.findWho("111",lw.treeList); //查找某一个树节点
    }


    public void findWho(String id,ArrayList<TreeBean> ts) {
        for (TreeBean t : ts) {
            if(t.getId().equals(id)&&t.getChildren()!=null){
                  findAll(t.getChildren());
            }else{
                if(t.getChildren()!=null){
                    findWho(id,t.getChildren());
                }
            }
        }
    }


    public void findAll(ArrayList<TreeBean> findList) {

        for (int i = 0; i < findList.size(); i++) {
            TreeBean tb = findList.get(i);
            System.out.println(tb.toString());
            if (tb.getChildren() != null) {
                findAll(tb.getChildren());
            }
        }
    }
    

    // 初始数据
    private void init() {
        ArrayList<TreeBean> children111 = new ArrayList<TreeBean>();
        TreeBean tb111 = new TreeBean("1111", "one1111", "111");
        TreeBean tb112 = new TreeBean("1112", "one1112", "111");
        children111.add(tb111);
        children111.add(tb112);
        TreeBean tb11 = new TreeBean("111", "one111", "11");
        tb11.setChildren(children111);
        TreeBean tb12 = new TreeBean("112", "one112", "11");
        TreeBean tb13 = new TreeBean("113", "one113", "11");
        ArrayList<TreeBean> children11 = new ArrayList<TreeBean>();
        children11.add(tb11);
        children11.add(tb12);
        children11.add(tb13);

        TreeBean tp11 = new TreeBean("11", "one1", "1");
        tp11.setChildren(children11);
        TreeBean tp12 = new TreeBean("12", "one2", "1");
        ArrayList<TreeBean> children1 = new ArrayList<TreeBean>();
        children1.add(tp11);
        children1.add(tp12);

        TreeBean tb1 = new TreeBean("1", "one", "0");
        tb1.setChildren(children1);
        ArrayList<TreeBean> children2 = new ArrayList<TreeBean>();
        children2.add(new TreeBean("21", "two1", "2"));
        children2.add(new TreeBean("22", "two2", "2"));

        TreeBean tb2 = new TreeBean("2", "two", "0");
        tb2.setChildren(children2);
        treeList.add(tb1);
        treeList.add(tb2);
    }
}

//TreeBean 的树结构模型
public class TreeBean {

    private String id;
    private String text;
    private String pid;
    private ArrayList<TreeBean> children=new ArrayList<TreeBean>();
}

思路分析：树结构最重要的一点是递归思想。无论查找全部还是查找单独某一个树节点，都需得到他的子节点。遍历子节点时候根据 children 可得到是否还有三级子节点有则递归调用。注意父节点与子节点的绑定关系即可。

基础排序

插入排序

/
* 插入排序，效率大于选择排序。
* 方法：将一个记录插入到已排好序的有序表（有可能是空表）中
*  每次和最后一个比较，若比前面小则再换位置，直到不比前面小。
*/
public static void insert(int arr[])
{

    int count=0;
    int pos ;

    for ( int i = 1; i < arr.length; i++) {
        pos=count; //一开始进来就是和最后一个数比
        int index=i;
        while( arr[index]<arr[pos ]&&pos>=0){ //排序数 如果比已经排好的最后一个数小则，和前一个比较
            int t=arr [pos];
            arr[pos ]=arr[index];
            arr[index]=t;

            index-=1;  //注意：这是个换了位置的数
            pos--; //准备和前一个比较
        }
        count++;
    }
}

思路分析：将一个记录插入到已排好序的有序表（有可能是空表）中
每次和最后一个比较，若比前面小则再换位置，直到不比前面小。

选择排序

/*
* 直接选择排序
* 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
* 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
*/
public static void directChoose(int[] arr) {
    int index;
    int temp;
    for(int i=1;i<arr.length;i++){
        index=0;
        for(int j=1;j<=arr.length-i;j++){
            if(arr[j]<arr[index]){
                index=j;
            }
        }
        temp=arr[arr.length-i];
        arr[arr.length-i]=arr[index];
        arr[index]=temp;
    }
}

思路分析：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

冒泡排序

//每一趟排序 都可以找出最大或最小值，下一趟排序的时候，就可以排除最后已筛选出的数，和剩下的数比较。冒泡排序每一轮都是相邻的两数在比较。
public static void maopao(int arr[])
{
    int temp = 0;
    for (int i = 0; i < arr.length - 1; i++)
    {
        for (int j = i + 1; j < arr.length; j++) //n个数  比较n-1轮   第n轮 比较n-1次， 第一轮可找出最大值。
            if (arr[i] < arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    }

}

思路分析：每一趟排序都可以找出最大或最小值，下一趟排序的时候，就可以排除最后已筛选出的数，和剩下的数比较。冒泡排序每一轮都是相邻的两数在比较。

快速排序

public class QuickSort {
    
    public static void main(String[] args) {
        long start=System.currentTimeMillis();
        int arr[] ={12,34,11,99,54,21,9,5,101};
        QuickSort t=new QuickSort();
        t.quicksort(arr,0,arr.length-1);
        t.print(arr);
        System.out.println("快速排序:"+(System.currentTimeMillis()-start));
    }
    
    
    public void quicksort(int arr[], int left, int right){
        if(left < right){
            int key = arr[left];
            int low = left;
            int high = right;
            while(low < high){
                    while(low < high && arr[high] > key){
                            high--;
                    }
                    arr[low] = arr[high];
                    while(low < high && arr[low] < key){
                            low++;
                    }
                    arr[high] = arr[low];
             }
              arr[low] = key;
              quicksort(arr,left,low-1);
              quicksort(arr,low+1,right);
        }
    }
    

    public void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

思路分析：
每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。巧妙运用分治思想。

二分法查找

import java.util.Scanner;

public class HalfSelect {

    /**
     * 二分法查找
     * 
     * @param arr
     *            数组
     * @param num
     *            要查找的数字
     * @return 返回位置
     */
    private static int halfLook(int[] arr, int num) {// 二分法查找
        int middle;
        int start = 0, last = arr.length - 1;
        if (num < arr[start] || num > arr[last])
            return -1;
        while (true) {
            middle = (last + start) / 2; // 求中间位置
            if (start > last) {
                break;
            }
            if (num > arr[middle]) {
                start = middle + 1;
            } else if (num < arr[middle]) {
                last = middle - 1;
            } else
                return middle; // 相等则返回
        }
        return -1;
    }

    public static void halfShow(int arr[]) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入你要查找的数:");
        int n = input.nextInt();
        int w = halfLook(arr, n);
        if (w >= 0)
            System.out.println((new StringBuilder("位置：")).append(w).toString());
        else
            System.out.println("没有该数！");
    }
    
}

思路分析：二分法查找前提是数据要先排好序，然后才能折半查找。不断取得中间位置的数字进行比较查询出目标数。

Json 格式的校验

在讲解之前，我们先熟悉一下 Promise.all()方法的用法。

 testPromiseAll() {
 
    function washFood(){
        console.log('做饭第一步：洗菜');
        let hasError = false;
        if(hasError){
            return "发现了一只虫子！洗掉它。";
        }else{
            return '菜洗干净了。';
        }
    }
    
    function cutFood() {
        console.log('做饭第二步：切菜');
        var p = new Promise(function (resolve, reject) { //做一些异步操作
            setTimeout(function () {
                let cutFoodHasError = true;  //控制默契切菜时 是否发生异常
                if(cutFoodHasError){
                    reject("呜呜~ 割到手了，流血！")
                }else{
                    resolve('切好了菜。');
                }
            }, 1000);
        })
        /* 试试打开这里的注释
        .catch(error=>{
            console.log("切菜异常:"+error); //异常本身就是返回resolve状态，值是null
            console.log("用创口贴止血，继续做菜。");
        });
        */
        return p;
    }

    function cooking() {
        console.log('做饭第三步：炒菜');
        var p = new Promise(function (resolve, reject) { //做一些异步操作
            setTimeout(function () {
                resolve('菜已做好!');
            }, 2000);
        });
        return p;
    }

    //数组里，如果放Promise 一定要返回状态。 
    Promise.all([washFood(), cutFood(),cooking()])
        .then((result) => {
            console.log('上桌，吃饭了：'+result);
            console.log(result);
        }).catch(error=>{
            console.log("菜没做成，出现了小事故:"+error);
        })
        
   /*
     结果：
     1. 当cutFoodHasError = true；打印如下结果：
        菜没做成，出现了小事故:呜呜~ 割到手了，流血！
     2. 当cutFoodHasError = true 且 cutFood方法里的Promise有异常捕捉时： 
        切菜异常:呜呜~ 割到手了，流血！
        上桌，吃饭了：菜洗干净了！,,菜已做好
     3. 当cutFoodHasError = false 
        上桌，吃饭了：菜洗好了。切好了菜。菜已做好！
    */
    
    /* 
    Promise.all使用总结：
    数组里可以是Promise对象，也可以是别的值，只有Promise会等待状态改变
    当所有的子Promise都完成，该Promise完成，返回值是全部值得数组
    有任何一个失败，该Promise失败，返回值是第一个先失败的子Promise结果 
    */
}

服务返回 json 字符串 result

//以下注释很重要：采用分治和递归的思想。另外结合Promise.all方法 做一个异步队列控制。
boolean isJsonFlag =  checkJsonObject(result);
function checkJsonObject(obj){
    return jsonFlag;
}

思路分析：

获取每一个 key, 和对应 value 。
对 value 进行类型判断,如果是 [ ] 数组类型，foreach 每一项判断是否为 { } 对象，如果是递归调用 checkObject(itemObject) 方法；对于 value 为普通类型时，只需更具正则或算法匹配是否符合 key: value 格式。
根据服务端返回的 result 字符窜分割后依据第一层级的 value类型为 [] 数组类型的个数的多少，分批用类似 Promise.all 方法异步执行多个 Promise，一旦有一个校验返回 reject，则立即是返回 false。判断不匹配。无需等待所有的 Promise 任务执行完成。而全部 Promise 校验正确才会返回 true;

总结：通过本 chat 的学习和手动敲码实践，你将收获到对分治和递归的思想的理解。对状态的标记思想，以及对图形的观察分析思路。重点是你的思维逻辑得到了提升！如果本 chat 对你有用，那我就太高兴了。最后，感谢大伙的支持！

快速搭建前端网络请求

HTTP超文本传输协议。TCP 三次握手。 1、客户端发syn询问给服务器 2、服务器回应询问syn,并发送一个指令ack 客户端 3、客户端回 ack 服务器。正式...

iOS中高级阶段路线图

1、iOS 11之前的导航栏的高度是64px（状态条+导航栏），iOS11之后如果设置了prefersLargeTitles = YES（默认NO）则为96pt。所以一般不用管。 2、在iOS ...

递归，分治，标记

目录

打印图案

等腰三角形之字母扩展

空心菱形 方法一: 两个等腰三角形拼接

空心菱形 方法二： 对角线相等

杨辉三角

螺旋矩阵

蛇形矩阵1

蛇形矩阵2

蛇形矩阵2

趣味习题

打印某年某月日历排版

找出最长的单词

颠倒一串英文句子

颠倒一串英文句子 Java版本

生成不重复的随机数

统计班级成绩排名 java版本

统计班级成绩排名 C 版本

报数123，报数3的童鞋退出，最后留下的是哪个同学。 Java 版本

报数 123，报数 3 的童鞋退出，最后留下的是哪个同学。 C 语言版本

模拟对象层级树结构

基础排序

插入排序

选择排序

冒泡排序

快速排序

二分法查找

Json 格式的校验

空心菱形方法一: 两个等腰三角形拼接

空心菱形方法二：对角线相等