Friday, January 29, 2016

zzC语言统计文件中的字符数、单词数以及总行数

统计文件的字符数、单词数以及总行数,包括:
  • 每行的字符数和单词数
  • 文件的总字符数、总单词数以及总行数

注意:
  • 空白字符(空格和tab缩进)不计入字符总数;
  • 单词以空格为分隔;
  • 不考虑一个单词在两行的情况;
  • 限制每行的字符数不能超过1000。

请先看代码:
  1. #include <stdio.h>
  2. #include <string.h>
  3. int *getCharNum(char *filename, int *totalNum);
  4. int main(){
  5. char filename[30];
  6. // totalNum[0]: 总行数 totalNum[1]: 总字符数 totalNum[2]: 总单词数
  7. int totalNum[3] = {0, 0, 0};
  8. printf("Input file name: ");
  9. scanf("%s", filename);
  10. if(getCharNum(filename, totalNum)){
  11. printf("Total: %d lines, %d words, %d chars\n", totalNum[0], totalNum[2], totalNum[1]);
  12. }else{
  13. printf("Error!\n");
  14. }
  15. return 0;
  16. }
  17. /**
  18. * 统计文件的字符数、单词数、行数
  19. *
  20. * @param filename 文件名
  21. * @param totalNum 文件统计数据
  22. *
  23. * @return 成功返回统计数据,否则返回NULL
  24. **/
  25. int *getCharNum(char *filename, int *totalNum){
  26. FILE *fp; // 指向文件的指针
  27. char buffer[1003]; //缓冲区,存储读取到的每行的内容
  28. int bufferLen; // 缓冲区中实际存储的内容的长度
  29. int i; // 当前读到缓冲区的第i个字符
  30. char c; // 读取到的字符
  31. int isLastBlank = 0; // 上个字符是否是空格
  32. int charNum = 0; // 当前行的字符数
  33. int wordNum = 0; // 当前行的单词数
  34. if( (fp=fopen(filename, "rb")) == NULL ){
  35. perror(filename);
  36. return NULL;
  37. }
  38. printf("line words chars\n");
  39. // 每次读取一行数据,保存到buffer,每行最多只能有1000个字符
  40. while(fgets(buffer, 1003, fp) != NULL){
  41. bufferLen = strlen(buffer);
  42. // 遍历缓冲区的内容
  43. for(i=0; i<bufferLen; i++){
  44. c = buffer[i];
  45. if( c==' ' || c=='\t'){ // 遇到空格
  46. !isLastBlank && wordNum++; // 如果上个字符不是空格,那么单词数加1
  47. isLastBlank = 1;
  48. }else if(c!='\n'&&c!='\r'){ // 忽略换行符
  49. charNum++; // 如果既不是换行符也不是空格,字符数加1
  50. isLastBlank = 0;
  51. }
  52. }
  53. !isLastBlank && wordNum++; // 如果最后一个字符不是空格,那么单词数加1
  54. isLastBlank = 1; // 每次换行重置为1
  55. // 一行结束,计算总字符数、总单词数、总行数
  56. totalNum[0]++; // 总行数
  57. totalNum[1] += charNum; // 总字符数
  58. totalNum[2] += wordNum; // 总单词数
  59. printf("%-7d%-7d%d\n", totalNum[0], wordNum, charNum);
  60. // 置零,重新统计下一行
  61. charNum = 0;
  62. wordNum = 0;
  63. }
  64. return totalNum;
  65. }
在D盘下创建文件demo.txt,并输入如下的内容:
I am Chinese. I love my country.
China has 960 square kilometers of territory.
China has a population of 1.35 billion.
The capital of China is Beijing.

                                By gunge

                                2014-10-12
运行程序,输出结果为:
Input file name: d://demo.txt
line   words  chars
1      7      26
2      7      39
3      7      33
4      6      27
5      0      0
6      2      7
7      0      0
8      1      10
Total: 8 lines, 30 words, 142 chars

上面的程序,每次从文件中读取一行,放到缓冲区buffer,然后遍历缓冲区,统计当前行的字符和单词数。

fgets()函数用于从文件中读取一行或指定个数的字符,其原型为:
   char * fgets(char *buffer, int size, FILE * stream);
参数说明:
  • buffer为缓冲区,用来保存读取到的数据。
  • size为要读取的字符的个数。如果该行字符数大于size-1,则读到 size-1 个字符时结束,并在最后补充' \0';如果该行字符数小于等于 size-1,则读取所有字符,并在最后补充 '\0'。即,每次最多读取 size-1 个字符。读取的字符包括换行符。
  • stream为文件指针。

有的读者问,为什么不使用getc(),每次从文件中读取一个字符,也无需开辟缓冲区。

这样没有问题,但是在处理换行时要注意跨平台问题,因为不同的平台对文本文件换行的处理不一样,Linux以'\n'为换行符,Windows以'\n\r'为换行符,Mac又以'\r\n'为换行符。所以,使用getc()函数处理换行时比较麻烦。

这里去繁就简,通过fgets()读取整行数据,然后再处理每个字符,直接忽略'\n'和'\r'。

注意:由于每行的结尾会有最多2个字节长度的换行符,fgets()还会添加NUL,所以缓冲区的长度至少为1003,才能容纳每行1000个字符,否则strlen()可能返回垃圾值。

请看代码第43行,打开文件出错时,返回NULL,而不是生硬的exit()。这样可以通知主调函数发生了错误,让主调函数做出适当的处理,或者通知用户,提高软件的用户体验。

Sunday, January 24, 2016

171. Excel Sheet Column Number

/*
171. Excel Sheet Column Number
Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28
    */


public class Solution {
    public int titleToNumber(String s) {
    int len = s.length();
    int[] number = new int[len];
    int titleNumber = 0;
    for(int i = 0; i < len; i++){
    number[i] = (int)(s.charAt(i) - 'A' + 1);
    titleNumber = titleNumber + number[i] * (int)(Math.pow(26, len - i - 1));
    }    
    return titleNumber;      
    }
}

/* a string problem, change string into int, combine with bit operate.*/

242 Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
Note:
You may assume the string contains only lowercase alphabets.

Naive solution:
public class Solution {
    public boolean isAnagram(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        if(slen != tlen){
            return false;
        } else {
            int round = slen;
            int cnt = slen;
// Use a ArrayList to store the characters, easy to add and remove, resize automaticly
            ArrayList<Character> s_array = new ArrayList<Character>(slen);
            ArrayList<Character> t_array = new ArrayList<Character>(slen);
            for(int i = 0; i < slen; i++){
                s_array.add(s.charAt(i));
            }
            for(int i = 0; i < slen; i++){
                t_array.add(t.charAt(i));
            }
            /*
            This is a way to convert String to seperate chars
            char s_char = new char[slen];
            char t_char = new char[tlen];
            s.getChars(0, slen, s_char, 0);
            t.getChars(0, tlen, t_char, 0); */
            while(round > 0){
                round--;
                for(int j = 0; j < cnt; j++){
                    if(s_array.get(round) == t_array.get(j)){
                        cnt--;
                        t_array.remove(j);
                        break;//stucked here for 4 hours. At first I use a 'continue' which did not stop the loop and 
// it keep remove t_array untill remove all the items.
                    }
                }
            }
            if(t_array.isEmpty()){
                return true;
            } else {
                return false;
            }
        }        
    }
}

//a better solution
//just compare the value of two strings

public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int[] count = new int[26];
        for(int i=0;i<s.length();i++){
            count[s.charAt(i)-'a']++;
            count[t.charAt(i)-'a']--;
        }
        for(int i:count){
            if(i!=0){
                return false;
            }
        }
        return true;
    }
}


Friday, January 22, 2016

LC100 Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        } else if(p == null || q == null){
            return false;
        } else {
            if(p.left == null && q.left == null){
                if(p.right == null && q.right == null){
                    if(p.val == q.val){
                        return true;
                    } else {
                        return false;
                    }
                } else if(p.right == null || q.right == null){
                    return false;
                } else {
                    if(p.val == q.val){
                        if(isSameTree(p.right, q.right)){
                            return true;
                        } else {
                            return false;
                        }
                    } else {
                        return false;
                    }
                }
            } else if(p.left == null || q.left ==null){
                return false;
            } else {
                if(p.val == q.val){
                    if(isSameTree(p.left, q.left) && isSameTree(p.right, q.right)){
                        return true;
                    } else {
                        return false;
                    }                  
                } else {
                    return false;
                }
            }
        }
    }
}


consider carefully and attentively, care about all corner cases. Every note's value, left child and right child should be compare completely

LC283 Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

public class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        for(int i = 0; i < n; i++){
            if(nums[i] != 0){
                nums[cnt] =nums[i];
                cnt++;
            }
        }
        for(int i = cnt; i < n; i++){
            nums[i] = 0;
        }
    }
}

find non-zero first, then put them according the relative order. set the rest with '0'