資訊專欄INFORMATION COLUMN
摘要：小鹿題目反轉(zhuǎn)字符串編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組的形式給出。如果為奇數(shù)，當(dāng)兩個指針相等時，反轉(zhuǎn)完畢。測試用例空字符串。奇數(shù)個數(shù)的字符串。長度為的字符串。考查內(nèi)容對字符串的基本操作。
Time：2019/4/18
Title: Reverse String
Difficulty: Easy
Author: 小鹿
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組 char[] 的形式給出。不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。
你可以假設(shè)數(shù)組中的所有字符都是 ASCII 碼表中的可打印字符。
Example 1:
Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]Slove:
1）反轉(zhuǎn)字符串，第一想到的就是將字符窗倒序存儲到數(shù)組中，可以先輸出，然后再 for 循環(huán)加入到數(shù)組中。題目中要求需要原地修改輸入數(shù)組，那么我們再想一個辦法。2）數(shù)組中的操作，需要原地修改數(shù)組，第一想到的就是用到指針，為什么能想到用指針呢？當(dāng)你做這種數(shù)組的也好還是鏈表的也好，做多了之后，下意識的給出解決方法然后去看看可不可行。
通過以上分析，得出兩種方法：
字符串反轉(zhuǎn)法
雙指針法
字符串反轉(zhuǎn)法：
1）字符串反轉(zhuǎn)法很簡單了，按照我們正常的思路走就可以了，首先輸出數(shù)組中的字符拼接成字符串。
2）然后從字符串尾部開始遍歷，正向輸入數(shù)組。
雙指針法：
1）定義兩個指針，分別指向字符串頭部和尾部。
2）兩個指針指向的值進行交換。
3）注意終止條件。
如果為偶數(shù)，當(dāng)頭指針 - 1 等于尾指針時，反轉(zhuǎn)完畢。
如果為奇數(shù)，當(dāng)兩個指針相等時，反轉(zhuǎn)完畢。
1）空字符串。2）偶數(shù)個數(shù)的字符串。
3）奇數(shù)個數(shù)的字符串。
4）長度為 1 的字符串。
var reverseString = function(s) {
//判斷輸入的字符串是否為空
if(s.length ==0) return s;
//定義兩個指針
let low = 0;
let high = s.length - 1;
// 循環(huán)反轉(zhuǎn)字符
while(true){
// 分為奇數(shù)/偶數(shù)兩種可能
if(low === high || high + 1 === low) break;
let temp = s[low];
s[low] = s[high];
s[high] = temp;
low++;
high--;
}
// 返回反轉(zhuǎn)好的字符串
return s;
};
var reverseString = function(s) {
//判斷輸入的字符串是否為空
if(s.length ==0) return s;
let str = "";
// 輸出字符串
for(let i in s){
str = str+`${s[i]}`;
}
// 反轉(zhuǎn)字符串輸入
for(let i = s.length - 1,j = 0;i >= 0;i--,j++){
s[j] = str.charAt(i);
}
//返回反轉(zhuǎn)好的字符串
return s;
};
字符串反轉(zhuǎn)法
時間復(fù)雜度：O（n）。遍歷整個數(shù)組，時間復(fù)雜度為 O（n）。
空間復(fù)雜度：O（n）。輸出數(shù)組需要額外的存儲空間，如果用數(shù)組存儲，需要開辟大小為 n 大小的內(nèi)存空間。如果需要數(shù)組輸出拼接字符串，空間復(fù)雜度為 O(1) 了。
雙指針法：
時間復(fù)雜度：O（n）。需要遍歷 n/2 的數(shù)據(jù)，時間復(fù)雜度為 O(n)。
空間復(fù)雜度：O（n）。只需常量級別的內(nèi)存空間，空間復(fù)雜度為O（1）。
1）對字符串的基本操作。2）數(shù)組的基本操作。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/103729.html
摘要：算法思路兩種方法一般反轉(zhuǎn)遞歸法一般解決定義三個指針，分別為，存儲當(dāng)前結(jié)點，指向反轉(zhuǎn)好的結(jié)點的頭結(jié)點，存儲下一結(jié)點信息。遞歸法重點分析先確定終止條件當(dāng)下一結(jié)點為時，返回當(dāng)前節(jié)點判斷當(dāng)前的鏈表是否為遞歸找到尾結(jié)點，將其存儲為頭結(jié)點。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 題目：Reverse...
摘要：小鹿題目翻轉(zhuǎn)字符串里的單詞給定一個字符串，逐個翻轉(zhuǎn)字符串中的每個單詞。說明無空格字符構(gòu)成一個單詞。遇到空格之后，將單詞進行倒序拼接。消除尾部的空格。測試用例空字符串。中間空格大于的字符串。 Time：2019/4/20Title: Reverse Words In a StringDifficulty: MidumnAuthor: 小鹿 題目：Reverse Words In a ...
摘要：反轉(zhuǎn)字符串公眾號愛寫編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組的形式給出。解題思路第一個字符與最后一個交換位置，繼而第二個與倒數(shù)第二個交換位置，一直交換到到中位數(shù)結(jié)束。持續(xù)交換它們所指向的元素，直到這兩個指針相遇。 Leetcode 344：Reverse String 反轉(zhuǎn)字符串 公眾號：愛寫bugWrite a function that reverses ...
摘要：反轉(zhuǎn)字符串公眾號愛寫編寫一個函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過來。輸入字符串以字符數(shù)組的形式給出。解題思路第一個字符與最后一個交換位置，繼而第二個與倒數(shù)第二個交換位置，一直交換到到中位數(shù)結(jié)束。持續(xù)交換它們所指向的元素，直到這兩個指針相遇。 Leetcode 344：Reverse String 反轉(zhuǎn)字符串 公眾號：愛寫bugWrite a function that reverses ...
摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數(shù)字則不取?；匚臄?shù)題目描述判斷一個整數(shù)是否是回文數(shù)?；匚臄?shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言 一直以來，前端開發(fā)的知識儲備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的，可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì)，但是我認為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此，我作為...
閱讀 1860·2021-09-23 11:21
閱讀 707·2019-08-30 15:55
閱讀 844·2019-08-29 15:40
閱讀 541·2019-08-29 12:56
閱讀 3175·2019-08-26 12:00
閱讀 3567·2019-08-23 18:24
閱讀 2259·2019-08-23 17:08
閱讀 1649·2019-08-23 17:03
