July 算法习题 - 字符串2 + Leetcode 8,9

timger 发布于2019-08-14 15:07 / 2905人阅读

摘要：判断一条单向链表是不是回文解法可以借助栈，将遍历到的前半段链表节点放入栈，后半段每当遍历到一个，都要与出栈的节点相比较。如果中间出现不相等的情况，则不是回文。

  [July 程序员编程艺术：面试和算法心得题目及习题][1]

字符串转换成整数

also Leetcode 8 String to Integer (atoi)

题目描述

输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串 "123"，输出整数 123。
给定函数原型int StrToInt(const char *str) ，实现字符串转换成整数的功能，不能使用库函数 atoi。

解题思路

实现是简单的，但是这道题主要考的是程序的鲁棒性。可以说要正确及完整的实现这道题，需要考虑所有常见的边界条件。

空指针输入：输入的是指针，在访问空指针时程序会崩溃，因此在使用指针之前需要先判断指针是否为空。

正负符号：整数不仅包含数字，还有可能是以"+"或"-"开头表示正负整数，因此如果第一个字符是"-"号，则要把得到的整数转换成负整数。

非法字符：输入的字符串中可能含有不是数字的字符。因此，每当碰到这些非法的字符，程序应停止转换。

整型溢出：输入的数字是以字符串的形式输入，因此输入一个很长的字符串将可能导致溢出

public class Solution {
    public int atoi(String str) {
        int digit=0;
        int positive = 1;
        double number=0;
        str = str.trim();
        if(str.length() == 0  || str == null){
            return 0;
        }
        if(str.charAt(0) =="+"){
            positive = 1;
            digit++;
        }
        if(str.charAt(0) == "-"){
            positive = -1;
            digit++;
        }
        while(digit<=str.length()-1){
            int k = 0;
            if(str.charAt(digit)<="9"&&str.charAt(digit)>="0"){
                k = str.charAt(digit) -"0";
                number  = k + number * 10; 
                digit++;
            }
            else{
                break;
            }
        }
        number = number * positive;
        System.out.println(""+number);
        if(number > Integer.MAX_VALUE ){
            return Integer.MAX_VALUE; 
        }
        if(number < Integer.MIN_VALUE){
            return Integer.MIN_VALUE;
        }
        return (int)number;
    }
}

习题：实现 string 到 double 的转换

分析：此题虽然类似于 atoi 函数，但毕竟 double 为 64 位，而且支持小数，因而边界条件更加严格，写代码时需要更加注意。

回文判断 一个整形数是否是回文

also leetcode 9 Palindrome Number
要求空间复杂度O(1)
按位判断一般是/和%的游戏，首先取首位 a/h (h是最接近a的10的次方，比如12321，h预计算出是10000), 再取末位a%10; 比较首位和末位是否相等，不等就返回false;

如图：

然后舍弃掉已经比较过的两个位数，从a中去掉首尾 12321 --> 232.

a = a % h; // 去掉首
a = a /10; //去掉尾
h = 100; // 因为已经去掉了两位

如图：

重复之前操作即可，如图：

    public boolean isPalindrome(int x) {
        int a = x, h =1;
        if(a < 0) return false;

        while(a / h>= 10) {
            h = h*10;
        }
        //compare the last and first digit and will not overflow    
        while(a> 0) {
            if(a/h != a%10) return false;
            a = a%h;
            a = a/10;
            h = h/100;
        }
        return true;
    }

一个字符串是否是回文

指一个顺着读和反过来读都一样的字符串，判断一个字串是否是回文？

这个比较简单用charAt 取字符串的首尾位比较即可。

判断一条单向链表是不是 “回文”

解法1 ：可以借助栈，将遍历到的前半段链表节点放入栈，后半段每当遍历到一个，都要与出栈的节点相比较。直到链表结尾。如果中间出现不相等的情况，则不是回文。
时间复杂度O(n),空间复杂度O(n)

如何进一步降低空间复杂度为O(1)
解法2：
分析：对于单链表结构，可以用两个指针从两端或者中间遍历并判断对应字符是否相等。但这里的关键就是如何朝两个方向遍历。由于单链表是单向的，所以要向两个方向遍历的话，可以采取经典的快慢指针的方法，即先位到链表的中间位置，再将链表的后半逆置，最后用两个指针同时从链表头部和中间开始同时遍历并比较即可。
缺陷：破坏了链表的结构

判断一个栈是不是 “回文”

分析：对于栈的话，只需要将字符串全部压入栈，然后依次将各字符出栈，这样得到的就是原字符串的逆置串，分别和原字符串各个字符比较，就可以判断了

云服务器 GPU云服务器字符串转2进制算法 ehcache 2 8 3 jquery 1 8 2 幻想云服务器1.8.9

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65296.html

字符串处理文章outline

摘要：遇到问题查查，看看，大神的讲解问问岛胖君下面是我最近整理出来的关于字符串的文章的怎么翻译汇集目录非常希望强化博客的功能，比如分类，置顶。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党最近在看算法和语言，基本属于看知识 --> java实现 --> 整理blog 这个路线。遇到问题查查st...

Karuru 2019-08-14 15:07 评论0 收藏0
July算法习题 - 字符串1

摘要：反转上述步骤得到的结果字符串，即反转字符串的两部分和给予反转，得到，形式化表示为，这就实现了整个反转。例如，原字符串为，，输出结果为。同单词翻转输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。 July 程序员编程艺术：面试和算法心得题目及习题旋转字符串题目描述给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如...

Betta 2019-08-14 12:09 评论0 收藏0
July 算法习题 - 字符串4（全排列和全组合）

摘要：求字符串的全排列字符串的全排列设计一个算法，输出一个字符串字符的全排列。的做法没有结果的，都是在一个字符串上进行的操作。字符串的全组合输入三个字符，则它们的组合有。因此可以循环字符串长度，然后输出对应代表的组合即可。求字符串的全排列字符串的全排列设计一个算法，输出一个字符串字符的全排列。比如，String = abc 输出是abc,bac,cab,bca,cba,...

tuniutech 2019-08-14 12:11 评论0 收藏0
字符串的全排列

摘要：问题输入一个字符串按字典序打印出该字符串中字符的所有排列。如此递归处理，从而得到所有字符的全排列。记斐波那契数列的第位这件事为，则有。其中，表示去掉那个开头字符的剩余字符串的全排列。问题输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。地址：https://...

sunny5541 2019-08-23 11:38 评论0 收藏0