List之Stack源码分析

源码版本为JDK1.7.0_75。

该类继承自Vector，说明该类是可克隆的、可序列化的，且是同步的。

public class Stack<E> extends Vector<E>

构造函数

public Stack() {     }

 

入栈

/** * 将一个元素放入栈顶，通过vector类的addElement方法实现      * Pushes an item onto the top of this stack. This has exactly      * the same effect as:      * <blockquote><pre>      * addElement(item)</pre></blockquote>      *      * @param   item   the item to be pushed onto this stack.      * @return  the <code>item</code> argument.      * @see     java.util.Vector#addElement      */     public E push(E item) {         addElement(item);           return item;     }

 

出栈

/** * 删除栈顶元素并将其返回，使用peek方法获取栈顶元素，使用vector类的removeElementAt方法完成元素的删除      * Removes the object at the top of this stack and returns that      * object as the value of this function.      *      * @return  The object at the top of this stack (the last item      *          of the <tt>Vector</tt> object).      * @throws  EmptyStackException  if this stack is empty.      */     public synchronized E pop() {         E       obj;         int     len = size();           obj = peek();         removeElementAt(len - 1);           return obj;     }     /** * 查看栈顶元素，但不将其从栈顶删除，使用vector类的elementAt方法实现。      * Looks at the object at the top of this stack without removing it      * from the stack.      *      * @return  the object at the top of this stack (the last item      *          of the <tt>Vector</tt> object).      * @throws  EmptyStackException  if this stack is empty.      */     public synchronized E peek() {         int     len = size();           if (len == 0)             throw new EmptyStackException();         return elementAt(len - 1);     }

 

是否为空

/**      * Tests if this stack is empty.      *      * @return  <code>true</code> if and only if this stack contains      *          no items; <code>false</code> otherwise.      */     public boolean empty() {         return size() == 0;     }

 

搜索

/** * vector从n-1到0对应栈顶到栈底，因此在搜索时，应使用lastIndexOf方法      * Returns the 1-based position where an object is on this stack.      * If the object <tt>o</tt> occurs as an item in this stack, this      * method returns the distance from the top of the stack of the      * occurrence nearest the top of the stack; the topmost item on the      * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>      * method is used to compare <tt>o</tt> to the      * items in this stack.      *      * @param   o   the desired object.      * @return  the 1-based position from the top of the stack where      *          the object is located; the return value <code>-1</code>      *          indicates that the object is not on the stack.      */     public synchronized int search(Object o) {         int i = lastIndexOf(o);           if (i >= 0) {             return size() - i;         }         return -1;     }

 

 

318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]

Return 16

The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]

Return 4

The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]

Return 0

No such pair of words.

解题思路：

该题目意思是给定一个string数组，找出最大的乘积(length(word[i])*length(word[j]))，同时word[i]与word[j]没有交集。

为了判断两个字符串是否有交集，首先将数组中的字符串用一个整数表示，整数中每一位对应一个小写字母。…..xxxxxxxxxxx对应……….fedcba。两个字符串是否有交集则将对应的整数进行与运算，若结果不为0，说明有交集。

由于在寻找最大乘积时，会频繁用到字符串的长度，因此可提前使用数组保存字符串长度（该过程在一定程度上会减少运行时间）

使用指针指向固定大小的数组相比于使用vector划分固定大小的数组，运行时间较少。

#include<vector> #include<string> #include<iostream> #include<algorithm> using namespace std; class Solution { public:     int maxProduct(vector<string>& words) {         int n=words.size();         if(n<2)return 0;         // 'vector<int>res' costs 20ms more than using 'int*res=new int[n]'         //vector<int>res=vector<int>(n,0);         int*res=new int[n];         // using array len to store the length of words,it can improve the time.         int*len=new int[n];         for(int i=0;i<n;i++){             //string word=words[i];             //transform(word.begin(),word.end(),word.begin(),::tolower);             res[i]=0;             len[i]=words[i].size();             int l=words[i].size();             for(int j=0;j<l;j++){                 res[i]|=1<<(words[i][j]-'a');             }             //res[i]=bit;             //cout<<bit<<endl;         }         int max=0;         for(int i=0;i<n;i++){             for(int j=i+1;j<n;j++)                 if(!(res[i]&res[j])){                     int tmp=len[i]*len[j];                     if(max<tmp)max=tmp;                 }         }         return max;     } }; //int main(){ //  vector<string>v; //  int n; //  cin>>n; //  for(int i=0;i<n;i++){ //      string tmp; //      cin>>tmp; //      v.push_back(tmp); //  } //  Solution test=Solution(); //  cout<<test.maxProduct(v)<<endl; //  system("pause"); //  return 0; //}