ArrayAndString（數組和字符串）

1.實現一個算法，確定一個字符串的所有字符是否全都不同。假使不允許使用額外的數據結構，又該怎么處理？

public class UniqueChars {public static void main(String[] args) {// TODO Auto-generated method stubString string = "abcdefgfedcba";System.out.print(isUniqueChars(string));}public static boolean isUniqueChars(String str) {if (str.length() > 256) {return false;}boolean[] char_set = new boolean[256];for (int i = 0; i < str.length(); i++) {int val = str.charAt(i);if (char_set[val]) {return false;}char_set[val] = true;}return true;}}
View Code

注意：向面試官確認上面的字符串是ASCII字符串還是Unicode字符串。若不是ASCII字符串需擴大存儲空間，但其余邏輯不變。

? ? ? ? ? 這里假定是ASCII字符串。首先做一個優化，若字符串長度大于字母表中的字符個數，就直接返回false。畢竟，若字母表只有256個字符，字符串里就不可能有280個各不相同的字符。

? ? ? ? ? ?然后構建一個布爾值的數組，索引值i對應的標記指示該字符串是否含有字母表第i個字符。若這個字符第二次出現，則立即返回false。時間復雜度o(n),空間復雜度o(1)。

若不允許使用額外的數據結構：

（1）將字符串中的每一個字符與其余字符進行比較。時間復雜度為o(n2)，空間復雜度o(1)。

public class UniqueChars {public static void main(String[] args) {// TODO Auto-generated method stubString string = "abcdefgfedcba";System.out.print(isUniqueChars(string));}public static boolean isUniqueChars(String str) {if (str.length() > 256) {return false;}for(int i = 0; i < str.length(); i++) {for(int j = i + 1; j < str.length(); j++) {if(str.charAt(i) == str.charAt(j)) return false;}}return true;}
}
View Code

（2）若允許修改輸入字符串，可以在o(nlogn)的時間里對字符串排序，然后線性檢查其中有無相鄰字符完全相同的情況。

2.用Java實現void reverse(char* str)函數，即反轉一個null結尾的字符串。

package ArrayAndString;public class Reverse {public static void main(String[] args) {// TODO Auto-generated method stubString string = "abcdefg";System.out.println(reverseString2(string));}//最簡單的方法public static String reverseString(String iniString) {// write code hereStringBuffer tmp = new StringBuffer(iniString);tmp = tmp.reverse();return tmp.toString();}//最常用的方法public static String reverseString2(String iniString) { char[] array = iniString.toCharArray(); String reverse = "";  //注意這是空串，不是nullfor (int i = array.length - 1; i >= 0; i--) { reverse += array[i];}return reverse; } }
View Code

3.給定兩個字符串，請編寫程序，確定其中一個字符串的字符重新排列后，能否變成另一個字符串。

解法一：對字符串排序后進行比較，若它們擁有相同順序的字符，即互為變位詞。

import java.util.*;public class IsAnagram {public static void main(String[] args) {// TODO Auto-generated method stubString string1 = "aceg";String string2 = "cega";System.out.println(permutation(string1, string2));    }public static String sort(String s) {char[] content = s.toCharArray();Arrays.sort(content);return new String(content);}public static boolean permutation(String s, String t) {if (s.length() != t.length()) {return false;}return sort(s).equals(sort(t));}}
View Code

解法二：利用變位詞的定義--組成兩個單詞的字符數相同，遍歷字母表，計算每個字符出現的次數，然后比較這兩個數組。

public class IsAnagram {public static void main(String[] args) {// TODO Auto-generated method stubString string1 = "aceg";String string2 = "cega";System.out.println(permutation(string1, string2));    }public static boolean permutation(String s, String t) {if (s.length() != t.length()) {return false;}int[] letters = new int[256];char[] s_array = s.toCharArray();for (char c : s_array) {letters[c]++;}for (int i = 0; i < t.length(); i++) {int c = (int) t.charAt(i);if (--letters[c] < 0) {return false;}}return true;}}
View Code

注意：向面試官確認 變位詞是否區分大小寫 以及 是否要考慮空白字符。

? ? ? ? ? 這里假定變位詞比較區分大小寫，空白也要考慮在內，是ASCII字符串。首先做一個優化，比較兩個字符串的長度，只要長度不同就不可能是變位詞。

4.編寫一個方法，將字符串中的空格全部替換為“%20”。假定該字符串尾部有足夠的空間存放新增字符，并且知道字符串的“真實”長度。（注：用Java實現的話，請使用字符數組實現，以便直接在數組上操作。）

思路：進行兩次掃描。第一次掃描先數出字符串中有多少空格，從而算出最終的字符串有多長。第二次掃描真正開始反向編輯字符串，檢測到空格則將%20復制到下一個位置，若不是空白，就復制原先的字符。

public class ReplaceString {public static void main(String[] args) {// TODO Auto-generated method stubString str = "abc d e f";char[] arr = new char[str.length() + 3 * 2 + 1];for (int i = 0; i < str.length(); i++) {arr[i] = str.charAt(i);}replaceSpaces(arr, str.length());    System.out.println("\"" + charArrayToString(arr) + "\"");}public static String charArrayToString(char[] array) {StringBuilder buffer = new StringBuilder(array.length);for (char c : array) {if (c == 0) {break;}buffer.append(c);}return buffer.toString();}public static void replaceSpaces(char[] str, int length) {int spaceCount = 0;int index = 0; int i = 0;for (i = 0; i < length; i++) {if (str[i] == ' ') {spaceCount++;}}index = length + spaceCount * 2;str[index] = '\0';for (i = length - 1; i >= 0; i--) {if (str[i] == ' ') {str[index - 1] = '0';str[index - 2] = '2';str[index - 3] = '%';index = index - 3;} else {str[index - 1] = str[i];index--;}}}}
View Code

注意：處理字符串操作問題時，常見做法是從字符串尾部開始編輯，從后往前反向操作。因為字符串尾部有額外的緩沖，可以直接修改，不必擔心會復寫原有數據。

5.利用字符重復出現的次數，編寫一個方法，實現基本的字符串壓縮功能。比如，字符串aabcccccaaa會變成a2b1c5a3。若“壓縮”后的字符串沒有變短，則返回原先的字符串。

public class StringZipper {public static void main(String[] args) {// TODO Auto-generated method stubString str = "aabccccaaa";System.out.println(compressString(str));}public static String compressString(String str) {if (str.length() == 0) {return str;}int flag = 0;int count = 1;StringBuffer sb = new StringBuffer();char last = str.charAt(0);for (int i = 1; i < str.length(); i++) {if (str.charAt(i) == last) {count++;flag = 1;} else {sb.append(last);sb.append(count);last = str.charAt(i);count = 1;}}sb.append(last);sb.append(count);if (flag == 0 || sb.length() >= str.length()) {return str;} else {return sb.toString();}}}
View Code

注意：使用flag變量記錄字符串中是否有重復字符。若最終flag=0說明字符串中無重復字符，返回原字符串。時間復雜度和空間復雜度都為o(N)。

6.給定一幅由N*N矩陣表示的圖像，其中每個像素的大小為4字節，編寫一個方法，將圖像旋轉90度。不占用額外內存空間能否做到？

二維數組a[n][n]順時針旋轉90度，找規律如下：

當n=1時，不動。當n=2時，有：a[0][0] = a[1][0]? a[1][0] = a[1][1]??a[1][1] = a[0][1]??a[0][1] = a[0][0]??初步總結規律為：a[i][j] = a[n-1-j][i]

當n=3，4，5,……時也是滿足的。到這里，如果不考慮空間復雜度，只需要再構建一個二維數組b[n][n]，利用公式b[i][j] = a[n-1-j][i]就可以解決。代碼如下：

public void rotate(int[][] matrix) {int n = matrix.length;int[][] m = new int[n][n];for(int row=0;row<n;row++){for(int col=0;col<n;col++){m[row][col] = matrix[n-1-col][row];}}//再賦值回matrix，注意java是形參是引用傳遞for(int row=0;row<n;row++){for(int col=0;col<n;col++){matrix[row][col] = m[row][col];}}}
View Code

但是題目要求不占用額外空間，應該怎么旋轉？接著上面的分析，以n=3為例：把焦點放在一個元素的旋轉上，可以看出要在原數組中旋轉，在不丟失數據的情況下，每個值的旋轉會“波及”4個數，以1為例波及到了1,3,7,9，每個數旋轉要不丟失數據就要考慮如何讓這4個數都得以保留。前邊總結了規律a[i][j] = a[n-1-j][i]，分析每組被波及的數，我們可以得出這里波及了的4個數其實就是a[i][j]? a[n-1-j][i]??a[n-1-i][n-1-j]??a[n-1-(n-1-j)][n-1-i]=a[j][n-1-i]?所以這里需要引入一個臨時變量temp就可以解決這4個數的順時針交換，如：

?int temp = matrix[i][j];

matrix[i][j] = matrix[n-1-j][i];

matrix[n-1-j][i] = matrix[n-1-i][n-1-j];

matrix[n-1-i][n-1-j] = matrix[j][n-1-i];

matrix[j][n-1-i] = temp;

把焦點放在一個元素上，數交換的問題解決了。那么現在把焦點回到整個二維數組上來，每個數的旋轉會波及4個數，相當于用上面的方法，每旋轉一個數，就把一組的4個數都旋轉了，

所以現在的問題就是如何才能完整的把所有的數都旋轉90度且不會多旋轉，繼續分析：

n=1時，不需旋轉。

n=2時，只需要完成1（a[0][0]）的旋轉，就完成了整個數組的旋轉。

n=3時，需要完成1,2（a[0][0],a[0][1]）的旋轉，就完成了整個數組的旋轉。

n=4時，需要完成1,2,3,6（a[0][0至3]，a[1][1]）的旋轉。

n=5時，需要完成(a[0][0至4]，a[1][1至2])的旋轉。

大致可以總結出這么一個規律：對于要旋轉的數a[i][j]滿足，i<n/2?且?i<=j<n-1-i，至此問題終于解決。

public class Rotate {public static void main(String[] args) {// TODO Auto-generated method stubint[][] arr = {{1,2,3}, {4,5,6}, {7,8,9}};int length = arr.length;int[][] arr1 = transform(arr, length);for(int i = 0; i < length; ++i) {for(int j = 0; j < length; ++j) {System.out.print(arr1[i][j]+" ");}}}public static int[][] transform(int[][]matrix, int n) {int limit = n / 2;for (int i = 0; i < limit; i++) {for(int j = i; j < n - i - 1; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[n-1-j][i];matrix[n-1-j][i] = matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j] = matrix[j][n-1-i];matrix[j][n-1-i] = temp;}}return matrix;}}
View Code

算法的時間復雜度為o(N的平方)，已經是最優做法。

7.編寫一個算法，若M*N矩陣中某個元素位0，則將其所在的行與列清零。

public class ClearZeros {public static void main(String[] args) {// TODO Auto-generated method stubint[][] arr = {{1,2,0}, {4,5,6}, {7,8,9}};int[][] arr1 = setZeros(arr);for(int i = 0; i < arr.length; ++i) {for(int j = 0; j < arr[0].length; ++j) {System.out.print(arr1[i][j]+" ");}}}public static int[][] setZeros(int[][] matrix) {boolean[] row = new boolean[matrix.length];boolean[] column = new boolean[matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (matrix[i][j] == 0) {row[i] = true;column[j] = true;}}}for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (row[i] || column[j]) {matrix[i][j] = 0;}}}return matrix;}}
View Code

注意：不能在第一次遍歷整個矩陣時，發現值為零的元素就直接將其所在的行與列清零，這樣的話最后整個矩陣的所有元素都會變為零。要新建一個矩陣標記零元素的位置，在第二次遍歷矩陣時將零元素所在的行與列清零。而且只需記錄哪行和哪列有零元素即可，無須記錄零元素的確切位置。

8.假定有一個方法isSubstring，可檢查一個單詞是否為其他字符串的子串。給定兩個字符串s1和s2,請編寫代碼檢查s2是否為s1旋轉而成，要求只能調用一次isSubstring。（比如，waterbottle是erbottlewat旋轉后的字符串）。

public class IsRotation {public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(isRotation("abc","abc"));}public static boolean isSubstring(String str1,String str2){if(str1.contains(str2) || str2.contains(str1)) {return true;}return false;}public static boolean isRotation(String str1,String str2){if(str1.length() != str2.length()) {return false;}String sum = str1 + str1;return isSubstring(sum, str2);}}
View Code

注意：假定s2由s1旋轉而成，那么將s1切分成x和y，就會滿足xy=s1和yx=s2。不論x和y之間的分割點在哪，yx都肯定是xyxy的子串，也即s2總是s1s1的子串。直接調用isSubstring(s1s1,s2)即可。

轉載于:https://www.cnblogs.com/struggleli/p/7815584.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/370643.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/370643.shtml
英文地址，請注明出處：http://en.pswp.cn/news/370643.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

MyBatis教程– CRUD操作和映射關系–第2部分

MyBatis教程– CRUD操作和映射關系–第2部分

為了說明這一點&#xff0c;我們正在考慮以下示例域模型&#xff1a; 會有用戶&#xff0c;每個用戶可能都有一個博客&#xff0c;每個博客可以包含零個或多個帖子。 這三個表的數據庫結構如下&#xff1a; CREATE TABLE user (user_id int(10) unsigned NOT NULL auto_incr…
閱讀更多...
position 的屬性值

position 的屬性值

理論上來說&#xff0c;全部 position 的取值有8個 包括&#xff1a;position&#xff1a;static | relative | absolute | fixed | sticky | initial | inherit | unset 其中最常用的是 static 、relative、absolute、fixed 和 sticky initial、inherit、unset 是css的關鍵…
閱讀更多...
[ JavaScript ] JavaScript 實現繼承.

[ JavaScript ] JavaScript 實現繼承.

對于javascript中的繼承&#xff0c;因為js中沒有后端語言中的類式繼承。所以js中的繼承&#xff0c;一般都是原型繼承(prototype)。 function P (name){this.name name;this.say function(){console.log(p);} }function S (name,id){this.id id;this.eat function(){conso…
閱讀更多...
mysql數據庫應用的權限層級_MySQL數據庫的用戶權限管理

mysql數據庫應用的權限層級_MySQL數據庫的用戶權限管理

嗨&#xff01;各位小伙伴今天翻了一下歷史記錄MySQL 數據庫還有點內容今天開始我們就來補上吧~用戶權限管理伙伴們要知道&#xff0c;在數據庫方面有兩個方向。一個是數據庫管理員(Database Administrator)簡稱DBA&#xff0c;一個是數據庫開發工程師(Database Developer)&…
閱讀更多...
linux i2c adapter 增加設備_Linux驅動之I2C驅動架構

linux i2c adapter 增加設備_Linux驅動之I2C驅動架構

一、Linux的I2C體系結構主要由三部分組成&#xff1a;(1) I2C核心提供I2C控制器和設備驅動的注冊和注銷方法&#xff0c;I2C通信方法&#xff0c;與適配器無關的代碼以及探測設備等。(2) I2C控制器驅動(適配器)(3) I2C設備驅動二、重要的結構體i2c_adapter//i2c控制器(適配器)i…
閱讀更多...
Alpha-end

Alpha-end

前言 失心瘋病源10團隊代碼管理github個人感悟 肝不動了&#xff0c;肝不動了。明天如果見不到我&#xff0c;不要太想我。站立會議 隊名&#xff1a;PMS530雨勤&#xff08;組長&#xff09; 今天完成了那些任務 熬夜肝代碼代碼簽入github明天的計劃 肝到凌晨還剩下哪些任務 團…
閱讀更多...
html 01前沿-web介紹

html 01前沿-web介紹

1. 認識網頁 網頁主要由文字、圖像和超鏈接等元素構成。當然&#xff0c;除了這些元素&#xff0c;網頁中還可以包含音頻、視頻以及Flash等。 2. 瀏覽器&#xff08;顯示代碼&#xff09; 瀏覽器是網頁顯示、運行的平臺&#xff0c;常用的瀏覽器有IE、火狐&#xff08;Firefox…
閱讀更多...
避免寫慢SQL

避免寫慢SQL

最近在整理數據庫中的慢SQL&#xff0c;同時也查詢了相關資料。記錄一下&#xff0c;要學會使用執行計劃來分析SQL。 1. 為查詢緩存優化你的查詢 大多數的MySQL服務器都開啟了查詢緩存。這是提高性最有效的方法之一&#xff0c;而且這是被MySQL的數據庫引擎處理的。當有很多相同…
閱讀更多...
為什么子孫后代會討厭使用java.util.Stack

為什么子孫后代會討厭使用java.util.Stack

在我用無意義的重言式殺死你之前&#xff0c;這是要點 如果您的應用程序接近實時&#xff0c;或者將代碼發送到Mars&#xff0c;則需要保留Java中默認的Stack實現。 根據LinkedList編寫您自己的版本。 同樣&#xff0c;如果您的應用程序是關鍵任務&#xff0c;并且希望堆棧由…
閱讀更多...
play 連接mysql_Play framework 2.x 連接mysql | 學步園

play 連接mysql_Play framework 2.x 連接mysql | 學步園

筆者所使用的系統為64位 windows7。本文假設java1.5版本以上環境已經搭好&#xff0c;play 框架已經下載至本地。首先我們創建一個項目。命令行進入play的目錄命令&#xff1a;play new demo再次輸入項目名字輸入2 選擇java項目創建完成界面OK&#xff0c;一個play框架下的java…
閱讀更多...
rpm -e --nodeps_微課 | rpm的思維導圖

rpm -e --nodeps_微課 | rpm的思維導圖

前導課程&#xff1a;微課 | rpm的查詢、升級與卸載命令本次微課將演示使用xmind繪制rpm思維導圖的過程&#xff0c;包括視頻文字&#xff0c;大約需要你10分鐘。另外&#xff0c;文末還有一則IT冷笑話&#xff0c;學習之余、會心一笑:)這個思維導圖將包含以下內容&#xff1a;…
閱讀更多...
CentOS7搭建lamp環境

CentOS7搭建lamp環境

Mysql安裝 CentOS 7 版本將MySQL數據庫軟件從默認的程序列表中移除&#xff0c;用mariadb代替了。MariaDB數據庫管理系統是MySQL的一個分支&#xff0c;主要由開源社區在維護&#xff0c;采用GPL授權許可。開發這個分支的原因之一是&#xff1a;甲骨文公司收購了MySQL后&#x…
閱讀更多...
border-sizing屬性詳解和應用

border-sizing屬性詳解和應用

box-sizing用于更改用于計算元素寬度和高度的默認的 CSS 盒子模型。它有content-box、border-box和inherit三種取值。inherit指的是從父元素繼承box-sizing表現形式&#xff0c;不再冗贅。1. 屬性講解 content-box 默認值&#xff0c;也是css2.1中的盒子模型。在計算 width和…
閱讀更多...
Couchbase：使用Twitter和Java創建大型數據集

Couchbase：使用Twitter和Java創建大型數據集

在播放/演示Couchbase或任何其他NoSQL引擎時&#xff0c;創建大型數據集的一種簡單方法是將Twitter feed注入到數據庫中。 對于這個小應用程序&#xff0c;我正在使用&#xff1a; Couchbase Server 2.0服務器 Couchbase Java SDK &#xff08;將由Maven安裝&#xff09; T…
閱讀更多...
查找標題已知的窗口句柄，遍歷窗口控件句柄

查找標題已知的窗口句柄，遍歷窗口控件句柄

有了回調函數的概念及上面的例子,我們可以繼續了。其實想要找到一個標題已知的窗口句柄,用一個API函數就可以了:FindWindow. 其函數原形是: function FindWindow(lpClassName, lpWindowName: PChar): HWND; stdcall; lpClassName:窗口類名.如果只知道標題,可以為空.窗口類名可以…
閱讀更多...
西門子scl語言編程手冊_西門子SCL編程PEEK指令講解

西門子scl語言編程手冊_西門子SCL編程PEEK指令講解

單詞“peek”在英語中表示“偷看&#xff0c;瞥一眼”&#xff0c;在計算機編程中表示“讀取數據”。在西門子SCL編程中&#xff0c;PEEK指令可以用來讀取輸入緩存區(I)、輸出緩存區(Q)、位存儲區(M)及數據塊(DB)中的數據&#xff0c;常用作間接尋址。今天這篇文章&#xff0c;…
閱讀更多...
HTML第一章：初始HTML

HTML第一章：初始HTML

設置ws字體大小&#xff1a;左上角file-->Settings--->在搜索框中輸入font網頁的第一行一定是<!DOCTYPE html>&#xff1a;網頁聲明&#xff0c;代表這個頁面是h5頁面html標簽中的leng"en"&#xff1a;意思是網頁中會用到英文 <meta>&#xff1a;…
閱讀更多...
Guava的Collections2：過濾和轉換Java集合

Guava的Collections2：過濾和轉換Java集合

Groovy的便利之一是能夠通過Groovy的閉包支持輕松地對集合執行過濾和轉換操作。 Guava將對集合的過濾和轉換引入標準Java&#xff0c;這是本文的主題。 Guava的Collections2類具有兩個公共方法&#xff0c;這兩個方法都是靜態的。 方法filter&#xff08;Collection&#xff0…
閱讀更多...
釘釘機器人怎么設置自動回復_項目部署成功后觸發釘釘機器人發送消息提醒——入門配置...

釘釘機器人怎么設置自動回復_項目部署成功后觸發釘釘機器人發送消息提醒——入門配置...

釘釘建好一個群打開群設置, 找到群機器人添加一個你想要的機器人可以使用自定義自定義機器人可以自定義頭像,名字,生成一個webhook(https post的請求地址)到這里, 釘釘機器人設置好了,接下來我們對照文檔進行配置https://ding-doc.dingtalk.com/doc#/serverapi2/qf2nxq/XAzBI -…
閱讀更多...
mysql加鎖語法_MySql 加鎖問題

mysql加鎖語法_MySql 加鎖問題

1、設置非自動提交 set autocommit0; 這時候 for update才會起作用2、一般用法 set autocommit0; for update(加鎖) ; commit/rollback; set autocommit1;首先看一下&#xff0c;set autocommit0 后&#xff0c;執行哪些語句會自動加鎖&#xff0c;加的是什么鎖&#xff1f…
閱讀更多...
最新文章

Copyright @ 2022~2023