자바 문자열 알고리즘 문제

9427 단어 Ĵava알고리즘
1. 함 수 를 만 듭 니 다. 입력 한 문자열 을 반전 시 키 는 역할 을 합 니 다.문자열 을 문자 배열 로 입력 하 십시오.  char[]  라 는 형식 으로 제시 했다.
다른 배열 에 추가 공간 을 할당 하지 마 십시오. 입력 배열 을 제자리 에서 수정 하고 O (1) 의 추가 공간 으로 이 문 제 를 해결 해 야 합 니 다.
배열 의 모든 문자 가 ASCII 메타 의 인쇄 가능 한 문자.
  :["h","e","l","l","o"]
  :["o","l","l","e","h"]

사고 분석: 시작 과 중간 색인 을 함께 증가 시 킨 다음 에 교환 하 는 것 이 고, 다른 하 나 는 머리 와 꼬리 교환 이 중간 으로 접근 하 는 것 이다.
public void reverseString(char[] s) {
	int len=s.length;
	for(int i=0;i

 
2. 32 비트 의 기호 정 수 를 제시 하려 면 이 정수 에서 각 비트 의 숫자 를 반전 시 켜 야 한다.
  : 123
  : 321

  : -123
  : -321

  : 120
  : 21

  :
              32        ,        [−231,  231 − 1]。
       ,               0。

문제 풀이 느낌: 한 문자열 의 문 제 는 관 해 는 문자열 을 사용 하지 않 았 다.
사고방식 해석: 정 수 를 문자열 로 바 꾸 고 정수 로 바 꿀 때 이상 을 포착 합 니 다. 이상 을 포착 하 는 것 은 모든 사람 을 만족 시 키 는 처리 방식 이 아 닐 수도 있 습 니 다.물론 마지막 이 튀 어 나 올 때마다 새 수 1 위 에 올 려 재 구성 하 는 것 도 있 고, 최대 수 를 10 으로 나 누 면 넘 치지 않 는 다 는 판단 도 있다.
public int reverse(int x) {
	boolean bol=false;
	if(x<0){
		x=-x;
		bol=true;
	}
	String str1=String.valueOf(x);
	String str2="";
	int len=str1.length();
	for(int i=len-1;i>=0;i--){
		str2+=str1.charAt(i);
	}
	try{
		x=Integer.parseInt(str2);
		if(bol){
			return -x;
		}         
	}catch(Exception e){
		return 0;
	}  
	return x;
}
//
public int reverse(int x) {
	int rev = 0;
	while (x != 0) {
		int pop = x % 10;
		x /= 10;
		if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
		if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
		rev = rev * 10 + pop;
	}
	return rev;
}

 
3. 문자열 을 지정 하고 첫 번 째 중복 되 지 않 는 문 자 를 찾 아 색인 을 되 돌려 줍 니 다.존재 하지 않 으 면 - 1 로 돌아 갑 니 다.
s = "leetcode"
   0.

s = "loveleetcode",
   2.

    :                。

사고 분석: 구조 배열, 모든 자모 가 정수 로 자신의 위치 에 대응 하고 + 1 에 저장 하 며 두 번 째 검색 값 이 1 인 색인 값 을 옮 겨 다 닙 니 다.맵 구현 효과 동일
 public int firstUniqChar(String s) {
 	int[] times = new int[256];
 	for (char c : s.toCharArray()) {
 		times[c - 'a']++;
 	}
 	for (int i = 0; i < s.length(); i++) {
 		if (times[s.charAt(i) - 'a'] == 1) {
 			return i;
 		}
 	}
 	return -1;
 }

 
4. 두 문자열 지정 s 화해시키다 t ,함 수 를 만들어 서 판단 하 다. t 과연 s 이위어
  : s = "anagram", t = "nagaram"
  : true

  : s = "rat", t = "car"
  : false

  :
               。

  :
          unicode      ?                ?

사고 분석: 위의 문제 방법 과 같 고 진급 은 잠시 보지 않 았 습 니 다.
public boolean isAnagram(String s, String t) {
	int[] nums1=new int[26];
	int[] nums2=new int[26];
	for(char c:s.toCharArray()){
		nums1[c-'a']++;
	}
	for(char c:t.toCharArray()){
		nums2[c-'a']++;
	} 
	for(int i=0;i<26;i++){
		if(nums2[i]!=nums1[i]){
			return false;
		}
	}     
	return true;   
}   

 
5. 문자열 을 지정 하여 답장 문자열 인지 확인 하고 알파벳 과 숫자 문자 만 고려 하여 알파벳 의 대소 문 자 를 무시 할 수 있 습 니 다.
설명: 이 문제 에서 우 리 는 빈 문자열 을 효과 적 인 답장 문자열 로 정의 합 니 다.
  : "A man, a plan, a canal: Panama"
  : true

  : "race a car"
  : false

사고방식 해석: 두 가지 해법 의 이 치 는 모두 같 지만 정칙 은 좀 느 린 것 같다.
 public boolean isPalindrome(String s) {
 	String str=s.toLowerCase().replaceAll("[^0-9a-z]","");
 	for(int i=0;i '9') && (s.charAt(i) < 'a' || s.charAt(i) > 'z') && i < j) i++;
		while ((s.charAt(j) < '0' || s.charAt(j) > '9') && (s.charAt(j) < 'a' || s.charAt(j) > 'z') && i < j) j--;
		if (s.charAt(i) != s.charAt(j)) return false;
		i++;j--;
	}
	return true;
}

 
6. 하 나 를 이 루 세 요  atoi  함수, 문자열 을 정수 로 변환 할 수 있 도록 합 니 다.
우선, 이 함 수 는 첫 번 째 빈 칸 이 아 닌 문 자 를 찾 을 때 까지 쓸모없는 시작 빈 칸 문 자 를 버 립 니 다.
우리 가 찾 은 첫 번 째 비 어 있 는 문자 가 플러스 또는 마이너스 일 때 이 기 호 를 뒤의 가능 한 한 많은 연속 숫자 와 조합 하여 이 정수 의 플러스 와 마이너스 로 한다.첫 번 째 비 어 있 는 문자 가 숫자 라면 그 다음 의 연속 적 인 숫자 문자 와 조합 하여 정 수 를 이룬다.
이 문자열 은 유효한 정수 부분 을 제외 하고 불필요 한 문자 가 존재 할 수 있 습 니 다. 이 문자 들 은 함수 에 영향 을 주지 않도록 무시 할 수 있 습 니 다.
메모: 이 문자열 의 첫 번 째 빈 칸 문자 가 유효한 정수 문자 가 아니라면 문자열 이 비어 있 거나 문자열 이 빈 문자 만 포함 되 어 있 을 때 함수 가 변환 되 지 않 아 도 됩 니 다.
어떠한 경우 에 도 함수 가 효과 적 인 변환 을 할 수 없 을 경우 0 을 되 돌려 주 십시오.
설명:
만약 에 우리 의 환경 이 32 비트 크기 의 기호 정수 만 저장 할 수 있다 고 가정 하면 그 수치 범 위 는? [−231,  231 − 1]。만약 수치 가 이 범 위 를 초과 한다 면, qing 은 되 돌아 갑 니 다. INT_MAX (231 또는 INT_MIN (−231) 
   1:

  : "42"
  : 42
   2:

  : "   -42"
  : -42
  :           '-',       。
                             ,     -42 。
   3:

  : "4193 with words"
  : 4193
  :         '3' ,             。
   4:

  : "words and 987"
  : 0
  :          'w',         、  。
                。
   5:

  : "-91283472332"
  : -2147483648
  :    "-91283472332"    32         。 
          INT_MIN (−231) 。

사고 분석: 먼저 빈 문 자 를 해결 한 다음 에 플러스 와 마이너스 번 호 를 먼저 떼 어 낸 다음 에 문자 가 숫자 인지 아 닌 지 를 보고 숫자 가 아니면 종료 합 니 다.
public int myAtoi(String str) {
        // ex:"5900         "
        String strs = str.trim();
        if(strs == null || "".equals(strs))   return 0;
        char Initials = strs.charAt(0);
        int res = 0;
        boolean isPos = Initials != '-' || Initials == '+' ;
        int i = 0;
        //            1  
        i = (Initials == '+' || Initials == '-') ? 1 : 0;
        // System.out.print(i);
        for (; i < strs.length(); i++)  {
            //                ,                    ,
            //  ,       ,      0
            if(!Character.isDigit(strs.charAt(i))) break;
            else{
                int right = strs.charAt(i) - '0';
                // System.out.println((Integer.MAX_VALUE - right) / 10);
                if (res > (Integer.MAX_VALUE - right) / 10) { 
                    return isPos ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                }
                res = res * 10 + right;   //        
            }
        }      
       return isPos ? res : -res;
}

 
7. 하나 정 하기 haystack 문자열 과 needle 문자열 은 haystack 문자열 에서 needle 문자열 이 나타 나 는 첫 번 째 위 치 를 찾 습 니 다 (0 부터).존재 하지 않 으 면 되 돌아 갑 니 다.  -1。 
   1:

  : haystack = "hello", needle = "ll"
  : 2
   2:

  : haystack = "aaaaa", needle = "bba"
  : -1
  :

  needle       ,          ?             。

      ,  needle              0 。  C    strstr()    Java  indexOf()     。

사고방식 해석: 가장 간단 한 해법
public int strStr(String haystack, String needle) {
        if (needle.equals(""))
            return 0;
        else if (!haystack.contains(needle))
            return -1;
        else {
            return haystack.indexOf(needle);
        }
}

 
8. 번호 서열 은 하나의 정수 서열 로 그 중의 정수 순서에 따라 번 호 를 하고 다음 수 를 얻는다.그 앞의 다섯 가지 항목 은 다음 과 같다.
1.     1
2.     11
3.     21
4.     1211
5.     111221

1      "one 1"  ("   ") ,   11。
11     "two 1s" ("   "),   21。
21     "one 2",  "one 1" ("   " ,  "   ") ,   1211。

        n(1 ≤ n ≤ 30),         n  。

  :             。

   1:

  : 1
  : "1"
   2:

  : 4
  : "1211"

사고 분석: 외부 while 순환 은 검색 문자열 이 고, 내 부 는 while 순환 으로 같은 숫자의 개 수 를 계산 하 며, 연 결 된 숫자 는 계수 의 숫자 로 계산 되 는 숫자 입 니 다.
public String countAndSay(int n) {
        String str="1";
        for(int i=0;i

 
9. 문자열 배열 의 가장 긴 공공 접 두 사 를 찾기 위해 함 수 를 작성 합 니 다.공공 접두사 가 존재 하지 않 으 면 빈 문자열 을 되 돌려 줍 니 다.  ""
   1:

  : ["flower","flow","flight"]
  : "fl"
   2:

  : ["dog","racecar","car"]
  : ""
  :          。
  :

            a-z 。

사고방식 해석: 첫 번 째 는 모든 문자 의 뒤에서 찾 는 것 이 고, 두 번 째 는 뒤로 찾 는 것 이다
public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length() ; i++){
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c)
                return strs[0].substring(0, i);             
        }
    }
    return strs[0];
}
//
public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (int i = 0; i < strs[0].length() ; i++){
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j ++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);             
            }
        }
        return strs[0];
}

좋은 웹페이지 즐겨찾기